Each Section and Topic title are links. At the end of each section, there is a link back to this table.
- 1.2.1 Coefficient Matrices
- 1.2.2 Partition Matrices
- 1.2.3 Elementary Row Operations
- 1.2.4 Some Special Matrices
- 1.2.5 Gauss-Jordan Elimination
- 1.2.6 Row Echelon Form
- 1.2.7 Backward Substitution
- 1.2.8 Reduced Row Echelon Form
- 1.2.9 Homogeneous Linear Systems
- 1.2.10 Exercises
- copyleft
1.2.1 Coefficient Matrices 
Simplifying Notation¶
We introduced linear systems in Section 1.1 Systems of Linear Equations. A linear system consists of $m$ linear equations containing $n$ unknowns or variables. This is called an $m\times n$ linear system. If you arrange all the terms with variables on the left-hand side of each equation and any remaining constant term on the right-hand side of each equation, the linear system is represented in standard form.
$$ \begin{array}{rcl} a_{11}x_1 + a_{12}x_2 +\ \cdots\ + a_{1n}x_n & = & b_1 \\ a_{21}x_1 + a_{22}x_2 +\ \cdots\ + a_{2n}x_n & = & b_2 \\ \\ \ddots\, \ \ +\ \ \ddots\, \ \ +\ \cdots\ +\ \ \ \ddots\, & = & \vdots \\ \\ a_{m1}x_1 + a_{m2}x_2 +\ \cdots + a_{mn}x_n & = & b_m \end{array} $$
Let us consider such a system.
Example 1 - Matrix Equations¶
$$ \begin{array}{rcl} -2x_2 - 2x_3 + 2x_4 & = &\ \ 0 \\ x_3 +\ \ x_2 +\ \ x_1 +\ \ x_4 & = &\ \ 6 \\ 4x_2 - 2x_4 +\ \ x_3 + 2x_1 & = & -1 \\ 2x_4 + 3x_1 +\ \ x_2 - 2x_3 & = &\ \ 3 \end{array} $$
Representing a linear system of equations in standard form is also called the row picture. In this example, each row is a linear equation in $4$-dimensional space; four dimensional because there are four separate variables (We can't draw this one). The row picture is very useful, and we will represent many linear systems in this form.
To the mathematician in all of us, this is still too much to write if we need to perform several operations on our equations. This is also not an efficient way to represent a linear system in a computer. We need to organize the linear system better. Let us arrange the terms of each equation so that the variables in each term appear in the same order.
$$ \begin{array}{rcl} -2x_2 - 2x_3 + 2x_4 & = &\ \ 0 \\ x_1 +\ \ x_2 +\ \ x_3 +\ \ x_4 & = &\ \ 6 \\ 2x_1 + 4x_2 +\ \ x_3 - 2x_4 & = & -1 \\ 3x_1 +\ \ x_2 - 2x_3 + 2x_4 & = &\ \ 3 \end{array} $$
This allows us to group columns of terms together.
$$ \begin{bmatrix} \ 0\ \\ \ x_1\ \\ \ 2x_1\ \\ \ 3x_1\ \end{bmatrix} + \begin{bmatrix} -2x_2 \\ \ \ x_2 \\ \ \ 4x_2 \\ \ \ x_2 \end{bmatrix} + \begin{bmatrix} -2x_3 \\ \ \ x_3 \\ \ \ x_3 \\ -2x_3 \end{bmatrix} + \begin{bmatrix}\ 2x_4 \\ \ \ x_4 \\ -2x_4 \\ \ \ 2x_4 \end{bmatrix} = x_1\begin{bmatrix} \ 0\ \\ \ 1\ \\ \ 2\ \\ \ 3\ \end{bmatrix} + x_2\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 4 \\ \ \ 1 \end{bmatrix} + x_3\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 1 \\ -2 \end{bmatrix} + x_4\begin{bmatrix}\ \ 2 \\ \ \ 1 \\ -2 \\ \ \ 2 \end{bmatrix} = \begin{bmatrix}\ \ 0 \\ \ \ 6 \\ -1 \\ \ \ 3 \end{bmatrix} $$
Now the equation has scalar variables multiplied by vectors in our $4$-dimensional space.
Definition (One of the Top Five Definitions in this class!)¶
The result of multiplying vectors by scalars and adding the scaled vectors is called a Linear Combination.
To be clear, the linear combination in our example is given by
$$ x_1\begin{bmatrix} \ 0\ \\ \ 1\ \\ \ 2\ \\ \ 3\ \end{bmatrix} + x_2\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 4 \\ \ \ 1 \end{bmatrix} + x_3\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 1 \\ -2 \end{bmatrix} + x_4\begin{bmatrix}\ \ 2 \\ \ \ 1 \\ -2 \\ \ \ 2 \end{bmatrix} $$
We can make our notation even more compact if we pack the vectors together into a matrix, and define matrix-vector multiplication to be this linear combination
Definition¶
A matrix is a rectangular array of numbers (scalars or other mathematical objects) called the entries of the matrix. Matrices whose elements are real numbers, $\mathbb{R}$, or complex numbers, $\mathbb{C}$, are called real matrices or complex matrices, respectively. Entries in a matrix are also called its elements.
The size of a matrix refers to the number of rows and columns. The number of rows, and columns, of a matrix are called the dimensions of the matrix. A matrix with $m$ rows and $n$ columns is called an $m\times n$ matrix, or $m$-by-$n$ matrix. An $m\times n$ matrix has $m\cdot n$ elements.
It is customary to denote matrices with a capital letter, and the elements by the corresponding lower-case letter. Hence if matrix $A$ is an $m\times n$ matrix, then the elements of matrix $A$ are denoted $a_{ij}$, where $i$ is the row index and $j$ is the column index.
In our example we pack the vectors in our linear system into matrix $A$:
$$ A = \begin{bmatrix} 0 & -2 & -2 & \ \ 2 \\ 1 & \ \ 1 & \ \ 1 &\ \ 1 \\ 2 &\ \ 4&\ \ 1& -2 \\ 3 &\ \ 1 & -2 &\ \ 2 \end{bmatrix}, $$
Definition¶
Multiplication of an $m\times n$ matrix $A$ on-the-right by an $n\times 1$ vector $\mathbf{x}$ is defined by the linear combination of columns of matrix $A$.
$$ A\mathbf{x} = \begin{bmatrix} \mathbf{a}_1 & \mathbf{a}_2 & \cdots & \mathbf{a}_n \end{bmatrix} \begin{bmatrix} x_1 \\ x_2 \\ \vdots \\ x_n \end{bmatrix} = x_1\mathbf{a}_1 + x_2\mathbf{a}_2 + \cdots + x_n\mathbf{a}_n, $$
where $\mathbf{a}_j$ is the $j^{\text{th}}$ column vector of matrix $A$, $1\le j\le n$.
$$ \begin{bmatrix} 0 & -2 & -2 & \ \ 2 \\ 1 & \ \ 1 & \ \ 1 &\ \ 1 \\ 2 &\ \ 4&\ \ 1& -2 \\ 3 &\ \ 1 & -2 &\ \ 2 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} := x_1\begin{bmatrix} \ 0\ \\ \ 1\ \\ \ 2\ \\ \ 3\ \end{bmatrix} + x_2\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 4 \\ \ \ 1 \end{bmatrix} + x_3\begin{bmatrix} -2 \\ \ \ 1 \\ \ \ 1 \\ -2 \end{bmatrix} + x_4\begin{bmatrix}\ \ 2 \\ \ \ 1 \\ -2 \\ \ \ 2 \end{bmatrix} $$
If we substitute our new matrix-vector multiplication into our equation we obtain the matrix equation:
$$ \begin{bmatrix} 0 & -2 & -2 & \ \ 2 \\ 1 & \ \ 1 & \ \ 1 &\ \ 1 \\ 2 &\ \ 4&\ \ 1& -2 \\ 3 &\ \ 1 & -2 &\ \ 2 \end{bmatrix}\begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix} $$
We call the matrix in our matrix-vector multiplication the coefficient matrix because the elements of the matrix are the coefficients of the variables from the system of linear equations. We will use capital letters to represent matrices, lower case letters in bold to represent vectors and Greek and Latin alphabet letters to represent scalars. We only use this convention so that our linear algebra equations will be easy to read.
We name our vector of variables $\mathbf{x}$:
$$ \mathbf{x} = \begin{bmatrix} x_1 \\ x_2 \\ x_3 \\ x_4 \end{bmatrix} $$
We name our vector of constants on the right-hand side of the equation vector $\mathbf{b}$
$$ \mathbf{b} = \begin{bmatrix} b_1 \\ b_2 \\ b_3 \\ b_4 \end{bmatrix} $$
Our equation becomes
$$ A\mathbf{x} = \mathbf{b}. $$
1.2.2 Partition Matrices
A Clever Partition¶
In order to solve linear systems of equations it will be necessary to perform several operations on the linear system to get the system of linear equations into a form that reveals its important properties. We want to write the system as efficiently as possible so that we can avoid repetitive and unnecessary writing. We also need an efficient representation so that we can represent the linear system in a computer. To meet these goals, we partition the coefficient matrix and the constant vector on the right-hand side of the matrix equation,
$$ A\mathbf{x} = \mathbf{b} \longrightarrow \begin{bmatrix}\ A & | & \mathbf{b}\ \end{bmatrix}$$
into a single matrix, that is a matrix constructed from two or more submatrices.
Definition¶
A matrix constructed from separate matrices whose dimensions match so that gluing them together results in a well-formed matrix. The augmented matrix of a linear system is a partition matrix.
Deconstructing a matrix into smaller, non-overlapping blocks partitions the matrix.
The matrices used to create a partition matrix, or the non-overlapping blocks of a matrix are called submatrices.
For the linear system of equations,
$$\begin{array}{rcl} -\ 2x_2 - 2x_3 + 2x_4 & = &\ \ 0 \\ x_1 +\ \ x_2 +\ \ x_3 +\ \ x_4 & = &\ \ 6 \\ 2x_1 + 4x_2 +\ \ x_3 - 2x_4 & = & -1 \\ 3x_1 +\ \ x_2 - 2x_3 + 2x_4 & = &\ \ 3 \end{array}, $$
we partition the coefficient matrix $A$ and the vector $\mathbf{b}$ to obtain the augmented matrix:
$$ A = \left[ \begin{array}{cccc}\ \ 0 & -2 & -2 & \ \ 2 \\ 1 & \ \ 1 & \ \ 1 &\ \ 1 \\ 2 &\ \ 4 &\ \ 1 & -2 \\ 3 &\ \ 1 & -2 &\ \ 2 \end{array} \right]\text{ and }\mathbf{b} = \begin{bmatrix}\ \ 0 \\ \ \ 6 \\ -1 \\ \ \ 3 \end{bmatrix} $$
into an augmented matrix for the linear system of equations.
Definition¶
The augmented matrix of a linear system of equations $A\mathbf{x}=\mathbf{b}$ is the partition matrix $B = \begin{bmatrix}\ A & | & \mathbf{b}\ \end{bmatrix}$.
$$ \begin{bmatrix}\ A & | & \mathbf{b}\ \end{bmatrix} = \left[\begin{array}{cccc|c} 0 & -2 & -2 & \ \ 2 &\ \ 0 \\ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] $$
The vertical bar reminds us that the augmented matrix consists of the coefficient matrix and the constant vector.
Exercise 1 - Augmented Matrix¶
Given the following linear system of equations
$$ \begin{align*} 6x + 3y + 9z + 9w &= 48 \\ 8x - 8y + 9z\,\ \ \ \ \ \ \ \ \ &= -14 \\ -7x - 4y - 7z + 6w &= -1 \\ 8x +\ \ y + 9z - 7w &= -8 \end{align*} $$
write down the augmented matrix in one step.
View Solution
$$\left[\begin{array}{cccc|c}\ \ 6 &\ \ 3 &\ \ 9&\ \ 9 &\ \ 48 \\ \ \ 8 & -8 &\ \ 9 &\ \ & -14 \\ -7 & -4 & -7 &\ \ 6 & -1 \\ \ \ 8 &\ \ 1 &\ \ 9 & -7 & -8 \end{array} \right] $$
Exercise 2 - System of Equations¶
Given the following augmented matrix
$$ A = \left[ \begin{array}{ccccc|c} \ \ 2 &\ \ 1 & -1 &\ \ 3 &\ \ 1 &\ \ 8 \\ \ \ 1 &\ \ 3 &\ \ 2 & -1 &\ \ 2 & 13 \\ -1 &\ \ 2 &\ \ 4 &\ \ 1 & -1 &\ \ 9 \\ \ \ 3 & -1 &\ \ 1 &\ \ 2 &\ \ 4 & 16 \\ \ \ 1 &\ \ 1 &\ \ 2 &\ \ 1 &\ \ 3 & 14 \end{array} \right] $$
write down the linear system of equations with variables $x_1$, $x_2$, $x_3$, $x_4$ and $x_5$ in one step.
View Solution
$$\begin{align*} 2x_1 +\ \ x_2 -\ \ x_3 + 3x_4 +\ \ x_5 &= 8 \\ x_1 + 3x_2 + 2x_3 -\ \ x_4 + 2x_5 &= 13 \\ -x_1 + 2x_2 + 4x_3 +\ \ x_4 -\ \ x_5 &= 9 \\ x_1 +\ \ x_2 + 2x_3 +\ \ x_4 + 3x_5 &= 14 \end{align*}$$
1.2.3 Elementary Row Operations
Video Lecture 1: Elimination with Matrices.¶
Video Lecture 1: Elimination with MatricesThe augmented matrix is a very dense representation of a system of linear equations. It is useful for a computer because it needs only store the array of numbers
$$ \left[\, A \,|\, \mathbf{b} \,\right] = \left[ \begin{array}{ccccc} 0 & -2 & -2 & \ \ 2 &\ \ 0 \\ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array} \right] $$
Notice the lack of the dashed vertical bar that we use to remind us that this is a partition matrix. The computer has no concept of what this array of numbers represents. You give the array of numbers meaning. You know that the array of numbers represents a linear system of equations. In applications You decide that your physical or abstract model is represented by your linear systems of equations. You decide what the solution to the system of linear equations implies about the state of your physical or abstract model.
Remember that each row of the augmented matrix represents one of the equations in the linear system. Every operation performed on the equations in 
Section 1.1 can be performed using a row upon the augmented matrix.
Elementary Operations
- Interchange two equations
- Multiply an equation on both sides by a nonzero number
- Add a multiple of one equation to another equation
This gives us three elementary row operations we can perform on our augmented matrix that results in the augmented matrix of an equivalent augmented matrix. Remember an equivalent system of linear equations is not precisely the same linear system, but the equivalent system has exactly the same set of solutions. The three elementary row operations are
Type I Elementary Row Operation¶
The first elementary row operation we can perform on an augmented or coefficient matrix results in interchanging two equations by interchanging two rows. It will become expedient for us to arrange for a small positive integer coefficient (1) to appear as the coefficient of the first variable in the first row (equation). However in our example we have
$$ \left[\begin{array}{cccc|c}\ \ 0 & -2 & -2 & \ \ 2 &\ \ 0 \\ \ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] $$
The most utilitarian leading coefficient in the first column is coefficient $1$ in row $2$. We use a Type I Elementary Row Operation to switch row one and row two (equation one and equation two). We can also show our work and describe our row operation with some notation:
$$ \left[\begin{array}{cccc|c}\ \ 0 & -2 & -2 & \ \ 2 &\ \ 0 \\ \ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] \begin{array}{c} R_2 \\ R_1 \\ \\ \\ \end{array} \longrightarrow \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 & -2 & -2 &\ \ 2 &\ \ 0 \\ \ \ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] $$
We noted that row 1 would become row 2 ($R_2$), and row two would become row 1 ($R_1$), then illustrated the result of the type I row operation. Notice that the order of the appearance of the equations has no effect on the solution to either linear system. This resulting system of linear equations is not exactly the same as the previous system but has the same set of solutions.
Type II Elementary Row Operation¶
How else might we simplify our linear system? Notice that all of the coefficients in our new row two, including the last entry that represents the right-hand side of our matrix equation, are all even. A Type II Elementary Row Operation multiplies one row (both sides of an equation) by a nonzero number such as negative one-half. Multiplying row two by negative one-half will simplify our subsequent computations.
$$ \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 & -2 & -2 &\ \ 2 &\ \ 0 \\ \ \ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] \begin{array}{c} \\ -\frac{R_2}{2} \\ \\ \\ \end{array} \longrightarrow \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 &\ \ 1 &\ \ 1 & -1 &\ \ 0 \\ \ \ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] $$
We denote that row two will be replaced with minus one-half of row two; and record the result of the type II row operation. As in a type I row operation, multiplying both sides of an equation by a nonzero constant has no effect on the graph of the equation; and it has no effect on the solutions to the linear system. When we multiplied both sides of equation two by a nonzero constant, the equation remained an equality. As a result, the same set of values for $x_1$, $x_2$, $x_3$, and $x_4$ solve the equation. This means that the equations
$$ -2x_2 - 2x_3 + 2x_4 = 0,\text{ and }x_2 + x_3 - x_4 = 0 $$
have the same graph, and hence intersect the other graphs at the same set of points (solutions). We say that the solution set has been preserved by these row operations.
Type III Elementary Row Operations¶
Ultimately we want to eliminate the first variable from all of the equations after the first one. We attain this goal by adding a multiple of row one to the rows beneath it so that the coefficients will be zeros. For example if we add $-2$ times equation one to equation three,
$$ \begin{array}{rcl} (-2)(\ \ \,x_1 +\ \ x_2 +\ \ x_3 +\ \ x_4) & = & (-2)6 \\ 2x_1 + 4x_2 +\ \ x_3 - 2x_4\, & = & -1 \\ \hline 2x_2 -\ \ x_3 - 4x_4\, & = & -13 \end{array} $$
One denotes this:
$$ \begin{align*} \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 &\ \ 1 &\ \ 1 & -1 &\ \ 0 \\ \ \ 2 &\ \ 4 &\ \ 1 & -2 & -1 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] &\begin{array}{r} \ \\ \ \\ R_3 - 2R_1 \\ \\ \end{array} \longrightarrow \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 &\ \ 1 &\ \ 1 & -1 &\ \ 0 \\ \ \ 0 &\ \ 2 & -1 & -4 & -13 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] \end{align*} $$
It is a little more difficult to understand that both of these linear systems have the same solution set. The most uncomplicated way to understand type III row operations is that when we add one equation to another, we are adding an equality (both sides of the equation are equal). Adding the same values to both sides of the third equation yields another equality. The third equation has changed and its graph is different. However, equality was never altered; the graphs of all of the equations still intersect at the same point(s).
To finish eliminating the first variable (column) from all of the equations except the first one (rows), one subtracts three times the first row (equation) from the last row (equation) as follows:
$$ \begin{align*} \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 &\ \ 1 &\ \ 1 & -1 &\ \ 0 \\ \ \ 0 &\ \ 2 & -1 & -4 & -13 \\ \ \ 3 &\ \ 1 & -2 &\ \ 2 &\ \ 3 \end{array}\right] \begin{array}{c} \\ \\ \\ R_4 - 3R_1 \end{array} \longrightarrow \left[\begin{array}{cccc|c}\ \ 1 & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ \ \ 0 &\ \ 1 &\ \ 1 & -1 &\ \ 0 \\ \ \ 0 &\ \ 2 & -1 & -4 & -13 \\ \ \ 0 & -2 & -5 & -1 & -15 \end{array}\right] \end{align*} $$
We now have a collection of three Elementary Row Operations. These operations are the foundation of the methods we use to solve linear systems of equations.
Definition¶
$$ \begin{array}{|l|l|} \hline \text{Name} & \text{Operation} \\ \hline \textbf{Type I} & \text{Interchange two rows of the augmented matrix} \\ \hline \textbf{Type II} & \text{Multiply a row by a nonzero number} \\ \hline \textbf{Type III} & \text{Add a multiple of one row of the augmented matrix to another row} \\ \hline \end{array} $$
One performs row operations on the augmented form of a linear system in order to simplify the linear system into one that can be easily solved. In the case of medium to large linear systems, the goal may be to simplify the linear system enough to recognize important properties of the linear system. The linear system that results from row operations is not exactly the same as the original system; however, it has the same set of solutions. We call the original augmented matrix and the resulting one row equivalent matrices.
Definition¶
Two $m\times n$ matrices $A$ and $B$ are called row equivalent if and only if matrix $B$ may be obtained by performing a finite number of elementary row operations upon matrix $A$.
Since row operations are clearly reversible, this means that matrix $A$ may also be obtained by performing a finite number of elementary row operations upon matrix $B$.
Exercise 3 - Perform Row Operations¶
Given the following augmented matrix from exercise 2, interchange row one and row two; and then eliminate the first variable of the linear system from all rows except our new first row.
$$ A = \left[ \begin{array}{ccccc|c} \ \ 2 &\ \ 1 & -1 &\ \ 3 &\ \ 1 &\ \ 8 \\ \ \ 1 &\ \ 3 &\ \ 2 & -1 &\ \ 2 & 13 \\ -1 &\ \ 2 &\ \ 4 &\ \ 1 & -1 &\ \ 9 \\ \ \ 3 & -1 &\ \ 1 &\ \ 2 &\ \ 4 & 16 \\ \ \ 1 &\ \ 1 &\ \ 2 &\ \ 1 &\ \ 3 & 14 \end{array} \right] $$
View Solution
$$ \left[ \begin{array}{ccccc|c} \ \ 2 &\ \ 1 & -1 &\ \ 3 &\ \ 1 &\ \ 8 \\ \ \ 1 &\ \ 3 &\ \ 2 & -1 &\ \ 2 & 13 \\ -1 &\ \ 2 &\ \ 4 &\ \ 1 & -1 &\ \ 9 \\ \ \ 3 & -1 &\ \ 1 &\ \ 2 &\ \ 4 & 16 \\ \ \ 1 &\ \ 1 &\ \ 2 &\ \ 1 &\ \ 3 & 14 \end{array} \right]\begin{array}{c} R_2 \\ R_1 \\ \\ \\ \\ \end{array} \longrightarrow \left[ \begin{array}{ccccc|c}\ \ 1 &\ \ 3 &\ \ 2 & -1 &\ \ 2 & 13 \\ \ \ 2 &\ \ 1 & -1 &\ \ 3 &\ \ 1 &\ \ 8 \\ -1 &\ \ 2 &\ \ 4 &\ \ 1 & -1 &\ \ 9 \\ \ \ 3 & -1 &\ \ 1 &\ \ 2 &\ \ 4 & 16 \\ \ \ 1 &\ \ 1 &\ \ 2 &\ \ 1 &\ \ 3 & 14 \end{array} \right] $$
$$ \left[ \begin{array}{ccccc|c}\ \ 1 &\ \ 3 &\ \ 2 & -1 &\ \ 2 & 13 \\ \ \ 2 &\ \ 1 & -1 &\ \ 3 &\ \ 1 &\ \ 8 \\ -1 &\ \ 2 &\ \ 4 &\ \ 1 & -1 &\ \ 9 \\ \ \ 3 & -1 &\ \ 1 &\ \ 2 &\ \ 4 & 16 \\ \ \ 1 &\ \ 1 &\ \ 2 &\ \ 1 &\ \ 3 & 14 \end{array} \right] \begin{array}{c} \\ R_2-2R_1 \\ R_3+R_1 \\ R_4-3R_1 \\ R_5-R_1\end{array} \longrightarrow \left[ \begin{array}{ccccc|c}\ \ 1 &\ \ 3 &\ \ 2 & -1 &\ \ 2 &\ \ 13 \\ \ \ 0 & -5 & -5 &\ \ 5 & -3 & -18 \\ \ \ 0 &\ \ 5 &\ \ 6 &\ \ 0 &\ \ 1 &\ \ 22 \\ \ \ 0 & -10 & -5 &\ \ 5 & -2 & -23 \\ \ \ 0 & -2 &\ \ 0 &\ \ 2 &\ \ 1 &\ \ 1 \end{array} \right] $$
1.2.4 Some Special Matrices
Basic Forms of Matrices¶
American English has a considerable number of words to describe automobiles that all roughly mean "car" but carry different connotations: sedan, coupe, hatchback, SUV, crossover, minivan, pickup, convertible, roadster, wagon, jeep, beater, clunker, ride, etc. Linear Algebra has numerous terms to describe matrices and linear transformations. The following are basic terms for recognizing matrices that represent linear systems distinguished by the fact that they are easy to solve.
Definition¶
For any square $n\times n$ matrix $A$ we have the following definitions.
- The diagonal elements are the elements whose row and column index are the same, $a_{ii}$, $1\le i\le n$.
- The main diagonal is the collection of all diagonal elements of matrix $A$.
- A diagonal matrix is a square $n\times n$ matrix $A$ whose elements not on the main diagonal are all zero.
- The upper triangle is the region of $A$ that contains the elements whose column indices are greater than their row indices. (above the diagonal)
- The lower triangle is the region of $A$ that contains the elements whose column indices are less than their row indices. (below the diagonal)
- A matrix whose lower triangular entries are all zeros is called an upper triangular matrix.
- A matrix whose upper triangular entries are all zeros is called a lower triangular matrix.
Partitions of a partition matrix are examples of submatrices. As with partition matrices, one often focuses on a smaller region of a matrix to draw insights into the properties of the matrix. A partition results from dividing a matrix into submatrices with horizontal and vertical lines between rows and columns. With respect to the augmented matrix $\left[\,A\,|\,B\,\right]$, the partitions are $A$ and the $m\times 1$ matrix $B$. Here we distinguish between the vector $\mathbf{b}$ and the $m\times1$ matrix $B$ used to represent the vector. The difference between a vector and its representation using an $m\times1$ matrix seems like an unnecessary distinction now; however, it will be very important in future chapters.
The upper triangle of a matrix is not a submatrix because it is not rectangular, however removing the first row and first column of an $m\times n$ matrix ($m\ge2$ and $n\ge2$) results in an $(m-1)\times(n-1)$ submatrix.
Definition¶
Let $A$ be an $m\times n$ matrix and select a subcollection of $1<p\le m$ row indices $1\le i_1< i_2<\cdots< i_p\le m$. and a subcollection of $1<q\le n$ column indices $1\le j_1< j_2<\cdots< j_q\le n$. The $p\times q$ matrix $B$ with elements $b_{rs} = a_{i_rj_s}$ is the submatrix of $A$ with elements at the intersections of the rows $1\le i_1< i_2<\cdots< i_p\le m$ and $1\le j_1< j_2<\cdots< j_q\le n$.
We will study determinants in chapter 3. It requires the use of submatrices called principal submatrices.
The strict definition above is valid, but cryptic. In practice submatrices are constructed either as partitions of a matrix, or by deleting rows and columns from the matrix.
In this chapter, our goal is to recognize patterns in matrices like these basic forms. We use row operations on complicated matrices in order to obtain row-equivalent matrices in these basic forms. Determining the basic row-equivalent matrix often provides us with the solution set of the original linear system.
Exercise 4 - Types of Square Matrices¶
For each type of matrix in the problems below, list all of the matrices of the specified type.
| $A = \begin{bmatrix} 1 & 2 & 3 \\ 0 & 4 & 5 \\ 0 & 0 & 6 \end{bmatrix}$ | $B = \begin{bmatrix} 1 & 0 & 0 \\ 2 & 0 & 0 \\ 3 & 4 & 5 \end{bmatrix}$ | $C = \begin{bmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 3 \end{bmatrix}$ | $D = \begin{bmatrix} 0 & 0 & 1 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix}$ |
|---|
- Diagonal:
- Upper Triangular:
- Lower Triangular:
View Solution
- Diagonal: C
- Upper Triangular: A,C,D
- Lower Triangular: B,C
Exercise 5 - Submatrices¶
Consider the matrix
$$ A = \left[ \begin{array}{cccc}\ \ 3\ &\ \ 1\ &\ \ 5\ &\ \ 5\ \\ \ \ 4\ & -4\ &\ \ 5\ &\ \ 0\ \\ -4\ & -2\ & -4\ &\ \ 3\ \\ \ \ 5\ &\ \ 1\ &\ \ 5\ & -4\ \end{array} \right] $$
Create the following submatrices:
- Remove the second row and first column.
- Remove the second row and second column.
- Remove the second row and third column.
- Remove the second row and fourth column.
View Solution
$$ A_{21} = \left[ \begin{array}{ccc}\ \ 1\ &\ \ 5\ &\ \ 5 \\ -2\ & -4\ &\ \ 3\ \\ \ \ 1\ &\ \ 5\ & -4\ \end{array} \right] $$$$ A_{22} = \left[ \begin{array}{ccc}\ \ 3\ &\ \ 5\ &\ \ 5\ \\ -4\ & -4\ &\ \ 3\ \\ \ \ 5\ &\ \ 5\ & -4\ \end{array} \right] $$
$$ A_{23} = \left[ \begin{array}{ccc}\ \ 3\ &\ \ 1\ &\ \ 5\ \\ -4&\ -2\ &\ \ 3\ \\ \ \ 5\ &\ \ 1\ & -4\ \end{array} \right] $$
$$ A_{24} = \left[ \begin{array}{ccc}\ \ 3\ &\ \ 1\ &\ \ 5\ \\ -4\ & -2\ & -4\ \\ \ \ 5\ &\ \ 1\ &\ \ 5 \ \end{array} \right] $$
1.2.5 Gauss-Jordan Elimination
Elimination with Row Operations¶
Video Lecture 2: Gauss-Jordan Elimination
Gauss-Jordan elimination makes use of submatrices and pivots. Pivot is one of those terms that makes sense in practice and can be tedious to define.
Definition¶
Given an $m\times n$ matrix $A$, a pivot is an element of the matrix $a_{ij}$ chosen for either geometrical or numerical advantage.
- The row that contains the pivot, row $i$, is called a pivot row.
- The column that contains the pivot, column $j$, is called a pivot column.
- The variable associated with the pivot (such as $x_j$) is called a pivot variable.
- The value $a_{ij}$ is called the pivot value, pivot coefficient, or value of the pivot.
In Gauss-Jordan elimination, one performs elementary row operations on the augmented matrix to reduce the augmented matrix into upper triangular form. The process consists of identifying exceptional positions in the augmented matrix called pivots, and eliminating the pivot variable from all rows beneath the pivot. This is similar to selecting a variable in a system of equations and eliminating that variable from the other equations.
This is the method all students must master to solve linear systems. In this course, even $2\times 2$ linear systems must be solved using Gaussian Elimination so that the process becomes second nature. This allows the student to demonstrate mastery of the method. When completing homework or exams, one must always use these techniques to obtain any credit for solving a problem.
This method also illustrates a learning technique utilized often in this course. Focus on learning the steps of the process; not the arithmetic. Students should focus their attention on the algorithm. One must learn the vocabulary, the ideas, and the process.
Example 2 - Elimination with Row Operations¶
Use Gauss-Jordan Elimination to reduce the linear system into upper triangular form and use backward substitution to solve
$$ \begin{align*} x_1 \qquad\,\ \ - 3x_3 &= 5 \\ 3x_1 +\,\ x_2 - 2x_3 &= 5 \\ x_1 + 2x_2 - 2x_3 &= -2 \end{align*} $$
First write the linear system in augmented form.
$$ \begin{align*} B = \left[\,A\,|\,\mathbf{b}\,\right] = \left[ \begin{array}{ccc|c}\ \ 1 &\ \ 0 & -3 &\ \ 5 \\ \ \ 3 &\ \ 1 & -2 &\ \ 5 \\ \ \ 1 &\ \ 2 & -2 & -2 \end{array} \right] \end{align*} $$
1. Determine the next (first) pivot¶
Try to find a pivot in the ${\color{crimson}\text{submatrix}}$ below and to the right of the current pivot. The submatrix for the first pivot is the entire matrix.
There are a variety of strategies for selecting pivots. A pivot must be a nonzero element of the first column of the submatrix. When performing computations by hand as in this class, choose an integer nonzero element of the first column with an absolute value close to one.
The only reason for choosing a small integer is to simplify subsequent computations.
If needed, use type I row operations to get the chosen pivot into the first position (first row, first column) of the submatrix.
If there is no nonzero element of the first column, this iteration of our process fails. Skip this submatrix and consider the submatrix starting one column to the right of the first position of the current one. This means delete the zero column from the current submatrix and start over with step 1.
$$ \begin{align*} {\color{crimson}\left[ \begin{array}{ccc|c}\ \ 1 &\ \ 0 & -3 &\ \ {\color{black}5} \\ \ \ 3 &\ \ 1 & -2 &\ \ {\color{black}5} \\ \ \ 1 &\ \ 2 & -2 & {\color{black}-2} \end{array} \right]} \end{align*} $$
Since the first element of matrix $A$ is already nonzero, $\rbb{$\color{royalblue}a_{11}=1$}$, we have our first pivot.
$$ \begin{align*} \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 3 &\ \ 1 & -2 &\ \ 5 \\ \ \ 1 &\ \ 2 & -2 & -2 \end{array} \right] \end{align*} $$
2. Eliminate the pivot variable from all following rows (equations).¶
Proceed using row operations to eliminate the pivot variable from the equations that follow the pivot row. In this case, subtract three times row one (the pivot row) from row two (a following row), and then Subtract row one (the pivot row) from row three
Everyone should denote the row operation as well as compute the row operation. Arithmetic mistakes happen. We are grading your problem solving process; not your arithmetic skills. Communicate your steps so that you can receive credit for them in your score.
$$ \begin{align*} \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ {\color{crimson}3} &\ \ 1 & -2 &\ \ 5 \\ \ \ {\color{crimson}1} &\ \ 2 & -2 & -2 \end{array} \right]\begin{array}{l} \\ R_2-3R_1 \\ R_3-R_1 \\ \end{array} \longrightarrow \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ 1 &\ \ 7 & -10 \\ \ \ 0 &\ \ 2 &\ \ 1 & -7 \end{array} \right] \end{align*} $$
Notice that we use an arrow instead of an equal sign because the augmented matrices and the linear systems they represent are NOT EQUAL! They are equivalent linear systems. This means that they have the same solution set.
Repeat Steps 1 and 2¶
Try to find a pivot in the ${\color{crimson}\text{submatrix}}$ below and to the right of the current pivot.
$$ \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ {\color{crimson}1} &\ \ {\color{crimson}7} & -10 \\ \ \ 0 &\ \ {\color{crimson}2} &\ \ {\color{crimson}1} & -7 \end{array} \right] $$
Since there is a coefficient $\rbb{$\color{royalblue}a_{22}=1$}$, select $a_{22}$ to be the second pivot.
$$ \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 7 & -10 \\ \ \ 0 &\ \ 2 &\ \ 1 & -7 \end{array} \right] $$
Use row operations to eliminate the pivot variable from all rows below the current pivot row.
$$ \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 7 & -10 \\ \ \ 0 &\ \ 2 &\ \ 1 & -7 \end{array} \right]\begin{array}{l} \\ \\ R_3 - 2R_2 \end{array} \longrightarrow \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 7 & -10 \\ \ \ 0 &\ \ 0 & -13 & 13 \end{array} \right] $$
Try to find a pivot in the ${\color{crimson}\text{submatrix}}$ below and to the right of the current pivot.
$$ \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 7 & -10 \\ \ \ 0 &\ \ 0 & {\color{crimson}-13} & 13 \end{array} \right] $$
The next pivot is $\rbb{$\color{royalblue}-13$}$
$$ \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$} &\ \ 0 & -3 &\ \ 5 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 7 & -10 \\ \ \ 0 &\ \ 0 & \rbb{$\color{royalblue}-13$} & 13 \end{array} \right] $$
Notice that the coefficient matrix is now an upper triangular matrix.
Definition¶
Given a linear system $A\mathbf{x}=\mathbf{b}$ and augmented matrix $B = \left[\,A\,|\,\mathbf{b}\,\right]$, if matrix $A$ is an upper triangular matrix, then the augmented matrix is said to be in upper triangular form.
If matrix $A$ is not square, then if all elements below the pivots are zero, and all entries of any free column are zero below any pivot on the left of it, then the augmented matrix is said to be in upper triangular form.
Exercise 6 - Identify Upper Triangular Form¶
For each type of matrix in the problems below, list all of the matrices that are in upper triangular form
| Matrix | Matrix | Matrix |
|---|---|---|
| $A = \left[\begin{array}{cccc|c}\ \ 2 &\ \ 2 &\ \ 2 & -2 & 0 \\ -2 &\ \ 3 & -4 &\ \ 1 & 0 \\ \ \ 0 &\ \ 0 &\ \ 2 & -4 & 0 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 4 & 0 \end{array} \right]$ | $B = \left[\begin{array}{cccc|c}\ \ 2 & -1 & -3 &\ \ 2 & -7 \\ \ \ 0 & -2 &\ \ 1 &\ \ 3 &\ \ 2 \\ \ \ 0 &\ \ 0 & -1 & -2 & -5 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 &\ \ 4 \end{array} \right]$ | $C = \left[\begin{array}{cccc|c} -1 &\ \ 2 &\ \ 2 &\ \ 2 &\ \ 3 \\ \ \ 0 & -5 &\ \ 3 & -4 & -3 \\ \ \ 0 &\ \ 4 &\ \ 3 &\ \ 2 &\ \ 9 \\ \ \ 0 &\ \ 0 &\ \ 0 & -1 &\ \ 5 \end{array} \right]$ |
| $D = \left[\begin{array}{cccc|c} -2 &\ \ 2 & -1 & -3 &\ \ 4 \\ \ \ 0 &\ \ 0 & -1 &\ \ 0 & -1 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 4 & -4 \end{array} \right]$ | $E = \left[\begin{array}{cccc|c}\ \ 2 &\ \ 2 &\ \ 5 &\ \ 3\ &\ \ 2 \\ \ \ 0 & -4 & -2 & -3 &\ \ 5 \\ \ \ 0 &\ \ 0 &\ \ 1 &\ \ 0 & -1 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 & 0 \end{array} \right]$ | $F = \left[\begin{array}{cccc|c} -2 &\ \ 5 & -1 &\ \ 0 &\ \ 0 \\ \ \ 0 & -3 & -3 & -3 & -9 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 1 &\ \ 1 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 & 0 \end{array} \right]$ |
View Solution
| Matrix | Matrix | Matrix |
|---|---|---|
| ${\color{crimson}A = \left[\begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}2$} &\ \ 2 &\ \ 2 & -2 & 0 \\ -2 &\ \ 3 & -4 &\ \ 1 & 0 \\ \ \ 0 &\ \ 0 &\ \ 2 & -4 & 0 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 4 & 0 \end{array} \right]}$ | $B = \left[\begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}2$} & -1 & -3 &\ \ 2 & -7 \\ \ \ 0 & \rbb{$\color{royalblue}-2$} &\ \ 1 &\ \ 3 &\ \ 2 \\ \ \ 0 &\ \ 0 & \rbb{$\color{royalblue}-1$} & -2 & -5 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 &\ \ 4 \end{array} \right]$ | ${\color{crimson}C = \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}-1$} &\ \ 2 &\ \ 2 &\ \ 2 &\ \ 3 \\ \ \ 0 & \rbb{$\color{royalblue}-5$} &\ \ 3 & -4 & -3 \\ \ \ 0 &\ \ 4 &\ \ 3 &\ \ 2 &\ \ 9 \\ \ \ 0 &\ \ 0 &\ \ 0 & -1 &\ \ 5 \end{array} \right]}$ |
| $D = \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}-2$} &\ \ \bbox[blueviolet,7px]{\color{white}2} & -1 & -3 &\ \ 4 \\ \ \ 0 &\ \ \bbox[blueviolet,7px]{\color{white}0} & \bbox[5px, border: 2px solid royalblue]{\color{royalblue}-1} &\ \ 0 & -1 \\ \ \ 0 &\ \ \bbox[blueviolet,7px]{\color{white}0} &\ \ 0 &\ \ 0 &\ \ 0 \\ \ \ 0 &\ \ \bbox[blueviolet,7px]{\color{white}0} &\ \ 0 &\ \ \bbox[5px, border: 2px solid royalblue]{\color{royalblue}4} & -4 \end{array} \right]$ | $E = \left[\begin{array}{cccc|c}\ \ \bbox[5px, border: 2px solid royalblue]{\color{royalblue}2} &\ \ 2 &\ \ 5 &\ \ 3\ &\ \ 2 \\ \ \ 0 & \bbox[5px, border: 2px solid royalblue]{\color{royalblue}-4} & -2 & -3 &\ \ 5 \\ \ \ 0 &\ \ 0 &\ \ \bbox[5px, border: 2px solid royalblue]{\color{royalblue}1} &\ \ 0 & -1 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 & 0 \end{array} \right]$ | $F = \left[\begin{array}{cccc|c} \bbox[5px, border: 2px solid royalblue]{\color{royalblue}-2} &\ \ 5 & \bbox[blueviolet,7px]{\color{white}-1} &\ \ 0 &\ \ 0 \\ \ \ 0 & \bbox[5px, border: 2px solid royalblue]{\color{royalblue}-3} & \bbox[blueviolet,7px]{\color{white}-3} & -3 & -9 \\ \ \ 0 &\ \ 0 &\ \ \bbox[blueviolet,7px]{\color{white}0} &\ \ \bbox[5px, border: 2px solid royalblue]{\color{royalblue}1} &\ \ 1 \\ \ \ 0 &\ \ 0 &\ \ \bbox[blueviolet,7px]{\color{white}0} &\ \ 0 & 0 \end{array} \right]$ |
Matrices $B$, $D$, $E$, and $F$ are all in upper triangular form. Matrices $D$ and $F$ have $\bbox[blueviolet,7px]{\color{white}\text{free columns}}$, however they have zeros below any pivots to the left of their position.
Matrices ${\color{crimson}A}$ and ${\color{crimson}C}$ are not in upper triangular form because each has a nonzero coefficient below a pivot.
1.2.6 Row Echelon Form
Using Gaussian Elimination one reduces a matrix to upper triangular form or Row Echelon Form.
In row echelon form, the pivots are all ones. This has some advantages over upper triangular form, however, it may not be possible to represent a linear system without denominators. Using type II row operations to ensure that the pivots all have a value of one, may require other coefficients to be fractions or real numbers. Unless one is specifically asked for row echelon form, upper triangular form will always suffice.
Definition¶
An upper triangular matrix whose diagonal pivots are all ones is said to be in row echelon form.
Example 3 - Gaussian Elimination¶
Use Gauss-Jordan Elimination to reduce the linear system into row echelon form.
$$ \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 1 & -1 &\ \ 0 \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}3$} &\ \ 2 &\ \ 13 \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2 \end{array}\right] \begin{array}{l} \ \\ \ \\ \frac{1}{3}R_3 \\ \ \end{array}\longrightarrow\left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6 \\ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 1 & -1 &\ \ 0 \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ \frac{2}{3} &\ \ \frac{13}{3} \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2 \end{array}\right] $$
Example 4 - Row Echelon Form¶
Use Gauss-Jordan Elimination to reduce the linear system into row echelon form.
$$ \begin{align*} 2x_1 - 3x_2 +\ \ 7x_3 &= 4 \\ x_1 \qquad\,\ \ +\ \ 3x_3 &= 3 \\ 4x_1 - 9x_2 + 15x_3 &= 6 \end{align*} $$
One performs elementary row operations on the augmented matrix to reduce the augmented matrix into row echelon form.
$$ \left[\,A\,|\,\mathbf{b}\,\right] = \left[\begin{array}{ccc|c}\ \ 2\ & -3\ &\ \ 7\ &\ 4\ \\ \ \ 1\ &\ \ 0\ &\ \ 3\ &\ 3\ \\ \ \ 4\ & -9\ & 15\ &\ 6\ \end{array}\right]. $$
One now performs the three elementary row operations on the augmented matrix to reduce the augmented matrix into row echelon form.
$$ \begin{align*} \left[ \begin{array}{ccc|c} \ \ 2\ & -3\ &\ \ 7\ &\ 4\ \\ \ \ 1\ &\ \ 0\ &\ \ 3\ &\ 3\ \\ \ \ 4\ & -9\ & 15\ &\ 6\ \end{array} \right] \begin{array}{l} R_2 \\ R_1 \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ 3\ \\ \ \ 2\ & -3\ &\ \ 7\ &\ 4\ \\ \ \ 4\ & -9\ & 15\ &\ 6\ \end{array} \right] \begin{array}{l} \end{array} \quad\text{Type I Row Operation} \\ \\ \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ 3\ \\ \ \ {\color{crimson}2}\ & -3\ &\ \ 7\ &\ 4\ \\ \ \ {\color{crimson}4}\ & -9\ & 15\ &\ 6\ \end{array} \right] \begin{array}{l} \\ R_2 - 2R_1 \\ R_3 - 4R_1 \end{array} &\longrightarrow \left[ \begin{array}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ \ 3\ \\ \ \ 0\ & -3\ &\ \ 1\ & -2\ \\ \ \ 0\ & -9\ &\ \ 3\ & -6\ \end{array} \right] \quad\text{Type III Row Operations} \\ \\ \begin{bmatrix}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ & | &\ \ 3\ \\ \ \ 0\ & \rbb{$\color{royalblue}-3$}\ &\ \ 1\ & | & -2\ \\ \ \ 0\ & {\color{crimson}-9}\ &\ \ 3\ & | & -6\ \end{bmatrix}\begin{array}{l} \\ \\ R_3 - 3R_2 \end{array} &\longrightarrow \begin{bmatrix}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ & | &\ \ 3\ \\ \ \ 0\ & \rbb{$\color{royalblue}-3$}\ &\ \ 1\ & | & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ & | &\ \ 0\ \end{bmatrix} \quad\text{Type III Row Operation} \\ \\ \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ \ 3\ \\ \ \ 0\ & \rbb{$\color{royalblue}-3$}\ &\ \ 1\ & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{array} \right] \begin{array}{l} \\ \frac{R_2}{-3} \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ \ 3\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -\frac{1}{3}\ &\ \ \frac{2}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{array} \right] \quad\text{Type II Row Operation} \\ \\ \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ \fcolorbox{blueviolet}{blueviolet}{${\color{white}3}$}\ &\ \ 3\ \\ \ \ 0\ & \rbb{$\color{royalblue}-3$}\ &\ \ \fcolorbox{blueviolet}{blueviolet}{${\color{white}1}$}\ & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ \fcolorbox{blueviolet}{blueviolet}{${\color{white}0}$}\ &\ \ 0\ \end{array} \right] \end{align*} $$
The last step identifies a free column. The last row of the row echelon form of the linear system translates to $0x_1 + 0x_2 + 0x_3 = 0$. This trivially true equation $0=0$ adds no constraint, so consistency is determined by the other rows. Since it has a free column, the linear system has infinitely many solutions.
Exercise 7 - How Many Solutions¶
Identify how many solutions has the following linear system ($1$, infinitely many, or none)
$$ \begin{align*} 4x_1 + x_2 +\ \ x_3 - 2x_4 &= 4 \\ 5x_1 + x_2 + 2x_3 - 2x_4 &= 6 \\ -x_1 + x_2 - 3x_3 -\ \ x_4 &= -4 \\ -4x_1 - 4x_3 &= -7 \end{align*} $$
View Solution
$$ \begin{bmatrix}\,A\,|\,\mathbf{b}\,\end{bmatrix} = \left[ \begin{array}{cccc|c}\ \ 4 &\ \ 1 &\ \ 1 & -2 &\ \ 4 \\ \ \ 5 &\ \ 1 &\ \ 2 & -2 &\ \ 6 \\ -1 &\ \ 1 & -3 & -1 & -4 \\ -4 &\ \ 0 & -4 &\ \ 0 & -7 \end{array} \right] $$$$ \begin{align*} \left[ \begin{array}{cccc|c}\ \ 4 &\ \ 1 &\ \ 1 & -2 &\ \ 4 \\ \ \ 5 &\ \ 1 &\ \ 2 & -2 &\ \ 6 \\ -1 &\ \ 1 & -3 & -1 & -4 \\ -4 &\ \ 0 & -4 &\ \ 0 & -7 \end{array} \right] \begin{array}{c} R_3 \\ \\ -R_1 \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}1$} & -1 &\ \ 3 &\ \ 1 &\ \ 4 \\ \ \ 5 &\ \ 1 &\ \ 2 & -2 &\ \ 6 \\ \ \ 4 &\ \ 1 &\ \ 1 & -2 &\ \ 4 \\ -4 &\ \ 0 & -4 &\ \ 0 & -7 \end{array} \right] \begin{array}{c} \\ R_2-5R_1 \\ R_3-4R_1 \\ R_4+4R_1 \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}1$} & -1 &\ \ 3 &\ \ 1 &\ \ 4 \\ \ \ 0 &\ \ 6 & -13 & -7 & -14 \\ \ \ 0 &\ \ 5 & -11 & -6 & -12 \\ \ \ 0 & -4 &\ \ 8 &\ \ 4 &\ \ 9 \end{array} \right] \begin{array}{c} \\ R_2-R_3 \\ \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}1$} & -1 &\ \ 3 &\ \ 1 &\ \ 4 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} & -2 & -1 & -2 \\ \ \ 0 &\ \ 5 & -11 & -6 & -12 \\ \ \ 0 & -4 &\ \ 8 &\ \ 4 &\ \ 9 \end{array} \right] \begin{array}{c} \\ \\ \\ R_3-5R_2 \\ R_4+4R_2 \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}1$} & -1 &\ \ 3 &\ \ 1 &\ \ 4 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} & -2 & -1 & -2 \\ \ \ 0 &\ \ 0 & -1 & -1 & -2 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 &\ \ 1 \end{array} \right] \begin{array}{c} \\ \\ -R_3 \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}1$} & -1 &\ \ 3 &\ \ 1 &\ \ 4 \\ \ \ 0 &\ \ \rbb{$\color{royalblue}1$} & -2 & -1 & -2 \\ \ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 1 &\ \ 2 \\ \ \ 0 &\ \ 0 &\ \ 0 &\ \ 0 &\ \ 1 \end{array} \right] \end{align*} $$
The row echelon form of the linear system indicates three pivot columns and one free column. The linear system is dependent due to the existence of a free column. Unfortunately, the free row translates to $0x_1 + 0x_2 + 0x_3 + 0x_4 = 1$, inconsistent. Therefore the linear system has no solutions.
1.2.7 Backward Substitution
Definition¶
Backward substitution is performed by assigning any free variables and proceeding from the last row to the first row. For each row one obtains either
- an algebraically solvable equation that can be solved for one of the pivot variables
- an unsolvable algebraic equation that indicates that the linear system has no solution.
Example 5 - Backward Substitution¶
$$ \left[ \begin{array}{cccc|c}\ \ \rbb{$\color{royalblue}1$}\ & \ \ 1 & \ \ 1 &\ \ 1 &\ \ 6\ \\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 1 & -1 &\ \ 0\ \\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ \frac{2}{3} &\ \ \frac{13}{3}\ \\ \ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2\ \end{array} \right] $$
Each column of the coefficient matrix in our augmented matrix is a pivot column. The pivots are all ones so the augmented matrix is in row echelon form. Since all of the columns are pivot columns, the linear system is independent. Since all of the equations (rows) are algebraically solvable, the linear system is consistent. Hence the linear system has a unique solution. Employing backward substitution one obtains:
$$ x_4 = 2 $$
Proceeding from bottom-to-top and substituting $2$ for $x_4$ in the next row yields
$$ \begin{align*} x_3 + \frac{2}{3}x_4 = x_3 + \frac{2}{3}\,2 &= \frac{13}{3} \\ \\ x_3 &= \frac{13}{3} - \frac{4}{3} = \frac{9}{3} = 3 \end{align*} $$
Continuing to the next row and substituting for $x_3$ and $x_4$ gives
$$ \begin{align*} x_2 + x_3 - x_4 = x_2 + 3 - 2 &= 0 \\ \\ x_2 &= -1 \end{align*} $$
Finally substituting the values of $x_2$, $x_3$ and $x_4$ into the first equation results in
$$ \begin{align*} x_1 + x_2 + x_3 + x_4 &= x_1 - 1 + 3 + 2 = 6 \\ \\ x_1 + 4 &= 6 \\ \\ x_1 &= 2 \end{align*} $$
This gives us the unique solution $\begin{bmatrix}\ \ 2\ \\ -1\ \\ \ \ 3\ \\ \ \ 2\ \end{bmatrix} = \langle\, 2,\ -1,\ 3,\ 2 \,\rangle$
The solution set is
$$ S = \left\{\, \begin{bmatrix}\ \ 2\ \\ -1\ \\ \ \ 3\ \\ \ \ 2\ \end{bmatrix} \,\right\} $$
Example 6 - Backward Substitution(2)¶
$$ \begin{align*} \begin{bmatrix}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ & -3\ & | &\ \ 5\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ &\ \ 7\ & | & -10\ \\ \ \ 0\ &\ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & | & -1\ \end{bmatrix} \end{align*} $$
Each column of matrix $A$ in our augmented matrix is a pivot column. Since all of the columns are pivot columns, the linear system is independent. Since all of the equations (rows) are algebraically solvable, the linear system is consistent. Hence the linear system has a unique solution. Now that the linear system is in row echelon form, employ backward substitution to obtain the solution.
$$ \begin{align*} x_3 &= -1 \\ \\ x_2 + 7(-1) &= -10 \\ x_2 &= -3 \\ \\ x_1 - 3(-1) &= 5 \\ x_1 &= 2 \end{align*} $$
From this one reports that the solution to the linear system $A\mathbf{x} = \mathbf{b}$ is the vector
$$ \mathbf{x} = \begin{bmatrix}\ \ 2\ \\ -3\ \\ -1\ \end{bmatrix} = \langle 2,\ -3,\ -1 \rangle $$
The solution set is
$$ S = \left\{ \begin{bmatrix}\ \ 2\ \\ -3\ \\ -1\ \end{bmatrix} \right\} $$
Example 7 - Backward Substitution(3)¶
$$ \left[ \begin{array}{ccc|c}\ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ \ 3\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -\frac{1}{3}\ &\ \ \frac{2}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ \fcolorbox{blueviolet}{blueviolet}{${\color{white}0}$}\ &\ \ 0\ \end{array} \right] $$
In this problem the first two columns are pivot columns and the third column is a free column because it has no pivot. We conclude that variable $x_3$ is a free variable. No matter what value $x_3$ may take
$$ \left[ \begin{array}{ccc}\ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -\frac{1}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ \fcolorbox{blueviolet}{blueviolet}{${\color{white}0}$}\ \end{array} \right] \left[ \begin{array}{c} 0 \\ 0 \\ x_3 \end{array} \right] = \left[ \begin{array}{c} 3x_3 \\ -\frac{1}{3}x_3 \\ x_3 \end{array} \right] = x_3 \left[ \begin{array}{c}\ \ 3 \\ -\frac{1}{3} \\ \ \ 1 \end{array} \right] $$
This computation shows us that
$$ \left[ \begin{array}{ccc}\ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -\frac{1}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ \fcolorbox{blueviolet}{blueviolet}{${\color{white}0}$}\ \end{array} \right] \left[ \begin{array}{c} -3 \\ \frac{1}{3} \\ 1 \end{array} \right] = -3 \left[ \begin{array}{c}\ 1\ \\ \ 0\ \\ \ 0\ \end{array} \right] + \frac{1}{3}\left[ \begin{array}{c}\ 0\ \\ \ 1\ \\ \ 0\ \end{array} \right] + 1\left[ \begin{array}{c}\ 3\ \\ -\frac{1}{3}\ \\ \ 0\ \end{array} \right] = \mathbf{0} $$
This means we can solve for column three
$$ \left[ \begin{array}{c}\ 3\ \\ -\frac{1}{3}\ \\ \ 0\ \end{array} \right] = 3 \left[ \begin{array}{c}\ 1\ \\ \ 0\ \\ \ 0\ \end{array} \right] - \frac{1}{3}\left[ \begin{array}{c}\ 0\ \\ \ 1\ \\ \ 0\ \end{array} \right] $$
We have the linear combination that establishes column three is a linear combination of the other two column vectors. Variable $x_3$ can be any real number and the pivot variables $x_1$ and $x_2$ adjust to still obtain $A\mathbf{x}= \mathbf{b}$.
We call the third column a free column because the third variable is a free variable, it is unconstrained. The linear system is dependent since one column is a linear combination of the other columns. The linear system is consistent. Hence the linear system has infinitely many solutions, one for every $x_3\in\mathbb{R}$.
Backward substitution begins with identifying the free variables :
$$ x_3 = s\in\mathbb{R} $$
Continuing using backward substitution one obtains
$$ \begin{align*} x_2 - \frac{1}{3}s &= \frac{2}{3} \\ x_2 &= \frac{1}{3}s + \frac{2}{3} \\ \\ x_1 + 3s &= 3 \\ x_1 &= -3s + 3 \end{align*} $$
One reports that the infinitely many solutions have the form
$$ \begin{align*} \mathbf{x} &= \begin{bmatrix} -3s + 3 \\ \frac{1}{3}s + \frac{2}{3} \\ s \end{bmatrix} = \left\langle -3s+3,\ \frac{1}{3}s+\frac{2}{3},\ s \right\rangle \\ \\ &= {\color{blueviolet} \begin{bmatrix} -3\ \\ \ \ \frac{1}{3}\ \\ \ \ 1\ \end{bmatrix}}s + {\color{royalblue}\begin{bmatrix}\ 3\ \\ \ \frac{2}{3}\ \\ \ 0\ \end{bmatrix}},\ \text{for any }s\in\mathbb{R} \end{align*} $$
The infinitely many vectors $\left\{\, {\color{blueviolet} \begin{bmatrix} -3\ \\ \ \ \frac{1}{3}\ \\ \ \ 1\ \end{bmatrix}}s\,:\,s\in\mathbb{R}\,\right\}$ is called the homogeneous solution. The vector $\begin{bmatrix}\ 3\ \\ \ \frac{2}{3}\ \\ \ 0\ \end{bmatrix}$ is called a particular solution.
The solution set becomes
$$ S = \left\{ {\color{blueviolet}\begin{bmatrix} -3\ \\ \ \ \frac{1}{3}\ \\ \ \ 1\ \end{bmatrix}}s + {\color{royalblue}\begin{bmatrix}\ 3\ \\ \ \frac{2}{3}\ \\ \ 0\ \end{bmatrix}} \,:\, s\in\mathbb{R}\right\} $$
1.2.8 Reduced Row Echelon Form
Video Lecture 3: Reduced Row Echelon Form¶
Video Lecture 3: Reduced Row Echelon Form
Reduced Row Echelon Form is the goal of Gauss-Jordan Elimination. Reduced Row Echelon Form is used to perform the Column-Rank (CR) Factorization . Backward substitution is simplest when a linear system is written in reduced row echelon form. Gauss-Jordan Elimination is also used to reduce a matrix into Jordan Normal Form, and Hermite Normal Form. Column-Rank Factorization, Jordan Normal Form, and Hermite Normal Form are introduced later in the course.
Definition¶
We say that $m\times n$ matrix $A$ is in reduced row echelon form if the matrix is in row echelon form, and the pivot variables are eliminated from all of the other equations. The matrix has zeros below and above each pivot.
Example 8 - Reduced Row Echelon Form¶
One continues to use elementary row operations to eliminate variables above the pivots as well as below the pivots.
$$ \begin{align*} \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ 1 & \ \ 1 &\ \ {\color{crimson}1} &\ \ 6\ \\ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 1 & {\color{crimson}-1} &\ \ 0\ \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ {\color{crimson}\frac{2}{3}} &\ \ \frac{13}{3}\ \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2\ \end{array}\right] \begin{array}{l} R_1-R_4 \\ R_2+R_4 \\ R_3 - \frac{2}{3}R_4 \\ \\ \\ \end{array} &\longrightarrow \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ 1 & \ \ 1 &\ \ 0 &\ \ 4 \\ 0\ &\ \ \rbb{$\color{royalblue}1$} &\ \ 1 & \ \ 0 &\ \ 2\ \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 0 &\ \ 3\ \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2\ \end{array}\right] \begin{array}{l} R_1-R_3 \\ R_2-R_3 \\ \ \\ \\ \\ \end{array} \longrightarrow \\ \\ \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ 1 & \ \ {\color{crimson}1} &\ \ 0 &\ \ 4\ \\ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ {\color{crimson}1} & \ \ 0 &\ \ 2\ \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 0 &\ \ 3\ \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2\ \end{array}\right] \begin{array}{l} R_1-R_3 \\ R_2-R_3 \\ \ \\ \\ \\ \end{array} &\longrightarrow \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ {\color{crimson}1} & \ \ 0 &\ \ 0 &\ \ 1\ \\ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 0 & \ \ 0 & -1\ \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 0 &\ \ 3\ \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2\ \end{array}\right] \begin{array}{l} R_1-R_2 \\ \\ \ \\ \\ \\ \end{array} \longrightarrow \\ \\ \left[\begin{array}{cccc|c} \rbb{$\color{royalblue}1$} & \ \ 0 & \ \ 0 &\ \ 0 &\ \ 2\ \\ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 0 & \ \ 0 & -1\ \\ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 0 &\ \ 3\ \\ 0 &\ \ 0 &\ \ 0 &\ \ \rbb{$\color{royalblue}1$} &\ \ 2\ \end{array}\right] \end{align*} $$
Now backward substitution is very easy to perform.
$$ \mathbf{x} = \begin{bmatrix}\ \ 2\ \\ -1\ \\ \ \ 3\ \\ \ \ 2\ \end{bmatrix} $$
The solution set is
$$ \left\{\,\begin{bmatrix}\ \ 2 \\ -1 \\ \ \ 3 \\ \ \ 2 \end{bmatrix}\,\right\} $$
Exercise 8 - Determine the Solution Set¶
Find the solution set of the following linear system in row echelon form.
$$ \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ & -3\ &\ \ 5\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ &\ \ 7\ & -10\ \\ \ \ 0\ &\ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -1\ \end{array} \right] $$
View Solution
$$ \begin{align*} \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ & {\color{crimson}-3}\ &\ \ 5\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ &\ \ {\color{crimson}7}\ & -10\ \\ \ \ 0\ &\ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -1\ \end{array} \right] &\longrightarrow \left[ \begin{array}{ccc|c} \ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 0\ &\ \ 2\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ & -3\ \\ \ \ 0\ &\ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ & -1\ \end{array} \right] \end{align*} $$The solution set of the linear system:
$$ \left\{ \begin{bmatrix}\ \ 2\ \\ -3\ \\ -1\ \end{bmatrix} \right\} $$
Exercise 9 - Determine the Solution Set¶
Use Gauss-Jordan Elimination to reduce the linear system into reduced row echelon form and use backward substitution to solve.
$$ \begin{align*} x_1 +\,\ x_2 +\ \ 4x_3 &= 6 \\ 2x_1 + 5x_2 + 11x_3 &= 4 \\ x_1 + 4x_2 +\ \ 7x_3 &= 4 \end{align*} $$
View Solution
$$ \left[\,A\,|\,\mathbf{b}\,\right] = \left[ \begin{array}{ccc|c}\ \ 1\ &\ \ 1\ &\ \ 4\ &\ \ 6\ \\ \ \ 2\ &\ \ 5\ &\ \ 11\ &\ \ 4\ \\ \ \ 1\ &\ \ 4\ &\ \ 7\ &\ \ 4\ \end{array} \right] $$Perform elementary row operations on the augmented matrix to reduce the augmented matrix to reduced row echelon form.
$$ \begin{align*} \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 1\ &\ \ 4\ &\ \ 6\ \\ \ \ 2\ &\ \ 5\ &\ \ 11\ &\ \ 4\ \\ \ \ 1\ &\ \ 4\ &\ \ 7\ &\ \ 4\ \end{array} \right] \begin{array}{c} \\ R_2-2R_1 \\ R_3-R_1 \end{array} &\longrightarrow \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 1\ &\ \ 4\ &\ \ 6\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}3$}\ &\ \ 3\ & -8\ \\ \ \ 0\ &\ \ 3\ &\ \ 3\ & -2\ \end{array} \right] \begin{array}{c} \\ \\ R_3-R_2 \end{array} \longrightarrow \\ \\ \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 1\ &\ \ 4\ &\ \ 6\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}3$}\ &\ \ 3\ & -8\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 6\ \end{array} \right] \begin{array}{c} \\ \frac{1}{3}R_2\\ \\ \end{array} &\longrightarrow \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 1\ &\ \ 4\ &\ \ 6\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ &\ \ 1\ & -\frac{8}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 6\ \end{array} \right] \begin{array}{c} R_1-R_2 \\ \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{ccc|c}\ \ \rbb{$\color{royalblue}1$}\ &\ \ 0\ &\ \ 3\ &\ \ \frac{26}{3}\ \\ \ \ 0\ &\ \ \rbb{$\color{royalblue}1$}\ &\ \ 1\ & -\frac{8}{3}\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 6\ \end{array} \right] \end{align*} $$
The reduced row echelon form of the augmented matrix shows that the linear system is __dependent__ because there is a free column, and the free row translates to $$ 0x_1 + 0x_2 + 0x_3 = 6 $$
This is impossible so the linear system is __inconsistent__; there are no solutions. The solution set $$ S = \left\{ \ \right\} = \emptyset $$
1.2.9 Homogeneous Linear Systems
Definition¶
A linear system $A\mathbf{x}=\mathbf{b}$ is called homogeneous when vector $\mathbf{b}$ is the zero vector, $\mathbf{b}=\mathbf{0}$.
A homogeneous linear system is ALWAYS consistent because zero is always a solution, $A\mathbf{0} = \mathbf{0}$.
Associated Homogeneous Linear System
Every linear system of equations $A\mathbf{x}=\mathbf{b}$ has an associated homogeneous linear system of the form $A\mathbf{x}=\mathbf{0}$.
Example 9 - Solve a Homogeneous System¶
In this example, the associated homogeneous linear system is given by
$$ \begin{align*} x_1 +\,\ x_2 +\ \ 4x_3 &= 0 \\ 2x_1 + 5x_2 + 11x_3 &= 0 \\ x_1 + 4x_2 +\ \ 7x_3 &= 0 \end{align*} $$
or
$$ A\mathbf{x} = \begin{bmatrix}\ 1\ &\ 1\ &\ 4\ \\ \ 2\ &\ 5\ &\ 11\ \\ \ 1\ &\ 4\ &\ 7\ \end{bmatrix}\mathbf{x} = \begin{bmatrix}\ 0\ \\ \ 0\ \\ \ 0\ \end{bmatrix} = \mathbf{0} = \mathbf{b} $$
The augmented matrix has a column of zeros that is never changed by any row operation. As a result, the column is usually excluded.
$$ \left[ \begin{array}{ccc|c}\ 1\ &\ 1\ &\ 4\ &\ 0\ \\ \ 2\ &\ 5\ &\ 11\ &\ 0\ \\ \ 1\ &\ 4\ &\ 7\ &\ 0\ \end{array} \right] \longrightarrow \begin{bmatrix}\ 1\ &\ 1\ &\ 4\ \\ \ 2\ &\ 5\ &\ 11\ \\ \ 1\ &\ 4\ &\ 7\ \end{bmatrix} $$
The homogeneous version of the augmented matrix precludes the right partition because the coefficients are always zero!
This means that when augmented matrix has no vertical bar, the right partition of zeros is implied. One must include a vertical bar in the augmented matrix in order to properly communicate the correct vector $\mathbf{b}$ when submitting work for a homework or exam problem.
$$ \begin{bmatrix}\ 1\ &\ 1\ &\ 4\ \\ \ 2\ &\ 5\ &\ 11\ \\ \ 1\ &\ 4\ &\ 7\ \end{bmatrix} \longleftrightarrow \begin{bmatrix}\ {\color{royalblue} 1}\ &\ 0\ &\ {\color{indigo}3}\ \\ \ 0\ &\ {\color{royalblue} 1}\ &\ {\color{indigo}1}\ \\ \ 0\ &\ 0\ &\ 0\ \end{bmatrix} $$
Performing backward substitution yields
$$ \begin{align*} x_3 &= s\in\mathbb{R} \\ \\ x_2 + s &= 0 \\ x_2 &= -s \\ \\ x_1 + 3s &= 0 \\ x_1 &= -3s \end{align*} $$
The homogeneous solution
$$ \left\{\, \begin{bmatrix} -3s\ \\ -s\ \\ \ \ s\ \end{bmatrix} \,:\, s\in\mathbb{R} \,\right\} $$
This is particularly true for $s=-1$. When $s=-1$, the linear system of equations becomes
$$ \begin{align*} \begin{bmatrix}\ 1\ &\ 1\ &\ 4\ \\ \ 2\ &\ 5\ &\ 11\ \\ \ 1\ &\ 4\ &\ 7\ \end{bmatrix}\begin{bmatrix}\ \ 3\ \\ \ \ 1\ \\ -1\ \end{bmatrix} &= \begin{bmatrix}\ 0\ \\ \ 0\ \\ \ 0\ \end{bmatrix} \\ \\ 3\begin{bmatrix}\ 1\ \\ \ 2\ \\ \ 1\ \end{bmatrix} + \begin{bmatrix}\ 1\ \\ \ 5\ \\ \ 4\ \end{bmatrix} - \begin{bmatrix}\ 4\ \\ \ 11\ \\ \ 7\ \end{bmatrix} &= \mathbf{0} \\ \\ 3\begin{bmatrix}\ 1\ \\ \ 2\ \\ \ 1\ \end{bmatrix} + \begin{bmatrix}\ 1\ \\ \ 5\ \\ \ 4\ \end{bmatrix} &= \begin{bmatrix}\ 4\ \\ 11\ \\ \ 7\ \end{bmatrix} \end{align*} $$
Linear Combinations¶
In example 5 we also see one of the advantages of reduced row echelon form. The reduced row echelon form of a coefficient matrix confers important information about the linearly dependent or free columns. Recall the reduced row echelon form
$$ \begin{bmatrix}\ \rbb{$\color{royalblue} 1$}\ &\ 0\ &\ \fcolorbox{blueviolet}{blueviolet}{${\color{white}3}$}\ \\ \ 0\ &\ \rbb{$\color{royalblue}1$}\ &\ \fcolorbox{blueviolet}{blueviolet}{${\color{white}1}$}\ \\ \ 0\ &\ 0\ &\ 0\ \end{bmatrix} $$
The values of the free column furnishes the linear combination of the pivot columns of the original coefficient matrix that yields the free column. In example 5,
$$ \begin{align*} \fcolorbox{blueviolet}{blueviolet}{${\color{white}3}$}{\color{royalblue}\begin{bmatrix}\ 1\ \\ \ 2\ \\ \ 1\ \end{bmatrix}} + \fcolorbox{blueviolet}{blueviolet}{${\color{white}1}$}{\color{royalblue}\begin{bmatrix}\ 1\ \\ \ 5\ \\ \ 4\ \end{bmatrix}} &= {\color{royalblue}\begin{bmatrix}\ {\color{blueviolet}3}(1) + {\color{blueviolet}1}(1)\ \\ \ {\color{blueviolet}3}(2) + {\color{blueviolet}1}(5)\ \\ \ {\color{blueviolet}3}(1) + {\color{blueviolet}1}(4)\ \end{bmatrix}} = {\color{blueviolet}\begin{bmatrix}\ 4\ \\ \ 11\ \\ \ 7\ \end{bmatrix}} \\ \end{align*} $$
Definition¶
Pivot Columns and Free Columns
Every free column of and $m\times n$ matrix $A$ can be written as a linear combination of the pivot columns. The coefficients of the pivot columns are revealed in the reduced row echelon form of the matrix.
Applying this important property of the columns of a matrix yields the column-rank factorization, null space, column space, and row space of a matrix. All subjects studied later in this course.
1.2.10 Exercises
Exercise 10 - Solve the Linear System¶
Use an augmented matrix, Gaussian elimination, and backward substitution to solve the linear system
$$ \begin{bmatrix} \ \ 1\ &\ \ 2\ &\ \ 0\ & -1\ \\ \ \ 5\ &\ \ 4\ & -6\ &\ \ 1\ \\ \ \ 0\ &\ \ 4\ &\ \ 4\ & -4\ \\ \ \ 2\ &\ \ 1\ & -3\ &\ \ 1\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} -3\ \\ -9\ \\ -4\ \\ -3\ \end{bmatrix} $$
View Solution
$$ \begin{align*} \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ 2\ &\ \ 0\ & -1\ & -3\ \\ \ \ {\color{blueviolet}5}\ &\ \ 4\ & -6\ &\ \ 1\ & -9\ \\ \ \ {\color{blueviolet}0}\ &\ \ 4\ &\ \ 4\ & -4\ & -4\ \\ \ \ {\color{blueviolet}2}\ &\ \ 1\ & -3\ &\ \ 1\ & -3\ \end{array} \right] \begin{array}{l} \\ R_2 - 5R_1 \\ \\ R_4 - 2R_1 \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ 2\ &\ \ 0\ & -1\ & -3\ \\ \ \ 0\ & {\color{crimson}-6}\ & {\color{crimson}-6}\ &\ \ {\color{crimson}6}\ &\ \ 6\ \\ \ \ 0\ &\ \ {\color{royalblue}4}\ &\ \ {\color{crimson}4}\ & {\color{crimson}-4}\ & -4\ \\ \ \ 0\ & {\color{crimson}-3}\ & {\color{crimson}-3}\ &\ \ {\color{crimson}3}\ &\ \ 3\ \end{array} \right] \begin{array}{l} \\ \\ R_3 + R_4 \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ 2\ &\ \ 0\ & -1\ & -3\ \\ \ \ 0\ & {\color{crimson}-6}\ & {\color{crimson}-6}\ &\ \ {\color{crimson}6}\ &\ \ 6\ \\ \ \ 0\ &\ \ {\color{royalblue}1}\ &\ \ {\color{crimson}1}\ & {\color{crimson}-1}\ & -1\ \\ \ \ 0\ & {\color{crimson}-3}\ & {\color{crimson}-3}\ &\ \ {\color{crimson}3}\ &\ \ 3\ \end{array} \right] \begin{array}{l} \\ \text{switch }R_3 \\ \text{and }R_2 \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ 2\ &\ \ 0\ & -1\ & -3\ \\ \ \ 0\ &\ \ {\color{royalblue}1}\ &\ \ 1\ & -1\ & -1\ \\ \ \ 0\ &{\color{blueviolet}-6}\ & -6\ &\ \ 6\ &\ \ 6\ \\ \ \ 0\ &{\color{blueviolet}-3}\ & -3\ &\ \ 3\ &\ \ 3\ \end{array} \right] \begin{array}{l} \\ \\ R_3 + 6R_2 \\ R_4 + 3R_2 \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ {\color{indigo}2}\ &\ \ 0\ & -1\ & -3\ \\ \ \ 0\ &\ \ {\color{royalblue}1}\ &\ \ 1\ & -1\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ {\color{crimson}0}\ &\ \ {\color{crimson}0}\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ {\color{crimson}0}\ &\ \ {\color{crimson}0}\ &\ \ 0\ \end{array} \right] \begin{array}{l} \\ \\ {\color{crimson}\text{pivot?}} \quad \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ 0\ & -2\ &\ \ 1\ & -1\ \\ \ \ 0\ &\ \ {\color{royalblue}1}\ &\ \ 1\ & -1\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ {\color{crimson}0}\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ {\color{crimson}0}\ &\ \ 0\ \end{array} \right] \begin{array}{l} \\ \\ {\color{crimson}\text{pivot?}} \quad \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ {\color{indigo}2}\ &\ \ 0\ & -1\ & -3\ \\ \ \ 0\ &\ \ {\color{royalblue}1}\ &\ \ 1\ & -1\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{array} \right] \begin{array}{l} R_1 - 2R_2 \\ \\ \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ {\color{royalblue}1}\ &\ \ 0\ & -2\ &\ \ 1\ & -1\ \\ \ \ 0\ &\ \ {\color{royalblue}1}\ &\ \ 1\ & -1\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{array} \right] \end{align*} $$This matrix has:
- two pivot columns (columns one and two), and two free columns (columns three and four)
- two pivot variables ($x_1$ and $x_2$), and two free variables ($x_3$ and $x_4$)
Utilizing back substitution results in
$$ \begin{align*} x_4 &= t\in\mathbb{R} \\ x_3 &= s\in\mathbb{R} \\ \\ x_2 + x_3 - x_4 &= x_2 + s - t = -1 \\ x_2 &= -1 - s + t \\ \\ x_1 - 2x_3 + x_4 &= x_1 - 2s + t = -1 \\ x_1 &= -1 + 2s - t \\ \\ \mathbf{x} &= \begin{bmatrix} 2s - t - 1 \\ -s + t - 1 \\ s \\ t \end{bmatrix} = \begin{bmatrix} -1\ \\ -1 \\ \ \ 0\ \\ \ \ 0\ \end{bmatrix} + s\begin{bmatrix} \ \ 2\ \\ -1\ \\ \ \ 1\ \\ \ \ 0\ \end{bmatrix} + t\begin{bmatrix} -1\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 1\ \end{bmatrix} \end{align*} $$
There are infinitely many solutions because variables $s$ and $t$ may be any real number. There are in fact an infinite plane of solutions in 4 dimensional space $\mathbb{R}^4$. The Solution Set is
$$ S = \left\{\,\begin{bmatrix} -1 + 2s - t \\ -1 - s + t \\ s \\ t \end{bmatrix} = \begin{bmatrix} -1\ \\ -1 \\ \ \ 0\ \\ \ \ 0\ \end{bmatrix} + s\begin{bmatrix} \ \ 2\ \\ -1\ \\ \ \ 1\ \\ \ \ 0\ \end{bmatrix} + t\begin{bmatrix} -1\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 1\ \end{bmatrix}\,:\,s,t\in\mathbb{R}\,\right\} $$
Exercise 11 - Solve the Linear System¶
Use an augmented matrix, Gaussian elimination, and backward substitution to solve the linear system
$$ \begin{bmatrix} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ \\ \ \ 9\ &\ \ 5\ &\ 12\ &\ \ 1\ \\ -9\ & -6\ & -7\ &\ \ 3\ \\ \ \ 3\ &\ \ 4\ &\ \ 1\ &\ \ 5\ \end{bmatrix}\mathbf{x} = \begin{bmatrix}\ \ 4\ \\ \ 15\ \\ -13\ \\ -5\ \end{bmatrix} $$
View Solution
$$ \begin{align*} \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 9\ &\ \ 5\ &\ 12\ &\ \ 1\ &\ 15\ \\ -9\ & -6\ & -7\ &\ \ 3\ & -13\ \\ \ \ 3\ &\ \ 4\ &\ \ 1\ &\ \ 5\ & -5\ \end{array} \right] \begin{array}{l} \\ R_2-3R_1 \\ R_3+3R_1 \\ R_4-R_1 \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 0\ & -1\ &\ \ 3\ &\ \ 1\ &\ \ 3\ \\ \ \ 0\ &\ \ 0\ &\ \ 2\ &\ \ 3\ & -1\ \\ \ \ 0\ &\ \ 2\ & -2\ &\ \ 5\ & -9\ \end{array} \right] \begin{array}{l} \\ \\ \\ R_4+2R_2 \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 0\ & -1\ &\ \ 3\ &\ \ 1\ &\ \ 3\ \\ \ \ 0\ &\ \ 0\ &\ \ 2\ &\ \ 3\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 4\ &\ \ 7\ & -3\ \end{array} \right] \begin{array}{l} \\ \\ \\ R_4-2R_3 \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 0\ & -1\ &\ \ 3\ &\ \ 1\ &\ \ 3\ \\ \ \ 0\ &\ \ 0\ &\ \ 2\ &\ \ 3\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ & -1\ \end{array} \right] \begin{array}{l} \\ R_2-R_4 \\ R_3-3R_4 \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 0\ & -1\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 0\ &\ \ 0\ &\ \ 2\ &\ \ 0\ &\ \ 2\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ & -1\ \end{array} \right] \begin{array}{l} \\ -R_2 \\ \frac{1}{2}R_3 \qquad \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 3\ &\ \ 0\ &\ \ 4\ \\ \ \ 0\ &\ \ 1\ & -3\ &\ \ 0\ & -4\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ & -1\ \end{array} \right] \begin{array}{l} R_1-3R_3 \\ R_2+3R_3 \\ \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 2\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ & -1\ \end{array} \right] \begin{array}{l} R_1-2R_2 \\ \\ \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 3\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ & -1\ \end{array} \right] \begin{array}{l} \frac{1}{3}R_1 \\ \\ \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 1\ & -1\ \end{array} \right] \end{align*} $$The solution is
$$ \mathbf{x} = \begin{bmatrix}\ \ 1\ \\ -1\ \\ \ \ 1\ \\ -1\ \end{bmatrix} $$
The solution set is
$$ S = \left\{\,\begin{bmatrix}\ \ 1\ \\ -1\ \\ \ \ 1\ \\ -1\ \end{bmatrix}\,\right\} $$
Exercise 12 - Solve the Linear System¶
Use an augmented matrix, Gaussian elimination, and backward substitution to solve the linear system
$$ \begin{bmatrix} \ \ 3\ &\ \ 6\ &\ \ 3\ &\ \ 0\ \\ -6\ & -9\ & -3\ & -3\ \\ -3\ & -7\ & -4\ &\ \ 1\ \\ \ \ 3\ & -2\ & -5\ &\ \ 8\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} -3\ \\ \ \ 9\ \\ \ \ 2\ \\ -11\ \end{bmatrix} $$
View Solution
$$ \begin{align*} \left[ \begin{array}{cccc|c} \ \ 3\ &\ \ 6\ &\ \ 3\ &\ \ 0\ & -3\ \\ -6\ & -9\ & -3\ & -3\ &\ \ 9\ \\ -3\ & -7\ & -4\ &\ \ 1\ &\ \ 2\ \\ \ \ 3\ & -2\ & -5\ &\ \ 8\ & -11\ \end{array} \right] \begin{array}{l} \frac{1}{3}R_1 \\ -\frac{1}{3}R_2 \quad \\ \\ \\ \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 2\ &\ \ 1\ &\ \ 0\ & -1\ \\ \ \ 2\ &\ \ 3\ &\ \ 1\ &\ \ 1\ & -3\ \\ -3\ & -7\ & -4\ &\ \ 1\ &\ \ 2\ \\ \ \ 3\ & -2\ & -5\ &\ \ 8\ & -11\ \end{array} \right] \begin{array}{l} \\ R_2-2R_1 \\ R_3+3R_1 \\ R_4-3R_1 \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 2\ &\ \ 1\ &\ \ 0\ & -1\ \\ \ \ 0\ & -1\ & -1\ &\ \ 1\ & -1\ \\ \ \ 0\ & -1\ & -1\ &\ \ 1\ & -1\ \\ \ \ 0\ & -8\ & -8\ &\ \ 8\ & -8\ \end{array} \right] \begin{array}{l} \\ -R_2 \\ R_3-R_2 \\ R_4-8R_2 \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 2\ &\ \ 1\ &\ \ 0\ & -1\ \\ \ \ 0\ &\ \ 1\ &\ \ 1\ & -1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{array} \right] \begin{array}{l} R_1-2R_2 \\ \\ \\ \\ \end{array} \longrightarrow \\ \\ \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 0\ & -1\ &\ \ 2\ & -3\ \\ \ \ 0\ &\ \ 1\ &\ \ 1\ & -1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ \end{array} \right] &\ \end{align*} $$ To find the solution, we need to assign our free variables first. $$ \begin{align*} x_3 &= \alpha\in\mathbb{R} \\ x_4 &= \beta\in\mathbb{R} \\ \\ x_1 - \alpha + 2\beta &= -3 \\ x_1 &= -3 + \alpha - 2\beta \\ \\ x_2 + \alpha - \beta &= 1 \\ x_2 &= 1 - \alpha + \beta \\ \\ \mathbf{x} &= \begin{bmatrix} -3 + \alpha - 2\beta \\ 1 - \alpha + \beta \\ \alpha \\ \beta \end{bmatrix} = \begin{bmatrix} -3\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 0\ \end{bmatrix} + \begin{bmatrix}\ \ \alpha\ \\ -\alpha\ \\ \ \ \alpha\ \\ \ \ 0\ \end{bmatrix} + \begin{bmatrix} -2\beta\ \\ \ \ \beta\ \\ \ \ 0\ \\ \ \ \beta \end{bmatrix} \\ &= \begin{bmatrix} -3\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 0\ \end{bmatrix} + \alpha\begin{bmatrix}\ \ 1\ \\ -1\ \\ \ \ 1\ \\ \ \ 0\ \end{bmatrix} + \beta\begin{bmatrix} -2\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 1\ \end{bmatrix} \end{align*} $$The solution is the set $\left\{\,\begin{bmatrix} -3\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 0\ \end{bmatrix} + \alpha\begin{bmatrix}\ \ 1\ \\ -1\ \\ \ \ 1\ \\ \ \ 0\ \end{bmatrix} + \beta\begin{bmatrix} -2\ \\ \ \ 1\ \\ \ \ 0\ \\ \ \ 1\ \end{bmatrix}\,:\,\alpha,\ \beta\in\mathbb{R} \right\}$.
Exercise 13 - Solve the Linear System¶
Use an augmented matrix, Gaussian elimination, and backward substitution to solve the linear system
$$ \begin{bmatrix} \ \ 1\ &\ \ 0\ & -1\ &\ \ 1\ \\ -2\ &\ \ 1\ &\ \ 2\ & -2\ \\ -1\ & -1\ &\ \ 0\ & -2\ \\ \ \ 1\ & -2\ &\ \ 0\ &\ \ 2\ \end{bmatrix}\mathbf{x} = \begin{bmatrix} -2\ \\ \ \ 2\ \\ \ \ 3\ \\ \ \ 5\ \end{bmatrix} $$
View Solution
$$ \begin{align*} \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 0\ & -1\ &\ \ 1\ & -2\ \\ -2\ &\ \ 1\ &\ \ 2\ & -2\ &\ \ 2\ \\ -1\ & -1\ &\ \ 0\ & -2\ &\ \ 3\ \\ \ \ 1\ & -2\ &\ \ 0\ &\ \ 2\ &\ \ 5\ \end{array} \right] \begin{array}{l} \\ R_2+2R_1 \\ R_3+R_1 \\ R_4-R_1 \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 0\ & -1\ &\ \ 1\ & -2\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ & -2\ \\ \ \ 0\ & -1\ & -1\ & -1\ &\ \ 1\ \\ \ \ 0\ & -2\ &\ \ 1\ &\ \ 1\ &\ \ 7\ \end{array} \right] \longrightarrow \begin{array}{l} \\ \\ R_3+R_2 \\ R_4+2R_2 \end{array} \\ \\ \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 0\ & -1\ &\ \ 1\ & -2\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ & -2\ \\ \ \ 0\ &\ \ 0\ & -1\ & -1\ & -1\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ &\ \ 3\ \end{array} \right] \begin{array}{l} \\ \\ -R_3 \\ R_4+R_3 \end{array} &\longrightarrow \left[ \begin{array}{cccc|c} \ \ 1\ &\ \ 0\ & -1\ &\ \ 1\ & -2\ \\ \ \ 0\ &\ \ 1\ &\ \ 0\ &\ \ 0\ & -2\ \\ \ \ 0\ &\ \ 0\ &\ \ 1\ &\ \ 1\ &\ \ 1\ \\ \ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 0\ &\ \ 2\ \end{array} \right] \end{align*} $$The last row now reads
$$ 0x_1 + 0x_2 + 0x_3 + 0x_4 = 2 $$
Since this is impossible, this problem has no solution. The solution set is $\left\{\ \right\}=\emptyset$.
