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 matricial 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 to $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 on 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 : single point of intersection (credits montereyinstitute)

$\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, the system then 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 does not provide any information about the variables.

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}$

Recapitulation

Transforming linear system into a matricial equation separates the coefficients from the variables. This make things more readable.

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

From the echelon matrix, we solve rows by substituing 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.