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 Λ S^{- 1}$ or
$Λ = S^{- 1} A S$ (diagonalization)
where
$Λ = [\begin{array}{cccc} λ_{1} & 0 & \dots & 0 \\ 0 & λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n} \end{array}]$ with
$λ_{i}$ being eigenvalue of
$A$ and
$S = [\begin{array}{cccc} \vec{x_{1}} & \vec{x_{2}} & \dots & \vec{x_{n}} \end{array}]$ consists of eigenvectors
$\vec{x_{i}}$ corresponding to
$λ_{i}$ if and only if
$A$ has
$n$ linearly independent eigenvectors
- Proof
  
  $\begin{aligned} S & = [\begin{array}{cccc} \vec{x_{1}} & \vec{x_{2}} & \dots & \vec{x_{n}} \end{array}] \\ A S & = [\begin{array}{cccc} A \vec{x_{1}} & A \vec{x_{2}} & \dots & A \vec{x_{n}} \end{array}] = [\begin{array}{cccc} λ_{1} \vec{x_{1}} & λ_{2} \vec{x_{2}} & \dots & λ_{n} \vec{x_{n}} \end{array}] \\ = [\begin{array}{cccc} \vec{x_{1}} & \vec{x_{2}} & \dots & \vec{x_{n}} \end{array}] [\begin{array}{cccc} λ_{1} & 0 & \dots & 0 \\ 0 & λ_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n} \end{array}] = S Λ \end{aligned}$
  
  $S$ is invertible if and only if
  $\vec{x_{1}}, \vec{x_{2}}, \dots, \vec{x_{n}}$ are linearly independent
  
  $⟹ A = S Λ S^{- 1}$ if and only if
  $\vec{x_{1}}, \vec{x_{2}}, \dots, \vec{x_{n}}$ are linearly independent
  The matrix
  $A$ is said to be diagonalizable
Theorem
If
$A$ is diagonalizable,
$A^{k} = S Λ^{k} S^{- 1}$ where
$Λ^{k} = [\begin{array}{cccc} λ_{1}^{k} & 0 & \dots & 0 \\ 0 & λ_{2}^{k} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n}^{k} \end{array}]$
- Proof
  
  $A = S Λ S^{- 1} A^{2} = (S Λ S^{- 1}) (S Λ S^{- 1}) = S Λ^{2} S^{- 1} where Λ^{2} = [\begin{array}{cccc} λ_{1}^{2} & 0 & \dots & 0 \\ 0 & λ_{2}^{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & \dots & λ_{n}^{2} \end{array}] ∴ A^{k} = S Λ^{k} S^{- 1}$
- Example
  
  $A = [\begin{array}{cc} 0.8 & 0.3 \\ 0.2 & 0.7 \end{array}], Λ = [\begin{array}{cc} λ_{1} & 0 \\ 0 & λ_{2} \end{array}] = [\begin{array}{cc} 1 & 0 \\ 0 & 0.5 \end{array}] S = [\begin{array}{cc} \vec{x_{1}} & \vec{x_{2}} \end{array}] = [\begin{array}{cc} 0.6 & 1 \\ 0.4 & - 1 \end{array}], S^{- 1} = [\begin{array}{cc} 1 & 1 \\ 0.4 & - 0.6 \end{array}] check A = S Λ S^{- 1} = [\begin{array}{cc} 0.6 & 1 \\ 0.4 & - 1 \end{array}] [\begin{array}{cc} 1 & 0 \\ 0 & 0.5 \end{array}] [\begin{array}{cc} 1 & 1 \\ 0.4 & - 0.6 \end{array}] \begin{aligned} A^{\infty} & = S Λ^{\infty} S^{- 1} \\ = [\begin{array}{cc} 0.6 & 1 \\ 0.4 & - 1 \end{array}] [\begin{array}{cc} 1^{\infty} & 0 \\ 0 & {0.5}^{\infty} \end{array}] [\begin{array}{cc} 1 & 1 \\ 0.4 & - 0.6 \end{array}] \\ = [\begin{array}{cc} 0.6 & 1 \\ 0.4 & - 1 \end{array}] [\begin{array}{cc} 1 & 0 \\ 0 & 0 \end{array}] [\begin{array}{cc} 1 & 1 \\ 0.4 & - 0.6 \end{array}] \\ = [\begin{array}{cc} 0.6 & 0 \\ 0.4 & 0 \end{array}] [\begin{array}{cc} 1 & 1 \\ 0.4 & - 0.6 \end{array}] = [\begin{array}{cc} 0.6 & 0.6 \\ 0.4 & 0.4 \end{array}] \end{aligned}$
Theorem
Let
$λ_{1}, λ_{2}, \dots, λ_{n}$ be
$A$ 's eigenvalues and
$\vec{x_{1}}, \vec{x_{2}}, \dots, \vec{x_{n}}$ be the corresponding eigenvectors, respectively.
If all
$λ_{i}$ are distinct then
${\vec{x_{1}}, \vec{x_{2}}, \dots, \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 . λ_{1}, λ_{2}, \dots, λ_{k}$ are distinct and
  ${\vec{x_{1}}, \vec{x_{2}}, \dots, \vec{x_{k}}}$ is linearly independent
  consider
  $n = k + 1$ , let
  $λ_{1}, λ_{2}, \dots, λ_{k}, λ_{k + 1}$ are all distinct if
  ${\vec{x_{1}}, \vec{x_{2}}, \dots, \vec{x_{k}}, \vec{x_{k + 1}}}$ is not linearly independent
  
  $i . e . c_{1} \vec{x_{1}} + c_{2} \vec{x_{2}} + \dots + c_{k} \vec{x_{k}} = \vec{x_{k + 1}} or c_{1} \vec{x_{1}} + c_{2} \vec{x_{2}} + \dots + c_{k} \vec{x_{k}} - \vec{x_{k + 1}} = 0$
  
  $(A \vec{x} = λ \vec{x} ⟹ (A - λ I) \vec{x} = 0) \begin{aligned} (A - λ_{k + 1} I) {\vec{x}}_{k + 1} = 0 \\ ⟹ & (A - λ_{k + 1} I) (c_{1} \vec{x_{1}} + c_{2} \vec{x_{2}} + \dots + c_{k} \vec{x_{k}}) = 0 \\ ⟹ & (A c_{1} \vec{x_{1}} + A c_{2} \vec{x_{2}} + \dots + A c_{k} \vec{x_{k}}) - (λ_{k + 1} c_{1} \vec{x_{1}} + λ_{k + 1} c_{2} \vec{x_{2}} + \dots + λ_{k + 1} c_{k} \vec{x_{k}}) = 0 \\ ∵ & A \vec{x_{1}} = λ_{1} \vec{x_{1}}, A \vec{x_{2}} = λ_{2} \vec{x_{2}}, \dots, A \vec{x_{k}} = λ_{k} \vec{x_{k}} \\ ⟹ & (c_{1} λ_{1} \vec{x_{1}} + c_{2} λ_{2} \vec{x_{2}} + \dots + c_{k} λ_{k} \vec{x_{k}}) - (c_{1} λ_{k + 1} \vec{x_{1}} + c_{2} λ_{k + 1} \vec{x_{2}} + \dots + c_{k} λ_{k + 1} \vec{x_{k}}) = 0 \\ ⟹ & \sum_{i = 1}^{k} c_{i} λ_{i} \vec{x_{i}} - \sum_{i = 1}^{k} c_{i} λ_{k + 1} \vec{x_{i}} = 0 \\ ⟹ & \sum_{i = 1}^{k} c_{i} (λ_{i} - λ_{k + 1}) \vec{x_{i}} = 0 \\ ⟹ & λ_{i} - λ_{k + 1} = 0 ⟹ λ_{i} = λ_{k + 1} (NOT all distinct)(contradiction) \\ ∴ & {\vec{x_{1}}, \vec{x_{2}}, \dots, \vec{x_{k}}, \vec{x_{k + 1}}} is linearly independent \end{aligned}$
Define(GM): The geometric multiplicity (GM) of an eigenvalue
$λ$ of
$A$ is the dimension of the eigenspace
$E_{A} (λ) i . e . N (A - λ I)$
Define(AM): The algebraic multiplicity (AM) of an eigenvalue
$λ$ of
$A$ is the number of times
$λ$ appears as a root of
$| \begin{matrix} A - λ I \end{matrix} | = 0$
- Example
  
  $A = [\begin{array}{cc} 0 & 1 \\ 0 & 0 \end{array}] | \begin{matrix} A - λ I \end{matrix} | = λ^{2} - 0 = 0, λ^{2} = 0 ⟹ A M = 2 E_{A} (λ = 0) = N (A - λ I) = N (A) = {c [\begin{matrix} 1 \\ 0 \end{matrix}]} ⟹ G M = d i m (E_{A}) = 1$
Theorem
Let
$A$ be
$n \times n$ matrix with eigenvalues
$λ_{1}, λ_{2}, \dots, λ_{k}$

$A$ is diagonalizable if and only if
1. $\sum_{i = 1}^{k} m_{i} = n, m_{i} = the AM of λ_{i}$
2. $m_{i} = d i m (E_{A} (λ_{i})) = G M (i) f o r i \in {1, 2, \dots, k}$
Example

$A = [\begin{array}{ccc} 4 & 0 & 1 \\ 2 & 3 & 2 \\ 1 & 0 & 4 \end{array}] | \begin{matrix} A - λ I \end{matrix} | = | \begin{matrix} [\begin{array}{ccc} 4 - λ & 0 & 1 \\ 2 & 3 - λ & 2 \\ 1 & 0 & 4 - λ \end{array}] \end{matrix} | = - (λ - 5) (λ - 3)^{2} \begin{aligned} G M (1) = E_{A} (λ_{1} = 5) & = N (A - 5 I) \\ = N ([\begin{array}{ccc} - 1 & 0 & 1 \\ 2 & - 2 & 2 \\ 1 & 0 & - 1 \end{array}]) = {c [\begin{array}{c} 1 \\ 2 \\ 1 \end{array}]} \end{aligned} \begin{aligned} G M (2) = E_{A} (λ_{1} = 3) & = N (A - 3 I) \\ = N ([\begin{array}{ccc} 1 & 0 & 1 \\ 2 & 0 & 2 \\ 1 & 0 & 1 \end{array}]) = {c_{1} [\begin{array}{c} - 1 \\ 0 \\ 1 \end{array}] + c_{2} [\begin{array}{c} 0 \\ 1 \\ 0 \end{array}]} \end{aligned} {\begin{matrix} λ_{1} = 5, A M (1) = 1, G M (1) = 1 \\ λ_{2} = 3, A M (2) = 2, G M (2) = 2 \end{matrix} ∴ A is diagonalizable, i . e . {[\begin{matrix} 1 \\ 2 \\ 1 \end{matrix}], [\begin{matrix} 1 \\ 0 \\ - 1 \end{matrix}], [\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}]} are linearly independent$

Positive Definite Matrices & Cholesky Factorization

Define (Positive definite): A symmetric matrix
$A$ is positive definite if
${\vec{x}}^{T} A \vec{x} > 0 \forall \vec{x} \neq \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}}^{T} A \vec{x} > 0, \forall \vec{x} \neq 0$
5. $A = R^{T} R$ where
  $R$ has independent columns (Cholesky Factorization)
- Proof 1 and 4
  For a symmetric
  $A$ ,
  $A = L D L^{T}$ where
  
  $L = [\begin{array}{cccc} 1 & 0 & \dots & 0 \\ 1 & \dots & 0 \\ ⋱ & ⋮ \\ 1 \end{array}] = [\begin{array}{cccc} \vec{a_{1}} & \vec{a_{2}} & \dots & \vec{a_{n}} \end{array}] D = [\begin{array}{cccc} d_{1} & 0 & \dots & 0 \\ 0 & d_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & d_{n} \end{array}], where d_{1}, d_{2}, \dots, d_{n} are pivots \begin{aligned} {\vec{x}}^{T} A \vec{x} & = {\vec{x}}^{T} L D L^{T} \vec{x} \\ = {\vec{x}}^{T} [\begin{array}{cccc} \vec{a_{1}} & \vec{a_{2}} & \dots & \vec{a_{n}} \end{array}] [\begin{array}{cccc} d_{1} & 0 & \dots & 0 \\ 0 & d_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & d_{n} \end{array}] [\begin{array}{c} {\vec{a_{1}}}^{T} \\ {\vec{a_{2}}}^{T} \\ ⋮ \\ {\vec{a_{n}}}^{T} \end{array}] \vec{x} \\ = \sum_{i = 1}^{n} d_{i} ({\vec{x}}^{T} \vec{a_{i}} {\vec{a_{i}}}^{T} \vec{x}) = \sum_{i = 1}^{n} d_{i} ({\vec{a_{i}}}^{T} \vec{x})^{2} \end{aligned} If d_{i} \geq 0 for all i = 1, 2, \dots, n ⟹ {\vec{x}}^{T} A \vec{x} \geq 0 This is 0 only when 1. \vec{x} = \vec{0} 2. \exists \vec{x} s . t . L^{T} \vec{x} = \vec{0} i . e . \exists \vec{x} \in N (L^{T}) However, N (L^{T}) = {0} since L^{T} has full rank$
- Proof 5
  
  $A = L D L^{T}$ and
  $D = [\begin{array}{cccc} d_{1} & 0 & \dots & 0 \\ 0 & d_{2} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & d_{n} \end{array}]$ where
  $d_{i} > 0$
  Split
  $D$ into
  $D^{'} D^{' T} = [\begin{array}{cccc} \sqrt{d_{1}} & 0 & \dots & 0 \\ 0 & \sqrt{d_{2}} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \sqrt{d_{n}} \end{array}] [\begin{array}{cccc} \sqrt{d_{1}} & 0 & \dots & 0 \\ 0 & \sqrt{d_{2}} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \sqrt{d_{n}} \end{array}]$
  
  $∴ A = L D^{'} D^{' T} L^{T} = R^{T} R where R = D^{' T} L^{T} = [\begin{array}{cccc} \sqrt{d_{1}} & 0 & \dots & 0 \\ 0 & \sqrt{d_{2}} & \dots & 0 \\ ⋮ & ⋮ & ⋱ & ⋮ \\ 0 & 0 & 0 & \sqrt{d_{n}} \end{array}] [\begin{array}{cccc} 1 \\ 0 & 1 \\ ⋮ & ⋮ & ⋱ \\ 0 & 0 & 0 & 1 \end{array}] has independent columns ⟹ A = R^{T} R where R has independent columns$
- Example
  
  $A = [\begin{array}{cc} 1 & - 2 \\ - 2 & 6 \end{array}]$ , we have shown that 1 and 4
  
  $3. | \begin{matrix} A - λ I \end{matrix} | = | \begin{matrix} [\begin{array}{cc} 1 - λ & - 2 \\ - 2 & 6 - λ \end{array}] \end{matrix} | = λ^{2} - 7 λ + 2 = 0 ⟹ λ = \frac{7 \pm \sqrt{41}}{2} > 0 \begin{aligned} 5. A = L D L^{T} & = [\begin{array}{cc} 1 & 0 \\ - 2 & 1 \end{array}] [\begin{array}{cc} 1 & 0 \\ 0 & 2 \end{array}] [\begin{array}{cc} 1 & - 2 \\ 0 & 1 \end{array}] \\ = R^{T} R where R = [\begin{array}{cc} 1 & 0 \\ 0 & \sqrt{2} \end{array}] [\begin{array}{cc} 1 & - 2 \\ 0 & 1 \end{array}] = [\begin{array}{cc} 1 & - 2 \\ 0 & \sqrt{2} \end{array}] \end{aligned}$

$\forall \vec{x} \neq 0$ , A symmetric
$A$ is

Positive definite if all
$λ_{i} > 0 ({\vec{x}}^{T} A \vec{x} > 0)$

Positive semidefinite if all
$λ_{i} \geq 0 ({\vec{x}}^{T} A \vec{x} \geq 0)$

Negative definite if all
$λ_{i} < 0 ({\vec{x}}^{T} A \vec{x} < 0)$

Negative semidefinite if all
$λ_{i} \leq 0 ({\vec{x}}^{T} A \vec{x} \leq 0)$

Indefinite, otherwise

Example

$A = [\begin{array}{cc} 1 & 2 \\ 2 & 4 \end{array}], λ_{1} = 0, λ_{2} = 5, \vec{x_{1}} = [\begin{matrix} 2 \\ - 1 \end{matrix}], \vec{x_{2}} = [\begin{matrix} 1 \\ 2 \end{matrix}] {\vec{x_{1}}}^{T} \vec{x_{2}} = 2 - 2 = 0 ⟹ \vec{x_{1}} ⊥ \vec{x_{2}}$
Theorem (Spectral Theorem)
Every symmetric matrix has factorization
$A = Q Λ Q^{T}$ with
$Q$ is orthogonal and
$Λ$ is real, diagonal
- Example
  
  $\vec{q_{1}} = \frac{1}{\sqrt{5}} [\begin{matrix} 2 \\ - 1 \end{matrix}], \vec{q_{2}} = \frac{1}{\sqrt{5}} [\begin{matrix} 1 \\ 2 \end{matrix}], Q = \frac{1}{\sqrt{5}} [\begin{array}{cc} 2 & 1 \\ - 1 & 2 \end{array}] = \frac{1}{\sqrt{5}} S A = Q Λ Q^{T} = (\frac{1}{\sqrt{5}} S) Λ (\frac{1}{\sqrt{5}} S^{T}) Λ = Q^{T} A Q = (\frac{1}{\sqrt{5}} S^{T}) A (\frac{1}{\sqrt{5}} S)$
- Proof
1. If
  $λ_{i} \neq λ_{j}, A \vec{x_{i}} = λ_{i} \vec{x_{i}}$ and
  $A \vec{x_{j}} = λ_{j} \vec{x_{j}}$
  
  ${\vec{x_{j}}}^{T} (A \vec{x_{i}}) = {\vec{x_{j}}}^{T} (λ_{i} \vec{x_{i}}) = λ_{i} {\vec{x_{j}}}^{T} \vec{x_{i}} ({\vec{x_{j}}}^{T} A) \vec{x_{i}} = (A^{T} \vec{x_{j}})^{T} \vec{x_{i}} = (A \vec{x_{j}})^{T} \vec{x_{i}} = λ_{j} {\vec{x_{j}}}^{T} \vec{x_{i}} ⟹ {\vec{x_{j}}}^{T} (A \vec{x_{i}}) = ({\vec{x_{j}}}^{T} A) \vec{x_{i}} ∵ λ_{i} \neq λ_{j} ⟹ {\vec{x_{j}}}^{T} \vec{x_{i}} = 0 ⟹ \vec{x_{i}} ⊥ \vec{x_{j}}$
2. If there exists repeated
  $λ$ , by schur's decomposition
  
  $A = Q U Q^{T} A^{T} = (Q U Q^{T})^{T} = Q U^{T} Q^{T} = A U = U^{T} ⟹ U must be diagonal$
- Remark 1
  
  $A = Q Λ Q^{T} = λ_{1} \vec{q_{1}} {\vec{q_{1}}}^{T} + λ_{2} \vec{q_{2}} {\vec{q_{2}}}^{T} + \dots + λ_{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
  $λ_{i}$ 's together (ex. if
  $λ_{1} = λ_{2}$ , use
  $λ_{1} (\vec{q_{1}} {\vec{q_{1}}}^{T} + \vec{q_{2}} {\vec{q_{2}}}^{T})$ )
  we obtain
  $A = \sum_{i = 1}^{k} λ_{i} P_{i}$ where
  $P_{i}$ is the projection matrix onto the eigenspace
  $E_{λ_{i}}$
- Remark 2
  For symmetricmatrix
  $A$
  the number of non-zero eigenvalues
  $= r$
  the number of non-zero pivots
  $= r a n k (A) = r a n k (Λ) =$ the number of eigenvalues

Symmetric Matrix

Theorem
A symmetric matrix has only real eigenvalues
- Recall (complex conjugate):
  Let
  $z = a + b i, \overset{―}{z} = a - b i$
  For any two complex number
  $z, w$
  1. $\overset{―}{z + w} = \overset{―}{z} + \overset{―}{w}$
  2. $\overset{―}{z - w} = \overset{―}{z} - \overset{―}{w}$
  3. $\overset{―}{z w} = \overset{―}{z} \overset{―}{w}$
  4. $\overset{―}{\frac{z}{w}} = \frac{\bar{z}}{\bar{w}} i f w \neq 0$
- Proof
  Let
  $λ$ be an eigenvalue and
  $\vec{x}$ be a corresponding eigenvector,
  $A \vec{x} = λ \vec{x}$
  
  $\overset{―}{A \vec{x}} = A \overset{―}{\vec{x}} = \overset{―}{λ \vec{x}} = \overset{―}{λ} \overset{―}{\vec{x}}$
  consider
  
  $λ {\vec{x}}^{T} \overset{―}{\vec{x}} = (A \vec{x})^{T} \overset{―}{\vec{x}} = {\vec{x}}^{T} A^{T} \overset{―}{\vec{x}} = {\vec{x}}^{T} A \overset{―}{\vec{x}} = {\vec{x}}^{T} \overset{―}{λ} \overset{―}{\vec{x}} = \overset{―}{λ} {\vec{x}}^{T} \overset{―}{\vec{x}} ∴ λ = \overset{―}{λ} ⟹ λ \in R$
Theorem
For a real matrix
$A$ (not necessarily symmetric), complex
$λ$ and
$\vec{x}$ come in conjugate pairs
- Proof
  
  $\begin{aligned} A \vec{x} = λ \vec{x} & ⟹ \overset{―}{A \vec{x}} = \overset{―}{λ \vec{x}} \\ ⟹ A \overset{―}{\vec{x}} = \overset{―}{λ} \overset{―}{\vec{x}} \\ ⟹ \overset{―}{λ} is also an eigenvalue with \overset{―}{\vec{x}} being an eigenvector \end{aligned}$
- Example
  
  $A = [\begin{array}{cc} 0 & - 1 \\ 1 & 0 \end{array}] | \begin{matrix} A - λ I \end{matrix} | = | \begin{matrix} [\begin{array}{cc} - λ & - 1 \\ 1 & - λ \end{array}] \end{matrix} | = λ^{2} + 1 = 0 ⟹ λ = \pm i λ_{1} = i, \vec{x_{1}} = [\begin{matrix} 1 \\ - i \end{matrix}], λ_{2} = - i, \vec{x_{2}} = [\begin{matrix} 1 \\ i \end{matrix}] \overset{―}{λ_{2}} = λ_{1}, \overset{―}{\vec{x_{2}}} = \vec{x_{1}}$

Schur Decomposition

Theorem
Let
$A$ be a square matrix,
$A = Q U Q^{- 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^{T} Q = 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}} = λ \vec{q_{1}}$
  Extend
  $\vec{q_{1}}$ to an orthogonal basis
  ${\vec{q_{1}}, \vec{q_{2}}, \dots, \vec{q_{n}}}$ via Gram-Schmidt Process
  Let
  $Q_{1} = [\begin{array}{cccc} \vec{q_{1}} & \vec{q_{2}} & \dots & \vec{q_{n}} \end{array}]$ is unitary
  
  $\begin{aligned} {\overset{―}{Q_{1}}}^{T} A Q_{1} & = [\begin{array}{c} {\overset{―}{\vec{q_{1}}}}^{T} \\ {\overset{―}{\vec{q_{2}}}}^{T} \\ ⋮ \\ {\overset{―}{\vec{q_{n}}}}^{T} \end{array}] [\begin{array}{cccc} A \vec{q_{1}} & A \vec{q_{2}} & \dots & A \vec{q_{n}} \end{array}] \\ = [\begin{array}{c} {\overset{―}{\vec{q_{1}}}}^{T} \\ {\overset{―}{\vec{q_{2}}}}^{T} \\ ⋮ \\ {\overset{―}{\vec{q_{n}}}}^{T} \end{array}] [\begin{array}{cccc} λ \vec{q_{1}} & A \vec{q_{2}} & \dots & A \vec{q_{n}} \end{array}] \\ = [\begin{array}{cccc} λ & * & \dots & * \\ 0 \\ ⋮ & A_{2} \\ 0 \end{array}] where A_{2 (n - 1) \times (n - 1)} = Q_{2} U_{2} {\overset{―}{Q_{2}}}^{T} \end{aligned}$
  Let
  $Q = Q_{1} [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & Q_{2} \end{array}]$ is unitary because
  $Q_{2}$ is unitary
  
  ${\overset{―}{Q}}^{T} Q = [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & {\overset{―}{Q_{2}}}^{T} \end{array}] {\overset{―}{Q_{1}}}^{T} Q_{1} [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & Q_{2} \end{array}] = [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & {\overset{―}{Q_{2}}}^{T} \end{array}] [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & Q_{2} \end{array}] = I \begin{aligned} {\overset{―}{Q}}^{T} A Q & = [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & {\overset{―}{Q_{2}}}^{T} \end{array}] {\overset{―}{Q_{1}}}^{T} A Q_{1} [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & Q_{2} \end{array}] \\ = [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & {\overset{―}{Q_{2}}}^{T} \end{array}] [\begin{array}{cccc} λ & * & \dots & * \\ 0 \\ ⋮ & A_{2} \\ 0 \end{array}] [\begin{array}{cc} 1 & {\vec{0}}^{T} \\ \vec{0} & Q_{2} \end{array}] \\ = [\begin{array}{cccc} λ & * & \dots & * \\ 0 \\ ⋮ & {\overset{―}{Q_{2}}}^{T} A_{2} Q_{2} \\ 0 \end{array}] \\ = [\begin{array}{cccc} λ & * & \dots & * \\ 0 \\ ⋮ & U_{2} \\ 0 \end{array}] = U \end{aligned}$

Linear Algebra Note 6

Eigenvectors & Eigenvalues (2021.12.08 ~ 2021.12.17)

Eigenvalue Decomposition (EVD) or Matrix Diagonalization

Positive Definite Matrices & Cholesky Factorization

Symmetric Matrix

Schur Decomposition

Read more

Linear Algebra Note 7

Linear Algebra Note 5

Linear Algebra Note 4

Linear Algebra Note 3