Let $A$ be a $n \times n$ matrix so that the Frobenius norm squared $\|A\|_F^2$ is $\Theta(n)$, the spectral norm squared $\|A\|_2^2=1$. Is it true that $\sum_{i=1}^n\max_{1\leq j\leq n} |A_{ij}|^2$ is $\Omega(n)$? Assume that $n$ is sufficiently large.
I cannot find a relation between matrix norms that can show this. The idea behind this question is that there are many singular values of $A$ that are $\Theta(1)$.
Thanks!
This is false in general, but true for matrices with non-negative entries.
For a counterexample, suppose that $n=p$ is prime, and consider the matrix $$ A=\left\|p^{-1/2}\left(\frac{i-j}p\right)\right\|_{i,j=0,\dotsc,p-1} $$ where $(\cdot/p)$ is the Legendre symbol. This is a circulant matrix; its non-zero eigenvalues are normalized Gaussian sums, equal $1$ in absolute value; hence, $\|A\|_2\le 1$. Also, we have $\|A\|_F^2=p-1$. On the other hand, $$ \sum_i \max_j |A_{ij}|^2 = 1. $$
Suppose now that all elements of $A$ are non-negative. Let $u_i\in{\mathbb R}^n$ be the row vectors of $A$, and denote by $\|\cdot\|_p$ the $\ell^p$-norm over ${\mathbb R}^n$; when $p=2$, this is the standard Euclidean norm. The Frobenius norm of $A$ is $\|A\|_F^2=\sum_i\|u_i\|_2^2$. Assuming that $\|A\|_F^2\ge cn$ and $\|A\|_2^2\le C$, we show that $\sum_i\|u_i\|_\infty^2\ge C^{-1}c^2n$.
Denoting by $\vec 1$ the all-$1$ vector, we have $$ C \ge \|A\|_2^2 = \max_x \frac{\|Ax\|_2^2}{\|x\|_2^2} \ge \frac{\|A\vec 1\|_2^2}{\|\vec 1\|_2^2} = \frac1n\sum_i \|u_i\|_1^2. $$ (It is this computation that uses the non-negativeness assumption.) This implies $$ \sum_i \|u_i\|_1^2 \le Cn $$ and, consequently, by Cauchy-Schwartz, $$ cn \le \|A\|_F^2 = \sum_i \|u_i\|_2^2 \le \sum_i \|u_i\|_\infty \|u_i\|_1 \le \left( \sum_i \|u_i\|_\infty^2\right)^{1/2} \left( \sum_i \|u_i\|_1^2\right)^{1/2} \le \left( Cn\sum_i \|u_i\|_\infty^2\right)^{1/2}, $$ which yields the desired estimate $$ \sum_i \|u_i\|_\infty^2 \ge C^{-1}c^2n. $$
