Prove $||A||_{2,\infty} = \max_{1\le i \le m}\sqrt{\sum_{j=1}^{n} |a_{ij}|^{2}}$

Question

Let $||.||_{2, \infty}$ denote an induced matrix norm from $L_{2}$ to $L_{\infty}$ and $A \in \mathbb{R}^{m \times n}$. I have to prove that $$||A||_{2,\infty} = \max_{1\le i \le m}\sqrt{\displaystyle \sum_{j=1}^{n} |a_{ij}|^{2}}$$ by showing both $||A||_{2,\infty} \le \max_{1\le i \le m}\sqrt{\displaystyle \sum_{j=1}^{n} |a_{ij}|^{2}}$ and $||A||_{2,\infty} \ge \max_{1\le i \le m}\sqrt{\displaystyle \sum_{j=1}^{n} |a_{ij}|^{2}}$.

I am completely stuck in the first part so far, below is what I have

$$ \begin{align*} ||Ax||_{\infty} &\le ||Ax||_{2} \\ &= ||\sum_{j=1}^{n} a_{j} x_{j}||_{2}\\ &\le \sum_{j=1}^{n} |x_{j}| ||a_j||_{2}\\ &= \sum_{j=1}^{n} |x_{j}| \sqrt{\sum_{i=1}^{m}|a_{ij}|^{2}}\\ &\le ||x||_{\infty}\sum_{j=1}^{n} \sqrt{\sum_{i=1}^{m}|a_{ij}|^{2}}\\ &\le ||x||_{2} \sum_{j=1}^{n}\sqrt{\sum_{i=1}^{m}|a_{ij}|^{2}}\\ \end{align*} $$ It isn't quite close to $||A||_{2,\infty} \le \max_{1\le i \le m}\sqrt{\displaystyle \sum_{j=1}^{n} |a_{ij}|^{2}}$. Any help will be appreciated.

Answer 1

You used $\|Ax\|_\infty \le\|Ax\|_2$ at the beginning. Though mathematically correct, it also means that at the end you can only estimates $\|A\|_{2, 2}$ instead of $\|A\|_{2,\infty}$.

So don't do that. Instead,

\begin{align*} \|Ax\|_\infty &= \max _{1\le i\le m} \left| \sum_{j=1}^n A_{ij} x_j\right| \\ &\le \max _{1\le i\le m} \sqrt{\sum_{j=1}^n A_{ij}^2} \sqrt{\sum_{j=1}^n |x_j|^2} \\ &= \left(\max _{1\le i\le m} \sqrt{\sum_{j=1}^n A_{ij}^2}\right) \ \|x\|_2 \end{align*}

where we use Cauchy-Schwarz. This already shows that $$\|A\|_{2, \infty} \le \max _{1\le i\le m} \sqrt{\sum_{j=1}^n A_{ij}^2}$$

and the equality follows essentially from the equality case of Cauchy-Schwarz: for any $i_0$, let $x = (A_{i_01}, A_{i_02} , \cdots, A_{i_0n})$. Then

\begin{align} \|Ax\|_{\infty} &= \max _{1\le i\le m} \left| \sum_{j=1}^n A_{ij} x_j\right| \\ &\ge \left| \sum_{j=1}^n A_{i_0j} x_j\right|\\ &= \sum_{j=1}^n A_{i_0j}^2\\ &= \sqrt{\sum_{j=1}^n A_{i_0j}^2}\sqrt{\sum_{j=1}^n A_{i_0j}^2} \\ &= \sqrt{\sum_{j=1}^n A_{i_0j}^2} \ \|x\|_2. \end{align} Since this holds for all $i_0$, pick such $i_0$ so that $$\sqrt{\sum_{j=1}^n A_{i_0j}^2} = \max_{1\le i\le m} \sqrt{\sum_{j=1}^n A_{ij}^2}$$ Then one has

$$ \|A\|_{2, \infty} \|x\|_2 \ge \|Ax\|_{\infty} \ge \max_{1\le i\le m} \sqrt{\sum_{j=1}^n A_{ij}^2} \|x\|_2,$$ which implies $$\|A\|_{2, \infty} \ge\max_{1\le i\le m} \sqrt{\sum_{j=1}^n A_{ij}^2}.$$

Answer 2

Using Cauchy's inequality on the rows $\mathbf{a}_i$ of $A$, $$\|A\mathbf{x}\|_\infty=\max(|\mathbf{a}_1\cdot\mathbf{x}|,\ldots,|\mathbf{a}_m\cdot\mathbf{x}|)\le\max_i\|\mathbf{a}_i\|_2\|\mathbf{x}\|_2$$ as required. All that remains is to find one vector where equality holds, for example using $\mathbf{x}=\mathbf{a}_k$, the row that has the maximum 2-norm.

---

Note: $\max_i\|\mathbf{a}_i\|_2=\max_{1\le i\le m}\sqrt{\sum_{j=1}^n|a_{ij}|^2}$.