# 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? – Omnomnomnom Jul 23 '18 at 22:13
• Is that "Cauchy Schwarz Bunyakovsky"? – Omnomnomnom Jul 23 '18 at 22:15
• @Omnomnomnom Yes it is. – mechanodroid Jul 23 '18 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}$ – Omnomnomnom Jul 23 '18 at 22:19