3
$\begingroup$

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

$\endgroup$

3 Answers 3

2
$\begingroup$

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

$\endgroup$
2
$\begingroup$

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.

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

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.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .