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$?

  • $\begingroup$ 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. $\endgroup$ – user10354138 May 21 at 22:53
  • $\begingroup$ The second inequality doesn't seem true. $\endgroup$ – user1551 May 21 at 23:03
  • $\begingroup$ $\| 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 $\endgroup$ – Shogun May 22 at 0:21
  • $\begingroup$ 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}|)$ $\endgroup$ – Shogun May 22 at 0:45
  • $\begingroup$ Sorry, I forget to say each entry of $W$ is nonnegative. $\endgroup$ – Eris May 22 at 1:00

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.