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?

$\endgroup$
7
  • $\begingroup$ +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). $\endgroup$
    – Srivatsan
    Nov 9, 2011 at 14:43
  • $\begingroup$ 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. $\endgroup$
    – p.s.
    Nov 9, 2011 at 14:44
  • $\begingroup$ @Srivatsan thanks for the question cleanup. How are you getting the matrix formatting? $\endgroup$
    – Mr.Wizard
    Nov 9, 2011 at 14:54
  • $\begingroup$ 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). $\endgroup$ Nov 9, 2011 at 15:04
  • $\begingroup$ I think that this should be related to the steady-state distribution of the corresponding Markov chain. $\endgroup$
    – Phira
    Nov 9, 2011 at 15:15

1 Answer 1

6
$\begingroup$

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

$\endgroup$
3
  • $\begingroup$ Thank you, Sasha. 10K+ over here I see. :-) $\endgroup$
    – Mr.Wizard
    Nov 9, 2011 at 17:24
  • $\begingroup$ Sasha, I'm wondering: is there any way to use LinearSolve for this? $\endgroup$
    – Mr.Wizard
    Jan 17, 2013 at 8:50
  • $\begingroup$ @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. $\endgroup$
    – Sasha
    Jan 17, 2013 at 15:43

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .