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][.]

4 ]=[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 . 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.

5 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. So, formally, the matrixAis positivesemi-definite if it can be obtained as:A=XXT(19)for a certain matrixX(containing real numbers).

6 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).

7 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.

8 (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.

9 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. 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.

10 (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. 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.