# $L^2$ Bounds for Markov Chains.

Consider a non-negative, square stochastic $n \times n$ matrix $P$ (rows sum to one, $P$ is ergodic).

We are interested in characterizing the set of $n \times n$ invertible matrices $A$ such that we have:

$\| APA^{-1} \|_2 \leq 1$

Here $\| \cdot \|_2$ means a matrix norm induced by the vector norm $L_2$.

One example is $\operatorname{diag}(\xi)^{1/2}$, where $\xi$ is the vector representing the stationary distribution and $\operatorname{diag}$ is an operator constructing a diagonal matrix with zeros off the diagonal.

I am interested in a rule defining all (or at least a large class) of valid choices for $A$.

This is not a full answer, but maybe helpful anyway, as it clarifies, that an answer depends on the properties of $P$ itself.

The induced matrix norm of the $L_2$-vector norm is the spectral norm, which is the maximal singular value of the matrix under consideration, so in order to find out something about $||APA^{-1}||_2$, we should look at

$$(A^{-1})^TP^TA^TAPA^{-1} \, .$$

If $A$ is orthogonal, so $A^{-1} \, = \, A^T$, this expression simplifies to

$$AP^TPA^{-1} \, ,$$

while if $A$ commutes with $P$, so $AP \, = \, PA$, it simplifies to

$$P^TP \, .$$

Therefore, as $P^TP$ and $AP^TPA^{-1}$ have the same spectrum, we have to find out something about the Perron-eigenvalue of $P^TP$, given $P$ is row stochastic.

By now, the nice answer of user1551 (my own answer was really clumsy compared to that) to your question

gives

$$||APA^{-1}||_2 \ \geq \ 1$$

for row stochastic $P$ and orthogonal or commuting $A$ and

$$||APA^{-1}||_2 \ = \ 1 \, ,$$

if and only if $P$ is doubly stochastic. Still, I leave my example here:

If $P$ is row stochastic, $P^T$ is column stochastic, which implies, that $P$ and $P^TP$ have the same column sums, because any matrix, which is column stochastic, preserves the component sum of any vector multiplied with it from the right.

Therefore, if $P$ is doubly stochastic, $P^TP$ is also doubly stochastic and the orthogonal matrices or matrices, which commute with $P$ are included in the class of matrices you are looking for in this case.

If $P$ is not doubly stochastic, there is at least one column sum larger than $1$, while the column sums sum to $n$. This always implies the Perron-eigenvalue of $P^TP$ to be larger than $1$, see the answer of user1551 mentioned above, example:

$$\mathbf{P} \ := \ \begin{pmatrix} \frac{1}{3} & \frac{1}{3} & \frac{1}{3} \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix}$$

$$\mathbf{P^TP} \ := \ \begin{pmatrix} \frac{10}{9} & \frac{1}{9} & \frac{1}{9} \\ \frac{1}{9} & \frac{1}{9} & \frac{1}{9} \\ \frac{1}{9} & \frac{1}{9} & \frac{10}{9} \end{pmatrix}$$

The Perron-eigenvalue of $P^TP$ is $\frac{\sqrt{3}+2}{3} \, > \, 1$, so no matrix commuting with $A$ or any orthogonal matrix is contained in the sought class for the matrix $P$.

@ ziutek , a stochastic matrix does not necessarily admit a stationary distribution. cf. below.

Note that $||APA^{-1}||_2=\sqrt{\rho (MM^T)}=\max_i \sigma_i$ where $M=APA^{-1}$ and $(\sigma_i)_i$ are the singular values of $M$ in decreasing order. Moreover $\rho(M)=\rho(P)=1$ and (it is true for every matrix) $\sigma_1\geq \rho(M)$. Thus your question is "find $A$ s.t. $||M||_2=\rho(M)$".

In this file $\| AB\|_\square \leq 1$ implies $\| BA\|_\triangle \leq 1$ , the following result is shown:

Prop. (user1551): there is a sub-mult. norm $||.||$ s.t. $ρ(U)=||U||$ iff the eigenvalues of $U$ of maximal modulus are semi-simple.

Necessarily, the eigenvalues of $P$ of modulus $1$ must be semi-simple. That is the case when $P$ is irreducible (because they are simple) that we'll assume in the sequel (that does not imply that a stationary distribution exists !). We may assume that $P=diag(T,N)$ where $\rho(T)<1$ and $N^h=I$ where $h$ is the period of $P$. Take $A=diag(B,C)$ with $B$ as in the proof above cited; then $||APA^{-1}||_2=||CNC^{-1}||_2$ and the condition is $||CNC^{-1}||_2=1$. I think that we MUST choose $C$ as follows: $C=RS$, a REAL matrix, s.t. $S$ (a complex matrix) diagonalizes $N$ and $R$ is unitary.

EDIT: A mistake. What I wanted to say is that a stationary distribution is not necessarily a limit distribution.