[Math] Characterize stochastic matrices such that max singular value is less or equal one.

linear algebramarkov chainsmatrices

By a stochastic matrix, I mean any non-negative square real matrix with rows summing to one.

It is well-known that singular values of stochastic matrices can be more than one.

Is there a characterization of the subset of stochastic matrices where the singular values are less or equal to one?

A sufficient, but not necessary, condition would be symmetric.

Is there a better characterization?

Best Answer

Here is a complete characterisation:

Proposition. Suppose $A$ is row stochastic (hence we always have $1=\rho(A)\le\|A\|_2$). Then $\|A\|_2=1$ if and only if $A$ is doubly stochastic.

Proof. If $A$ is doubly stochastic, so is $A^TA$ and hence $\left(\|A\|_2^2\equiv\right)\rho(A^TA)=1$.

Conversely, if $\|A\|_2(\equiv\|A^T\|_2)=1$, let $e$ be the all-one vector. Then $$ \|e\|_2^2=\langle e,e\rangle=\langle e,Ae\rangle=\langle A^Te,\,e\rangle\le\|A^Te\|_2\|e\|_2\le\|A^T\|_2\|e\|_2^2=\|e\|_2^2. $$ Therefore ties must occur in the two inequalities above, meaning that $A^Te$ is parallel to $e$ and $\|A^Te\|_2=\|e\|_2$. Thus $A^Te=e$, i.e. $A$ is also column-stochastic.

Related Question