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


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

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

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

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.