Gaussian elimination
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations.
≈ 12 min read
Names in other languages
No names in other languages are held for this entry yet.
Article bodies are English and are not machine-translated. A name in another language is not a translation of the article.
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix.
The method is named after Carl Friedrich Gauss (1777–1855). To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible.
There are three types of elementary row operations: * swapping two rows, * multiplying a row by a nonzero number, and * adding a multiple of one row to another row. Using these operations, a matrix can always be transformed into reduced row echelon form: each nonzero row is above every zero row, each nonzero row has leftmost nonzero entry equal to 1, the columns containing these leading 1s have all other entries 0, and the leading 1 in each nonzero row is to the right of the leading 1 in the previous row.
This final form is unique; in other words, it is independent of the sequence of row operations used.…
In mathematics, Gaussian elimination, also known as row reduction, is an algorithm for solving systems of linear equations. It consists of a sequence of row-wise operations performed on the corresponding matrix of coefficients. This method can also be used to compute the rank of a matrix, the determinant of a square matrix, and the inverse of an invertible matrix.
The method is named after Carl Friedrich Gauss (1777–1855). To perform row reduction on a matrix, one uses a sequence of elementary row operations to modify the matrix until the lower left-hand corner of the matrix is filled with zeros, as much as possible.
There are three types of elementary row operations: swapping two rows, multiplying a row by a nonzero number, and adding a multiple of one row to another row. Using these operations, a matrix can always be transformed into reduced row echelon form: each nonzero row is above every zero row, each nonzero row has leftmost nonzero entry equal to 1, the columns containing these leading 1s have all other entries 0, and the leading 1 in each nonzero row is to the right of the leading 1 in the previous row.
This final form is unique; in other words, it is independent of the sequence of row operations used. For example, in the following sequence of row operations (where two elementary operations on different rows are done at the first and third steps), the third and fourth matrices are the ones in row echelon form, and the final matrix is the unique reduced row echelon form. \begin{bmatrix} 1 & 3 & 1 & 9 \\ 1 & 1 & -1 & 1 \\ 3 & 11 & 5 & 35 \end{bmatrix}\to \begin{bmatrix} 1 & 3 & 1 & 9 \\ 0 & -2 & -2 & -8 \\ 0 & 2 & 2 & 8 \end{bmatrix}\to \begin{bmatrix} 1 & 3 & 1 & 9 \\ 0 & -2 & -2 & -8 \\ 0 & 0 & 0 & 0 \end{bmatrix}\to \begin{bmatrix} 1 & 0 & -2 & -3 \\ 0 & 1 & 1 & 4 \\ 0 & 0 & 0 & 0 \end{bmatrix} Using row operations to convert a matrix into reduced row echelon form is sometimes called .
In this case, the term Gaussian elimination refers to the process until it has reached its upper triangular, (unreduced) row echelon form. For computational reasons, when solving systems of linear equations, it is sometimes preferable to stop row operations before the matrix is completely reduced. \begin{bmatrix} 0 & \color{red}{\mathbf{2}} & 1 & -1 \\ 0 & 0 & \color{red}{\mathbf{3}} & 1 \\ 0 & 0 & 0 & 0 \end{bmatrix}.
It is in echelon form because the zero row is at the bottom and the leading entry of the second row (in the third column) is to the right of the leading entry of the first row (in the second column). A matrix is said to be in reduced row echelon form if furthermore all of the leading entries are equal to 1 (which can be achieved by using the elementary row operation of type 2), and in every column containing a leading entry, all of the other entries in that column are zero (which can be achieved by using elementary row operations of type 3). \begin{alignat}{4} 2x &{}+{}& y &{}-{}& z &{}={}& 8 & \qquad (L_1) \\ -3x &{}-{}& y &{}+{}& 2z &{}={}& -11 & \qquad (L_2) \\ -2x &{}+{}& y &{}+{}& 2z &{}={}& -3 & \qquad (L_3) \end{alignat} The table below is the row reduction process applied simultaneously to the system of equations and its associated augmented matrix.
In practice, one does not usually deal with the systems in terms of equations, but instead makes use of the augmented matrix, which is more suitable for computer manipulations. The row reduction procedure may be summarized as follows: eliminate from all equations below , and then eliminate from all equations below . This will put the system into triangular form.
Then, using back-substitution, each unknown can be solved for. The second column describes which row operations have just been performed. For the first step, is eliminated from by adding to .
Next, is eliminated from by adding to . These row operations are labelled in the table as \begin{align} L_2 + \tfrac32 L_1 &\to L_2, \\ L_3 + L_1 &\to L_3. \end{align} Once is also eliminated from the third row, the result is a system of linear equations in triangular form, and so the first part of the algorithm is complete.
From a computational point of view, it is faster to solve the variables in reverse order, a process known as back-substitution. One sees the solution is , , and . In particular, there is a unique solution to the original system of equations in this case.
Instead of stopping once the matrix is in row echelon form, one could continue until the matrix is in reduced row echelon form, as it is done in the table. The process of row reducing until the matrix is reduced is sometimes referred to as Gauss–Jordan elimination, to distinguish it from stopping after reaching echelon form. \det(A) = \frac{\prod\operatorname{diag}(B)}{d}.
Computationally, for an matrix, this method needs only arithmetic operations, while using Leibniz formula for determinants requires (n\, n!) operations (number of summands in the formula times the number of multiplications in each summand) , and recursive Laplace expansion requires operations if the sub-determinants are memorized for being computed only once (number of operations in a linear combination times the number of sub-determinants to compute, which are determined by their columns) . Even on the fastest computers, these two methods are impractical or almost impracticable for above 20.
A = \begin{bmatrix} 2 & -1 & 0 \\ -1 & 2 & -1 \\ 0 & -1 & 2 \end{bmatrix}. To find the inverse of this matrix, one takes the following matrix augmented by the identity and row-reduces it as a 3 × 6 matrix: [ 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].
By performing row operations, one can check that the reduced row echelon form of this augmented matrix is \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] =: [ I | B ]. One can think of each row operation as the left product by an elementary matrix. On the right, we see on the right that the product of these elementary matrices is (since ).
Meanwhile, on the left, we see that the effect of left multiplying the product of these matrices into yields the identity matrix. In other words, . Therefore , the inverse desired.
This procedure for finding the inverse works for square matrices of any size. 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}, where the stars are arbitrary entries, and are nonzero entries.
This echelon matrix contains a wealth of information about : the rank of is 5, since there are 5 nonzero rows in ; the vector space spanned by the columns of has a basis consisting of its columns 1, 3, 4, 7 and 9 (the columns with in ), and the stars show how the other columns of 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.
Bareiss algorithm
The first strongly-polynomial time algorithm for Gaussian elimination was published by Jack Edmonds in 19671. Independently, and almost simultaneously, Erwin Bareiss discovered another algorithm, based on the following remark, which applies to a division-free variant of Gaussian elimination.
In standard Gaussian elimination, one subtracts from each row R_i below the pivot row R_k a multiple of R_k by r_{i,k}/r_{k,k}, where r_{i,k} and r_{k,k} are the entries in the pivot column of R_i and R_k, respectively. Bareiss variant consists, instead, of replacing R_i with \frac{r_{k,k}R_i-r_{i,k}R_k}{r_{k-1,k-1}}.
This produces a row echelon form that has the same zero entries as with the standard Gaussian elimination. Bareiss' main remark is that each matrix entry generated by this variant is the determinant of a submatrix of the original matrix. In particular, if one starts with integer entries, the divisions occurring in the algorithm are exact divisions resulting in integers.
Therefore, all intermediate entries and final entries are integers. Moreover, Hadamard's inequality provides an upper bound on the absolute values of the intermediate and final entries, and thus a bit complexity of \tilde O(n^5), using soft O notation.
Moreover, as an upper bound on the size of final entries is known, a complexity \tilde O(n^4) can be obtained with modular computation followed either by Chinese remaindering or Hensel lifting. As a corollary, the following problems can be solved in strongly polynomial time with the same bit complexity: Testing whether m given rational vectors are linearly independent Computing the determinant of a rational matrix Computing a solution of a rational equation system Ax = b Computing the inverse matrix of a nonsingular rational matrix Computing the rank of a rational matrix h := 1 /* Initialization of the pivot row */ k := 1 /* Initialization of the pivot column */ while h ≤ m and k ≤ n: /* Find the k-th pivot: */ i_max := argmax (i = h ... m, abs(A[i, k])) if A[i_max, k] = 0: /* No pivot in this column, pass to next column */ k := k + 1 else: swap rows(h, i_max) /* Do for all rows below pivot: */ for i = h + 1 ... m: f := A[i, k] / A[h, k] /* Fill with zeros the lower part of pivot column: */ A[i, k] := 0 /* Do for all remaining elements in current row: */ for j = k + 1 ... n: A[i, j] := A[i, j] - A[h, j] * f /* Increase pivot row and column */ h := h + 1 k := k + 1 This algorithm differs slightly from the one discussed earlier, by choosing a pivot with largest absolute value.
Such a partial pivoting may be required if, at the pivot place, the entry of the matrix is zero. In any case, choosing the largest possible absolute value of the pivot improves the numerical stability of the algorithm, when floating point is used for representing numbers.
Upon completion of this procedure the matrix will be in row echelon form and the corresponding system may be solved by back substitution.
Text derived from https://en.wikipedia.org/w/index.php?oldid=1365416799 under CC BY-SA 4.0; modifications have been made.
References
- ↩Wikipedia “Gaussian elimination” publication date (×1) · confidence 0.95 revision URL