2
$\begingroup$

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?

  • 0
    What do you mean by "convert"? What should be the relationship between the original matrix and the new one?2012-08-07
  • 0
    @NateEldredge by convert i mean $f(A)$ should result in doubly stochastic matrix2012-08-07
  • 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.2012-08-08
  • 0
    @GerryMyerson Do you know any reference where it has been proved. I guess proof must be very much simple2012-08-08
  • 0
    @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.2012-08-08
  • 0
    You got it, Learner.2012-08-08

1 Answers 1

4

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.

  • 0
    Thanks for your reference. Anything similar on rectangular matrix?2012-08-07