What are the conditions for a non-Hermitian matric's Rayleigh quotient to be less than its maximum eigenvalue?

Question

What I am trying to prove is that: for a row-stochastic matrix P (not necessarily symmetric), whose every row sums $\sum_{j=1}^nP_{ij}=1$, the Rayleigh quotient of P, $R(\mathbf{x})=\frac{\mathbf{x}^{\top}P\mathbf{x}}{\mathbf{x}^{\top}\mathbf{x}} \leq 1$, which is its maximum eigenvalue. Is this statement valid? And if yes please help me with the proofs.

You can assume $\mathbf{x}\in\mathbb{R}^n$.

• I have been shown that this is not true for all row-stochastic matrix. Is there any condition make this statement works?

Answer 1

Let $$P=\begin{pmatrix} 1-a&a\\1-a&a\end{pmatrix}$$ Then $$x^TPx=(1-a)x_1^2+x_1x_2+ax_2^2,\quad x^Tx=x_1^2+x_2^2$$ For $x_1=2$ and $x_2=1$ we get $$x^TPx=4(1-a)+2+a=6-3a,\quad x^Tx=5$$ Thus the inequality fails for $a<{1\over 3}.$

For doubly stochastic matrix a stronger inequality holds. Indeed by the Cauchy-Schwarz inequality we get $$\sum_{j=1}^np_{ij}|y_j|\le \left (\sum_{j=1}^np_{ij}y_j^2\right )^{1/2}$$ Therefore applying again the Cauchy-Schwarz inequality we get$$|x^TPy|\le \sum_{i=1}^n|x_i|\left (\sum_{j=1}^np_{ij}y_j^2\right )^{1/2}\le \left (\sum_{i=1}^nx_i^2\right )^{1/2}\left (\sum_{i,j=1}^np_{ij}y_j^2\right )^{1/2}=(x^Tx)^{1/2}(y^Ty)^{1/2}$$

Answer 2

Denote by $e$ the vector of ones. We always have $$ \max_{x\ne0}\frac{x^TPx}{x^Tx}\ge\frac{e^TPe}{e^Te}=1.\tag{$\ast$} $$ We shall see that equality holds if and only if $P$ is doubly stochastic.

Suppose equality holds in $(\ast)$. Let $S=\frac12(P+P^T)$. Then $x^TPx=x^TSx$ for every vector $x$. So, from $(\ast)$ we obtain $$ 1=\frac{e^TSe}{e^Te}\le\max_{x\ne0}\frac{x^TSx}{x^Tx}=1. $$ That is, the maximum Rayleigh quotient for $S$ is attained by the vector $e$. Since $S$ is real symmetric, this means the maximum eigenvalue of $S$ is equal to $1$ and $e$ is a corresponding eigenvector. Hence $e=Se=\frac12(Pe+P^Te)=\frac12(e+P^Te)$. In turn, $P^Te=e$. Thus $P$ is also column stochastic, i.e., it is doubly stochastic.

Conversely, if $P$ is doubly stochastic, its induced $2$-norm (maximum singular value) is equal to $1$, because $1\le\rho(P)^2\le\|P\|_2^2=\rho(P^TP)\le\|P^TP\|_\infty=1$. Therefore $$ 1=\frac{e^TPe}{e^Te} \le\max_{x\ne0}\frac{x^TPx}{x^Tx} =\max_{\|u\|_2=1}u^TPu \le\max_{\|u\|_2=\|v\|_2=1}u^TPv =\|P\|_2=1. $$