We've seen how to solve linear systems using Gaussian Elimination, but we've only seen examples where there is one solution. In this lecture, we will see other cases.

Let's start with a new term.

In the previous lecture, we solved the system:

$$\large \begin{split} x+y+2z&=9\\ 2x+4y-3z&=1\\ 3x+6y-5z&=0\\ \end{split} $$

From the coefficient matrix, we made an augmented matrix, and we used row operations until we reached the form where we could read off the solution:

$$ \large \begin{bmatrix} 1 & 1 & 2 & : & 9 \\ 2 & 4 & -3 & : & 1 \\ 3 & 6 & -5 & : & 0 \end{bmatrix} \sim \begin{bmatrix} 1 & 0 & 0 & : & 1 \\ 0 & 1 & 0 & : & 2 \\ 0 & 0 & 1 & : & 3 \end{bmatrix} $$

The coefficient matrix is said to be row equivalent to

$$\large \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix}$$

This matrix is in reduced row echelon form or rref. This form is characterized by four requirements:

1. If there are any rows of all zeros, they occur at the bottom of the matrix.
2. The first non-zero entry in any row is a 1 (called a leading one or a pivot).
3. Each leading one is to the right of the leading one in the row above it.
4. Every other entry in the column of a leading one is a zero.

Here are a few examples of matrices in rref:

$$\large \begin{bmatrix} 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & 1 \\ \end{bmatrix}, \hspace{.2in} \begin{bmatrix} 1 & 0 & 4 & 0 \\ 0 & 1 & 5 & 0 \\ 0 & 0 & 0 & 1 \\ 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 \\ \end{bmatrix}, \hspace{.2in} \begin{bmatrix} 1 & 2 & 0 & 0 & 2 & 0 \\ 0 & 0 & 1 & 0 & 5 & 0 \\ 0 & 0 & 0 & 1 & -3 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 \\ \end{bmatrix}, \hspace{.2in} \begin{bmatrix} 0 & 1 \\ 0 & 0 \\ \end{bmatrix} $$

Every matrix is row equivalent to a matrix in rref, and the process of Gaussian Elimination always ends with a matrix in rref.

We can now describe the solution process as:

• Get the augmented matrix.
• Use Gaussian Elimination to put the matrix in rref.
• Read off the solution.

Armed with this new terminology, we can now discuss different scenarios.

This is the scenario we've already seen. If $\large A$ is row equivalent to the identity matrix, then $\large A \vec{x}=\vec{b}$ is consistent and has one solution. As an example:

$$\large \begin{bmatrix} 2 & 1 & -1 & : &-1\\ -1 & 3 & 1 & : &-1\\ 3& -1 & 2 & : & 15\\ \end{bmatrix}\sim \begin{bmatrix} 1 & 0 & 0 & : &2\\ 0 & 1 & 0 & : &-1\\ 0& 0 & 1 & : & 4\\ \end{bmatrix} $$

In this case, we see easily that $\large x=2$, $\large y=-1$, and $\large z=4$.

If $\large A$ is row equivalent to a matrix with a row of zeros, we could end up in the following scenario:

$$\large \begin{bmatrix} 1 & 2 & -1 & : &4\\ 2 & 4 & 1 & : &5\\ 3& 6 & -2 & : & 10\\ \end{bmatrix}\sim \begin{bmatrix} 1 & 2 & -1 & : &4\\ 0 & 0 & 1 & : &-1\\ 0& 0 & 0 & : & -1\\ \end{bmatrix} $$

In this case, that last row represents the equation $\large 0x+0y+0z=-1$, which is nonsense! Arriving at an equation like this is an indication that the system has no solution.

There's another possibility if $\large A$ is row equivalent to a matrix with a row of zeros. The following can happen:

$$\large \begin{bmatrix} 1 & 2 & -1 & : &3\\ 2 & 5 & 1 & : &10\\ 3& 7 & 0 & : & 13\\ \end{bmatrix}\sim \begin{bmatrix} 1 & 0 & -7 & : &-5 \\ 0 & 1 & 3 & : & 4\\ 0& 0 & 0 & : & 0\\ \end{bmatrix} $$

That last equation now represents $\large 0x+0y+0z=0$, which is trivially true! What does this mean? Let's see a short video on how to interpret this scenario:

We that when we have infinitely many solutions, we still want to describe the solution set. Is it every point on a line? A plane? How many free variables are there in the solution set? The answer to all these questions comes from the rref form and the process outlined in the video.

If we have more equations than unknowns, the system is known as overdetermined or overconstrained. We are attempting to place too many constraints on too few variables. In this case, the matrix $\large A$ is tall and skinny. This scenario usually, but not always, leads to an inconsistent system.

Let's take the following system as an example:

$$\large \begin{split} x+y+z &= 3\\ x-y+z&=1\\ x+y-z&=1\\ 2x+y+z&=4\\ x+2y+2z&=9\\ \end{split} $$

This turns into an augmented matrix, which we put into rref. We have:

$$\large \begin{bmatrix} 1 & 1 & 1 & : &3\\ 1 & -1 & 1 & : &1\\ 1& 1 & -1 & : & 1\\ 2& 1 & 1 & : & 4\\ 1& 2 & 2 & : & 9\\ \end{bmatrix}\sim \begin{bmatrix} 1 & 0 & 0 & : & 0 \\ 0 & 1 & 0 & : & 0 \\ 0 & 0 & 1 & : & 0 \\ 0 & 0 & 0 & : & 1 \\ 0 & 0 & 0 & : & 0 \\ \end{bmatrix} $$

The fourth row of the augmented system in rref gives us the contradiction to know this system is inconsistent (Why is the third row not a problem?).

Our last scenario is the case when the system is underdetermined, meaning we have more variables than constraints. An underdetermined system usually (but not always) leads to infinitely many solutions since there aren't enough equations to tie us down to a single solution.

Let's take the following system as an example (we have too many variable to use $\large x, y, z$, so we use subscripts on the uknowns now):

$$\large \begin{split} x_1+2x_2-x_3+3x_4+2x_5&=5\\ 2x_1+4x_2-x_3+8x_4+x_5&=7\\ x_1+2x_2+2x_3+6x_4-5x_5&=2\\ \end{split} $$

This turns into an augmented matrix, which we put into rref. We have:

$$\large \begin{bmatrix} 1 & 2 & -1 & 3 & 2 & : &5\\ 2 & 4 & -1 & 8 & 1 & : &7\\ 1 & 2 & 2 & 6 & -5 & : &2\\ \end{bmatrix}\sim \begin{bmatrix} 1 & 2 & 0 & 0 & \frac{7}{3} & : &12 \\ 0 & 0 & 1 & 0 & -\frac{5}{3} & : &1 \\ 0 & 0 & 0 & 1 & -\frac{2}{3} & : &-2 \\ \end{bmatrix} $$

How do we characterize the solutions in this case? The video will show how we do it:

We see that if we have 5 variables and 3 leading ones in rref, we will have a solution set characterized by two free variables. This is true in general: leading ones + free variables = total number of variables.

The examples we've seen lead naturally to a definition:

Definition: The rank of a matrix is the number of leading ones in the rref of the matrix.

The rank of $\large A$ relates to solutions of $\large A\vec{x}=\vec{b}$, as we've seen, but it is also an important concept when dealing with data. Essentially, the rank of a matrix is an indicator of how much of the information in the matrix is unique and how much is redundant. If a $\large 5\times 5$ matrix has rank 3, then 2 of the rows are redundant in some way.

In terms of $\large A\vec{x}=\vec{b}$, if $\large A$ is $\large 5\times 5$ but has rank 3, two of the equations are redundant, and we actually only have 3 equations for 5 unknowns. We'll have infinitely many solutions with two free variables.

We've now seen examples covering all the possibilities. Let's summarize what we know about $\large A\vec{x}=\vec{b}$ based on Gaussian elimination:

• If there is a line $\large \left[ 0 \quad 0 \quad 0 \quad \dots \quad 0 \quad : \quad c \right]$ for a nonzero $\large c$ in the rref of the augmented matrix, the system is inconsistent. Otherwise, it is consistent.
• If the system is consistent, and if the number of leading ones in the rref of $\large A$ (not the augmented part) is equal to the number of columns in $\large A$, the solution is unique. Otherwise, there are infinitely many solutions.
• If there are infinitely many solutions, the number of free variables is the number of columns of $\large A$ minus the number of leading ones in the rref of $\large A$.

With Gaussian elimination, we can now add to our list of equivalencies for square matrices:

The following are all equivalent facts about a square $\large n\times n$ matrix $\large A$.

1. $\large A$ is invertible.
2. $\large \text{det}(A)\ne 0$.
3. $\large A$ is row equivalent to $\large I$, the identity matrix.
4. $\large A\vec{x}=\vec{0}$ has only the trivial solution.
5. $\large A\vec{x}=\vec{b}$ has a unique solution for any $\large \vec{b}$.

Definition: A square matrix $\large A$ that meets the above criteria is called nonsingular. Otherwise, the matrix is called singular.

I can:

• Recognize if a matrix is in rref.
• Put any matrix into rref using Gaussian elimination.
• Solve any system of equations using Gaussian elimination.
• Parametrically describe the solution set when there are infinitely many solutions.
• Identify the rank of a matrix by looking its equivalent matrix in rref.