Linear-2 4

Polynomial division #theorem

\begin{matrix} Let f (x), g (x) \in F [x] : \deg (f (x)) \geq \deg (g (x)) \\ Then \exists q (x), r (x) \in F [x] : {\begin{matrix} f (x) = q (x) g (x) + r (x) \\ \deg (r (x)) < \deg (g (x)) \end{matrix} \end{matrix}

Divisibility of polynomial #lemma

\begin{matrix} Let f (x) \in F [x] \\ Let α \in F \\ Then (x - α) ∣ f (x) ⟺ f (α) = 0 \\ Proof: \\ ⟸ Let f (α) = 0 \\ \deg (f (x)) \geq 1 = d e g (x - α) \\ ⟹ \exists q (x), r (x) \in F [x] : {\begin{matrix} f (x) = q (x) (x - α) + r (x) \\ \deg (r (x)) < 1 \end{matrix} ⟹ r (x) = β \\ f (α) = q (α) \cdot 0 + r (α) = 0 ⟹ r (α) = 0 ⟹ r (x) = 0 \\ ⟹ f (x) = q (x) (x - α) ⟹ (x - α) ∣ f (x) \\ ⟹ Let (x - α) ∣ f (x) \\ ⟹ \exists q (x) \in F [x] : f (x) = q (x) (x - α) \\ ⟹ f (α) = q (α) \cdot 0 = 0 \end{matrix}

Algebraic and geometric multiplicities limits #lemma

\begin{matrix} Let A \in F^{n \times n} \\ Let α \in F be an eigenvalue of A \\ Then 1 \leq μ_{A} (α), γ_{A} (α) \leq n \\ Proof: \\ \exists v \neq 0 : (α I - A) v = 0 ⟹ N (α I - A) \neq 0 \\ ⟹ γ_{A} (α) = \dim (N (α I - A)) \geq 1 \\ A \in F^{n \times n} ⟹ N (α I - A) \subseteq F^{n} ⟹ \dim (N (α I - A)) \leq n \\ ⟹ 1 \leq γ_{A} (α) \leq n \\ (λ - α)^{μ_{A} (α)} ∣ P_{A} (λ) \\ ⟹ \deg ((λ - α)^{μ_{A} (α)}) \leq \deg (P_{A} (λ)) = n ⟹ μ_{A} (α) \leq n \\ P_{A} (α) = 0 ⟹ (λ - α) ∣ P_{A} (λ) \\ ⟹ μ_{A} (α) \geq 1 ⟹ 1 \leq μ_{A} (α) \leq n \end{matrix}

Geometric multiplicity is at most algebraic multiplicity #theorem

\begin{matrix} Let A \in F^{n \times n} \\ Let α \in F be an eigenvalue of A \\ Then γ_{A} (α) \leq μ_{A} (α) \\ Proof: \\ Let γ_{A} (α) = t \geq 1 \\ Let B = {v_{1}, \dots, v_{t}} be a basis of eigenspace in respect to α \\ Let C = B \cup {u_{1}, \dots, u_{n - t}} \\ Let P = (\begin{matrix} \overset{|}{\underset{|}{v_{1}}} & \dots & \overset{|}{\underset{|}{v_{t}}} & \overset{|}{\underset{|}{u_{1}}} & \dots & \overset{|}{\underset{|}{u_{n - t}}} \end{matrix}) \\ P is invertible \\ P^{- 1} A P = P^{- 1} (\begin{matrix} \overset{|}{\underset{|}{A v_{1}}} & \dots & \overset{|}{\underset{|}{A v_{t}}} & \overset{|}{\underset{|}{A u_{1}}} & \dots & \overset{|}{\underset{|}{A_{u_{n - t}}}} \end{matrix}) = \\ = P^{- 1} (\begin{matrix} α v_{1} & \dots & α v_{n} & \overset{|}{\underset{|}{*}} & \dots & \overset{|}{\underset{|}{*}} \end{matrix}) = (\begin{matrix} \overset{|}{\underset{|}{α P^{- 1} v_{1}}} & \dots & \overset{|}{\underset{|}{α P^{- 1} v_{t}}} & \overset{|}{\underset{|}{*}} & \dots & \overset{|}{\underset{|}{*}} \end{matrix}) = \\ \underset{\begin{matrix} P^{- 1} v_{i} = P^{- 1} C_{i} (P) \\ P^{- 1} C_{i} (P) = C_{i} (P^{- 1} P) \\ C_{i} (P^{- 1} P) = e_{i} \end{matrix}}{=} (\begin{matrix} \overset{|}{\underset{|}{α e_{1}}} & \dots & \overset{|}{\underset{|}{α e_{t}}} & \overset{|}{\underset{|}{*}} & \dots & \overset{|}{\underset{|}{*}} \end{matrix}) \\ ⟹ P^{- 1} A P = (\begin{matrix} α I_{t} & C \\ 0 & B \end{matrix}) \\ A \sim P^{- 1} A P ⟹ P_{A} (λ) = P_{P^{- 1} A P} (λ) = | λ I - P^{- 1} A P | = | \begin{matrix} (λ - α) I_{t} & C \\ 0 & λ I - B \end{matrix} | = \\ = | (λ - α) I_{t} | \cdot | λ I - B | = (λ - α)^{t} \cdot | λ I - B | \\ ⟹ μ_{A} (α) \geq t = γ_{A} (α) \end{matrix}

Linear independency of eigenvectors in respect to distinct eigenvalues #lemma

\begin{matrix} Let A \in F^{n \times n} \\ Let {λ_{1}, \dots, λ_{t}} be eigenvalues of A \\ Let \forall i \in [1, t] : A v_{i} = λ_{i} v_{i} \\ Then {v_{1}, \dots, v_{t}} is a linear independence \\ Proof: \\ Base case. {v_{t}} is a linear independence \\ Induction step. Let {v_{2}, \dots, v_{t}} be a linear independence \\ Let \sum_{i = 1}^{t} α_{i} v_{i} = 0 \\ ⟹ {\begin{matrix} \sum_{i = 1}^{t} α_{i} A v_{i} = \sum_{i = 1}^{t} α_{i} λ_{i} v_{i} = 0 \\ \sum_{i = 1}^{t} α_{i} λ_{1} v_{i} = 0 \end{matrix} \\ ⟹ \sum_{i = 2}^{t} α_{i} (λ_{i} - λ_{1}) v_{i} = 0 \\ \forall i \in [2, n] : λ_{i} \neq λ_{1} ⟹ α_{i} = 0 \\ ⟹ By induction: {v_{1}, \dots, v_{t}} is a linear independence \end{matrix}

Union of Eigenspace bases #theorem

\begin{matrix} Let A \in F^{n \times n} \\ Let {α_{i}}_{i \in [1, t]} \subseteq F be eigenvalues of A \\ Let \forall i \in [1, t] : B_{i} be a basis of eigenspace in respect to α_{i} \\ Then ⋃_{i = 1}^{t} B_{i} is a linear independence \\ Proof: \\ Let \forall i \in [1, t] : B_{i} = {v_{i_{1}}, \dots, v_{i_{k_{i}}}} \\ Let {α_{i_{j}}}_{\begin{matrix} i \in [1, t] \\ j \in [1, k_{i}] \end{matrix}} \subseteq F \\ Let \sum_{i = 1}^{t} \sum_{j = 1}^{k_{i}} α_{i_{j}} v_{i_{j}} = 0 \\ Case 1. Let \forall i \in [1, t] : \sum_{j = 1}^{k_{i}} α_{i_{j}} v_{i_{j}} = 0 \\ ⟹ \forall i \in [1, t] : B_{i} is a linear independence ⟹ \forall j \in [1, k_{i}] : α_{i_{j}} = 0 \\ ⟹ ⋃_{i = 1}^{t} B_{i} is a linear independence \\ Case 2. Let \exists i \in [1, t] : \sum_{j = 1}^{k_{i}} α_{i_{j}} v_{i_{j}} \neq 0 \\ Let \forall i \in [1, t] : u_{i} = \sum_{j = 1}^{k_{i}} α_{i_{j}} v_{i_{j}} \\ \forall i \in [1, t] : u_{i} \in s p (B_{i}) ⟹ [\begin{matrix} u_{i} = 0 \\ A u_{i} = λ_{i} u_{i} \end{matrix} \\ \sum_{i = 1}^{t} u_{i} = 0 \underset{\begin{matrix} {u_{1}, \dots, u_{t}} \\ is a linear independence \end{matrix}}{⟹} \forall i \in [1, t] : u_{i} = 0 - Contradiction! \\ ⟹ Case 1. \end{matrix}

Diagonalizability and geometric multiplicities #lemma

\begin{matrix} Let A \in F^{n \times n} \\ Then A is diagonalizable ⟺ \sum_{i = 1}^{t} γ_{A} (λ_{i}) = n \\ Proof: \\ ⟹ Let A be diagonalizable \\ ⟹ \exists B = {v_{1}, \dots, v_{n}} basis of F^{n} : \forall i \in [1, n] : A v_{i} = λ_{i} v_{i} \\ ⟹ t = n ⟹ n = \sum_{i = 1}^{n} 1 \leq \sum_{i = 1}^{n} γ_{A} (λ_{i}) \leq n ⟹ \sum_{i = 1}^{n} γ_{A} (λ_{i}) = n \\ ⟸ Let \sum_{i = 1}^{t} γ_{A} (λ_{i}) = n \\ Let \forall i \in [1, t] : B_{i} = {v_{i_{1}}, \dots, v_{i_{k_{i}}}} \\ Let P \in F^{n \times n} : C_{i_{j}} (P) = v_{i_{j}} \\ P^{- 1} A P = P^{- 1} (\begin{matrix} \overset{|}{\underset{|}{λ_{1} v_{1_{1}}}} & \dots & \overset{|}{\underset{|}{λ_{1} v_{1_{k_{1}}}}} & \dots \dots & \overset{|}{\underset{|}{λ_{t} v_{t_{1}}}} & \dots & \overset{|}{\underset{|}{λ_{t} v_{t_{k_{t}}}}} \end{matrix}) = \\ = (\begin{matrix} λ_{1} I_{k_{1}} & 0 & \dots & 0 \\ 0 & λ_{2} I_{k_{2}} & ⋱ & ⋮ \\ ⋮ & ⋱ & ⋱ & 0 \\ 0 & \dots & 0 & λ_{t} I_{k_{t}} \end{matrix}) = D \\ ⟹ A is diagonalizable \end{matrix}

Diagonalizability criterion #theorem

\begin{matrix} Let A \in F^{n \times n} \\ Then A is diagonalizable ⟺ {\begin{matrix} \sum_{i = 1}^{t} μ_{A} (λ_{i}) = n \\ \forall i \in [1, t] : μ_{A} (λ_{i}) = γ_{A} (λ_{i}) \end{matrix} \\ Proof: \\ ⟹ Let A be diagonalizable \\ ⟹ \sum_{i = 1}^{t} γ_{A} (λ_{i}) = n \\ \forall i \in [1, t] : γ_{A} (λ_{i}) \leq μ_{A} (λ_{i}) \\ ⟹ n = \sum_{i = 1}^{t} γ_{A} (λ_{i}) \leq \sum_{i = 1}^{t} μ_{A} (λ_{i}) \leq n \\ ⟹ \sum_{i = 1}^{t} μ_{A} (λ_{i}) = n \\ ⟹ \sum_{i = 1}^{t} μ_{A} (λ_{i}) - \sum_{i = 1}^{t} γ_{A} (λ_{i}) = 0 ⟹ \sum_{i = 1}^{t} (\underset{\geq 0}{\underset{⏟}{μ_{A} (λ_{i}) - γ_{A} (λ_{i})}}) = 0 \\ ⟹ \forall i \in [1, t] : μ_{A} (λ_{i}) = γ_{A} (λ_{i}) \\ ⟸ Let {\begin{matrix} \sum_{i = 1}^{t} μ_{A} (λ_{i}) = n \\ \forall i \in [1, t] : μ_{A} (λ_{i}) = γ_{A} (λ_{i}) \end{matrix} \\ {\begin{matrix} \sum_{i = 1}^{t} μ_{A} (λ_{i}) = n \\ \forall i \in [1, t] : μ_{A} (λ_{i}) = γ_{A} (λ_{i}) \end{matrix}} ⟹ \sum_{i = 1}^{t} γ_{A} (λ_{i}) = n \\ ⟹ A is diagonalizable \end{matrix}