Editing Gaussian elimination (section)

== Applications ==
Historically, the first application of the row reduction method is for solving systems of linear equations. Below are some other important applications of the algorithm.

=== Computing determinants ===
To explain how Gaussian elimination allows the computation of the determinant of a square matrix, we have to recall how the elementary row operations change the determinant:
* Swapping two rows multiplies the determinant by −1
* Multiplying a row by a nonzero scalar multiplies the determinant by the same scalar
* Adding to one row a scalar multiple of another does not change the determinant.

If Gaussian elimination applied to a square matrix {{mvar|A}} produces a row echelon matrix {{mvar|B}}, let {{mvar|d}} be the product of the scalars by which the determinant has been multiplied, using the above rules. Then the determinant of {{mvar|A}} is the quotient by {{mvar|d}} of the product of the elements of the diagonal of {{mvar|B}}:
<math display="block">\det(A) = \frac{\prod\operatorname{diag}(B)}{d}.</math>

Computationally, for an {{math|''n'' × ''n''}} matrix, this method needs only {{math|[[O notation|O(''n''<sup>3</sup>)]]}} arithmetic operations, while using [[Leibniz formula for determinants]] requires <math>(n\, n!)</math> operations <small>(number of summands in the formula times the number of multiplications in each summand)</small>, and
recursive [[Laplace expansion]] requires {{math|O(''n'' 2<sup>''n''</sup>)}} operations if the sub-determinants are memorized for being computed only once <small>(number of operations in a linear combination times the number of sub-determinants to compute, which are determined by their columns)</small>. Even on the fastest computers, these two methods are impractical or almost impracticable for {{math|''n''}} above 20.

=== Finding the inverse of a matrix ===
{{See also|Invertible matrix}}
A variant of Gaussian elimination called '''Gauss–Jordan elimination''' can be used for finding the inverse of a matrix, if it exists. If {{math|''A''}} is an {{math|''n'' × ''n''}} square matrix, then one can use row reduction to compute its [[invertible matrix|inverse matrix]], if it exists. First, the {{math|''n'' × ''n''}} [[identity matrix]] is augmented to the right of {{math|''A''}}, forming an {{math|''n'' × 2''n''}} [[block matrix]] {{math|[''A'' {{!}} ''I'']}}. Now through application of elementary row operations, find the reduced echelon form of this {{math|''n'' × 2''n''}} matrix. The matrix {{math|''A''}} is invertible if and only if the left block can be reduced to the identity matrix {{math|''I''}}; in this case the right block of the final matrix is {{math|''A''<sup>−1</sup>}}. If the algorithm is unable to reduce the left block to {{math|''I''}}, then {{math|''A''}} is not invertible.

For example, consider the following matrix:
<math display="block">A =
 \begin{bmatrix}
  2 & -1 &  0 \\
 -1 &  2 & -1 \\
  0 & -1 &  2
 \end{bmatrix}.
</math>

To find the inverse of this matrix, one takes the following matrix augmented by the identity and row-reduces it as a 3&nbsp;×&nbsp;6 matrix:
<math display="block">[ A | I ] = 
 \left[\begin{array}{ccc|ccc}
   2 & -1 &  0 & 1 & 0 & 0 \\
  -1 &  2 & -1 & 0 & 1 & 0 \\
   0 & -1 &  2 & 0 & 0 & 1
 \end{array}\right].
</math>

By performing row operations, one can check that the reduced row echelon form of this augmented matrix is
<math display="block">[ I | B ] = 
 \left[\begin{array}{rrr|rrr}
  1 & 0 & 0 & \frac34 & \frac12 & \frac14 \\
  0 & 1 & 0 & \frac12 &      1  & \frac12 \\
  0 & 0 & 1 & \frac14 & \frac12 & \frac34
 \end{array}\right].
</math>

One can think of each row operation as the left product by an [[elementary matrix]]. Denoting by {{math|''B''}} the product of these elementary matrices, we showed, on the left, that {{math|1=''BA'' = ''I''}}, and therefore, {{math|1=''B'' = ''A''<sup>−1</sup>}}. On the right, we kept a record of {{math|1=''BI'' = ''B''}}, which we know is the inverse desired. This procedure for finding the inverse works for square matrices of any size.

=== Computing ranks and bases ===
The Gaussian elimination algorithm can be applied to any {{math|''m'' × ''n''}} matrix {{mvar|A}}. In this way, for example, some 6&nbsp;×&nbsp;9 matrices can be transformed to a matrix that has a row echelon form like
<math display="block"> T=
\begin{bmatrix}
a & * & * & *& * & * & * & * & * \\
0 & 0 & b & * & * & * & * & * & * \\
0 & 0 & 0 & c & * & * & * & * & * \\
0 & 0 & 0 & 0 & 0 & 0 & d & * & * \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & e \\
0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0
\end{bmatrix},
</math>
where the stars are arbitrary entries, and {{math|''a'', ''b'', ''c'', ''d'', ''e''}} are nonzero entries. This echelon matrix {{mvar|T}} contains a wealth of information about {{mvar|A}}: the [[rank of a matrix|rank]] of {{mvar|A}} is 5, since there are 5 nonzero rows in {{mvar|T}}; the [[vector space]] spanned by the columns of {{mvar|A}} has a basis consisting of its columns 1, 3, 4, 7 and 9 (the columns with {{math|''a'', ''b'', ''c'', ''d'', ''e''}} in {{mvar|T}}), and the stars show how the other columns of {{mvar|A}} can be written as linear combinations of the basis columns.

All of this applies also to the reduced row echelon form, which is a particular row echelon format.