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

538 Solutions
95 Solvers

Last Solution submitted on Apr 22, 2023

Last 200 Solutions

Problem Comments

4 Comments

4 Comments

Show 1 older 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?

Andrea Caruso on 7 Nov 2020

Nice problem

锦 on 30 Jul 2022

good problem.

Armando Longobardi on 11 Nov 2022

See also this: https://it.mathworks.com/matlabcentral/cody/problems/47618

There is a nice video explaining how to solve these problems.

Solution Comments

Show comments

Problem Recent Solvers95

Problem Tags

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 Solvers95

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 Solvers95

Suggested Problems

More from this Author50

Problem Tags

Community Treasure Hunt

Players