Let $E\_0$ be a matrix with non-negative entries.


Given $E\_n$, we apply the following two operations in sequence to produce $E\_{n+1}$.


A. Divide every entry by the sum of all entries in its column (to make the matrix column-stochastic).


B. Divide every entry by the sum of all entries in its row (to make the matrix row-stochastic).


For example:


$E\_0=\begin{pmatrix}
\frac{2}{5} & \frac{1}{5} & \frac{2}{5} & 0 & 0\\ 
\frac{1}{5} & 0 & \frac{7}{10} & \frac{1}{10} & 0\\ 
0 & 0 & 0 & \frac{3}{10} & \frac{7}{10}
\end{pmatrix}\overset{A}{\rightarrow}\begin{pmatrix}
\frac{2}{3} & 1 & \frac{4}{11} & 0 & 0\\ 
\frac{1}{3} & 0 & \frac{7}{11} & \frac{1}{4} & 0\\ 
0 & 0 & 0 & \frac{3}{4} & 1
\end{pmatrix}\overset{B}{\rightarrow}\begin{pmatrix}
\frac{22}{67} & \frac{33}{67} & \frac{12}{67} & 0 & 0\\ 
\frac{44}{161} & 0 & \frac{12}{23} & \frac{33}{161} & 0\\ 
0 & 0 & 0 & \frac{3}{7} & \frac{4}{7}
\end{pmatrix}=E\_1$


What is the limit of $E\_n$ as $n \to \infty$?
----------------------------------------------




---


Additional remarks.


In my problem, the matrix has $c\in \{1,2,\dots,5\}$ rows and $r=5$ columns (note that the two letters are reversed, but in the original context of this problem these letters $r$ and $c$ do not actually stand for rows and columns). So $E\_0$ can be $1\times 5$, $2\times 5$, ... or $5\times 5$.


We denote with $(e\_n)\_{ij}$ the entries of $E\_{n}$; hence $(e\_n)\_{ij}\in[0;1]$ and $\forall i \sum\_{j=1}^{r}(e\_n)\_{ij}=1$ for $n>0$.


I managed to express $(e\_{n+1})\_{ij}$ as a function of $(e\_{n})\_{ij}$ :


$$(e\_{n+1})\_{ij}=\frac{\frac{(e\_{n})\_{ij}}{\sum\_{k=1}^{c}(e\_n)\_{kj}}}{\sum\_{l=1}^{r}\frac{(e\_n)\_{il}}{\sum\_{k=1}^{c}(e\_n)\_{kl}}}$$


What I can't seem to find now is an expression $(e\_{n})\_{ij}$ as a function of $(e\_{0})\_{ij}$, to be able to calculate $\underset{n \to +\infty }{lim}(e\_n)\_{ij}$


I wrote code to compute this iteration; when I ran it with the previous example $E\_0$, I found out that:


$E\_0=\begin{pmatrix}
\frac{2}{5} & \frac{1}{5} & \frac{2}{5} & 0 & 0\\ 
\frac{1}{5} & 0 & \frac{7}{10} & \frac{1}{10} & 0\\ 
0 & 0 & 0 & \frac{3}{10} & \frac{7}{10}
\end{pmatrix}\overset{n \rightarrow+\infty}{\rightarrow}E\_n=\begin{pmatrix}
\frac{7}{25} & \frac{3}{5} & \frac{3}{25} & 0 & 0\\ 
\frac{8}{25} & 0 & \frac{12}{25} & \frac{1}{5} & 0\\ 
0 & 0 & 0 & \frac{2}{5} & \frac{3}{5}
\end{pmatrix}$


Not only do the row sums equal $1$, but the column sums equal $\frac{3}{5}$: it seems that in this process column sums converge to $\frac{c}{r}$.


I'm not a mathematician so I was looking for a simple inductive proof. I tried to express $E\_2$ (and so on) as a function of $E\_0$, but it quickly gets overwhelming, starting from $E\_2$...



Limit of alternated row and column normalizations
When $E\_0$ is square (i.e., $r = c$) this procedure is called Sinkhorn iteration or the Sinkhorn-Knopp algorithm (see [this Wikipedia page](https://en.wikipedia.org/wiki/Sinkhorn%27s_theorem)). You can find a wealth of results by Googling those terms, the most well-known of which is that if $E\_0$ has strictly positive entries (and again, is square) then the limit of $E\_n$ indeed exists and is doubly stochastic.


