## `linalg::gaussJordan` -- Gauss-Jordan elimination

#### Introduction

`linalg::gaussJordan``(A)` performs Gauss-Jordan elimination on the matrix A, i.e., it returns the reduced row echelon form of A.

#### Call(s)

`linalg::gaussJordan(A <, All>)`

#### Parameters

`A` | - | a matrix of a domain of category `Cat::Matrix`

#### Options

`All` | - | additionally returns the rank and the determinant of `A` (if `A` is a square) as well as the characteristic column indices of the matrix in reduced row echelon form.

#### Returns

a matrix of the same domain type as `A`, or the list `[T, rank(A), det(A), j1,...,jr]` when the option All is given (see below).

#### Related Functions

`linalg::gaussElim`

#### Details

- The component ring R of `A` must be an integral domain, i.e., a domain of category `Cat::IntegralDomain`.
- If R is a field, i.e., a domain of category `Cat::Field`, then the leading entries of the matrix T in reduced row echelon form are equal to one.

  If R is a ring providing the method `"gcd"`, then the components of each row of T do not have a non-trivial common divisor.

- If the component ring of `A` is a field, then the reduced row echelon form is unique.

#### Option: All

- Returns a list [T, rank(A), det(A), {j1,...,jr}] where T is the reduced row echelon form of `A` and {j1,...,jr} is the set of characteristic column indices of `T`.

  If `A` is not square, then the value `FAIL` is given instead of det(A).

#### Example 1

We apply Gauss-Jordan elimination to the following matrix:

    >> A := Dom::Matrix(Dom::Rational)(
         [[1, 2, 3, 4], [-5, 0, 3, 0], [3, 5, 6, 9]]
       )

                                 +-             -+
                                 |   1, 2, 3, 4  |
                                 |               |
                                 |  -5, 0, 3, 0  |
                                 |               |
                                 |   3, 5, 6, 9  |
                                 +-             -+

    >> linalg::gaussJordan(A, All)

                   -- +-              -+                     --
                   |  |  1, 0, 0, 1/2  |                      |
                   |  |                |                      |
                   |  |  0, 1, 0, 1/2  |, 3, FAIL, {1, 2, 3}  |
                   |  |                |                      |
                   |  |  0, 0, 1, 5/6  |                      |
                   -- +-              -+                     --

We see that rank(B)=3. Because the determinant of a matrix is only defined for square matrices, the third element of the returned list is the value `FAIL`.

#### Example 2

If we consider the matrix from example 1 as an integer matrix and apply the Gauss-Jordan elimination we get the following matrix:

    >> B := Dom::Matrix(Dom::Integer)(
         [[1, 2, 3, 4], [-5, 0, 3, 0], [3, 5, 6, 9]]
       ):
       linalg::gaussJordan(B)

                                +-               -+
                                |  2,  0,  0,  1  |
                                |                 |
                                |  0, -2,  0, -1  |
                                |                 |
                                |  0,  0, -6, -5  |
                                +-               -+

#### Background

- Let T be an m x n matrix. Then T is a matrix in reduced row echelon form, if r in {0,1,...,n} and indices j1,j2,...,jr in {1,...,n} exist with:
  1. j1<j2<...<jr.
  2. For each i in {1,...,r}: T[i,1]=T[i,2]=...=T[i,ji-1]=0. In addition, if A is defined over a field: T[i,ji] = 1.
  3. For each i in {r+1,...,m}: T[i,j]=0 for each j in {1,...,n}.
  4. For each i in {1,...,r}: T[k,ji]=0 for each k in {1,...,i-1}.

  The indices j1,j2,...,jr are the characteristic column indices of the matrix T.

Do you have questions or comments?
Copyright © SciFace Software GmbH & Co. KG 2000