Incomplete Confusion Matrices

226 Views Asked by At

Are the elements of an $n\times n$ matrix uniquely described by the sums of the rows, the sums of the columns, and the elements along the main diagonal?

In other words, say I have the following matrix:

\begin{array}{|c|c|c|c|c|} \hline \color{red}{a_{1,1}}&a_{1,2}& a_{1,3} & a_{1,4} & a_{1,5} \\ \hline a_{2,1}&\color{red}{a_{2,2}}& a_{2,3} & a_{2,4} & a_{2,5} \\ \hline a_{3,1}&a_{3,2}& \color{red}{a_{3,3}} & a_{3,4} & a_{3,5} \\ \hline a_{4,1}&a_{4,2}& a_{4,3} & \color{red}{a_{4,4}} & a_{4,5} \\ \hline a_{5,1}&a_{5,2}& a_{5,3} & a_{5,4} & \color{red}{a_{5,5}} \\ \hline \end{array}

but I only know each of $\color{red}{a_{1,1}},\color{red}{a_{2,2}},\color{red}{a_{3,3}},\color{red}{a_{4,4}},\color{red}{a_{5,5}}$, as well as the sums of each row and column.

Can $a_{m,n}$ be recovered for arbitrary $m,n$ ?

2

There are 2 best solutions below

0
On BEST ANSWER

From a dimensional point of view, the answer is generally "no". You have $n$ column sums, $n$ row sums, and $n$ entries along the diagonal, for a total of $3n$ "knowns". On the other hand, you have a total of $n^2$ unknown matrix entries. Taken together, this represents a system of $3n$ [linear] equations with $n^2$ unknowns. For sufficiently large values of $n$ (say, $n>3$), we have $$ 3n < n^2, $$ which means that the system will be underdetermined in these cases. In an underdetermined linear system, once you have one solution, you have infinitely many solutions, hence you will not, generally speaking, be able to uniquely pin down the matrix. Explicit counter-examples can be constructed via the procedure in Mike Earnest's comment: add a constant to $a_{1,3}$ and $a_{2,4}$ and subtract the same constant from $a_{1,4}$ and $a_{2,3}$.

Even in the $3\times 3$ case (which isn't addressed by the above argument), it is possible to construct counter-examples (Omnomnomnom gives a good one in their answer—more generally, take any magic square its transpose). In the $2\times 2$ case, the sums and diagonal are sufficient (indeed, they are more than sufficient): suppose that we have a matrix given by $$\begin{pmatrix} a & b \\ c & d \\ \end{pmatrix},$$ where $a$ and $b$ are known, and we are given \begin{align*} a + b &= k, \\ c + d &= \ell, \\ a + c &= m, \\ b + d &= n, \end{align*} where $k$, $\ell$, $m$, and $n$ are known values. Note that these equations give an overdetermined system (since $b$ and $c$ are the only unknowns). These typically don't have solutions, but if we assume that we are in a case such that a solution exists, it will be unique: we must have $$b = k-a = n-d \qquad\text{and}\qquad c = \ell-d = m-a.$$

Finally, in the $1\times 1$ case, it is (I hope) obvious that any one column sum, row sum, or diagonal uniquely determines the matrix.

0
On

The answer is no. For instance: in the $n = 3$ case, the matrices $$ \pmatrix{8&1&6\\3&5&7\\4&9&2}, \quad \pmatrix{8&3&4\\1&5&9\\6&7&2} $$ are distinct but share diagonal entries and row/column sums.