Mrthdrb

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^nmax_1leq jleq 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/2left(fraci-jpright)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|_2le 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_iinmathbb 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^2ge cn$ and $|A|_2^2le C$, we show that $sum_i|u_i|_infty^2ge C^-1c^2n$.

Denoting by $vec 1$ the all-$1$ vector, we have
$$ C ge |A|_2^2 = max_x frac_2^2x ge fracvec 1 = frac1nsum_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^2right)^1/2 left( sum_i |u_i|_1^2right)^1/2 le
left( Cnsum_i |u_i|_infty^2right)^1/2, $$
which yields the desired estimate
$$ sum_i |u_i|_infty^2 ge C^-1c^2n. $$