0
$\begingroup$

I'm trying to prove that $$\frac{1}{\sqrt{n}}\lVert A\rVert_\infty \leq \lVert A \rVert_2$$ I know that $\lVert A \rVert_\infty = \max_i\lVert a^t_i\rVert$ and $\lVert A \rVert_2 = \sigma_1(A)$ where $\sigma_1$ is the largest singular value of $A$, but I can't seem to connect the two.

$\endgroup$
  • 1
    $\begingroup$ Do you know that $\|A\|_p = \max_{\|x\|_p = 1} \|Ax\|_p$? If yes, hint: Hölder inequality. $\endgroup$ – user251257 Mar 15 '17 at 19:35
  • 1
    $\begingroup$ math.stackexchange.com/questions/391744/matrix-norm-inequality Doing a little search first wouldn't hurt. $\endgroup$ – Hyperplane Mar 15 '17 at 19:38
  • $\begingroup$ @Hyperplane it also doesn't hurt to read the question. OP uses $\|A\|_2$ differently from the question you linked. $\endgroup$ – Umberto P. Mar 15 '17 at 19:52
1
$\begingroup$

I think it is best to reserve $\|A\|_2$ for the usual $2$-norm $\displaystyle \|A\|_2 = \sup_{\|x\|_2 = 1} \|Ax\|_2$.

You can use the singular value decomposition: there exist unitary matrices $U$ and $V$ and a matrix $S$ with singular values of $A$ along the diagonal and zeros elsewhere satisfying $$A = USV.$$

Suppose that $x$ is a vector with $\|x\|_2 = 1$. Then you have $$\|Ax\|_2 = \|USVx\|_2 = \|SVx\|_2 \le \|S\|_2 \|Vx\|_2 = \|S\|_2.$$ Because of its particular form, the $2$-norm of $S$ is its largest entry. Since its nonzero entries are the singular values of $A$, this means $$\|S\|_2 = \sigma_1(A)$$ so that $$\|A\|_2 \le \sigma_1(A) .$$

The fact that $\|A\|_\infty \le \sqrt n \|A\|_2$ is easy to prove, giving you $$ \frac 1 {\sqrt n} \|A\|_\infty \le \sigma_1(A).$$

$\endgroup$

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.