Matrix Norm Inequality $\lVert A\rVert_\infty \leq \sqrt{n} \lVert A\rVert_2$

Solution 1:

Let $x\in \mathbb{R}^n_\infty$. We know that $\Vert y\Vert_\infty\leq \Vert y\Vert_2\leq\sqrt{n}\Vert y\Vert_\infty$ for all $y\in\mathbb{R}^n$, so $$ \Vert A(x)\Vert_\infty\leq\Vert A(x)\Vert_2\leq\Vert A\Vert_2\Vert x\Vert_2\leq\Vert A\Vert_2\sqrt{n}\Vert x\Vert_\infty $$ Since $x\in \mathbb{R}^n_\infty$ is arbitrary $$ \Vert A\Vert_\infty\leq\sqrt{n}\Vert A\Vert_2 $$

Solution 2:

Writing $A=(A_1,\dots,A_n)^\mathrm{T}$ with $A_i$ being the $i$-th row of the matrix, let $A_j$ be the row for which $$ \lVert A\rVert_\infty = \max_{1\leq i\leq n }\lVert A_i\rVert_1 = \lVert A_j\rVert_1 = \sum_{k=1}^n \left|A_{i,j}\right| $$ Then $$ n\lVert A\rVert_2^2 = n\sum_{i=1}^n \lVert A_i\rVert_2^2 \geq n\lVert A_j\rVert_2^2 \geq \lVert A_j\rVert_1^2 = \lVert A\rVert_\infty^2 $$ where the last inequality is "standard" (relation between 1 and 2-norm on $\mathbb{R}^n$, can be proven with Cauchy-Schwarz).