19
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},\\    \quad \ \ \ 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,

(2) \det B=\det A=d_{n}.

Combining (1) and (2) we get b_{nn}=d_{n}/d_{n-1}, which concludes the inductive argument.

Leave a Reply

You must be logged in to post a comment.