# Diagonalization

### Big Idea
An $n \times n$ matrix $A$ is diagonalizable if it possesses $n$ linearly independent eigenvectors, which form a basis for $\mathbb{R}^n$ (or $\mathbb{C}^n$). If $A$ is diagonalizable, it can be decomposed as $A=PDP^{-1}$. A key class of matrices, real symmetric matrices, is always diagonalizable, always has real eigenvalues, and its eigenvectors corresponding to distinct eigenvalues are always orthogonal.

## Eigenvalues and Eigenvectors
:::info
**Definition**
An *eigenvalue* $\lambda$ of a matrix $A$ is a number that satisfies the equation $A\mathbf{v} = \lambda \mathbf{v}$ for some nonzero vector $\mathbf{v}$.

* **Eigenvalue $\lambda$:** The scalar that scales the eigenvector during the transformation. Eigenvalues of a real matrix may be real or complex.
* **Eigenvector $\mathbf{v}$:** The nonzero vector whose direction is unchanged by the transformation $A$.

The set of all eigenvectors for a given eigenvalue $\lambda$, along with the zero vector, forms the eigenspace for $\lambda$: $$E_{\lambda} = \mathcal{N}(A - \lambda I)$$
:::

### Characteristic Polynomial
:::info
**Definition**
The characteristic polynomial of $A$ is defined as $C_A(x) = \det(A - xI)$.
:::

:::danger
**Proposition**
* The eigenvalues of $A$ are the *roots* of the characteristic polynomial.
* The degree of $C_A(x)$ is $n$, and $A$ and $A^T$ always have the same characteristic polynomial (and thus the same eigenvalues).
* If $A$ has $n$ distinct eigenvalues, the corresponding eigenvectors are linearly independent and form an eigenbasis for $\mathbb{R}^n$ (or $\mathbb{C}^n$).
:::

::: info
**Definition (Multiplicity)**
The characteristic polynomial factors into $$C_A(x) = \pm (x - \lambda_1)^{m_1} \cdots (x - \lambda_k)^{m_k}$$ where $\lambda_1, \dots, \lambda_k$ are the distinct eigenvalues.

* The *algebraic multiplicity* $m_i$ of $\lambda_i$ is the exponent of the factor $(x - \lambda_i)$.
* The *geometric multiplicity* $d_i$ of $\lambda_i$ is the dimension of the eigenspace: $d_i = \dim E_{\lambda_i}$.
:::

:::warning
**Examples**
1. $A = \begin{bmatrix} 3 & 1\\ 0 & 3 \end{bmatrix}$
* The characteristic polynomial is $C_A(x) = (x - 3)^2$.
* The eigenvalue $\lambda_1=3$ has algebraic multiplicity $m_1=2$, but its eigenspace $E_3 = \text{span}\{\begin{bmatrix}1\\0\end{bmatrix}\}$ has geometric multiplicity $d_1=1$.
2. $A = \begin{bmatrix} 1 & 0\\ 0 & 1 \end{bmatrix}$
* The characteristic polynomial is $C_A(x) = (x - 1)^2$.
* The eigenvalue $\lambda_1=1$ has both algebraic and geometric multiplicity $m_1=d_1=2$.
:::

### Computing Eigenvalues
Eigenvalues are found by setting the determinant of the characteristic matrix to zero: $\det(A - \lambda I) = 0$.

1. Calculate $C_A(x) = \det(A - xI)$.
2. Find the roots of $C_A(x)$ (the eigenvalues, $\lambda$).
3. Find a basis for $\mathcal{N}(A - \lambda_i I)$ (the eigenvectors, $\mathbf{v}$).

:::warning
**Example** $A = \begin{bmatrix} 2 & 0 & 0\\ 1 & 2 & -1\\ 1 & 3 & -2 \end{bmatrix}$
* The characteristic polynomial is
$$
C_A(x) = \det(A - xI)
= \begin{vmatrix}
2-x & 0 & 0\\
1 & 2-x & -1\\
1 & 3 & -2-x
\end{vmatrix}
= (x-2)(x-1)(x+1)
$$
* The distinct eigenvalues are $\lambda_1=2$, $\lambda_2=1$, and $\lambda_3=-1$.
* $\lambda_1 = 2$: $$(A - 2I)\mathbf{x} = 0 \Rightarrow \mathbf{x} = t\begin{bmatrix}1\\1\\1\end{bmatrix}$$
* $\lambda_2 = 1$: $$(A - I)\mathbf{x} = 0 \Rightarrow \mathbf{x} = t\begin{bmatrix}0\\1\\1\end{bmatrix}$$
* $\lambda_3 = -1$: $$(A + I)\mathbf{x} = 0 \Rightarrow \mathbf{x} = t\begin{bmatrix}0\\1\\3\end{bmatrix}$$
* Thus, eigenvectors corresponding to distinct eigenvalues are *linearly independent*.
:::

#### Remark
While using the characteristic polynomial $C_A(x) = \det(A - xI)$ is the theoretical method for finding eigenvalues, it is impractical for large matrices. This method works for small matrices (e.g., $2 \times 2$ or $3 \times 3$) but becomes computationally impossible for larger ones. For instance, if $A$ is $5 \times 5$, finding the eigenvalues requires solving a polynomial equation of degree 5, for which no general analytical formula exists for the roots.

:::success
**Exercise**
1. Let $\mathbf{u} \in \mathbb{R}^n$ be a nonzero vector and $H = I - \dfrac{2}{\|\mathbf{u}\|^2}\mathbf{u}\mathbf{u}^{T}$ be the corresponding elementary reflector.
* a. $\lambda = -1$ is an eigenvalue of $H$ with multiplicity $1$.
* b. The characteristic polynomial of $H$ is $(x - 1)^{n-1}(x + 1)$.
2. Let $P$ be the orthogonal projection matrix onto a subspace $U \subset \mathbb{R}^n$ with $\dim(U) = m$.
* a. Then $\lambda = 1$ is an eigenvalue for $P$ with multiplicity $m$.
* b. Then $\lambda = 0$ is an eigenvalue for $P$ with multiplicity $n - m$.
* c. All the eigenvalues of $P$ are either $1$ or $0$.
3. Let $(\lambda_1, \mathbf{v})$ be an eigenvalue/eigenvector pair for a matrix $A$, i.e., $A\mathbf{v} = \lambda_1 \mathbf{v}$.
* a. For another matrix $B$, assume that $B\mathbf{v} = \lambda_2 \mathbf{v}$. Find an eigenvalue/eigenvector pair for $A + B$.
* b. Under the same condition in part a, find an eigenvalue/eigenvector pair for $AB$.
* c. Now suppose we only know $AB = BA$ for a matrix $B$. Show that $B\mathbf{v}$ is also an eigenvector of $A$.
:::

## Diagonalization
:::info
**Definition** An $n \times n$ matrix $A$ is *diagonalizable* if it is similar to a diagonal matrix $D$: $$P^{-1} A P = D$$ for some invertible matrix $P$.
:::

:::danger
**Theorem**
* If $A$ is diagonalizable with $A = PDP^{-1}$, the diagonal entries of $D$ are the eigenvalues of $A$, and the columns of $P$ are the corresponding *eigenvectors*.
* A matrix $A$ is diagonalizable if and only if for every eigenvalue $\lambda$, the algebraic multiplicity equals the geometric multiplicity ($m_i = d_i$).
* If $A$ has distinct eigenvalues, it is automatically diagonalizable.
:::

:::warning
**Examples**
1. $A = \begin{bmatrix} 2 & 0 & 0\\ 1 & 2 & -1\\ 1 & 3 & -2 \end{bmatrix}$ is diagonalizable because all three eigenvalues are distinct, meaning $m_i=d_i=1$ for all $i$.
* The diagonalization is $A = PDP^{-1}$ where: $$P = \begin{bmatrix} 1 & 0 & 0\\ 1 & 1 & 1\\ 1 & 1 & 3 \end{bmatrix}, \quad D = \begin{bmatrix} 2 & 0 & 0\\ 0 & 1 & 0\\ 0 & 0 & -1 \end{bmatrix}$$
2. $A = \begin{bmatrix} 3 & 1\\ 0 & 3 \end{bmatrix}$ is not diagonalizable because its single eigenvalue $\lambda=3$ has algebraic multiplicity 2 but geometric multiplicity 1 ($m_1 \neq d_1$).
:::

### Applications
If $A = PDP^{-1}$, the decomposition allows for simple calculations of matrix powers, determinants, and the trace:

1. $\det(A) = \det(D) = \lambda_1 \lambda_2 \cdots \lambda_n$ (The determinant is the product of the eigenvalues).
2. $\operatorname{tr}(A) = \operatorname{tr}(D) = \lambda_1 + \lambda_2 + \cdots + \lambda_n$ (The trace is the sum of the eigenvalues).
3. $A^k = P D^k P^{-1}$ for any integer $k \geq 0$ (and $k<0$ if $A$ is invertible).

:::success
**Exercise**

4. Let $\mathbf{v}_1, \mathbf{v}_2 \in \mathbb{R}^2$ be linearly independent vectors. Let $\lambda_1, \lambda_2$ be real numbers. Then there exists a *unique* $2 \times 2$ matrix $A$ with eigenvalues $\lambda_1, \lambda_2$ and corresponding eigenvectors $\mathbf{v}_1, \mathbf{v}_2$.
5. Let $\lambda$ be a (nonzero) eigenvalue of an invertible matrix $A$. Identify all *True* statements:
* a. $\lambda^{-1}$ is an eigenvalue of $A^{-1}$
* b. $\lambda$ is an eigenvalue of $A^{T}$
* c. $\lambda^{2}$ is an eigenvalue of $A A^{T}$
* d. $\lambda$ is an eigenvalue of $P A P^{-1}$ for any invertible matrix $P$
* e. $\lambda \neq 0$
:::

## Spectral Theorem
The *Spectral Theorem* specializes the concept of diagonalization for symmetric matrices, which are common in physical systems.

:::danger
**Theorem** Let $A$ be a symmetric matrix ($A=A^T$).

* All eigenvalues of $A$ are *real numbers*.
* Eigenvectors corresponding to *distinct eigenvalues are orthogonal*.
* $A$ is *orthogonally diagonalizable*: $A = PDP^T$, where $P$ is an orthogonal matrix ($P^{-1}=P^T$) composed of orthonormal eigenvectors.
:::

:::success
**Exercise**

6. Consider the following types of matrices (all assumed to be square):
A. Matrices with a basis of eigenvectors
B. Matrices with distinct eigenvalues
C. Matrices with repeated eigenvalues
D. Hermitian matrices
E. Non-zero orthogonal projection matrices
F. Matrices of the form $\begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix}$ with $a \neq 0$.
* a. Which types are always diagonalizable
* b. Which types are sometimes, but not always diagonalizable?
* c. Which types always have an orthonormal basis of eigenvectors?
7. Suppose $A$ is a symmetric $3 \times 3$ matrix with distinct eigenvalues $\lambda_1, \lambda_2, \lambda_3$ and eigenvectors $$
\mathbf{v}_1 = \begin{bmatrix} 1 \\ 1 \\ 1 \end{bmatrix} \hspace{10mm} \mathbf{v}_2 = \begin{bmatrix} 1 \\ 0 \\ -1 \end{bmatrix}
$$ Find an eigenvector $\mathbf{v}_3$ for eigenvalue $\lambda_3$.
:::