Given $x \in \mathbb{R}^m$ and $A \in M_{m,n}(\mathbb{R})$, it can be shown that the following inequalities hold:
$$||A||_\infty \leq \sqrt(n)\space ||A||_2$$
and
$$||A||_2 \leq \sqrt(m) \space ||A||_\infty$$
The infinity norm $||\bullet||_\infty$ is defined by the maximum absolute row sum as follows:
$$||A||_\infty = \text{max}\sum_{j=1}^{n} |a_{ij}| \space\space \text{for} \space\space 1\leq i\leq m$$
The 2-norm $||\bullet||_2$ is the standard Euclidean norm as:
$$||A||_2 = \bigg(\sum_{i=1}^{m} \sum_{j=1}^{n} |a_{ij}|^2\bigg)^{1/2}$$
What would be a generic example of where the equality specifically holds for each equation?
My thoughts:
Would the first one be only when the matrix contains all zeros except for 1 element?
Would the second one be only when the matrix contains a unique constant?
I can easily prove these inequalities, but I am having a difficult time visualizing examples of where the equality holds.
Any thoughts / help would be greatly appreciated!
Best Answer
Examining the sources of looseness in your proof will help you find cases where equality holds.
$$\|A\|_\infty^2 = \max_i \left(\sum_{j=1}^n |a_{ij}|\right)^2 \le \sum_{i=1}^n \left(\sum_{j=1}^n |a_{ij}|\right)^2 \le n \sum_{i=1}^n \sum_{j=1}^n |a_{ij}|^2 = n \|A\|_2^2.$$ The first inequality is tight when only one row is nonzero. For the second inequality (Cauchy-Schwarz), note that for a fixed $i$, we have $\left(\sum_{j=1}^n |a_{ij}|\right)^2 = \sum_{j=1}^n |a_{ij}|^2$ when all the summands have the same absolute value. This leads us to an example where both inequalities hold: let some row of $A$ be $\begin{bmatrix} c & \cdots & c \end{bmatrix}$ and let the remaining entries of $A$ be zero. Then $\|A\|_2 = \sqrt{n} |c|$ and $\|A\|_\infty = n |c|$. (You can even negate some entries of this example, and equality will still hold.)
$$\|A\|_2^2 = \sum_{i=1}^m \sum_{j=1}^n |a_{ij}|^2 \le m \max_i \sum_{j=1}^n |a_{ij}|^2 \le m \max_i \left(\sum_{j=1}^n |a_{ij}|\right)^2 = m \|A\|_\infty.$$ For the first inequality to be tight, it suffices to have the rows of $A$ be identical. For the second inequality, note that for a fixed $i$, we have $\sum_j |a_{ij}|^2 = \left(\sum_j |a_{ij}|\right)^2$ if exactly one of the summands is nonzero. This leads us to an example where both inequalities hold: let one of the columns of $A$ be $\begin{bmatrix} c \\ \vdots \\ c \end{bmatrix}$, and let the other entries of $A$ be zero. Then $\|A\|_2 = \sqrt{m} |c|$ and $\|A\|_\infty = |c|$. (An even more general example is $A$ having exactly one $c$ somewhere in each row, and all other entries zero.)