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

436 Solutions
75 Solvers

Last Solution submitted on May 22, 2022

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

Nice problem

Solution Comments

Solution 6842954

1 Comment

1 Comment

Eric Le Saux on 4 May 2022 at 10:15

That's brilliant!

Solution 1215302

1 Comment

1 Comment

Shuvo Kumar Paul on 27 Jul 2021

Hello, I am a beginner. I tried a lot but couldn't figure out the solution. Can you please help me with this problem?

Solution 1191720

1 Comment

1 Comment

Andrew Newell on 18 May 2017

I confess, I found the results using intlinprog.

Solution 208042

2 Comments

2 Comments

Andrew Newell on 18 May 2017

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

Daigo on 16 Jan 2022

I have no idea how you came up with this... So elegant.

Problem Recent Solvers75

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 Solvers75

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 Solvers75

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players