Exercise 1
Let $ A $ be an $ n \times n $ matrix. Prove the equivalence between:
(i) There is a $ B $ with $ AB = I $.
(ii) There is a $ C $ with $ CA = I $.
Proof:
We show both conditions are equivalent to $ \operatorname{rank}(A) = n $.
If there exists $ B $ with $ AB = I $, then $ A $ is surjective, so $ \operatorname{rank}(A) = n $.
If there exists $ C $ with $ CA = I $, then $ A $ is injective, so $ \operatorname{rank}(A) = n $.
Conversely, if $ \operatorname{rank}(A) = n $, then $ A $ is invertible (as $ A $ is square), so both $ AB = I $ and $ CA = I $ hold with $ B = C = A^{-1} $.
Exercise 2
Give an $ m \times n $ matrix $ A $ such that:
There is a $ B $ with $ AB = I $.
There is no $ C $ with $ CA = I $.
Solution:
We need $ m > n $ and $ \operatorname{rank}(A) = n $.
Consider $ A = \begin{pmatrix} 1 & 0 \\ 0 & 1 \\ 0 & 0 \end{pmatrix} $, a $ 3 \times 2 $ matrix with $ \operatorname{rank}(A) = 2 $.
Since $ \operatorname{rank}(A) = 2 = n $, the columns are linearly independent, so $ A $ has a right inverse $ B = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix} $ with $ AB = I_2 $.
However, $ \operatorname{rank}(A) = 2 < 3 = m $, so $ A $ is not surjective, hence has no left inverse. If $ CA = I_3 $ existed, then $ \operatorname{rank}(I_3) = 3 \leq \operatorname{rank}(A) = 2 $, a contradiction.
Exercise 3
Find all solutions of the following systems of linear equations, where $ x_1, x_2, x_3, x_4 $ are variables and $ \lambda $ is a parameter.
(1) $$ \begin{cases} 2x_1 - x_2 + x_3 + x_4 = 1, \\ x_1 + 2x_2 - x_3 + 4x_4 = 2, \\ x_1 + 7x_2 - 4x_3 + 11x_4 = \lambda. \end{cases} $$
(2) $$ \begin{cases} \lambda x_1 + x_2 + x_3 + x_4 = 1, \\ x_1 + \lambda x_2 + x_3 + x_4 = \lambda, \\ x_1 + x_2 + \lambda x_3 + x_4 = \lambda^2, \\ x_1 + x_2 + x_3 + \lambda x_4 = \lambda^3. \end{cases} $$
Solution:
(1) Form the augmented matrix and perform row reduction: $$ \left( \begin{array}{cccc|c} 2 & -1 & 1 & 1 & 1 \\ 1 & 2 & -1 & 4 & 2 \\ 1 & 7 & -4 & 11 & \lambda \end{array} \right) $$ After Gaussian elimination, we obtain: $$ \left( \begin{array}{cccc|c} 1 & 0 & 1 & 6 & 4 \\ 0 & 1 & -1 & -1 & -1 \\ 0 & 0 & 0 & 0 & \lambda-5 \end{array} \right) $$
- If $ \lambda \neq 5 $: no solution.
- If $ \lambda = 5 $: infinitely many solutions with two free variables.
Setting $ x_3 = s, x_4 = t $, we get: $$ x_1 = 4-s-6t, \quad x_2 = -1+s+t, \quad x_3 = s, \quad x_4 = t. $$
(2) Form the augmented matrix with parameter $ \lambda $:
$$ \left( \begin{array}{cccc|c} \lambda & 1 & 1 & 1 & 1 \\ 1 & \lambda & 1 & 1 & \lambda \\ 1 & 1 & \lambda & 1 & \lambda^2 \\ 1 & 1 & 1 & \lambda & \lambda^3 \end{array} \right) $$Case 1: $ \lambda = 1 $
The system becomes $ x_1 + x_2 + x_3 + x_4 = 1 $ (all four equations are identical). Setting $ x_2 = s, x_3 = t, x_4 = u $ as free variables: $$ x_1 = 1 - s - t - u, \quad x_2 = s, \quad x_3 = t, \quad x_4 = u. $$
Case 2: $ \lambda = -3 $
Performing row operations leads to an inconsistent system. Specifically, after reduction we obtain a row of the form $ (0, 0, 0, 0 \mid c) $ with $ c \neq 0 $. No solution exists.
Case 3: $ \lambda \notin {-3, 1} $
Subtracting appropriate multiples of rows, we can reduce the system. Notice that if all $ x_i $ are equal, say $ x_i = c $, then:
- First equation: $ (\lambda + 3)c = 1 $
- Second equation: $ (\lambda + 3)c = \lambda $
- Third equation: $ (\lambda + 3)c = \lambda^2 $
- Fourth equation: $ (\lambda + 3)c = \lambda^3 $
For consistency, we need $ 1 = \lambda = \lambda^2 = \lambda^3 $, which is impossible for $ \lambda \neq 1 $. However, the right-hand sides satisfy $ 1 + \lambda + \lambda^2 + \lambda^3 = b $.
After complete row reduction, we find that the system has rank 4 (full rank) when $ \lambda \neq -3, 1 $, giving a unique solution: $$ x_1 = x_2 = x_3 = x_4 = \frac{1 + \lambda + \lambda^2 + \lambda^3}{\lambda + 3} = c. $$ This can be verified by substitution into the original equations.
Exercise 4
Use Gaussian elimination to calculate an upper triangular system $ Ux = c $ for the linear system $ Ax = b $. Write down the elementary matrix in each step and point out the failures you meet.
(i) $ A = \begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{pmatrix} $ and $ b = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} $.
(ii) $ A = \begin{pmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{pmatrix} $ and $ b = 0 $.
(iii) $ A = \begin{pmatrix} 0 & 1 & 2 \\ 7 & 8 & 3 \\ 6 & 5 & 4 \end{pmatrix} $ and $ b = 0 $.
Solution:
(i) $ A = \begin{pmatrix} 0 & 1 & 2 \\ 3 & 4 & 5 \\ 6 & 7 & 8 \end{pmatrix} $, $ b = \begin{pmatrix} 0 \\ 1 \\ 1 \end{pmatrix} $
Failure: The first pivot position is zero, so we need a row swap.
Step 1: Swap rows 1 and 2. $$ P_{12} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} $$
After applying: $ \begin{pmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 6 & 7 & 8 \end{pmatrix} $, $ b = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} $
Step 2: Eliminate position (3,1) using $ E_{31} $. $$ E_{31} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -2 & 0 & 1 \end{pmatrix} $$
After applying: $ \begin{pmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & -1 & -2 \end{pmatrix} $, $ b = \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix} $
Step 3: Eliminate position (3,2) using $ E_{32} $. $$ E_{32} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 1 & 1 \end{pmatrix} $$
After applying: $ U = \begin{pmatrix} 3 & 4 & 5 \\ 0 & 1 & 2 \\ 0 & 0 & 0 \end{pmatrix} $, $ c = \begin{pmatrix} 1 \\ 0 \\ -1 \end{pmatrix} $
Failure: The system is inconsistent since the last row gives $ 0 = -1 $.
(ii) $ A = \begin{pmatrix} 1 & 4 & 7 \\ 2 & 5 & 8 \\ 3 & 6 & 9 \end{pmatrix} $, $ b = 0 $
Step 1: Eliminate position (2,1) using $ E_{21} $. $$ E_{21} = \begin{pmatrix} 1 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \end{pmatrix} $$
After applying: $ \begin{pmatrix} 1 & 4 & 7 \\ 0 & -3 & -6 \\ 3 & 6 & 9 \end{pmatrix} $, $ b = 0 $
Step 2: Eliminate position (3,1) using $ E_{31} $. $$ E_{31} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -3 & 0 & 1 \end{pmatrix} $$
After applying: $ \begin{pmatrix} 1 & 4 & 7 \\ 0 & -3 & -6 \\ 0 & -6 & -12 \end{pmatrix} $, $ b = 0 $
Step 3: Eliminate position (3,2) using $ E_{32} $. $$ E_{32} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & -2 & 1 \end{pmatrix} $$
After applying: $ U = \begin{pmatrix} 1 & 4 & 7 \\ 0 & -3 & -6 \\ 0 & 0 & 0 \end{pmatrix} $, $ c = 0 $
Failure: The third row is zero, indicating the matrix is singular. The system has infinitely many solutions (with one free variable).
(iii) $ A = \begin{pmatrix} 0 & 1 & 2 \\ 7 & 8 & 3 \\ 6 & 5 & 4 \end{pmatrix} $, $ b = 0 $
Failure: The first pivot position is zero, requiring a row swap.
Step 1: Swap rows 1 and 2. $$ P_{12} = \begin{pmatrix} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1 \end{pmatrix} $$
After applying: $ \begin{pmatrix} 7 & 8 & 3 \\ 0 & 1 & 2 \\ 6 & 5 & 4 \end{pmatrix} $, $ b = 0 $
Step 2: Eliminate position (3,1) using $ E_{31} $. $$ E_{31} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ -\frac{6}{7} & 0 & 1 \end{pmatrix} $$
After applying: $ \begin{pmatrix} 7 & 8 & 3 \\ 0 & 1 & 2 \\ 0 & -\frac{13}{7} & \frac{10}{7} \end{pmatrix} $, $ b = 0 $
Step 3: Eliminate position (3,2) using $ E_{32} $. $$ E_{32} = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & \frac{13}{7} & 1 \end{pmatrix} $$
After applying: $ U = \begin{pmatrix} 7 & 8 & 3 \\ 0 & 1 & 2 \\ 0 & 0 & \frac{36}{7} \end{pmatrix} $, $ c = 0 $
The system has a unique solution (the trivial solution $ x = 0 $).
Exercise 5
Use Gauss-Jordan to calculate the inverse of the following matrices.
(i) $ \begin{pmatrix} 16 & 15 & 14 & 13 \\ 5 & 4 & 3 & 12 \\ 6 & 1 & 2 & 11 \\ 7 & 8 & 9 & 10 \end{pmatrix} $.
(ii) $ \begin{pmatrix} 1 & 1 & 10 & 1 \\ 1 & 10 & 1 & 1 \\ 1 & 1 & 1 & 10 \\ 10 & 1 & 1 & 1 \end{pmatrix} $.
(iii) $ aa^T - I_n $ with $ a = \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix} \in \mathbb{R}^n $.
Solution:
(i) For $ A = \begin{pmatrix} 16 & 15 & 14 & 13 \\ 5 & 4 & 3 & 12 \\ 6 & 1 & 2 & 11 \\ 7 & 8 & 9 & 10 \end{pmatrix} $:
Form the augmented matrix $ [A | I_4] $ and apply row operations to reduce $ A $ to $ I_4 $.
After Gauss-Jordan elimination, we obtain:
$$ A^{-1} = \begin{pmatrix} \dfrac{83}{690} & - \dfrac{2}{15} & \dfrac{1}{6} & - \dfrac{62}{345} \\ \dfrac{34}{345} & \dfrac{11}{30} & - \dfrac{1}{3} & - \dfrac{139}{690} \\ - \dfrac{17}{138} & - \dfrac{1}{3} & \dfrac{1}{6} & \dfrac{26}{69} \\ - \dfrac{6}{115} & \dfrac{1}{10} & 0 & \dfrac{11}{230} \end{pmatrix} $$(ii) For $ A = \begin{pmatrix} 1 & 1 & 10 & 1 \\ 1 & 10 & 1 & 1 \\ 1 & 1 & 1 & 10 \\ 10 & 1 & 1 & 1 \end{pmatrix} $:
Form $ [A | I_4] $ and reduce. After row operations:
$$ A^{-1} = \frac{1}{117} \begin{pmatrix} -1 & -1 & -1 & 12 \\ -1 & 12 & -1 & -1 \\ 12 & -1 & -1 & -1 \\ -1 & -1 & 12 & -1 \end{pmatrix} $$(iii) For $ M = aa^T - I_n $ where $ a = \begin{pmatrix} 1 \\ \vdots \\ 1 \end{pmatrix} \in \mathbb{R}^n $:
Form the augmented matrix $ [M | I_n] $ and apply row operations to reduce $ M $ to $ I_n $.
After Gauss-Jordan elimination, we obtain: $$ M^{-1} = \frac{1}{n-1} aa^T - I_n $$ Explicitly, $ M^{-1} $ has diagonal entries $ \frac{1}{n-1}-1 $ and off-diagonal entries $ \frac{1}{n-1} $.