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. 



Relation between Frobenius norm, infinity norm and sum of maxima
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.$$


