studybyyourself » Chapter 3 : Matrix and elimination

1. Matrix

A matrix is a grid of $m$ rows and $n$ columns. It contains the coefficients of a linear system. These are the so-called elements of the matrix.

Example I shows how a linear system is turned into a matrix equation in the form $A\vec{x} = \vec{y}$.

Example I

$\left\{ \begin{array}{ r@{~}c@{~} r!{~} } -x-3y+z & = & 10 \\ x+y-3z & = & -12 \\ 3x+4y+2z & = & -5 \end{array} \right. \iff \underbrace{ \begin{pmatrix} -1 & -3 & 1 \\ 1 & 1 & -3 \\ 3 & 4 & 2 \end{pmatrix} }_{ A } \underbrace{ \begin{pmatrix} x \\ y \\ z \\ \end{pmatrix} }_{ \vec{x} } = \underbrace{ \begin{pmatrix} 10 \\ -12 \nonumber \\ -5 \\ \end{pmatrix} }_{ \vec{y} }$

Index notation is used to specify a matrix element $a_{i,j}$, with $i$ the row and $j$ the column. For example, the element $a_{3,2}$ equals $4$ in the $A$ matrix of example I.

2. Matrix elimination

The matrix elimination, also called Gaussian elimination, is a method to solve a linear system. This is in fact the addition method applied to matrices.

The starting point for a matrix elimination is the augmented matrix, as example II shows. The variable elimination is performed by adding two rows together. One of the two rows is then replaced by the result of the addition.

Example II

$\left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -3 & 1 & 10 \\ 1 & 1 & -3 & -12 \\ 3 & 4 & 2 & -5 \end{array} \right) \overset{ R{_1}+R{_2}\rightarrow{R_2}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -3 & 1 & 10 \\ 0 & -2 & -2 & -2 \\ 3 & 4 & 2 & -5 \end{array} \right) \overset{3R{_1}+R{_3}\rightarrow{R_3}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -3 & 1 & 10 \\ 0 & -2 & -2 & -2 \\ 0 & -5 & 5 & 25 \end{array} \right)$

$\overset{ -\frac{1}{2}R{_2} \rightarrow R{_2}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -3 & 1 & 10 \\ 0 & 1 & 1 & 1 \\ 0 & -5 & 5 & 25 \end{array} \right) \overset{5R{_2}+R{_3} \rightarrow R{_3}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -3 & 1 & 10 \\ 0 & 1 & 1 & 1 \\ 0 & 0 & 10 & 30 \end{array} \right)$
Once we get the augmented matrix in echelon form we can solve back the system by going from the bottom up, as follows :

$ 10z = 30 \iff$ $z = 3$

Let’s replace $z$ in the second row :

$ y + 1 \cdot \underbrace{3}_{z} = 1 \iff$ $y = -2$

Let’s replace $y$ and $z$ in the first row :

$-1x + -3 \cdot \underbrace{-2}_{y} + 1 \cdot \underbrace{3}_{z} = 10 \iff -x + 9 = 10 \iff$ $x = -1$

The solution is :

Figure 3.1 : the solution of a linear system of three variables is the intersection point of three planes (wikipedia)

$\begin{equation} \vec{x} = \begin{pmatrix} -1 \\ -2 \\ 3 \end{pmatrix} \end{equation}$

Example III

$\left\{ \begin{array}{ r@{~}c@{~} r!{~} } 4x+y+3z & = & 1 \\ 2x+y+z & = & 2 \\ -x-y \phantom{+8z} & = & 0 \end{array} \right. \iff \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} 4 & 1 & 3 & 1 \\ 2 & 1 & 1 & 2 \\ -1 & -1 & 0 & 0 \end{array} \right) \overset{ R{_1} \leftrightarrow R{_3}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -1 & 0 & 0 \\ 2 & 1 & 1 & 2 \\ 4 & 1 & 3 & 1 \end{array} \right)$
$\overset{2R{_1}+R{_2}\rightarrow{R_2}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -1 & 0 & 0 \\ 0 & -1 & 1 & 2 \\ 4 & 1 & 3 & 1 \end{array} \right) \overset{ 4R{_1}+R{_3} \rightarrow R{_3}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -1 & 0 & 0 \\ 0 & -1 & 1 & 2 \\ 0 & -3 & 3 & 1 \end{array} \right) \overset{ -3R{_2}+R{_3} \rightarrow R{_3}}{\iff} \left( \begin{array}{!{}l@{~} !{}l@{~} !{~}l | !{~}l@{}} -1 & -1 & 0 & 0 \\ 0 & -1 & 1 & 2 \\ 0 & 0 & 0 & -5 \end{array} \right)$

From the last row of the echelon matrix we have :

$0x+0y+0z = -5$

That equation is unsolvable, therefore the system has no solution :

$\begin{equation} \vec{x} = \{\} \end{equation}$

Example IV

$\left\{ \begin{array}{ r@{~}c@{~} r!{~} } 2x+-2y & = & 2 \\ x+ -y & = & 1 \end{array} \right. \iff \left( \begin{array}{!{}l@{~} !{~}l | !{~}l@{}} 2 & -2 & 2 \\ 1 & -1 & 1 \end{array} \right) \overset{ R{_1} \leftrightarrow R{_2}}{\iff} \left( \begin{array}{!{}l@{~} !{~}l | !{~}l@{}} 1 & -1 & 1 \\ 2 & -2 & 2 \end{array} \right) \overset{ -2R{_1}+R{_2}\rightarrow{R_2}}{\iff} \left( \begin{array}{!{}l@{~} !{~}l | !{~}l@{}} 1 & -1 & 1 \\ 0 & 0 & 0 \end{array} \right)$

From the last row of the echelon matrix we have :

$0x+0y = 0 \iff 0=0$

That equation provides no information about the variables, since any pair of $(x, y)$ satisfies it.

Let’s move on to the upper row from which we get :

$1x+-1y = 1 \iff x = 1+y$. Let $y= \beta$.

Only one relevant equation remains but the system has two variables. Thus the system has infinitely many solutions and the general solution is :

$\begin{equation} \vec{x} = \begin{pmatrix} 1 + \beta \\ \beta \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \end{pmatrix} + \beta\begin{pmatrix} 1 \\ 1 \end{pmatrix} \end{equation}, \beta \in \mathbb{R}$

Wrap-up

The matrix equation makes it possible to separates the coefficients from the variables. This simplifies the notation.

Solving a matrix equation is done by performing operations on the augmented matrix rows, namely interchanging rows, multiplying a row by a factor (different from $0$) and replacing a row by the sum of two rows together. This until we eventually get a matrix in echelon form (like a staircase).

From the echelon matrix, we solve rows by substituting back the values found from the bottom up. Rows of all zeroes do not provide any information about the variables and can thus be ignored.