For a symmetric matrix $A$, $\|A\|_2 \leq \|A\|_{\infty}$?

Question

I am reading the following paper.

• Yuval Dagan, Constantinos Daskalakis, Nishanth Dikkala, Surbhi Goel, Anthimos Vardis Kandiros, Statistical Estimation from Dependent Data, ICML 2021.

From page 6 under section 3, in the "Notation: Matrix Norms" paragraph, it is stated that $$\|A\|_2 \leq \|A\|_{\infty}$$ since $A \in \mathbb{R}^{n \times n}$ is symmetric, where $\|A\|_2 := \sqrt{\lambda_{\max}(A^T A)}$ and $\|A\|_{\infty} := \max_{i}\sum_{j=1}^n |a_{ij}|$. Is this statement correct? If it is correct, how to prove that if $A$ is symmetric, then $\|A\|_2 \leq \|A\|_{\infty}$?

Answer 1

For $x\in\Bbb{R}^n$, let $\|x\|_\infty = \max_{i=1}^n |x_n|$.

If $y=Ax$ then $$ \begin{align} |y_i| &= \left|\sum_{j=1}^n a_{ij} x_j\right| \le\sum_{j=1}^n |a_{ij}| |x_j|\\ &\le \left(\sum_{j=1}^n |a_{ij}|\right)\|x\|_\infty\le \|A\|_\infty \|x\|_\infty \end{align} $$ for all $1\le i\le n$. Therefore $\|y\|_\infty \le \|A\|_\infty \|x\|_\infty$.

Since $A$ is symmetric, it is orthogonally diagonalizable. There exists a non-zero vector $x\in\Bbb{R}^n$ such that $Ax = \lambda x$ where $\lambda$ is the eigenvalue of largest absolute value among the eigenvalues of $A$. Moreover, $\|A\|_2=|\lambda|$ by definition.

Since $x\ne 0$, $\|x\|_\infty > 0$. By the result above $$|\lambda\|\|x\|_\infty = \|\lambda x\|_\infty = \|Ax\|_\infty \le \|A\|_\infty \|x\|_\infty$$

Dividing both sides of the inequality by $\|x\|_\infty$, we get $\|A\|_2 = |\lambda| \le \|A\|_\infty$.