Bounding $\|A\|_2$ with $\max_i \|A_i \|_2$?

Question

Given a Matrix $A=(A_1, \dots, A_n)$ with columns $A_i \in \mathbb{R}^n$. I am trying to understand the solution of my homework assignment where in one line we state the inequality $\|A(x-y)\|_2\leq \max_i \|A_i\|_2 \|x-y\|_2$. I know that $\|A(x-y)\|_2\leq \|A\|_2 \|x-y\|_2$ holds, so is $\|A\|_2$ bounded by $\max_i \|A_i\|_2$?

Answer 1

The reverse is true:

$$ \| A \|_2 = \sup_{x: \|x\|_2 = 1} \| Ax \|_2 \geq \sup_{i} \| A \mathbf{e}_i\|_2 = \max_{i} \| A_{i} \|_2, $$

where $\mathbf{e}_i$ is the $i^{\text{th}}$ canonical basis vector.

I also don't think your first inequality is correct. If it were, you could simply divide by $\|x - y\|_2$, take a supremum over pairs $x, y$, and obtain

$$ \|A\|_2 = \sup_{v \in \mathbf{B}} \| A v \|_2 \leq \max_{i} \| A_i \|_2 $$

However, this is clearly false if you consider, e.g., the matrix

$$ A = \begin{bmatrix} \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \frac{1}{\sqrt{2}} & \frac{1}{\sqrt{2}} \\ \end{bmatrix}. $$

Its maximum column norm is $\max_{i} \| A_{i} \|_2 = 1$, but its spectral norm is $\| A\|_2 = \sqrt{2}$.