# Inequality of matrix norms

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.

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

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