Why Gaussian Elimination works?
Elementary Matrices
Given an augmented matrix of a system of m linear equations in n variables, we can do three elementary row operations on it. It turns out those operations can be regarded as the multiplication of some very specific n x n square matrices to the augmented matrix. Those n x n square matrices are called the elementary matrices.
Suppose the augmented matrix is , where is the m x n coefficient matrix and is the column matrix formed by the constants on the right hand side of the linear equations in the system. We consider the three elementary row operations one by one as follows:
Interchange ith and jth rows:
Let , where the two off-diagonal "1"s are in the ith and jth rows. Then we multiply it to the augmented matrix as follows:
Then is the augmented matrix after interchanging ith and jth rows.
Multiply ith row by a nonzero constant:
Let , where the "" is in the ith row. Then we multiply it to the augmented matrix as follows:
Then is the augmented matrix after multiplying the ith row by .
Replace ith row by the sum of itself and times jth row:
Let , where the "" is in the position. Then we multiply it to the augmented matrix as follows:
Then is the augmented matrix after replacing ith row by the sum of itself and times jth row.
Remark: As we know, elementary row operations are reversible. Therefore, any elementary matrix is invertible and its inverse is also an elementary matrix.
In the applet below, you can use an elementary matrix to do various row operations on a 5 x 6 matrix by computing . Find the elementary matrix for each of the following row operations:
- Interchange 1st row and 3th row.
- Multiply 5th row by 2.
- Replace 2nd row by the sum of itself and 3 times 1st row.
Why Gaussian elimination works?
Given an augmented matrix of a linear system , the corresponding matrix equation is . Whenever we do a row operation on the augmented matrix, there exists an elementary matrix such that the new augmented matrix is and the new matrix equation is .
If solves the matrix equation , it certainly solves . Conversely, if solves , then it solves , which is . Therefore, both linear systems must have the same set of solutions.
Suppose the augmented matrix is row reduced to the one in echelon in r steps. Then there exists a sequence of elementary matrices such that is in echelon form, and its corresponding matrix equation is . Using the above fact repeatedly, we can see that its set of solutions is the same as that of the original matrix equation . More generally, if two linear system are row equivalent, they have the same set of solutions. That is why Gaussian elimination works.