# Equivalence induced matrix norms!

The equivalence of vector norms on finite dimensional spaces immediately implies that all induced matrix norms are equivalent. Theorem 1, here, gives some of the popular induced norms. I am interested in the $\|A\|_{2,1}$ and $\|A\|_{2,2}$ norm, where \begin{equation*} \|A\|_{2,1}=\sup\{\|A\mathbf{x}\|_1:\|\mathbf{x}\|_2=1\} \end{equation*} and \begin{equation*} \|A\|_{2,2}=\sup\{\|A\mathbf{x}\|_2:\|\mathbf{x}\|_2=1\} \end{equation*}

According to my analysis so far; $\|A\|_{2,1}$ upper-bounds $\|A\|_{2,2}$. Can someone verify?

For a matrix $A\in\mathbb{R}^{n\times m}$

$\|A\|_{2,1}=\max_{u\in\{1,-1\}^n}\|A^Tu\|_2\leq \sqrt{\sum_{i=1}^m(\sum_{j=1}^n|a_{ij}|)^2}$.

And $\|A\|_{2,2}=\lambda_{\max}(A^TA)=\sigma_{\max}(A)\leq\|A\|_F= \sqrt{\sum_{i=1}^m\sum_{j=1}^n|a_{ij}|^2}$,

$\implies$ $$\|A\|_{2,2}^2\leq{\sum_{i=1}^m\sum_{j=1}^n|a_{ij}|^2}\leq{\sum_{i=1}^m\left(\sum_{j=1}^n|a_{ij}|\right)^2}$$.

Your inequalities all go in the same direction, so you cannot possibly prove inequalities both ways.

You have the easy inequalities $$\|x\|_2\leq\|x\|_1\leq\sqrt n\,\|x\|_2.$$ So you immediately get (from the definition, not the characterization you quote) $$\tag{1}\bbox[5px,border:2px solid green]{\|A\|_{2,2}\leq\|A\|_{2,1}\leq\sqrt n\|A\|_{2,2}.}$$ These inequalities are sharp. For instance, if $A=E_{11}$, then $$\|Ax\|_1=\|(x_1,0,\ldots,0)\|_1=|x_1|=\|x\|_2.$$ So $\|A\|_{2,2}=\|A\|_{1,1}$. And if $A=I_m$, then $\|Ax\|_1=\|x\|_1$, so $$\|A\|_{2,1}=\max\{\|x\|_1:\ \|x\|_2=1\}=\sqrt n,$$ while $\|A\|_{2,2}=1$. So $\|A\|_{2,1}=\sqrt n\|A\|_{2,2}$.

Edit: here is a short proof of the inequalities $(1)$, in case they are not obvious.

You have, for any nonzero $x$. $$\frac{\|Ax\|_2}{\|x\|_2}\leq\frac{\|Ax\|_1}{\|x\|_2}\leq\|A\|_{2,1}.$$ Now you take supremum (forget about the term on the middle) and you obtain $$\|A\|_{2,2}\leq\|A\|_{1,1}.$$ Similarly, start with $$\frac{\|Ax\|_1}{\|x\|_2}\leq\sqrt{n}\,\frac{\|Ax\|_2}{\|x\|_2}\leq\sqrt{n}\,\|A\|_{2,2}.$$ Now forget the middle term and take supremum, to obtain $$\|A\|_{2,1}\leq\sqrt{n}\,\|A\|_{2,2}.$$

• what do you mean by characterization?
– amj
Commented Dec 1, 2017 at 23:42
• The definition is \begin{equation*} \|A\|_{2,1}=\sup\{\|A\mathbf{x}\|_1:\|\mathbf{x}\|_2=1\}. \end{equation*} You also have the characterization $$\|A\|_{2,1}=\max_{u\in\{1,-1\}^n}\|A^Tu\|_2.$$ Commented Dec 2, 2017 at 0:08
• Regarding your answer, we have to take supremum over $\|A\mathbf{x}\|$ such that $\|\mathbf{x}\|_2=1$, but there could be alot of $\mathbf{x}$ with unit $\ell_2$ norm and some $\mathbf{x}$ that maximizes $\|A\mathbf{x}\|_{2}$ might not maximize $\|A\mathbf{x}\|_{1}$.
– amj
Commented Dec 3, 2017 at 22:28
• Not sure how you think that affects my answer. Commented Dec 3, 2017 at 22:36
• Let $\mathbf{x}'$ and $\mathbf{x}''$ be such that $\|.\|_2=1$ for both of them. Now, let $\sup\|A\mathbf{x}\|_1=\|A\mathbf{x}'\|_1$ and $\sup\|A\mathbf{x}\|_2=\|A\mathbf{x}''\|_2$, then your inequalities might not hold!
– amj
Commented Dec 3, 2017 at 22:42