Normalize row and column sums of a symmetric matrix

120 Views Asked by At

This is a slightly stupid question, and I am quite embarrassed that I cannot answer it.

Let $A = (a_{ij})_{ij}$ be a a symmetric matrix. Is it always possible to find a matrix $S$ such that for $A' = (a'_{ij}))_{ij} = SAS^T$ such that the row and column sums satisfy

$$\sum_{i} a'_{ij} = \sum_{i} a'_{ji} = 1$$

for all $j$? If not, is there a conditition under which this becomes possible?

1

There are 1 best solutions below

1
On

$ \def\o{{\tt1}} $Your question is related to the Sinkhorn Theorem which says that diagonal matrices $(D_1,D_2)$ exists such that $D_1AD_2$ is doubly stochastic.

It is not necessary that $D_1=D_2$ even if $A$ is symmetric.
For example $$\eqalign{ A &= \left[ \begin{array}{ccc} 0.42 & 0.14 & 0.20 \\ 0.14 & 0.24 & 0.41 \\ 0.20 & 0.41 & 0.20 \\\end{array} \right], \qquad D_1AD_2 = \left[ \begin{array}{ccc} 0.5631 & 0.1837 & 0.2531 \\ 0.1837 & 0.3083 & 0.5079 \\ 0.2531 & 0.5079 & 0.2389 \\\end{array} \right] \\ \\ D_1 &= {\rm Diag}\big(1.30561,\quad 1.27800,\quad 1.232420\big) \\ D_2 &= {\rm Diag}\big(1.02695,\quad 1.00523,\quad 0.969383\big) \\ }$$ which was calculated using a standard Iterative Proportional Fitting algorithm.

The desired form $(SAS^T)$ can be obtained by setting $$\eqalign{ S &= \sqrt{D_1D_2} \\ &= {\rm Diag}\big(1.15793,\quad 1.13344,\quad 1.09302\big) \\ }$$