row echelon test

Not Reviewed
Equation / Last modified by AndrewBudd on 2017/02/17 19:05
`A = `
Rating
Copied from
ID
AndrewBudd.row echelon test
UUID
083d59ea-f384-11e6-9770-bc764e2038f2

The row echelon form of a matrix, obtained through Gaussian elimination (or row reduction), is when

  • All non-zero rows of the matrix are above any zero rows
  • The leading (first non-zero) entry of each column is strictly to the right of the leading entry of the row above it. Put another way, each leading entry has only zeroes in all entries below and to the right of it. These leading entries are also called pivots.
  • Some textbooks (and this calculator) also have that every leading entry is `1`, though this isn't always considered necessary.

(A matrix can also be in "column echelon form", but this is the same as saying its transpose is in row echelon form, so we don't talk about it much.)

For example, a 3x3 matrix in row echelon form would look something like:

     `A= ((1, A_(12), A_(13)), (0, 1, A_(23)), (0, 0, 1))`,

Or, if the leading coefficients aren't required to be one

     `A= ((A_(11), A_(12), A_(13)), (0, A_(22), A_(23)), (0, 0, A_(33)))`

Any matrix can be transformed into row echelon form, and this is done through a finite sequence of elementary row operations. There are three types of elementary row operations:

  • Row switching - Switching the entries in two of the rows.

     `((a, b, c), (d, e, f), (g, h, i)) -> ((d, e, f), (a, b, c), (g, h, i))`

  • Row multiplication - Each entry in a row multiplied by a non-zero constant. (Note: We can therefore also divide by a non-zero constant, since this is the same as multiplying by the reciprocal and zero is already off limits.)

     `((a, b, c), (d, e, f), (g, h, i)) -> ((ka, kb, kc), (d, e, f), (g, h, i));  k!=0`

  • Row addition - We can add a multiple of a row to any other row, entry by entry.

     `((a, b, c), (d, e, f), (g, h, i)) -> ((a, b, c), (d+ka, e+kb, f+kc), (g, h, i)); k!=0`

Performing these row operations preserves a lot of the properties of the matrix; for example, if the matrix represents a system of linear equations, the solutions to the equations are unchanged.  This also means that the row space, the span or set of all possible linear combinations of the row vectors, of the matrix is preserved. So the row space of a matrix `A` is the same as the row space of its row echelon form, and by extension the rank (or the dimension of the row space) of `A` - usually written `rank(A)` or `rk(A)` - is also preserved. The non-zero rows of a matrix's echelon form form a basis for the row space, so the number of non-zero rows is the dimension of the row space. (Note that the rank can also refer to the dimension of the column space, or the set of all possible linear combinations of the column vectors. But the dimension of the column space is always equal to the dimension of the row space, so it is more convenient for now to only talk about the latter.)

For example, consider the matrix
     `A = ((2, 6, 6), (2, 7, 8), (1, 4, 5))`

and its row echelon form
     `((1, 3, 3), (0, 1, 2), (0, 0, 0))`.

There are two non-zero rows, so the rank of the echelon matrix is `2`. It follows then that `rank(A)=2`, but it's much easier to see this by looking at the echelon form than looking at the original matrix. (Note that counting the number of non-zero rows is the same as counting the pivots.)

We can also use the row echelon form to find the null space and nullity of `A`. The null space (also called the kernel of `A` and written `ker(A)`) is the set of all solutions to the equation `A vec(x)=0`. Put another way, for an `m times n` matrix `A`,
     `text(Null) A = {x:x inRR^n and A vec(x)=0}`.

The nullity of `A`, usually written `text(nul)(A)`, is the dimension of the null space of `A`. This is very easy to see for matrices in row echelon form thanks to the rank-nullity theorem, which says that for an `m times n` matrix, then `rank(A)+text(nul)(A)=n`. Since the rank of `A` is as easy as counting the pivots of the echelon form of A and `n` is just the number of columns, we can easily find the nullity of `A` through simple subtraction.

Returning to our example from above, we saw that with the matrix `A` and echelon matrix
     `((1, 3, 3), (0, 1, 2), (0, 0, 0))`,

the rank was `2`.  Since `A` is a 3x3 matrix, we can also immediately say that `text(nul)(A)=n-rank(A)=3-2=1`. So we know the dimension of the null space, but actually finding the null space of `A` itself takes a little more work.

We want the solutions to `Avec(x)=0`, so we can write this as the augmented matrix
     ` ((2, 6, 6, :, 0), (2, 7, 8, :, 0), (1, 4, 5, :, 0))`.

As we said above, row reduction preserves the solutions, so we know we can consider instead the much simpler
     `((1, 3, 3, :, 0), (0, 1, 2, :, 0), (0, 0, 0, :, 0))`.

So we have
     `x_1+3x_2+3x_3=0`
     `x_2+2x_3=0`

Starting with the second equation, we get
     `x_2=-2x_3`,

and substituting back into the first equation gives
     `x_1+3*(-2x_3)+3x_3=0`
     `x_1-3x_3=0`
     `x_1=3x_3`.

So `x_3` is our free variable, and `x_1` and `x_2` are defined in terms of their relation to `x_3`. So
     `x_3 ((3), (-2), (1))`

is a solution to the equation `Avec(x)=0` for any chosen value of `x_3`. That is our null space. Since that `x_3` is a variable we're choosing and can be anything, we can switch it for a more generic `r` and write
     `text(Null) A = {((3r), (-2r), (r)): r in RR}`. 

Since this vector `(3r, -2r, r)^T` is a basis for the null space, we can see again that the dimension of the null space is `1`, as we expected.

Reference

Strang, Gilbert. Linear Algebra and Its Applications. 3rd ed. San Diego: Harcourt, Brace, Jovanovich, 1988. Print.