Why do we usually not want the eigenvalues of non-symmetric matrices?

Question

I came across this line in a class note I am reading where it discusses finding eigenvalues of matrices.

In reality we don't go all the way with Arnoldi. We stop at a decent value of 𝑘. Then the 𝑘 eigenvalues of 𝐻 are (usually) good approximations to 𝑘 extreme eigenvalues of 𝐴. Trefethen and Bau emphasize for non-symmetric 𝐴 that we may not want eigenvalues of 𝐴 in the first place! When they are badly conditioned, this led Trefethen and Embree to the theory of pseudospectra.

Why is this the case? I understand that for symmetric matrices, there are many nice properties of eigenvalues. For example the eigenvalues of a real symmetric matrix are real. SVD comes from the eigenvalues of $A^TA$ which is symmetric, etc.

But why are we so confident that we usually don't need to find the eigenvalues of non-symmetric matrix? Is it purely because of the nice properties of symmetric matrix that make us tend to formulate our problems that way? If someone can explain or point to where Trefethen and Bau explains it, that would be great. I have that book, but I can't find the explanation based in the relevant chapters I went through.

Answer 1

Stability under perturbations

Let $E$ be a perturbation such that $\|E\| \leq \varepsilon$.

If $A$ is symmetric, then the eigenvalues of $A+E$ are at a distance $\varepsilon$ from those of $A$. (Bauer-Fike Theorem.)

If $A$ is non-symmetric, then the eigenvalues of $A+E$ can be much further away. Example: start with a Jordan block of size $n$, and perturb the $(1,n)$ entry to $\varepsilon$; then the eigenvalues are the $k$th complex roots of $\varepsilon$, which have magnitude $\varepsilon^{1/n}$. If $\varepsilon=10^{-16}$ and $n=16$, an incredibly tiny perturbation changed the eigenvalues by $0.1$.

Instead, if $A$ is non-symmetric, then the $\delta$-pseudospectrum of $A+E$ is at a distance $\varepsilon$ from that of $A$ (follows from the definition).

So, the point is, how sure are you that the numbers in your matrix $A$ are correct? What if that measurement is only accurate to the third decimal digit? What about that tiny $2^{-52}$ error that you make when you truncate the coefficient 2/3 to a double? Those small perturbations affect your computed eigenvalues. There is little point in computing a number if you don't know how accurate it is in the first place. Or, worse, if you know from the start that it is inaccurate.

Pseudospectra capture nicely this concept that the true location of the eigenvalues is uncertain, for non-symmetric matrices, and provide a concept analogous to eigenvalues that is stable under perturbations.

Answer 2

Amazing question which has a long answer, but I will try to be concise. In the context of Krylov subspace methods for general matrices, the eigenvalues of a non-symmetric matrix mean very little. In “Any nonincreasing convergence curve is possible for GMRES”, Greenbaum et al. show that any nonincreasing convergence curve is possible for GMRES independent of the eigenvalue distribution of the matrix. To remedy this problem, Trefethen suggests pseudospectra of a matrix and pseudospectra-convergence analysis for various Krylov subspace methods (“Generalizing eigenvalue theorems to pseudospectra theorems” and “Pseudospectra and Spectra”, but really checkout anything Trefethen wrote on Krylov methods and pseudospectra). However, in some cases, determining pseudospectra of a matrix is difficult (without having the matrix). For example, if you are investigating the matrix representation of a linear operator (say, discretization of a PDE), you have a lot of functional analysis tools which don't help with the pseudospectra analysis at all.

Hence, other people are pushing for another analysis technique called numerical range (or, field of values). This technique is amenable to functional analysis techniques and there has been some exciting developments recently. (See “The Field of Values Bounds on Ideal GMRES” for example, but the last 10 or so years were amazing in terms of new theoretical results and their applications).

However, all of these methods provide an asymptotical limit, not a practical one. For example, you regularly see optimality (in the context of preconditioners) proofs, but to observe optimality in practice one has to be solving very large problems. Mark Embree (who worked with Trefethen on pseudospectra) has the paper “How descriptive are GMRES convergence bounds?”, where he demonstrates that all three types of bounds fail to provide informative and meaningful predictions regarding the convergence. They are usually incredibly pessimistic, and the convergence is achieved much earlier than predicted in practice.

I tend to use field of values in general, even for symmetric matrices -though you have to be careful with indefinite matrices, ratio field of values or other variants are better to use in that case, or use eigenvalues-. Most of the time, I interpret the result I obtained qualitatively rather than quantitatively. Which means that if I can prove that the residual reduces by 10% every iteration (miserably slow) independent of a parameter, I don't conclude that the convergence (tol < 1e-8) will be achieved in 175 iterations. I conclude that independent of the parameter of interest, the problem is solvable at most some number $k$ iterations which will be much smaller than the matrix size $n$.

There will be a lot of typos/grammatical mistakes in this answer, but it is late here. My apologies.

Answer 3

Comment on: "But why are we so confident that we usually don't need to find the eigenvalues of non-symmetric matrix?"

Eigenvalues and eigenspaces are relevant when you have an endomorphism, the same vector space as domain and range, like for instance in the linearization of an ODE system around some (equilibrium or periodic) solution. Then you can ask to decompose the corresponding system into smaller, decoupled systems, which the transformation to an eigen-basis would deliver. Many such tasks are derived from a variational formulation (finite elements, Galerkin) leading to eigenvalue or generalized eigenvalue problems with symmetric matrices.

In a more general situation, domain and range will be different, the matrix components will not encode easily visible structural information. Metric properties of the matrix or effective rank computations then lead to the spectral radius and singular spectrum. Restoring the endomorphism property for instance via an approximative inverse matrix and then considering the defect will also be better controlled via the singular spectrum.

As observed, structurally, the singular spectrum is related to the spectrum of the symmetric matrix $A^TA$ or more directly of the block matrix $\pmatrix {0&A\\A^T&0}$