# Gaussian Elimination

Carl Friedrich**Gauss**lived during the late 18th century and early 19th century, but he is still considered one of the most prolific mathematicians in history. His contributions to the science of mathematics and physics span fields such as algebra, number theory, analysis, differential geometry, astronomy, and optics, among others. His discoveries regarding matrix theory changed the way mathematicians have worked for the last two centuries.

## Row Operations and the Augmented Matrix

A**matrix**can serve as a device for representing and solving a system of equations. To express a system in matrix form, we extract the coefficients of the variables and the constants, and these become the entries of the matrix. We use a vertical line to separate the coefficient entries from the constants, essentially replacing the equal signs. When a system is written in this form, we call it an

**augmented matrix**. For example, consider the following [latex]2\times 2[/latex] system of equations.

**coefficient matrix**.

**system of equations**such as

*x*-terms go in the first column,

*y*-terms in the second column, and

*z*-terms in the third column. It is very important that each equation is written in standard form [latex]ax+by+cz=d[/latex] so that the variables line up. When there is a missing variable term in an equation, the coefficient is 0.

### How To: Given a system of equations, write an augmented matrix.

- Write the coefficients of the
*x*-terms as the numbers down the first column. - Write the coefficients of the
*y*-terms as the numbers down the second column. - If there are
*z*-terms, write the coefficients as the numbers down the third column. - Draw a vertical line and write the constants to the right of the line.

### Example: Writing the Augmented Matrix for a System of Equations

Write the augmented matrix for the given system of equations.Answer: The augmented matrix displays the coefficients of the variables, and an additional column for the constants.

### Try It

Write the augmented matrix of the given system of equations.Answer: [latex]A+B=\left[\begin{array}{c}2\\ 1\\ 1\end{array}\begin{array}{c}6\\ \text{ }\text{ }\text{ }0\\ -3\end{array}\right]+\left[\begin{array}{c}3\\ 1\\ -4\end{array}\begin{array}{c}-2\\ 5\\ 3\end{array}\right]=\left[\begin{array}{c}2+3\\ 1+1\\ 1+\left(-4\right)\end{array}\begin{array}{c}6+\left(-2\right)\\ 0+5\\ -3+3\end{array}\right]=\left[\begin{array}{c}5\\ 2\\ -3\end{array}\begin{array}{c}4\\ 5\\ 0\end{array}\right][/latex]

### Row Operations

Now that we can write systems of equations in augmented matrix form, we will examine the various**row operations**that can be performed on a matrix, such as addition, multiplication by a constant, and interchanging rows. Performing row operations on a matrix is the method we use for solving a system of equations. In order to solve the system of equations, we want to convert the matrix to

**row-echelon form**, in which there are ones down the

**main diagonal**from the upper left corner to the lower right corner, and zeros in every position below the main diagonal as shown.

**row-equivalent**in a simpler form. Here are the guidelines to obtaining row-echelon form.

- In any nonzero row, the first nonzero number is a 1. It is called a
*leading*1. - Any all-zero rows are placed at the bottom on the matrix.
- Any leading 1 is below and to the right of a previous leading 1.
- Any column containing a leading 1 has zeros in all other positions in the column.

**coefficient matrix**to row-echelon form and do back-substitution to find the solution.

- Interchange rows. (Notation: [latex]{R}_{i}\leftrightarrow {R}_{j}[/latex] )
- Multiply a row by a constant. (Notation: [latex]c{R}_{i}[/latex] )
- Add the product of a row multiplied by a constant to another row. (Notation: [latex]{R}_{i}+c{R}_{j}[/latex])

### A General Note: Gaussian Elimination

The**Gaussian elimination**method refers to a strategy used to obtain the row-echelon form of a matrix. The goal is to write matrix [latex]A[/latex] with the number 1 as the entry down the main diagonal and have all zeros below.

### How To: Given an augmented matrix, perform row operations to achieve row-echelon form.

- The first equation should have a leading coefficient of 1. Interchange rows or multiply by a constant, if necessary.
- Use row operations to obtain zeros down the first column below the first entry of 1.
- Use row operations to obtain a 1 in row 2, column 2.
- Use row operations to obtain zeros down column 2, below the entry of 1.
- Use row operations to obtain a 1 in row 3, column 3.
- Continue this process for all rows until there is a 1 in every entry down the main diagonal and there are only zeros below.
- If any rows contain all zeros, place them at the bottom.

### Example: Performing Row Operations on a 3×3 Augmented Matrix to Obtain Row-Echelon Form

Perform row operations on the given matrix to obtain row-echelon form.Answer: The first row already has a 1 in row 1, column 1. The next step is to multiply row 1 by [latex]-2[/latex] and add it to row 2. Then replace row 2 with the result.

### Try It

Write the system of equations in row-echelon form.Answer: [latex]\left[\begin{array}{ccc}1& -\frac{5}{2}& \frac{5}{2}\\ \text{ }0& 1& 5\\ 0& 0& 1\end{array}|\begin{array}{c}\frac{17}{2}\\ 9\\ 2\end{array}\right][/latex]

### Q & A

#### Can any system of linear equations be solved by Gaussian elimination?

*Yes, a system of linear equations of any size can be solved by Gaussian elimination.*

### How To: Given a system of equations, solve with matrices using a calculator.

- Save the augmented matrix as a matrix variable [latex]\left[A\right],\left[B\right],\left[C\right]\text{,} \dots [/latex].
- Use the
**ref(**function in the calculator, calling up each matrix variable as needed.

### Example: Solving Systems of Equations Using a Calculator

Solve the system of equations.[latex]\begin{array}{r}\hfill 5x+3y+9z=-1\\ \hfill -2x+3y-z=-2\\ \hfill -x - 4y+5z=1\end{array}[/latex]

Answer: Write the augmented matrix for the system of equations.

[latex]\left[\begin{array}{rrr}\hfill 5& \hfill 3& \hfill 9\\ \hfill -2& \hfill 3& \hfill -1\\ \hfill -1& \hfill -4& \hfill 5\end{array}\text{ }|\text{ }\begin{array}{r}\hfill 5\\ \hfill -2\\ \hfill -1\end{array}\right][/latex]

On the matrix page of the calculator, enter the augmented matrix above as the matrix variable [latex]\left[A\right][/latex].[latex]\left[A\right]=\left[\begin{array}{rrrrrrr}\hfill 5& \hfill & \hfill 3& \hfill & \hfill 9& \hfill & \hfill -1\\ \hfill -2& \hfill & \hfill 3& \hfill & \hfill -1& \hfill & \hfill -2\\ \hfill -1& \hfill & \hfill -4& \hfill & \hfill 5& \hfill & \hfill 1\end{array}\right][/latex]

Use the**ref(**function in the calculator, calling up the matrix variable [latex]\left[A\right][/latex].

[latex]\text{ref}\left(\left[A\right]\right)[/latex]

Evaluate.[latex]\begin{array}{l}\hfill \\ \left[\begin{array}{rrrr}\hfill 1& \hfill \frac{3}{5}& \hfill \frac{9}{5}& \hfill \frac{1}{5}\\ \hfill 0& \hfill 1& \hfill \frac{13}{21}& \hfill -\frac{4}{7}\\ \hfill 0& \hfill 0& \hfill 1& \hfill -\frac{24}{187}\end{array}\right]\to \begin{array}{l}x+\frac{3}{5}y+\frac{9}{5}z=-\frac{1}{5}\hfill \\ \text{ }y+\frac{13}{21}z=-\frac{4}{7}\hfill \\ \text{ }z=-\frac{24}{187}\hfill \end{array}\hfill \end{array}

[/latex] Using back-substitution, the solution is [latex]\left(\frac{61}{187},-\frac{92}{187},-\frac{24}{187}\right)[/latex].### Applications of Systems of Equations

Now we will turn to the applications for which systems of equations are used. In the next example we determine how much money was invested at two different rates given the sum of the interest earned by both accounts.### Example: Applying 2 × 2 Matrices to Finance

Carolyn invests a total of $12,000 in two municipal bonds, one paying 10.5% interest and the other paying 12% interest. The annual interest earned on the two investments last year was $1,335. How much was invested at each rate?Answer: We have a system of two equations in two variables. Let [latex]x=[/latex] the amount invested at 10.5% interest, and [latex]y=[/latex] the amount invested at 12% interest.

[latex]\begin{array}{l}\text{ }x+y=12,000\hfill \\ 0.105x+0.12y=1,335\hfill \end{array}[/latex]

As a matrix, we have[latex]\left[\begin{array}{rr}\hfill 1& \hfill 1\\ \hfill 0.105& \hfill 0.12\end{array}\text{ }|\text{ }\begin{array}{r}\hfill 12,000\\ \hfill 1,335\end{array}\right][/latex]

Multiply row 1 by [latex]-0.105[/latex] and add the result to row 2.[latex]\left[\begin{array}{rr}\hfill 1& \hfill 1\\ \hfill 0& \hfill 0.015\end{array}\text{ }|\text{ }\begin{array}{r}\hfill 12,000\\ \hfill 75\end{array}\right][/latex]

Then,[latex]\begin{array}{l}0.015y=75\hfill \\ \text{ }y=5,000\hfill \end{array}[/latex]

So [latex]12,000 - 5,000=7,000[/latex]. Thus, $5,000 was invested at 12% interest and $7,000 at 10.5% interest.### Example: Applying 3 × 3 Matrices to Finance

Ava invests a total of $10,000 in three accounts, one paying 5% interest, another paying 8% interest, and the third paying 9% interest. The annual interest earned on the three investments last year was $770. The amount invested at 9% was twice the amount invested at 5%. How much was invested at each rate?Answer: We have a system of three equations in three variables. Let [latex]x[/latex] be the amount invested at 5% interest, let [latex]y[/latex] be the amount invested at 8% interest, and let [latex]z[/latex] be the amount invested at 9% interest. Thus,

[latex]\begin{array}{l}\text{ }x+y+z=10,000\hfill \\ 0.05x+0.08y+0.09z=770\hfill \\ \text{ }2x-z=0\hfill \end{array}[/latex]

As a matrix, we have[latex]\left[\begin{array}{rrr}\hfill 1& \hfill 1& \hfill 1\\ \hfill 0.05& \hfill 0.08& \hfill 0.09\\ \hfill 2& \hfill 0& \hfill -1\end{array}\text{ }|\text{ }\begin{array}{r}\hfill 10,000\\ \hfill 770\\ \hfill 0\end{array}\right][/latex]

Now, we perform Gaussian elimination to achieve row-echelon form.[latex]\begin{array}{l}\begin{array}{l}\hfill \\ -0.05{R}_{1}+{R}_{2}={R}_{2}\to \left[\begin{array}{rrrrrr}\hfill 1& \hfill & \hfill 1& \hfill & \hfill 1& \hfill \\ \hfill 0& \hfill & \hfill 0.03& \hfill & \hfill 0.04& \hfill \\ \hfill 2& \hfill & \hfill 0& \hfill & \hfill -1& \hfill \end{array}|\begin{array}{rr}\hfill & \hfill 10,000\\ \hfill & \hfill 270\\ \hfill & \hfill 0\end{array}\right]\hfill \end{array}\hfill \\ -2{R}_{1}+{R}_{3}={R}_{3}\to \left[\begin{array}{rrrrrr}\hfill 1& \hfill & \hfill 1& \hfill & \hfill 1& \hfill \\ \hfill 0& \hfill & \hfill 0.03& \hfill & \hfill 0.04& \hfill \\ \hfill 0& \hfill & \hfill -2& \hfill & \hfill -3& \hfill \end{array}|\begin{array}{rr}\hfill & \hfill 10,000\\ \hfill & \hfill 270\\ \hfill & \hfill -20,000\end{array}\right]\hfill \\ \frac{1}{0.03}{R}_{2}={R}_{2}\to \left[\begin{array}{rrrrrr}\hfill 0& \hfill & \hfill 1& \hfill & \hfill 1& \hfill \\ \hfill 0& \hfill & \hfill 1& \hfill & \hfill \frac{4}{3}& \hfill \\ \hfill 0& \hfill & \hfill -2& \hfill & \hfill -3& \hfill \end{array}|\begin{array}{rr}\hfill & \hfill 10,000\\ \hfill & \hfill 9,000\\ \hfill & \hfill -20,000\end{array}\right]\hfill \\ 2{R}_{2}+{R}_{3}={R}_{3}\to \left[\begin{array}{rrrrrr}\hfill 1& \hfill & \hfill 1& \hfill & \hfill 1& \hfill \\ \hfill 0& \hfill & \hfill 1& \hfill & \hfill \frac{4}{3}& \hfill \\ \hfill 0& \hfill & \hfill 0& \hfill & \hfill -\frac{1}{3}& \hfill \end{array}|\begin{array}{rr}\hfill & \hfill 10,000\\ \hfill & \hfill 9,000\\ \hfill & \hfill -2,000\end{array}\right]\hfill \end{array}[/latex]

The third row tells us [latex]-\frac{1}{3}z=-2,000[/latex]; thus [latex]z=6,000[/latex]. The second row tells us [latex]y+\frac{4}{3}z=9,000[/latex]. Substituting [latex]z=6,000[/latex], we get[latex]\begin{array}{r}\hfill y+\frac{4}{3}\left(6,000\right)=9,000\\ \hfill y+8,000=9,000\\ \hfill y=1,000\end{array}[/latex]

The first row tells us [latex]x+y+z=10,000[/latex]. Substituting [latex]y=1,000[/latex] and [latex]z=6,000[/latex], we get [latex-display]\begin{array}{l}x+1,000+6,000=10,000\hfill \\ \text{ }x=3,000\text{ }\hfill \end{array}[/latex-display] The answer is $3,000 invested at 5% interest, $1,000 invested at 8%, and $6,000 invested at 9% interest.### Try It

A small shoe company took out a loan of $1,500,000 to expand their inventory. Part of the money was borrowed at 7%, part was borrowed at 8%, and part was borrowed at 10%. The amount borrowed at 10% was four times the amount borrowed at 7%, and the annual interest on all three loans was $130,500. Use matrices to find the amount borrowed at each rate.Answer: $150,000 at 7%, $750,000 at 8%, $600,000 at 10%

## Key Concepts

- An augmented matrix is one that contains the coefficients and constants of a system of equations.
- A matrix augmented with the constant column can be represented as the original system of equations.
- Row operations include multiplying a row by a constant, adding one row to another row, and interchanging rows.
- We can use Gaussian elimination to solve a system of equations.
- Row operations are performed on matrices to obtain row-echelon form.
- To solve a system of equations, write it in augmented matrix form. Perform row operations to obtain row-echelon form. Back-substitute to find the solutions.
- A calculator can be used to solve systems of equations using matrices.
- Many real-world problems can be solved using augmented matrices.

## Glossary

**augmented matrix**a coefficient matrix adjoined with the constant column separated by a vertical line within the matrix brackets

**coefficient matrix**a matrix that contains only the coefficients from a system of equations

**Gaussian elimination**using elementary row operations to obtain a matrix in row-echelon form

**main diagonal**entries from the upper left corner diagonally to the lower right corner of a square matrix

**row-echelon form**after performing row operations, the matrix form that contains ones down the main diagonal and zeros at every space below the diagonal

**row-equivalent**two matrices [latex]A[/latex] and [latex]B[/latex] are row-equivalent if one can be obtained from the other by performing basic row operations

**row operations**adding one row to another row, multiplying a row by a constant, interchanging rows, and so on, with the goal of achieving row-echelon form

## Licenses & Attributions

### CC licensed content, Original

- Revision and Adaptation.
**Provided by:**Lumen Learning**License:**CC BY: Attribution.

### CC licensed content, Shared previously

- College Algebra.
**Provided by:**OpenStax**Authored by:**Abramson, Jay et al..**License:**CC BY: Attribution.**License terms:**Download for free at http://cnx.org/contents/[email protected]. - Question ID 125538.
**Authored by:**Jim Smart.**License:**CC BY: Attribution.**License terms:**IMathAS Community License CC-BY + GPL. - Question ID 84689.
**Authored by:**Alison Shelton.**License:**CC BY: Attribution.**License terms:**IMathAS Community License CC-BY + GPL. - Question ID 6369.
**Authored by:**David Lippman.**License:**CC BY: Attribution.**License terms:**IMathAS Community License CC-BY + GPL. - Question ID 2520.
**Authored by:**Greg Langkamp.**License:**CC BY: Attribution.**License terms:**IMathAS Community License CC-BY + GPL.

### CC licensed content, Specific attribution

- Precalculus.
**Provided by:**OpenStax**Authored by:**OpenStax College.**Located at:**https://cnx.org/contents/[email protected]:1/Preface.**License:**CC BY: Attribution.