# Bound spectral radius of a certain matrix.

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)
• What approaches have you tried? – Harald Hanche-Olsen Nov 26 '14 at 21:11
• @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. – 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.$$