6

Given a non-negative real matrix $A \in \Bbb R_+^{m \times n}$, how do I convert it to a doubly stochastic matrix (each row and column sums to $1$)

$$\sum_{j=1}^n A_{ij}= 1, \qquad \forall i = 1, \dots, m \tag{row sum}$$

$$\sum_{i=1}^m A_{ij}= 1, \qquad \forall j = 1, \dots, n \tag{column sum}$$

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

Rodrigo de Azevedo
  • 20,693
  • 5
  • 43
  • 100
Learner
  • 2,616
  • 1
  • 25
  • 37
  • What do you mean by "convert"? What should be the relationship between the original matrix and the new one? – Nate Eldredge Aug 07 '12 at 15:43
  • @NateEldredge by convert i mean $f(A)$ should result in doubly stochastic matrix – Learner Aug 07 '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 08 '12 at 02:18
  • @GerryMyerson Do you know any reference where it has been proved. I guess proof must be very much simple – Learner Aug 08 '12 at 06: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 08 '12 at 08:24
  • You got it, Learner. – Gerry Myerson Aug 08 '12 at 13:11
  • @RodrigodeAzevedo Please don't make purely cosmetic edits to (ten year) old posts. It puts them on the active queue, where they distract from new postings. – Ethan Bolker May 05 '23 at 19:50
  • @EthanBolker Adding tags is not a purely cosmetic edit. It is how one can find duplicates and prevent answering the same questions over and over again. – Rodrigo de Azevedo May 05 '23 at 20:00

1 Answers1

11

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.

Christian Blatter
  • 222,181
  • 13
  • 176
  • 441
  • Thanks for your reference. Anything similar on rectangular matrix? – Learner Aug 07 '12 at 16:16
  • A non-square matrix cannot be doubly stochastic. A doubly stochastic matrix $T$ should be able to define transition probability forward and backward $T^\top$ in time. If this matrix is not square, it means that in one of these directions some states are not used. Either there is an absorbing subspace forward in time, or there is a an absorbing subspace in the time-reversed process. In any case $\mathbb 1$ cannot be either a left or right eigenvector. – MRule Apr 01 '21 at 17:30