---
title: Linear Algebra Note 6
tags: Linear Algebra, 線性代數, 魏群樹, 大學, 國立陽明交通大學, 筆記
---

# Linear Algebra Note 6

## Eigenvectors & Eigenvalues (2021.12.08 ~ 2021.12.17)

### Eigenvalue Decomposition (EVD) or Matrix Diagonalization

- Theorem
Let $A$ be a $n \times n$ matrix.
$A$ can be decomposed into $A=S \Lambda S^{-1}$ or $\Lambda = S^{-1}AS$ (diagonalization)
where $\Lambda = \left[\begin{array}{c c c c}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n \\
\end{array}\right]$ with $\lambda_i$ being eigenvalue of $A$ and $S = \left[\begin{array}{c c c c}
\vec{x_1} & \vec{x_2} & \cdots & \vec{x_n} \\
\end{array}\right]$ consists of eigenvectors $\vec{x_i}$ corresponding to $\lambda_i$ if and only if $A$ has $n$ linearly independent eigenvectors
- Proof
$\begin{split}S &= \left[\begin{array}{c c c c}
\vec{x_1} & \vec{x_2} & \cdots & \vec{x_n} \\
\end{array}\right] \\
AS &= \left[\begin{array}{c c c c}
A\vec{x_1} & A\vec{x_2} & \cdots & A\vec{x_n} \\
\end{array}\right] = \left[\begin{array}{c c c c}
\lambda_1\vec{x_1} & \lambda_2\vec{x_2} & \cdots & \lambda_n\vec{x_n} \\
\end{array}\right] \\
&= \left[\begin{array}{c c c c}
\vec{x_1} & \vec{x_2} & \cdots & \vec{x_n} \\
\end{array}\right]\left[\begin{array}{c c c c}
\lambda_1 & 0 & \cdots & 0 \\
0 & \lambda_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n \\
\end{array}\right] = S\Lambda\end{split}$
$S$ is invertible if and only if $\vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_n}$ are linearly independent
$\implies A = S \Lambda S^{-1}$ if and only if $\vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_n}$ are linearly independent
The matrix $A$ is said to be diagonalizable

- Theorem
If $A$ is diagonalizable, $A^k = S \Lambda^k S^{-1}$ where $\Lambda^k = \left[\begin{array}{c c c c}
\lambda_1^k & 0 & \cdots & 0 \\
0 & \lambda_2^k & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n^k \\
\end{array}\right]$
- Proof
$A = S \Lambda S^{-1} \\
A^2 = (S \Lambda S^{-1})(S \Lambda S^{-1}) = S \Lambda^2 S^{-1} \text{ where } \Lambda^2 = \left[\begin{array}{c c c c}
\lambda_1^2 & 0 & \cdots & 0 \\
0 & \lambda_2^2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & \cdots & \lambda_n^2 \\
\end{array}\right] \\
\therefore A^k = S \Lambda^k S^{-1}$
- Example
$A = \left[\begin{array}{c c}
0.8 & 0.3 \\
0.2 & 0.7 \\
\end{array}\right],\ \Lambda = \left[\begin{array}{c c}
\lambda_1 & 0 \\
0 & \lambda_2 \\
\end{array}\right] = \left[\begin{array}{c c}
1 & 0 \\
0 & 0.5 \\
\end{array}\right] \\
S = \left[\begin{array}{c c}
\vec{x_1} & \vec{x_2} \\
\end{array}\right] = \left[\begin{array}{c c}
0.6 & 1 \\
0.4 & -1 \\
\end{array}\right],\ S^{-1} = \left[\begin{array}{c c}
1 & 1 \\
0.4 & -0.6 \\
\end{array}\right] \\
\text{check } A = S \Lambda S^{-1} = \left[\begin{array}{c c}
0.6 & 1 \\
0.4 & -1 \\
\end{array}\right]\left[\begin{array}{c c}
1 & 0 \\
0 & 0.5 \\
\end{array}\right]\left[\begin{array}{c c}
1 & 1 \\
0.4 & -0.6 \\
\end{array}\right] \\
\begin{split}A^{\infty} &= S \Lambda^{\infty} S^{-1} \\
&= \left[\begin{array}{c c}
0.6 & 1 \\
0.4 & -1 \\
\end{array}\right]\left[\begin{array}{c c}
1^{\infty} & 0 \\
0 & 0.5^{\infty} \\
\end{array}\right]\left[\begin{array}{c c}
1 & 1 \\
0.4 & -0.6 \\
\end{array}\right] \\
&= \left[\begin{array}{c c}
0.6 & 1 \\
0.4 & -1 \\
\end{array}\right]\left[\begin{array}{c c}
1 & 0 \\
0 & 0 \\
\end{array}\right]\left[\begin{array}{c c}
1 & 1 \\
0.4 & -0.6 \\
\end{array}\right] \\
&= \left[\begin{array}{c c}
0.6 & 0 \\
0.4 & 0 \\
\end{array}\right]\left[\begin{array}{c c}
1 & 1 \\
0.4 & -0.6 \\
\end{array}\right]
= \left[\begin{array}{c c}
0.6 & 0.6 \\
0.4 & 0.4 \\
\end{array}\right]\end{split}$

- Theorem
Let $\lambda_1,\ \lambda_2,\ \cdots,\ \lambda_n$ be $A$'s eigenvalues and $\vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_n}$ be the corresponding eigenvectors, respectively.
If all $\lambda_i$ are distinct then $\{ \vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_n} \}$ are linearly independent, i.e. $A$ is diagonalizable
- Proof (using mathematical induction)
$n = 1,\ \{ \vec{x_1} \}$ is linearly independent
Assume this is true for $n=k$
$i.e.\ \lambda_1,\ \lambda_2,\ \cdots,\ \lambda_k$ are distinct and $\{ \vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_k} \}$ is linearly independent
consider $n = k+1$ , let $\lambda_1,\ \lambda_2,\ \cdots,\ \lambda_k,\ \lambda_{k+1}$ are all distinct if $\{ \vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_k},\ \vec{x_{k+1}} \}$ is not linearly independent
$i.e.\ c_1\vec{x_1} + c_2\vec{x_2} + \cdots + c_k\vec{x_k} = \vec{x_{k+1}} \text{ or } c_1\vec{x_1} + c_2\vec{x_2} + \cdots + c_k\vec{x_k} - \vec{x_{k+1}} = 0$
$(\ A\vec{x} = \lambda \vec{x} \implies (A-\lambda I)\vec{x} = 0\ ) \\
\begin{split}&(A-\lambda_{k+1}I)\vec{x}_{k+1} = 0 \\
\implies &(A-\lambda_{k+1}I)(c_1\vec{x_1} + c_2\vec{x_2} + \cdots + c_k\vec{x_k}) = 0 \\
\implies &(Ac_1\vec{x_1} + Ac_2\vec{x_2} + \cdots + Ac_k\vec{x_k}) - (\lambda_{k+1}c_1\vec{x_1} + \lambda_{k+1}c_2\vec{x_2} + \cdots + \lambda_{k+1}c_k\vec{x_k}) = 0 \\
\because\ &A\vec{x_1} = \lambda_1\vec{x_1},\ A\vec{x_2} = \lambda_2\vec{x_2},\ \cdots,\ A\vec{x_k} = \lambda_k\vec{x_k} \\
\implies &(c_1\lambda_1\vec{x_1} + c_2\lambda_2\vec{x_2} + \cdots + c_k\lambda_k\vec{x_k}) - (c_1\lambda_{k+1}\vec{x_1} + c_2\lambda_{k+1}\vec{x_2} + \cdots + c_k\lambda_{k+1}\vec{x_k}) = 0 \\
\implies &\sum\limits_{i = 1}^k{c_i\lambda_i\vec{x_i}} - \sum\limits_{i = 1}^k{c_i\lambda_{k+1}\vec{x_i}} = 0 \\
\implies &\sum\limits_{i = 1}^k{c_i (\lambda_i-\lambda_{k+1}) \vec{x_i}} = 0 \\
\implies &\lambda_i - \lambda_{k+1} = 0 \implies \lambda_i = \lambda_{k+1} \text{ (NOT all distinct)(contradiction) } \\
\therefore\ &\{ \vec{x_1},\ \vec{x_2},\ \cdots,\ \vec{x_k},\ \vec{x_{k+1}} \} \text{ is linearly independent}\end{split}$

- Define(GM): The geometric multiplicity (GM) of an eigenvalue $\lambda$ of $A$ is the dimension of the eigenspace $E_A(\lambda)\ i.e.\ N(A-\lambda I)$
- Define(AM): The algebraic multiplicity (AM) of an eigenvalue $\lambda$ of $A$ is the number of times $\lambda$ appears as a root of $\begin{vmatrix}
A-\lambda I
\end{vmatrix}=0$
- Example
$A = \left[\begin{array}{c c}
0 & 1 \\
0 & 0 \\
\end{array}\right] \\
\begin{vmatrix}
A-\lambda I
\end{vmatrix} = \lambda^2-0=0,\ \lambda^2=0 \implies AM=2 \\
E_A(\lambda=0) = N(A-\lambda I) = N(A) = \{ c\left[\begin{array}{c}
1 \\
0 \\
\end{array}\right] \} \\
\implies GM = dim(E_A) = 1$
- Theorem
Let $A$ be $n \times n$ matrix with eigenvalues $\lambda_1,\ \lambda_2,\ \cdots,\ \lambda_k$
$A$ is diagonalizable if and only if
1. $\sum\limits_{i=1}^k{m_i}=n,\ m_i=\text{the AM of }\lambda_i$
2. $m_i = dim(E_A(\lambda_i)) = GM(i)\ for\ i \in \{ 1,\ 2,\ \cdots,\ k\}$

- Example
$A = \left[\begin{array}{c c c}
4 & 0 & 1 \\
2 & 3 & 2 \\
1 & 0 & 4 \\
\end{array}\right] \\
\begin{vmatrix}
A-\lambda I
\end{vmatrix} = \begin{vmatrix}
\left[\begin{array}{c c c}
4-\lambda & 0 & 1 \\
2 & 3-\lambda & 2 \\
1 & 0 & 4-\lambda \\
\end{array}\right]
\end{vmatrix} = -(\lambda-5)(\lambda-3)^2 \\
\begin{split}GM(1) = E_A(\lambda_1=5) &= N(A-5I) \\
&= N(\left[\begin{array}{c c c}
-1 & 0 & 1 \\
2 & -2 & 2 \\
1 & 0 & -1 \\
\end{array}\right]) = \{ c\left[\begin{array}{c}
1 \\
2 \\
1 \\
\end{array}\right]\}\end{split} \\
\begin{split}GM(2) = E_A(\lambda_1=3) &= N(A-3I) \\
&= N(\left[\begin{array}{c c c}
1 & 0 & 1 \\
2 & 0 & 2 \\
1 & 0 & 1 \\
\end{array}\right]) = \{ c_1\left[\begin{array}{c}
-1 \\
0 \\
1 \\
\end{array}\right] + c_2\left[\begin{array}{c}
0 \\
1 \\
0 \\
\end{array}\right]\}\end{split} \\
\left\{\begin{array}{c}
\lambda_1 = 5,\ AM(1)=1,\ GM(1)=1 \\
\lambda_2 = 3,\ AM(2)=2,\ GM(2)=2 \\
\end{array}\right. \\
\therefore A \text{ is diagonalizable},\ i.e. \{ \left[\begin{array}{c}
1 \\
2 \\
1 \\
\end{array}\right],\ \left[\begin{array}{c}
1 \\
0 \\
-1 \\
\end{array}\right],\ \left[\begin{array}{c}
0 \\
1 \\
0 \\
\end{array}\right]\} \text{ are linearly independent}$

### Positive Definite Matrices & Cholesky Factorization

- Define (Positive definite): A **symmetric** matrix $A$ is positive definite if $\vec{x}^TA\vec{x} > 0\ \forall\ \vec{x} \not= \vec{0}$

- Theorem
$A$ is positive definite. This is equivalent to the following:
1. All $n$ pivots are positive
2. All $n$ upper left determinants are positive
3. All $n$ eigenvalues are positive
4. $\vec{x}^TA\vec{x} > 0,\ \forall \vec{x} \not= 0$
5. $A = R^TR$ where $R$ has independent columns (Cholesky Factorization)
- Proof 1 and 4
For a symmetric $A$, $A=LDL^T$ where
$L = \left[\begin{array}{c c c c}
1 & 0 & \cdots & 0 \\
& 1 & \cdots & 0 \\
& & \ddots & \vdots \\
& & & 1 \\
\end{array}\right] = \left[\begin{array}{c c c c}
\vec{a_1} & \vec{a_2} & \cdots & \vec{a_n} \\
\end{array}\right] \\
D = \left[\begin{array}{c c c c}
d_1 & 0 & \cdots & 0 \\
0 & d_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & d_n \\
\end{array}\right], \text{ where } d_1,\ d_2,\ \cdots,\ d_n \text{ are pivots} \\
\begin{split}\vec{x}^TA\vec{x} &= \vec{x}^TLDL^T\vec{x} \\
&= \vec{x}^T\left[\begin{array}{c c c c}
\vec{a_1} & \vec{a_2} & \cdots & \vec{a_n} \\
\end{array}\right]\left[\begin{array}{c c c c}
d_1 & 0 & \cdots & 0 \\
0 & d_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & d_n \\
\end{array}\right]\left[\begin{array}{c}
\vec{a_1}^T \\
\vec{a_2}^T \\
\vdots \\
\vec{a_n}^T \\
\end{array}\right]\vec{x} \\
&= \sum\limits_{i=1}^n{d_i(\vec{x}^T\vec{a_i}\vec{a_i}^T\vec{x})} = \sum\limits_{i=1}^n{d_i(\vec{a_i}^T\vec{x})^2}\end{split} \\
\text{If } d_i \ge 0 \text{ for all } i=1,\ 2,\ \cdots,\ n \implies \vec{x}^TA\vec{x} \ge 0 \\
\text{This is 0 only when} \\
\text{1. } \vec{x} = \vec{0} \\
\text{2. } \exists\ \vec{x}\ s.t. L^T\vec{x} = \vec{0}\ i.e. \exists\ \vec{x} \in N(L^T) \\
\text{However, } N(L^T) = \{ 0 \} \text{ since } L^T \text{ has full rank}$
- Proof 5
$A = LDL^T$ and $D = \left[\begin{array}{c c c c}
d_1 & 0 & \cdots & 0 \\
0 & d_2 & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & d_n \\
\end{array}\right]$ where $d_i > 0$
Split $D$ into $D'D'^T = \left[\begin{array}{c c c c}
\sqrt{d_1} & 0 & \cdots & 0 \\
0 & \sqrt{d_2} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \sqrt{d_n} \\
\end{array}\right]\left[\begin{array}{c c c c}
\sqrt{d_1} & 0 & \cdots & 0 \\
0 & \sqrt{d_2} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \sqrt{d_n} \\
\end{array}\right]$
$\therefore A = LD'D'^TL^T = R^TR \\
\text{ where } R = D'^TL^T = \left[\begin{array}{c c c c}
\sqrt{d_1} & 0 & \cdots & 0 \\
0 & \sqrt{d_2} & \cdots & 0 \\
\vdots & \vdots & \ddots & \vdots \\
0 & 0 & 0 & \sqrt{d_n} \\
\end{array}\right]\left[\begin{array}{c c c c}
1 & & & \\
0 & 1 & & \\
\vdots & \vdots & \ddots & \\
0 & 0 & 0 & 1 \\
\end{array}\right] \text{ has independent columns} \\
\implies A=R^TR \text{ where } R \text{ has independent columns}$
- Example
$A = \left[\begin{array}{c c}
1 & -2 \\
-2 & 6 \\
\end{array}\right]$, we have shown that 1 and 4
$\text{3. } \begin{vmatrix}
A-\lambda I
\end{vmatrix} = \begin{vmatrix}
\left[\begin{array}{c c}
1-\lambda & -2 \\
-2 & 6-\lambda \\
\end{array}\right]
\end{vmatrix} = \lambda^2-7\lambda+2 = 0 \implies \lambda = {7 \pm \sqrt{41} \over 2} > 0 \\
\begin{split} \text{5. } A = LDL^T &= \left[\begin{array}{c c}
1 & 0 \\
-2 & 1 \\
\end{array}\right]\left[\begin{array}{c c}
1 & 0 \\
0 & 2 \\
\end{array}\right]\left[\begin{array}{c c}
1 & -2 \\
0 & 1 \\
\end{array}\right] \\
&= R^TR \text{ where } R = \left[\begin{array}{c c}
1 & 0 \\
0 & \sqrt{2} \\
\end{array}\right]\left[\begin{array}{c c}
1 & -2 \\
0 & 1 \\
\end{array}\right] = \left[\begin{array}{c c}
1 & -2 \\
0 & \sqrt{2} \\
\end{array}\right]\end{split}$

> $\forall\ \vec{x} \not= 0$ , A symmetric $A$ is
> 1. **Positive definite** if all $\lambda_i > 0\ (\vec{x}^TA\vec{x} > 0)$
> 2. **Positive semidefinite** if all $\lambda_i \ge 0\ (\vec{x}^TA\vec{x} \ge 0)$
> 3. **Negative definite** if all $\lambda_i < 0\ (\vec{x}^TA\vec{x} < 0)$
> 4. **Negative semidefinite** if all $\lambda_i \le 0\ (\vec{x}^TA\vec{x} \le 0)$
> 5. **Indefinite**, otherwise

- Example
$A = \left[\begin{array}{c c}
1 & 2 \\
2 & 4 \\
\end{array}\right],\ \lambda_1 = 0,\ \lambda_2 = 5,\ \vec{x_1} = \left[\begin{array}{c}
2 \\
-1 \\
\end{array}\right],\ \vec{x_2} = \left[\begin{array}{c}
1 \\
2 \\
\end{array}\right] \\
\vec{x_1}^T\vec{x_2} = 2-2=0 \implies \vec{x_1} \perp \vec{x_2}$

- Theorem (Spectral Theorem)
Every **symmetric** matrix has factorization $A = Q\Lambda Q^T$ with $Q$ is orthogonal and $\Lambda$ is real, diagonal
- Example
$\vec{q_1} = {1 \over \sqrt{5}}\left[\begin{array}{c}
2 \\
-1 \\
\end{array}\right], \vec{q_2} = {1 \over \sqrt{5}}\left[\begin{array}{c}
1 \\
2 \\
\end{array}\right],\ Q = {1 \over \sqrt{5}}\left[\begin{array}{c c}
2 & 1 \\
-1 & 2 \\
\end{array}\right] = {1 \over \sqrt{5}}S \\
A = Q \Lambda Q^T = ({1 \over \sqrt{5}}S)\Lambda({1 \over \sqrt{5}}S^T) \\
\Lambda = Q^TAQ = ({1 \over \sqrt{5}}S^T)A({1 \over \sqrt{5}}S)$
- Proof
1. If $\lambda_i \not= \lambda_j,\ A\vec{x_i} = \lambda_i\vec{x_i}$ and $A\vec{x_j} = \lambda_j\vec{x_j}$
$\vec{x_j}^T(A\vec{x_i}) = \vec{x_j}^T(\lambda_i\vec{x_i}) = \lambda_i\vec{x_j}^T\vec{x_i} \\
(\vec{x_j}^TA)\vec{x_i} = (A^T\vec{x_j})^T\vec{x_i} = (A\vec{x_j})^T\vec{x_i} = \lambda_j\vec{x_j}^T\vec{x_i} \\
\implies \vec{x_j}^T(A\vec{x_i}) = (\vec{x_j}^TA)\vec{x_i} \\
\because\ \lambda_i \not= \lambda_j \implies \vec{x_j}^T\vec{x_i}=0 \implies \vec{x_i} \perp \vec{x_j}$
2. If there exists repeated $\lambda$ , by schur's decomposition
$A = QUQ^T \\
A^T = (QUQ^T)^T = QU^TQ^T = A \\
U = U^T \implies U \text{ must be diagonal}$
- Remark 1
$A = Q \Lambda Q^T = \lambda_1\vec{q_1}\vec{q_1}^T + \lambda_2\vec{q_2}\vec{q_2}^T + \cdots + \lambda_n\vec{q_n}\vec{q_n}^T$
where each $\vec{q_i}\vec{q_i}^T$ is a rank-1 matrix
This theorem suggest that every symmetric matrix can be decomposed into the sum of $n$ rank-1 matrices.
Moreover, if we group some $\lambda_i$'s together (ex. if $\lambda_1 = \lambda_2$ , use $\lambda_1(\vec{q_1}\vec{q_1}^T + \vec{q_2}\vec{q_2}^T)$)
we obtain $A = \sum\limits_{i=1}^k{\lambda_iP_i}$ where $P_i$ is the projection matrix onto the eigenspace $E_{\lambda_i}$
- Remark 2
For symmetricmatrix $A$
the number of non-zero eigenvalues $=r$
the number of non-zero pivots $=rank(A) = rank(\Lambda) =$ the number of eigenvalues

### Symmetric Matrix

- Theorem
A symmetric matrix has only real eigenvalues
- Recall (complex conjugate):
Let $z = a+bi,\ \overline{z} = a-bi$
For any two complex number $z,\ w$
1. $\overline{z+w} = \overline{z} + \overline{w}$
2. $\overline{z-w} = \overline{z} - \overline{w}$
3. $\overline{zw} = \overline{z}\ \overline{w}$
4. $\overline{{z \over w}} = {\bar{z} \over \bar{w}}\ if\ w \not= 0$
- Proof
Let $\lambda$ be an eigenvalue and $\vec{x}$ be a corresponding eigenvector, $A\vec{x} = \lambda\vec{x}$
$\overline{A\vec{x}} = A\overline{\vec{x}} = \overline{\lambda\vec{x}} = \overline{\lambda}\ \overline{\vec{x}}$
consider
$\lambda\vec{x}^T\overline{\vec{x}} = (A\vec{x})^T\overline{\vec{x}} = \vec{x}^TA^T\overline{\vec{x}} = \vec{x}^TA\overline{\vec{x}} = \vec{x}^T\overline{\lambda}\ \overline{\vec{x}} = \overline{\lambda}\vec{x}^T\overline{\vec{x}} \\
\therefore \lambda = \overline{\lambda} \implies \lambda \in \mathbb{R}$

- Theorem
For a real matrix $A$ (not necessarily symmetric), complex $\lambda$ and $\vec{x}$ come in **conjugate pairs**
- Proof
$\begin{split}A\vec{x} = \lambda\vec{x} &\implies \overline{A\vec{x}} = \overline{\lambda\vec{x}} \\
&\implies A\overline{\vec{x}} = \overline{\lambda}\ \overline{\vec{x}} \\
&\implies \overline{\lambda}\text{ is also an eigenvalue with } \overline{\vec{x}} \text{ being an eigenvector}\end{split}$
- Example
$A = \left[\begin{array}{c c}
0 & -1 \\
1 & 0 \\
\end{array}\right] \\
\begin{vmatrix}
A - \lambda I
\end{vmatrix} = \begin{vmatrix}
\left[\begin{array}{c c}
-\lambda & -1 \\
1 & -\lambda \\
\end{array}\right]
\end{vmatrix} = \lambda^2+1=0 \implies \lambda = \pm i \\
\lambda_1 = i,\ \vec{x_1} = \left[\begin{array}{c}
1 \\
-i \\
\end{array}\right],\ \lambda_2 = -i,\ \vec{x_2} = \left[\begin{array}{c}
1 \\
i \\
\end{array}\right] \\
\overline{\lambda_2} = \lambda_1,\ \overline{\vec{x_2}} = \vec{x_1}$

### Schur Decomposition

- Theorem
Let $A$ be a square matrix, $A = QUQ^{-1}$ where $U$ is an upper triangular matrix and $Q$ is unitary $(i.e.\ Q^T = Q^{-1})$
Moreover, if $A$ has real eigenvalues, then $Q^TQ=I$ (orthogonal matrix)
- Proof (by induction)
Assume this is true for any $(n-1) \times (n-1)$ matrices
Let $\vec{q_1}$ be an eigenvector s.t. $A\vec{q_1} = \lambda\vec{q_1}$
Extend $\vec{q_1}$ to an orthogonal basis $\{ \vec{q_1},\ \vec{q_2},\ \cdots,\ \vec{q_n} \}$ via Gram-Schmidt Process
Let $Q_1 = \left[\begin{array}{c c c c}
\vec{q_1} & \vec{q_2} & \cdots & \vec{q_n} \\
\end{array}\right]$ is unitary
$\begin{split}\overline{Q_1}^TAQ_1 &= \left[\begin{array}{c}
\overline{\vec{q_1}}^T \\
\overline{\vec{q_2}}^T \\
\vdots \\
\overline{\vec{q_n}}^T \\
\end{array}\right]\left[\begin{array}{c c c c}
A\vec{q_1} & A\vec{q_2} & \cdots & A\vec{q_n} \\
\end{array}\right] \\
&= \left[\begin{array}{c}
\overline{\vec{q_1}}^T \\
\overline{\vec{q_2}}^T \\
\vdots \\
\overline{\vec{q_n}}^T \\
\end{array}\right]\left[\begin{array}{c c c c}
\lambda\vec{q_1} & A\vec{q_2} & \cdots & A\vec{q_n} \\
\end{array}\right] \\
&= \left[\begin{array}{c c c c}
\lambda & * & \cdots & * \\
0 & & & \\
\vdots & & A_2 & \\
0 & & & \\
\end{array}\right] \text{ where } A_{2(n-1) \times (n-1)} = Q_2U_2\overline{Q_2}^T\end{split}$
Let $Q = Q_1\left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & Q_2 \\
\end{array}\right]$ is unitary because $Q_2$ is unitary
$\overline{Q}^TQ = \left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & \overline{Q_2}^T \\
\end{array}\right]\overline{Q_1}^TQ_1\left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & Q_2 \\
\end{array}\right] = \left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & \overline{Q_2}^T \\
\end{array}\right]\left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & Q_2 \\
\end{array}\right] = I \\
\begin{split}\overline{Q}^TAQ &= \left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & \overline{Q_2}^T \\
\end{array}\right]\overline{Q_1}^TAQ_1\left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & Q_2 \\
\end{array}\right] \\
&= \left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & \overline{Q_2}^T \\
\end{array}\right]\left[\begin{array}{c c c c}
\lambda & * & \cdots & * \\
0 & & & \\
\vdots & & A_2 & \\
0 & & & \\
\end{array}\right]\left[\begin{array}{c c}
1 & \vec{0}^T \\
\vec{0} & Q_2 \\
\end{array}\right] \\
&= \left[\begin{array}{c c c c}
\lambda & * & \cdots & * \\
0 & & & \\
\vdots & & \overline{Q_2}^TA_2Q_2 & \\
0 & & & \\
\end{array}\right] \\
&= \left[\begin{array}{c c c c}
\lambda & * & \cdots & * \\
0 & & & \\
\vdots & & U_2 & \\
0 & & & \\
\end{array}\right] = U\end{split}$