Gaussian elimination method for solving systems of linear equations.
Literature: Collection of problems in mathematics. Part 1. Edited by A. V. Efimov, B. P. Demidovich.
Let's consider a system of $m$ linear equations with $n$ unknowns of the general form.
$$\left\{\begin{array}{lcl}a_{11}x_1+a_{12}x_2+...+a_{1n}x_n=b_1\\ a_{21}x_1+a_{22}x_2+...+a_{2n}x_n=b_2\\...............................\\ a_{m1}x_1+a_{m2}x_2+...+a_{mn}x_n=b_m\end{array}\right.\qquad (1)$$
Forward elimination of the Gauss method:
Using elementary row operations and column permutations, the augmented matrix of system (1) can be transformed into the form:
$A=\begin{pmatrix}a_{11}'&a_{12}'&...&a_{1r}'&a_{1,r+1}'&...&a_{1n}'\\0&a_{22}'&...&a_{2r}'&a_{2,r+1}'&...&a_{2n}'\\...&...&...&...&...&...&...\\0&0&...&a_{rr}'&a_{r,r+1}'&...&a_{rn}'\\0&0&0&0&0&0&0\\...&...&...&...&...&...&...\\0&0&...&0&0&...&0\end{pmatrix};\qquad(2).$
Matrix (2) is the augmented matrix of the system.
$$\left\{\begin{array}{lcl}a_{11}'x_1+a_{12}'x_2+...+a_{1r}'x_r+a_{1,r+1}'x_{r+1}+...+a_{1n}'x_n=b_1'\\ \qquad\qquad a_{22}'x_2+...+a_{2r}'x_r+a_{2,r+1}'x_{r+1}+...+a_{2n}'x_n=b_2'\\\qquad\qquad\qquad..............................\\ \qquad\qquad\qquad\qquad\quad\,\, a_{rr}'x_r+a_{r,r+1}'x_{r+1}+...+a_{rn}'x_n=b_r'\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad 0=b_{r+1}'\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad0=b_{r+2}'\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad........\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad 0=b_m'\end{array}\right.\qquad (3)$$
which is equivalent to the original system.
Backward substitution of the Gauss method:
If at least one of the numbers $b'_{r+1}, ..., b'm$ is nonzero, then systems (3) and, consequently, the original system (1) are inconsistent. However, if $b'{r+1}=...=b'm=0$, then the system is consistent, and from equations (3), we can express the basic unknowns in terms of the free variables $x{r+1},...,x_n$.
Examples:
Using the Gauss method, investigate the consistency and find the general solution of the following systems:
3.240.
$$\left\{\begin{array}{lcl}x_1+2x_2+3x_3+4x_4=0\\7x_1+14x_2+20x_3+27x_4=0\\ 5x_1+10x_2+16x_3+19x_4=-2\\3x_1+5x_2+6x_3+13x_4=5\end{array}\right.$$
Solution.
Let's write down the augmented matrix:
$\begin{pmatrix}1&2&3&4&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\3&5&6&13&|&5\end{pmatrix}.$
By performing elementary row operations on the augmented matrix, we get:
$\begin{pmatrix}1&2&3&4&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\3&5&6&13&|&5\end{pmatrix}\sim (I\times3)$ $\begin{pmatrix}3&6&9&12&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\3&5&6&13&|&5\end{pmatrix}\sim (IV-I)$ $\begin{pmatrix}3&6&9&12&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(I\times\frac{5}{3})$ $\begin{pmatrix}5&10&15&20&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(III-I;I:5)$ $\begin{pmatrix}1&2&3&4&|&0\\7&14&20&27&|&0\\0&0&1&-1&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(I\times 7)$ $\begin{pmatrix}7&14&21&28&|&0\\7&14&20&27&|&0\\0&0&1&-1&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(II-I;I: 7)$
$\begin{pmatrix}1&2&3&4&|&0\\0&0&-1&-1&|&0\\0&0&1&-1&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(III+II;II: -1)$ $\begin{pmatrix}1&2&3&4&|&0\\0&0&1&1&|&0\\0&0&0&-2&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim$ $\begin{pmatrix}1&2&3&4&|&0\\0&-1&-3&1&|&5\\0&0&1&1&|&0\\0&0&0&-2&|&-2\end{pmatrix}.$
The system is consistent.
Back substitution step of the Gauss method:
$-2x_4=-2\Rightarrow x_4=1;$
$x_3+x_4=0\Rightarrow x_3=-x_4=-1;$
$-x_2-3x_3+x_4=5\Rightarrow x_2=-3x_3+x_4-5=3+1-5=-1$
$x_1+2x_2+3x_3+4x_4=0\Rightarrow x_1=-2x_2-3x_3-4x_4=2+3-4=1.$
Answer:$x_1=1; x_2=-1; x_3=-1;x_4=1.$
3.241.
$$\left\{\begin{array}{lcl}x_1+x_2=1\\ x_1+x_2+x_3=4\\x_2+x_3+x_4=-3\\x_3+x_4+x_5=2\\x_4+x_5=-1\end{array}\right.$$
Solution.
Let's write down the augmented matrix:
$\begin{pmatrix}1&1&0&0&0&|&1\\1&1&1&0&0&|&4\\0&1&1&1&0&|&-3\\0&0&1&1&1&|&2\\0&0&0&1&1&|&-1\end{pmatrix}.$
By performing elementary row operations on the augmented matrix, we get:
$\begin{pmatrix}1&1&0&0&0&|&1\\1&1&1&0&0&|&4\\0&1&1&1&0&|&-3\\0&0&1&1&1&|&2\\0&0&0&1&1&|&-1\end{pmatrix}\sim(II-I)$
$\begin{pmatrix}1&1&0&0&0&|&1\\0&0&1&0&0&|&3\\0&1&1&1&0&|&-3\\0&0&1&1&1&|&2\\0&0&0&1&1&|&-1\end{pmatrix}\sim(IV-II-V)$
$\begin{pmatrix}1&1&0&0&0&|&1\\0&0&1&0&0&|&3\\0&1&1&1&0&|&-3\\0&0&0&0&0&|&0\\0&0&0&1&1&|&-1\end{pmatrix}\sim$
$\begin{pmatrix}1&1&0&0&0&|&1\\0&1&1&1&0&|&-3\\0&0&1&0&0&|&3\\0&0&0&1&1&|&-1\\0&0&0&0&0&|&0\end{pmatrix}.$
The system is consistent.
Backward substitution using the Gauss method:
$x_5=c;$
$x_4+x_5=-1 \Rightarrow x_4=-1-x_5=-1-c;$
$x_3=3$
$x_2+x_3+x_4=-3\Rightarrow x_2=-3-x_3-x_4=-3-3+1+c=-5+c.$
$x_1+x_2=1\Rightarrow x_1=1-x_2=1+5-c=6-c$
Answer: $x_1=6-c; x_2=-5+c; x_3=3; x_4=1-c; x_5=c.$
Jordan-Gauss method for solving systems of linear equations.
Using elementary row operations and column permutations, the augmented matrix of the system (1) can be transformed into the form:
$A=\begin{pmatrix}1&0&...&0&a_{1r+1}'&...&a_{1n}'\\0&1&...&0&a_{2,r+1}'&...&a_{2n}'\\...&...&...&...&...&...&...\\0&0&...&1&a_{r,r+1}'&...&a_{rn}'\\0&0&0&0&0&0&0\\...&...&...&...&...&...&...\\0&0&...&0&0&...&0\end{pmatrix};\qquad(4).$
The matrix (4) is the augmented matrix of the system
$$\left\{\begin{array}{lcl}x_1\qquad\qquad\quad+a_{1,r+1}'x_{r+1}+...+a_{1n}'x_n=b_1'\\ \qquad x_2\qquad\quad+a_{2,r+1}'x_{r+1}+...+a_{2n}'x_n=b_2'\\\qquad\qquad..........................\\ \qquad\qquad\quad x_r+a_{r,r+1}'x_{r+1}+...+a_{rn}'x_n=b_r'\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad 0=b_{r+1}'\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad0=b_{r+2}'\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad........\\\qquad\qquad\qquad\qquad\qquad\qquad\qquad\qquad 0=b_m'\end{array}\right.\qquad (5)$$ which is equivalent to the original system.
If at least one of the numbers $b'_{r+1},...,b'm$ is nonzero, then systems (5) and, consequently, the original system (1) are inconsistent. However, if $b'{r+1}=...=b'm=0$, then the system is consistent, and formulas (5) provide an explicit expression for the basic variables in terms of the free variables $x{r+1},...,x_n$.
Examples:
Using the Jordan-Gauss method, investigate the consistency and find the general solution of the following systems:
3.240.
$$\left\{\begin{array}{lcl}x_1+2x_2+3x_3+4x_4=0\\7x_1+14x_2+20x_3+27x_4=0\\ 5x_1+10x_2+16x_3+19x_4=-2\\3x_1+5x_2+6x_3+13x_4=5\end{array}\right.$$
Solution.
Let's write down the augmented matrix:
$\begin{pmatrix}1&2&3&4&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\3&5&6&13&|&5\end{pmatrix}.$
Performing elementary row operations on the augmented matrix, we get:
$\begin{pmatrix}1&2&3&4&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\3&5&6&13&|&5\end{pmatrix}\sim (I\times3)$ $\begin{pmatrix}3&6&9&12&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\3&5&6&13&|&5\end{pmatrix}\sim (IV-I)$ $\begin{pmatrix}3&6&9&12&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(I\times\frac{5}{3})$ $\begin{pmatrix}5&10&15&20&|&0\\7&14&20&27&|&0\\5&10&16&19&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(III-I;I:5)$ $\begin{pmatrix}1&2&3&4&|&0\\7&14&20&27&|&0\\0&0&1&-1&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(I\times 7)$ $\begin{pmatrix}7&14&21&28&|&0\\7&14&20&27&|&0\\0&0&1&-1&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(II-I;I: 7)$ $\begin{pmatrix}1&2&3&4&|&0\\0&0&-1&-1&|&0\\0&0&1&-1&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim(III+II;II: -1)$ $\begin{pmatrix}1&2&3&4&|&0\\0&0&1&1&|&0\\0&0&0&-2&|&-2\\0&-1&-3&1&|&5\end{pmatrix}\sim$ $\begin{pmatrix}1&2&3&4&|&0\\0&-1&-3&1&|&5\\0&0&1&1&|&0\\0&0&0&-2&|&-2\end{pmatrix}\sim(I+II\times 2)$ $\begin{pmatrix}1&0&-3&6&|&10\\0&-1&-3&1&|&5\\0&0&1&1&|&0\\0&0&0&-2&|&-2\end{pmatrix}\sim(I+III\times 3;II+III\times 3;IV:-2)$ $\begin{pmatrix}1&0&0&9&|&10\\0&-1&0&4&|&5\\0&0&1&1&|&0\\0&0&0&1&|&1\end{pmatrix}\sim(I-IV\times 9;II-IV\times 4;III-IV)$ $\begin{pmatrix}1&0&0&0&|&1\\0&-1&0&0&|&1\\0&0&1&0&|&-1\\0&0&0&1&|&1\end{pmatrix}\sim(II:-1)$ $\begin{pmatrix}1&0&0&0&|&1\\0&1&0&0&|&-1\\0&0&1&0&|&-1\\0&0&0&1&|&1\end{pmatrix}.$
From here, we immediately get the answer.
Answer:$x_1=1; x_2=-1; x_3=-1;x_4=1.$
3.241.
$$\left\{\begin{array}{lcl}x_1+x_2=1\\ x_1+x_2+x_3=4\\x_2+x_3+x_4=-3\\x_3+x_4+x_5=2\\x_4+x_5=-1\end{array}\right.$$
Solution.
Let's write down the augmented matrix:
$\begin{pmatrix}1&1&0&0&0&|&1\\1&1&1&0&0&|&4\\0&1&1&1&0&|&-3\\0&0&1&1&1&|&2\\0&0&0&1&1&|&-1\end{pmatrix}.$
Performing elementary row operations on the augmented matrix, we obtain:
$\begin{pmatrix}1&1&0&0&0&|&1\\1&1&1&0&0&|&4\\0&1&1&1&0&|&-3\\0&0&1&1&1&|&2\\0&0&0&1&1&|&-1\end{pmatrix}\sim(II-I)$ $\begin{pmatrix}1&1&0&0&0&|&1\\0&0&1&0&0&|&3\\0&1&1&1&0&|&-3\\0&0&1&1&1&|&2\\0&0&0&1&1&|&-1\end{pmatrix}\sim(IV-II-V)$ $\begin{pmatrix}1&1&0&0&0&|&1\\0&0&1&0&0&|&3\\0&1&1&1&0&|&-3\\0&0&0&0&0&|&0\\0&0&0&1&1&|&-1\end{pmatrix}\sim$$\begin{pmatrix}1&1&0&0&0&|&1\\0&1&1&1&0&|&-3\\0&0&1&0&0&|&3\\0&0&0&1&1&|&-1\\0&0&0&0&0&|&0\end{pmatrix}\sim(I-II+III; II-III-IV)$ $\begin{pmatrix}1&0&0&-1&0&|&7\\0&1&0&0&-1&|&-5\\0&0&1&0&0&|&3\\0&0&0&1&1&|&-1\\0&0&0&0&0&|&0\end{pmatrix}\sim(I+IV)$ $\begin{pmatrix}1&0&0&0&1&|&6\\0&1&0&0&-1&|&-5\\0&0&1&0&0&|&3\\0&0&0&1&1&|&-1\\0&0&0&0&0&|&0\end{pmatrix}.$ Considering $x_1, x_2, x_3, x_4 -$
as basic variables and $x_5 -$ as a free variable, we get
$x_5=c;$
$x_4+x_5=-1 \Rightarrow x_4=-1-x_5=-1-c;$
$x_3=3$
$x_2-x_5=-5\Rightarrow x_2=-5+x_5=-5+c.$
$x_1+x_5=6\Rightarrow x_1=6-x_5=6-c.$
Answer: $x_1=6-c; x_2=-5+c; x_3=3; x_4=1-c; x_5=c.$
Homework.
1. Using the Gauss method and the Jordan-Gauss method, investigate the compatibility and find the general solution of the following system: $$\left\{\begin{array}{lcl}x_1-2x_2+3x_3=6\\ 2x_1+3x_2-4x_3=18\\3x_1-2x_2+5x_3=6\end{array}\right.$$
3.242. Using the Gauss method, investigate the compatibility and find the general solution of the following system
$$\left\{\begin{array}{lcl}105x_1-175x_2-315x_3+245x_4=84\\ 90x_1-150x_2-270x_3+210x_4=72\\75x_1-125x_2-225x_3+175x_4=59\end{array}\right.$$
Answer: The system is inconsistent.
3.243. Investigate the compatibility using the Jordan-Gauss method and find the general solution of the following system.
$$\left\{\begin{array}{lcl}8x_1+12x_2=20\\ 14x_1+21x_2=35\\9x_3+11x_4=0\\16x_3+20x_4=0\\10x_3+12x_6=22\\15x_5+18x_6=33\end{array}\right.$$
Answer: $x_1=\frac{5}{2}-\frac{3}{2}c_1; x_2=c_1; x_3=0; x_4=0; x_5=\frac{11}{5}-\frac{6}{5}c_2; x_6=c_2.$
