# Relation between Frobenius norm, infinity norm and sum of maxima

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.

• 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. – Christian Remling Apr 7 at 16:41
• @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. – 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.$$