Bounding operator norm of matrix using eigen-values

Question

I have a symmetric matrix $A$ and I have managed to show that all eigenvalues of $A$ lie in $[-c,c]$. I want to prove that the operator norm of $A$ is less than $c$ i.e. $||A||\leq c$.

I could prove that this norm is less than $c^2$ as follows :

From the hypothesis, we have that $cI-A\succeq 0$ and $cI+A\succeq 0$ since the hypothesis states that $-cx^Tx\leq x^TAx\leq cx^Tx$. Now $(cI-A)(cI+A)=(cI+A)(cI-A)=c^2I-A^2\succeq 0$.

So, $x^TA^2x\leq c^2 x^Tx\implies ||Ax||^2\leq c^2 ||x||^2$.

However I don't see how to get the bound of $c$.

Answer 1

Your $\preceq$s are backwards. The hypothesis implies that $cI-A$ and $cI+A$ are both positive semidefinite, not negative semidefinite. So their product is also positive semidefinite, and this gives you the inequality $x^T A^2 x \le c^2 x^T x$. Since $x^T A^2 x = x^T A^T A x = (Ax)^T (Ax) = \|Ax\|^2$, this implies $\|Ax\|^2 \le c^2 \|x\|^2$ as desired. (What you wrote seemed to have lost some squares.)

The conclusion $\|Ax\| \ge c^2 \|x|$ (or even $\|Ax\|^2 \ge c^2 \|x\|^2$ is clearly wrong, as you can see by taking $A$ to be the zero matrix.

Answer 2

If your definition of operator norm is "maximum singular value," then simply note that the eigenvalues of $A^\top A$ lie in $[0, c^2]$ so the singular values lie in $[0, c]$.

---

If your definition of operator norm is $\max_{x : \|x\| = 1} \|A x\|$, then write $A = U\Lambda U^\top$ where $U$ is orthogonal and $\Lambda$ is diagonal. Then

$$\max_{x : \|x\|=1} \|Ax\|^2 = \max_{x : \|x\|=1} x^\top A^\top A x = \max_{x : \|x\|=1} x^\top U\Lambda^2 U^\top x \overset{y=U^\top x}{=} \max_{y : \|y\|=1} y^\top \Lambda^2 y = \max_{y : \sum_i y_i^2 = 1} \sum_{i=1}^n y_i^2 \lambda_i^2.$$

WLOG let $\lambda_1^2 \ge \cdots \ge \lambda_n^2$ By Hölder's inequality, $\sum_{i=1}^n y_i^2 \lambda_i^2 \le \left(\sum_{i=1}^n y_i^2\right) \lambda_1^2$ with equality when $y = (1, 0, \ldots, 0)$.

Answer 3

If $A$ is symmetric (and real) then it has an orthonormal basis of eigenvectors $v_k$. Then any unit $x$ can be written as $x=\sum_k x_k v_k$ with $\sum_k |x_k|^2 = 1$ and so $\|Ax\|^2 = \|A(\sum_k x_k v_k)\|^2 =\|\sum_k x_k A v_k\|^2 = \|\sum_k x_k \lambda_k v_k\|^2= \sum_k |x_k|^2|\lambda_k|^2 \le c^2 \sum_k |x_k|^2=c^2$.