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.

Given a non-negative real matrix $A \in R_+^{m \times n}$, how do i convert the matrix to doubly stochastic matrix i.e, each row summed to 1 and each column sums to one. In math terms,
Row Sum : $\sum_{j=1}^n A_{ij}= 1, \forall i= 1 \cdots m$
Column Sum : $\sum_{i=1}^m A_{ij}= 1, \forall j= 1 \cdots n$

Is the conversion is possible? if not, can we find a nearest matrix which is doubly stochastic matrix?

share|improve this question
    
What do you mean by "convert"? What should be the relationship between the original matrix and the new one? –  Nate Eldredge Aug 7 '12 at 15:43
    
@NateEldredge by convert i mean $f(A)$ should result in doubly stochastic matrix –  Learner Aug 7 '12 at 16:18
1  
Note that it is impossible for all the row sums and all the column sums to be 1 if the matrix is not square. –  Gerry Myerson Aug 8 '12 at 2:18
    
@GerryMyerson Do you know any reference where it has been proved. I guess proof must be very much simple –  Learner Aug 8 '12 at 6:17
    
@GerryMyerson I did my best to prove the same. consider a rectangular matrix $A$ with dimension $m \times n$. Sum of row sums will be $m$ where as sum of column sums will be $n$. However we added all the entries in the matrix once which does not give rise to two numbers. Hence there wont be a rectangular matrix which is doubly stochastic. –  Learner Aug 8 '12 at 8:24

1 Answer 1

up vote 4 down vote accepted

There is a paper by Richard Sinkhorn: A relationship between arbitrary positive matrices and doubly stochastic matrices, The Annals of Mathematical statistics, 35 (1964), 876–879.

There he proves the following

Theorem. If $A$ is a square matrix with strictly positive entries then there are a unique doubly stochastic matrix $T_A$ and diagonal matrices $D_1$, $D_2$ such that $T_A=D_1AD_2$. The matrices $D_1$ and $D_2$ are themselves unique up to a scalar factor.

share|improve this answer
    
Thanks for your reference. Anything similar on rectangular matrix? –  Learner Aug 7 '12 at 16:16
1  
doubly stochastic matrices aren't even rectangular! –  Peter Sheldrick Aug 7 '12 at 16:57

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.