Eigenvalues and matrix diagonalization

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. In other words, the linear transformation of vector ${\bf\phi}$ by ${\bf A}$ only has the effect of scaling (by a factor of $\lambda$) the vector in the same direction (1-D space).

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 constant $c$. Typically for the uniqueness of ${\bf\phi}$, we keep it normalized so that $\vert\vert{\bf\phi}\vert\vert=1$.

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

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

For this homogeneous equation system to have non-zero solutions 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$$

This is the characteristic polynomial equation of matrix ${\bf A}$. 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$ eigen-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]$$

If ${\bf A}$ is positive definite, i.e., ${\bf x}^T{\bf A}{\bf x}>0$ for any vector ${\bf x}$, then all eigenvalues are positive.

Defining the eigenvalue matrix (a diagonal matrix) and eigenvector matrix as

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

we can write the eigen-equations in more compact forms:

$${\bf A}{\bf\Phi}={\bf\Phi}{\bf\Lambda}, \;\;\;\;\;\;\;\;\;... ...r}\;\;\;\;\;\;\; {\bf\Phi}^{-1}{\bf A}{\bf\Phi}={\bf\Lambda}$$

We see that ${\bf A}$ can be diagonalized by its eigenvector matrix ${\bf\Phi}=[{\bf\phi}_1,\cdots,{\bf\phi}_n]$ composed of all its eigenvectors to a diagonal matrix composed of its eigenvalues ${\bf\Lambda}=diag[\lambda_1,\cdots,\lambda_n]$.

We further have:

$${\bf A}^2=({\bf\Phi}{\bf\Lambda}{\bf\Phi}^{-1})({\bf\Phi}{\... ...Lambda}{\bf\Phi}^{-1} ={\bf\Phi}{\bf\Lambda}^2{\bf\Phi}^{-1}$$

and in general

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

Assuming ${\bf A}{\bf\phi}=\lambda{\bf\phi}$, we have the following:

• ${\bf A}^T$ has the same eigenvalues and eigenvectors as ${\bf A}$.

  Proof: As a matrix ${\bf A}$ and its transpose ${\bf A}^T$ have the same determinant, they have the same characteristic polynomial:
  

  $$\big\vert{\bf A}-\lambda{\bf I}\big\vert =\big\vert({\bf A... ...f I})^T\big\vert =\big\vert{\bf A}^T-\lambda{\bf I}\big\vert$$
  
  
  therefore they have the same eigenvalues and eigenvectors.

• The eigenvalues and eigenvectors of ${\bf A}^*$ are the complex conjugate of the eigenvalues and eigenvectors as ${\bf A}$.

• ${\bf A}^T{\bf A}$ has the same eigenvectors as ${\bf A}$, but its eigenvalues are $\lambda^2$.

  Proof:
  

  $${\bf A}^T{\bf A}{\bf\phi}={\bf A}^T\lambda{\bf\phi}=\lambda^2{\bf\phi}$$
  
  

• ${\bf A}^k$ has the same eigenvectors as ${\bf A}$, but its eigenvalues are $\{\lambda_1^k,\cdots,\lambda_n^k \}$, where $k$ is a positive integer.

  Proof:
  

  $${\bf A}^2{\bf\phi}={\bf A}{\bf A}{\bf\phi}={\bf A}\lambda{\bf\phi} =\lambda^2{\bf\phi}$$
  
  
  This result can be generalized to
  
  $${\bf A}^k{\bf\phi}=\lambda^k{\bf\phi}$$
  
  

• In particular when $k=-1$, i.e., the eigenvalues of ${\bf A}^{-1}$ are $\{1/\lambda_1,\cdots,1/\lambda_n \}$.

  Proof: Left multiplying ${\bf A}^{-1}$ on both sides of ${\bf A}{\bf\phi}=\lambda{\bf\phi}$ we get
  

  $${\bf A}^{-1}{\bf A}{\bf\phi}={\bf I}{\bf\phi} ={\bf\phi}=\lambda{\bf A}^{-1}{\bf\phi}$$
  
  
  Dividing both sides by $\lambda$ we get
  
  $${\bf A}^{-1}{\bf\phi}=\frac{1}{\lambda}{\bf\phi}$$
  
  

• The eigenvalues of a matrix are invariant under any unitary transform ${\bf B}={\bf R}^*{\bf A}{\bf R}$, where ${\bf R}$ is unitary, i.e., ${\bf R}^{-1}={\bf R}^*$, or ${\bf R}^*{\bf R}={\bf R}{\bf R}^*={\bf I}$

  Proof:

  Let ${\bf\Lambda}=diag(\lambda_1,\cdots,\lambda_n)$ and ${\bf\Phi}=[{\bf\phi}_1,\cdots,{\bf\phi}_n]$ be 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}=[{\bf\psi}_1,\cdots,{\bf\psi}_n]$ be 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}$$
  
  
  We see that ${\bf A}$ and ${\bf B}={\bf R}^*{\bf A}{\bf R}$ have the same eigenvalues ${\bf\Sigma}={\bf\Lambda}$ and their eigenvector matrices are related by ${\bf\Phi}={\bf R}{\bf\Psi}$ or ${\bf\Psi}={\bf R}^*{\bf\Phi}$.

• Given all eigenvalues $\lambda_1,\cdots,\lambda_n$ of a matrix ${\bf A}$, its trace and determinant can be obtained as
  
  $$tr({\bf A}) =\sum_{k=1}^n \lambda_k, \;\;\;\;\;\;\;\;\;\;\;\; det({\bf A}) =\prod_{k=1}^n \lambda_k$$
  
  

• The spectrum of an $n \times n$ square matrix ${\bf A}$ is 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)$$
  
  
  where $\vert z\vert=\sqrt{x^2+y^2}$ is the modulus of a complex number $z=x+jy$. 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=\vert\lambda_{max}\vert$. As the eigenvalues of ${\bf A}^{-1}$ are $\{1/\lambda_{max},\cdots,1/\lambda_{min}\}$, $\rho({\bf A}^{-1})=1/\vert\lambda_{min}$.

• If ${\bf A}$ is Hermitian (symmetric if real) (e.g., the covariance matrix of a random vector)), then
  1. all of its eigenvalues are real, and
  2. all of its eigenvectors are orthogonal.

  Proof:

  Let $\lambda$ and ${\bf\phi}$ be an eigenvalue of a Hermitian matrix ${\bf A}={\bf A}^*$ and the corresponding eigenvector satisfying ${\bf A}{\bf\phi}=\lambda{\bf\phi}$, then we have
  

  $$({\bf A}{\bf\phi})^*{\bf\phi}=(\lambda{\bf\phi})^*{\bf\phi}... ...i}^*{\bf\phi} =\bar{\lambda}\;\vert\vert{\bf\phi}\vert\vert^2$$
  
  
  On the other hand, we also have
  
  $$({\bf A}{\bf\phi})^*{\bf\phi}={\bf\phi}^*{\bf A}^*{\bf\phi}... ...^*\lambda{\bf\phi} =\lambda\;\vert\vert{\bf\phi}\vert\vert^2$$
  
  
  i.e., $\bar\lambda=\lambda$ is real.

  To show the eigenvectors are orthogonal, consider
  

  $${\bf\phi}_i^*{\bf A}{\bf\phi}_j={\bf\phi}_i^*\lambda_j{\bf\phi}_j =\lambda_j{\bf\phi}_i^*{\bf\phi}_j$$
  
  
  similarly, we also have
  
  $$({\bf\phi}_j^*{\bf A}{\bf\phi}_i)^*=(\lambda_i{\bf\phi}_j^*... ...a_i{\bf\phi}_i^*{\bf\phi}_j=\lambda_i{\bf\phi}_i^*{\bf\phi}_j$$
  
  
  But the left-hand sides of the two equations above are the same:
  
  $$({\bf\phi}_j^*{\bf A}{\bf\phi}_i)^*={\bf\phi}_i^*{\bf A}^*{\bf\phi}_j ={\bf\phi}_i^*{\bf A}{\bf\phi}_j$$
  
  
  therefoe the difference of their right-hand sides must be zero:
  
  $$(\lambda_i-\lambda_j)\;{\bf\phi}_i^*{\bf\phi}_j=0$$
  
  
  If $\lambda_i\ne\lambda_j$, we get ${\bf\phi}_i^*{\bf\phi}_j=0$, i.e., the eigenvectors corresponding to different eigenvalues are orthogonal.

  Q.E.D.

  When all eigenvectors are normalized ${\bf\phi}_i^*{\bf\phi}_i=\vert\vert{\bf\phi}_i\vert\vert^2=1$, they become orthonormal
  

  $$\langle{\bf\phi}_i,{\bf\phi}_j\rangle={\bf\phi}_i^*{\bf\phi... ...j}=\left\{\begin{array}{ll}1&i=j 0&i\ne j\end{array}\right.$$
  
  
  i.e., the eigenvector matrix ${\bf\Phi}=[{\bf\phi}_1,\cdots,{\bf\phi}_n]^T$ is unitary (orthogonal if ${\bf A}$ is real):
  
  $${\bf\Phi}^{-1}={\bf\Phi}^*\;\;\;\;\mbox{i.e.}\;\;\;\; {\bf\Phi}^*{\bf\Phi}={\bf I}$$
  
  
  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^*$$
  
  
  We see that ${\bf A}$ can be written as a linear combination of $n$ matrices ${\bf\phi}_i{\bf\phi}^*_i$ weighted by $\lambda_i$ ($n=1,\cdots,n$).