Linear-1 8

1

\begin{matrix} A = (\begin{matrix} 1 & 1 & 0 \\ 0 & 1 & 1 \\ 3 & 5 & 2 \end{matrix}), B = (\begin{matrix} 1 & 2 & 4 \\ 0 & 3 & 5 \end{matrix}) \end{matrix}

1a

\begin{matrix} Find R (A) \\ Solution: \\ R (A) = s p ({R_{1} (A), R_{2} (A), R_{3} (A)}) = \\ = s p ({(\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}), (\begin{matrix} 3 \\ 5 \\ 2 \end{matrix})}) \\ (\begin{matrix} 3 \\ 5 \\ 2 \end{matrix}) = 3 (\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}) + 2 (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix}) \\ ⟹ R (A) = s p ({(\begin{matrix} 1 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 1 \end{matrix})}) \end{matrix}

1b

\begin{matrix} Find C (A) \\ Solution: \\ C (A) = s p ({C_{1} (A), C_{2} (A), C_{3} (A)}) = \\ = s p ({(\begin{matrix} 1 \\ 0 \\ 3 \end{matrix}), (\begin{matrix} 1 \\ 1 \\ 5 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 2 \end{matrix})}) \\ (\begin{matrix} 1 \\ 1 \\ 5 \end{matrix}) = (\begin{matrix} 1 \\ 0 \\ 3 \end{matrix}) + (\begin{matrix} 0 \\ 1 \\ 2 \end{matrix}) \\ ⟹ C (A) = s p ({(\begin{matrix} 1 \\ 0 \\ 3 \end{matrix}), (\begin{matrix} 0 \\ 1 \\ 2 \end{matrix})}) \end{matrix}

1c

\begin{matrix} Find N (A) \\ Solution: \\ N (A) = {x | A x = 0} \\ (\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 3 & 5 & 2 & 0 \end{array}) \to (\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 2 & 2 & 0 \end{array}) \to (\begin{array}{cccc} 1 & 1 & 0 & 0 \\ 0 & 1 & 1 & 0 \\ 0 & 0 & 0 & 0 \end{array}) \\ ⟹ {\begin{matrix} x = s \\ y = - s \\ z = s \end{matrix} ⟹ N (A) = s p ({(\begin{matrix} 1 \\ - 1 \\ 1 \end{matrix})}) \end{matrix}

1d

\begin{matrix} Find R (B) \\ Solution: \\ R (B) = s p ({R_{1} (B), R_{2} (B)}) \\ ⟹ R (B) = s p ({(\begin{matrix} 1 \\ 2 \\ 4 \end{matrix}), (\begin{matrix} 0 \\ 3 \\ 5 \end{matrix})}) \end{matrix}

1e

\begin{matrix} Find C (B) \\ Solution: \\ C (B) = s p ({C_{1} (B), C_{2} (B), C_{3} (B)}) = \\ = s p ({(\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 2 \\ 3 \end{matrix}), (\begin{matrix} 4 \\ 5 \end{matrix})}) \\ (\begin{matrix} 1 & 0 \\ 2 & 3 \\ 4 & 5 \end{matrix}) \to (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 5 \end{matrix}) \to (\begin{matrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{matrix}) \\ ⟹ C (B) = s p ({(\begin{matrix} 1 \\ 0 \end{matrix}), (\begin{matrix} 2 \\ 3 \end{matrix})}) \end{matrix}

1f

\begin{matrix} Find N (B) \\ Solution: \\ N (B) = {x | B x = 0} \\ (\begin{array}{cccc} 1 & 2 & 4 & 0 \\ 0 & 3 & 5 & 0 \end{array}) \\ ⟹ {\begin{matrix} x = - 2 s \\ y = - 5 s \\ z = 3 s \end{matrix} ⟹ N (B) = s p ({(\begin{matrix} - 2 \\ - 5 \\ 3 \end{matrix})}) \end{matrix}

2

\begin{matrix} A = (\begin{matrix} a & a & - 1 \\ a^{2} & a & a^{2} - a \\ a & a & 2 a + 1 \end{matrix}) \\ Determine r a n k (A) for all values of a \\ Find values of a such that \exists A^{- 1} \\ Solution: \\ (\begin{matrix} a & a & - 1 \\ a^{2} & a & a^{2} - a \\ a & a & 2 a + 1 \end{matrix}) \to (\begin{matrix} a & a & - 1 \\ 0 & a - a^{2} & a^{2} \\ 0 & 0 & 2 a + 2 \end{matrix}) \overset{2 a + 2 \neq 0}{\to} (\begin{matrix} a & a & 0 \\ 0 & a - a^{2} & 0 \\ 0 & 0 & 1 \end{matrix}) \\ \overset{a - a^{2} \neq 0}{\to} (\begin{matrix} a & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) \overset{a \neq 0}{\to} (\begin{matrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟹ r a n k (A) = 3 \\ 1. a = 0 \\ ⟹ A = (\begin{matrix} 0 & 0 & - 1 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) \to (\begin{matrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 1 \end{matrix}) ⟹ a = 0 ⟹ r a n k (A) = 1 \\ 2. a - a^{2} = 0 \\ ⟹ a = a^{2} ⟹ a = 1 \\ ⟹ A = (\begin{matrix} 1 & 1 & - 1 \\ 1 & 1 & 1 \\ 0 & 0 & 3 \end{matrix}) \to (\begin{matrix} 1 & 1 & - 1 \\ 0 & 0 & 1 \\ 0 & 0 & 3 \end{matrix}) \to (\begin{matrix} 1 & 1 & - 1 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \end{matrix}) \\ ⟹ a = 1 ⟹ r a n k (A) = 2 \\ 3. 2 a + 2 = 0 \\ ⟹ a = - 1 ⟹ A = (\begin{matrix} - 1 & - 1 & - 1 \\ 1 & - 1 & 0 \\ - 1 & - 1 & - 1 \end{matrix}) \to (\begin{matrix} - 1 & - 1 & - 1 \\ 0 & - 2 & - 1 \\ 0 & 0 & 0 \end{matrix}) \\ ⟹ a = - 1 ⟹ r a n k (A) = 2 \\ ⟹ {\begin{cases} r a n k (A) = 1 & a = 0 \\ r a n k (A) = 2 & a = \pm 1 \\ r a n k (A) = 3 & otherwise \end{cases} \\ \exists A^{- 1} ⟺ r a n k (A) = 3 ⟺ a \notin {- 1, 0, 1} \end{matrix}

3

\begin{matrix} A \in R^{4 \times 8} \\ r a n k (A) = 4 \\ r a n k (A) = 4 ⟹ C F (A) = (\begin{matrix} 1 & 0 & 0 & 0 & a_{15} & a_{16} & a_{17} & a_{18} \\ 0 & 1 & 0 & 0 & a_{25} & a_{26} & a_{27} & a_{28} \\ 0 & 0 & 1 & 0 & a_{35} & a_{36} & a_{37} & a_{38} \\ 0 & 0 & 0 & 1 & a_{45} & a_{46} & a_{47} & a_{48} \end{matrix}) \end{matrix}

3a

\begin{matrix} Is the set of rows of A a linear dependence or independence? \\ Solution: \\ C F (A) has no zero-rows \\ ⟹ Set of rows of A is a linear independence \end{matrix}

3b

\begin{matrix} Is the set of columns of A a linear dependence or independence? \\ Solution: \\ C_{5} (C F (A)) = a_{15} C_{1} (C F (A)) + a_{25} C_{2} (C F (A)) + a_{35} C_{3} (C F (A)) + a_{45} C_{4} (C F (A)) \\ ⟹ Set of columns of A is a linear dependence \end{matrix}

3c

\begin{matrix} Find d i m (N (A)) \\ Solution: \\ r a n k (A) + d i m (N (A)) = 8 ⟹ d i m (N (A)) = 4 \end{matrix}

4

\begin{matrix} A \in R^{m \times n} \\ m \neq n \\ Prove: at least one of matrices A A^{T}, A^{T} A is not invertible \\ Proof: \\ Let m < n \\ ⟹ r a n k (A) = d i m (R (A)) \leq m < n \\ A^{T} A \in R^{n \times n} \\ r a n k (A^{T} A) \leq r a n k (A) < n ⟹ r a n k (A^{T} A) \neq n ⟹ ∄ (A^{T} A)^{- 1} \\ Let m > n \\ ⟹ r a n k (A) = d i m (C (A)) \leq n < m \\ A A^{T} \in R^{m \times m} \\ r a n k (A A^{T}) \leq r a n k (A) < m ⟹ r a n k (A A^{T}) \neq m ⟹ ∄ (A A^{T})^{- 1} \end{matrix}

5

\begin{matrix} A \in R^{n \times n} \\ ∄ A^{- 1} \\ B = {u_{1}, u_{2}, \dots, u_{n}} is a basis of R^{n} \\ Prove: {A u_{1}, A u_{2}, \dots, A u_{n}} is a linear dependence \\ Proof: \\ Let U = (\begin{matrix} u_{1} & u_{2} & \dots & u_{n} \end{matrix}) \in R^{n \times n} \\ Let M = A U \\ ⟹ M = (\begin{matrix} A u_{1} & A u_{2} & \dots & A u_{n} \end{matrix}) \\ r a n k (M) = r a n k (A U) \leq r a n k (A) < n \\ ⟹ n > r a n k (M) = d i m (C (M)) = d i m (s p ({A u_{1}, A u_{2}, \dots, A u_{n}})) \\ ⟹ {A u_{1}, A u_{2}, \dots, A u_{n}} is a linear dependence \end{matrix}

6a

\begin{matrix} A, B \in F^{m \times n} \\ Prove: r a n k (A + B) \leq r a n k (A) + r a n k (B) \\ Proof: \\ A + B = (\begin{matrix} C_{1} (A + B) & C_{2} (A + B) & \dots & C_{n} (A + B) \end{matrix}) \\ Let \forall i \in [1, n] : C_{i}^{A} = C_{i} (A), C_{i}^{B} = C_{i} (B) \\ Note that \forall i \in [1, n] : C_{i} (A + B) = C_{i}^{A} + C_{i}^{B} \\ ⟹ {C_{1} (A + B), \dots, C_{n} (A + B)} \subseteq s p ({C_{1}^{A}, C_{2}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, C_{2}^{B}, \dots, C_{n}^{B}}) \\ C (A + B) = s p ({C_{1} (A + B), C_{2} (A + B), \dots, C_{n} (A + B)}) \\ ⟹ C (A + B) \subseteq s p ({C_{1}^{A}, C_{2}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, C_{2}^{B}, \dots, C_{n}^{B}}) \\ ⟹ r a n k (A + B) = d i m (C (A + B)) \leq d i m (s p ({C_{1}^{A}, C_{2}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, C_{2}^{B}, \dots, C_{n}^{B}})) \\ Let us now prove that \\ d i m (s p ({C_{1}^{A}, C_{2}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, C_{2}^{B}, \dots, C_{n}^{B}})) \leq r a n k (A) + r a n k (B) \\ Let r a n k (A) = k \\ ⟹ \exists {C_{1}^{A}, \dots, C_{k}^{A}} that is a linear independence and \\ \forall i \in [1, n] : C_{i}^{A} \in s p ({C_{1}^{A}, \dots, C_{k}^{A}}) \\ Let r a n k (B) = l \\ ⟹ \exists {C_{1}^{B}, \dots, C_{l}^{B}} that is a linear independence and \\ \forall i \in [1, n] : C_{i}^{B} \in s p ({C_{1}^{B}, \dots, C_{l}^{B}}) \\ {\begin{matrix} {C_{1}^{A}, \dots, C_{n}^{A}} \subseteq s p ({C_{1}^{A}, \dots, C_{k}^{A}}) \\ {C_{1}^{B}, \dots, C_{n}^{B}} \subseteq s p ({C_{1}^{B}, \dots, C_{l}^{B}}) \end{matrix} ⟹ \\ ⟹ {C_{1}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, \dots, C_{n}^{B}} \subseteq s p ({C_{1}^{A}, \dots, C_{k}^{A}, C_{1}^{B}, \dots, C_{l}^{B}}) \\ ⟹ s p ({C_{1}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, \dots, C_{n}^{B}}) \subseteq s p ({C_{1}^{A}, \dots, C_{k}^{A}, C_{1}^{B}, \dots, C_{l}^{B}}) \\ ⟹ d i m (s p ({C_{1}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, \dots, C_{n}^{B}})) \leq \underset{\leq k + l = r a n k (A) + r a n k (B)}{\underset{⏟}{d i m (s p ({C_{1}^{A}, \dots, C_{k}^{A}, C_{1}^{A}, \dots, C_{l}^{B}}))}} \\ ⟹ d i m (s p ({C_{1}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, \dots, C_{n}^{B}})) \leq r a n k (A) + r a n k (B) \\ ⟹ r a n k (A + B) \leq d i m (s p ({C_{1}^{A}, \dots, C_{n}^{A}, C_{1}^{B}, \dots, C_{n}^{B}})) \leq r a n k (A) + r a n k (B) \\ ⟹ r a n k (A + B) \leq r a n k (A) + r a n k (B) \end{matrix}

6b

\begin{matrix} A, B \in F^{m \times n} \\ Prove: d i m (N (A + B)) \geq d i m (N (A)) + d i m (N (B)) - n \\ Proof: \\ r a n k (A) + d i m (N (A)) = n \\ r a n k (A + B) \leq r a n k (A) + r a n k (B) ⟹ n - r a n k (A + B) \geq n - r a n k (A) - r a n k (B) \\ n - r a n k (A + B) = d i m (N (A + B)) \\ n - r a n k (A) - r a n k (B) = d i m (N (A)) - r a n k (B) = d i m (N (A)) + d i m (N (B)) - n \\ ⟹ d i m (N (A + B)) \geq d i m (N (A)) + d i m (N (B)) - n \end{matrix}

7

\begin{matrix} A \in F^{m \times n} \\ r a n k (A) = k \\ Prove: A can be written as a sum of k matrices of rank 1 \\ Proof: \\ Let C F_{i} = (\begin{matrix} 0 \\ ⋮ \\ 0 \\ R_{i} (C F (A)) \\ 0 \\ ⋮ \\ 0 \end{matrix}) \\ \forall i \in [1, m] : r a n k (C F_{i}) = 1 \\ r a n k (A) = k ⟹ C F (A) has exactly k non-zero rows \\ ⟹ C F (A) can be written as: \\ C F (A) = \sum_{i = 1}^{m} C F_{i} = \sum_{i = 1}^{k} C F_{i} + \sum_{i = k + 1}^{m} 0 \\ C F (A) = P_{1} P_{2} \dots P_{l} A, where P_{i} is an elementary matrix \\ Elementary matrices are invertible \\ ⟹ P_{l}^{- 1} P_{l - 1}^{- 1} \dots P_{1}^{- 1} C F (A) = A \\ ⟹ A = P_{l}^{- 1} P_{l - 1}^{- 1} \dots P_{1}^{- 1} \sum_{i = 1}^{k} C F_{i} = \\ = P_{l}^{- 1} P_{l - 1}^{- 1} \dots P_{1}^{- 1} C F_{1} + P_{l}^{- 1} P_{l - 1}^{- 1} \dots P_{1}^{- 1} C F_{2} + \dots + P_{l}^{- 1} P_{l - 1}^{- 1} \dots P_{1}^{- 1} C F_{k} \\ Multiplication by an elementary matrix does not affect rank \\ ⟹ \forall i \in [1, k] : r a n k (P_{l}^{- 1} P_{l - 1}^{- 1} \dots P_{1}^{- 1}) = r a n k (C F_{i}) = 1 \\ ⟹ A can be written as a sum of k matrices of rank 1 \end{matrix}