Linear-1 8

Dimension theorem #theorem

\begin{matrix} Let V be a finitely generated vector space \\ U, W \subseteq V - 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 \\ ⟹ It is possible to increase B to the basis of U and W \\ Basis of U : B_{U} = {v_{1}, v_{2}, \dots, v_{n}, u_{n + 1}, \dots, u_{n + k}} \\ Basis of W : B_{W} = {v_{1}, v_{2}, \dots, v_{n}, w_{n + 1}, \dots, w_{n + t}} \\ d i m (U \cap W) = n \\ d i m (U) = n + k \\ d i m (W) = n + t \\ \tilde{B} = {v_{1}, \dots, v_{n}, u_{n + 1}, \dots, u_{n + k}, w_{n + 1}, \dots, w_{n + t}} \\ U + W = s p (B_{U}) + s p (B_{W}) = s p (B_{U} \cup B_{W}) = s p (\tilde{B}) \\ ⟹ s p (\tilde{B}) = U + W \\ (α_{1}, \dots, α_{n}, β_{1}, \dots, β_{k}, γ_{1}, \dots, γ_{t}) \cdot (v_{1}, \dots, v_{n}, u_{n + 1}, \dots, u_{n + k}, w_{n + 1}, \dots, w_{n + t})^{T} = 0 \\ \underset{Linear combination of B_{U}}{\underset{⏟}{(α_{1}, \dots, α_{n}, β_{1}, \dots, β_{k}) \cdot (v_{1}, \dots, v_{n}, u_{n + 1}, \dots, u_{n + k})^{T}}} = - (γ_{1}, \dots, γ_{t}) \cdot (w_{n + 1}, \dots, w_{n + t})^{T} \\ - (γ_{1}, \dots, γ_{t}) \cdot (w_{n + 1}, \dots, w_{n + t})^{T} \in s p (B_{U}) = U \\ ⟹ - (γ_{1}, \dots, γ_{t}) \cdot (w_{n + 1}, \dots, w_{n + t})^{T} \in U \cap W \\ ⟹ - (γ_{1}, \dots, γ_{t}) \cdot (w_{n + 1}, \dots, w_{n + t})^{T} = (δ_{1}, \dots, δ_{n}) \cdot (v_{1}, \dots, v_{n})^{T} \\ ⟹ (α_{1}, \dots, α_{n}, β_{1}, \dots, β_{k}) \cdot (v_{1}, \dots, v_{n}, u_{n + 1}, \dots, u_{n + k})^{T} = (δ_{1}, \dots, δ_{n}) \cdot (v_{1}, \dots, v_{n})^{T} \\ ⟹ \underset{Linear combination of B_{U}}{\underset{⏟}{(α_{1} - d_{1}, \dots, α_{n} - δ_{n}, β_{1}, \dots, β_{k}) \cdot (v_{1}, \dots, v_{n}, u_{n + 1}, \dots, u_{n + k})^{T}}} = 0 \\ ? ? ? \end{matrix}

Uniqueness of linear combination #lemma

\begin{matrix} Let V be a finitely generated vector space over F \\ B = {v_{1}, \dots, v_{n}} - basis of V \\ ⟹ \forall v \in V : \exists! (α_{1}, \dots, α_{n}) \in F, (v_{1}, \dots, v_{n}) \in B : \sum_{i = 1}^{n} α_{i} v_{i} = v \\ Proof: \\ s p (B) = V \\ Let v \in s p (B) \\ Let v = α_{1} v_{1} + \dots + α_{n} v_{n} \\ Let v = β_{1} v_{1} + \dots + β_{n} v_{n} \\ \sum_{i = 1}^{n} α_{i} v_{i} = \sum_{i = 1}^{n} β_{i} v_{i} \\ \sum_{i = 1}^{n} (α_{i} - β_{i}) v_{i} = 0 \\ B is a linear independence ⟹ \forall i \in [1, n] : α_{i} - β_{i} = 0 ⟹ α_{i} = β_{i} \\ ⟹ \exists! (α_{1}, \dots, α_{n}) \in F, (v_{1}, \dots, v_{n}) \in B : \sum_{i = 1}^{n} α_{i} v_{i} = v \end{matrix}

Matrix spaces #definition

\begin{matrix} Let A \in F^{m \times n} \\ Matrix columns space C (A) = s p ({C_{1} (A), \dots, C_{n} (A)}) \\ Matrix rows space R (A) = s p ({R_{1} (A), \dots, R_{m} (A)}) \\ Matrix zero space N (A) = {v \in F^{n} | A v = 0} \end{matrix}

Example

\begin{matrix} A = (\begin{matrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}) \\ C (A) = s p ({(\begin{matrix} 1 \\ 4 \end{matrix}), (\begin{matrix} 2 \\ 5 \end{matrix}), (\begin{matrix} 3 \\ 6 \end{matrix})}) \\ (\begin{array}{cccc} 1 & 2 & 3 & 0 \\ 4 & 5 & 6 & 0 \end{array}) \to (\begin{array}{cccc} 1 & 2 & 3 & 0 \\ 0 & 3 & 6 & 0 \end{array}) ⟹ {(\begin{matrix} 1 \\ 4 \end{matrix}), (\begin{matrix} 2 \\ 5 \end{matrix})} is a basis of C (A) \\ R (A) = s p ({(\begin{matrix} 1 \\ 2 \\ 3 \end{matrix}), (\begin{matrix} 4 \\ 5 \\ 6 \end{matrix})}) \\ (\begin{array}{ccc} 1 & 4 & 0 \\ 2 & 5 & 0 \\ 3 & 6 & 0 \end{array}) \to (\begin{array}{ccc} 1 & 4 & 0 \\ 0 & 3 & 0 \\ 0 & 0 & 0 \end{array}) ⟹ d i m (R (A)) = 2 \\ (\begin{array}{cccc} 1 & 2 & 3 & 0 \\ 4 & 5 & 6 & 0 \end{array}) \to (\begin{array}{cccc} 1 & 2 & 3 & 0 \\ 0 & 1 & 2 & 0 \end{array}) ⟹ A v = 0 ⟺ v = (\begin{matrix} t \\ - 2 t \\ t \end{matrix}) \\ ⟹ N (A) = {(\begin{matrix} t \\ - 2 t \\ t \end{matrix}) | t \in R} = s p ({(\begin{matrix} 1 \\ - 2 \\ 1 \end{matrix})}) \end{matrix}

Matrix multiplication narrows its spaces #lemma

\displaylines{ A \in \mathbb{F}^{m \times n}, B \in \mathbb{F}^{n \times m} \\ C(AB) \subseteq C(A) \\ R(AB) \subseteq R(B) \\ \\ \text{Proof:} \\ C_{i}(AB) = \sum_{i=1}^{k} \alpha_{i}C_{i}(A) \implies C_{i}(AB) \in C(A) \\ \forall i \in [1, n]: C_{i}(AB) \in C(A) \implies C(AB) = sp(\Set{ C_{i}(AB) }) \subseteq C(A) \\ \text{Proof for R(AB) is TODO by yourself} \\ } $$--- ## Column space and equations system#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{n \times m}, b \in \mathbb{F}^{n} \
\text{Then } \exists x \in \mathbb{F}^{m}: Ax = b \iff b \in C(A) \
\
\text{Proof:} \
\exists x \in \mathbb{F}^{m}: Ax = b \iff \exists x \in \mathbb{F}^{m}: \sum_{i=1}^{m} \alpha_{i}C_{i}(A) = b \iff b \in C(A) \
}

--- ## Column space and row space dimensions#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{m \times n} \
\text{Then } dim(C(A)) = dim(R(A)) \
\
\text{Proof:} \
\dots
}

--- ## Matrix rank#definition

\displaylines{
r(A) = rank(A) = dim(C(A)) = dim(R(A)) \
}

--- ## Matrix multiplication reduces rank#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{m \times n}, B \in \mathbb{F}^{n \times k} \
rank(AB) \leq rank(A), rank(AB) \leq rank(B) \
\
\text{Proof:} \
C(AB) \subseteq C(A) \implies sp(C(AB)) \subseteq sp(C(A)) \implies dim(C(AB)) \leq dim(C(A)) \
R(AB) \subseteq R(B) \implies sp(R(AB)) \subseteq sp(R(A)) \implies dim(R(AB)) \leq dim(R(A)) \
}

--- ## Invertible matrix multiplication does not reduce rank#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{m \times n} \
B \in \mathbb{F}^{n \times n}, \exists B^{-1} \implies rank(AB) = rank(A) \
B \in \mathbb{F}^{m \times m}, \exists B^{-1} \implies rank(BA) = rank(B) \
\
\text{Proof:} \
rank(A) = rank(ABB^{-1}) \leq rank(AB) \implies rank(AB) = rank(A) \
rank(B) = rank(B^{-1}BA) \leq rank(BA) \implies rank(BA) = rank(B) \
}

--- ## Row-equality is equivalent to rank equality#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{m \times n} \
\text{Let } B \text{ row-equal to } A \
\text{Then } rank(A) = rank(B) \
\
\text{Proof:} \
B = \prod_{i=1}^{k} E_{i} A \
\forall i \in [1, k]: \exists E_{i}^{-1} \implies rank(A) = rank(\prod_{i=1}^{k} E_{i} A) = rank(B) \
\implies rank(A) = rank(CF(A)) \
}

--- ## Invertible matrix is full-ranked#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{n \times n} \
\exists A^{-1} \iff rank(A) = n \
\
\text{Proof:} \
\exists A^{-1} \implies CF(A) = I \
rank(A) = rank(CF(A)) \implies rank(A) = rank(CF(A)) = rank(I) = n \
\implies rank(A) = n \
rank(A) = n \implies rank(CF(A)) = n \implies CF(A) = I \
\implies \exists A^{-1} \
}

--- ## Dimension theorem for matrices#lemma

\displaylines{
\text{Let } A \in \mathbb{F}^{m \times n} \
rank(A) + dim(N(A)) = n \
}

- - -