15. Reduced echelon form

15. Reduced echelon form

Definition

Definition:

A matrix is in reduced echelon form if:

  • it's in echelon form,

  • all its leading entries are equal to 1,

  • (*) in any column containing a leading entry, there are no other nonzero entries.

Consider the following matrices: The 3-by-3 matrix A equals 1, 2, 3; 0, 1, 2; 0, 0, 1. The 1-by-2 matrix B equals 1, 1. The 2-by-4 matrix C equals 1, 0, 1, 1; 0, 1, 2, minus 1. The 2-by-4 matrix D equals 0, 0, 1, 0; 0, 0, 2, 0. The 3-by-3 matrix E = 3, 0, 1; 0, 2, 0; 0, 0, 0. The 2-by-2 matrix F = 0, 1; 1, 0.

  • A is in echelon form an its leading entries are all 1. However, condition (*) doesn't hold: for example column 2 contains a leading entry (1) and another nonzero entry (the 2 above it).

  • B is in echelon form, its leading entry is 1 and, in the column containing the leading entry, there are no other nonzero entries, so B is in reduced echelon form.

  • C is in reduced echelon form.

  • D and F are not even in echelon form.

  • E is in echelon form, but its leading entries are not 1, so it is not in reduced echelon form.

Reason for the definition

Consider the augmented matrix 1, 0, 1, 1, bar 5; 0, 1, 2, -1, bar, 13. This corresponds to the system of simultaneous equations: w + y + z = 5, x + 2 y minus z = 13.. These are two equations in four variables, so the best we can hope for is to use the equations to express some of the variables (dependent variables) in terms of the rest (free variables). Then, for any value of the free variables, we get a solution (where the dependent variables are determined by the free variables and the equations).

We get w = 5 minus y minus z and x = 13 minus 2 y + z, using w, x as dependent variables and y, z as free variables. Why did I pick w, x as the dependent variables? If we had tried to use the first equation to express y in terms of w and z, since y appears in the second equation, we would need to substitute y = 5 minus w minus z into the second equation to proceed. We didn't need to do that for w or x because w only appeared in equation 1 and x only appeared in equation 2. That is a consequence of condition (*): if we take our dependent variables to be the ones whose coefficients are the leading entries then they only appear in one of the equations.

Another example

Consider the augmented matrix 1, 2, 0, 1, bar, 1; 0, 0, 1, 8, bar, 2; 0, 0, 0, 0, bar, 0. This corresponds to the equations: w + 2 x + z = 1, y + 8 z = 2, 0 = 0. The third equation here is trivially satisfied, so we can ignore it. The dependent variables are w and y, as they have the leading entries as their coefficients. We get w = 1 minus 2 x minus z, y = 2 minus 8 z, with x, z as free variables.

Note that x also appears only in the first equation, so we could use x as a dependent variable, but that's just luck: we're only guaranteed that the variables whose coefficients are leading entries will appear in precisely one equation.

Consider the augmented matrix 1, 2, 0, 1, bar, 1; 0, 0, 1, 8, bar, 2; 0, 0, 0, 0, bar, 3 which differs from the previous one only in the very last entry. That corresponds to the system: w + 2 x + z = 1, y + 8 z = 2, 0 = 3. The third equation here doesn't hold, which means there is no solution: even if you can find w, x, y, z satisfying the first two equations, you'll never be able to solve the third.

Strategy

Our strategy (which we'll see implemented in some examples next time) is as follows:

  • given a system of equations, write down an augmented matrix;

  • perform row operations on the augmented matrix until the part left of the bar is in reduced echelon form;

  • read off from this whether solutions exist (they do unless one of the rows is 0, 0, dot dot dot, 0, bar, b for b not equal to zero);

  • if solutions exist, write down the solution by finding the dependent variables in terms of the free variables.