Let $M$ be an $n \times n$ nonnegative row-stochastic matrix, and let $M_i$ be the matrix whose $i$-th row is the same as that of $M$, and whose remaining rows are all the same as that of the identity matrix. For example, if $M = \begin{bmatrix} 1/6 & 2/6 & 3/6 \\ 4/15 & 5/15 & 6/15 \\ 7/24 & 8/24 & 9/24 \end{bmatrix}$, then $M_2 = \begin{bmatrix} 1 & 0 & 0 \\ 4/15 & 5/15 & 6/15 \\ 0 & 0 & 1 \end{bmatrix}$.
- Is there a clean expression for the sum of $M_{\pi(1)} M_{\pi(2)} \dots M_{\pi(n)}$ over all permutations $\pi$ of $1, \dots, n$? (More formally, $\sum_{\pi \in S_n} \prod_{i=1}^n M_{\pi(i)}$.)
After some examples, I suspect that the answer is $n!$ times the diagonal matrix whose elements are $M_{1,1}, M_{2,2}, \dots$, but I have no idea how to prove it. Might it involve looking at the transpose?
- Fix a length-$n$ column vector $v$ whose elements are reals from $0$ to $1$. Repeat this process forever: choose a random permutation $\pi$ (different every time), and update $v$ to be equal to the product of $\prod_{i=1}^n M_{\pi(i)}$ by $v$. Must this process converge on a final vector whose elements are all equal with high probability, if $M$ represents a strongly connected graph?
I know that you can pick some permutation $\pi$ that will increase the smallest element of $v$ or decrease the largest, but I can't seem to prove that they will coincide.
In the $2 \times 2$ case, with $M = \pmatrix{a_{11} & 1-a_{11}\cr a_{21} & 1 - a_{21}}$. your sum is $$\left(\begin{array}{cc} -a_{2,1} a_{1,1}+2 a_{1,1}+a_{2,1} & \left(a_{2,1}-2\right) \left(a_{1,1}-1\right) \\ a_{2,1} \left(a_{1,1}+1\right) & -a_{2,1} a_{1,1}-a_{2,1}+2 \end{array}\right) $$
In the $3 \times 3$ case, with $$M = \left(\begin{array}{ccc} a_{1,1} & a_{1,2} & 1-a_{1,1}-a_{1,2} \\ a_{2,1} & a_{2,2} & 1-a_{2,1}-a_{2,2} \\ a_{3,1} & a_{3,2} & 1-a_{3,1}-a_{3,2} \end{array}\right)$$ your sum is too complicated to write out here. All matrix elements are polynomials of total degree $3$ in the $a_{ij}$. The $(2,1)$ matrix element, for example, is
$$ -a_{1,1} a_{2,2} a_{3,2}-a_{1,2} a_{2,1} a_{3,2}-2 a_{1,2} a_{2,2} a_{3,2}-2 a_{1,1} a_{3,2}+3 a_{1,2} a_{2,2}-a_{1,2} a_{3,2}+a_{3,2} a_{2,2}+3 a_{1,2}+2 a_{3,2}$$