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! 



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


