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
    +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).2011-11-09
  • 0
    It's almost [alternating projections](http://www.stanford.edu/class/ee392o/alt_proj.pdf), 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.2011-11-09
  • 0
    @Srivatsan thanks for the question cleanup. How are you getting the matrix formatting?2011-11-09
  • 0
    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](http://math.stackexchange.com/suggested-edits/2966) rather than Srivatsan).2011-11-09
  • 0
    I think that this should be related to the steady-state distribution of the corresponding Markov chain.2011-11-09
  • 0
    @Phira, but exactly what is the corresponding Markov chain? Normalizing the rows can change the relative proportions within each column, and vice versa. I think, though that each normalization will decrease the _variance_ of all matrix entries totally, it if does anything at all. So at least it shouldn't get trapped in a cycle.2011-11-09
  • 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
    Thank you, Sasha. 10K+ over here I see. :-)2011-11-09
  • 0
    Sasha, I'm wondering: is there any way to use `LinearSolve` for this?2013-01-17
  • 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