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

Created by Ned Gulley

Consider a matrix x

 x = [ 1 2 0
       0 5 0 
       3 0 8 ]

If we sum x along the rows we get

 row_sums = [3 5 11]

Summing along the columns gives

 col_sums = [4 7 8]

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 CAT scan. Can you put all the bones in the right place?

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.

Bonus question: Under what circumstances does the answer become unique? Discuss.

Problem Group

Community

Solve This Now!

6 solvers submitted 27 solutions (4.5 solutions/solver).

Solution Map Solution List Solvers

Problem Comments

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?

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

Tags

Problem Group

6 solvers submitted 27 solutions (4.5 solutions/solver).

Problem Comments