Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
+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

1 Answer 1

up vote 6 down vote accepted

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

share|improve this answer
    
Thank you, Sasha. 10K+ over here I see. :-) –  Mr.Wizard Nov 9 '11 at 17:24
    
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
    
Thanks, again.. –  Mr.Wizard Jan 17 '13 at 16:18

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.