Definition:Gaussian Elimination

From ProofWiki
Jump to navigation Jump to search

Definition

Let $\mathbf A$ be a matrix over a field $K$.

Let $\mathbf E$ be a reduced echelon matrix which is row equivalent to $\mathbf A$.


The Gaussian elimination method is a technique for converting $\mathbf A$ into $\mathbf E$ by means of a sequence of elementary row operations.


Procedure

Let $\mathbf A$ be a matrix over a field $F$.

Let $\mathbf E$ be a reduced echelon matrix which is row equivalent to $\mathbf A$.


Let the first column of $\mathbf A$ containing a non-zero element be column $j$.

Let a non-zero element in row $i$ be distinguished.

This element $a_{i j} \ne 0$ is called the pivot element.


Perform the elementary row operation:

$(1): \quad r_1 \leftrightarrow r_i$

This moves the pivot element to $a_{1 j}$.


Then perform the elementary row operation:

$(2): \quad r_1 \to \dfrac {r_1} {a_{1 j} }$

that is, divide all the elements of row $1$ by the pivot element.

This gives a matrix with $1$ in the $\tuple {1, j}$ position:

$\begin {bmatrix} 0 & \cdots & 0 & 1 & b_{1, j + 1} & \cdots & b_{1 n} \\ 0 & \cdots & 0 & b_{2 j} & b_{2, j + 1} & \cdots & b_{2 n} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & b_{m j} & b_{m, j + 1} & \cdots & b_{m n} \\ \end {bmatrix}$

Now the elementary row operations $r_k \to r_k - b_{k j} r_1, k \in \set {2, 3, \ldots, m}$ gives the matrix:

$\begin{bmatrix} 0 & \cdots & 0 & 1 & c_{1, j + 1} & \cdots & c_{1 n} \\ 0 & \cdots & 0 & 0 & c_{2, j + 1} & \cdots & c_{2 n} \\ \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ 0 & \cdots & 0 & 0 & c_{m, j + 1} & \cdots & c_{m n} \\ \end{bmatrix}$

If some zero rows have appeared, do some further elementary row operations, that is row interchanges, to put them at the bottom.


We now repeat the process with the remaining however-many-there-are rows:

$\begin{bmatrix} \cdots & 0 & 1 & d_{1, j + 1} & \cdots & d_{1, k - 1} & d_{1 k} & d_{1, k + 1} & \cdots & d_{1 n} \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 1 & d_{2, k + 1} & \cdots & d_{2 n} \\ \cdots & 0 & 0 & 0 & \cdots & 0 & d_{3 k} & d_{3, k + 1} & \cdots & d_{3 n} \\ \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & 0 & 0 & 0 & \cdots & 0 & d_{n k} & d_{m, k + 1} & \cdots & d_{m n} \\ \end{bmatrix}$


Then we can get the reduced echelon form by:

$r_i \to r_i - d_{i k} r_2, i \in \set {1, 3, 4, \ldots, m}$

as follows:

$\begin{bmatrix} \cdots & 0 & 1 & {e_{1, j + 1 } } & \cdots & {e_{1, k - 1} } & 0 & {e_{1, k + 1} } & \cdots & {e_{1 n} } \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 1 & {e_{2, k + 1} } & \cdots & {e_{2 n} } \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & {e_{3, k + 1} } & \cdots & {e_{3 n} } \\ \ddots & \vdots & \vdots & \vdots & \ddots & \vdots & \vdots & \vdots & \ddots & \vdots \\ \cdots & 0 & 0 & 0 & \cdots & 0 & 0 & {e_{m, k + 1} } & \cdots & {e_{m n} } \\ \end{bmatrix}$

Thus we progress, until the entire matrix is in reduced echelon form.


Also defined as

Some sources do not insist that $\mathbf E$ be a reduced echelon matrix at the end of the Gaussian elimination process, but merely an echelon matrix.


Also known as

Some sources refer to the technique of Gaussian elimination as Gauss elimination.

Gaussian elimination is sometimes seen referred to as pivotal condensation.


Examples

Arbitrary Matrix $1$

Let $\mathbf A$ denote the matrix:

$\mathbf A = \begin {bmatrix} 0 & 0 & 5 & 35 & -24 & 1 \\ 0 & 2 & 1 & -1 & 1 & 0 \\ 0 & 3 & 2 & 2 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 5 & 3 & 1 & 0 & 1 \end {bmatrix}$

The reduced echelon form of $\mathbf A$ is:

$\mathbf E = \begin {bmatrix} 0 & 1 & 0 & -4 & 0 & 26 \\ 0 & 0 & 1 & 7 & 0 & -43 \\ 0 & 0 & 0 & 0 & 1 & -9 \\ 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 \end {bmatrix}$


Arbitrary Matrix $2$

Let $\mathbf A$ denote the matrix:

$\mathbf A = \begin {bmatrix} 1 & -1 & 2 & 1 \\ 2 & 1 & -1 & 1 \\ 1 & -2 & 1 & 1 \\ \end {bmatrix}$

The reduced echelon form of $\mathbf A$ is:

$\mathbf E = \begin {bmatrix} 1 & 0 & 0 & \dfrac 5 8 \\ 0 & 1 & 0 & -\dfrac 1 8 \\ 0 & 0 & 1 & \dfrac 1 8 \\ \end {bmatrix}$


Arbitrary Matrix $3$

Let $\mathbf A$ denote the matrix:

$\mathbf A = \begin {bmatrix} 1 & 1 & -1 \\ 1 & -1 & 2 \\ 2 & 0 & 2 \\ 2 & 1 & -1 \\ \end {bmatrix}$

The reduced echelon form of $\mathbf A$ is:

$\mathbf E = \begin {bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ 0 & 0 & 0 \\ \end {bmatrix}$


Also see

  • Results about Gaussian elimination can be found here.


Source of Name

This entry was named for Carl Friedrich Gauss.


Sources

Retrieved from "https://proofwiki.org/w/index.php?title=Definition:Gaussian_Elimination&oldid=732507"