# Relation between Frobenius, spectral norm and sum of maxima

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!

• According to Wikipedia, $\|A\|_F=\|A\|_2$. Please, explain your notation! – W-t-P Apr 7 '19 at 8:13
• Frobenius norm, where did you find that? It is wrong what you are saying. – horxio Apr 7 '19 at 8:14
• What you are saying is incorrect. Can you please tell me where exactly you found this relation? It is wrong that the Frobenius norm is equal to the spectral norm. Think about it, if they were equal, why should we have two definitions? it holds that $||A||_F \geq ||A||_2$. – horxio Apr 7 '19 at 8:23
• The last sentence in the ""Entrywise" matrix norms" reads: The special case p = 2 is the Frobenius norm; see also the "Frobenius norm" section below. Instead of arguing who is (in)correct, please explain your notation. – W-t-P Apr 7 '19 at 8:36
• @W-t-P I find your comments towards a new user a bit aggressive. The problem here is that $\|A\|_2$ is standard notation for two different things, as the Wikipedia page that you linked also notes (if you read a bit earlier, These norms again share the notation with the induced and entrywise p-norms, but they are different, and earlier the definition of the spectral norm). On the other hand, the terms Frobenius norm and spectral norm are unambiguous and look perfectly fine to me as explanations of the notation in OP's question. – Federico Poloni Apr 7 '19 at 12:43

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