Augmented matrix

In the linear equation in the $n$ unknowns $x_1, x_2, ..., x_n$

$\displaystyle a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n = b,$

the numbers $a_1, a_2, ..., a_n$ are called the coefficients of the equation, and $b$ is the constant term or right-hand side.

The coefficient row of the equation $a_1x_1 + a_2x_2 + a_3x_3 + ... + a_nx_n = b$ is the row matrix $[a_1\ \ a_2\ \ ...\ \ a_n\ \ b]$

The augmented matrix of a system of linear equations is the matrix whose rows are the coeficient rows of the equations.

Elementary row operations

When we solved linear systems of equations by elimination (see Part 1 of this summary) we did so by

• multiplying both sides of selected equations by constants, and then
• adding the resulting equations.

If we represent the equations as coefficients rows in a matrix, then what we did corresponds to multiplying rows by (nonzero) constants and then adding the resulting rows. These operations on rows are examples of elementary row operations, which are operations we can do on the augmented matrix of a system that do not change the solutions (if any) and allow us to obtain the solution.

We consider three kinds of operations we can do on the augmented matrix of a system without affecting the solution of the underlying system:

Type 1: Replacing $R_{i}$ by $aR_{i}$ where $a \neq 0$; that is, multiplying or dividing a row by a nonzero number

Type 2: Replacing $R_i$ by $aR_i \pm bR_j$ where $a \neq 0$; that is, multiplying a row by a nonzero number and adding or subtracting a multiple of another row

Type 3: Changing the order of the rows

For Types 1 and 2 we write the instruction for the row operation next to the row we wish to replace.

We are using the term "elementary row operations" more freely than most books do: Traditionally, one insists that $a = 1$ in an operation of Type 2, and that only row swaps are permitted in Type 3. However, our less restrictive operations can be obtained by combining two or more of the stricter operations, and also permit us to reduce integer matrices with fewer steps.

Important note
As observed above, elementary row operations do not effect the solutions (if any) of the corresponding system of equations, so, if the result of doing these operations is a nice and simple matrix like, say,

	$1$	$0$	$0$	$0$	$4$
	$0$	$1$	$0$	$0$	$-3$
	$0$	$0$	$1$	$0$	$\frac{3}{2}$
	$0$	$0$	$0$	$1$	$0$

then the original system of equations (whatever that was) has the solution

$x_1 = 4, x_2 = -3, x_3 = \dfrac{3}{2}, x_4 = 0$,

as that is what the above matrix is saying.

This is the reason we do row operaions: to simplify a matrix to the point that you can just read off the solution.

Clearing a column: Pivoting

If we select any nonzero entry in a matrix, we say that its column is cleared if all the other entries in that column are zero.:

Example:	$\begin{bmatrix} 4 & \color{indianred}{0} & -1 & 2 \\0 & \color{indianred}{0} & 1 & -1 \\7 & \color{indianred}{\box{-1}} & 9 & 0\\3 & \color{indianred}{0} & -2 & 0\end{bmatrix}$    has the (red) column of the boxed entry $-1$ cleared

Notice that, if the above matrix is thought of as the augmented matrix of a system of equations in three unknowns $x, y, z$, then the fact that the $y$ column is cleared means that $y$ has been eliminated from all the equations except the third one. In general:

Using elementary row operations to clear a column of some nonzero entry is equivalent to eliminating the corresponding variable from the other equations.

To pivot on a selected nonzero entry, called the pivot entry of a matrix means to use elementary row operations to clear its column.

How to pivot

Reduced row echelon form

If we have solved a system of $n$ linear equations in $n$ unknowns, then its augmented matrix will look like this:

	Solved system	Augmented matrix
$n = 2$	$x = a$ $y = b$	$1$ $0$ $a$   $0$ $1$ $b$
$n = 3$	$x = a$ $y = b$ $z = c$	$1$ $0$ $0$ $a$   $0$ $1$ $0$ $b$ $0$ $0$ $1$ $c$
. . .
General case	$x_1 = a_1$ $x_2 = a_2$ $x_3 = a_3$ $...$ $x_n = a_n$	$1$ $0$ $0$ $...$ $0$ $a_1$   $0$ $1$ $0$ $...$ $0$ $a_2$ $0$ $0$ $1$ $...$ $0$ $a_3$ $...$ $...$ $...$ $...$ $...$ $...$ $0$ $0$ $0$ $...$ $1$ $a_n$

All these matrices are in what we call reduced row echelon form. A matrix is in reduced row echelon form if it has the following properties:

• The leading entry (that is, the first non-zero entry) in each row is a 1.
  $\qquad$

  	$\box{1}$	$0$	$0$	$...$	$0$	$a_1$
  	$0$	$\box{1}$	$0$	$...$	$0$	$a_2$
  	$0$	$0$	$\box{1}$	$...$	$0$	$a_3$
  	$...$	$...$	$...$	$...$	$...$	$...$
  	$0$	$0$	$0$	$...$	$\box{1}$	$a_n$

  
  
  
• The column of every leading entry is clear (see "clearing a column" above).
  $\qquad$

  	$\color{indianred}{\box{1}}$	$\color{blue}{0}$	$\color{green}{0}$	$...$	$\color{purple}{0}$	$a_1$
  	$\color{indianred}{0}$	$\color{blue}{\box{1}}$	$\color{green}{0}$	$...$	$\color{purple}{0}$	$a_2$
  	$\color{indianred}{0}$	$\color{blue}{0}$	$\color{green}{\box{1}}$	$...$	$\color{purple}{0}$	$a_3$
  	$...$	$...$	$...$	$...$	$...$	$...$
  	$\color{indianred}{0}$	$\color{blue}{0}$	$\color{green}{0}$	$...$	$\color{purple}{\box{1}}$	$a_n$
  	$\color{indianred}{\Big\uparrow}$	$\color{blue}{\Big\uparrow}$	$\color{green}{\Big\uparrow}$	$\ $	$\color{purple}{\Big\uparrow}$	$\ $

  
  Columns of the leading entries cleared
  
  
• The rows are arranged so that the leading entries go from left to right as you go down the rows. Further, rows of zeros (if any) are at the bottom. (There are none in the examples we have seen so far.)

We will call a matrix reduced if it is in row reduced echelon form.

Reducing a matrix: Preliminary step and simplifying steps

Basically, all you need to do to row reduce a matrix to row echeclon form is to pivot on the leading entry of each row and then rearrange the rows if necessary so that the leading entries go from left to right and any rows of zeros are at the bottom. However, as we prefer to work with integral matrices, there is a preliminary step and some (optional) intermediate steps that make the calculations a lot easier. Here is the preliminary step:

Preliminary step: Clear al fractions and decimals (if any) before starting

We clear fractions and (terminating) decimals by multiplying the rows that contain them by suitable nonzero integers.

Specifically, we clear fractions in any row by multiplying that row by a common multiple of the denominators appearing in that row (preferably the lowest common multiple to avoid numbers that are too large: see the simplification step below). To clear terminsting decimals, multiply by a large enough whole number (like 4, 5, 10, 20, 40, 50, 100, .. etc.). Repeating decimals should first be converted to fractions.

Simplifying step (optional): Divide each row by any common factor (if there is one)

This (optional) step can be done at any point of the calculation. Although optional,it makes the integers we work with as small as possible, and so the calculations will be easier. For instance, if all the numbers in a row are even, divide that row by 2, or if all the numbers in a row are divisible by 10, then divide that row by 10. Make sure that it is a common factor, or else fractions will result and we would defeat the puepose of the preliminary step.

Reducing a matrix and solving the associated system (unique solution case):

Once the matrix is in integral form (and preferably simplified to avoid big numbers) the reduction process is as follows:

• Pivot on the leading entry (that is, the first nonzero entry) in the first row.
• Then, pivot on the leading entry in the second row, then the leading entry in the third row, continuing in this way until the columns of every leading entry are cleared.
• At each stage of this process, do simplifications steps if applicable.
• When done, that the matrix is essentially reduced, apart from possibly having to reorder the rows.

Reducing a matrix and solving the associated system (non-unique solution or no solution):

Notice that what results when you were done with the above example had a particularly nice form: the diagonal entries are all ones. However, the next exapmle shows that you may not always wind up with that kind of result: