3
$\begingroup$

For $A \in \mathbb R^{m \times n}$ and the induced norms:

$$ \| A \|_1 = \max_{x \ne 0} \frac{\|Ax\|_1}{\|x\|_1} $$ $$ \| A \|_2 = \max_{x \ne 0} \frac{\|Ax\|_2}{\|x\|_2} $$

... where:

$$ \|x\|_1 = \sum_{k=1}^n |x_k| $$

$$ \|x\|_2 = \sqrt{\sum_{k=1}^n |x_k|^2} $$

... does the following inequality hold in general?

$$ \|A\|_2 \le \|A\|_1 $$

Improve this question
$\endgroup$
0

2 Answers 2

Reset to default
7
$\begingroup$

To avoid ambiguity I will write $\lVert\cdot\rVert_{p\to r}$ for the $\ell_p$-to-$\ell_r$-norm. Note that in general, $\lVert A\rVert_{1\to r} = \max_{1\leq j\leq n} \lVert (Ae_j)\rVert_r$.

Let $A$ be the $n\times n$ matrix whose top row has $1$ in every entry, and all other entries of the matrix are $0$. Then by the remark above, $\lVert A\rVert_{1\to 1} =1$. On the other hand,

$$ \lVert A\rVert_{2\to 2} \geq \lVert A^* \rVert_{2\to 2} \geq \lVert A^*e_1\rVert_2 = \sqrt{n} $$

giving a counterexample to your question. (In fact this lower bound is an equality, although this is not needed to answer the question.)

Improve this answer
$\endgroup$
3
  • 2
    $\begingroup$ One point about induced norms on matrices, told me by Kahan decades ago: if we have two distinct induced norms, taking the maximum of those creates a new function on matrices with some nice properties, but it cannot be an induced norm itself. Oh: so no induced norm can dominate another. $\endgroup$
    – Will Jagy
    Commented Oct 10, 2022 at 22:03
  • $\begingroup$ It might be worthwhile to add the following intuitive explanation of the phenomenon that is at work here: the problem is that a given norm on a vector space influences the induced norm (i.e., the operator norm, as my inner functional analyst wants to say) of an operator $A$ in two ways: in the expression $\|Ax\|$ over which we take a surpremum, and in the condition $\|x\| \le 1$ for taking the supremum. If you increase the norm on the vector space, the first point "wants" to increase the induced norm of $A$, while the second point "wants" to decrease it. $\endgroup$
    – Jochen Glueck
    Commented Oct 10, 2022 at 22:21
  • $\begingroup$ In fact the counterexample saturates the true bound I have added. $\endgroup$
    – Oscar Lanzi
    Commented Oct 10, 2022 at 23:57
3
$\begingroup$

It certainly holds for all matrices where $|a_{ij}|=|a_{ji}|$ (meaning both symmetric and skew-symmetric matruces, among otbers). It is reported here that

$||A||_2^2\le||A||_1||A||_\infty,$

and where the condition above is satisfied $||A||_1=||A||_\infty$.

For all $n×n$ matrices we always have

$||A||_1\le n||A||_\infty$

$||A||_\infty\le n||A||_1$

and so the bound given above implies

$||A||_2\le\sqrt{n}||A||_1$

$||A||_2\le\sqrt{n}||A||_\infty.$

Improve this answer
$\endgroup$
1
  • 2
    $\begingroup$ Comment just for other readers (apologies if you know this already Oscar): the inequality you mention is a special case of Riesz-Thorin interpolation with $\ell_2^n$ as the halfway-point between $\ell_1^n$ and $\ell_\infty^n$. $\endgroup$
    – Yemon Choi
    Commented Oct 10, 2022 at 21:13

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .