Problem 1286. MatCAT - Reconstruct X from Its X-rays

Created by Ned Gulley

Solve Later

{"relationships":[{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/document","targetMode":"","relationshipId":"rId1","target":"/matlab/document.xml"},{"relationshipType":"http://schemas.mathworks.com/matlab/code/2013/relationships/output","targetMode":"","relationshipId":"rId2","target":"/matlab/output.xml"}],"parts":[{"partUri":"/matlab/document.xml","relationship":[],"contentType":"application/vnd.mathworks.matlab.code.document+xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\"?>\n<w:document xmlns:w=\"http://schemas.openxmlformats.org/wordprocessingml/2006/main\"><w:body><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Consider a matrix x</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ x = [ 1 2 0\n       0 5 0 \n       3 0 8 ]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>If we sum x along the rows we get</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ row_sums = [3 5 11]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Summing along the columns gives</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"code\"/></w:pPr><w:r><w:t><![CDATA[ col_sums = [4 7 8]]]></w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Metaphorically, we might call these sums \"x-rays\". Your job is to take these x-rays and reconstruct the matrix x being x-rayed, in the fashion of a</w:t></w:r><w:r><w:t> </w:t></w:r><w:hyperlink w:docLocation=\"http://en.wikipedia.org/wiki/X-ray_computed_tomography\"><w:r><w:t>CAT scan</w:t></w:r></w:hyperlink><w:r><w:t>. Can you put all the bones in the right place?</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>All matrix elements must be non-negative integers. There is no guarantee of a unique answer. I will only check that the row and column sums match the supplied matrix, and that your elements are non-negative integers.</w:t></w:r></w:p><w:p><w:pPr><w:pStyle w:val=\"text\"/></w:pPr><w:r><w:t>Bonus question: Under what circumstances does the answer become unique? Discuss.</w:t></w:r></w:p></w:body></w:document>"},{"partUri":"/matlab/output.xml","contentType":"text/xml","content":"<?xml version=\"1.0\" encoding=\"UTF-8\" standalone=\"no\" ?><embeddedOutputs><metaData><evaluationState>manual</evaluationState><layoutState>code</layoutState><outputStatus>ready</outputStatus></metaData><outputArray type=\"array\"/><regionArray type=\"array\"/></embeddedOutputs>"}]}

Solve

Solution Stats

201 Solutions
64 Solvers

Last Solution submitted on Sep 11, 2020

Last 200 Solutions

Problem Comments

1 Comment

1 Comment

Alfonso Nieto-Castanon on 24 Feb 2013

regarding the discussion question, my guess is that the only cases where the answer becomes unique are those 'trivial' single-vector or equivalent cases. More precisely those cases where min(nnz(row_sums),nnz(col_sums))<=1. The reasons is that if one solution exist where x(a,b)>0 and x(c,d)>0 (and a~=c and b~=d; i.e. they are not in the same row or column), then you could simply subtract one from x(a,b) and x(c,d), and add one to x(c,b) and x(a,d), and the result will also be a valid solution... thoughts?

Solution Comments

Solution 1191720

1 Comment

1 Comment

Andrew Newell on 18 May 2017

I confess, I found the results using intlinprog.

Solution 208042

1 Comment

1 Comment

Andrew Newell on 18 May 2017

I would love to know how you came up with that.

Problem Recent Solvers64

Problem Tags

matrices

Problem 1286. MatCAT - Reconstruct X from Its X-rays

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers64

Suggested Problems

More from this Author50

Problem Tags

Problem 1286. MatCAT - Reconstruct X from Its X-rays

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers64

Suggested Problems

More from this Author50

Problem Tags

Players