Theorems and proofs

(1) Short criterion for a vector subspace

\begin{matrix} Let V be a vector space over F \\ Let W \subseteq V \\ 1. 0_{V} \in W \\ 2. \forall α \in F, \forall u, v \in W : u + α v \in W \\ 1 and 2 ⟺ W is a vector subspace of V \\ Note: 2 can be separated into two properties: \\ 2.1 \forall u, v \in W : u + v \in W \\ 2.2 \forall α \in F, \forall v \in W : α v \in W \\ Proof: \\ Let W be a vector subspace of V \\ ⟹ W is a vector space ⟹ 0_{W} \in W \\ 0_{W} is neutral to addition in W : 0_{W} = 0_{W} + 0_{W} \\ ⟹ \underset{0_{V}}{\underset{⏟}{0_{W} + (- 0_{W})}} = 0_{W} + (\underset{0_{V}}{\underset{⏟}{0_{W} + (- 0_{W})}}) ⟹ 0_{V} = 0_{W} + 0_{V} \\ 0_{V} is neutral to addition in V ⟹ 0_{W} = 0_{V} ⟹ 0_{V} \in W \\ W is a vector space ⟹ W is closed for addition and multiplication by scalar \\ ⟹ \forall α \in F, \forall u, v \in W : u + α v \in W \end{matrix}

\begin{matrix} Let 1 and 2 \\ Let us prove that W is a vector space over F by checking 7 vector space axioms: \\ \begin{matrix} a . & Closure on addition and multiplication by scalar \\ b . & Commutativity \\ c . & Associativity \\ d . & Distributivity \\ e . & Neutral element for addition \\ f . & Inverse on addition \\ g . & Neutral element for multiplication by scalar \end{matrix} \\ 1 and 2 ⟹ W is closed on addition and multiplication by scalar ⟹ a \\ \forall α \in F, \forall v_{1}, v_{2} \in W : v_{1}, v_{2} \in V ⟹ {\begin{matrix} v_{1} + v_{2} = v_{2} + v_{1} \\ α v_{1} = v_{1} α \end{matrix} ⟹ b \\ \forall α, β \in F, \forall v_{1}, v_{2}, v_{3} \in W : v_{1}, v_{2}, v_{3} \in V ⟹ {\begin{matrix} (v_{1} + v_{2}) + v_{3} = v_{1} + (v_{2} + v_{3}) \\ α (β v) = (α β) v \end{matrix} ⟹ c \\ \forall α, β \in F, \forall v_{1}, v_{2} \in W : v_{1}, v_{2} \in V ⟹ {\begin{matrix} α (v_{1} + v_{2}) = α v_{1} + α v_{2} \\ (α + β) v = α v + β v \end{matrix} ⟹ d \\ 1 ⟹ \forall v \in W : 0_{v} + v = v \in W ⟹ e \\ \forall v \in W : v \in V ⟹ 1_{F} \cdot v = v \in W ⟹ g \\ \forall v \in W : v \in V ⟹ \exists - v \in V : v + (- v) = 0_{V} \\ 1_{F} v + (- 1_{F}) v = (1_{F} + (- 1_{F})) v = 0_{V} ⟹ - v = - 1_{F} v ⟹ - v \in W ⟹ f \\ ⟹ W is a vector space ⟹ W is a vector subspace of V \end{matrix}

(2) Elementary row operations

\begin{matrix} Let A \in F^{m \times n} \\ Let p be an elementary row operation \\ Then p (A) = p (I) A \\ Proof: \\ Let p be scalar row multiplication \\ α \in F, i \in [1, m] : \forall X \in F^{m \times n} : R_{i} (p (X)) = α R_{i} (X) \\ Let k \neq i \\ R_{k} (p (I) A) = R_{k} (p (I)) A = R_{k} (I) A = e_{k} A = R_{k} (A) = R_{k} (p (A)) \\ R_{i} (p (I) A) = R_{i} (p (I)) A = α R_{i} (I) A = α e_{i} A = α R_{i} (A) = R_{i} (p (A)) \\ ⟹ p (A) = p (I) A \\ Let p be row addition \\ α \in F, i \neq j \in [1, m] : \forall X \in F^{m \times n} : R_{i} (p (X)) = R_{i} (X) + α R_{j} (X) \\ Let k \neq i \\ R_{k} (p (I) A) = R_{k} (p (I)) A = R_{k} (I) A = e_{k} A = R_{k} (A) = R_{k} (p (A)) \\ R_{i} (p (I) A) = R_{i} (p (I)) A = (R_{i} (I) + α R_{j} (I)) A = e_{i} A + α e_{j} A = \\ = R_{i} (A) + α R_{j} (A) = R_{i} (p (A)) \\ ⟹ p (A) = p (I) A \\ Let p be row switching \\ i \neq j \in [1, m] : \forall X \in F^{m \times n} : R_{i} (p (X)) = R_{j} (X), R_{j} (p (X)) = R_{i} (X) \\ Let i \neq k \neq j \\ R_{k} (p (I) A) = R_{k} (p (I)) A = e_{k} A = R_{k} (A) = R_{k} (p (A)) \\ R_{i} (p (I) A) = R_{i} (p (I)) A = R_{j} (I) A = e_{j} A = R_{j} (A) = R_{i} (p (A)) \\ R_{j} (p (I) A) = R_{j} (p (I)) A = R_{i} (I) A = e_{i} A = R_{i} (A) = R_{j} (p (A)) \\ ⟹ p (A) = p (I) A \end{matrix}

(3) Linear dependence properties

\begin{matrix} Let V be a vector space over F \\ Let S \subseteq V \\ 1. S is a linear dependence \\ 2. \exists v \in S : v \in s p (S ∖ {v}) \\ 3. \exists v \in S : s p (S) = s p (S ∖ {v}) \\ 1 ⟺ 2 ⟺ 3 \\ Proof: \\ Let S = {v_{1}, v_{2}, \dots, v_{n}} \\ Let 1 \\ ⟹ \exists α_{i} \neq 0 : \sum_{i = 1}^{n} α_{i} v_{i} = 0 \\ Let α_{1} \neq 0 (WLOG) ⟹ v_{1} = \sum_{i = 2}^{n} (\frac{- α_{i}}{α_{i - 1}}) v_{i} \\ \forall i \in [2, n] : v_{i} \neq v_{1} ⟹ v_{1} \in s p (S ∖ {v_{1}}) ⟹ 1 ⟹ 2 \\ Let 2 \\ Let v_{1} \in s p (S ∖ {v_{1}}) (WLOG) \\ S ∖ {v_{1}} \subseteq S ⟹ s p (S ∖ {v_{1}}) \subseteq s p (S) \\ Let u \in s p (S) \\ u = \sum_{i = 1}^{n} α_{i} v_{i} = α_{1} v_{1} + \sum_{i = 2}^{n} α_{i} v_{i} \\ v_{1} \in s p (S ∖ {v_{1}}) ⟹ v_{1} = \sum_{j = 2}^{n} β_{j} v_{j} \\ ⟹ u = α_{1} \sum_{j = 2}^{n} β_{j} v_{j} + \sum_{i = 2}^{n} α_{i} v_{i} = \sum_{i = 2}^{n} (α_{1} β_{i} + α_{i}) v_{i} ⟹ u \in s p (S ∖ {v_{1}}) \\ ⟹ s p (S) \subseteq s p (S ∖ {v_{1}}) ⟹ s p (S) = s p (S ∖ {v_{1}}) ⟹ 2 ⟹ 3 \\ Let 3 \\ Let s p (S ∖ {v_{1}}) = s p (S) (WLOG) \\ v_{1} \in S ⟹ v_{1} \in s p (S) ⟹ v_{1} \in s p (S ∖ {v_{1}}) \\ ⟹ v_{1} = \sum_{i = 2}^{n} α_{i} v_{i} ⟹ v_{1} - \sum_{i = 2}^{n} α_{i} v_{i} = 0 \\ ⟹ {1, - α_{2}, - α_{3}, \dots, - α_{n}} is a non-trivial linear combination of S \\ ⟹ S is a linear dependence ⟹ 3 ⟹ 1 \\ ⟹ [1 ⟹ 2 ⟹ 3 ⟹ 1] ⟹ 1 ⟺ 2 ⟺ 3 \end{matrix}

(4) Linear independence properties

\begin{matrix} Let V be a finitely generated vector space \\ Let B \subseteq V \\ 1. s p (B) = V \\ 2. B is a linear independence \\ 3. | B | = d i m (V) \\ If any two properties are true, then the third one is also true \\ Proof: \\ 1 and 2 ⟹ 3 by definition of basis \\ Let 2 and 3 \\ Let s p (B) \neq V ⟹ \exists v \in V : v \notin s p (B) \\ ⟹ B \cup {v} is a linear independence \\ Let C be a basis of V \\ d i m (V) = | C | < | B \cup {v} | \\ But C is a maximal linear independence of V - Contradiction! \\ ⟹ s p (B) = V ⟹ 2 and 3 ⟹ 1 \\ Let 1 and 3 \\ Let C be a basis of V \\ Let B be a linear dependence \\ ⟹ \exists v \in B : s p (B ∖ {v}) = s p (B) = V \\ ⟹ d i m (V) = | C | \leq | B ∖ {v} | = d i m (V) - 1 - Contradiction! \\ ⟹ B is a linear independence ⟹ 1 and 3 ⟹ 2 \end{matrix}

(5) Dimension theorem

\begin{matrix} Let V be a finitely generated vector space \\ Let U, W \subseteq V be vector subspaces of V \\ Then d i m (U + W) = d i m (U) + d i m (W) - d i m (U \cap W) \\ Proof: \\ Let B be a basis of U \cap W, B = {v_{1}, v_{2}, \dots, v_{n}} \\ U \cap W \subseteq U, W \\ ⟹ B \subseteq B_{U} = B \cup {u_{1}, u_{2}, \dots, u_{k}} \\ ⟹ B \subseteq B_{W} = B \cup {w_{1}, w_{2}, \dots, w_{t}} \\ d i m (U \cap W) = n \\ d i m (U) = n + k, d i m (W) = n + t \\ Let \hat{B} = B_{U} \cup B_{W} \\ U + W = s p (B_{U}) + s p (B_{W}) = s p (B_{U} \cup B_{W}) = s p (\hat{B}) \\ Let \sum_{i = 1}^{n} α_{i} v_{i} + \sum_{j = 1}^{k} β_{j} u_{j} + \sum_{r = 1}^{t} γ_{r} w_{r} = 0 \\ ⟹ \underset{\in s p (B_{U}) = U}{\underset{⏟}{\sum_{i = 1}^{n} α_{i} v_{i} + \sum_{j = 1}^{k} β_{j} u_{j}}} = \underset{\in s p (B_{W}) = W}{\underset{⏟}{- \sum_{r = 1}^{t} γ_{r} w_{r}}} \\ ⟹ - \sum_{r = 1}^{t} γ_{r} w_{r} \in U \cap W \\ ⟹ - \sum_{r = 1}^{t} γ_{r} w_{r} = \sum_{i = 1}^{n} δ_{i} v_{i} \\ ⟹ \underset{\in s p (B_{W})}{\underset{⏟}{\sum_{i = 1}^{n} δ_{i} v_{i} + \sum_{r = 1}^{t} γ_{r} w_{r}}} = 0 ⟹ δ_{1} = δ_{2} = \dots = δ_{n} = γ_{1} = γ_{2} = \dots = γ_{t} = 0 \\ ⟹ \sum_{r = 1}^{t} γ_{r} w_{r} = 0 ⟹ \underset{\in s p (B_{U})}{\underset{⏟}{\sum_{i = 1}^{n} α_{i} v_{i} + \sum_{j = 1}^{k} β_{j} u_{j}}} = 0 \\ ⟹ α_{1} = α_{2} = \dots = α_{n} = β_{1} = β_{2} = \dots = β_{k} = 0 \\ ⟹ \hat{B} is a linear independence ⟹ \hat{B} is a basis of U + W \\ ⟹ d i m (U + W) = | \hat{B} | = | B_{U} \cup B_{W} | = | B_{U} | + | B_{W} | - | B_{U} \cap B_{W} | \\ ⟹ d i m (U + W) = d i m (U) + d i m (W) - d i m (U \cap W) \end{matrix}

(-) Defining theorem for linear transformation

\begin{matrix} Let V, U be finitely generated vector spaces over F \\ Let B = {v_{1}, v_{2}, \dots, v_{n}} be a basis of V \\ Let u_{1}, u_{2}, \dots, u_{n} \in U \\ Then \exists! linear transformation T : V \to U : \forall i \in [1, n] : T (v_{i}) = u_{i} \\ Proof: \\ B is a basis of V ⟹ \forall v \in V : \exists {α_{i}}_{i \in [1, n]} \subseteq F : v = \sum_{i = 1}^{n} α_{i} v_{i} \\ Let \forall v \in V : T (v) = \sum_{i = 1}^{n} α_{i} u_{i}, where α_{i} are the linear combination of B for v \\ ⟹ \forall i \in [1, n] : T (v_{i}) = T (1 v_{i}) = 1 u_{i} = u_{i} \\ Let u, v \in V, α \in F \\ u = \sum_{i = 1}^{n} β_{i} v_{i} ⟹ T (u) = \sum_{i = 1}^{n} β_{i} u_{i} \\ v = \sum_{i = 1}^{n} γ_{i} v_{i} ⟹ T (v) = \sum_{i = 1}^{n} γ_{i} u_{i} \\ ⟹ u + α v = \sum_{i = 1}^{n} β_{i} v_{i} + α \sum_{i = 1}^{n} γ_{i} v_{i} = \sum_{i = 1}^{n} (β_{i} + α γ_{i}) v_{i} \\ ⟹ T (u + α v) = \sum_{i = 1}^{n} (β_{i} + α γ_{i}) u_{i} = \sum_{i = 1}^{n} β_{i} u_{i} + α \sum_{i = 1}^{n} γ_{i} u_{i} = T (u) + α T (v) \\ ⟹ T is a linear transformation ⟹ Such linear transformation exists \\ Let T_{2} be another linear transformation such that \forall i \in [1, n] : T_{2} (v_{i}) = u_{i} \\ T (u) = T (\sum_{i = 1}^{n} β_{i} v_{i}) = \sum_{i = 1}^{n} β_{i} u_{i} \\ T_{2} (u) = T_{2} (\sum_{i = 1}^{n} β_{i} v_{i}) = \sum_{i = 1}^{n} β_{i} T_{2} (v_{i}) = \sum_{i = 1}^{n} β_{i} u_{i} = T (u) \\ ⟹ T_{2} = T ⟹ Such linear transformation is unique \end{matrix}

(6) Rank-nullity theorem for linear transformation

\begin{matrix} Let V, U be finitely generated vector spaces \\ Let T : V \to U be a linear transformation \\ Then d i m (V) = d i m (k e r (T)) + d i m (I m (T)) \\ Proof: \\ Let d i m (V) = n \\ k e r (T) = {v \in V | T (v) = 0} \\ I m (T) = {u \in U : \exists v \in V : T (v) = u} \\ k e r (T) \subseteq V ⟹ \exists B_{k} = {u_{1}, u_{2}, \dots, u_{k}} a basis of k e r (T) ⟹ d i m (k e r (T)) = k \\ Let S = {v_{1}, v_{2}, \dots, v_{n - k}} such that B = B_{k} \cup S is a basis of V \\ T (v) = T (\sum_{i = 1}^{k} α_{i} u_{i} + \sum_{i = 1}^{n - k} β_{i} v_{i}) = \sum_{i = 1}^{k} α_{i} T (u_{i}) + \sum_{i = 1}^{n - k} β_{i} T (v_{i}) = \sum_{i = 1}^{n - k} β_{i} T (v_{i}) \in s p (T [S]) \\ ⟹ I m (T) = s p ({\underset{0}{\underset{⏟}{T (u_{1})}}, \underset{0}{\underset{⏟}{T (u_{2})}}, \dots, \underset{0}{\underset{⏟}{T (u_{n})}}, T (v_{1}), T (v_{2}), \dots, T (v_{n - k})}) = \\ = s p ({T (v_{1}), T (v_{2}), \dots, T (v_{n - k})}) \\ Let \sum_{i = 1}^{n - k} α_{i} T (v_{i}) = 0 \\ ⟹ T (\sum_{i = 1}^{n - k} α_{i} v_{i}) = 0 ⟹ \sum_{i = 1}^{n - k} α_{i} v_{i} \in k e r (T) \\ ⟹ \sum_{i = 1}^{n - k} α_{i} v_{i} = \sum_{i = 1}^{k} β_{i} u_{i} ⟹ \sum_{i = 1}^{n - k} α_{i} v_{i} - \sum_{i = 1}^{k} β_{i} u_{i} = 0 \\ B is a linear indepedendence ⟹ α_{1} = α_{2} = \dots = α_{n - k} = - β_{1} = - β_{2} = \dots = - β_{k} = 0 \\ ⟹ {T (v_{1}), T (v_{2}), \dots, T (v_{n - k})} is a linear independence \\ ⟹ {T (v_{1}), T (v_{2}), \dots, T (v_{n - k})} is a basis of I m (T) ⟹ d i m (I m (T)) = n - k \\ ⟹ n = d i m (k e r (T)) + d i m (I m (T)) = d i m (V) \end{matrix}

(7) Invertibility of linear transformation

\begin{matrix} Let T : V \to U be a linear transformation \\ Then T is invertible ⟺ T is bijective \\ Proof: \\ Let T be invertible \\ ⟹ \exists linear transformation T^{- 1} : T T^{- 1} = T^{- 1} T = I \\ T T^{- 1} = I ⟹ T T^{- 1} is surjective ⟹ T is surjective \\ T^{- 1} T = I ⟹ T^{- 1} T is injective ⟹ T is injective \\ ⟹ T is bijective \\ Let T be bijective \\ T is a function ⟹ \exists inverse function T^{- 1} \\ Let u_{1}, u_{2} \in U, α \in F \\ T^{- 1} (u_{1} + α u_{2}) = T^{- 1} (T T^{- 1} (u_{1} + α u_{2})) = T^{- 1} (T T^{- 1} (u_{1}) + α T T^{- 1} (u_{2})) = \\ = T^{- 1} (T (T^{- 1} (u_{1}) + α T^{- 1} (u_{2}))) = T^{- 1} T (T^{- 1} (u_{1}) + α T^{- 1} (u_{2})) = T^{- 1} (u_{1}) + α T^{- 1} (u_{2}) \\ ⟹ T^{- 1} is a linear transformation \end{matrix}

(8) Isomorphic vector spaces

\begin{matrix} Let V, U be finitely generated vector spaces over F \\ V and U are isomorphic ⟺ d i m (V) = d i m (U) \\ Proof: \\ Let d i m (V) = d i m (U) \\ Let B = {v_{1}, v_{2}, \dots, v_{n}} be a basis of V \\ Let C = {u_{1}, u_{2}, \dots, u_{n}} be a basis of W \\ Let T : V \to U, \forall i \in [1, n] : T (v_{i}) = u_{i} \\ {T (v_{1}), T (v_{2}), \dots, T (v_{n})} = C \subseteq I m (T) \\ d i m (s p (C)) = d i m (U) ⟹ d i m (I m (T)) \geq d i m (U) \\ ⟹ d i m (I m (T)) = d i m (U) ⟹ I m (T) = U ⟹ T is surjective \\ Let v \neq \hat{v} \in V \\ \exists {α_{i}}_{i \in [1, n]} \subseteq F : v = \sum_{i = 1}^{n} α_{i} v_{i} \\ \exists {β_{i}}_{i \in [1, n]} \subseteq F : \hat{v} = \sum_{i = 1}^{n} β_{i} {\hat{v}}_{i} \\ v \neq \hat{v} ⟹ \exists j \in [1, n] : α_{j} \neq β_{j} \\ T (v) = T (\sum_{i = 1}^{n} α_{i} v_{i}) = \sum_{m = 1}^{n} α_{i} u_{i} \\ T (\hat{v}) = T (\sum_{i = 1}^{n} β_{i} v_{i}) = \sum_{m = 1}^{n} β_{i} u_{i} \\ C is a linear independence \land a_{j} \neq β_{j} ⟹ \sum_{m = 1}^{n} α_{i} u_{i} \neq \sum_{m = 1}^{n} β_{i} u_{i} \\ ⟹ T (v) \neq T (\hat{v}) ⟹ T is injective \\ ⟹ T is bijective ⟹ T is an isomorphism ⟹ V ≅ U \\ Let V ≅ U \\ ⟹ \exists T : V \to U invertible linear transformation \\ T is invertible ⟹ {\begin{matrix} T is surjective ⟹ I m (T) = U \\ T is injective ⟹ k e r (T) = {0} \end{matrix} \\ d i m (V) = d i m (k e r (T)) + d i m (I m (T)) = 0 + d i m (U) ⟹ d i m (V) = d i m (U) \end{matrix}

(9) Representation matrix for linear transformation

\begin{matrix} Let V, U be finitely generated vector spaces over F \\ Let T : V \to U be a linear transformation \\ Let B, C be bases of V, U \\ Then exists matrix A : \forall v \in V : A [v]_{B} = [T (v)]_{C} \\ A is denoted as [T]_{C}^{B} \\ Proof: \\ Let d i m (V) = n \\ Let d i m (U) = m \\ B = {v_{1}, v_{2}, \dots, v_{n}} \\ C = {u_{1}, u_{2}, \dots, u_{m}} \\ \forall j \in [1, n] : \exists {α_{i j}}_{i \in [1, m]} : T (v_{j}) = u = \sum_{i = 1}^{m} α_{i j} u_{i} \\ Let A \in F^{m \times n} : A_{i j} = α_{i j} \\ Let T_{A} : R^{n} \to R^{m}, T (v) = A v \\ \forall j \in [1, n] : T_{A} ([v_{j}]_{B}) = A [v_{j}]_{B} = A e_{j} = \underset{\in F^{m}}{\underset{⏟}{C_{j} (A)}} = \sum_{i = 1}^{m} α_{i j} e_{i} = \sum_{i = 1}^{m} α_{i j} [u_{i}]_{C} = \\ = {[\sum_{i = 1}^{m} α_{i j} u_{i}]}_{C} = [T (v_{j})]_{C} \\ Let v \in V \\ \exists {β_{k}}_{k \in [1, n]} \subseteq F : v = \sum_{k = 1}^{n} β_{k} v_{k} \\ ⟹ [T (v)]_{C} = {[T (\sum_{k = 1}^{n} β_{k} v_{k})]}_{C} = {[\sum_{k = 1}^{n} β_{k} T (v_{k})]}_{C} = \sum_{k = 1}^{n} β_{k} [T (v_{k})]_{C} = \sum_{k = 1}^{n} β_{k} A [v_{k}]_{B} = \\ = \sum_{k = 1}^{n} A β_{k} [v_{k}]_{B} = A \sum_{k = 1}^{n} [β_{k} v_{k}]_{B} = A {[\sum_{k = 1}^{n} β_{k} v_{k}]}_{B} = A [v]_{B} \\ ⟹ \forall v \in V : A [v]_{B} = [T (v)]_{C} \end{matrix}

(10) Kernel and Image in relation to representation matrix

\begin{matrix} Let V, U be finitely generated vector spaces \\ Let T : V \to U be a linear transformation \\ Let [T]_{D}^{B} be a representation matrix of T \\ Prove: \begin{matrix} [k e r (T)]_{B} = N ([T]_{D}^{B}) \\ [I m (T)]_{D} = C ([T]_{D}^{B}) \end{matrix} \\ Proof: \\ [v]_{B} \in [k e r (T)]_{B} ⟺ v \in k e r (T) ⟺ T (v) = 0 ⟺ [T]_{D}^{B} [v]_{B} = [T (v)]_{D} = [0]_{D} = 0 \\ ⟺ [v]_{B} \in N ([T]_{D}^{B}) ⟹ [k e r (T)]_{B} = N ([T]_{D}^{B}) \\ \forall v \in V : [T]_{D}^{B} [v]_{B} \in C ([T]_{D}^{B}) \\ [u]_{D} \in [I m (T)]_{D} ⟺ u \in I m (T) ⟺ \exists v \in V : T (v) = u ⟺ [T]_{D}^{B} [v]_{B} = [u]_{D} \\ ⟺ [u]_{D} \in C ([T]_{D}^{B}) ⟹ [I m (T)]_{D} = C ([T]_{D}^{B}) \end{matrix}