Approximation of the norm of the powers of this random matrix

146 Views Asked by At

This is from example 35.1 in Numerical Linear Algebra by Trefethen and Bau.

Suppose that $ B $ is a 200 x 200 real matrix with entries i.i.d from $ \mathcal{N}(0,\sigma^2) $ where $ \sigma = 0.5/\sqrt{200} $. Let $ A = 2I + B $. The eigenvalues of $ A $ are approximately uniformly distributed in the disk of radius 1/2 centered at $ z = 2 $ in the complex plane. The matrix $ I -A/2 $ is then a random matrix scaled so that its spectrum approximately fills the disk of radius 1/4 centered at $ z = 0 $. The authors then claim that this justifies the following: $ \|(I-A/2)^n\|_2 \approx 4^{-n} $. Why is this?

It seems like this should be relatively straightforward, and I must be missing something obvious. In attempting to figure this out, I've come across the formula: $\lim_{n \to \infty} \|C^n\|^{1/n} = \rho(C) $, where $ \rho $ is the spectral radius of $ C $. However, the claim as stated applies to $ n = 1,2,3,\ldots $.

Thanks!

[Edit] In particular, I don't see why the knowledge that the eigenvalues of $ I - A/2 $ are approximately evenly spread over the disk of radius 1/4 centered at $ z = 0 $ implies that $ \|(I-A/2)^n\|_2 \approx 4^{-n} $.

1

There are 1 best solutions below

0
On

After some investigation, I've concluded that the claim is false.

It should be that $ \|(I-A/2)^n\|_2 \approx 2(4^{-n})$. I don't want to get too far into random matrix theory, but apparently we have that for large $ n $ and $ X_{ij} \sim \mathcal{N}(0,\sigma^2) $, $ \|X\|_2 \approx 2 \sigma \sqrt{n} $ and $ \rho(X) \approx \sigma \sqrt{n} $. Theorem 1.1 in this paper justifies the first approximation. The second approximation is justified because the eigenvalues of $ X $ are distributed uniformly across the disk of radius $ \sigma \sqrt{n} $, so the largest eigenvalue in absolute value will likely be near the edge of the disk. Combining, we have that $ \|X\|_2 \approx 2\rho(X) $.

The random matrix $ I - A/2 $ has the same eigenvalue distribution as $ X $ where $ X_{ij} \sim \mathcal{N}(0, 0.25/\sqrt{200}) $. The $n$th power of $ X $ has eigenvalues spread roughly uniformly over the disk of radius $ \rho(X)^n $, so $ \|(I-A/2)^n\|_2 \approx 2(4^{-n}) $.