A stochastic matrix is a positive matrix whose columns sum to one. The largest eigenvalue of a stochastic matrix is one. But the largest singular value can exceed one. Are there any known bounds on this largest singular value?
(Note, when the matrix is doubly stochastic—with both rows and columns summing to one—then the largest singular equals one.)
Best Answer
We can get a quick upper bound as follows: let $\|x\|$ denote the norm (Euclidean length) of a vector, and denote $$ \|(x_1,\dots,x_n)\|_\infty = \max_{i=1,\dots,n}|x_n| $$ It is well known that $$ \max_{x \neq 0} \frac{\|Ax\|_\infty}{\|x\|_\infty} = \max_{i=1,\dots,n}\sum_{j=1}^n |a_{ij}| $$ Thus, for a stochastic matrix $A$, we have $$ \sigma_1(A) = \max_{x \neq 0} \frac{\|Ax\|}{\|x\|} \leq \max_{x \neq 0} \frac{\sqrt{n} \|Ax\|_\infty}{\frac 1{\sqrt{n}}\|x\|_\infty} = n \max_{i=1,\dots,n}\sum_{j=1}^n |a_{ij}| = n $$ I'm not sure if this bound is tight.
We can see that it is possible to get a maximum singular value of at least $\sqrt{n}$. In particular, it suffices to consider $A = \mathbf 1 e_1^T$ where $\mathbf 1$ is the column-vector of $1$s and $e_1$ is the standard basis vector $(1,0,\dots,0)^T$.