Macaulay2 » Documentation
Packages » Macaulay2Doc :: reducedRowEchelonForm
next | previous | forward | backward | up | index | toc

reducedRowEchelonForm -- compute the reduced row echelon form of a matrix or mutable matrix over a field

Synopsis

Description

A matrix over a field is in reduced row echelon form if (1) all rows consisting only of zeros are at the bottom, (2) the leading coefficient (called the pivot) of a nonzero row is always strictly to the right of the leading coefficient of the row above it, and (3) the leading coefficient of each nonzero row is 1. See Row echelon form for more discussion.

Given a matrix A (over a field), there is a unique matrix R such that (1) the row spans of A and R are the same, and (2) R is in reduced row echelon form.

If the matrix A is over either a finite field, or the rationals, then this returns the unique reduced row echelon form for the matrix, which is unique.

i1 : R0 = matrix(QQ, {{1,0,3,0,5},{0,1,-2,0,2},{0,0,0,1,7}})

o1 = | 1 0 3  0 5 |
     | 0 1 -2 0 2 |
     | 0 0 0  1 7 |

              3       5
o1 : Matrix QQ  <-- QQ
 
i2 : B = matrix(QQ, {{1,2,3},{0,3,-1},{1,2,0}})

o2 = | 1 2 3  |
     | 0 3 -1 |
     | 1 2 0  |

              3       3
o2 : Matrix QQ  <-- QQ
 
i3 : A = B * R0

o3 = | 1 2 -1 3  30 |
     | 0 3 -6 -1 -1 |
     | 1 2 -1 0  9  |

              3       5
o3 : Matrix QQ  <-- QQ
 
i4 : R = reducedRowEchelonForm A

o4 = | 1 0 3  0 5 |
     | 0 1 -2 0 2 |
     | 0 0 0  1 7 |

              3       5
o4 : Matrix QQ  <-- QQ
 
i5 : assert(R == R0)
 
i6 : LUdecomposition A

o6 = ({0, 1, 2}, | 1 0 0 |, | -1/9 -2/9 1/9 -1/3 -10/3 |)
                 | 0 1 0 |  | 0    -1/3 2/3 1/9  1/9   |
                 | 1 0 1 |  | 0    0    0   1    7     |

o6 : Sequence
 
i7 : A5 = sub(A, ZZ/5)

o7 = | 1 2  -1 -2 0  |
     | 0 -2 -1 -1 -1 |
     | 1 2  -1 0  -1 |

             ZZ 3      ZZ 5
o7 : Matrix (--)  <-- (--)
              5         5
 
i8 : reducedRowEchelonForm A5

o8 = | 1 0 -2 0 0 |
     | 0 1 -2 0 2 |
     | 0 0 0  1 2 |

             ZZ 3      ZZ 5
o8 : Matrix (--)  <-- (--)
              5         5
 
i9 : rank A5

o9 = 3

This function is useful while learning the concepts and algorithms of linear algebra. In practice though, one tends to use LU decompositions rather than reduced row echelon forms.

In fact, this function doesn't work over the reals or complexes (due to often poor numerical stability), as an LU decomposition is better for solving systems over the real numbers. If numerical stability is an issue, using a singular value decomposition (SVD) is also a good idea.

i10 : AR = sub(A, RR)

o10 = | 1 2 -1 3  30 |
      | 0 3 -6 -1 -1 |
      | 1 2 -1 0  9  |

                 3         5
o10 : Matrix RR    <-- RR
               53        53
 
i11 : LUdecomposition AR

o11 = ({0, 1, 2}, | 1 0 0 |, | 1 2 -1 3  30  |)
                  | 0 1 0 |  | 0 3 -6 -1 -1  |
                  | 1 0 1 |  | 0 0 0  -3 -21 |

o11 : Sequence
 
i12 : SVD AR

o12 = ({31.6062}, | -.956949 .0376118 -.287807 |, | -.0394384 -.0769597
       {6.95666}  | .0201977 -.980536 -.195297 |  | -.0222938 -.467435 
       {1.28466}  | -.289551 -.192702 .937564  |  | .505782   .555496  
                                                  | .0471081  .572207  
                                                  | -.860182  .373609  
      -----------------------------------------------------------------------
      .0356042 -.0914707 -.991407   |)
      .86799   .157169   .0538433   |
      .406354  -.520081  -.00066372 |
      .172926  .792242   -.113177   |
      .224276  -.262297  .037471    |

o12 : Sequence
 
i13 : AC = sub(A, CC)

o13 = | 1 2 -1 3  30 |
      | 0 3 -6 -1 -1 |
      | 1 2 -1 0  9  |

                 3         5
o13 : Matrix CC    <-- CC
               53        53
 
i14 : LUdecomposition AC

o14 = ({0, 1, 2}, | 1 0 0 |, | 1 2 -1 3  30  |)
                  | 0 1 0 |  | 0 3 -6 -1 -1  |
                  | 1 0 1 |  | 0 0 0  -3 -21 |

o14 : Sequence
 
i15 : SVD AC

o15 = ({31.6062}, | -.956949 .0376118 -.287807 |, | -.0394384 -.0769597
       {6.95666}  | .0201977 -.980536 -.195297 |  | -.0222938 -.467435 
       {1.28466}  | -.289551 -.192702 .937564  |  | .505782   .555496  
                                                  | .0471081  .572207  
                                                  | -.860182  .373609  
      -----------------------------------------------------------------------
      .0356042 -.0914707 -.991407   |)
      .86799   .157169   .0538433   |
      .406354  -.520081  -.00066372 |
      .172926  .792242   -.113177   |
      .224276  -.262297  .037471    |

o15 : Sequence

This function also works over finite fields.

i16 : A9 = sub(A, GF 9)

o16 = | 1 -1 -1 0  0  |
      | 0 0  0  -1 -1 |
      | 1 -1 -1 0  0  |

                   3           5
o16 : Matrix (GF 9)  <-- (GF 9)
 
i17 : R9 = reducedRowEchelonForm A9

o17 = | 1 -1 -1 0 0 |
      | 0 0  0  1 1 |
      | 0 0  0  0 0 |

                   3           5
o17 : Matrix (GF 9)  <-- (GF 9)

It is not yet implemented over fraction fields and extension fields. Use LUdecomposition instead.

i18 : S = frac(QQ[x])

o18 = S

o18 : FractionField
 
i19 : R = matrix(S, {{1,0,x,0,x^2+1},{0,1,-1/x,0,2*x},{0,0,0,1,7*x}})

o19 = | 1 0 x      0 x2+1 |
      | 0 1 (-1)/x 0 2x   |
      | 0 0 0      1 7x   |

              3      5
o19 : Matrix S  <-- S
 
i20 : B = matrix(S, {{1,2*x,3},{0,3,-x},{1,2*x^2,0}})

o20 = | 1 2x  3  |
      | 0 3   -x |
      | 1 2x2 0  |

              3      3
o20 : Matrix S  <-- S
 
i21 : A = B * R

o21 = | 1 2x  x-2    3  5x2+21x+1 |
      | 0 3   (-3)/x -x -7x2+6x   |
      | 1 2x2 -x     0  4x3+x2+1  |

              3      5
o21 : Matrix S  <-- S
 
i22 : LUdecomposition A

o22 = ({0, 1, 2}, | 1 0          0 |, | 1 2x x-2    3            
                  | 0 1          0 |  | 0 3  (-3)/x -x           
                  | 1 (2x2-2x)/3 1 |  | 0 0  0      (2x3-2x2-9)/3
      -----------------------------------------------------------------------
      5x2+21x+1         |)
      -7x2+6x           |
      (14x4-14x3-63x)/3 |

o22 : Sequence

Even though it is not implemented currently as a canned routine, we can put A into reduced row echelon form using elementary row operations. Recall that rows and columns in Macaulay2 are indexed starting with 0.

i23 : M = mutableMatrix A

o23 = | 1 2x  x-2    3  5x2+21x+1 |
      | 0 3   (-3)/x -x -7x2+6x   |
      | 1 2x2 -x     0  4x3+x2+1  |

o23 : MutableMatrix
 
i24 : rowAdd(M, 2, -1, 0)

o24 = | 1 2x     x-2    3  5x2+21x+1   |
      | 0 3      (-3)/x -x -7x2+6x     |
      | 0 2x2-2x -2x+2  -3 4x3-4x2-21x |

o24 : MutableMatrix
 
i25 : rowMult(M, 1, 1/M_(1,1))

o25 = | 1 2x     x-2    3      5x2+21x+1   |
      | 0 1      (-1)/x (-x)/3 (-7x2+6x)/3 |
      | 0 2x2-2x -2x+2  -3     4x3-4x2-21x |

o25 : MutableMatrix
 
i26 : rowAdd(M, 2, -M_(2,1), 1)

o26 = | 1 2x x-2    3             5x2+21x+1         |
      | 0 1  (-1)/x (-x)/3        (-7x2+6x)/3       |
      | 0 0  0      (2x3-2x2-9)/3 (14x4-14x3-63x)/3 |

o26 : MutableMatrix
 
i27 : rowMult(M, 2, 1/M_(2,3))

o27 = | 1 2x x-2    3      5x2+21x+1   |
      | 0 1  (-1)/x (-x)/3 (-7x2+6x)/3 |
      | 0 0  0      1      7x          |

o27 : MutableMatrix

At this point the matrix is in row echelon form. We clear out the entries above the pivots to place it into reduced row echelon form.

i28 : rowAdd(M, 0, -M_(0,1), 1)

o28 = | 1 0 x      (2x2+9)/3 (14x3+3x2+63x+3)/3 |
      | 0 1 (-1)/x (-x)/3    (-7x2+6x)/3        |
      | 0 0 0      1         7x                 |

o28 : MutableMatrix
 
i29 : rowAdd(M, 0, -M_(0,3), 2)

o29 = | 1 0 x      0      x2+1        |
      | 0 1 (-1)/x (-x)/3 (-7x2+6x)/3 |
      | 0 0 0      1      7x          |

o29 : MutableMatrix
 
i30 : rowAdd(M, 1, -M_(1,3), 2)

o30 = | 1 0 x      0 x2+1 |
      | 0 1 (-1)/x 0 2x   |
      | 0 0 0      1 7x   |

o30 : MutableMatrix
 
i31 : assert(R == matrix M)

See also

Ways to use reducedRowEchelonForm :

For the programmer

The object reducedRowEchelonForm is a method function.