next | previous | forward | backward | up | top | index | toc | Macaulay2 web site
Macaulay2Doc :: reducedRowEchelonForm

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 https://en.wikipedia.org/wiki/Row_echelon_form (missing documentation) 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 :