Transformation of Matrices

Lessons

Senior 6 · Mathematics

Transformation of Matrices

5 lessons

Lesson 2 of 5

Inverse and linear systems by elimination

40 min

Elimination does the whole job

Lesson 1 turned matrices into echelon form. This lesson uses that form for the two jobs you did with determinants in S5: finding an inverse and solving a system. The new method has two advantages. It works for systems of any size, including systems with more unknowns than equations. And when a system has no solution, or infinitely many, it tells you which, and describes all the solutions.

The inverse by Gauss–Jordan elimination

Recall that a square matrix $A$ of order $n$ is invertible when there is a matrix $A^{- 1}$ with $AA^{-1} = A^{-1}A = I_n$ . If row operations with elementary matrices $E_1, E_2, \dots, E_k$ reduce $A$ to $I_{n}$ , then $E_k \cdots E_2E_1A = I_n$ , so $A^{-1} = E_k \cdots E_2E_1 = E_k \cdots E_2E_1 I_n$ . In words: the same operations that turn $A$ into $I$ turn $I$ into $A^{- 1}$ . Write the two side by side and reduce:

(A \mid I_n) \longrightarrow \cdots \longrightarrow (I_n \mid A^{-1}) .

If instead a zero row appears on the left, $A$ cannot be reduced to $I_{n}$ , and it has no inverse.

Important

Theorem. For a square matrix $A$ of order $n$ , the following say the same thing:

$A$ is invertible;
$\operatorname{rank} A = n$ ;
$\det A \ne 0$ ;
the reduced row echelon form of $A$ is $I_{n}$ .

Reason. Row operations multiply the determinant by a non-zero number (lesson 1), so $\det A \ne 0$ exactly when the echelon form has no zero row, that is, $n$ pivots.

Worked example 1: a $3 \times 3$ inverse

Find the inverse of $A = \begin{pmatrix} 1 & 1 & 2 \\ 2 & 3 & 5 \\ 1 & 2 & 4 \end{pmatrix}$ .

Solution. Clear column 1, then column 2 below the pivots:

\left(\begin{array}{rrr|rrr} 1 & 1 & 2 & 1 & 0 & 0 \\ 2 & 3 & 5 & 0 & 1 & 0 \\ 1 & 2 & 4 & 0 & 0 & 1 \end{array}\right) \xrightarrow[R_3 \to R_3 - R_1]{R_2 \to R_2 - 2R_1} \left(\begin{array}{rrr|rrr} 1 & 1 & 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 1 & 2 & -1 & 0 & 1 \end{array}\right) \xrightarrow{R_3 \to R_3 - R_2} \left(\begin{array}{rrr|rrr} 1 & 1 & 2 & 1 & 0 & 0 \\ 0 & 1 & 1 & -2 & 1 & 0 \\ 0 & 0 & 1 & 1 & -1 & 1 \end{array}\right) .

Three pivots, so $A$ is invertible. Now clear the entries above the pivots, from the bottom up:

\xrightarrow[R_1 \to R_1 - 2R_3]{R_2 \to R_2 - R_3} \left(\begin{array}{rrr|rrr} 1 & 1 & 0 & -1 & 2 & -2 \\ 0 & 1 & 0 & -3 & 2 & -1 \\ 0 & 0 & 1 & 1 & -1 & 1 \end{array}\right) \xrightarrow{R_1 \to R_1 - R_2} \left(\begin{array}{rrr|rrr} 1 & 0 & 0 & 2 & 0 & -1 \\ 0 & 1 & 0 & -3 & 2 & -1 \\ 0 & 0 & 1 & 1 & -1 & 1 \end{array}\right) .

So $A^{-1} = \begin{pmatrix} 2 & 0 & -1 \\ -3 & 2 & -1 \\ 1 & -1 & 1 \end{pmatrix}$ . Check one entry of $AA^{-1}$ : row 2 of $A$ times column 1 of $A^{- 1}$ is $2 (2) + 3 (- 3) + 5 (1) = 0$ , as it should be off the diagonal.

Solving a system by Gaussian elimination

A system of $m$ linear equations in $n$ unknowns is written $A X = b$ , where $A$ is the $m \times n$ coefficient matrix, $X$ the column of unknowns and $b$ the column of constants. The augmented matrix $(A \mid b)$ holds all the information. Reduce it to echelon form with row operations (never column operations), then solve from the last equation upwards: this is back substitution.

Definition

A system is consistent if it has at least one solution and inconsistent if it has none. It is homogeneous if $b = 0$ ; a homogeneous system is always consistent, since $X = 0$ (the trivial solution) satisfies it. A variable whose column contains no pivot is a free variable (or parameter): it may take any real value.

Important

Rouché–Capelli theorem (also called the Kronecker–Capelli theorem). Let $A X = b$ have $n$ unknowns, and let $r = \operatorname{rank} A$ and $r' = \operatorname{rank}(A \mid b)$ . Then

if $r \lt r'$ , the system has no solution;
if $r = r^{'} = n$ , it has exactly one solution;
if $r = r' \lt n$ , it has infinitely many solutions, described by $n - r$ free parameters.

Reason. $r \lt r'$ means the echelon form of $(A \mid b)$ has a row $(0 \ 0 \ \cdots \ 0 \mid c)$ with $c \ne 0$ , which says $0 = c$ : impossible. Otherwise each non-zero row fixes one pivot variable in terms of the variables to its right, and the $n - r$ variables without a pivot are free.

The rank test (Rouché–Capelli theorem) decides the number of solutions before you solve.

Worked example 2: one solution

Solve $\begin{cases} x + 2y - z = 1 \\ 2x + 5y + z = 12 \\ -x + y + 4z = 11 \end{cases}$

Solution.

\left(\begin{array}{rrr|r} 1 & 2 & -1 & 1 \\ 2 & 5 & 1 & 12 \\ -1 & 1 & 4 & 11 \end{array}\right) \xrightarrow[R_3 \to R_3 + R_1]{R_2 \to R_2 - 2R_1} \left(\begin{array}{rrr|r} 1 & 2 & -1 & 1 \\ 0 & 1 & 3 & 10 \\ 0 & 3 & 3 & 12 \end{array}\right) \xrightarrow{R_3 \to R_3 - 3R_2} \left(\begin{array}{rrr|r} 1 & 2 & -1 & 1 \\ 0 & 1 & 3 & 10 \\ 0 & 0 & -6 & -18 \end{array}\right)

Here $r = r^{'} = 3 = n$ , so there is exactly one solution. Back substitution: $- 6 z = - 18$ gives $z = 3$ ; $y + 3 (3) = 10$ gives $y = 1$ ; $x + 2 (1) - 3 = 1$ gives $x = 2$ . Check in the third equation: $- 2 + 1 + 12 = 11$ . The solution is $(x, y, z) = (2, 1, 3)$ .

Worked example 3: infinitely many solutions, and none

(a) Solve $\begin{cases} x + 2y - z = 3 \\ 2x + 5y + z = 4 \\ 3x + 7y = 7 \end{cases}$ (b) Show that the system is inconsistent if the last constant 7 is replaced by 8.

Solution. (a) The augmented matrix is the matrix of lesson 1, worked example 1, whose reduced form was found there:

\left(\begin{array}{rrr|r} 1 & 2 & -1 & 3 \\ 2 & 5 & 1 & 4 \\ 3 & 7 & 0 & 7 \end{array}\right) \sim \left(\begin{array}{rrr|r} 1 & 0 & -7 & 7 \\ 0 & 1 & 3 & -2 \\ 0 & 0 & 0 & 0 \end{array}\right) .

$r = r' = 2 \lt 3$ : infinitely many solutions with $3 - 2 = 1$ parameter. Column 3 has no pivot, so $z$ is free; put $z = t$ . The rows read $x - 7 t = 7$ and $y + 3 t = - 2$ , so

(x, y, z) = (7 + 7t,\ -2 - 3t,\ t), \quad t \in \mathbb{R} .

Geometrically, the three planes meet along a line through $(7, - 2, 0)$ with direction $(7, - 3, 1)$ . Check with $t = 1$ : $(14, - 5, 1)$ gives $14 - 10 - 1 = 3$ , $28 - 25 + 1 = 4$ , $42 - 35 = 7$ .

(b) The same operations now end with the row $(0 \ 0 \ 0 \mid 1)$ , which says $0 = 1$ . So $r = 2 \lt r' = 3$ and there is no solution: the third plane is parallel to the line where the first two meet.

Worked example 4: discussing a system with parameters

Discuss, according to the real numbers $k$ and $m$ , the system $\begin{cases} x + y + z = 1 \\ x + 2y + 3z = 2 \\ x + 3y + kz = m \end{cases}$

Solution. The coefficient matrix is matrix $B$ of lesson 1, worked example 2. The same operations give

\left(\begin{array}{rrr|r} 1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 2 \\ 1 & 3 & k & m \end{array}\right) \sim \left(\begin{array}{rrr|r} 1 & 1 & 1 & 1 \\ 0 & 1 & 2 & 1 \\ 0 & 0 & k-5 & m-3 \end{array}\right) .

$k \ne 5$ : $r = r^{'} = 3$ , exactly one solution, with $z = \frac{m - 3}{k - 5}$ .
$k = 5$ and $m \ne 3$ : the last row is $(0 \ 0 \ 0 \mid m - 3)$ with $m - 3 \ne 0$ , so $r = 2 \lt r' = 3$ : no solution.
$k = 5$ and $m = 3$ : $r = r^{'} = 2$ : infinitely many solutions. With $z = t$ : $y = 1 - 2 t$ , $x = 1 - y - z = t$ , so $(x, y, z) = (t, 1 - 2 t, t)$ .

Warning

A zero row is not a contradiction. The row $(0 \ 0 \ 0 \mid 0)$ says $0 = 0$ : it only means one equation depended on the others. The contradiction is $(0 \ 0 \ 0 \mid c)$ with $c \ne 0$ . Pupils often write "no solution" when they see any zero row; count the ranks instead.

Tip

For a square homogeneous system $A X = 0$ : if $\det A \ne 0$ the only solution is the trivial one; if $\det A = 0$ there are infinitely many solutions. One determinant answers the question before you reduce anything.

MIT OpenCourseWare: Lecture 8 of 18.06 Linear Algebra, Solving Ax = b: Row Reduced Form R, with Gilbert Strang (about 48 min). Watch for the moment he decides when Ax = b is solvable and builds the complete solution from one particular solution plus the free variables.

✦

Practice

Questions 1 to 3 are routine; 4 to 6 need more care; 7 asks you to explain.

Find the inverse of $\begin{pmatrix} 2 & 1 & 0 \\ 1 & 1 & 1 \\ 0 & 1 & 3 \end{pmatrix}$ by Gauss–Jordan elimination.
Show by row reduction that $\begin{pmatrix} 1 & 2 & 3 \\ 2 & 1 & 0 \\ 3 & 3 & 3 \end{pmatrix}$ has no inverse, and state its rank.
Solve $\begin{cases} 2x - y + z = 3 \\ x + y - 2z = -3 \\ 3x + 2y + z = 10 \end{cases}$
Solve $\begin{cases} x + y - z = 2 \\ 2x + 3y + z = 7 \\ x + 2y + 2z = 5 \end{cases}$ and describe the solution set geometrically.
Show that $\begin{cases} x - 2y + z = 1 \\ 2x - 3y + 4z = 5 \\ x - y + 3z = 3 \end{cases}$ has no solution, by comparing ranks.
Discuss, according to the real numbers $a$ and $b$ , the system $\begin{cases} x + y + z = 2 \\ 2x + 3y + z = 5 \\ x + 2y + az = b \end{cases}$
Find all solutions of the homogeneous system $\begin{cases} x + 2y - z = 0 \\ 3x - y + 2z = 0 \\ x - 5y + 4z = 0 \end{cases}$ and explain, using the determinant, why there are non-trivial ones.

Show answersHide answers

$\begin{pmatrix} 2 & -3 & 1 \\ -3 & 6 & -2 \\ 1 & -2 & 1 \end{pmatrix}$
$R_{3} = R_{1} + R_{2}$ , so $R_3 \to R_3 - R_1 - R_2$ gives a zero row: rank 2, not invertible (and $\det = 0$ ).
$(x, y, z) = (1, 2, 3)$
$(x, y, z) = (-1 + 4t,\ 3 - 3t,\ t)$ , $t \in \mathbb{R}$ : a line through $(- 1, 3, 0)$ with direction $(4, - 3, 1)$ .
Rank of the coefficient matrix 2, rank of the augmented matrix 3; the echelon form contains $(0 \ 0 \ 0 \mid 1)$ .
The reduced last row is $(0 \ 0 \ a \mid b - 3)$ . $a \ne 0$ : one solution. $a = 0, b \ne 3$ : none. $a = 0, b = 3$ : infinitely many, $(x, y, z) = (1 - 2t,\ 1 + t,\ t)$ .
$\det = 0$ , so non-trivial solutions exist: $(x, y, z) = s (- 3, 5, 7)$ , $s \in \mathbb{R}$ .

Sources and credits

Written by Ganzaa: the explanations, the flowchart, the worked examples, the practice items and the quiz questions. Every inverse and solution was checked with exact fraction arithmetic and by substitution.
Video: 8. Solving Ax = b: Row Reduced Form R, MIT 18.06 Linear Algebra, Gilbert Strang, MIT OpenCourseWare, embedded from YouTube.

1Elimination does the whole job

2The inverse by Gauss–Jordan elimination

3Solving a system by Gaussian elimination

Elimination does the whole job

The inverse by Gauss–Jordan elimination

Solving a system by Gaussian elimination