Mo logo [home] [lexicon] [problems] [tests] [courses] [auxiliaries] [notes] [staff] german flag
Mathematics-Online lexicon:

Gauss-Jordan algorithm

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z overview
The Gauss-Jordan algorithm can be used to solve a linear system

$\displaystyle Ax = b $

with a non-singular $ n\times n$ coefficient matrix $ A$. With equivalence transformations it successively eliminates the unknowns

$\displaystyle x_\ell \,, \quad \ell=1, \ldots ,n\,, $

until the coefficient matrix becomes the unit matrix and the right-hand side contains the solution $ x$.

To implement the algorithm we combine the coefficient matrix and the right-hand side to an $ n \times (n+1)$ matrix $ W=(A,b)$. Before the $ \ell$-th elimination step this matrix has the form

$\displaystyle \left( \begin{array}{ccc\vert ccc} 1 & & 0 & w_{1,\ell} & \cdots&... ...vdots & & \vdots \\ & & & w_{n,\ell} & \cdots& w_{n,n+1} \end{array} \right) $

with modified entries $ w_{i,j}$.

The elimination of $ x_\ell$ proceeds in three steps:

  1. Determination of a maximum $ \vert w_{i,\ell}\vert$ of the absolute values of $ w_{\ell,\ell} , \ldots , w_{n,\ell}$ and permutation of rows $ \ell$ and $ i$,
  2. Division of row $ \ell$ by $ w_{\ell,\ell}$,
  3. Subtraction of the $ w_{j,\ell}$-fold multiple of row $ \ell$ from rows $ j$ for $ j \neq \ell$:

    $\displaystyle w_{j,k} \longleftarrow w_{j,k} -w_{j,\ell} \; w_{\ell,k}\,, \quad k=\ell,\ldots,n+1 \,. $

The third step generates zeros in positions $ (j,\ell)\,,\; j\neq \ell$, i.e., the dimension of the unit matrix in the upper left block increases by one. Consequently, after $ n$ elimination steps, column $ n+1$ of $ W$ contains the solution $ x$.

(Authors: Höllig/Pfeil/Walter/Wohlmuth)
[Examples] [Links]
  automatically generated 3/ 8/2007