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

227 Solutions
42 Solvers

Last Solution submitted on Nov 17, 2020

Last 200 Solutions

Problem Comments

2 Comments

2 Comments

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?

Andrea Caruso on 7 Nov 2020 at 11:38

Nice problem

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 Solvers42

Problem Tags

matrices

Community Treasure Hunt

Find the treasures in MATLAB Central and discover how the community can help you!

Start Hunting!

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers42

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

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

Solution Stats

Last 200 Solutions

Problem Comments

Solution Comments

Problem Recent Solvers42

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players