Matrices and Gaussian elimination

When we solve a system by elimination, only the numbers change. The letters ${x}$, ${y}$, ${z}$ and the equals signs just come along. A matrix lets us write only the numbers. This makes the work shorter and neater, and it is how computers solve large systems.

Matrices

A matrix is a rectangular array of numbers. A matrix with ${m}$ rows and ${n}$ columns has size ${m\times n}$ (read "${m}$ by ${n}$"). The numbers in it are its entries.

The augmented matrix of a system lists the coefficients of each equation in a row, with the constant on the right side after a vertical bar. Each column belongs to one variable. For example:

$\begin{cases}x+y+z=4\\2x-y+z=8\\x+2y-z=-3\end{cases}$

has the augmented matrix

$\left[\begin{array}{rrr|r}1&1&1&4\\2&-1&1&8\\1&2&-1&-3\end{array}\right]$

Watch out: Write the equations with the variables in the same order first. Use ${0}$ for a missing variable. For example, ${2x+3y=4}$ in a system with ${x}$, ${y}$, ${z}$ has the row ${2\ \ 3\ \ 0\ \,|\ 4}$.

Row operations

The operations on equations from systems in three variables become operations on rows. ${R_1}$, ${R_2}$, ${R_3}$ name the rows.

1. Add a multiple of one row to another row. (${R_2-2R_1\to R_2}$ means: replace row ${2}$ by row ${2}$ minus ${2}$ times row ${1}$.)

2. Multiply a row by a nonzero number. (${\frac{1}{3}R_2\to R_2}$)

3. Swap two rows. (${R_2\leftrightarrow R_3}$)

These elementary row operations do not change the solutions of the system.

Row-echelon form

The goal is a matrix in row-echelon form:

This is the triangular form of the system. Changing a matrix to row-echelon form and then back-substituting is called Gaussian elimination.

Example 1: Solve the system above by Gaussian elimination.

Solution:

Start with the augmented matrix. First make zeros below the ${1}$ in the first column.

${R_2-2R_1\to R_2}$:

$\left[\begin{array}{rrr|r}1&1&1&4\\0&-3&-1&0\\1&2&-1&-3\end{array}\right]$

${R_3-R_1\to R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&4\\0&-3&-1&0\\0&1&-2&-7\end{array}\right]$

Next we want a ${1}$ in the second row, second column. Row ${3}$ already has a ${1}$ there, so swap.

${R_2\leftrightarrow R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&4\\0&1&-2&-7\\0&-3&-1&0\end{array}\right]$

Now make a zero below that ${1}$.

${R_3+3R_2\to R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&4\\0&1&-2&-7\\0&0&-7&-21\end{array}\right]$

Finally, make the third leading entry a ${1}$.

${-\frac{1}{7}R_3\to R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&4\\0&1&-2&-7\\0&0&1&3\end{array}\right]$

This is row-echelon form. Write it as a system again:

$\begin{cases}x+y+z=4\\y-2z=-7\\z=3\end{cases}$

Back-substitute: ${z=3}$, then ${y=-7+6=-1}$, then ${x=4-(-1)-3=2}$. The solution is ${(2,-1,3)}$.

Gauss-Jordan elimination

We can keep going until the matrix is in reduced row-echelon form: row-echelon form, with zeros also above each leading 1. Then the solution can be read off directly. This is called Gauss-Jordan elimination.

Example 2: Continue Example 1 to reduced row-echelon form.

Solution:

Work from the bottom up. Use the leading 1 in row ${3}$ to make zeros above it.

${R_2+2R_3\to R_2}$:

$\left[\begin{array}{rrr|r}1&1&1&4\\0&1&0&-1\\0&0&1&3\end{array}\right]$

${R_1-R_3\to R_1}$:

$\left[\begin{array}{rrr|r}1&1&0&1\\0&1&0&-1\\0&0&1&3\end{array}\right]$

Then use the leading 1 in row ${2}$ to make a zero above it.

${R_1-R_2\to R_1}$:

$\left[\begin{array}{rrr|r}1&0&0&2\\0&1&0&-1\\0&0&1&3\end{array}\right]$

Each row now says one thing: ${x=2}$, ${y=-1}$, ${z=3}$.

No solution or infinitely many

A row ${0\ \ 0\ \ 0\ |\ c}$ with ${c\ne 0}$ means ${0=c}$: the system has no solution.

A row of all zeros means ${0=0}$. If there are fewer leading 1s than variables, the system has infinitely many solutions.

A variable whose column has no leading 1 is a free variable. It can be any number ${t}$.

Example 3: Solve the system.

$\begin{cases}x-y+2z=1\\2x+y+z=8\\x+2y-z=7\end{cases}$

Solution:

Write the augmented matrix. Make zeros below the first leading 1.

${R_2-2R_1\to R_2}$ and ${R_3-R_1\to R_3}$:

$\left[\begin{array}{rrr|r}1&-1&2&1\\0&3&-3&6\\0&3&-3&6\end{array}\right]$

Rows ${2}$ and ${3}$ are the same. Subtract them, and make the second leading entry a ${1}$.

${R_3-R_2\to R_3}$, then ${\frac{1}{3}R_2\to R_2}$:

$\left[\begin{array}{rrr|r}1&-1&2&1\\0&1&-1&2\\0&0&0&0\end{array}\right]$

The last row is all zeros. There are only two leading 1s, for three variables. The column of ${z}$ has no leading 1, so ${z}$ is free. Let ${z=t}$. Back-substitute:

${y-z=2}$, so ${y=2+t}$.

$\begin{align*}x&=1+y-2z\\&=1+(2+t)-2t\\&=3-t\end{align*}$

The solutions are all triples ${(3-t,\ 2+t,\ t)}$, where ${t}$ is any real number.

Check with ${t=1}$, the triple ${(2,3,1)}$: ${2-3+2=1}$, ${\ 4+3+1=8}$, and ${2+6-1=7}$.

An application

Example 4: Find the parabola ${y=ax^2+bx+c}$ that passes through the points ${(1,2)}$, ${(2,3)}$, and ${(-1,6)}$.

Solution:

Each point gives one equation in the unknowns ${a}$, ${b}$, ${c}$. For example, ${(2,3)}$ gives ${3=a(2)^2+b(2)+c}$:

$\begin{cases}a+b+c=2\\4a+2b+c=3\\a-b+c=6\end{cases}$

Write the augmented matrix, and make zeros below the first leading 1.

${R_2-4R_1\to R_2}$ and ${R_3-R_1\to R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&2\\0&-2&-3&-5\\0&-2&0&4\end{array}\right]$

Row ${3}$ is easy to simplify. Then swap it into row ${2}$.

${-\frac{1}{2}R_3\to R_3}$, then ${R_2\leftrightarrow R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&2\\0&1&0&-2\\0&-2&-3&-5\end{array}\right]$

Make a zero below the second leading 1, and a leading 1 in row ${3}$.

${R_3+2R_2\to R_3}$, then ${-\frac{1}{3}R_3\to R_3}$:

$\left[\begin{array}{rrr|r}1&1&1&2\\0&1&0&-2\\0&0&1&3\end{array}\right]$

So ${c=3}$ and ${b=-2}$. Then ${a=2-b-c=2+2-3=1}$. The parabola is

${y=x^2-2x+3}$.

Check: At ${x=-1}$, ${y=1+2+3=6}$.

Summary

← Systems of linear equations in three variablesSystems of inequalities →