Gaussian Elimination
What is Gaussian Elimination?
Given a system of linear equations:
,
where are real numbers. We want to find an efficient way to solve the system for the solution(s). Let us first consider a very simple example:
In high school, we already learned how to solve this system: We can multiple the first equation by 2 and add to the second equation to eliminate the variable . Then we get
The solution to the system can be easily obtained by first solving the second equation for and then substitute the value of to the first equation to find the value of . Hence the solution is .
This variable-eliminating process can be vastly generalized to deal with any system of linear equations of any size. Such generalization is called Gaussian elimination. The action of using one equation to eliminate a variable in another equation is a special case of the so-called elementary row operation. And the system in the last step that we can easily solve for the solution is said to be in echelon form. This is the "workhorse algorithm" that all students must learn well when studying linear algebra because almost every problem in linear algebra involving computation is about solving a linear system of some kind.
Augmented Matrix
For a system of linear equations, all the essential information is contained in the coefficients and the constants . Therefore, we can compactly represent the system as a matrix. First of all, we have
is called the coefficient matrix of the system. The column contains all the coefficients of the variable in all the linear equations, where . Then we can add the column of constant to the right in the coefficient matrix and separate it from the coefficients by a vertical line to form the augmented matrix of the system:
(Note: The vertical line may not be drawn in augmented matrices in some textbooks.)
Gaussian elimination is an algorithm of transforming an augmented matrix into the one in echelon form.
Exercise
Write down the augmented matrix of the following system of linear equations: