# Matrix algorithm convergence

Suppose I start with a $n \times n$ matrix of zeros and ones:

$$\begin{bmatrix} 0 & 0 & 0 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & 1 & 1\\ \end{bmatrix}$$

Then I normalize each row such that it sums to $1$:

$$\begin{bmatrix} 0.& 0.& 0.& 0.5& 0.5\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ 0.2& 0.2& 0.2& 0.2& 0.2\\ \end{bmatrix}$$

And then do the same for each column:

$$\begin{bmatrix} 0. & 0. & 0. & 0.384615 & 0.384615\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ 0.25& 0.25& 0.25& 0.153846& 0.153846\\ \end{bmatrix}$$

Repeat this process 15 times, and I have:

$$\begin{bmatrix} 0. & 0. & 0. & 0.5 & 0.5\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ 0.25& 0.25& 0.25& 0.125& 0.125\\ \end{bmatrix}$$

Assuming that the original matrix is such that this process is stable, each row and column in the final matrix should sum to $1$.

My questions:

• Is there a name for what this algorithm converges to, or something closely related?

• What algorithm will produce the same result but converge faster?

-
+1 I find the question very interesting. On a related note, if we can normalize the rows and columns in arbitrary order, I wonder whether the limiting matrix will be unique (assuming the limit exists). –  Srivatsan Nov 9 '11 at 14:43
It's almost alternating projections, but not quite because normalizing like that isn't exactly a projection. If you divided by the 2-norm instead of the 1-norm, it would be a projection. –  p.s. Nov 9 '11 at 14:44
@Srivatsan thanks for the question cleanup. How are you getting the matrix formatting? –  Mr.Wizard Nov 9 '11 at 14:54
If you start editing your question, you can see the source of the question. You can always cancel the edit afterward if you don't have any changes to make. (Also, credit for matrix formatting should go to ratchet freak rather than Srivatsan). –  Henning Makholm Nov 9 '11 at 15:04
I think that this should be related to the steady-state distribution of the corresponding Markov chain. –  Phira Nov 9 '11 at 15:15

The algorithm converges to a doubly stochastic matrix. Because normalizing rows and columns is equivalent to multiplying the original matrix on the left and on the right with some diagonal matrix (see Sinkhorn's theorem), the doubly stochastic matrix will be related to the original matrix $Z$ as $P_d = D_1 Z D_2$.
Sasha, I'm wondering: is there any way to use LinearSolve for this? –  Mr.Wizard Jan 17 '13 at 8:50
@Mr.Wizard I do not think so. For a $n\times n$ matrix, there are $2n$ linear equations, but generically about $n^2$ unknowns. Positivity constraints should play a role. I am not sure if values of the initial matrix elements matter, or whether the convergent only depends on the non-zero elements pattern. –  Sasha Jan 17 '13 at 15:43