4

I realize that a matrix of objects, where each slot could either be occupied or empty, is impossible to resolve if you are only given the amount of occupied slots in each row and each column.

Ex: A $2 \times 2$ matrix with one object in each column and one in each row could be:

$$ \begin{pmatrix} 0 & 1 \\ 1 & 0 \end{pmatrix}$$ Or $$ \begin{pmatrix} 1 & 0 \\ 0 & 1 \end{pmatrix}$$

My question is, if the amount of objects in all of the possible diagonals is also known, can the contents of the matrix then always be known? If not, is there a sizelimit where the ambiguity starts?

Chappers
  • 67,606
Johan
  • 41
  • What do you mean by "all possible diagonals"? Just the two primary diagonals, or the $n$ forward diagonals that "wrap around" the matrix as well as the $n$ backward diagonals? – Rory Daulton Jun 07 '15 at 19:38
  • I mean not just the two primary ones. I don't know all the appropriate terms yet. A 2 x 2 matrix would have three possible "Up-Left" and three possible "Down-Left" diagonals. – Johan Jun 07 '15 at 19:40
  • So, what @Rory was describing, but without the wrap around. This is different than the situation that coffee describes. It sounds like you are describing the situation where you know the multiset of objects in each R, C, & D, but not the list, so you cant associate the number of entries in a diagonal with the diagonal they are in. Does that make sense? If yes, is it what you mean? – Eric Stucky Jun 08 '15 at 01:29
  • @EricStucky I just added a cutoff discussion for the case where the diagonals do not wrap around. Seems the same cutoff $n\le 3$ occurs there, i.e unique for $n \le 3$ but for $n=4$ there are two different having the same row/column and non-wrap diagonal sums. – coffeemath Jun 08 '15 at 08:00
  • @EricStucky On re-reading your comment above, if one does not insist that corresponding rows/columns or diagonals have equal sums, but only that the multiset of these are equal for the two matrices, then e.g. if the diagonals do not wrap then each of the 2x2 matrices [1,0;0,1] and [0,1;1,0] gives the same multiset of three $0$'s, six $1$'s and one $2$ for the sums. This would make $n=1$ the "cutoff", The same two matrices give equal multisets of sums provided the diagonals wrap. – coffeemath Jun 08 '15 at 08:29
  • @EricStucky Yes, the diagonal only goes to the edge, and then it ends. In each row, column and diagonal the number of entries is known, but not their location. I guess that means that it is not a list? – Johan Jun 09 '15 at 11:16
  • @coffeemath The matrices should have the same entries, at the same locations. Their rows, columns and diagonals would thus need to have equal sums. And I don't agree with you about n = 1 being the cutoff. In my example with the two 2 x 2 matrices, both would have 1's as the sum in each column and row, but the first would have 1 in its first "up-right" diagonal, then a 0, then a 1. Its "down-right" diagonals would be 0,2,0. Whereas those six diagonals in the other matrix would be 0,2,0,1,0,1. It's the same values, but different order, which lets you distinguish between the two matrices. – Johan Jun 09 '15 at 11:30
  • @Johan My statements about $n=1$ being a kind of cutoff was about the multisets of sums obtained. So this means what you call the order of the values in the above comment is being ignored. Note that this multiset approach was not an interpretation of your original posted question, only one of the other versions referred to by Eric Stucky in a comment he made. – coffeemath Jun 09 '15 at 11:55

1 Answers1

1

For $n=3$ the sums of rows, columns, and wrap-around diagonals determine the matrix, even over the reals, since if we define one sum as that of all the entries, and then two each of rows and columns, and two each of left. respectively right diagonals this is nine equations, whose determinant is $27.$ Note that e.g. there is no need to include the sum of the third row since it is a consequence of the overall sum and that of the other two rows.

For $n=4$ there is the following example built on block $2 \times 2$ matrices. Let $I$ be the (2 by 2) identity, $J$ the complement of that (i.e. rows $0,1;1,0$). Also let $Z$ be the zero matrix and $M_1$ the matrix of all $1$'s.

Form matrix $A$ with block rows $I,Z;M_1,J$ and matrix $B$ the same as matrix $A$ but with the positions of blocks $I,J$ switched.

Then for each of matrices $A,B$ the sums across are $1,1,3,3$ and down are $3,3,1,1$ while all the wraparound diagonals of either $A$ or $B$ have sum $2.$

Added: for convenience here are the two matrices $A,B.$

$$A=\begin{pmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 \end{pmatrix} $$ and

$$B=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 \end{pmatrix} $$

Another interpretation: If by the diagonals the OP does not mean for them to "wrap around", so that they stop where they hit the edges of the matrix, then the "cutoff" is still $n=3$. Two matrices of size $3 \times 3$ with all the corresponding row or column or diagonal sums equal are easily seen to be the same entry by entry, as if they are [a,b,c;d,e,f;g,h,i] and [a',b',c';d',e',f';g',h',i'] then the equality of corresponding length 1 diagonals gives a=a',c=c',g=g',i=i', and then equality of corresponding row sums implies b=b' and h=h', also equality of corresponding column sums gives d=d' and f=f', and finally equality of say the corresponding center row sums gives the remaining e=e'.

For $n=4$ there are the following two matrices $C,D$ having all the corresponding sums of rows, columns, and non-wrapped diagonals equal.

$$C=\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 \end{pmatrix}$$

and

$$D\begin{pmatrix} 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 \end{pmatrix}$$

For each of these matrices, all row or column sums are $1$, while corresponding "non-wrapped" diagonals have the same sums, specifically the length 1 diagonals have sum $0$, the length 2 or 3 diagonals have sum $1$, and the length 4 diagonals all have sum $0.$

PS: I noticed later that matrices $C,D$ also work as examples where corresponding rows, columns, and wrap-around diagonals all have the same sum. (Making the above example of $A,B$ unnecessary...)

coffeemath
  • 29,884
  • 2
  • 31
  • 52
  • Thanks, you have demonstrated nicely that even a 4 x 4 matrix can not be defined from the sums I asked about. I do notice though, that the two 4 x 4 matrices are the same but rotate, so maybe the general appearence of the matrix can be known, but it's orientation is uncertain? – Johan Jun 09 '15 at 11:08
  • @johan I enjoyed this problem (upvoted it before). I think the $C,D$ matrices can be generalized to higher dimensions by inserting middle rows/columns of all zeroes, though I haven't completely checked that. – coffeemath Jun 09 '15 at 11:11
  • @Johan I do not know about the rotation aspect, that is, whether one can get a 4 by 4 matrix from its row, column, diagonal sums "up to a rotation" of the matrix. Seems to me that would be difficult to show even if it is true. I think the matrices $A,B$ above aren't rotations of each other, except in a kind of block sense. – coffeemath Jun 09 '15 at 12:00