## `linalg::gaussElim` -- Gaussian elimination

#### Introduction

`linalg::gaussElim``(A)` performs Gaussian elimination on the matrix A to reduce A to an upper row echelon form.

#### Call(s)

`linalg::gaussElim(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 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::gaussJordan`, `lllint`

#### Details

- A row echelon form of `A` returned by `linalg::gaussElim` is not unique. See `linalg::gaussJordan` for computing the reduced row echelon form.
- 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`, ordinary Gaussian elimination is used. Otherwise, `linalg::gaussElim` applies fraction-free Gaussian elimination to `A`.
- Refer to the help page of `Dom::Matrix` for details about the computation strategy of `linalg::gaussElim`.

#### Option: All

- Returns a list [T, rank(A), det(A), {j1,...,jr}] where T is a 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).

- `linalg::gaussElim` serves as an interface function for the method `"gaussElim"` of the matrix domain of `A`, i.e., one may call `A::dom::gaussElim(A)` directly instead of `linalg::gaussElim``(A, All)`

#### Example 1

We apply Gaussian elimination to the following matrix:

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

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

which reduces `A` to the following row echelon form:

    >> linalg::gaussElim(A)

                                +-              -+
                                |  1, 2,  3,  4  |
                                |                |
                                |  0, 2,  4,  4  |
                                |                |
                                |  0, 0, -1, -1  |
                                +-              -+

#### Example 2

We apply Gaussian elimination to the matrix:

    >> B := Dom::Matrix(Dom::Integer)(
         [[1, 2, -1], [1, 0, 1], [2, -1, 4]]
       )

                                  +-           -+
                                  |  1,  2, -1  |
                                  |             |
                                  |  1,  0,  1  |
                                  |             |
                                  |  2, -1,  4  |
                                  +-           -+

and get the following result:

    >> linalg::gaussElim(B, All)

                      -- +-           -+                   --
                      |  |  1,  2, -1  |                    |
                      |  |             |                    |
                      |  |  0, -2,  2  |, 3, -2, {1, 2, 3}  |
                      |  |             |                    |
                      |  |  0,  0, -2  |                    |
                      -- +-           -+                   --

We see that rank(B)=3 and det(B)=-2.

#### Background

- Let T be an m x n matrix. Then T is a matrix in an upper 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.
  3. For each i in {r+1,...,m}: T[i,j]=0 for each j in {1,...,n}.

  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