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

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

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

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.

• What is "CSB" here? Jul 23, 2018 at 22:13
• Is that "Cauchy Schwarz Bunyakovsky"? Jul 23, 2018 at 22:15
• @Omnomnomnom Yes it is. Jul 23, 2018 at 22:15
• Neat. If you're interested in writing this using traces rather than summations, we have $$\|Ax\|_2^2 = (x^TA^TAx) = \operatorname{Tr}(A^TAxx^T)^2 \leq \operatorname{Tr}(A^TA)\operatorname{Tr}(xx^T)$$ where again, the idea is that we have applied CSB to the Hilbert-Schmidt (AKA Frobenius) inner product over $\Bbb R^{n \times n}$ Jul 23, 2018 at 22:19

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.