If $|A_{ij}|\leq 1$ for all entries of symmetric $A$, then the largest possible spectral norm of $A$ is smaller than $n$?

Question

In other words, for any symmetric or antisymmetric matrix $A\in\mathbb{R}^{n\times n}$ that has $|A_{ij}|\leq 1$, can we conclude that \begin{align*} \|A\| \leq \|J\|, \end{align*} where $\|\cdot\|$ denotes spectral norm and $J$ represents all one matrix?

Since we already know that all one matrix $J$ has the smallest eigenvalue $\sigma_n = 0$ and all other eigenvalues $\sigma_1 = \sigma_2 = \ldots = \sigma_{n-1} = n$, it is to say whether such $A$ can have singular value greater than $n$.

Answer 1

This is true for any matrix. In particular, we note that $\|A\| \leq \|A\|_F$, where $\|\cdot\|_F$ denotes the Frobenius norm. From there, we have $$ \|A\| \leq \|A\|_F = \sqrt{\sum_{i,j=1}^nA_{ij}^2} \leq \sqrt{\sum_{i,j=1}^n 1} = n $$

Answer 2

We have

$$\|J\| \ge \frac{\|J(1, \ldots, 1)\|_2}{\|(1, \ldots, 1)\|_2} = \frac{\|(n, \ldots, n)\|_2}{\sqrt{n}} = n$$

On the other hand, for $x = (x_1,\ldots, x_n)$ with $\|x\|_2 = 1$ we have

$$\|Ax\|_2^2 = \left\|\left(\sum_{j=1}^n A_{ij}x_j\right)_{i=1}^n\right\|_2^2 = \sum_{i=1}^n \left|\sum_{j=1}^n A_{ij}x_j\right|^2 \stackrel{CSB}\le \sum_{i=1}^n \underbrace{\left(\sum_{j=1}^n A_{ij}^2\right)}_{\le n} \underbrace{\left(\sum_{j=1}^n x_j^2\right)}_{= 1} \le n^2$$

so taking the supremum over the unit sphere gives $\|A\| \le n$.

Therefore

$$\|A\| \le n \le \|J\|$$

It basically boils down to @Omnomnomnom's answer, but it might be useful to someone.

Answer 3

Let $A$ being a complex $n\times n$ matrix. Let $$R_i=\sum_{j\neq i} |A_{ij}|.$$

Gershgorin circle theorem implies that each eigenvalues of $A$ lies within at least one of the closed discs centered at $A_{ii}$, with radius $R_i$.

This particularly means that, if $A$ is diagonalizable, then $$\|A\|_2=\max_i |\lambda_i|\leq |A_{ii}|+R_i,$$ where $\lambda_i$ is an eigenvalue of $A$.

To the general case, you can see that $$\|A\|_2=\max_i |\sigma_i|,$$ where $\sigma_i^2$ is an eigenvalue of $B=A^*A$, and apply the aforementioned theorem to $B$.

Please see https://doi.org/10.1016/0024-3795(90)90120-2 and https://doi.org/10.13001/1081-3810.2866 to find some estimates to $$\left|\lambda_j-\frac{tr(A)}{n}\right|,$$ when $A$ is symmetric and nonsymmetric. You can finf more on SearchOnMath.