When reading Golub's "Matrix Computations", I came across a series of norm inequalities. While I could prove a lot of them, this one has me stuck:
$$ \frac{1}{\sqrt{m}} ||A||_1 \le ||A||_2 \le \sqrt{n}||A||_1$$
where $A \in \mathbb{R}^{m\times n},$ $||A||_1 = \displaystyle \max_{j \in [1,n]} \sum_{i=1}^m |a_{ij}|$ and $||A||_2 = \max_{||x||=1}||Ax||_2$, where $||Ax||_2$ is the standard Euclidean norm of the vector $Ax$.
I know that $||A||_2 = \max \sigma(A)$ (maximum singular value of $A$), in case that's useful. Help?
Best Answer
If $x \in \mathbb{R}^p$, you have $\|x\|_2 \le \|x\|_1 \le \sqrt{p} \|x\|_2$.
To see this, note that $\|x\|_2^2 = \sum_i x_i^2 \le (\sum_i |x_i|)(\sum_i |x_i|) = \|x\|_1^2$, and the other side follows directly from the Cauchy Schwartz Justin Bieber inequality.
We have $A:\mathbb{R}^n \to \mathbb{R}^m$.
Then $\|Ax\|_2 \le \|Ax\|_1 \le \|A\|_1 \|x\|_1 \le \sqrt{n} \|A\|_1 \|x\|_2$, and so $\|A\|_2 \le \sqrt{n} \|A\|_1$.
Similarly, $\|A x\|_1 \le \sqrt{m} \|A x\|_2 \le \sqrt{m} \|A\|_2 \|x\|_2 \le \sqrt{m} \|A\|_2 \|x\|_1$, and so $\|A\|_1 \le \sqrt{m} \|A\|_2$.