# Upper bound of infinity norm of stochastic matrix

If $$W$$ is a doubly stochastic, symmetric positive definite matrix, each entry of $$W$$ is nonnegative, then we know $$\mathbf{1}$$ is an eigenvector of $$W$$ corresponding to eigenvalue 1. If a vector $$y$$ satisfies $$y\bot\mathbf{1}$$, how do we prove that $$y^TW^TWy\leq \lambda_2(W^TW)\left\Vert y\right \Vert^2$$, where $$\lambda_2(W^TW)$$ is the second largest eigenvalue of $$W^TW$$. Further, can we obtain a bound for $$\left\Vert Wy\right\Vert_\infty$$ where the bound is not $$\left\Vert W\right\Vert_\infty\left\Vert y \right\Vert_\infty$$?

• Since $W$ is symmetric, $y\in\bigoplus_{i=2}^n E_{\lambda_i}(W)$ (orthogonal direct sum), where $1=\lambda_1\geq\lambda_2\geq\lambda_3\geq\dots\geq\lambda_n$ are the eigenvalues of $W$. This proves the first bound. – user10354138 May 21 at 22:53
• The second inequality doesn't seem true. – user1551 May 21 at 23:03
• $\| Ax \|_{|\infty} \leq \|A\|_{\infty} \|x\|_{\infty}$ in general. Since $W$ is doubly stochastic then $\|W\|_{\infty} = 1$ . I would expect this to be true if it were $\lambda_{1}(W)$ but I'm not sure – Shogun May 22 at 0:21
• Actually $\|W \|_{\infty} \geq 1$ since $\sum_{i=1}^{n} w_{ij} = 1$ and $\|W\|_{\infty} = \max_{1 \leq i \leq m} ( \sum_{j=1}^{n} | w_{ij}|)$ – Shogun May 22 at 0:45
• Sorry, I forget to say each entry of $W$ is nonnegative. – Eris May 22 at 1:00