# Matrix Norm Inequality

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?

• After you ask a question here, if you get an acceptable answer, you should "accept" the answer by clicking the check mark ✓ next to it. This scores points for you and for the person who answered your question. You can find out more about accepting answers here: How do I accept an answer?, Why should we accept answers?. – Clement C. Feb 25 '17 at 19:17

## 2 Answers

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

• What does the notation $\mathbb{R}_{\infty}^n$ mean? – Chad Nov 15 '18 at 4:46
• $\mathbb{R}^n$ with $\max$ norm – Norbert Nov 15 '18 at 13:30

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).

• I think $\|A\|_2$ denotes the operator 2-norm $\|A\|_2=\max_{\|x\|_2=1}\|Ax\|_2$, not the Frobenius norm (vector 2-norm) $\|A\|_F^2=\operatorname{trace}(A^\ast A)=\sum_{i,j}|a_{ij}|^2$. – user1551 May 15 '13 at 7:26
• What justifies the first equality on the second line? – Chad Nov 15 '18 at 5:00
• @Chad The definition of $\lVert\cdot\rVert_2$ (assuming this notation is indeed the one the OP use, as for matrices $\lVert\cdot\rVert_2$ is commonly used for several norms) – Clement C. Nov 15 '18 at 5:07
• Interesting. I'm attempting to prove the same inequality that the OP posted, but interpreting $||\cdot||_p$ as the induced operator norm. Perhaps I'll post a separate question. – Chad Nov 15 '18 at 5:22
• Yes, this particular answer will not help for that... – Clement C. Nov 15 '18 at 5:24