Eigenvalues and eigenvectors

For any matrix ${\bf A}$, if there exist a vector $\phi$ and a value $\lambda$ such that

$${\bf A}{\bf\phi}=\lambda {\bf\phi}$$

then $\lambda$ and ${\bf\phi}$ are called the eigenvalue and eigenvector of matrix ${\bf A}$, respectively. Note that the eigenvector ${\bf\phi}$ is not unique but up to any scaling factor, i.e, if ${\bf\phi}$ is the eigenvector of ${\bf A}$ so is $c{\bf\phi}$ with any costant $c$. Typically for the uniqueness of ${\bf\phi}$, we keep if normalized with $\vert\vert{\bf\phi}\vert\vert=1$.

To obtain $\lambda$, rewrite the above equation as

$$(\lambda {\bf I}-{\bf A}) {\bf\phi} =0$$

which is a homogeneous equation system. For this system to have non-zero solution for ${\bf\phi}$, the determinant of its coefficient matrix has to be zero:

$$det(\lambda {\bf I}-{\bf A})=\vert \lambda {\bf I}-{\bf A} \vert = 0$$

Solving this $n$th order equation of $\lambda$, we get $n$ eigenvalues $\{ \lambda_1,\cdots,\lambda_n \}$. Substituting each $\lambda_i$ back into the equation system, we get the corresponding eigenvector ${\bf\phi_i}$. We can put all $n$ equations ${\bf A}{\bf\phi}_i=\lambda_i{\bf\phi}_i$ together and have

$${\bf A}[{\bf\phi_1},\cdots,{\bf\phi}_n] =[\lambda_1 {\bf\p... ... \vdots \\ 0 & 0 & \cdots & \lambda_n \end{array} \right]$$

or in a more compact matrix form,

$${\bf A}{\bf\Phi}={\bf\Phi}{\bf\Lambda}, \;\;\;\;\;\;\mbox{or}\;\;\;\;\;\;\; {\bf\Phi}^{-1}{\bf A}{\bf\Phi}={\bf\Lambda}$$

where

$${\bf\Lambda}=diag[\lambda_1,\cdots,\lambda_n] \;\;\;\;\;\... ...and}\;\;\;\;\;\;\; {\bf\Phi}=[{\bf\phi}_1,\cdots,{\bf\phi}_n]$$

are the diagonal eigenvalue matrix and eigenvector matrix, respectively.

The spectrum of an $N\times N$ square matrix ${\bf A}$ the set of its eigenvalues $\{\lambda_1,\cdots,\lambda_N\}$. The spectral radius of ${\bf A}$, denoted by $\rho({\bf A})$, is the maximum of the absolute values of the elements of its spectrum:

$$\rho({\bf A})=\max(\vert\lambda_1\vert,\cdots,\vert\lambda_N\vert)$$

The absolute value of a complex number $z=x+jy$ is $\vert z\vert=\sqrt{x^2+y^2}$, the Euclidean distance between $z$ and the origin of the complex plane. If all eigenvalues are sorted such that $\vert\lambda_1\vert\ge\cdots \ge\vert\lambda_N\vert$ then $\rho({\bf A})=\vert\lambda_1\vert$.

The trace and determinant of ${\bf A}$ can be obtained from its eigenvalues

$$tr({\bf A}) =\sum_{k=1}^n \lambda_k, \;\;\;\;\;\mbox{and}\;\;\;\;\;\;\; det({\bf A}) =\prod_{k=1}^n \lambda_k$$

It can also be shown that

• ${\bf A}^T$ has the same eigenvalues and eigenvectors as ${\bf A}$.
• ${\bf A}^m$ has the same eigenvectors as ${\bf A}$, but its eigenvalues are $\{\lambda_1^m,\cdots,\lambda_n^m \}$, where $m$ is a positive integer.
• In particular when $m=-1$, i.e., the eigenvalues of ${\bf A}^{-1}$ are $\{1/\lambda_1,\cdots,1/\lambda_n \}$.

The eigenvalues and eigenvectors of a matrix are invariant under any unitary transform ${\bf B}={\bf R}^*{\bf A}{\bf R}$. To prove this, we first assume ${\bf\Lambda}=diag(\lambda_1,\cdots,\lambda_N)$ and ${\bf\Phi}$ are the eigenvalue and eigenvector matrices of a square matrix ${\bf A}$:

$${\bf A}{\bf\Phi}={\bf\Phi}{\bf\Lambda}$$

and ${\bf\Sigma}=diag(\sigma_1,\cdots,\sigma_N)$ and ${\bf\Psi}$ are the eigenvalue and eigenvector matrices of ${\bf B}={\bf R}^*{\bf A}{\bf R}$, a unitary transform of ${\bf A}$:

$${\bf B}{\bf\Psi}=\left({\bf R}^*{\bf A}{\bf R}\right){\bf\Psi}={\bf\Psi}{\bf\Sigma}$$

Left-multiplying ${\bf R}$ on both sides we get the eigenequation of ${\bf A}$

$${\bf R}{\bf R}^*{\bf A}{\bf R}{\bf\Psi} ={\bf A}{\bf R}{\bf\Psi}={\bf R}{\bf\Psi}{\bf\Sigma}$$

with same eigenvalue and igenvector matrices

$${\bf R}{\bf\Psi}={\bf\Phi},\;\;\;\;\;\;{\bf\Sigma}={\bf\Lambda}$$

If ${\bf A}$ is Hermitian (symmetric if real), such as a covarance matrix, then all of its eigenvalues $\lambda_i$'s are real and all eigenvectors ${\bf\phi}_i$'s are orthogonal and can be normalized (orthonormal):

$$<{\bf\phi}_i,{\bf\phi}_j>=\delta_{ij}=\left\{\begin{array}{ll} 1&i=j\\ 0&i\ne j\end{array}\right.$$

and the eigenvector matrix ${\bf\Phi}$ is unitary (orthogonal if ${\bf A}$ is real):

$${\bf\Phi}^{-1}={\bf\Phi}^*$$

and we have

$${\bf\Phi}^{-1}{\bf A}{\bf\Phi}={\bf\Phi}^*{\bf A}{\bf\Phi}={\bf\Lambda},$$

Left and right multiplying by ${\bf\Phi}$ and ${\bf\Phi}^*={\bf\Phi}^{_1}$ respectively on the two sides, we get

$${\bf A}={\bf\Phi} {\bf\Lambda}{\bf\Phi}^*=[{\bf\phi}_1,\cdo... ...} \right] =\sum_{i=1}^n \lambda_i {\bf\phi}_i {\bf\phi}_i^*$$

The generalized eigenvalue problem of two symmetric matrices ${\bf A}={\bf A}^T$ and ${\bf B}={\bf B}^T$ is to find a scalar $\lambda$ and the corresponding vector ${\bf\phi}$ for the following equation to hold:

$${\bf A}{\bf\phi}_i=\lambda_i{\bf B}{\bf\phi}_i, \;\;\;\;\;\;\;(i=1,\cdots,n)$$

or in matrix form

$${\bf A}{\bf\Phi}={\bf B}{\bf\Phi}{\bf\Lambda}$$

The eigenvalue and eigenvector matrices ${\bf\Lambda}$ and ${\bf\Phi}$ can be found in the following steps.

• Solve the eigenvalue problem of ${\bf B}$ to find its diagonal eigenvalue matrix ${\bf\Lambda}_B$ and orthogonal eigenvector matrix ${\bf\Phi}_B=({\bf\Phi}_B^T)^{-1}$ so that
  
  $${\bf B}{\bf\Phi}_B={\bf\Phi}_B{\bf\Lambda}_B, \;\;\;\;\;\;... ...}{\bf\Phi}_B={\bf\Phi}_B^T{\bf B}{\bf\Phi}_B ={\bf\Lambda}_B$$
  
  

• Left and right multiplying both sides of the second equation above by ${\bf\Lambda}^{-1/2}$ (whitening) we get
  
  $${\bf\Lambda}^{-1/2}_B ({\bf\Phi}_B^T{\bf B}{\bf\Phi}_B) {\b... ...f\Lambda}^{-1/2}_B{\bf\Lambda}_B{\bf\Lambda}^{-1/2}_B={\bf I}$$
  
  
  We define
  
  $${\bf\Phi}'_B={\bf\Phi}_B{\bf\Lambda}^{-1/2}_B$$
  
  
  and get
  
  $$({\bf\Phi}'_B)^T{\bf B}{\bf\Phi}'_B={\bf I}$$
  
  
  Note that ${\bf\Phi}_B'$ is not orthogonal
  
  $$({\bf\Phi}')^{-1}_B=({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B)^{-1}... ...hi}^T_B \ne {\bf\Lambda}^{-1/2}_B{\bf\Phi}^T_B={\bf\Phi}^T_B$$
  
  

• Apply the same transform to ${\bf A}$:
  
  $$({\bf\Phi}'_B)^T{\bf A}{\bf\Phi}'_B =({\bf\Lambda}^{-1/2}_... ...Phi}_B^T){\bf A}({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B) ={\bf A}'$$
  
  
  Note that ${\bf A}'$ is symmetric as well as ${\bf A}$:
  
  $${\bf A}'^T=({\bf\Phi}'_B^T{\bf A}{\bf\Phi}'_B)^T ={\bf\Phi}'_B^T{\bf A}{\bf\Phi}'_B={\bf A}'$$
  
  

• Diagonalize ${\bf A}'$

  As ${\bf A}'$ is symmetric,, it can be diagonalized by its orthogonal eigenvector matrix ${\bf\Phi}_A$:
  

  $${\bf\Phi}_A^T{\bf A}'{\bf\Phi}_A={\bf\Lambda}$$
  
  
  i.e.,
  

  $${\bf\Phi}_A^T ({\bf\Lambda}^{-1/2}_B{\bf\Phi}_B^T{\bf A}{\bf\Phi}_B{\bf\Lambda}^{-1/2}_B) {\bf\Phi}_A = ({\bf\Phi}_A^T {\bf\Lambda}^{-1/2}_B{\bf\Phi}_B^T){\bf A}( {\bf\Phi}_B{\bf\Lambda}^{-1/2}_B {\bf\Phi}_A)$$

  $$= {\bf\Phi}^T {\bf A}{\bf\Phi} ={\bf\Lambda}$$

  
  
  where we have defined
  
  $${\bf\Phi}={\bf\Phi}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A$$
  
  
  which is not orthogonal:
  
  $${\bf\Phi}^{-1}=( {\bf\Phi}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_... ...e {\bf\Phi}_A^T{\bf\Lambda}^{-1/2}_B{\bf\Phi}_B^T={\bf\Phi}^T$$
  
  

• This ${\bf\Phi}$ also diagonalizes ${\bf B}$:
  

  $${\bf\Phi}^T{\bf B}{\bf\Phi} = ({\bf\Phi}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A)^T {\bf B}({\bf\Phi... ...da}^{-1/2}_B ({\bf\Phi}_B^T{\bf B}{\bf\Phi}_B){\bf\Lambda}^{-1/2}_B{\bf\Phi}_A$$

  $$= {\bf\Phi}_A^T{\bf\Lambda}^{-1/2}_B{\bf\Lambda}_B{\bf\Lambda}^{-1/2}_B{\bf\Phi}_A ={\bf\Phi}_A^T{\bf\Phi}_A={\bf I}$$

  
  

• Now we have
  
  $$\left\{ \begin{array}{l} {\bf\Phi}^T{\bf A}{\bf\Phi}={\bf\Lambda}\\ {\bf\Phi}^T{\bf B}{\bf\Phi}={\bf I}\end{array}\right.$$
  
  
  Right multiplying both sides of the second equation by ${\bf\Lambda}$ and equating the left-hand side to that of the first equation, we get
  
  $${\bf A}{\bf\Phi}={\bf B}{\bf\Phi}{\bf\Lambda}$$
  
  
  i.e., ${\bf\Lambda}$ and ${\bf\Phi}$ are the eigenvalue and eigenvector matrices of the generalized eigenvalue problem. Note, however, as shown above, ${\bf\Phi}$ is not orthogonal.

The Rayleigh quotient of two symmetric matrices ${\bf A}$ and ${\bf B}$ is a function of a vector ${\bf w}$ defined as:

$$R({\bf w})=\frac{{\bf w}^T{\bf A}{\bf w}}{{\bf w}^T{\bf B}{\bf w}}$$

To find the optimal ${\bf w}$ corresponding to the extremum (maximum or minimum) of $R({\bf w})$, we find its derivative with respect to ${\bf w}$:

$$\frac{d}{d{\bf w}}R({\bf w}) =\frac{2{\bf A}{\bf w}({\bf w}^... ...\bf w}({\bf w}^T{\bf A}{\bf w})} {({\bf w}^T{\bf B}{\bf w})^2}$$

Setting it to zero we get

$${\bf A}{\bf w}({\bf w}^T{\bf B}{\bf w})={\bf B}{\bf w}({\bf... ...bf B}{\bf w} =R({\bf w}){\bf B}{\bf w}=\lambda {\bf B}{\bf w}$$

The second equation can be recognized as a generalized eigenvalue problem with $\lambda=R({\bf w})$ being the eigenvalue and and ${\bf w}$ the corresponding eigenvector. Solving this we get the vector ${\bf w}={\bf\phi}$ corresponding to the maximum/minimum eigenvalue $\lambda=R({\bf w})$, which maximizes/minimizes the Rayleigh quotient.