9
$\begingroup$

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?

  • 0
    @HenningMakholm The Markov chain interpretation might correspond to a symmetric matrix that is manipulated simultaneously on rows and columns.2011-11-09

1 Answers 1

6

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

Alternative algorithm may be in solving the system of quadratic equations:

enter image description here

  • 0
    @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.2013-01-17