1
$\begingroup$

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$
  • $\begingroup$ 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?. $\endgroup$ – Clement C. Feb 25 '17 at 19:17
3
$\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$
  • $\begingroup$ What does the notation $\mathbb{R}_{\infty}^n$ mean? $\endgroup$ – Chad Nov 15 '18 at 4:46
  • $\begingroup$ $\mathbb{R}^n$ with $\max$ norm $\endgroup$ – Norbert Nov 15 '18 at 13:30
1
$\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$
  • 1
    $\begingroup$ 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$. $\endgroup$ – user1551 May 15 '13 at 7:26
  • $\begingroup$ What justifies the first equality on the second line? $\endgroup$ – Chad Nov 15 '18 at 5:00
  • 1
    $\begingroup$ @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) $\endgroup$ – Clement C. Nov 15 '18 at 5:07
  • 1
    $\begingroup$ 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. $\endgroup$ – Chad Nov 15 '18 at 5:22
  • $\begingroup$ Yes, this particular answer will not help for that... $\endgroup$ – Clement C. Nov 15 '18 at 5:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.