3
$\begingroup$

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.

$\endgroup$
  • 1
    $\begingroup$ 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? $\endgroup$ – Hans Musgrave Jul 20 '18 at 13:04
  • $\begingroup$ Nice thought, but no $A$ is almost surely not symmetric, the rows are generated independently from Dirichlet distributions. $\endgroup$ – ippiki-ookami Jul 20 '18 at 13:06
1
$\begingroup$

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

$\endgroup$
  • $\begingroup$ 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. $\endgroup$ – ippiki-ookami Jul 21 '18 at 5:42
  • 1
    $\begingroup$ @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$. $\endgroup$ – user1551 Jul 21 '18 at 7:02
  • 1
    $\begingroup$ @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)$. $\endgroup$ – user1551 Jul 21 '18 at 7:39
  • 1
    $\begingroup$ 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). $\endgroup$ – user1551 Jul 21 '18 at 7:41
  • 1
    $\begingroup$ @ippiki-ookami See this. $\endgroup$ – user1551 Jul 22 '18 at 12:17

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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