Gaussian Elimination¶
The idea of Gaussian elimination is to convert a system of linear equation into an equivalent system using elementary operations, such that, new system is easy to solve.
In previous classes we have seen many method of solving system of linear equation. \(i.e.,\)
 Hit and Trial Method
 Substitution Method
 Elimination
 Cramer's Rule
Gaussian elimination is a prominent method to solve any system of linear equation.
Step 1: Write out the augmented matrix¶
A system of linear equation is generally of the form
where \(A \in M(n \times m)\) and \(\newcommand{\R}{\mathbb{R}}\bb \in \R^n\) are given, and \(\x=(x_1,\dots, x_m)^T\) is the vector of unknowns. For example, the system
can be written in the form \eqref{eq:linear} with
To simplify notation, we write \(A\) and \(\bb\) into a single augmented matrix,
Step 2: Bring \(\tilde{A}\) into reduced row echelon form¶
The goal of this step is to bring the augmented matrix into reduced row echelon form. A matrix is in this form if
 the first nonzero entry of each row is \(1\), this element is referred to as the \emph{pivot},
 each pivot is the only nonzero entry in its column,
 each row has at least as many leading zeros as the previous r * For example, the following matrix is in row echelon form, where \(*\) could be any, possibly nonzero, number:
Three types of elementary row operations are permitted in this process, namely
 exchanging two rows of \(\tilde{A}\),
 multiplying a row by a nonzero scalar,
 adding a multiple of one row to another row.
As an example, we rowreduce the augmented matrix \eqref{e.m}:
Step 3: Zero, one, or many solutions?¶
There are two fundamentally different situations:

The matrix \(A\) is regular. In this case, the lefthand block of \(\tilde{A}\) has been reduced to the identity matrix. There is exactly one solution, independent of which vector \(\bb\) you started out with.

The matrix \(A\) is degenerate. In this case, the lefthand block of the rowreduced augmented matrix has more columns than nonzero rows. Then, dependent on which vector \(\bb\) you started out with, there is either no solution at all (the system is inconsistent), or an infinite number of solutions (the system is underdetermined).
If the rightmost column of the rowreduced augmented matrix has a nonzero entry in a row that is otherwise zero, the system is inconsistent.
Otherwise, the general solution has the following structure. It is the sum of a particular solution of the inhomogeneous equation \(A\x=\bb\) and the general solution of the homogeneous equation \(A\x=0\).
Step 4: Write out the solution¶
 If the lefthand block of the rowreduced matrix is not square, make it square by adding or removing rows of zeros. This has to be done in such a way that the leading \(1\) in each row (the \emph{pivot}) lies on the diagonal!
 The rightmost column of the rowreduced augmented matrix is a particular solution.
 To find a basis for the general solution of the homogeneous system, proceed as follows: Take every column of the rowreduced augmented matrix that has a zero on the diagonal. Replace that zero by \(1\). The set of these column vectors is the basis you need.
In the example above, a particular solution is \((9, 11, 5, 0)^T\) and the general solution of the homogeneous equation is a onedimensional subspace with basis vector \((2,1,1,1)^T\). Therefore, the general solution to the inhomogeneous equation \(A\x=\bb\) is the line
Another example: Assume that the rowreduced matrix is
Padding the matrix with the required rows of zeros gives
and the general solution is
Step 5: Check your solution¶
By multiplying \(A\) with the vectors representing the solution, you can easily verify that the computation is correct. In our example,
After watching this you can try question 1 from assignment 1.
Last modified on: 20230109 21:58:56