On page 271 of Trefethen and Bau's Numerical Linear Algebra, it is constructed a matrix

$$A=2I_{m\times m}+0.5\cdot\frac{\text{rand}(m)}{\sqrt{m}}$$

for $m=200$, where rand(m) is an array with $m\times m$ measures of a normal random variable with mean zero and variance one.

The eigenvalues of this matrix are contained in a complex circle of radius $\frac{1}{2}$ and centre $2$. In the book it is stated $\|I-\frac{1}{2}A\|_2\approx \frac{1}{4}$. Where the norm is defined as $\|A\|_{2}=\sup\limits_{x\in \mathbb{C}}\frac{\|Ax\|}{\|x\|}$,i.e., the spectral norm.

I was wondering how can this result be obtained.

  • $\begingroup$ Is it just an application of Gershgorin's theorem? $\endgroup$ Dec 29 '20 at 0:33
  • $\begingroup$ I guess that the fact that the eigenvalues are contained in a circle of radius1/2 is a consequence of Gershgorin's theorem. But I do not see how to justify the claim about the norm. $\endgroup$
    – Leibniz
    Dec 29 '20 at 12:56

The book does not actually state a norm equality, rather they state that $$ \| (I - \tfrac{1}{2} A)^n \| \sim (1/4)^n$$ Here, $n$ is the degree of the Krylov polynomial used, for the purpose of analyzing $n$ steps of the GMRES iteration. Thus the approximation above describes the exponential decay behavior as $n$ increases. It is not literally true that for $n = 1$, $\| I - \tfrac{1}{2} A \|$ is close to $1/4$. In fact, we can show that $$ \| I - \tfrac{1}{2} A \| \approx 1/2, $$ or rather that the difference between the above norm and $1/2$ is small with high probability.

To see this, first note that $I - \tfrac{1}{2} A$ is $-\tfrac{1}{4 \sqrt{m}} \text{rand}(m)$, and what you call $\text{rand}(m)$ is known as a Gaussian matrix $G_m$, and is widely studied in random matrix theory. The spectral norm of your matrix is extremely well understood; the spectral norm of $G_m/\sqrt{m}$ is the same as the square root of the leading singular value of the Wishart matrix $$ \frac{1}{m} G_m G_m^T,$$ and the literature on Wishart matrices is extensive, as it is a natural generalization of classic probability distributions such as $\chi^2$ distribution. In fact, one can obtain information about the asymptotic behavior of the spectral measure of the Wishart matrix as $m$ becomes large. A well-known result of Marchenko-Pastur is that for $m$ large, the spectral measure of this Wishart matrix looks like a continuous measure supported on $[0,4]$. Thus the largest singular value will be very close to $4$ (note that it can be larger than $4$ with small probability), and thus after taking the square root, the spectral norm of $G_m/\sqrt{m}$ will be close to $2$. Dividing by $4$ yields a spectral norm estimate of $1/2$ for your matrix.

Let us now turn to the actual statement from the textbook, which is to show $$ \| (I - \tfrac{1}{2} A)^n \| \sim (1/4)^n.$$ The key result here is that if $p(z) = (1 - z/2)^n$, then $\|p(A)\|$ can be estimated by a constant times $\sup_{\lambda \in \sigma} |p(\lambda)|$, where $\sigma$ is the spectrum of $A$. It then remains to show the original statement from the textbook, which is that the spectrum of $A$ is distributed about a complex disk centered at $2$ with radius $1/2$. If this is true, then $p(\sigma)$ takes values on the complex disk of radius $(1/4)^n$; we are thus reduced to showing that the spectrum of $G_m/\sqrt{m}$ is distributed about the complex unit disk with high probability. This is, again, a famous result in random matrix theory, and is known as the circular law. You may wish to read some literature on random matrix theory for generalizations and other similar topics. Unfortunately the theory is not always suitable for proving reliability of numerical algorithms, but it has connections to other mathematical fields.

Also note that I believe Gerschgorin's theorem is too weak to provide an accurate estimate here.


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.