Chapter 10 Eigenvalues and Singular Values - MathWorks

1 Chapter 10 Eigenvalues and SingularValuesThis Chapter is about Eigenvalues and Singular Values of matrices. Computationalalgorithms and sensitivity to perturbations are both Eigenvalue and Singular Value DecompositionsAneigenvalueandeigenvector of a square matrixAare a scalar and a nonzerovectorxso thatAx= valueand pair ofsingular vectorsof a square or rectangular matrixAare a nonnegative scalar and two nonzero vectorsuandvso thatAv= u,AHu= superscript onAHstands forHermitian transposeand denotes the complexconjugate transpose of a complex matrix. If the matrix is real, thenATdenotes thesame matrix. InMatlab, these transposed matrices are denoted byA'.The term eigenvalue is a partial translation of the German eigenwert. Acomplete translation would be something like own value or characteristic value, but these are rarely used.

2 The term Singular value relates to the distance betweena matrix and the set of Singular play an important role in situations where the matrix is a trans-formation from one vector space onto itself. Systems of linear ordinary differentialequations are the primary examples. The Values of can correspond to frequenciesof vibration, or critical Values of stability parameters, or energy levels of Values play an important role where the matrix is a transformation fromone vector space to a different vector space, possibly with a different of over- or underdetermined algebraic equations are the primary 16, 201312 Chapter 10. Eigenvalues and Singular ValuesThe definitions of eigenvectors and Singular vectors do not specify their nor-malization. An eigenvectorx, or a pair of Singular vectorsuandv, can be scaled byany nonzero factor without changing any other important properties.

3 Eigenvectorsof symmetric matrices are usually normalized to have Euclidean length equal to one, x 2= 1. On the other hand, the eigenvectors of nonsymmetric matrices often havedifferent normalizations in different contexts. Singular vectors are almost alwaysnormalized to have Euclidean length equal to one, u 2= v 2= 1. You can stillmultiply eigenvectors, or pairs of Singular vectors, by 1 without changing eigenvalue-eigenvector equation for a square matrix can be written(A I)x= 0, x = implies thatA Iis Singular and hence thatdet(A I) = definition of an eigenvalue, which does not directly involve the correspondingeigenvector, is thecharacteristic equationorcharacteristic polynomialofA. Thedegree of the polynomial is the order of the matrix. This implies that ann-by-nmatrix hasneigenvalues, counting multiplicities.

4 Like the determinant itself, thecharacteristic polynomial is useful in theoretical considerations and hand calcula-tions, but does not provide a sound basis for robust numerical 1, 2, .. , nbe the Eigenvalues of a matrixA, letx1, x2, .. , xnbe a setof corresponding eigenvectors, let denote then-by-ndiagonal matrix with the jon the diagonal, and letXdenote then-by-nmatrix whosejth column isxj. ThenAX=X .It is necessary to put on the right in the second expression so that each column ofXis multiplied by its corresponding eigenvalue. Now make a key assumption thatis not true for all matrices assume that the eigenvectors are linearly 1exists andA=X X 1,with nonsingularX. This is known as theeigenvalue decompositionof the it exists, it allows us to investigate the properties ofAby analyzing the diagonalmatrix.

5 For example, repeated matrix powers can be expressed in terms of powersof scalars:Ap=X pX the eigenvectors ofAare not linearly independent, then such a diagonal decom-position does not exist and the powers ofAexhibit a more complicated any nonsingular matrix, thenA=T BT 1is known as asimilarity transformationandAandBare said to besimilar. IfAx= xandx=T y, thenBy= y. In other words, a similarity transforma-tion preserves Eigenvalues . The eigenvalue decomposition is an attempt to find asimilarity transformation to diagonal Eigenvalue and Singular Value Decompositions3 Written in matrix form, the defining equations for Singular Values and vectorsareAV=U ,AHU=V is a matrix the same size asAthat is zero except possibly on its maindiagonal. It turns out that Singular vectors can always be chosen to be perpendicularto each other, so the matricesUandV, whose columns are the normalized singularvectors, satisfyUHU=IandVHV=I.

6 In other words,UandVareorthogonalif they are real, orunitaryif they are complex. Consequently,A=U VH,with diagonal and orthogonal or unitaryUandV. This is known as thesingularvalue decomposition , orSVD, of the abstract linear algebra terms, Eigenvalues are relevant if a square,n-by-nmatrixAis thought of as mappingn-dimensional space onto itself. We try to finda basis for the space so that the matrix becomes diagonal. This basis might becomplex even ifAis real. In fact, if the eigenvectors are not linearly independent,such a basis does not even exist. The SVD is relevant if a possibly rectangular,m-by-nmatrixAis thought of as mappingn-space ontom-space. We try to findone change of basis in the domain and a usually different change of basis in therange so that the matrix becomes diagonal. Such bases always exist and are alwaysreal ifAis real.

7 In fact, the transforming matrices are orthogonal or unitary, sothey preserve lengths and angles and do not magnify thann, then in the full SVD,Uis a large, squarem-by-mmatrix. The lastm ncolumns ofUare extra ; they are not neededA=U V A=U V Figure and economy 10. Eigenvalues and Singular Valuesto reconstructA. A second version of the SVD that saves computer memory ifAis rectangular is known as theeconomy-sizedSVD. In the economy version, onlythe firstncolumns ofUand firstnrows of are computed. The matrixVisthe samen-by-nmatrix in both decompositions. Figure shows the shapes ofthe various matrices in the two versions of the SVD. Both decompositions can bewrittenA=U VH, even though theUand in the economy decomposition aresubmatrices of the ones in the full A Small ExampleAn example of the eigenvalue and Singular value decompositions of a small, squarematrix is provided by one of the test matrices from = gallery(3)The matrix isA= 149 50 154537 180 546 27 9 25.

8 This matrix was constructed in such a way that the characteristic polynomial factorsnicely:det(A I) = 3 6 2+ 11 6= ( 1)( 2)( 3).Consequently, the three Eigenvalues are 1= 1, 2= 2, and 3= 3, and = 1 0 00 2 00 0 3 .The matrix of eigenvectors can be normalized so that its elements are all integers:X= 1 47 3 9 490 19 .It turns out that the inverse ofXalso has integer entries:X 1= 130 43 13327 9 28 3 1 3 .These matrices provide the eigenvalue decomposition of our example:A=X X SVD of this matrix cannot be expressed so neatly with small Singular Values are the positive roots of the equation 6 668737 4+ 4096316 2 36 = 0,but this equation does not factor nicely. The Symbolic Toolbox eigshow5svd(sym(A))returns exact formulas for the Singular Values , but the overall length of the result is922 characters.

9 So we compute the SVD numerically.[U,S,V] = svd(A)producesU = = = expressionU*S*V'generates the original matrix to within roundoff (3), notice the big difference between the Eigenvalues , 1, 2, and3, and the Singular Values , 817, , and This is related, in a way that wewill make more precise later, to the fact that this example is very far from being asymmetric eigshowThe functioneigshowis available in theMatlabdemosdirectory. The input toeigshowis a real, 2-by-2 matrixA, or you can choose anAfrom a pull-down listin the title. The defaultAisA=(1/4 3/41 1/2).Initially,eigshowplots the unit vectorx= [1,0] , as well as the vectorAx, whichstarts out as the first column ofA. You can then use your mouse to movex, shownin green, around the unit circle.

10 As you movex, the resultingAx, shown in blue,also moves. The first four subplots in Figure show intermediate steps asxtraces out a green unit circle. What is the shape of the resulting orbit ofAx? Animportant, and nontrivial, theorem from linear algebra tells us that the blue curveis an a proof by GUI of this caption foreigshowsays MakeAxparallel tox. For such a directionx, the operatorAis simply a stretching or magnification by a factor . In otherwords,xis an eigenvector and the length ofAxis the corresponding 10. Eigenvalues and Singular ValuesxA*xxA*xxA*xxA*xxA*xxA*xFigure last two subplots in Figure show the Eigenvalues and eigenvectorsof our 2-by-2 example. The first eigenvalue is positive, soAxlies on top of theeigenvectorx. The length ofAxis the corresponding eigenvalue; it happens to be5/4 in this example.