# Rescaling stochastic matrix

Let $A$ be the stochastic transition matrix of an ergodic Markov chain of size $n$ (number of states of the chain). Let $\pi$ be the row vector such that $\pi A = \pi$ (a.k.a. left eigenvector associated with eigenvalue $1$, a.k.a stationary distribution), and let $D$ the diagonal matrix such that $D_{ii} = \sqrt{\pi_i}$. Suppose also that the chain is such that $D^2A = A^TD^2$ is verified (it is reversible). Then we know that $B = DAD^{-1}$ is real symmetric, so that $B$ is diagonalizable with real eigenvalues, and $A$ and $B$ share these eigenvalues by matrix similarity. We then have that $\|L\|_2 = \|U \Lambda U^T\|_2 = \|\Lambda\|_2$ where $\Lambda$ is the diagonal matrix of the eigenvalues, and $U$ is the orthogonal matrix of the right eigenvectors so that $\|L\|_2 = \max_{i \in[n]} |\lambda_i| = 1$ (largest eigenvalue in magnitude of a stochastic matrix).

Now I claim the following conjecture that $\|B\|_2 = 1$ even when $D^2A = A^TD^2$ is not verified (it is not reversible), but in that case I fail to prove it, and I would appreciate some pointers to understand why it is still the case. The reason I believe it is true is from numerical simulation.

• Just a thought, if $A$ is symmetric then $D^2A=A^TD^2$. I've found it pretty easy to accidentally create symmetric or other nice examples in numerical experiments. Is your $A$ always symmetric? – Hans Musgrave Jul 20 '18 at 13:04
• Nice thought, but no $A$ is almost surely not symmetric, the rows are generated independently from Dirichlet distributions. – ippiki-ookami Jul 20 '18 at 13:06

Your conjecture is true. By Perron-Frobenius theorem, if $u$ is a positive eigenvector of a nonnegative matrix, the eigenvalue it corresponds to must be the matrix's spectral radius. Now, let $u$ be the the entrywise square root of $\pi$. Then $u$ is a positive eigenvector of $B^TB$ corresponding to the eigenvalue $1$. Hence $\|B\|^2=\rho(B^TB)=1$.
• So if I understand it all correctly, there is only one left eigen-vector (up to scaling) for $B^TB$ that has all non-negative entries, we happen to know it, it is even called the Perron-Frobenius left eigenvector, and the existence and uniqueness of this vector arises from the mere fact that $B^TB$ has all non-negative entries, and additionally, the eigenvalue it corresponds to is always the largest in magnitude, which is also provably real. The Perron-Frobenius theorem has definitely a lot to say. – ippiki-ookami Jul 21 '18 at 5:42
• @ippiki-ookami No. What Perron-Frobenius theorem says is that if $M\ge0,\,u>0$ and $u^TM=\lambda u^T$, then $\lambda$ must be equal to $\rho(M)$. In other words, $\rho(M)$ is the only eigenvalue of $M$ that can possibly have a positive eigenvector. But in general, it may happen that $M$ has multiple linearly independent positive eigenvectors (e.g. when $M=I$) or no positive eigenvector at all (e.g. when $M=\operatorname{diag}(1,0)$). Anyway, in your case, $M=B^TB$ does have a positive left eigenvector $u$ for the eigenvalue $\lambda=1$, so we know that $\rho(B^TB)=1$. – user1551 Jul 21 '18 at 7:02
• @ippiki-ookami (1) A nonnegative eigenvector is not enough. You need a positive one. E.g. $v=(0,1)$ is a nonnegative eigenvector of $M=\operatorname{diag}(1,0)$ for the $\lambda=0$, but $\rho(M)=1$. (2) I am not aware of any such characterisation, but Perron-Frobenius thm guarantees that if $M\ge0$ is irreducible (i.e. Ergodic if $M$ is a transition matrix), then $M$ must have a +ve eigenvector for $\rho(M)$. – user1551 Jul 21 '18 at 7:39
• Note that in your case, while $B$ is irreducible, we cannot infer that $B^TB$ is irreducible. However, as $A$ is irreducible, $\pi$ must be positive. Hence $u>0,\ D$ is invertible (and that's why $B$ exists in the first place). – user1551 Jul 21 '18 at 7:41