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

## Synopsis

• Usage:
R = reducedRowEchelonForm A
• Inputs:
• A, , or , a matrix over eiither a finite field or the rationals
• Outputs:
• R, , or , the same type as A, the reduced row echelon form of A

## 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)`