c11-0 (Numerical Recipes in C)

Eigensystems11.0 IntroductionAn N × N matrix A is said to have an eigenvector x and correspondingeigenvalue λ ifA · x = λx(11.0.1)Obviously any multiple of an eigenvector x will also be an eigenvector, but wewon’t consider such multiples as being distinct eigenvectors. (The zero vector is notconsidered to be an eigenvector at all.) Evidently (11.0.1) can hold only ifdet |A − λ1| = 0(11.0.2)which, if expanded out, is an N th degree polynomial in λ whose roots are the eigenvalues.

This proves that there are always N (not necessarily distinct) eigenvalues.Equal eigenvalues coming from multiple roots are called degenerate. Root-searchingin the characteristic equation (11.0.2) is usually a very poor computational methodfor finding eigenvalues. We will learn much better ways in this chapter, as well asefficient ways for finding corresponding eigenvectors.The above two equations also prove that every one of the N eigenvalues hasa (not necessarily distinct) corresponding eigenvector: If λ is set to an eigenvalue,then the matrix A − λ1 is singular, and we know that every singular matrix has atleast one nonzero vector in its nullspace (see §2.6 on singular value decomposition).If you add τ x to both sides of (11.0.1), you will easily see that the eigenvaluesof any matrix can be changed or shifted by an additive constant τ by adding tothe matrix that constant times the identity matrix.

The eigenvectors are unchangedby this shift. Shifting, as we will see, is an important part of many algorithmsfor computing eigenvalues. We see also that there is no special significance to azero eigenvalue. Any eigenvalue can be shifted to zero, or any zero eigenvaluecan be shifted away from zero.456Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).Chapter 11.45711.0 IntroductionDefinitions and Basic FactsA matrix is called symmetric if it is equal to its transpose,A = AToraij = aji(11.0.3)A = A†oraij = aji *(11.0.4)It is termed orthogonal if its transpose equals its inverse,AT · A = A · AT = 1(11.0.5)and unitary if its Hermitian conjugate equals its inverse. Finally, a matrix is callednormal if it commutes with its Hermitian conjugate,A · A† = A† · A(11.0.6)For real matrices, Hermitian means the same as symmetric, unitary means thesame as orthogonal, and both of these distinct classes are normal.The reason that “Hermitian” is an important concept has to do with eigenvalues.The eigenvalues of a Hermitian matrix are all real.

In particular, the eigenvaluesof a real symmetric matrix are all real. Contrariwise, the eigenvalues of a realnonsymmetric matrix may include real values, but may also include pairs of complexconjugate values; and the eigenvalues of a complex matrix that is not Hermitianwill in general be complex.The reason that “normal” is an important concept has to do with the eigenvectors.

The eigenvectors of a normal matrix with nondegenerate (i.e., distinct)eigenvalues are complete and orthogonal, spanning the N -dimensional vector space.For a normal matrix with degenerate eigenvalues, we have the additional freedom ofreplacing the eigenvectors corresponding to a degenerate eigenvalue by linear combinations of themselves. Using this freedom, we can always perform Gram-Schmidtorthogonalization (consult any linear algebra text) and find a set of eigenvectors thatare complete and orthogonal, just as in the nondegenerate case.

The matrix whosecolumns are an orthonormal set of eigenvectors is evidently unitary. A special caseis that the matrix of eigenvectors of a real, symmetric matrix is orthogonal, sincethe eigenvectors of that matrix are all real.When a matrix is not normal, as typified by any random, nonsymmetric, realmatrix, then in general we cannot find any orthonormal set of eigenvectors, nor evenany pairs of eigenvectors that are orthogonal (except perhaps by rare chance). Whilethe N non-orthonormal eigenvectors will “usually” span the N -dimensional vectorspace, they do not always do so; that is, the eigenvectors are not always complete.Such a matrix is said to be defective.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).It is called Hermitian or self-adjoint if it equals the complex-conjugate of its transpose(its Hermitian conjugate, denoted by “†”)458Chapter 11.EigensystemsLeft and Right Eigenvectorsx · A = λx(11.0.7)These are called left eigenvectors. By taking the transpose of equation (11.0.7), wesee that every left eigenvector is the transpose of a right eigenvector of the transposeof A. Now by comparing to (11.0.2), and using the fact that the determinant of amatrix equals the determinant of its transpose, we also see that the left and righteigenvalues of A are identical.If the matrix A is symmetric, then the left and right eigenvectors are justtransposes of each other, that is, have the same numerical values as components.Likewise, if the matrix is self-adjoint, the left and right eigenvectors are Hermitianconjugates of each other.

For the general nonnormal case, however, we have thefollowing calculation: Let XR be the matrix formed by columns from the righteigenvectors, and XL be the matrix formed by rows from the left eigenvectors. Then(11.0.1) and (11.0.7) can be rewritten asA · XR = XR · diag(λ1 . . . λN )XL · A = diag(λ1 . . . λN ) · XL(11.0.8)Multiplying the first of these equations on the left by XL , the second on the rightby XR , and subtracting the two, gives(XL · XR ) · diag(λ1 . .

. λN ) = diag(λ1 . . . λN ) · (XL · XR )(11.0.9)This says that the matrix of dot products of the left and right eigenvectors commuteswith the diagonal matrix of eigenvalues. But the only matrices that commute with adiagonal matrix of distinct elements are themselves diagonal. Thus, if the eigenvaluesare nondegenerate, each left eigenvector is orthogonal to all right eigenvectors exceptits corresponding one, and vice versa. By choice of normalization, the dot productsof corresponding left and right eigenvectors can always be made unity for any matrixwith nondegenerate eigenvalues.If some eigenvalues are degenerate, then either the left or the right eigenvectors corresponding to a degenerate eigenvalue must be linearly combined amongthemselves to achieve orthogonality with the right or left ones, respectively.

Thiscan always be done by a procedure akin to Gram-Schmidt orthogonalization. Thenormalization can then be adjusted to give unity for the nonzero dot products betweencorresponding left and right eigenvectors. If the dot product of corresponding left andright eigenvectors is zero at this stage, then you have a case where the eigenvectorsare incomplete! Note that incomplete eigenvectors can occur only where there aredegenerate eigenvalues, but do not always occur in such cases (in fact, never occurfor the class of “normal” matrices). See [1] for a clear discussion.Sample page from NUMERICAL RECIPES IN C: THE ART OF SCIENTIFIC COMPUTING (ISBN 0-521-43108-5)Copyright (C) 1988-1992 by Cambridge University Press.Programs Copyright (C) 1988-1992 by Numerical Recipes Software.Permission is granted for internet users to make one paper copy for their own personal use.

Further reproduction, or any copying of machinereadable files (including this one) to any servercomputer, is strictly prohibited. To order Numerical Recipes books,diskettes, or CDROMsvisit website http://www.nr.com or call 1-800-872-7423 (North America only),or send email to trade@cup.cam.ac.uk (outside North America).While the eigenvectors of a non-normal matrix are not particularly orthogonalamong themselves, they do have an orthogonality relation with a different set ofvectors, which we must now define. Up to now our eigenvectors have been columnvectors that are multiplied to the right of a matrix A, as in (11.0.1). These, moreexplicitly, are termed right eigenvectors. We could also, however, try to find rowvectors, which multiply A to the left and satisfy45911.0 IntroductionIn both the degenerate and nondegenerate cases, the final normalization tounity of all nonzero dot products produces the result: The matrix whose rowsare left eigenvectors is the inverse matrix of the matrix whose columns are righteigenvectors, if the inverse exists.Multiplying the first equation in (11.0.8) by XL , and using the fact that XLand XR are matrix inverses, we getX−1R · A · XR = diag(λ1 .