Gaussian elimination method

Aug 19

Gaussian elimination method

Gaussian elimination method

Consider the system

$a_{11}x+a_{12}y+a_{13}z=a_{1}$ , $a_{21}x+a_{22}y+a_{23}z=a_{2}$ , $a_{31}x+a_{32}y+a_{33}z=a_{3}.$

If the first equation is nontrivial, then one of the coefficients is different from zero. Suppose it is $a_{11}.$ Adding the first equation multiplied by $-a_{21}/a_{11}$ to the second one we eliminate $x$ from it. Similarly, adding the first equation multiplied by $-a_{31}/a_{11}$ to the third one we eliminate $x$ from it. The system becomes

$a_{11}x+a_{12}y+a_{13}z=a_{1}$ , $b_{22}y+b_{23}z=b_{2}$ , $b_{32}y+b_{33}z=b_{3},$

where $b$ with indexes stands for new numbers.

If $b_{22}\neq 0,$ we can use the second equation to eliminate $y$ from the third equation and the result will be

$a_{11}x+a_{12}y+a_{13}z=a_{1}$ , $b_{22}y+b_{23}z=b_{2}$ , $c_{33}z=c_{3}$

with some new $c$ 's. If $c_{33}\neq 0,$ we can solve the system backwards, finding first $z$ from the third equation, then $y$ from the second and, finally $x$ from the first.

Notice that for the method to work it does not matter what happens with the vector at the right of the system. It only matters what happens to $A.$ That's why we focus on transformations of $A.$

Theoretical treatment

Exercise 1. Denote

$d_{1}=a_{11},\ d_{2}=\det \left(\begin{array}{cc}a_{11} & a_{12} \\ a_{21} & a_{22}\end{array}\right) ,..., \ d_{n}=\det A$

the leading principal minors of $A.$ If all of them are different from zero, then the Gaussian method reduces $A$ (by way of premultiplication of $A$ by elementary matrices) to the triangular matrix

$B=\left(\begin{array}{cccc}b_{11} & b_{12} & ... & b_{1n} \\ 0 & b_{22} & ... & b_{2n} \\ ... & ... & ... & ... \\0 & 0 & ... & b_{nn}\end{array}\right)$

where $b_{11}=d_{1},\ b_{22}=d_{2}/d_{1},...,\ b_{nn}=d_{n}/d_{n-1}.$

Proof by induction. Let $n=2.$ Premultiplying $A=\left(\begin{array}{cc}a_{11} & a_{12} \\a_{21} & a_{22}\end{array}\right)$ by $I-\frac{a_{21}}{a_{11}}e_{2}^{T}e_{1}$ we get the desired result:

$B=\left(\begin{array}{cc}a_{11} & a_{12} \\0 & a_{22}-\frac{a_{21}a_{12}}{a_{11}}\end{array}\right) =\left(\begin{array}{cc}d_{1} & a_{12} \\0 & \frac{d_{2}}{d_{1}}\end{array}\right) .$

Now let the statement hold for $n-1.$ By the induction assumption we can start with the matrix of form

$A=\left(\begin{array}{ccccc}d_{1} & b_{12} & ... & b_{1n} & b_{1n} \\ 0 & d_{2}/d_{1} & ... & b_{2n} & b_{2n} \\ ... & ... & ... & ... & ... \\0 & 0 & ... & d_{n-1}/d_{n-2} & b_{2n} \\ a_{n1} & a_{n2}&... & a_{n-1,n} & a_{nn} \end{array}\right) .$

Using the condition that all $d_{1},...,d_{n-1}$ are different from zero, we can make zero the elements $a_{n1}, ..., a_{n-1,n}$ . The result is:

$B=\left(\begin{array}{ccccc}d_{1} & b_{12} & ... & b_{1n} & b_{1n} \\ 0 & d_{2}/d_{1} & ... & b_{2n} & b_{2n} \\ ... & ... & ... & ... & ... \\0 & 0 & ... & d_{n-1}/d_{n-2} & b_{2n} \\ 0 & 0 & ... & 0 & b_{nn}\end{array}\right) .$

The determinant of a triangular matrix equals the product of diagonal elements because of the cross-out rule:

(1) $\det B=d_{1}(d_{2}/d_{1})...(d_{n-1}/d_{n-2})b_{nn}=d_{n-1}b_{nn}$

(for example, if a product contains $b_{1n}$ , you should cross out the first row and then the product should contain one of the zeros below $d_1$ ).

On the other hand, $B$ is a result of premultiplication by elementary matrices: $B=C_{1}...C_{n-1}A$ where by Exercise 1 $\det C_{i}=1$ for all $i.$ Hence,