Linear-1 3

1a

\begin{matrix} A \in Z_{7}^{4 \times 4} \\ (\begin{array}{cc} A & I \end{array}) = (\begin{array}{cccccccc} 1 & 0 & 2 & 3 & 1 & 0 & 0 & 0 \\ 6 & 4 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 5 & 5 & 2 & 0 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array}) \overset{R_{2} = R_{2} + R_{1}}{\underset{R_{3} = R_{3} + (- R_{1})}{\to}} (\begin{array}{cccccccc} 1 & 0 & 2 & 3 & 1 & 0 & 0 & 0 \\ 0 & 4 & 2 & 4 & 1 & 1 & 0 & 0 \\ 0 & 5 & 3 & 6 & 6 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array}) \\ \overset{R_{3} = R_{3} + 4 R_{2}}{\underset{R_{2} = 2 R_{2} + (- R_{3})}{\to}} (\begin{array}{cccccccc} 1 & 0 & 2 & 3 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 6 & 5 & 6 & 0 \\ 0 & 0 & 4 & 1 & 3 & 4 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 0 & 1 \end{array}) \overset{R_{3} = 2 R_{3}}{\underset{R_{4} = R_{3} - R_{4}}{\to}} (\begin{array}{cccccccc} 1 & 0 & 2 & 3 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 6 & 5 & 6 & 0 \\ 0 & 0 & 1 & 2 & 6 & 1 & 2 & 0 \\ 0 & 0 & 0 & 1 & 6 & 1 & 2 & 6 \end{array}) \\ \overset{R_{3} = R_{3} + 2 (- R_{4})}{\underset{R_{1} = R_{1} + 3 (- R_{4})}{\to}} (\begin{array}{cccccccc} 1 & 0 & 2 & 0 & 4 & 4 & 1 & 3 \\ 0 & 1 & 0 & 0 & 6 & 5 & 6 & 0 \\ 0 & 0 & 1 & 0 & 1 & 6 & 5 & 2 \\ 0 & 0 & 0 & 1 & 6 & 1 & 2 & 6 \end{array}) \overset{R_{1} = R_{1} + 2 (- R_{3})}{\to} (\begin{array}{cccccccc} 1 & 0 & 0 & 0 & 2 & 6 & 5 & 6 \\ 0 & 1 & 0 & 0 & 6 & 5 & 6 & 0 \\ 0 & 0 & 1 & 0 & 1 & 6 & 5 & 2 \\ 0 & 0 & 0 & 1 & 6 & 1 & 2 & 6 \end{array}) = \\ = (\begin{array}{cc} I & A^{- 1} \end{array}) ⟹ A^{- 1} = (\begin{matrix} 2 & 6 & 5 & 6 \\ 6 & 5 & 6 & 0 \\ 1 & 6 & 5 & 2 \\ 6 & 1 & 2 & 6 \end{matrix}) \end{matrix}

1b

\begin{matrix} A \in R^{3 \times 3} \\ (\begin{array}{cc} A & I \end{array}) = (\begin{array}{cccccc} 1 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 0 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 \end{array}) \overset{R_{2} = R_{2} - R_{1}}{\underset{R_{3} = \frac{1}{2} (R_{3} - R_{2})}{\to}} (\begin{array}{cccccc} 1 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & - 1 & - 1 & 1 & 0 \\ 0 & 0 & 1 & \frac{1}{2} & \frac{- 1}{2} & \frac{1}{2} \end{array}) \\ \overset{R_{2} = R_{2} + R_{3}}{\underset{R_{1} = R_{1} - R_{3}}{\to}} (\begin{array}{cccccc} 1 & 0 & 0 & \frac{1}{2} & \frac{1}{2} & \frac{- 1}{2} \\ 0 & 1 & 0 & \frac{- 1}{2} & \frac{1}{2} & \frac{1}{2} \\ 0 & 0 & 1 & \frac{1}{2} & \frac{- 1}{2} & \frac{1}{2} \end{array}) = \\ = (\begin{array}{cc} I & A^{- 1} \end{array}) ⟹ A^{- 1} = \frac{1}{2} (\begin{matrix} 1 & 1 & - 1 \\ - 1 & 1 & 1 \\ 1 & - 1 & 1 \end{matrix}) \end{matrix}

2

\begin{matrix} A, B \in F^{n \times n} \\ A_{i j} = {\begin{cases} 1 & i \geq j \\ 0 & otherwise \end{cases} \\ B_{i j} = {\begin{cases} 1 & i = j \\ - 1 & i = j + 1 \\ 0 & otherwise \end{cases} \\ Prove that A and B are inverse matrices of each other \\ Proof: \\ (A B)_{i j} = \sum_{k = 1}^{n} A_{i k} B_{k j} = \sum_{k = 1}^{i} \underset{k \leq i ⟹ 1}{\underset{⏟}{A_{i k}}} B_{k j} + \sum_{k = i + 1}^{n} \underset{k > i ⟹ 0}{\underset{⏟}{A_{i k}}} B_{k j} = \sum_{k = 1}^{i} B_{k j} \\ 1. i = j ⟹ (A B)_{i j} = \sum_{k = 1}^{j} B_{k j} = \sum_{k = 1}^{j - 1} \underset{k < j ⟹ 0}{\underset{⏟}{B_{k j}}} + B_{j j} = 0 + 1 = 1 \\ 2. i > j ⟹ (A B)_{i j} = \underset{1}{\underset{⏟}{\sum_{k = 1}^{j} B_{k j}}} + \sum_{k = j + 1}^{i} B_{k j} = 1 + B_{j + 1, j} + \sum_{k = j + 2}^{i} \underset{k > j + 1 ⟹ 0}{\underset{⏟}{B_{k j}}} = \\ = 1 + - 1 + 0 = 0 \\ 3. i < j ⟹ (A B)_{i j} = \sum_{k = 1}^{i} \underset{k < j ⟹ 0}{\underset{⏟}{B_{k j}}} = 0 \\ ⟹ (A B)_{i j} = {\begin{cases} 1 & i = j \\ 0 & otherwise \end{cases} ⟹ A B = I ⟹ B = A^{- 1}, A = B^{- 1} \end{matrix}

A \in F^{n \times n}

3a

\begin{matrix} Prove or disprove: If A is an elementary matrix, then A^{2} = I \\ Disproof: \\ Let A = (\begin{matrix} 1 & 0 \\ 0 & α \end{matrix}) \\ This matrix is an elementary row-multiplication matrix \\ A^{2} = A A = (\begin{matrix} 1 & 0 \\ 0 & α \end{matrix}) \times (\begin{matrix} 1 & 0 \\ 0 & α \end{matrix}) = (\begin{matrix} 1 & 0 \\ 0 & α^{2} \end{matrix}) \\ ⟹ A^{2} \neq I \end{matrix}

3b

\begin{matrix} Prove or disprove: A^{2} = I ⟹ A is an elementary matrix \\ Disproof: \\ A = (\begin{matrix} 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 \end{matrix}) \\ A is not an elementary matrix, as it swaps two pairs of rows, \\ but A^{2} = I ⟹ Disproved \end{matrix}

3c

\begin{matrix} Prove or disprove: ∄ A^{- 1} ⟹ \exists B \neq 0 : A B = 0 \\ Proof: \\ ∄ A^{- 1} ⟹ System of equations A x = 0 \\ Has an all-zero row in the canonical form \\ ⟹ \exists x \neq 0 : A x = 0 \\ ⟹ Exists a non-zero matrix B comprised of columns equal to x \\ ⟹ \exists x \neq 0 : \exists B = x \cdot (1_{1 \times n})^{T} \neq 0 : A x = 0 ⟹ A B = 0 \end{matrix}

3d

\begin{matrix} Prove or disprove: B \neq 0 \land A B = 0 ⟹ ∄ A^{- 1} \\ Proof: \\ Let \exists A^{- 1} \\ Then B = I B = (A^{- 1} A) B = A^{- 1} (A B) = A^{- 1} \cdot 0 = 0 \\ B \neq 0 \land B = 0 - Contradiction! \\ ⟹ ∄ A^{- 1} \end{matrix}

\begin{matrix} A = (\begin{matrix} a_{11} & . & . & . & a_{1 n} \\ . & . & . \\ . & . & . \\ . & . & . \\ a_{n 1} & . & . & . & a_{n n} \end{matrix}) \in F^{n \times n} \\ B = (\begin{matrix} a_{11} & . & . & . & a_{1 n} & 0 \\ . & . & . & . \\ . & . & . & . \\ . & . & . & . \\ a_{n 1} & . & . & . & a_{n n} & 0 \\ b_{1} & . & . & . & b_{n} & b_{n + 1} \end{matrix}) \in F^{n + 1 \times n + 1} \end{matrix}

4a

\begin{matrix} Prove: ∄ A^{- 1} ⟹ ∄ B^{- 1} \\ Proof: \\ Let E_{i} be an elementary matrix \in F^{n \times n} \\ Let E = (\prod_{i = 1}^{k} E_{i}) \\ Let A_{1} = E A \\ ∄ A^{- 1} ⟹ \exists E : \exists A_{1}, that has at least one all-zero row R \\ Let E_{i}^{'} = (\begin{matrix} E_{i} & 0_{n \times 1} \\ 0_{1 \times n} & 1 \end{matrix}) \in F^{n + 1 \times n + 1} \\ Note that E_{i}^{'} is an elementray matrix \\ Let B_{1} = (\prod_{i = 1}^{k} E_{i}^{'}) \cdot B = (\begin{matrix} A_{1} & 0_{n \times 1} \\ {b_{1}, \dots, b_{n}} & b_{n + 1} \end{matrix}) \\ B_{1} is obtained by applying elementary transformations to B \\ and has at least one all-zero row (\begin{matrix} R & 0 \end{matrix}) ⟹ ∄ B^{- 1} \end{matrix}

4b

\begin{matrix} Find sufficient and necessary conditions for {b_{1}, \dots, b_{n + 1}} such that: \\ \exists A^{- 1} ⟺ \exists B^{- 1} \\ 1. \exists B^{- 1} ⟹ \exists A^{- 1} \\ Let \exists B^{- 1} \\ (\exists B^{- 1} ⟹ \exists A^{- 1}) \equiv (∄ B^{- 1} \lor \exists A^{- 1}) \equiv (False \lor \exists A^{- 1}) \equiv \exists A^{- 1} \\ ⟹ \exists B^{- 1} ⟹ \exists A^{- 1} \\ 2. \exists A^{- 1} ⟹ B^{- 1} \\ Let \exists A^{- 1} \\ Let E_{i} be an elementary matrix \in F^{n \times n} \\ Then \exists E = (\prod_{i = 1}^{k} E_{i}) : E A = I \\ Let E_{i}^{'} = (\begin{matrix} E_{i} & 0_{n \times 1} \\ 0_{1 \times n} & 1 \end{matrix}) \in F^{n + 1 \times n + 1} \\ Note that E_{i}^{'} is an elementray matrix \\ Then \exists E^{'} = (\prod_{i = 1}^{k} E_{i}^{'}) : E^{'} B = (\begin{matrix} I_{n} & 0_{n \times 1} \\ {b_{1}, \dots, b_{n}} & b_{n + 1} \end{matrix}) \\ Let us apply some more elementary transformations: \\ \forall i \in [1, n] : R_{n + 1} = R_{n + 1} - b_{i} \cdot R_{i} \\ After applying these elementary transformations the resulting matrix will look like this: \\ B_{1} = (\begin{matrix} I_{n} & 0_{n \times 1} \\ 0_{1 \times n} & b_{n + 1} \end{matrix}) \\ b_{n + 1} \neq 0 ⟺ \exists B_{1}^{- 1} ⟺ \exists B^{- 1} \\ ⟹ b_{n + 1} \neq 0 ⟺ \exists B^{- 1} \\ 1. and 2. ⟹ b_{n + 1} \neq 0 ⟺ (\exists A^{- 1} ⟺ \exists B^{- 1}) \end{matrix}

5a

\begin{matrix} Prove or disprove: A, B are elementary row-addition matrices \\ ⟹ \exists A, B \in R^{n \times n} : ∄ (A + B)^{- 1} \\ Proof: \\ Let A = (\begin{matrix} [\begin{matrix} 1 & 0 \\ 2 & 1 \end{matrix}] & 0_{2 \times (n - 2)} \\ 0_{(n - 2) \times 2} & I_{n - 2} \end{matrix}), B = (\begin{matrix} [\begin{matrix} 1 & 2 \\ 0 & 1 \end{matrix}] & 0_{2 \times (n - 2)} \\ 0_{2 \times (n - 2)} & I_{n - 2} \end{matrix}) \\ A : R_{2} = R_{2} + 2 R_{1}, B : R_{1} = R_{1} + 2 R_{2} \\ A + B = (\begin{matrix} [\begin{matrix} 2 & 2 \\ 2 & 2 \end{matrix}] & 0_{2 \times (n - 2)} \\ 0_{2 \times (n - 2)} & 2 I_{n - 2} \end{matrix}) \\ (A + B)_{1} = (A + B)_{2} ⟹ ∄ (A + B)^{- 1} \end{matrix}

5b

\begin{matrix} Prove or disprove: A, B are elementary row-switching matrices \\ ⟹ \exists A, B \in R^{n \times n} : ∄ (A + B)^{- 1} \\ Proof: \\ If I can be considered an elementary row-switching matrix, \\ then the statement is correct for all n \geq 1 \\ Otherwise it is only correct for n \geq 4 \\ Let A = (\begin{matrix} [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] & 0_{2 \times (n - 2)} \\ 0_{(n - 2) \times 2} & I_{n - 2} \end{matrix}), B = (\begin{matrix} I_{n - 2} & 0_{2 \times 2} \\ 0_{2 \times 2} & [\begin{matrix} 0 & 1 \\ 1 & 0 \end{matrix}] \end{matrix}) \\ A : R_{1} \leftrightarrow R_{2}, B : R_{n - 1} \leftrightarrow R_{n} \\ A + B = (\begin{matrix} [\begin{matrix} 1 & 1 \\ 1 & 1 \end{matrix}] & 0_{2 \times (n - 2)} \\ 0_{(n - 2) \times 2} & B_{n - 2}^{'} \end{matrix}) \\ (A + B)_{1} = (A + B)_{2} ⟹ ∄ (A + B)^{- 1} \end{matrix}

5c

\begin{matrix} Prove or disprove: A B = B A, A^{3} + 3 A^{2} B + 3 A B^{2} + B^{3} = I \\ ⟹ \exists A, B \in R^{n \times n} : ∄ (A + B)^{- 1} \\ Disproof: \\ A B = B A ⟹ (A + B)^{3} = (A A + A B + B A + B B) (A + B) = \\ A A A + A B A + B A A + B B A + A A B + A B B + B A B + B B B = \\ = A^{3} + 3 A^{2} B + 3 A B^{2} + B^{3} = I \\ ⟹ (A + B) \underset{(A + B)^{- 1}}{\underset{⏟}{(A + B)^{2}}} = I ⟹ \exists (A + B)^{- 1} \end{matrix}

6a

\begin{matrix} Given: A \in R^{4 \times 5} \\ (\prod_{i = 1}^{n} E_{i}) \cdot A = (\begin{matrix} a_{11} \\ 0 & a_{22} \\ 0 & 0 & a_{33} \\ 0 & 0 & 0 & a_{44} & a_{45} \end{matrix}), where E_{i} is an elementary matrix \\ Prove: \forall b \in R^{4 \times 1} system of equations A x = b has infinitely many solutions \\ Proof: \\ A x = b ⟺ (\begin{matrix} a_{11} \\ 0 & a_{22} \\ 0 & 0 & a_{33} \\ 0 & 0 & 0 & a_{44} & a_{45} \end{matrix}) \cdot (\begin{matrix} x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ x_{5} \end{matrix}) = (\begin{matrix} b_{1}^{'} \\ b_{2}^{'} \\ b_{3}^{'} \\ b_{4}^{'} \end{matrix}) \\ ⟺ {\begin{matrix} a_{11} x_{1} + a_{12} x_{2} + a_{13} x_{3} + & a_{14} x_{4} + & a_{15} x_{5} & = b_{1}^{'} \\ a_{22} x_{2} + a_{23} x_{3} + & a_{24} x_{4} + & a_{25} x_{5} & = b_{2}^{'} \\ a_{33} x_{3} + & a_{34} x_{4} + & a_{35} x_{5} & = b_{3}^{'} \\ a_{44} x_{4} + & a_{45} x_{5} & = b_{4}^{'} \end{matrix} \\ ⟹ {\begin{matrix} x_{5} = t \\ x_{4} = α_{1} t \\ x_{3} = α_{2} t \\ x_{2} = α_{3} t \\ x_{1} = α_{4} t \end{matrix} ⟹ System of equations has infinitely many solutions \end{matrix}

6b

\begin{matrix} In addition to what is given in 6a, \\ A \cdot (\begin{matrix} 1 & 2 & 0 \\ 0 & - 3 & - 4 \\ - 2 & 1 & 4 \\ - 1 & 0 & 2 \\ 1 & 0 & 1 \end{matrix}) = (\begin{matrix} 0 & - 4 & - 9 \\ 0 & 4 & 21 \\ 0 & - 7 & - 13 \\ 0 & 6 & - 6 \end{matrix}) \\ Find a set of solutions for the system of equations A x = (\begin{matrix} - 4 \\ 4 \\ - 7 \\ 6 \end{matrix}) \\ Solution: \\ A \cdot (\begin{matrix} 1 & 2 & 0 \\ 0 & - 3 & - 4 \\ - 2 & 1 & 4 \\ - 1 & 0 & 2 \\ 1 & 0 & 1 \end{matrix}) = (\begin{matrix} 0 & - 4 & - 9 \\ 0 & 4 & 21 \\ 0 & - 7 & - 13 \\ 0 & 6 & - 6 \end{matrix}) | \cdot (\begin{matrix} 0 \\ 1 \\ 0 \end{matrix}), (\begin{matrix} 1 \\ 0 \\ 0 \end{matrix}) \\ A \cdot (\begin{matrix} 2 \\ - 3 \\ 1 \\ 0 \\ 0 \end{matrix}) = (\begin{matrix} - 4 \\ 4 \\ - 7 \\ 6 \end{matrix}), A \cdot (\begin{matrix} 1 \\ 0 \\ 2 \\ - 1 \\ 1 \end{matrix}) \underset{Homogeneous!}{=} 0 \\ ⟹ A x = (\begin{matrix} - 4 \\ 4 \\ - 7 \\ 6 \end{matrix}) ⟹ x = {(\begin{matrix} 2 \\ - 3 \\ 1 \\ 0 \\ 0 \end{matrix}) + α (\begin{matrix} 1 \\ 0 \\ 2 \\ - 1 \\ 1 \end{matrix}) | \forall α \in R} \end{matrix}