So I'm trying to prove that
$\lVert A\rVert_\infty \leq \sqrt{n} \lVert A\rVert_2$.
I've written the right hand side in terms of rows, but this method doesn't seem to be getting me anywhere.
Where else should I go?
$\endgroup$ 12 Answers
$\begingroup$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 $$
$\endgroup$ 2 $\begingroup$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).
$\endgroup$ 5
