Sender: Guy
Subject: Matrix Reconstruction

Is there a way to get the sums of rows, columns and diagonals of an n x n matrix to reconstruct the original matrix?

For larger matrices the answer is NO. I am NOT sure what is meant by a diagonal - but a will give a quick argument that includes the most generous interpretation (all sums of entries which are parallel to a main diagonal).

You are trying to determine all nxn entries in the matrix. Each SUM is a linear equation in these entries. So, to have a chance, you will need to have nxn independent equations.

Any way, you have n sumes of rows, n sums of columns. With a generous interpretation of diagonals, you have 2n-1 diagonals in each direction.

Over all, this gives 4n-2 linear equations. As noted above, these are NOT all independent. Clearly if n >= 4, then there are NOT ENOUGH LINEAR EQUATIONS. I think with n=3 there are not enough independent equations either. However, for n=2, there ARE enough, just with the main diagonal and the row and column sums.

Again the fact that they are NOT independent means that if you are given ALL the sums, they must satisfy some conditions to have ANY solutions. E.g. if all row sums are 0 and all column sums are 1, there are no solutions!

I'm not clear what exactly you mean by "diagonals", do you mean e.g. all diagonals traversing the matrix in a top/left to bottom/right direction, or do you mean just the two main diagonals forming a "cross"? I will use the first interpretation in what follows.

In either case though, for large enough n the answer is definitely "no". One easy way to see this is to consider the number of entries in, say, a 4*4 matrix, and compare it to the total number of rows/columns/diagonals. There are 16 entries, yet only 4+4+4=12 sums. Hence there will be matrices with different entries that will produce exactly the same sums. An easy example is the following:

Compare

0 0 0 0
0 0 0 0
0 0 0 0
0 0 0 0

with

 1  0 -1  0
 0 -1  0  1
-1  0  1  0
 0  1  0 -1

Both matrices have rows, columns, and diagonals (my interpretation) with sums zero, yet they are obviously two different matrices. If you were just given the sums (all zero), you would have no way of knowing which of these two (or many other) matrices you originally were working with.

You can easily reconstruct matrices if they are 2x2, and (I think) with somewhat more difficulty 3x3 depending on which interpretation of "diagonals" you use.

Hope this helps,
Patrick