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.
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.$$
