In linear algebra, Gaussian elimination is an algorithm that can be used to determine the solutions of a system of linear equations, to find the rank of a matrix, and to calculate the inverse of an invertible square matrix. Gaussian elimination is named after German mathematician and scientist Carl Friedrich Gauss. Linear algebra is the branch of mathematics concerned with the study of vectors, vector spaces (also called linear spaces), linear maps (also called linear transformations), and systems of linear equations. ... Flowcharts are often used to graphically represent algorithms. ... In mathematics and linear algebra, a system of linear equations is a set of linear equations such as A standard problem is to decide if any assignment of values for the unknowns can satisfy all three equations simultaneously, and to find such an assignment if it exists. ... In linear algebra, the column rank (row rank respectively) of a matrix A with entries in some field is defined to be the maximal number of columns (rows respectively) of A which are linearly independent. ... In mathematics, a matrix (plural matrices) is a rectangular table of elements (or entries), which may be numbers or, more generally, any abstract quantities that can be added and multiplied. ... In linear algebra, an n-by-n (square) matrix A is called invertible or non-singular if there exists an n-by-n matrix B such that where In denotes the n-by-n identity matrix and the multiplication used is ordinary matrix multiplication. ... Johann Carl Friedrich Gauss (pronounced ,  ; in German usually Gauß, Latin: ) (30 April 1777 – 23 February 1855) was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, electrostatics, astronomy, and optics. ...

Elementary row operations are used throughout the algorithm. The algorithm has two parts, each of which considers the rows of the matrix in order. The first part reduces the matrix to row echelon form while the second reduces the matrix further to reduced row echelon form. The first part alone is sufficient for many applications. In mathematics, elementary row (or column) operations are elementary linear transformations on a matrix which preserve matrix equivalence. ... In mathematics, a matrix is in row echelon form if is satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ... In mathematics, a matrix is in reduced row echelon form (also known as row canonical form) if it satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ...

A related but less-efficient algorithm, Gauss–Jordan elimination, brings a matrix to reduced row echelon form in one pass. In mathematics, Gauss–Jordan elimination is a version of Gaussian elimination that puts zeros both above and below each pivot element as it goes from the top row of the given matrix to the bottom. ...

History

The method of Gaussian elimination appears in Chapter Eight, Rectangular Arrays, of the important Chinese mathematical text Jiuzhang suanshu or The Nine Chapters on the Mathematical Art. Its use is illustrated in eighteen problems, with two to five equations. The first reference to the book by this title is dated to 179 CE, but parts of it were written as early as approximately 150 BCE.^[1] The Nine Chapters on the Mathematical Art (九章算術) is a Chinese mathematics book, probably composed in the 1st century AD, but perhaps as early as 200 BC. This book is the earliest surviving mathematical text from China that has come down to us by being copied by scribes and (centuries later...

However, the method was invented in Europe independently.^{[citation needed]} It is named after the mathematician Carl Friedrich Gauss. Leonhard Euler, considered one of the greatest mathematicians of all time A mathematician is a person whose primary area of study and research is the field of mathematics. ... Johann Carl Friedrich Gauss (pronounced ,  ; in German usually Gauß, Latin: ) (30 April 1777 – 23 February 1855) was a German mathematician and scientist who contributed significantly to many fields, including number theory, statistics, analysis, differential geometry, geodesy, electrostatics, astronomy, and optics. ...

Algorithm overview

The process of Gaussian elimination has two parts. The first part (Forward Elimination) reduces a given system to either triangular or echelon form, or results in a degenerate equation with no solution, indicating the system has no solution. This is accomplished through the use of elementary row operations. The second step uses back substitution to find the solution of the system above. In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan (for many, Gaussian elimination is regarded as the front half of the complete Gauss-Jordan elimination), is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining... In mathematics, a degenerate case is a limiting case in which a class of object changes its nature so as to belong to another, usually simpler, class. ... In mathematics, elementary row (or column) operations are elementary linear transformations on a matrix which preserve matrix equivalence. ... In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. ...

Stated equivalently for matrices, the first part reduces a matrix to row echelon form using elementary row operations while the second reduces it to reduced row echelon form, or row canonical form. In mathematics, a matrix is in row echelon form if is satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ... In mathematics, elementary row (or column) operations are elementary linear transformations on a matrix which preserve matrix equivalence. ... In mathematics, a matrix is in reduced row echelon form (also known as row canonical form) if it satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ... In mathematics, a matrix is in reduced row echelon form (also known as row canonical form) if it satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ...

Another point of view, which turns out to be very useful to analyze the algorithm, is that Gaussian elimination computes a matrix decomposition. The three elementary row operations used in the Gaussian elimination (multiplying rows, switching rows, and adding multiples of rows to other rows) amount to multiplying the original matrix with invertible matrices from the left. The first part of the algorithm computes an LU decomposition, while the second part writes the original matrix as the product of a uniquely determined invertible matrix and a uniquely determined reduced row-echelon matrix. In the mathematical discipline of linear algebra, a matrix decomposition is a factorization of a matrix into some canonical form. ... In linear algebra, the LU decomposition is a matrix decomposition which writes a matrix as the product of a lower and upper triangular matrix. ...

Example

Suppose the goal is to find and describe the solution(s), if any, of the following system of linear equations: In mathematics and linear algebra, a system of linear equations is a set of linear equations such as A standard problem is to decide if any assignment of values for the unknowns can satisfy all three equations simultaneously, and to find such an assignment if it exists. ...

The algorithm is as follows: eliminate x from all equations below L₁, and then eliminate y from all equations below L₂. This will put the system into triangular form. Then, using back-substitution, each unknown can be solved for. In the mathematical discipline of linear algebra, a triangular matrix is a special kind of square matrix where the entries below or above the main diagonal are zero. ...

In our example, we eliminate x from L₂ by adding to L₂, and then we eliminate x from L₃ by adding L₁ to L₃. Formally:

The result is:

Now we eliminate y from L₃ by adding − 4L₂ to L₃:

The result is:

This result is a system of linear equations in triangular form, and so the first part of the algorithm is complete.

The second part, back-substitution, consists of solving for the unknowns in reverse order. Thus, we can easily see that

Then, z can be substituted into L₂, which can then be solved easily to obtain

Next, z and y can be substituted into L₁, which can be solved to obtain

Thus, the system is solved.

This algorithm works for any system of linear equations. It is possible that the system cannot be reduced to triangular form, yet still have at least one valid solution: for example, if y had not occurred in L₂ and L₃ after our first step above, the algorithm would have been unable to reduce the system to triangular form. However, it would still have reduced the system to echelon form. In this case, the system does not have a unique solution, as it contains at least one free variable. The solution set can then be expressed parametrically (that is, in terms of the free variables, so that if values for the free variables are chosen, a solution will be generated). In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan (for many, Gaussian elimination is regarded as the front half of the complete Gauss-Jordan elimination), is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining... In mathematics, and in other disciplines involving formal languages, including mathematical logic and computer science, a free variable is a notation for a place or places in an expression, into which some definite substitution may take place, or with respect to which some operation (summation or quantification, to give two...

In practice, one does not usually deal with the actual systems in terms of equations but instead makes use of the augmented matrix (which is also suitable for computer manipulations). This, then, is the Gaussian Elimination algorithm applied to the augmented matrix of the system above, beginning with: In linear algebra, the augmented matrix of a matrix is obtained by combining two matrices. ... In linear algebra, the augmented matrix of a matrix is obtained by combining two matrices. ...

which, at the end of the first part of the algorithm looks like this:

That is, it is in row echelon form. In mathematics, a matrix is in row echelon form if is satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ...

At the end of the algorithm, we are left with

That is, it is in reduced row echelon form, or row canonical form. In mathematics, a matrix is in reduced row echelon form (also known as row canonical form) if it satisfies the following requirements: All nonzero rows are above any rows of all zeroes. ...

Other applications

Finding the inverse of a matrix

Suppose A is a matrix and you need to calculate its inverse. The identity matrix is augmented to the right of A, forming a matrix (the block matrix B = [A,I]). Through application of elementary row operations and the Gaussian elimination algorithm, the left block of B can be reduced to the identity matrix I, which leaves A ^{− 1} in the right block of B. It has been suggested that this article or section be merged with invertible matrix. ... In linear algebra, the identity matrix of size n is the n-by-n square matrix with ones on the main diagonal and zeros elsewhere. ... In the mathematical discipline of matrix theory, a block matrix or a partitioned matrix is a partition of a matrix into rectangular smaller matrices called blocks. ...

If the algorithm is unable to reduce A to triangular form, then A is not invertible.

In practice, inverting a matrix is rarely required. Most of the time, one is really after the solution of a particular system of linear equations.^[2]

The general algorithm to compute ranks and bases

The Gaussian elimination algorithm can be applied to any matrix A. If we get "stuck" in a given column, we move to the next column. In this way, for example, some matrices can be transformed to a matrix that has a reduced row echelon form like

(the *'s are arbitrary entries). This echelon matrix T contains a wealth of information about A: the rank of A is 5 since there are 5 non-zero rows in T; the vector space spanned by the columns of A has a basis consisting of the first, third, fourth, seventh and ninth column of A (the columns of the ones in T), and the *'s tell you how the other columns of A can be written as linear combinations of the basis columns. In linear algebra, the column rank (row rank respectively) of a matrix A with entries in some field is defined to be the maximal number of columns (rows respectively) of A which are linearly independent. ... In mathematics, a vector space (or linear space) is a collection of objects (called vectors) that, informally speaking, may be scaled and added. ...

Analysis

Gaussian elimination on an n × n matrix requires approximately 2n³ / 3 operations. So it has a complexity of .

This algorithm can be used on a computer for systems with thousands of equations and unknowns. However, the cost becomes prohibitive for systems with millions of equations. These large systems are generally solved using iterative methods. Specific methods exist for systems whose coefficients follow a regular pattern (see system of linear equations). It has been suggested that this article or section be merged with Guess value. ... In mathematics and linear algebra, a system of linear equations is a set of linear equations such as A standard problem is to decide if any assignment of values for the unknowns can satisfy all three equations simultaneously, and to find such an assignment if it exists. ...

The Gaussian elimination can be performed over any field. In abstract algebra, a field is an algebraic structure in which the operations of addition, subtraction, multiplication and division (except division by zero) may be performed, and the same rules hold which are familiar from the arithmetic of ordinary numbers. ...

Gaussian elimination is numerically stable for diagonally dominant or positive-definite matrices. For general matrices, Gaussian elimination is usually considered to be stable in practice if you use partial pivoting as described below, even though there are examples for which it is unstable.^[3] In the mathematical subfield of numerical analysis, numerical stability is a property of numerical algorithms. ... In mathematics, a matrix is said to be diagonally dominant if in every row of the matrix, the magnitude of the diagonal entry in that row is larger than the sum of the magnitudes of all the other (non-diagonal) entries in that row. ... In linear algebra, a positive-definite matrix is a Hermitian matrix which in many ways is analogous to a positive real number. ... In numerical analysis, pivoting is a process performed on a matrix in order to improve numerical stability, particularly in Gaussian elimination. ...

Pseudocode

As explained above, Gaussian elimination writes a given m × n matrix A uniquely as a product of an invertible m × m matrix S and a row-echelon matrix T. Here, S is the product of the matrices corresponding to the row operations performed.

The formal algorithm to compute T from A follows. We write A[i,j] for the entry in row i, column j in matrix A. The transformation is performed "in place", meaning that the original matrix A is lost and successively replaced by T.

 i := 1 j := 1 while (i ≤ m and j ≤ n) do Find pivot in column j, starting in row i: maxi := i for k := i+1 to m do if abs(A[k,j]) > abs(A[maxi,j]) then maxi := k end if end for if A[maxi,j] ≠ 0 then swap rows i and maxi, but do not change the value of i Now A[i,j] will contain the old value of A[maxi,j]. divide each entry in row i by A[i,j] Now A[i,j] will have the value 1. for u := i+1 to m do subtract A[u,j] * row i from row u Now A[u,j] will be 0, since A[u,j] - A[i,j] * A[u,j] = A[u,j] - 1 * A[u,j] = 0. end for i := i + 1 end if j := j + 1 end while  

This algorithm differs slightly from the one discussed earlier, because before eliminating a variable, it first exchanges rows to move the entry with the largest absolute value to the "pivot position". Such a pivoting procedure improves the numerical stability of the algorithm; some variants are also in use. In mathematics, the absolute value (or modulus[1]) of a real number is its numerical value without regard to its sign. ... In numerical analysis, pivoting is a process performed on a matrix in order to improve numerical stability, particularly in Gaussian elimination. ...

The column currently being transformed is called the pivot column. Proceed from left to right, letting the pivot column be the first column, then the second column, etc. and finally the last column before the vertical line. For each pivot column, do the following two steps before moving on to the next pivot column:

1. Locate the diagonal element in the pivot column. This element is called the pivot. The row containing the pivot is called the pivot row. Divide every element in the pivot row by the pivot to get a new pivot row with a 1 in the pivot position.
2. Get a 0 in each position below the pivot position by subtracting a suitable multiple of the pivot row from each of the rows below it.

Upon completion of this procedure the augmented matrix will be in row-echelon form and may be solved by back-substitution. In mathematics, Gaussian elimination or Gauss–Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan (many regard Gaussian elimination as the front half of the complete Gauss–Jordan elimination), is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank...

See also

• Frontal solver
• Gauss-Jordan elimination

A frontal solver is an approach to solving sparse linear systems which is used extensively in finite element analysis[1]. It is a variant of Gauss elimination that automatically avoids all operations involving zero terms. ... In mathematics, Gaussian elimination or Gauss-Jordan elimination, named after Carl Friedrich Gauss and Wilhelm Jordan, is an algorithm in linear algebra for determining the solutions of a system of linear equations, for determining the rank of a matrix, and for calculating the inverse of an invertible square matrix. ...

Notes

1. ^ Calinger, pp 234–236
2. ^ Atkinson (1989), p. 514
3. ^ Golub and Van Loan, §3.4.6

References

• Atkinson, Kendall A. An Introduction to Numerical Analysis, 2nd edition, John Wiley & Sons, New York, 1989. ISBN 0-471-50023-2.
• Calinger, Ronald (1999), A Contextual History of Mathematics, Prentice Hall, ISBN 978-0-02-318285-3 .
• Golub, Gene H., and Van Loan, Charles F. Matrix computations, 3rd edition, Johns Hopkins, Baltimore, 1996. ISBN 0-8018-5414-8.
• Lipschutz, Seymour, and Lipson, Mark. Schaum's Outlines: Linear Algebra. Tata McGraw-hill edition.Delhi 2001. pp. 69-80.

Pearson can mean Pearson PLC the media conglomerate. ...

External links

• Gaussian elimination www.math-linux.com.
• Gaussian elimination as java applet at some local site. Only takes natural coefficients.
• Gaussian elimination at Holistic Numerical Methods Institute
• LinearEquations.c Gaussian elimination implemented using C language