Consider a stochastic matrix $P$, i.e. real, non-negative, square, rows sum to one. Consider $\Xi = \text{diag}(\xi)$ to be a diagonal matrix with a principal left eigenvector $\xi$ of $P$ (i.e. $\xi^\top P = \xi^\top$) on the main diagonal and zeros elsewhere (i.e. the stationary distribution if the chain is ergodic). Denote by $\sigma(\cdot)$ the spectral radius of a matrix.

Prove the following spectral radius bound.

$\sigma(P^\top \Xi^2 P) \leq \max_i \xi_i^2$

I have tried the following approaches:

  1. $\| P^\top \Xi^2 P \|_2 \leq \| P^\top \|_2 \| \Xi^2 \|_2 \|P \|_2 = \| \Xi^2 \|_2 \|P \|_2^2 \leq (\sqrt2)^2 \max_i \xi_i^2 $ (not sharp enough).
  2. $\| P^\top \Xi^2 P \|_1 \leq \| P^\top \|_1 \| \Xi^2 \|_1 \|P \|_1 \leq n \max_i \xi_i^2 $ (even less sharp)
  • $\begingroup$ What approaches have you tried? $\endgroup$ Nov 26 '14 at 21:11
  • $\begingroup$ @HaraldHanche-Olsen Thanks for the comment. Unfortunately I don't have much experience doing this and the only tool I know for bounding the spectral radius is to try to find a sub-multiplicative matrix norm. I have looked at the obvious suspects (see edited question) but unfortunately the bounds I obtained were too weak. I understand what I'm trying to do is probably an application of some basic theory I don't know about. If so, please just give a reference where I can look it up. $\endgroup$
    – ziutek
    Nov 26 '14 at 21:23

What about using the $\infty$-norm? That is $$ \|A\|_\infty = \sup_{x: \|x\|_\infty=1} \|Ax\|_\infty. $$ Take a vector $x$. Then $$ \|Px\|_\infty \le \max_{i}\left|\sum_j p_{ij} x_j\right| \le \max_{i}\sum_j p_{ij} (\max_k |x_k|) \le\|x\|_\infty. $$ Denote $z:=Px$. Then $$ \|P^T\Xi^2 z\|_\infty = \max_i \left|\sum_j p_{ji}\xi_j^2 z_j\right| \le\max_i \left|\sum_j p_{ji}\xi_j \right| \|\xi\|_\infty\|z\|_\infty. $$ Since $P^T\xi = \xi$, it follows $$ \sum_j p_{ji}\xi_j=\xi_i, $$ hence $\max_i \left|\sum_j p_{ji}\xi_j \right|=\|\xi\|_\infty$, which gives $$ \|P^T\Xi^2 Px\|_\infty = \|P^T\Xi^2 z\|_\infty\le \|\xi\|_\infty^2 \|z\|_\infty = \|\xi^2\|_\infty \|z\|_\infty, $$ which proves $$ \sigma(P^T\Xi^2 P) \le \|P^T\Xi^2 P\|_\infty \le \|\xi^2\|_\infty. $$


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.