6
$\begingroup$

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$...

Improve this question
$\endgroup$
5
  • $\begingroup$ Does 'transition' just mean "permutation of a set of matrices"? How are your transitions defined when the relevant sums are 0? $\endgroup$
    – LSpice
    Dec 28, 2019 at 18:26
  • $\begingroup$ A column is never equal to 0. I even barely never have 0 as coefficient, but I added some in my example to make it easier to understand and manipulate. $\endgroup$
    – Axel Carré
    Dec 28, 2019 at 18:32
  • $\begingroup$ @LSpice: It is reasonable to assume the OP takes the numbers to be $\ge 0$. If a row or column is identically $0$ then the corresponding transition is defined to leave it as it is. No, "transition" means either the operation $t$ or $t'$ applied to some given matrix. $\endgroup$
    – Alex M.
    Dec 28, 2019 at 18:33
  • $\begingroup$ I actually does $t$ $t'$ a infinite number of times, and the output finally never changes (even thought I never really get to it). $\endgroup$
    – Axel Carré
    Dec 28, 2019 at 18:38
  • 1
    $\begingroup$ As with many problems of this type, finding the "limiting outcome" is much better done by finding 1) invariants of the transition, and 2) commonalities of fixed points. You have done the latter; there are enough of the former and latter to solve this in general. $\endgroup$
    – user44191
    Dec 28, 2019 at 20:00

2 Answers 2

Reset to default
5
$\begingroup$

When $E_0$ is square (i.e., $r = c$) this procedure is called Sinkhorn iteration or the Sinkhorn-Knopp algorithm (see this Wikipedia page). 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.

Improve this answer
$\endgroup$
1
$\begingroup$

The paragraph below applies to a different problem, where row normalization is split out from column normalization, so I have an $"E_{n+1/2}"$ which will be sometimes different from both $E_n$ and $E_{n+1}$. (If the starting matrix "looks like" an order k square stochastic matrix, then it will be invariant under both normalizations.)

Note that some cases will not converge to a single limit. Given a c by r matrix of all ones, normalizing by column (of r entries) results in all entries being 1/r, while normalizing by rows gives all entries being 1/c, so the sequence will fluctuate between these two. Except when the entries are all zero, I would expect a similar oscillation with any other starting nonzero binary matrix. You might be able to establish oscillation for matrices with more distinct values.

Getting back to the posted problem, the transformations have an invariance under permutations of rows, similarly of columns. Thus if the input looks like an upper two by two diagonal block matrix and a lower two by three nonzero matrix, the upper block may converge on a stochastic two by two block, while the lower will be influenced (if it converges at all) by a ratio of 3/2. So the block structure will influence the results, and the ratio c/r might not apply.

Gerhard "Goes This Way And That" Paseman, 2019.12.28.

Improve this answer
$\endgroup$
3
  • $\begingroup$ It turns out I am wrong; some binary matrices (and non binary too) stabilize: those with a nonzero upper k by k minor which are order k stochastic matrices, and zero elsewhere, are invariant under the transform. The oscillation occurs when the nonzero part is nonsquare. Gerhard "Is Shaping Up The Argument" Paseman, 2019.12.28. $\endgroup$
    – Gerhard Paseman
    Dec 28, 2019 at 21:22
  • 1
    $\begingroup$ Possibly the question changed between your post and now, but it looks like the original poster was considering "normalize by columns then normalize by rows" to be a single operation, so your example converges to the matrix with all entries = 1/r. $\endgroup$
    – Bill Bradley
    Dec 28, 2019 at 21:23
  • $\begingroup$ @Bill, indeed, I will edit to clarify my perception. Gerhard "Should Read Post More Carefully" Paseman, 2019.12.28. $\endgroup$
    – Gerhard Paseman
    Dec 28, 2019 at 21:29

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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