18
$\begingroup$

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.

$\endgroup$
2
28
$\begingroup$

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$ could be just anywhere in the complex plane. No bound can be formulated a priori. (Counterexample to show that no bound exist: 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 $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.

$\endgroup$
6
  • 2
    $\begingroup$ This is a good answer. But the asker failed to give context, so it may not be immediately relevant. The excerpt is from Gilbert Strang's Learning from Data book, particularly in the Numerical Linear Algebra section between "Krylov Subspaces and Arnoldi iteration" and "Linear systems by Arnoldi and GMRES" $\endgroup$ Aug 8 at 7:53
  • $\begingroup$ Interesting, can you explain a bit on why symmetric matrix is stable under perturbation while the non-symmetric ones can have eigenvalues all over the place? $\endgroup$ Aug 8 at 14:46
  • $\begingroup$ @CuriousMind I have added some more detail. $\endgroup$ Aug 8 at 14:58
  • $\begingroup$ @FedericoPoloni thank you let me study a bit more $\endgroup$ Aug 8 at 15:05
  • 1
    $\begingroup$ "If $A$ is non-symmetric, then the eigenvalues of $A+E$ can be just anywhere on the complex plane. No bound can be formulated a priori." This is wrong. Bhatia's Matrix Analysis Theorem VIII.1.5 contains the bound $4(\|A\|+\epsilon)^{1-1/n}\epsilon^{1/n}$ in the optimal matching distance between the eigenvalues of $A$ and $A+E$. No doubt, $\epsilon^{1/n}$ is an unfathomably bad scaling, but the claim that the eigenvalues of $A+E$ can be anywhere in the complex plane and that no a priori bound is possible is overstated. $\endgroup$
    – eepperly16
    Aug 10 at 22:01
8
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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

$\endgroup$
-1
$\begingroup$

Operationally, you need the eigenvalues from a non-symmetric matrix for hypothesis testing in multivariate statistics. During a multivariate normal linear regression analysis (multiple dependent outcomes that are normally distributed), eigenanalysis is always used to calculate Wilks-Lambda for the non-symmetric matrix ${\mathbf W}^{-1}{\mathbf B}$. The generalized eigenvalue problem can be used for eigenanalysis of a non-symmetric matrix, and is typically solved with the QR algorithm. The QR algorithm starts by rearranging all elements in upper Hessenberg form, followed by iterative production of a series of Hessenberg matrices which converge to a triangular matrix. During each iteration a bulge is created and chased down using a Givens transformation. I favor an alternative approach which allows use of the symmetric eigenvalue problem and Power Matrix Theorem to extract eigenvalues from ${\mathbf W}^{-1}{\mathbf B}$. This is based on the fact that the eigenvalues of the non-symmetric matrix ${\bf W}^{-1}{\bf B}$ are equal to the eigenvalues of the symmetric matrix (${\bf W}^{1/2})^{-1}{\bf B}({\bf W}^{1/2})^{-1}$, in accordance with the following Theorem.

Theorem (Equivalent Eigenvalues): The eigenvalues of the square non-symmetric matrix $\mathbf{W}^{-1}\mathbf{B}$ are equal to the eigenvalues of the square symmetric matrix $(\mathbf{W}^{1/2})^{-1}\mathbf{B}(\mathbf{W}^{1/2})^{-1}$.

Proof: Let $(\mathbf{W}^{-1} \mathbf{B}-\boldsymbol{\Lambda}\mathbf{I})\mathbf{E}=\mathbf{0}$, then it is shown that \begin{equation} \begin{split} (\mathbf{W}^{-1} \mathbf{B}-\boldsymbol{\Lambda}\mathbf{I})\mathbf{E}&=\mathbf{0}\\ (\mathbf{B}-\boldsymbol{\Lambda}\mathbf{W})\mathbf{E}&=\mathbf{0}\quad \quad \textrm{ mult. by }\mathbf{W}\\ (\mathbf{B}-\boldsymbol{\Lambda}\mathbf{W}^{1/2}\mathbf{W}^{1/2})\mathbf{E}&=\mathbf{0}\quad \quad \textrm{ sub. } \mathbf{W} \textrm{ with } \mathbf{W}^{1/2} \mathbf{W}^{1/2}\\ (\mathbf{W}^{1/2})^{-1}(\mathbf{B}-\boldsymbol{\Lambda}\mathbf{W}^{1/2}\mathbf{W}^{1/2})\mathbf{E}&=(\mathbf{W}^{1/2})^{-1}\mathbf{0}=\mathbf{0}\quad \quad \textrm{ mult. by } (\mathbf{W}^{1/2})^{-1}\\ [(\mathbf{W}^{1/2})^{-1}\mathbf{B}-\boldsymbol{\Lambda}\mathbf{W}^{1/2}](\mathbf{W}^{1/2})^{-1}\mathbf{W}^{1/2} \mathbf{E}&=\mathbf{0}\quad \quad \textrm{ insert } (\mathbf{W}^{1/2})^{-1}\mathbf{W}^{1/2}=\mathbf{I}\\ [(\mathbf{W}^{1/2})^{-1}\mathbf{B}(\mathbf{W}^{1/2})^{-1} -\boldsymbol{\Lambda}\mathbf{I}]\mathbf{W}^{1/2} \mathbf{E}&=\mathbf{0} \blacksquare .\\ \end{split} \end{equation} The above proof shows that the eigenvalues of $\mathbf{W}^{-1}\mathbf{B}$ are the same as the eigenvalues of $(\mathbf{W}^{1/2})^{-1}\mathbf{B}(\mathbf{W}^{1/2})^{-1}$. Because $(\mathbf{W}^{1/2})^{-1}\mathbf{B}(\mathbf{W}^{1/2})^{-1}$ is square symmetric, extracting the eigenvalues becomes a symmetric eigenvalue problem, which can be solved using, for example, the Jacobi method or singular value decomposition. The above Theorem to obtain the eigenvalue matrix $\boldsymbol{\Lambda}$ from the non-symmetric matrix $\mathbf{W}^{-1}\mathbf{B}$ fulfills our need in order to calculate Wilk's Lambda. One should also recognize, however, that the eigenvectors of $\mathbf{W}^{-1}\mathbf{B}$ are not equal to the eigenvectors of $(\mathbf{W}^{1/2})^{-1}\mathbf{B}(\mathbf{W}^{1/2})^{-1}$.

$\endgroup$
3
  • 4
    $\begingroup$ I don't believe anyone would argue with the point that we can calculate eigenvalues for non-symmetric matrices, as well as that there are better or worse methods to do it. Moreover, I believe there certainly are applications where eigenvalues is what you need exactly. However, the point of the question is totally different. $\endgroup$
    – Anton Menshov
    Aug 8 at 22:31
  • 1
    $\begingroup$ Agreed with @AntonMenshov. If you read any of the other answers, you see peer-reviewed, proven applications where eigenvalues of a non-symmetric matrix tells you nothing of interest. Furthermore, they can even be misleading. $\endgroup$ Aug 8 at 22:33
  • 2
    $\begingroup$ Consider Federico Poloni's answer. If nothing, roundoff errors will prevent successful computation of the exact position of eigenvalues of the matrix of interest, generally. So there may not be any information left in eigenvalues. This may be because there are small perturbations in the matrix, there are roundoff error occurring in the intermediate steps of calculations, or one of the many other reasons. Pseudospectra gives you a way out in the sense that you know "for sure" that the eigenvalues of the original matrix is in $\varepsilon$ neighborhood of the "computational" matrix. $\endgroup$ Aug 8 at 22:51

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.