Chapter 9Systems of Linear Equations
In Chapter 8 we saw that the determinant $|A|$ represents “the area of the parallelogram formed by the vectors that make up the matrix” and “the volume of the parallelepiped,” and that when $|A|=0$ the figure is squashed completely flat and its area or volume becomes $0$—that is, the vectors are linearly dependent (one can be written as a constant multiple of the other, or several vectors end up lying in the same plane). In this chapter, through concrete calculations, we confirm that this single piece of information, “whether or not $|A|=0$,” completely governs the number of solutions of a system of linear equations: whether there is exactly one solution, infinitely many solutions involving parameters, or no solution at all.
The starting point is a formula that uses determinants to write down the inverse matrix $A^{-1}$ explicitly. To this end, we define a new matrix, the adjugate matrix (the adjugate of $A$), and prove the formula $A^{-1}=\dfrac{1}{|A|}\tilde A$ ourselves, using cofactor expansion (already covered in Chapter 8). Next, for a general matrix (not necessarily square), we define a number called the rank and learn to compute it as the “number of steps” of the row echelon matrix obtained by elementary row operations. Once the rank is known, the quantity called the degrees of freedom, obtained by subtracting the rank from the number of unknowns, tells us “how many parameters can be chosen freely” in the solutions of a system of linear equations—this is the most important idea in this chapter, and it applies equally to the homogeneous case (all the right-hand sides are $0$) and the nonhomogeneous case (the right-hand sides are not $0$). On this basis, we complete Gaussian elimination (the sweep-out method), in which merely applying elementary row operations to the augmented matrix lets us decide mechanically among a unique solution, infinitely many solutions, and no solution, and write down the solutions explicitly. Finally, using the same technique of elementary row operations, we treat a method of finding inverse matrices, the criterion for invertibility, and the normal form, the ultimate simple form that every matrix can be brought to by elementary row and column operations.
- The definition of the adjugate matrix $\tilde A$, and the proof of the inverse matrix formula $A^{-1}=\dfrac{1}{|A|}\tilde A$ (using cofactor expansion)
- The definition of rank: the number of nonzero rows of the row echelon matrix obtained by elementary row operations. $0\le \rank A\le\min(m,n)$
- The definition of the degrees of freedom $=n-\rank A$ ($n$ is the number of unknowns), and a test for whether a homogeneous system of linear equations has solutions other than the trivial solution
- The condition for a nonhomogeneous system of linear equations to have a solution ($\rank A=\rank\tilde A$), and the classification of the solutions by the degrees of freedom when they exist
- Gaussian elimination: simply reducing the augmented matrix to a row echelon matrix by elementary row operations yields every case—a unique solution, infinitely many solutions (in parametric form), or no solution
- How to find an inverse matrix, $[A\mid E]\to[E\mid A^{-1}]$, and the conditions for invertibility, “$A$ is invertible $\iff$ $\rank A=n$ $\iff$ the row echelon matrix is the identity matrix $E_n$” ($\iff$ is the symbol for “necessary and sufficient condition” and is read “… is equivalent to …”)
- The normal form $\begin{bmatrix}I_r&O\\O&O\end{bmatrix}$ (using both elementary row operations and elementary column operations, every matrix can be brought to this form)
Source notes: Yasuhide Mochizuki, Mathematics Notes: Linear Algebra, pp. 9–14.
9.1 The Adjugate Matrix and the Formula for the Inverse Matrix
Consider the square matrix of order $n$
$$ A=\begin{bmatrix}a_{11}&a_{12}&\cdots&a_{1n}\\a_{21}&a_{22}&\cdots&a_{2n}\\\vdots&\vdots&&\vdots\\a_{n1}&a_{n2}&\cdots&a_{nn}\end{bmatrix} $$As we learned in Chapter 8, the determinant of the matrix of order $(n-1)$ obtained by deleting the $i$th row and the $j$th column from $A$ is called the minor and is written $M_{ij}$. Attaching the sign $(-1)^{i+j}$ to it gives $A_{ij}=(-1)^{i+j}M_{ij}$, which we called the $(i,j)$ cofactor of $A$. The determinant can be evaluated by cofactor expansion along any row or any column:
$$ |A|=\sum_{k=1}^{n}a_{ik}A_{ik}\ \ (\text{expansion along the }i\text{th row}) =\sum_{k=1}^{n}a_{kj}A_{kj}\ \ (\text{expansion along the }j\text{th column}) $$Either way, the value is the same. In this section, we use these cofactors to write down the inverse matrix $A^{-1}$ as an explicit formula. Before defining the general case of order $n$, let us first get a feel for the operation of “arranging the cofactors and transposing” through a small example that is familiar even from high school. The cofactors of a square matrix $A=\begin{bmatrix}a&b\\c&d\end{bmatrix}$ of order $2$ ($ad-bc\neq0$) are $A_{11}=d,\ A_{12}=-c,\ A_{21}=-b,\ A_{22}=a$ (the determinant of a $1\times1$ matrix is just its entry, so each minor is simply the one number that remains after the deletion). Transposing the matrix $\begin{bmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{bmatrix}=\begin{bmatrix}d&-c\\-b&a\end{bmatrix}$ formed by arranging them gives $\begin{bmatrix}d&-b\\-c&a\end{bmatrix}$, and the result of dividing this by $|A|=ad-bc$ is exactly the inverse matrix formula of order $2$ that already appeared in high school mathematics:
$$ A^{-1}=\frac{1}{ad-bc}\begin{bmatrix}d&-b\\-c&a\end{bmatrix} $$In other words, the procedure “arrange the cofactors, transpose, and divide by $|A|$” is nothing other than an extension of this familiar formula of order $2$ to the general case of order $n$. So let us now define this operation properly for square matrices of order $n$.
Definition 9.1: Adjugate matrix
Arrange the cofactors $A_{ij}$ ($i,j=1,\ldots,n$) of a square matrix $A$ of order $n$ into the matrix
$$ \begin{bmatrix}A_{11}&A_{12}&\cdots&A_{1n}\\A_{21}&A_{22}&\cdots&A_{2n}\\\vdots&\vdots&&\vdots\\A_{n1}&A_{n2}&\cdots&A_{nn}\end{bmatrix} $$The transpose of this matrix (the matrix obtained by interchanging rows and columns; it is written by attaching $t$ at the upper left, as $^t(\ \cdot\ )$) is called the adjugate matrix of $A$ and is written $\tilde A$. That is,
\begin{equation} \tilde A={}^{t}\!\begin{bmatrix}A_{11}&A_{12}&\cdots&A_{1n}\\A_{21}&A_{22}&\cdots&A_{2n}\\\vdots&\vdots&&\vdots\\A_{n1}&A_{n2}&\cdots&A_{nn}\end{bmatrix} =\begin{bmatrix}A_{11}&A_{21}&\cdots&A_{n1}\\A_{12}&A_{22}&\cdots&A_{n2}\\\vdots&\vdots&&\vdots\\A_{1n}&A_{2n}&\cdots&A_{nn}\end{bmatrix} \qquad\cdots\label{eq:9-adjugate} \end{equation}(Because we take the transpose, the $(i,j)$ entry of $\tilde A$ is the $(j,i)$ cofactor $A_{ji}$ of $A$. Note that the order of the subscripts is interchanged.)
Formula 9.1: Inverse matrix formula
If a square matrix $A$ of order $n$ is invertible ($|A|\neq0$), then its inverse matrix
can be expressed in terms of the adjugate matrix.
Proof
The inverse matrix was defined as the matrix satisfying $AA^{-1}=A^{-1}A=E$ ($E$ is the identity matrix). Therefore, if we can show the two equations $A\tilde A=|A|E$ and $\tilde A A=|A|E$, then dividing both sides by $|A|$ ($\neq0$) gives $A\cdot\dfrac{1}{|A|}\tilde A=E$ and $\dfrac{1}{|A|}\tilde A\cdot A=E$, and from the definition we can conclude that $A^{-1}=\dfrac{1}{|A|}\tilde A$.
(i) We show that $A\tilde A=|A|E$. By the definition of the matrix product, the $(i,j)$ entry of $A\tilde A$ is the inner product of the $i$th row of $A$ and the $j$th column of $\tilde A$. By Definition 9.1, the $j$th column of $\tilde A$ is $(A_{j1},A_{j2},\ldots,A_{jn})$ (the cofactors of the $j$th row of $A$), so we have
$$ (A\tilde A)_{ij}=\sum_{k=1}^{n}a_{ik}A_{jk} $$Now we split into two cases.
(a) The case $i=j$. The sum $\displaystyle\sum_{k=1}^{n}a_{ik}A_{ik}$ is exactly the formula for the cofactor expansion of $A$ along the $i$th row, so it equals $|A|$.
(b) The case $i\neq j$. Look at $\displaystyle\sum_{k=1}^{n}a_{ik}A_{jk}$. The coefficient $a_{ik}$ is an entry of “the $i$th row of $A$,” but the cofactor $A_{jk}$ is built from “the minor obtained by deleting the $j$th row and the $k$th column of $A$,” and so does not depend on the contents of the $j$th row itself (naturally, since that row has been deleted). So consider the matrix $A'$ obtained from $A$ by replacing its $j$th row (in place of the original $j$th row) entirely by the entries of the $i$th row. Then the cofactor $A'_{jk}$ of $A'$ is given by exactly the same expression as $A_{jk}$. Therefore
$$ \sum_{k=1}^{n}a_{ik}A_{jk}=\sum_{k=1}^{n}a'_{jk}A'_{jk}=|A'| $$(the right-hand side is the expression for the cofactor expansion of $A'$ along the $j$th row). Now $A'$ is a matrix whose $i$th row and $j$th row are both “the $i$th row of the original $A$,” so the two rows are exactly identical. A determinant with two identical rows is $0$ (a property already learned in Chapter 8), so $|A'|=0$. Hence, when $i\neq j$, $\displaystyle\sum_{k=1}^{n}a_{ik}A_{jk}=0$.
Combining (a) and (b), we obtain $(A\tilde A)_{ij}=|A|\,\delta_{ij}$. Here $\delta_{ij}$ is the Kronecker delta (the symbol that returns $1$ when $i=j$ and $0$ when $i\neq j$). The matrix whose $(i,j)$ entry is $|A|\delta_{ij}$ is exactly $|A|E$, so $A\tilde A=|A|E$.
(ii) We show that $\tilde A A=|A|E$. This time we consider the inner product of the $i$th row of $\tilde A$ and the $j$th column of $A$. Since the $i$th row of $\tilde A$ is $(A_{1i},A_{2i},\ldots,A_{ni})$, we have
$$ (\tilde A A)_{ij}=\sum_{k=1}^{n}A_{ki}a_{kj} $$When $i=j$, this becomes $\displaystyle\sum_k a_{ki}A_{ki}$, which is the expression for the cofactor expansion of $A$ along the $i$th column, so it equals $|A|$. When $i\neq j$, we only need to repeat exactly the same argument as in (b) for “columns” instead of “rows”: consider the matrix obtained by replacing the $i$th column of $A$ by the entries of the $j$th column. Its cofactor expansion along the $i$th column coincides with $\displaystyle\sum_k a_{kj}A_{ki}$, and since this matrix has identical $i$th and $j$th columns (it has two identical columns), its determinant is $0$. Hence $(\tilde A A)_{ij}=|A|\delta_{ij}$, that is, $\tilde A A=|A|E$.
From (i) and (ii), we have shown that $A\tilde A=\tilde A A=|A|E$, and since $|A|\neq0$, dividing both sides by it gives $A^{-1}=\dfrac{1}{|A|}\tilde A$.
∎
Intuition: Why does “only the diagonal survive”?
The heart of the formula comes down to a single point: when we form the product of a matrix and its adjugate matrix, the determinant $|A|$ appears in the diagonal entries ($i=j$), while the off-diagonal entries ($i\neq j$) come out neatly as $0$ and vanish. That the off-diagonal entries are $0$ is no accident; it is a direct consequence of a property of determinants (Chapter 8): “if a row (or column) that does not really belong there is slipped into the cofactor expansion formula, we are in effect computing ‘a determinant with two identical rows,’ which is mechanically $0$.” In some textbooks, this fact that “a cofactor expansion into which entries of another row or column have been slipped gives $0$” is also called an “alien cofactor expansion” (a row expanded by the cofactors of a different row).
Example 9.1: The adjugate matrix and the inverse matrix of a $3\times3$ matrix
Find the adjugate matrix $\tilde A$ of $A=\begin{bmatrix}2&0&1\\1&3&-1\\0&1&2\end{bmatrix}$, and use Formula 9.1 to find the inverse matrix $A^{-1}$.
Solution. First we compute all $9$ cofactors. We compute a $2\times2$ determinant by $\begin{vmatrix}p&q\\r&s\end{vmatrix}=ps-qr$.
$$ \begin{aligned} A_{11}&=+\begin{vmatrix}3&-1\\1&2\end{vmatrix}=3\cdot2-(-1)\cdot1=7, & A_{12}&=-\begin{vmatrix}1&-1\\0&2\end{vmatrix}=-(1\cdot2-(-1)\cdot0)=-2, \\ A_{13}&=+\begin{vmatrix}1&3\\0&1\end{vmatrix}=1\cdot1-3\cdot0=1, & A_{21}&=-\begin{vmatrix}0&1\\1&2\end{vmatrix}=-(0\cdot2-1\cdot1)=1, \\ A_{22}&=+\begin{vmatrix}2&1\\0&2\end{vmatrix}=2\cdot2-1\cdot0=4, & A_{23}&=-\begin{vmatrix}2&0\\0&1\end{vmatrix}=-(2\cdot1-0\cdot0)=-2, \\ A_{31}&=+\begin{vmatrix}0&1\\3&-1\end{vmatrix}=0\cdot(-1)-1\cdot3=-3, & A_{32}&=-\begin{vmatrix}2&1\\1&-1\end{vmatrix}=-(2\cdot(-1)-1\cdot1)=3, \\ A_{33}&=+\begin{vmatrix}2&0\\1&3\end{vmatrix}=2\cdot3-0\cdot1=6. && \end{aligned} $$For the sign $(-1)^{i+j}$, we used the fact that it is $+$ when $i+j$ is even and $-$ when it is odd. Transposing the matrix of cofactors $\begin{bmatrix}7&-2&1\\1&4&-2\\-3&3&6\end{bmatrix}$ arranged in this way gives
$$ \tilde A=\begin{bmatrix}7&1&-3\\-2&4&3\\1&-2&6\end{bmatrix} $$Next, the cofactor expansion of $|A|$ along the first row gives $|A|=a_{11}A_{11}+a_{12}A_{12}+a_{13}A_{13}=2\cdot7+0\cdot(-2)+1\cdot1=15$. Since $|A|\neq0$, $A$ is invertible, and by Formula 9.1
$$ A^{-1}=\frac{1}{15}\begin{bmatrix}7&1&-3\\-2&4&3\\1&-2&6\end{bmatrix} =\begin{bmatrix}\dfrac{7}{15}&\dfrac{1}{15}&-\dfrac15\\[4pt]-\dfrac{2}{15}&\dfrac{4}{15}&\dfrac15\\[4pt]\dfrac{1}{15}&-\dfrac{2}{15}&\dfrac25\end{bmatrix} $$(Here we reduced $-3/15=-1/5$, $3/15=1/5$, and $6/15=2/5$.) Computing $A\cdot A^{-1}$ directly confirms that it equals the identity matrix $E$ (verified with SymPy; verification script verify/univmath/ch09_check.py).
9.2 Rank and Row Echelon Matrices
From here on we consider a general matrix of type $(m,n)$ (a matrix with $m$ rows and $n$ columns), which need not be square. If we repeatedly apply elementary row operations—the three kinds of operations (i) multiplying a row by a constant, (ii) adding a constant multiple of another row to a row, and (iii) interchanging two rows—any matrix can be brought to a form like the one below. How these three operations affect the value of a determinant (multiplying a row by a constant multiplies the determinant by the same constant, interchanging two rows reverses its sign, and so on) was covered in Chapter 8. In this chapter, however, we use these three operations not for the value of the determinant itself but for a different purpose: “to reduce the matrix $A$ (or the augmented matrix) to the simplest possible form while leaving the solution set of the system $A\bm x=\bm b$ unchanged.” Since the matrix need not be square, they are a tool with a wider range of applicability, one that can be used even when a determinant cannot be defined at all.
Definition 9.2: Row echelon form and rank
Applying elementary row operations repeatedly to the matrix of type $(m,n)$
$$ A=\begin{bmatrix}a_{11}&a_{12}&a_{13}&\cdots&a_{1n}\\a_{21}&a_{22}&a_{23}&\cdots&a_{2n}\\\vdots&\vdots&\vdots&&\vdots\\a_{m1}&a_{m2}&a_{m3}&\cdots&a_{mn}\end{bmatrix} $$we can bring it to the following form—one in which the number of leading $0$s in each row strictly increases from top to bottom (that is, the matrix takes a staircase shape), and any rows whose entries are all $0$ are always grouped together at the bottom. A matrix in this form is said to be in row echelon form (it is also called a row echelon matrix).
$$ \begin{bmatrix} a_{11}'&a_{12}'&a_{13}'&\cdots& &a_{1n}'\\ 0&a_{22}'&a_{23}'&\cdots& &a_{2n}'\\ \vdots&0&a_{33}'&\cdots& &\vdots\\ 0&\vdots& &\ddots& &a_{rn}'\\ 0&0&\cdots&0&\cdots&0 \end{bmatrix} \Big\}\ \rank A=r \qquad(0\le r\le\min(m,n)) $$The number $r$ of rows whose entries are not all $0$ (that is, the rows corresponding to the “steps” of the staircase) is called the rank of $A$ and is written $\rank A$. The number of steps in the staircase is always the same, regardless of how the elementary row operations are carried out (this can be proved from a different point of view, namely as “the number of rows that are independent as row vectors,” but that proof has to wait for the theory of linear independence in Chapter 10; here we use only the computational method of reducing the matrix to a row echelon matrix and counting the number of steps). There are only $m$ rows, and each step of the staircase uses up at least one column as well, so the number of steps cannot exceed the number $n$ of columns either; hence $\rank A$ is always at least $0$ and at most $\min(m,n)$. (In this book we use elementary row operations to compute the rank, but the same rank is obtained if we use elementary column operations, which are the same kinds of operations applied to columns instead of rows. Elementary column operations are defined in Definition 9.5 in Section 9.6.1.)
Example 9.2: The rank of a matrix of type $(3,4)$
Find the rank $\rank M$ of $M=\begin{bmatrix}1&2&-1&3\\2&4&1&0\\-1&-2&2&-5\end{bmatrix}$.
Solution. We reduce the matrix to a row echelon matrix by elementary row operations. First, subtract $2$ times the first row from the second row ($R_2\to R_2-2R_1$), and add the first row to the third row ($R_3\to R_3+R_1$).
$$ \begin{bmatrix}1&2&-1&3\\2&4&1&0\\-1&-2&2&-5\end{bmatrix} \xrightarrow[R_3\to R_3+R_1]{R_2\to R_2-2R_1} \begin{bmatrix}1&2&-1&3\\0&0&3&-6\\0&0&1&-2\end{bmatrix} $$(Row 2: $2-2\cdot1=0$, $4-2\cdot2=0$, $1-2\cdot(-1)=3$, $0-2\cdot3=-6$. Row 3: $-1+1=0$, $-2+2=0$, $2+(-1)=1$, $-5+3=-2$.) Next, subtract $3$ times the third row from the second row ($R_2\to R_2-3R_3$).
$$ \begin{bmatrix}1&2&-1&3\\0&0&3&-6\\0&0&1&-2\end{bmatrix} \xrightarrow{R_2\to R_2-3R_3} \begin{bmatrix}1&2&-1&3\\0&0&0&0\\0&0&1&-2\end{bmatrix} $$Finally, interchanging the second and third rows gives a proper row echelon matrix, in which the number of leading $0$s increases step by step.
$$ \begin{bmatrix}1&2&-1&3\\0&0&0&0\\0&0&1&-2\end{bmatrix} \xrightarrow{R_2\leftrightarrow R_3} \begin{bmatrix}1&2&-1&3\\0&0&1&-2\\0&0&0&0\end{bmatrix} $$There are two nonzero rows (the first and second rows), so $\rank M=2$ (the same result was also verified with SymPy's rref).
9.3 Degrees of Freedom and Homogeneous Systems of Linear Equations
A system of linear equations $A\bm x=\bm b$ (where $A$ is the coefficient matrix of type $(m,n)$, $\bm x=(x_1,\ldots,x_n)$ is the column vector of the unknowns, and $\bm b$ is the column vector of the constants on the right-hand side) whose right-hand side is entirely $0$, that is, with $\bm b=\bm 0$, is called a homogeneous system of linear equations. A system whose right-hand side is not $0$ is called a nonhomogeneous system of linear equations and is treated in the next section. In this section we consider the homogeneous case.
(A note on notation: from this chapter on, column vectors (elements of $\R^n$, numbers arranged vertically) are written in boldface, as in $\bm x,\bm b$. In Chapter 8 the same “column vectors” were written with an arrow, $\vec x$—this is only a difference in how symbols are decorated from chapter to chapter, and the objects referred to are the same. In Chapter 10, since we deal with elements of abstract vector spaces, whose vectors are not necessarily tuples of numbers, we deliberately write them with neither arrows nor boldface.)
A homogeneous system of linear equations $A\bm x=\bm 0$ has a special feature: $\bm x=\bm 0$, in which every unknown is set to $0$, is always a solution (because $A\bm 0=\bm 0$ always holds). This “obvious” solution, which can be seen at once by substitution, is called the trivial solution. The question is whether any other solution (a nontrivial solution) exists.
Definition 9.3: Degrees of freedom
If $n$ is the number of unknowns, then
$$ \text{degrees of freedom}=n-\rank A $$defines the degrees of freedom (of the solutions of $A\bm x=\bm 0$).
Why is “$n-\rank A$” the number of parameters we can choose freely?
If we reduce the coefficient matrix $A$ to a row echelon matrix by elementary row operations, the number of steps (pivots) is $\rank A=r$. Call the $r$ unknowns corresponding to the columns that contain pivots the pivot variables, and the remaining $n-r$ unknowns the free variables. Then each row of the row echelon matrix gives an equation of the form “pivot variable $=$ linear expression in the free variables.” That is, however we choose the values of the $n-r$ free variables, the values of the pivot variables are then determined uniquely, and we obtain one solution of $A\bm x=\bm 0$. Therefore the set of all solutions is completely described by “$n-r$ freely chosen parameters.” If $n-r=0$ (there is no free variable), there is no parameter to choose, so all the pivot variables are fixed at $0$ and the only solution is the trivial solution $\bm x=\bm 0$.
Theorem 9.1: Classifying the solutions of a homogeneous system of linear equations by the degrees of freedom
For a homogeneous system of linear equations $A\bm x=\bm 0$ (with $n$ unknowns),
$$ \begin{cases} \text{If the degrees of freedom}>0\ \text{then }A\bm x=\bm 0\ \text{also has solutions other than the trivial solution (nontrivial solutions).}\\ \text{If the degrees of freedom}=0\ \text{then }A\bm x=\bm 0\ \text{has only the trivial solution.} \end{cases} $$When $A$ is a square matrix ($m=n$), the degrees of freedom $=0\iff\rank A=n\iff A$ is invertible ($|A|\neq0$). That is, a homogeneous system of linear equations has only the trivial solution exactly when $A$ is an invertible square matrix. The relation between invertibility and the degrees of freedom is treated in detail in Section 9.6.
Intuition: Starting with two variables
Before turning to the three-variable examples, let us first confirm the meaning of the degrees of freedom with two variables (the $x,y$ plane), which is within the scope of high school mathematics. A homogeneous linear equation $ax+by=0$ (where $a,b$ are not both $0$) represents a line through the origin in the $xy$ plane. If we consider a system of two homogeneous equations, the coefficient matrix is of type $(2,2)$, and only two cases can occur.
(i) When the two equations are independent ($\rank A=2$), the two lines have different slopes and have no common point other than the origin. The degrees of freedom $=2-2=0$, and the only solution is the origin $(0,0)$, the trivial solution (Figure 9.2, left).
(ii) When the two equations are dependent ($\rank A=1$, one being a constant multiple of the other), the two lines are in fact the same line, and every point on that line is a solution. The degrees of freedom $=2-1=1$, and the points on the line can be written with a single parameter $t$ as $(x,y)=t\,(x_0,y_0)$, where $(x_0,y_0)$ is a point on that line other than the origin (Figure 9.2, right).
We can carry over this intuition—“each time we lose one independent equation, the degrees of freedom of the solution increase by one”—as it is to the three-variable ($xyz$ space) case that follows. With three variables, a single homogeneous equation represents a plane through the origin.
Now let us actually check the three-variable case with the three examples from the original notes. A single homogeneous equation represents a plane through the origin in $xyz$ space, so three homogeneous equations pose a geometric problem: how do three planes through the origin intersect?
Example 9.3: An example with 0 degrees of freedom (only the trivial solution)
Find the degrees of freedom of the following homogeneous system of linear equations, and find all of its solutions.
$$ \begin{cases} x_1+2x_2+x_3=0\\ 2x_1+3x_2+3x_3=0\\ -x_1+x_2+4x_3=0 \end{cases} $$Solution. The coefficient matrix is $A=\begin{bmatrix}1&2&1\\2&3&3\\-1&1&4\end{bmatrix}$, and the number of unknowns is $n=3$. We reduce it to a row echelon matrix by elementary row operations. Performing $R_2\to R_2-2R_1$ ($2-2=0$, $3-4=-1$, $3-2=1$) and $R_3\to R_3+R_1$ ($-1+1=0$, $1+2=3$, $4+1=5$), we obtain
$$ \begin{bmatrix}1&2&1\\2&3&3\\-1&1&4\end{bmatrix} \to \begin{bmatrix}1&2&1\\0&-1&1\\0&3&5\end{bmatrix} $$Performing further $R_3\to R_3+3R_2$ ($3+3\cdot(-1)=0$, $5+3\cdot1=8$), we obtain
$$ \begin{bmatrix}1&2&1\\0&-1&1\\0&3&5\end{bmatrix} \to \begin{bmatrix}1&2&1\\0&-1&1\\0&0&8\end{bmatrix} $$There are three nonzero rows, so $\rank A=3$. The degrees of freedom $=n-\rank A=3-3=0$. Therefore, by Theorem 9.1, the only solution is the trivial solution. Indeed, rewriting the equations using the row echelon matrix, we obtain
$$ \begin{cases} x_1+2x_2+x_3=0\\ -x_2+x_3=0\\ 8x_3=0 \end{cases} $$From the third equation, $x_3=0$; substituting this into the second equation gives $x_2=0$, and substituting further into the first equation gives $x_1=0$. Hence $(x_1,x_2,x_3)=(0,0,0)$ is the only solution.
Example 9.4: An example with 1 degree of freedom (one parameter)
Find the degrees of freedom of the following homogeneous system of linear equations, and find all of its solutions.
$$ \begin{cases} x_1+2x_2-x_3=0\\ 2x_1-x_2+3x_3=0\\ 4x_1+3x_2+x_3=0 \end{cases} $$Solution. The coefficient matrix is $B=\begin{bmatrix}1&2&-1\\2&-1&3\\4&3&1\end{bmatrix}$, and $n=3$. Performing $R_2\to R_2-2R_1$ ($2-2=0$, $-1-4=-5$, $3-(-2)=5$) and $R_3\to R_3-4R_1$ ($4-4=0$, $3-8=-5$, $1-(-4)=5$), we obtain
$$ \begin{bmatrix}1&2&-1\\2&-1&3\\4&3&1\end{bmatrix} \to \begin{bmatrix}1&2&-1\\0&-5&5\\0&-5&5\end{bmatrix} $$Performing further $R_3\to R_3-R_2$ ($-5-(-5)=0$, $5-5=0$), we obtain
$$ \begin{bmatrix}1&2&-1\\0&-5&5\\0&-5&5\end{bmatrix} \to \begin{bmatrix}1&2&-1\\0&-5&5\\0&0&0\end{bmatrix} \to \begin{bmatrix}1&2&-1\\0&-1&1\\0&0&0\end{bmatrix} $$(In the last step we divided the second row by $-5$ to make the matrix easier to read. Dividing a row by a constant other than $0$ is also a kind of elementary row operation.) There are two nonzero rows, so $\rank B=2$. The degrees of freedom $=3-2=1$. By Theorem 9.1, the system has nontrivial solutions (a one-parameter family). Rewriting the equations from the row echelon matrix, we obtain
$$ \begin{cases} x_1+2x_2-x_3=0\\ -x_2+x_3=0 \end{cases} $$The free variable is $x_3$ (the pivot variables are $x_1,x_2$). So we let $x_3=k$ ($k$ is an arbitrary real number). The second equation then gives $x_2=x_3=k$, and substituting this into the first equation gives $x_1=-2x_2+x_3=-2k+k=-k$. Hence
$$ \begin{cases}x_1=-k\\x_2=k\\x_3=k\end{cases}\qquad(k\in\R) $$is the complete set of solutions. For $k=1$ we obtain the solution $(-1,1,1)$, and the line through the origin with this direction vector is the entire solution set.
Example 9.5: An example with 2 degrees of freedom (two parameters)
Find the degrees of freedom of the following homogeneous system of linear equations, and find all of its solutions.
$$ \begin{cases} 2x_1-x_2+x_3=0\\ 4x_1-2x_2+2x_3=0\\ -6x_1+3x_2-3x_3=0 \end{cases} $$Solution. The coefficient matrix is $C=\begin{bmatrix}2&-1&1\\4&-2&2\\-6&3&-3\end{bmatrix}$, and $n=3$. Looking closely, the second row is exactly twice the first row, and the third row is exactly $-3$ times the first row. Indeed, if we apply $R_2\to R_2-2R_1$ ($4-4=0,-2+2=0,2-2=0$) and $R_3\to R_3+3R_1$ ($-6+6=0,3-3=0,-3+3=0$), we obtain
$$ \begin{bmatrix}2&-1&1\\4&-2&2\\-6&3&-3\end{bmatrix} \to \begin{bmatrix}2&-1&1\\0&0&0\\0&0&0\end{bmatrix} $$Only one nonzero row remains. Thus $\rank C=1$, and the degrees of freedom $=3-1=2$. The system has degenerated into effectively just the single equation $2x_1-x_2+x_3=0$, and the two variables $x_1,x_2$ are free variables ($x_3$ is the pivot variable). Let $x_1=k$ and $x_2=l$ ($k,l$ are arbitrary real numbers). Then $x_3=-2x_1+x_2=-2k+l$. Hence
$$ \begin{cases}x_1=k\\x_2=l\\x_3=-2k+l\end{cases}\qquad(k,l\in\R) $$describes all the solutions. Since the three equations have degenerated into effectively the equation of a single plane, the solutions fill that entire plane (a two-dimensional expanse through the origin).
9.4 Nonhomogeneous Systems of Linear Equations and Degrees of Freedom
Now the right-hand side is not necessarily $\bm 0$: we consider a nonhomogeneous system of linear equations $A\bm x=\bm b$ ($\bm b\neq\bm 0$). Unlike in the homogeneous case, $\bm x=\bm 0$ is in general not a solution ($A\bm 0=\bm 0\neq\bm b$), so we must begin by checking whether a solution exists at all.
Definition 9.4: Augmented matrix (nonhomogeneous case)
For the nonhomogeneous system of linear equations $A\bm x=\bm b$ ($\bm b\neq\bm 0$), let $A$ be the coefficient matrix and let $\bm b$ be the column vector formed by the constant terms on the right-hand side. The matrix obtained by adjoining $\bm b$ as one extra column to the right of the matrix $A$,
$$ A_0=[\,A\mid\bm b\,] $$is called the augmented matrix (in the nonhomogeneous case). We write $A_0'=[\,A'\mid\bm b'\,]$ for the result of applying elementary row operations to $A_0$ ($A'$ is the part obtained by applying the elementary row operations to $A$, and $\bm b'$ is the part obtained by applying the same elementary row operations to $\bm b$).
Theorem 9.2: Condition for the existence of solutions of a nonhomogeneous system of linear equations, and the degrees of freedom
Test for the existence of a solution
$$ \begin{cases} \rank A' \lt \rank A_0'\ \text{implies that no solution exists.}\\ \rank A' = \rank A_0'\ \text{implies that a solution exists.} \end{cases} $$When a solution exists, we define: degrees of freedom $=n-\rank A_0'$ ($n$ is the number of unknowns).
Test for the type of solution
$$ \begin{cases} \text{If the degrees of freedom}>0\ \text{then the system has infinitely many solutions containing parameters (an indeterminate solution).}\\ \text{If the degrees of freedom}=0\ \text{then the system has exactly one solution.} \end{cases} $$(When $A$ is a square matrix, the case where the degrees of freedom $=0$ gives $\rank A_0'=\rank A'=n$, which corresponds to the case where $A$ is invertible; the solution is then determined uniquely as $\bm x=A^{-1}\bm b$ by using the inverse matrix $A^{-1}$. The case where the degrees of freedom $>0$ gives $\rank A' \lt n$, which corresponds to the case where $A$ has no inverse matrix. We will organize this correspondence with invertibility once more in Section 9.6.)
Intuition: Nonhomogeneous equations in two variables split into three cases
Here too, let us first think in two variables (the $xy$ plane). A nonhomogeneous linear equation $ax+by=c$ ($c\neq0$) represents a general line, not necessarily passing through the origin. A system of two equations $\begin{cases}a_1x+b_1y=c_1\\a_2x+b_2y=c_2\end{cases}$ poses the question “how do two lines intersect?”, and there are three cases (Figure 9.6).
(i) The two lines meet at one point: exactly one solution (0 degrees of freedom). (ii) The two lines coincide completely: every point on the line is a solution (1 degree of freedom). (iii) The two lines are parallel but offset (they do not coincide): there is no common point, so there is no solution.
With three variables (the $xyz$ space), lines are replaced by planes, and the same three cases occur—the planes meet at a single point (0 degrees of freedom); the whole figure formed by their intersection (a line or a plane) is the set of solutions (the degrees of freedom are $>0$); or they do not intersect at all (no solution). In Example 9.6 below, let us actually work out a three-variable case.
Example 9.6: Existence of solutions and degrees of freedom for a nonhomogeneous system of linear equations
For the following nonhomogeneous system of linear equations, determine whether a solution exists, and if one exists, find all the solutions.
$$ \begin{cases} x_1+2x_2-x_3=2\\ 2x_1-x_2+3x_3=9\\ 4x_1+3x_2+x_3=13 \end{cases} $$Solution. The augmented matrix is $A_0=\left[\begin{array}{ccc|c}1&2&-1&2\\2&-1&3&9\\4&3&1&13\end{array}\right]$. We apply elementary row operations. If we apply $R_2\to R_2-2R_1$ ($2-2=0,-1-4=-5,3-(-2)=5,9-4=5$) and $R_3\to R_3-4R_1$ ($4-4=0,3-8=-5,1-(-4)=5,13-8=5$), we obtain
$$ \left[\begin{array}{ccc|c}1&2&-1&2\\2&-1&3&9\\4&3&1&13\end{array}\right] \to \left[\begin{array}{ccc|c}1&2&-1&2\\0&-5&5&5\\0&-5&5&5\end{array}\right] $$Next, applying $R_3\to R_3-R_2$ (entry by entry, $-5-(-5)=0,5-5=0,5-5=0$) and dividing the second row by $-5$, we obtain
$$ \left[\begin{array}{ccc|c}1&2&-1&2\\0&-5&5&5\\0&-5&5&5\end{array}\right] \to \left[\begin{array}{ccc|c}1&2&-1&2\\0&-5&5&5\\0&0&0&0\end{array}\right] \to \left[\begin{array}{ccc|c}1&2&-1&2\\0&-1&1&1\\0&0&0&0\end{array}\right] =A_0' $$The augmented matrix $A_0'$ has two nonzero rows, so $\rank A_0'=2$. On the other hand, the coefficient-matrix part $A'=\begin{bmatrix}1&2&-1\\0&-1&1\\0&0&0\end{bmatrix}$, obtained from $A_0'$ by removing the rightmost column (the column of $\bm b'$), also has two nonzero rows, so $\rank A'=2$. Since $\rank A'=\rank A_0'=2$, by Theorem 9.2 a solution exists. Since the degrees of freedom $=n-\rank A_0'=3-2=1$, the system has infinitely many solutions (one parameter).
The coefficient matrix $A=\begin{bmatrix}1&2&-1\\2&-1&3\\4&3&1\end{bmatrix}$ in this problem happens to be a square matrix, so the same conclusion can also be confirmed with the determinant. Actually computing $|A|$, we obtain
$$ |A|=1\cdot\begin{vmatrix}-1&3\\3&1\end{vmatrix}-2\cdot\begin{vmatrix}2&3\\4&1\end{vmatrix}+(-1)\cdot\begin{vmatrix}2&-1\\4&3\end{vmatrix}=1\cdot(-10)-2\cdot(-10)-1\cdot10=-10+20-10=0 $$Hence $|A|=0$ ($A$ is a singular matrix, $\rank A \lt 3$). This corresponds exactly to the result above, $\rank A'=2 \lt n=3$, and confirms that, because $A$ is not invertible (has no inverse matrix), the formula $\bm x=A^{-1}\bm b$ of Section 9.1 cannot be used, and the solution can be found only by Gaussian elimination (the “sweep-out” method).
Rewriting the equations from the row echelon matrix, we obtain
$$ \begin{cases} x_1+2x_2-x_3=2\\ -x_2+x_3=1 \end{cases} $$The free variable is $x_3$. Let $x_3=k$ ($k\in\R$). Then the second equation gives $-x_2+k=1$, that is, $x_2=k-1$. Substituting into the first equation gives $x_1+2(k-1)-k=2$, and hence $x_1=2-2(k-1)+k=2-2k+2+k=4-k$. Therefore
$$ \begin{cases}x_1=-k+4\\x_2=k-1\\x_3=k\end{cases}\qquad(k\in\R) $$describes all the solutions (one can also check that for $k=0$, $(4,-1,0)$ is one particular solution; it has been verified with SymPy that $A\bm x=\bm b$ holds for any $k$).
9.5 Solving Systems of Linear Equations by Gaussian Elimination (the Sweep-Out Method)
Combining the “existence condition for solutions” and the “classification of solutions by degrees of freedom” that we saw in the previous two sections gives a mechanical, easy-to-follow procedure (an algorithm) for actually solving a system of linear equations. This is called Gaussian elimination (also known as the sweep-out method, or Gauss's elimination method).
Theorem 9.3: Gaussian elimination
To solve a system of linear equations $A\bm x=\bm b$ (with $n$ unknowns), it suffices to reduce the augmented matrix $A_0=[\,A\mid\bm b\,]$ by elementary row operations to a row echelon matrix $A_0'=[\,A'\mid\bm b'\,]$. Let $\rank A'=r$ and $\rank A_0'=r_0$. Then the form of the solution falls into the following three cases.
$$ \begin{array}{lll} \text{(i)}&\text{exactly one solution (unique solution)}&r=r_0=n\quad(\text{degrees of freedom}=0)\\ \text{(ii)}&\text{infinitely many solutions (involving parameters)}&r=r_0 \lt n\quad(\text{degrees of freedom}=n-r_0\gt0)\\ \text{(iii)}&\text{no solution}&r \lt r_0\quad(\text{degrees of freedom are not defined in this case}) \end{array} $$Conclusion: When $\rank A' \lt \rank A_0'$ there is no solution, and when $\rank A'=\rank A_0'$ a solution exists. (The unique solution in (i) coincides with the trivial solution $\bm x=\bm 0$ of Section 9.3 only when $\bm b=\bm 0$ (the homogeneous equation). When $\bm b\neq\bm 0$ (the nonhomogeneous equation), even a unique solution is not $\bm x=\bm 0$—indeed, the solution $(x,y,z)=(1,2,-1)$ of Example 9.7 below is an example of this.)
Caution: Degrees of freedom are not defined when there is no solution
In case (iii), “no solution,” not a single solution exists to begin with, so the very concept of degrees of freedom (= the number of free parameters remaining in the solution) cannot be defined. In this book we do not define degrees of freedom in case (iii).
Intuition: Elementary row operations are really “adding and subtracting equations”
Elementary row operations—multiplying a row by a constant, adding a constant multiple of one row to another row, interchanging two rows—look abstract when written in the language of matrices, but when we go back to the original system of equations and read them there, they are essentially “nothing more than multiplying several conditions (= equations) by some factors and adding or subtracting them.” For example, the operation “add $-2\times$ the first equation to the second equation” is merely a rephrasing that makes one new equation from the $2$ equations, and it does not change the solution set represented by the system as a whole (from the original two equations we can make the new two equations, and conversely from the new two equations we can make the original two, so the two pairs are equivalent). Gaussian elimination is nothing other than a translation of this “adding and subtracting of equations” into the unified procedure of elementary row operations on matrices.
Example 9.7: Gaussian elimination (a unique solution)
Use Gaussian elimination to solve the following system of linear equations.
$$ \begin{bmatrix}2&3&1\\1&1&-1\\3&1&-1\end{bmatrix} \begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}7\\4\\6\end{bmatrix} $$Solution. The augmented matrix is $\left[\begin{array}{ccc|c}2&3&1&7\\1&1&-1&4\\3&1&-1&6\end{array}\right]$. Interchanging the first and second rows puts a $1$ in the upper left corner, which makes the subsequent calculations easier.
$$ \left[\begin{array}{ccc|c}2&3&1&7\\1&1&-1&4\\3&1&-1&6\end{array}\right] \xrightarrow{R_1\leftrightarrow R_2} \left[\begin{array}{ccc|c}1&1&-1&4\\2&3&1&7\\3&1&-1&6\end{array}\right] $$Sweep out the first column. Use $R_2\to R_2-2R_1$ ($2-2=0,3-2=1,1-(-2)=3,7-8=-1$) and $R_3\to R_3-3R_1$ ($3-3=0,1-3=-2,-1-(-3)=2,6-12=-6$).
$$ \left[\begin{array}{ccc|c}1&1&-1&4\\2&3&1&7\\3&1&-1&6\end{array}\right] \to \left[\begin{array}{ccc|c}1&1&-1&4\\0&1&3&-1\\0&-2&2&-6\end{array}\right] $$Next, sweep out the second column. Eliminate the second-column entry of the third row with $R_3\to R_3+2R_2$ ($-2+2=0,2+6=8,-6-2=-8$), and then eliminate the second-column entry of the first row as well with $R_1\to R_1-R_2$ ($1-1=0,-1-3=-4,4-(-1)=5$).
$$ \left[\begin{array}{ccc|c}1&1&-1&4\\0&1&3&-1\\0&-2&2&-6\end{array}\right] \xrightarrow{R_3\to R_3+2R_2} \left[\begin{array}{ccc|c}1&1&-1&4\\0&1&3&-1\\0&0&8&-8\end{array}\right] \xrightarrow{R_1\to R_1-R_2} \left[\begin{array}{ccc|c}1&0&-4&5\\0&1&3&-1\\0&0&8&-8\end{array}\right] $$Finally, sweep out the third column. First divide the third row by $8$ to make its leading entry $1$ ($R_3\to R_3/8$), and then use it to eliminate the third-column entries of the first and second rows: $R_1\to R_1+4R_3$ ($-4+4=0,5+4\cdot(-1)=1$) and $R_2\to R_2-3R_3$ ($3-3=0,-1-3\cdot(-1)=2$).
$$ \left[\begin{array}{ccc|c}1&0&-4&5\\0&1&3&-1\\0&0&8&-8\end{array}\right] \xrightarrow{R_3\to R_3/8} \left[\begin{array}{ccc|c}1&0&-4&5\\0&1&3&-1\\0&0&1&-1\end{array}\right] \to \left[\begin{array}{ccc|c}1&0&0&1\\0&1&0&2\\0&0&1&-1\end{array}\right] $$The rows have all reached the form $[1,0,0\mid{*}]$ (the identity matrix). Since $\rank A'=\rank A_0'=3=n$, the degrees of freedom are $0$, and there is exactly one solution, namely
$$ \begin{cases}x=1\\y=2\\z=-1\end{cases} $$(verified with SymPy's solver for systems of equations).
Example 9.8: Gaussian elimination (infinitely many solutions)
Use Gaussian elimination to solve the following system of linear equations.
$$ \begin{bmatrix}1&-2&4\\0&-1&-1\\-1&4&-2\end{bmatrix} \begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}3\\-1\\-1\end{bmatrix} $$Solution. The augmented matrix is $\left[\begin{array}{ccc|c}1&-2&4&3\\0&-1&-1&-1\\-1&4&-2&-1\end{array}\right]$. Since the entries of the first column other than the one in the first row are not yet all $0$, we clear it with $R_3\to R_3+R_1$ ($-1+1=0,4-2=2,-2+4=2,-1+3=2$).
$$ \left[\begin{array}{ccc|c}1&-2&4&3\\0&-1&-1&-1\\-1&4&-2&-1\end{array}\right] \xrightarrow{R_3\to R_3+R_1} \left[\begin{array}{ccc|c}1&-2&4&3\\0&-1&-1&-1\\0&2&2&2\end{array}\right] $$Sweep out the second column. With $R_3\to R_3+2R_2$ ($2-2=0,2-2=0,2-2=0$), the third row becomes entirely $0$.
$$ \left[\begin{array}{ccc|c}1&-2&4&3\\0&-1&-1&-1\\0&2&2&2\end{array}\right] \xrightarrow{R_3\to R_3+2R_2} \left[\begin{array}{ccc|c}1&-2&4&3\\0&-1&-1&-1\\0&0&0&0\end{array}\right] $$Divide the second row by $-1$ to make its leading entry $1$ ($R_2\to -R_2$), and use it to eliminate the second-column entry of the first row ($R_1\to R_1+2R_2$, $-2+2=0,4+2=6,3+2=5$).
$$ \left[\begin{array}{ccc|c}1&-2&4&3\\0&-1&-1&-1\\0&0&0&0\end{array}\right] \xrightarrow{R_2\to-R_2} \left[\begin{array}{ccc|c}1&-2&4&3\\0&1&1&1\\0&0&0&0\end{array}\right] \xrightarrow{R_1\to R_1+2R_2} \left[\begin{array}{ccc|c}1&0&6&5\\0&1&1&1\\0&0&0&0\end{array}\right] $$There are two nonzero rows, so $\rank A'=\rank A_0'=2 \lt n=3$. A solution exists, and the degrees of freedom $=3-2=1$ (infinitely many solutions). Converting back to equations, we have
$$ \begin{cases}x+6z=5\\y+z=1\end{cases} $$Setting the free variable $z=t$ ($t\in\R$), we get $x=5-6t$, $y=1-t$. Hence
$$ \begin{cases}x=5-6t\\y=1-t\\z=t\end{cases}\qquad(t\in\R) $$is the complete set of solutions.
Example 9.9: Gaussian elimination (no solution)
Use Gaussian elimination to solve the following system of linear equations.
$$ \begin{bmatrix}1&-2&4\\0&-1&-1\\-1&4&-2\end{bmatrix} \begin{bmatrix}x\\y\\z\end{bmatrix} = \begin{bmatrix}2\\-3\\0\end{bmatrix} $$Solution. The coefficient matrix is exactly the same as in Example 9.8, but note that the right-hand side $\bm b$ is different (it has changed from $(3,-1,-1)$ to $(2,-3,0)$). The augmented matrix is $\left[\begin{array}{ccc|c}1&-2&4&2\\0&-1&-1&-3\\-1&4&-2&0\end{array}\right]$. We carry out exactly the same elementary row operations as in Example 9.8 ($R_3\to R_3+R_1$, followed by $R_3\to R_3+2R_2$, $R_2\to-R_2$, and $R_1\to R_1+2R_2$), applying them to the right-hand-side column in the same way.
$$ \left[\begin{array}{ccc|c}1&-2&4&2\\0&-1&-1&-3\\-1&4&-2&0\end{array}\right] \xrightarrow{R_3\to R_3+R_1} \left[\begin{array}{ccc|c}1&-2&4&2\\0&-1&-1&-3\\0&2&2&2\end{array}\right] \xrightarrow{R_3\to R_3+2R_2} \left[\begin{array}{ccc|c}1&-2&4&2\\0&-1&-1&-3\\0&0&0&-4\end{array}\right] $$(The right end of the third row: $2+2\cdot(-3)=2-6=-4$. The coefficient part becomes $0$ for the same reason as in Example 9.8, but the constant on the right-hand side becomes $-4$, and this time it does not become $0$.) Continuing with $R_2\to-R_2$ and $R_1\to R_1+2R_2$, we obtain
$$ \left[\begin{array}{ccc|c}1&-2&4&2\\0&-1&-1&-3\\0&0&0&-4\end{array}\right] \to \left[\begin{array}{ccc|c}1&0&6&8\\0&1&1&3\\0&0&0&\mathbf{-4}\end{array}\right] $$The third row means $0\cdot x+0\cdot y+0\cdot z=-4$. No matter what values of $x,y,z$ we substitute, the left-hand side can only be $0$, yet the right-hand side is $-4\,(\neq0)$. This is a contradiction (an inconsistent equation), and no real numbers $x,y,z$ satisfy it. In fact, $\rank A'=2$ (the coefficient part has two nonzero rows), whereas $\rank A_0'=3$ (the augmented matrix has three nonzero rows; the last row is also counted, since its $\bm b'$ side is nonzero), and since $\rank A' \lt \rank A_0'$, by Theorem 9.3(iii) there is no solution.
9.6 Finding Inverse Matrices, Conditions for Invertibility, and the Normal Form
In Section 9.1 we found the inverse matrix by the formula $A^{-1}=\frac{1}{|A|}\tilde A$, which uses the adjugate matrix. This method is easy to follow because we “just plug into a formula,” but as $n$ grows, the amount of computation for the cofactors explodes (computing a single cofactor of a matrix of order $n$ requires a determinant of order $(n-1)$, and we need $n^2$ of them). Here we learn a more practical way of finding inverse matrices, one that applies the Gaussian elimination (the sweep-out method) of Section 9.5.
Theorem 9.4: Finding the inverse matrix (by Gaussian elimination)
Let $A$ be a square matrix of order $n$. Place the identity matrix $E$ of the same size to the right of $A$ to form the matrix $[\,A\mid E\,]$ of type $(n,2n)$, apply elementary row operations to it, and sweep out until the left half, the part $A$, becomes exactly the identity matrix $E$.
$$ [\,A\mid E\,]\ \xrightarrow{\text{elementary row operations}}\ [\,E\mid B\,] $$Then the matrix $B$ that appears in the right half is the inverse matrix of $A$: $B=A^{-1}$. (The condition for this sweeping out to be carried through to the end—that is, for the left half to be turned into the identity matrix $E$—is that $A$ be invertible. We discuss this in detail in Theorem 9.5 below.)
Why does this method give the inverse matrix?
Each of the three kinds of elementary row operations has the same effect as “multiplying on the left by some invertible matrix” (for example, the operation “add $c$ times the first row to the second row” gives the same result as multiplying on the left by a matrix $P$ that is close to the identity matrix, with $c$ inserted only in the corresponding position. We call such a $P$ an elementary matrix). Suppose that we reach $[\,E\mid B\,]$ from $[\,A\mid E\,]$ by repeating elementary row operations $m$ times, and let $P_1,P_2,\ldots,P_m$ be the corresponding elementary matrices (in the order in which the operations were performed). Then for the left half we have
$$ P_m\cdots P_2P_1A=E $$This says precisely that “$P_m\cdots P_2P_1$ is the inverse matrix of $A$” (it is just the definition of the inverse matrix). As for the right half, since we apply the same elementary matrices to the identity matrix $E$, we obtain
$$ P_m\cdots P_2P_1E=P_m\cdots P_2P_1=B $$and hence $B=P_m\cdots P_2P_1=A^{-1}$. In other words, the mechanism is this: if we apply “the sequence of operations that changes $A$ into the identity matrix” in the same order to the place that was the identity matrix from the start, then $A^{-1}$ is produced there automatically.
Example 9.10: Computing an inverse matrix by Gaussian elimination
Find the inverse matrix of $A=\begin{bmatrix}1&1&1\\1&2&3\\1&3&6\end{bmatrix}$ by using $[\,A\mid E\,]$.
Solution. $[\,A\mid E\,]=\left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\1&2&3&0&1&0\\1&3&6&0&0&1\end{array}\right]$. We sweep out the first column. $R_2\to R_2-R_1$ ($1-1=0,2-1=1,3-1=2,0-1=-1,1-0=1,0-0=0$), $R_3\to R_3-R_1$ ($1-1=0,3-1=2,6-1=5,0-1=-1,0-0=0,1-0=1$).
$$ \left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\1&2&3&0&1&0\\1&3&6&0&0&1\end{array}\right] \to \left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\0&1&2&-1&1&0\\0&2&5&-1&0&1\end{array}\right] $$Next we sweep out the second column. $R_3\to R_3-2R_2$ ($2-2=0,5-4=1,-1-(-2)=1,0-2=-2,1-0=1$).
$$ \left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\0&1&2&-1&1&0\\0&2&5&-1&0&1\end{array}\right] \xrightarrow{R_3\to R_3-2R_2} \left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\0&1&2&-1&1&0\\0&0&1&1&-2&1\end{array}\right] $$At this point the left half has become upper triangular (everything below the diagonal is $0$). From here we sweep out from the bottom upward. First we use the third row to eliminate the third-column entries of the second and first rows. $R_2\to R_2-2R_3$ ($2-2=0,-1-2=-3,1-2\cdot(-2)=1+4=5,0-2=-2$), $R_1\to R_1-R_3$ (not $1-1=0,1-1=0,1-1=0,-1$ but $1-1=0$; for the constant terms, $1-1=0,0-(-2)=2,0-1=-1$).
$$ \left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\0&1&2&-1&1&0\\0&0&1&1&-2&1\end{array}\right] \xrightarrow{R_2\to R_2-2R_3} \left[\begin{array}{ccc|ccc}1&1&1&1&0&0\\0&1&0&-3&5&-2\\0&0&1&1&-2&1\end{array}\right] \xrightarrow{R_1\to R_1-R_3} \left[\begin{array}{ccc|ccc}1&1&0&0&2&-1\\0&1&0&-3&5&-2\\0&0&1&1&-2&1\end{array}\right] $$Finally, we use the second row to eliminate the second-column entry of the first row. $R_1\to R_1-R_2$ ($1-1=0,0-(-3)=3,2-5=-3,-1-(-2)=1$).
$$ \left[\begin{array}{ccc|ccc}1&1&0&0&2&-1\\0&1&0&-3&5&-2\\0&0&1&1&-2&1\end{array}\right] \xrightarrow{R_1\to R_1-R_2} \left[\begin{array}{ccc|ccc}1&0&0&3&-3&1\\0&1&0&-3&5&-2\\0&0&1&1&-2&1\end{array}\right] $$Since the left half has become the identity matrix $E$, the right half is $A^{-1}$.
$$ A^{-1}=\begin{bmatrix}3&-3&1\\-3&5&-2\\1&-2&1\end{bmatrix} $$($A\cdot A^{-1}=E$ was verified with SymPy. In fact, since $|A|=1$, computing the adjugate matrix directly with Formula 9.1 gives the same result.)
Theorem 9.5: Conditions for invertibility of a matrix
For a square matrix $A$ of order $n$, the following three conditions are equivalent (if any one of them holds, the other two hold as well).
$$ \text{“$A$ is invertible ($|A|\neq0$, it has an inverse matrix)”}\iff\text{“$\rank A=n$”}\iff\text{“the row echelon matrix of $A$ is the identity matrix $E_n$”} $$Therefore, in the language of Section 9.3, “$A$ is invertible” $\iff$ “the homogeneous system of linear equations $A\bm x=\bm0$ has $0$ degrees of freedom” $\iff$ “$A\bm x=\bm 0$ has only the trivial solution” are also equivalent. Conversely, when $A$ is not invertible ($|A|=0$, $\rank A \lt n$), we call $A$ a singular matrix; in that case, in the course of Gaussian elimination some row necessarily becomes entirely $0$, and we cannot sweep out $[\,A\mid E\,]$ all the way to the form $[\,E\mid B\,]$ (a row of $0$s appears in the left half, so we cannot reach the identity matrix).
9.6.1 Normal form
Besides elementary row operations, we can also consider operations that do the same job on the columns of a matrix.
Definition 9.5: Elementary column operation
The operations obtained by applying, to the columns of a matrix, exactly the same three kinds of operations as the elementary operations on rows—(i) multiplying a column by a constant that is not $0$, (ii) adding a constant multiple of another column to a column, (iii) interchanging two columns—are called elementary column operations.
Using elementary row operations alone, we could bring any matrix to a row echelon matrix; if we then also use elementary column operations, we can go further, to an ultimate form that is even simpler than a row echelon matrix.
Definition 9.6: Normal form
If we use both elementary row operations and elementary column operations on a matrix $A$ of type $(m,n)$, we can transform it into the following form, in which the identity matrix $I_r$ of size $r\times r$ ($r=\rank A$) appears in the upper left and all other entries are $0$. We call this the normal form of $A$.
$$ \begin{bmatrix}I_r&O\\O&O\end{bmatrix} $$($I_r$ is the identity matrix of order $r$, and each $O$ is a zero matrix of the appropriate size. The number of $1$s in the normal form is exactly equal to $\rank A$.)
Example 9.11: Finding the normal form
Find the normal form of $A=\begin{bmatrix}1&2&0&2\\3&6&2&4\\2&4&1&3\end{bmatrix}$.
Solution. First we bring the matrix to a row echelon matrix by elementary row operations. $R_2\to R_2-3R_1$ ($3-3=0,6-6=0,2-0=2,4-6=-2$), $R_3\to R_3-2R_1$ ($2-2=0,4-4=0,1-0=1,3-4=-1$).
$$ \begin{bmatrix}1&2&0&2\\3&6&2&4\\2&4&1&3\end{bmatrix} \to \begin{bmatrix}1&2&0&2\\0&0&2&-2\\0&0&1&-1\end{bmatrix} $$If we apply $R_2\to R_2-2R_3$ ($2-2=0,-2-(-2)=0$), the second row becomes all $0$.
$$ \begin{bmatrix}1&2&0&2\\0&0&2&-2\\0&0&1&-1\end{bmatrix} \xrightarrow{R_2\to R_2-2R_3} \begin{bmatrix}1&2&0&2\\0&0&0&0\\0&0&1&-1\end{bmatrix} $$To collect the rows that are all $0$ at the bottom, we interchange the second and third rows by $R_2\leftrightarrow R_3$.
$$ \begin{bmatrix}1&2&0&2\\0&0&0&0\\0&0&1&-1\end{bmatrix} \xrightarrow{R_2\leftrightarrow R_3} \begin{bmatrix}1&2&0&2\\0&0&1&-1\\0&0&0&0\end{bmatrix} $$Since there are two nonzero rows, $\rank A=2$. What we have so far is a row echelon matrix obtained by elementary row operations alone. From here we proceed to the normal form by using elementary column operations. The pivot of the first row is in the first column and that of the second row is in the third column, so we first interchange the second and third columns to move the pivots to the left ($C_2\leftrightarrow C_3$).
$$ \begin{bmatrix}1&2&0&2\\0&0&1&-1\\0&0&0&0\end{bmatrix} \xrightarrow{C_2\leftrightarrow C_3} \begin{bmatrix}1&0&2&2\\0&1&0&-1\\0&0&0&0\end{bmatrix} $$Finally, we eliminate the remaining nonzero entries (the $2$ in the first row and third column, the $2$ in the first row and fourth column, and the $-1$ in the second row and fourth column) by elementary column operations. $C_3\to C_3-2C_1$ ($2-2\cdot1=0$; in the other rows, $0-2\cdot0=0$), $C_4\to C_4-2C_1$ ($2-2=0$; the second row stays $-1-2\cdot0=-1$), and then $C_4\to C_4+C_2$ (first row $0+0=0$, second row $-1+1=0$).
$$ \begin{bmatrix}1&0&2&2\\0&1&0&-1\\0&0&0&0\end{bmatrix} \xrightarrow[C_4\to C_4-2C_1]{C_3\to C_3-2C_1} \begin{bmatrix}1&0&0&0\\0&1&0&-1\\0&0&0&0\end{bmatrix} \xrightarrow{C_4\to C_4+C_2} \begin{bmatrix}1&0&0&0\\0&1&0&0\\0&0&0&0\end{bmatrix} $$This is the normal form of $A$; the identity matrix $I_2$ of size $2\times2$ ($=\rank A$) appears in the upper left (it has the form $\begin{bmatrix}I_2&O\\O&O\end{bmatrix}$).
9.7 Summary and Exercises
9.7.1 Summary
- The adjugate matrix $\tilde A$ (the transpose of the matrix whose entries are the cofactors) and the inverse matrix formula $A^{-1}=\dfrac{1}{|A|}\tilde A$. The heart of the proof was this single point: “each diagonal entry is the cofactor expansion of the determinant itself, while each off-diagonal entry becomes a ‘determinant with two identical rows (columns)’ and hence equals $0$.”
- Rank: the number of nonzero rows of the row echelon matrix obtained by elementary row operations. $0\le\rank A\le\min(m,n)$.
- Degrees of freedom $=n-\rank A$ (homogeneous case) or $n-\rank A_0'$ (nonhomogeneous case in which a solution exists). The degrees of freedom represent “the number of parameters that can be chosen freely in the solution.”
- Homogeneous system of linear equations $A\bm x=\bm0$: if the degrees of freedom $=0$, only the trivial solution exists; if the degrees of freedom $>0$, nontrivial solutions also exist. For $n$ variables, the geometric picture of the solutions grows from a point (0 degrees of freedom) to a line (1 degree of freedom) to a plane (2 degrees of freedom), and so on.
- Nonhomogeneous system of linear equations $A\bm x=\bm b$: if $\rank A'<\rank A_0'$ there is no solution; if $\rank A'=\rank A_0'$ a solution exists, and the degrees of freedom in that case distinguish a unique solution from infinitely many solutions.
- Gaussian elimination (the “sweep-out” method): simply reducing the augmented matrix $[A\mid\bm b]$ to a row echelon matrix by elementary row operations gives, at the same time, both the three-way classification of the solutions (unique solution, infinitely many solutions, no solution) and the explicit form of the solutions.
- Finding the inverse matrix: $[\,A\mid E\,]\xrightarrow{\text{elementary row operations}}[\,E\mid A^{-1}\,]$. Conditions for invertibility: “$A$ is invertible” $\iff$ “$\rank A=n$” $\iff$ “the row echelon matrix is $E_n$.”
- Normal form: using both elementary row operations and elementary column operations, any matrix can be brought to the form $\begin{bmatrix}I_r&O\\O&O\end{bmatrix}$ ($r=\rank A$).
9.7.2 Exercises
Exercise 9.1: Finding the inverse matrix using the adjugate matrix
For $A=\begin{bmatrix}3&1&-1\\1&2&0\\0&1&1\end{bmatrix}$, find the adjugate matrix $\tilde A$, and then use Formula 9.1 to find the inverse matrix $A^{-1}$.
Hint: Follow the same procedure as in Example 9.1: compute all nine cofactors $A_{11},\ldots,A_{33}$ first, and then transpose. For $|A|$, it suffices to expand along the first row.
Exercise 9.2: Degrees of freedom and solutions of a homogeneous system of linear equations in four unknowns
Find the degrees of freedom of the following homogeneous system of linear equations, and find all of its solutions.
$$ \begin{cases} x_1+x_2-x_3+2x_4=0\\ 2x_1+x_2+x_3+x_4=0\\ x_1-x_2+5x_3-5x_4=0\\ 3x_1+2x_2+3x_4=0 \end{cases} $$Hint: Reducing the coefficient matrix to a row echelon matrix by elementary row operations leaves three nonzero rows ($\rank=3$). There is one free variable (degrees of freedom $4-3=1$). As in Example 9.4, set the free variable equal to $t$ and express the other variables in terms of $t$.
Exercise 9.3: Condition for the existence of solutions of a nonhomogeneous system containing a parameter
Let $k$ be a constant, and consider the following system of linear equations.
$$ \begin{cases} x_1+2x_2-x_3=2\\ 2x_1-x_2+3x_3=9\\ 4x_1+3x_2+x_3=k \end{cases} $$For what values of $k$ does this system of linear equations have a solution? Also find all the solutions in that case.
Hint: The coefficient matrix on the left-hand side is the same as the one used in Example 9.6 and Example 9.9, and $\rank A'=2$ (always). When the augmented matrix is swept out, an expression containing $k$ remains at the right end of the last row. Find the condition under which it becomes $0$.
Exercise 9.4: Solving a system of linear equations in four unknowns by Gaussian elimination
Use Gaussian elimination (the “sweep-out” method) to solve the following system of linear equations.
$$ \begin{bmatrix}1&1&0&1\\2&1&1&0\\0&1&2&1\\1&0&1&2\end{bmatrix} \begin{bmatrix}x_1\\x_2\\x_3\\x_4\end{bmatrix} = \begin{bmatrix}6\\3\\3\\6\end{bmatrix} $$Hint: As in Example 9.7, first sweep out the first column, and then sweep out the second and third columns in turn. To keep the coefficients from growing large, put off division as long as possible and carry out the elimination while keeping all the entries integers.
Exercise 9.5: Finding the normal form
Find the normal form of $A=\begin{bmatrix}1&2&0&-1\\2&4&1&1\\3&6&1&0\end{bmatrix}$.
Hint: Follow the same procedure as in Example 9.11. First reduce the matrix to a row echelon matrix by elementary row operations (you will find $\rank A=2$). Next, swap columns so that the pivot columns move to the left, and then eliminate the remaining nonzero entries by elementary column operations.
Exercise 9.6: Testing invertibility by the rank and, if the matrix is invertible, finding its inverse
For $A=\begin{bmatrix}1&2&1\\0&1&3\\2&3&4\end{bmatrix}$, find $\rank A$ and determine whether $A$ is invertible. If it is invertible, find the inverse matrix $A^{-1}$ (you may use either method, the adjugate matrix or Gaussian elimination).
Hint: Reduce the matrix to a row echelon matrix by elementary row operations and count the nonzero rows. If all $n=3$ rows are nonzero, then the matrix is invertible by Theorem 9.5.
9.7.3 References
- Yasuhide Mochizuki, Mathematics Notes: Linear Algebra (handwritten lecture notes, in Japanese). The source of this chapter.
- Masahiko Saito, Senkei Daisū Nyūmon [Introduction to Linear Algebra], University of Tokyo Press, 1966 (in Japanese).
- Ichiro Satake, Senkei Daisūgaku [Linear Algebra], Shōkabō, 1958 (in Japanese).
Related simulator: What the determinant represents (area, volume, rank, degrees of freedom)