0
$\begingroup$

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$ ?

$\endgroup$
4
  • 2
    $\begingroup$ From a purely dimensional point of view, the answer seems to be "no". You have $2n+1$ row, column, and diagonal sums, but $n^2$ entries which need to be determined. Hence you have a system of $2n+1$ equations in $n^2$ variables, which is under-determined for most values of $n$. $\endgroup$
    – Xander Henderson
    Jul 3, 2018 at 22:02
  • $\begingroup$ I meant to say that I know each individual value along the main diagonal. so $3n$ values. $\endgroup$
    – David Diaz
    Jul 3, 2018 at 22:09
  • 1
    $\begingroup$ @DavidDiaz even so: for sufficiently large $n$, $3n < n^2$. $\endgroup$ Jul 3, 2018 at 22:14
  • 1
    $\begingroup$ Given any solution $a_{i,j}$ to your constraints, then adding some number $c$ to both $a_{1,3}$ and $a_{2,4}$, while subtracting $c$ from $a_{1,4}$ and $a_{2,3}$, gives a new solution to the constraints. $\endgroup$ Jul 3, 2018 at 22:15

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
1
$\begingroup$

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .