Solving Systems and Row Reduction

Section 4.2 Solving Systems and Row Reduction

Subsection 4.2.1 System of Linear Equations

So far, the focus of this course has been geometric. In this section, I change my perspective to look at the algebraic side of linear algebra. A major problem in algebra is solving systems of equations: given several equations in several variables, can I find values for each variable that satisfy all the equations? In general, algebra considers any kind of equation.

Example 4.2.1.

\begin{align*} x^2 + y^2 + z^2 \amp = 3\\ xy + 2xz - 3yz \amp = 0\\ x+y+z \amp = 3 \end{align*}

This system is solved by \(\begin{pmatrix} x \\ y \\ z \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 1 \end{pmatrix}\) When substituted in the equations, these values satisfy all three. No other triples satisfy, so this is a unique solution.

Solving arbitrary systems of equations is a very difficult problem. There are two initial techniques, which are usually taught in high-school mathematics: isolating and replacing variables; or performing arithmetic with the equations themselves. Both are useful techniques. However, when the equations become quite complicated, both methods can fail. In that case, solutions to systems can only be approached with approximation methods. The methodology of these approximations is a whole branch of mathematics in itself.

I am going to restrict myself to a class of systems that are more approachable: systems of linear equations. Recall the definition of a linear equation from Definition 3.2.2.

Definition 4.2.2.

Let \(a_i\) and \(c\) be real numbers. A linear equation in the variables \(x_1, x_2 \ldots, x_n\) is an equation of the following form.

\begin{equation*} a_1 x_1 + a_2 x_2 + \ldots + a_n x_n = c \end{equation*}

Given a fixed set of variables \(x_1, x_2, \ldots, x_n\text{,}\) I want to consider systems of linear equations in those variables. While much simpler than the general case, linear systems are a common and useful type of system to consider. Such systems also work well with arithmetic solution techniques since I can add two linear equations together and still have a linear equation.

This turns out to be the key idea: I can do arithmetic with linear equations. Specifically, there are three things I can do with a system of linear equations. These three techniques preserve the solutions; that is, they don’t alter the values of the variables that solve the system.

Multiply a single equation by a (non-zero) constant. (Multiplying both sides of the equation, of course).
Change the order of the equations.
Add one equation to another.

If I combine the first and third, I could restate the third as: add a multiple of one equation to another. In practice, I often think of the third operation this way.

Subsection 4.2.2 Matrix Represetation of Systems of Linear Equations

If I worked with the equations directly, I would find, with careful application of the three techniques, I could always solve linear systems. However, the notation becomes cumbersome for large systems. Therefore, matrices are used to encode the information in a nicely organized way.

Consider a general system with \(m\) equations in the variables \(x_1, x_2, \ldots, x_n\text{,}\) where \(a_{ij}\) and \(c_i\) are real numbers.

\begin{align*} \amp a_{11} x_1 + a_{12} x_2 + \ldots a_{1n} x_n \amp = \amp c_1\\ \amp a_{21} x_1 + a_{22} x_2 + \ldots a_{2n} x_n \amp = \amp c_2\\ \amp \vdots \amp \vdots \amp\\ \amp a_{m1} x_1 + a_{m2} x_2 + \ldots a_{mn} x_n \amp = \amp c_m \end{align*}

I encode this as an extended matrix by taking the \(a_{ij}\) and the \(c_i\) as the matrix coefficients. I drop the \(x_i\text{,}\) keeping track of them implicitly by their positions in the matrix. The result is a \(m \times (n+1)\) extended matrix where the vertical line notes the position of the equals sign in the original equation.

\begin{equation*} \left( \begin{array}{cccc|c} a_{11} \amp a_{12} \amp \ldots \amp a_{1n} \amp c_1 \\ a_{21} \amp a_{22} \amp \ldots \amp a_{2n} \amp c_2 \\ \vdots \amp \vdots \amp \vdots \amp \vdots \amp \vdots \\ a_{m1} \amp a_{m2} \amp \ldots \amp a_{mn} \amp c_1 \end{array} \right) \end{equation*}

Example 4.2.3.

\begin{align*} -x+3y+6z \amp = 1\\ 2x + 2y + 2z \amp = -6\\ 5x-5y+z \amp = 0 \end{align*}

I transfer the coefficients into the matrix representation.

\begin{equation*} \left( \begin{array}{ccc|c} -1 \amp 3 \amp 6 \amp 1 \\ 2 \amp 2 \amp 2 \amp -6 \\ 5 \amp -5 \amp 1 \amp 0 \end{array} \right) \end{equation*}

Example 4.2.4.

\begin{align*} -3x-10y+15z \amp = -34\\ 20x - y + 19z \amp = 25\\ 32x + 51y - 31z \amp = 16 \end{align*}

I transfer the coefficients into the matrix representation.

\begin{equation*} \left( \begin{array}{ccc|c} -3 \amp -10 \amp 15 \amp -34 \\ 20 \amp -1 \amp 19 \amp 25 \\ 32 \amp 51 \amp -31 \amp 16 \end{array} \right) \end{equation*}

Example 4.2.5.

Sometimes not every equation explicitly mentions each variable.

\begin{align*} x-2z \amp = 0\\ 2y + 3z \amp = - 1\\ -3x - 4y \amp = 9 \end{align*}

This system is clarified by adding the extra variables with coefficient \(0\text{.}\)

\begin{align*} x + 0y -2z \amp = 0\\ 0x + 2y + 3z \amp = - 1\\ -3x - 4y + 0z \amp = 9 \end{align*}

Then it can be clearly encoded as a matrix.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp -2 \amp 0 \\ 0 \amp 2 \amp 3 \amp -1 \\ -3 \amp -4 \amp 0 \amp 9 \end{array} \right) \end{equation*}

In this way, I can change any system of linear equations into an extended matrix (with one column after the vertical line) and any such extended matrix into a system of equations. The columns represent the hidden variables. In the examples above, the first column is the \(x\) column; the second is the \(y\) column; the third is the \(z\) column; and the column after the vertical line is the column of constants.

Subsection 4.2.3 Row Operations and Gaussian Elimination

I defined three operations on systems of equations. Now that I have encoded systems as matrices, I need to understand the equivalent operations for matrices. Each equation in the system gives a row in the matrix; therefore, equation operations become row operations.

Multiply an equation by a non-zero constant \(\implies\) multiply a row by a non-zero constant.
Change the order of the equations \(\implies\) exchange two rows of a matrix.
Add (a multiple of) an equation to another equation \(\implies\)add (a multiple of) one row to another row.

Since the original operations didn’t change the solution of a system of equations, the row operations on matrices also preserve the solution of the associated system.

In addition, I need to know what a solution looks like in matrix form.

Example 4.2.6.

This example shows the encoding of a direction solution.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp -3 \\ 0 \amp 1 \amp 0 \amp -2 \\ 0 \amp 0 \amp 1 \amp 8 \end{array} \right) \end{equation*}

The system has three columns before its vertical line; therefore it corresponds to a system of equations in \(x,y,z\text{.}\) If I translate this back into equations, I get the following system.

\begin{align*} x + 0y + 0z \amp = -3\\ 0z + y + 0z \amp = -2\\ 0x + 0y + z \amp = 8 \end{align*}

Removing the zero terms gives \(x=-3\text{,}\) \(y=-2\) and \(z=8\text{.}\) This equation delivers its solution directly: no work is necessary. I just read the solution off the page.

There is a name for the special form of a matrix where I can directly read the solutions of the associated linear system.

Definition 4.2.7.

A matrix is a reduced row-echelon matrix or is said to be in reduced row-echelon form if the following things are true:

The first non-zero entry in each row is one. (A row entirely of zeros is fine). These entries are called leading ones.
Each leading one is in a column where all the other entries are zero.

As long as an extended matrix is in reduced row-echelon form, I can always directly read off the solution to the system.

Knowing how to recognize solutions in matrix form and knowing the row operations, I can now describe the full matrix-based approach to solving linear systems. First, I translate a system into a matrix. Then, I use row operations (which don’t change the solution at all) to turn the matrix into reduced row-echelon form, where I can just read off the solution. Row operations will always be able to accomplish this.

Definition 4.2.8.

The process of using row operations to change a matrix into reduced row-echelon form is called Gaussian elimination or row reduction. This process proceeds in the following steps.

Choose a row that has a non-zero entry in the first column. (Often, I exchange this row with the first so that I am working on the first row).
Multiply by a constant to get a leading one in the chosen row.
Now that there is a leading one, I want to clear all the other entries in the column containing that leading one. Therefore, I add multiples of the row with the leading one to the other rows, one by one, to make those column entries zero.
The steps so far produce a column with a leading one in the first column and sets all other first column entries to zero.
Then I proceed to the next column and repeat the process all over again. Any column, which is all zeros is skipped.
The process stops when every row either starts with a leading one or is a row entirely of zeros.

Definition 4.2.9.

The rank of a matrix is the number of leading ones in its reduced row-echelon form.

Subsection 4.2.4 Examples of Row Reduction

Example 4.2.10.

Solve this system with row reduction.

\begin{gather*} x + z = 4 \\ 3x - y + 2z = 0 \\ y -5z = -3 \end{gather*}

I first turn the system into a matrix.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 4 \\ 3 \amp -1 \amp 2 \amp 0 \\ 0 \amp 1 \amp -5 \amp -3 \end{array} \right) \end{equation*}

Then I will row reduce. For the examples here, I’m going to be very explicit and show each little step. (As I do more and more row reductions, this level of detail will be unnecessary.) There is already a leading one in the first row, so I try to clear its column. There is a three below it. To remove that three, I subtract three times the first row from the second.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 4 \\ 0 \amp -1 \amp -1 \amp -12 \\ 0 \amp 1 \amp -5 \amp -3 \end{array} \right) \end{equation*}

Then the first column is finished. Now I want a leading one in the second row. To get this, I’ll exchange the second and third rows.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 4 \\ 0 \amp 1 \amp -5 \amp -3 \\ 0 \amp -1 \amp -1 \amp -12 \end{array} \right) \end{equation*}

Then I have a leading one in the second row. I want to clear its column. There is already a zero above, but I need to clear the \(-1\) below. To do that, I add the second row to the third.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 4 \\ 0 \amp 1 \amp -5 \amp -3 \\ 0 \amp 0 \amp -6 \amp -15 \end{array} \right) \end{equation*}

That finishes the second column. Now I want a leading one in the third row. To get that, I divide the third row by \(-6\text{.}\)

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 1 \amp 4 \\ 0 \amp 1 \amp -5 \amp -3 \\ 0 \amp 0 \amp 1 \amp \frac{5}{2} \end{array} \right) \end{equation*}

Then I need to clear the column above this leading one. I first subtract the third row from the first row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp \frac{3}{2} \\ 0 \amp 1 \amp -5 \amp -3 \\ 0 \amp 0 \amp 1 \amp \frac{5}{2} \end{array} \right) \end{equation*}

Then I add \(5\) times the third row to the second.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp \frac{3}{2} \\ 0 \amp 1 \amp 0 \amp \frac{19}{2} \\ 0 \amp 0 \amp 1 \amp \frac{5}{2} \end{array} \right) \end{equation*}

The matrix is now in reduced row-echelon form and I can read off the unique solution.

\begin{align*} \amp x = \frac{3}{2} \amp \amp y = \frac{19}{2} \amp \amp z = \frac{5}{2} \end{align*}

Example 4.2.11.

Solve this system with row reduction.

\begin{gather*} 2x + y - 3z = 1\\ 4x + z = 7 \\ -3x - 3y + 2z = 0 \end{gather*}

I turn the system to a matrix.

\begin{equation*} \left( \begin{array}{ccc|c} 2 \amp 1 \amp -3 \amp 1 \\ 4 \amp 0 \amp 1 \amp 7 \\ -3 \amp -3 \amp 2 \amp 0 \end{array} \right) \end{equation*}

I want to make a leading one in the first row, so I divide the first row by \(2\text{.}\)

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp \frac{1}{2} \amp \frac{-3}{2} \amp \frac{1}{2} \\ 4 \amp 0 \amp 1 \amp 7 \\ -3 \amp -3 \amp 2 \amp 0 \end{array} \right) \end{equation*}

Then I want to clear the column under this leading one. I start by subtracting \(4\) times the first row from the second row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp \frac{1}{2} \amp \frac{-3}{2} \amp \frac{1}{2} \\ 0 \amp -2 \amp 7 \amp 5 \\ -3 \amp -3 \amp 2 \amp 0 \end{array} \right) \end{equation*}

Then I add \(3\) times the first row to the third row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp \frac{1}{2} \amp \frac{-3}{2} \amp \frac{1}{2} \\ 0 \amp -2 \amp 7 \amp 5 \\ 0 \amp \frac{-3}{2} \amp \frac{-5}{2} \amp \frac{3}{2} \end{array} \right) \end{equation*}

That finishes the first column. Next, I want a leading one in the second row. To get that, I divide the second row by \(-2\text{.}\)

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp \frac{1}{2} \amp \frac{-3}{2} \amp \frac{1}{2} \\ 0 \amp 1 \amp \frac{-7}{2} \amp \frac{-5}{2} \\ 0 \amp \frac{-3}{2} \amp \frac{-5}{2} \amp \frac{3}{2} \end{array} \right) \end{equation*}

Then I want to clear the column above and below this leading one. First, I’ll subtract \(\frac{1}{2}\) times the second row from the first row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp \frac{1}{4} \amp \frac{7}{4} \\ 0 \amp 1 \amp \frac{-7}{2} \amp \frac{-5}{2} \\ 0 \amp \frac{-3}{2} \amp \frac{-5}{2} \amp \frac{3}{2} \end{array} \right) \end{equation*}

Then I’ll add \(\frac{3}{2}\) times the second row to the third row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp \frac{1}{4} \amp \frac{7}{4} \\ 0 \amp 1 \amp \frac{-7}{2} \amp \frac{-5}{2} \\ 0 \amp 0 \amp \frac{-31}{4} \amp \frac{-9}{4} \end{array} \right) \end{equation*}

That finishes the second column. Now I need a leading one in the third row. To get that, I’ll divide the third row by \(\frac{-31}{4}\text{.}\)

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp \frac{1}{4} \amp \frac{7}{4} \\ 0 \amp 1 \amp \frac{-7}{2} \amp \frac{-5}{2} \\ 0 \amp 0 \amp 1 \amp \frac{9}{31} \end{array} \right) \end{equation*}

Now I need to clear the column above the leading one. (The arithmetic is starting to get pretty annoying here, but I will press on. I made good use of a computer algebra system to do the fraction arithmetic for me.) First, I subtract \(\frac{1}{4}\) times the third row from the first row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp \frac{52}{31} \\ 0 \amp 1 \amp \frac{-7}{2} \amp \frac{-5}{2} \\ 0 \amp 0 \amp 1 \amp \frac{9}{31} \end{array} \right) \end{equation*}

Then I add \(\frac{7}{2}\) times the third row to the second row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp 0 \amp \frac{52}{31} \\ 0 \amp 1 \amp 0 \amp \frac{-46}{31} \\ 0 \amp 0 \amp 1 \amp \frac{9}{31} \end{array} \right) \end{equation*}

This is the reduced row echelon form. Now I can read off the solution.

\begin{align*} \amp x = \frac{52}{31} \amp \amp y = \frac{-46}{31} \amp \amp z = \frac{9}{31} \end{align*}

Example 4.2.12.

Solve this system with row reduction.

\begin{gather*} 2x - 6y + z = 9\\ x + 4y - 2z = -2 \\ 5x + 6y - 5z = 3 \end{gather*}

I turn the system into a matrix.

\begin{equation*} \left( \begin{array}{ccc|c} 2 \amp -6 \amp 1 \amp 9 \\ 1 \amp 4 \amp -2 \amp -2 \\ 5 \amp 6 \amp -5 \amp 3 \end{array} \right) \end{equation*}

Then I want to row reduce this. I start by interchanging rows one and two, to get a leading one in the first row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 4 \amp -2 \amp -2 \\ 2 \amp -6 \amp 1 \amp 9 \\ 5 \amp 6 \amp -5 \amp 3 \end{array} \right) \end{equation*}

Then I want to clear the column below the leading one. I subtract \(2\) times the first row from the second.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 4 \amp -2 \amp -2 \\ 0 \amp -14 \amp 5 \amp 13 \\ 5 \amp 6 \amp -5 \amp 3 \end{array} \right) \end{equation*}

Then I subtract \(5\) times the first row from the third row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 4 \amp -2 \amp -2 \\ 0 \amp -14 \amp 5 \amp 13 \\ 0 \amp -14 \amp 5 \amp 13 \end{array} \right) \end{equation*}

Immediately, I notice something odd. I can subtract the second row from the third to clear it entirely.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 4 \amp -2 \amp -2 \\ 0 \amp -14 \amp 5 \amp 13 \\ 0 \amp 0 \amp 0 \amp 0 \end{array} \right) \end{equation*}

Then I can keep going, by dividing the second row by \(-14\text{.}\)

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 4 \amp -2 \amp -2 \\[1em] 0 \amp 1 \amp \frac{-5}{14} \amp \frac{-13}{14} \\ 0 \amp 0 \amp 0 \amp 0 \end{array} \right) \end{equation*}

Then I need to clear above this new leading one. I subtract \(4\) times the second row from the first row.

\begin{equation*} \left( \begin{array}{ccc|c} 1 \amp 0 \amp \frac{-24}{7} \amp \frac{-40}{7} \\[1em] 0 \amp 1 \amp \frac{-5}{14} \amp \frac{-13}{14} \\ 0 \amp 0 \amp 0 \amp 0 \end{array} \right) \end{equation*}

This matrix is now in reduced row-echelon form. There is nothing more to be done. However, reading off the solution isn’t as obvious in this case. I will go over this kind of solution in the next section of the notes.

Prev Top Next