Main Content

rref

Reduced row echelon form (Gauss-Jordan elimination)

Description

R = rref(A) returns the reduced row echelon form of A using Gauss-Jordan elimination with partial pivoting.

example

R = rref(A,tol) specifies a pivot tolerance that the algorithm uses to determine negligible columns.

[R,p] = rref(A) also returns the nonzero pivots p.

example

Examples

collapse all

Create a matrix and calculate the reduced row echelon form. In this form, the matrix has leading 1s in the pivot position of each column.

A = magic(3)
A = 3×3

     8     1     6
     3     5     7
     4     9     2

RA = rref(A)
RA = 3×3

     1     0     0
     0     1     0
     0     0     1

The 3-by-3 magic square matrix is full rank, so the reduced row echelon form is an identity matrix.

Now, calculate the reduced row echelon form of the 4-by-4 magic square matrix. Specify two outputs to return the nonzero pivot columns. Since this matrix is rank deficient, the result is not an identity matrix.

B = magic(4)
B = 4×4

    16     2     3    13
     5    11    10     8
     9     7     6    12
     4    14    15     1

[RB,p] = rref(B)
RB = 4×4

     1     0     0     1
     0     1     0     3
     0     0     1    -3
     0     0     0     0

p = 1×3

     1     2     3

Use Gauss-Jordan elimination on augmented matrices to solve a linear system and calculate the matrix inverse. These techniques are mainly of academic interest, since there are more efficient and numerically stable ways to calculate these values.

Create a 3-by-3 magic square matrix. Add an additional column to the end of the matrix. This augmented matrix represents a linear system Ax=b, with the extra column corresponding to b.

A = magic(3);
A(:,4) = [1; 1; 1]
A = 3×4

     8     1     6     1
     3     5     7     1
     4     9     2     1

Calculate the reduced row echelon form of A. Index into R to extract the entries in the extra (augmented) column, which contains the solution to the linear system.

R = rref(A)
R = 3×4

    1.0000         0         0    0.0667
         0    1.0000         0    0.0667
         0         0    1.0000    0.0667

x = R(:,end)
x = 3×1

    0.0667
    0.0667
    0.0667

A more efficient way to solve this linear system is with the backslash operator, x = A\b.

Create a similar magic square matrix, but this time append an identity matrix of the same size to the end columns.

A = [magic(3) eye(3)]
A = 3×6

     8     1     6     1     0     0
     3     5     7     0     1     0
     4     9     2     0     0     1

Calculate the reduced row echelon form of A. In this form the extra columns contain the inverse matrix for the 3-by-3 magic square matrix.

R = rref(A)
R = 3×6

    1.0000         0         0    0.1472   -0.1444    0.0639
         0    1.0000         0   -0.0611    0.0222    0.1056
         0         0    1.0000   -0.0194    0.1889   -0.1028

inv_A = R(:,4:end)
inv_A = 3×3

    0.1472   -0.1444    0.0639
   -0.0611    0.0222    0.1056
   -0.0194    0.1889   -0.1028

A more efficient way to calculate the inverse matrix is with inv(A).

Consider a linear system of equations with four equations and three unknowns.

x1+x2+5x3=62x1+x2+8x3=8x1+2x2+7x3=10-x1+x2-x3=2.

Create an augmented matrix that represents the system of equations.

A = [1  1  5;
     2  1  8;
     1  2  7;
    -1  1 -1];
b = [6 8 10 2]';
M = [A b];

Use rref to express the system in reduced row echelon form.

R = rref(M)
R = 4×4

     1     0     3     2
     0     1     2     4
     0     0     0     0
     0     0     0     0

The first two rows of R contain equations that express x1 and x2 in terms of x3. The second two rows imply that there exists at least one solution that fits the right-hand side vector (otherwise one of the equations would read 1=0). The third column does not contain a pivot, so x3 is an independent variable. Therefore, there are infinitely many solutions for x1 and x2, and x3 can be chosen freely.

x1=2-3x3x2=4-2x3.

For example, if x3=1, then x1=-1 and x2=2.

From a numerical standpoint, a more efficient way to solve this system of equations is with x0 = A\b, which (for a rectangular matrix A) calculates the least-squares solution. In that case, you can check the accuracy of the solution with norm(A*x0-b)/norm(b) and the uniqueness of the solution by checking if rank(A) is equal to the number of unknowns. If more than one solution exists, then they all have the form of x=x0+nt, where n is the null space null(A) and t can be chosen freely.

Input Arguments

collapse all

Input matrix.

Data Types: single | double
Complex Number Support: Yes

Pivot tolerance, specified as a scalar. If the largest element (by absolute value) in a pivot column is below the tolerance, then the column is zeroed out. This prevents division and multiplication with nonzero pivot elements smaller than the tolerance.

Data Types: single | double

Output Arguments

collapse all

Reduced row echelon form of A, returned as a matrix.

Nonzero pivot columns, returned as a vector. Each element in p is a column index of A. You can use p to estimate several quantities:

  • length(p) is an estimate of the rank of A.

  • x(p) contains the pivot variables in a linear system Ax = b.

  • A(:,p) is a basis for the range of A.

  • R(1:r,p) is the r-by-r identity matrix, where r = length(p).

Limitations

  • rank, orth, and null are typically faster and more accurate for computing the rank and basis vectors of a matrix.

  • mldivide is recommended to solve linear systems.

More About

collapse all

Algorithms

rref implements Gauss-Jordan elimination with partial pivoting. A default tolerance of max(size(A))*eps*norm(A,inf) tests for negligible column elements that are zeroed-out to reduce roundoff error.

Extended Capabilities

expand all

Version History

Introduced before R2006a

See Also

| | |