Let $A$ be a sequence of $n \times n$ matrices so that the Frobenius norm squared satisfies $\|A\|_F^2 \simeq n$ and the infinity norm squared is $\|A\|_{\infty}^2 = 1$. Is the following true?

$$\sum_{i=1}^n\max_{1\leq j\leq n} |A_{ij}|^2\gtrsim n$$

I cannot find a relation between matrix norms that can show this.

  • $\begingroup$ I've taken the liberty to adjust your notations so that they will be more readily understandable to mathematicians (I believe), but feel free to go back to the original version if you don't like this. $\endgroup$ – Christian Remling Apr 7 at 16:41
  • 2
    $\begingroup$ @ChristianRemling: Funnily, it is precisely the original notation that I used to consider mathematical, while yours is completely unknown to me, and looks like taken from some physics or engineering book. $\endgroup$ – Alex M. Apr 7 at 17:20

The answer is Yes. This is not really a problem about matrices. The best way to analyse it is to rewrite it in terms of the row vectors $u_i\in{\mathbb C}^n$. Let me denote $\|\cdot\|_p$ the $\ell^p$-norm over ${\mathbb C}^n$ ; when $p=2$, this is the standard Euclidian norm. The Frobenius norm is $\sum_i\|u_i\|_2^2$, while $\|A\|_\infty$ is $\max_i\|u_i\|_1$. Finally, you want to estimate $\sum_i\|u_i\|_\infty$.

Now, remember that $\|u\|_2^2\le\|u\|_1\|u\|_\infty$. Say that $\|A\|_2^2\ge\frac nc$ and $\|A\|_\infty\le c$ for some $c<\infty$. One deduces $$\frac nc\le c\sum_i\|u_i\|_\infty.$$ By Cauchy-Schwarz, there comes $$\frac{n^2}{c^2}\le c^2n\sum_i\|u_i\|_\infty^2,$$ which is the desired conclusion.

To summarize the calculus above, one has $$\|A\|^2_F\le\|A\|_\infty\sum_i\|u_i\|_\infty,$$ hence $$\|A\|_F^4\le n\|A\|_\infty^2\sum_i\|u_i\|^2_\infty.$$


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.