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

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. $\endgroup$ – W-t-P Apr 7 '19 at 8:36These 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 termsFrobenius normandspectral normare unambiguous and look perfectly fine to me as explanations of the notation in OP's question. $\endgroup$ – Federico Poloni Apr 7 '19 at 12:434more comments