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