2

I have the following symmetric matrix

$$ \begin{pmatrix} 1 & 5 & 3 \\ 5 & 25 & 15 \\ 3 & 15 & 9 \\ \end{pmatrix} $$ whose rows and columns sum to 9, 45 and 27. I would like to transform this matrix such that the diagonal is zero, but the row and columns still sum to the same values as the original and the matrix is still symmetric. Is there an algorithm that can find such matrices?

For instance,

$$ \begin{pmatrix} 0 & 13.5 & -4.5 \\ 13.5 & 0 & 63/2 \\ -4.5 & 63/2 & 0 \\ \end{pmatrix} $$

However, all elements must be strictly non-negative. Can this be achieved?

RedPen
  • 581
  • no idea what transformations you would allow. The standard method for finding $P$ that makes $P^THP$ diagonal is at http://math.stackexchange.com/questions/1388421/reference-for-linear-algebra-books-that-teach-reverse-hermite-method-for-symmetr – Will Jagy Mar 10 '22 at 17:06
  • @WillJagy Thank you for the reference, I realise that is a further constraint, all elements must be non-negative! – RedPen Mar 10 '22 at 17:08
  • what does 'transformation' mean? Your first matrix is rank 1 and symmetric so it can be written as $\mathbf {xx}^T$. By any typical meaning of transformation, your resulting matrix should not increase in rank; but yours is non-zero with trace zero which results in a contradiction. – user8675309 Mar 10 '22 at 17:23
  • $(1)$ Must the new matrix be symmteric again ? $(2)$ If you only allow non-negative entries (by the way, "strictly" can be omitted in this terminology) , the original matrix must satisfy some additional conditions. – Peter Mar 10 '22 at 17:58

2 Answers2

2

As you want to obtain the column/row sum, the symmetry and positivity you can start by combinatorics. Fortunately you don't have many possibilities. Let's start with the first row/column. By having zero on the diagonal, the numbers $5$ and $3$ have to be replace by two which sum up to $9$ $$ \begin{pmatrix} 0 & 0 & 9 \\ 0 & 0 & . \\ 9 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 1 & 8 \\ 1 & 0 & . \\ 8 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 2 & 7 \\ 2 & 0 & . \\ 7 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 3 & 6 \\ 3 & 0 & . \\ 6 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 4 & 5 \\ 4 & 0 & . \\ 5 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 5 & 4 \\ 5 & 0 & . \\ 4 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 6 & 3 \\ 6 & 0 & . \\ 3 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 7 & 2 \\ 7 & 0 & . \\ 2 & . & 0 \\ \end{pmatrix}, \begin{pmatrix} 0 & 8 & 1 \\ 8 & 0 & . \\ 1 & . & 0 \\ \end{pmatrix} \text{ or } \begin{pmatrix} 0 & 9 & 0 \\ 9 & 0 & . \\ 0 & . & 0 \\ \end{pmatrix}. $$ In the next step you want to get $45$ in the second row, which impossible under the constraint that the last row has to sum up to $27$. As there is no such matrix, there can't be any transformation.

EDIT: As you don't allow only natrual number, consider the following case. By this you also see that it is impossible for real nonnegative numbers: $$\begin{pmatrix} 0 & 9-a & a \\ 9-a & 0 & 36+a \\ a & 36+a & 0 \\ \end{pmatrix} \text{ for } a\in[0,9]. $$

mag
  • 2,409
  • Thank you for your answer, is there a way to solve this for real nonnegative numbers such that the diagonals are vanishingly small $\epsilon\approx 0$, if so, how can I solve this system? – RedPen Mar 10 '22 at 21:47
2

In 3 by 3, the space of symmetric matrices with all row sums and column sums zero is dimension 3. The letters I used gave such a matrix as $$ \left( \begin{array}{c|c|c} -c-d&d&c\\ \hline d&-d-b&b\\ \hline c&b&-b-c\\ \end{array} \right) $$

Any symmetric matrix with the prescribed row and column sums differs from your original by one of the above displayed matrices. As you demand all $0$ on the diagonal, the values of my $b,c,d$ are prescribed by linear equations. Here $b = \frac{33}{2} \; , \; \; \; \; $ $c = \frac{-15}{2} \; , \; \; \; \; $ $d = \frac{17}{2} \; , \; \; \; \; $

This gives your second matrix, the only possibility.

Worth your time to write out a proof for dimension and a parametrization of the row sum zerp/column sumzero/symmetric

Will Jagy
  • 139,541
  • Thank you for your answer, is there a way to solve this for real nonnegative numbers such that the diagonals are vanishingly small $\epsilon\approx 0$, if so, how can I solve this system? – RedPen Mar 10 '22 at 21:48