The Eigen-Decomposition: Eigenvalues and Eigenvectors

1 The Eigen-Decomposition: Eigenvalues and EigenvectorsHerv Abdi11 OverviewEigenvectorsandeigenvaluesare numbers and vectors associatedto square matrices, and together they provide theeigen-decompo-sitionof a matrix which analyzes the structure of this matrix. Eventhough the eigen-decomposition does not exist for all square ma-trices, it has a particularly simple expression for a class of matri-ces often used in multivariate analysis such as correlation, covari-ance, or cross-product matrices. The eigen-decomposition of thistype of matrices is important in statistics because it is used to findthe maximum (or minimum) of functions involving these matri-ces. For example, principal component analysis is obtained fromthe eigen-decomposition of a covariance matrix and gives the leastsquare estimate of the original data and Eigenvalues are also referred to ascharacter-istic vectors and latent rootsorcharacteristic equation(in German, eigen means specific of or characteristic of ).

2 The set of eigen-values of a matrix is also called : Neil Salkind (Ed.) (2007).Encyclopedia of Measurement and Oaks (CA): correspondence to: Herv AbdiProgram in Cognition and Neurosciences, MS: ,The University of Texas at Dallas,Richardson, TX 75083 0688, herve1 Herv Abdi:The Eigen-Decomposition32128u11Au-111-1uAuab 22 Figure 1:Two Eigenvectors of a and definitionThere are several ways to define Eigenvectors and Eigenvalues , themost common approach defines an eigenvector of the matrixAasa vectoruthat satisfies the following equation:Au= u.(1)when rewritten, the equation becomes:(A I)u=0,(2)where is a scalar called theeigenvalueassociated to a similar manner, we can also say that a vectoruis an eigen-vector of a matrixAif the length of the vector (but not its direction)is changed when it is multiplied example, the matrix:A=[2321](3)has the Eigenvectors :u1=[32]with eigenvalue 1=4(4)2 Herv Abdi:The Eigen-Decompositionandu2=[ 11]with eigenvalue 2= 1(5)We can verify (as illustrated in Figure 1) that only the length ofu1andu2is changed when one of these two vectors is multiplied bythe matrixA:[2321][32]=4[32]=[128](6)and[232 1][ 11]= 1[ 11]=[1 1].

3 (7)For most applications we normalize the Eigenvectors ( ,trans-form them such that their length is equal to one):uTu=1 .(8)For the previous example we obtain:u1=[. ].(9)We can check that:[2321][. ]=[ ]=4[. ](10)and[2321][ . ]=[.7071 .7071]= 1[ . ].(11)Traditionally, we put together the set of Eigenvectors ofAin a ma-trix denotedU. Each column ofUis an eigenvector ofA. Theeigenvalues are stored in a diagonal matrix (denoted ), where thediagonal elements gives the Eigenvalues (and all the other valuesare zeros). We can rewrite the first equation as:AU=U ;(12)3 Herv Abdi:The Eigen-Decompositionor also as:A=U U 1.(13)For the previous example we obtain:A=U U 1=[3 121][400 1][.. ]=[2321].(14)It is important to note that not all matrices have example, the matrix[0100]does not have Eigenvalues . Evenwhen a matrix has Eigenvalues and Eigenvectors , the computationof the Eigenvectors and Eigenvalues of a matrix requires a largenumber of computations and is therefore better performed by :An infinity of Eigenvectors for one eigenvalueIt is only through a slight abuse of language that we can talk abouttheeigenvector associated withonegiven eigenvalue.

4 Strictly speak-ing, there is aninfinityof Eigenvectors associated to each eigen-value of a matrix. Because any scalar multiple of an eigenvector isstill an eigenvector, there is, in fact, an (infinite) family of eigen-vectors for each eigenvalue, but they are all proportional to eachother. For example,[1 1](15)is an eigenvector of the matrixA:[2321].(16)4 Herv Abdi:The Eigen-DecompositionTherefore:2 [1 1]=[2 2](17)is also an eigenvector ofA:[2321][2 2]=[ 22]= 1 2[1 1].(18)3 Positive (semi-)definite matricesA type of matrices used very often in statistics are calledpositivesemi-definite. The eigen-decomposition of these matrices alwaysexists, and has a particularly convenient form. A matrix is said tobe positive semi-definite when it can be obtained as the product ofa matrix by its transpose. This implies that a positive semi-definitematrix is always symmetric.

5 So, formally, the matrixAis positivesemi-definite if it can be obtained as:A=XXT(19)for a certain matrixX(containing real numbers). Positive semi-definite matrices of special relevance for multivariate analysis pos-itive semi-definite matrices include correlation matrices. covari-ance, and, cross-product important properties of a positive semi-definite matrix isthat its Eigenvalues are always positive or null, and that its eigen-vectors are pairwise orthogonal when their Eigenvalues are differ-ent. The Eigenvectors are also composed of real values (these lasttwo properties are a consequence of the symmetry of the matrix,for proofs see, ,Strang, 2003; or Abdi & Valentin, 2006). Be-cause Eigenvectors corresponding to different Eigenvalues are or-thogonal, it is possible to store all the Eigenvectors in an orthogo-nal matrix (recall that a matrix is orthogonal when the product ofthis matrix by its transpose is a diagonal matrix).

6 This implies the following equality:U 1=UT.(20)5 Herv Abdi:The Eigen-DecompositionWe can, therefore, express the positive semi-definite matrixAas:A=U UT(21)whereUTU=Iare the normalized Eigenvectors ; if they are notnormalized thenUTUis a diagonal example, the matrix:A=[3113](22)can be decomposed as:A=U UT= 12 12 12 12 [4002] 12 12 12 12 =[3113],(23)with 12 12 12 12 12 12 12 12 =[1001].(24) a matrix is positive semi-definite we can rewrite Equation21 asA=U UT =UTAU.(25)This shows that we can transform the matrixAinto an equivalentdiagonalmatrix. As a consequence, the eigen-decomposition of apositive semi-definite matrix is often referred to as Abdi:The definition for positive semi-definite ma-tricesA matrixAis said to be positive semi-definite if we observe thefollowing relationship for any non-zero vectorx:xTAx 0 x.

7 (26)(when the relationship is 0 we say that the matrix is negativesemi-definite).When all the Eigenvalues of a symmetric matrix are positive,we say that the matrix ispositive definite. In that case, Equation 26becomes:xTAx>0 x.(27)4 Trace, Determinant, Eigenvalues of a matrix are closely related to three importantnumbers associated to a square matrix, namely itstrace, itsdeter-minantand trace of a matrixAis denotedtrace{A}and is equal to the sumof its diagonal elements. For example, with the matrix:A= 123456789 (28)we obtain:trace{A}=1+5+9=15 .(29)The trace of a matrix is also equal to the sum of its Eigenvalues :trace{A}= ` `=trace{ }(30)with being the matrix of the Eigenvalues ofA. For the previousexample, we have: =diag{ , , 0}.(31)7 Herv Abdi:The Eigen-DecompositionWe can verify that:trace{A}= ` `= +( )=15(32) and rankAnother classic quantity associated to a square matrix is itsdeter-minant.

8 This concept of determinant, which was originally de-fined as a combinatoric notion, plays an important r le in com-puting the inverse of a matrix and in finding the solution of sys-tems of linear equations (the termdeterminantis used becausethis quantity determines the existence of a solution in systems oflinear equations). The determinant of a matrix is also equal to theproduct of its Eigenvalues . Formally, if|A|the determinant ofA, wehave:|A|= ` `with `being the`-th eigenvalue ofA.(33)For example, the determinant of matrixA(from the previous sec-tion), is equal to:|A|= 0=0 .(34)Finally, therankof a matrix can be defined as being the num-ber of non-zero Eigenvalues of the matrix. For our example:rank{A}=2 .(35)For a positive semi-definite matrix, the rank corresponds to thedimensionality of the Euclidean space which can be used to rep-resent the matrix.

9 A matrix whose rank is equal to its dimensionsis called afull rankmatrix. When the rank of a matrix is smallerthan its dimensions, the matrix is calledrank-deficient,singular,ormulticol inear. Only full rank matrices have an properties ofthe eigen-decompositionThe eigen-decomposition is important because it is involved inproblems of optimization. For example, in principal component8 Herv Abdi:The Eigen-Decompositionanalysis, we want to analyze anI JmatrixXwhere the rows areobservations and the columns are variables describing these ob-servations. The goal of the analysis is to find rowfactor scores,such that these factor scores explain as much of the variance ofXas possible, and such that the sets of factor scores are pairwiseorthogonal. This amounts to defining the factor score matrix asF=XP,(36)under the constraints thatFTF=PTXTXP(37)is a diagonal matrix ( ,Fis an orthogonal matrix) and thatPTP=I(38)( ,Pis an orthonormal matrix).

10 There are several ways of obtain-ing the solution of this problem. One possible approach is to usethe technique of the Lagrangian multipliers where the constraintfrom Equation 38 is expressed as the multiplication with a diago-nal matrix of Lagrangian multipliers denoted in order to give thefollowing expression (PTP I)(39)(see Harris, 2001; and Abdi & Valentin, 2006; for details). Thisamount to defining the following equationL=FTF (PTP I)=PTXTXP (PTP I).(40)In order to find the values ofPwhich give the maximum values ofL, we first compute the derivative ofLrelative toP: L P=2 XTXP 2 P,(41)and then set this derivative to zero:XTXP P=0 XTXP= P.(42)9 Herv Abdi:The Eigen-DecompositionBecause is diagonal, this is clearly an eigen-decomposition prob-lem, and this indicates that is the matrix of Eigenvalues of thepositive semi-definite matrixXTXordered from the largest to thesmallest and thatPis the matrix of Eigenvectors ofXTXassociatedto.