Let’s consider a problem where we have to buy oranges and apples but under the following conditions.

- The difference between 2X the number of oranges and the number of apples should be 3.
- The sum of 4X the number of oranges and the number of apples should be 9.
- The difference between 5X the number of oranges and 3X the number of apples should be 7.

# System of Linear Equations

These conditions could be modeled using the following equations

$$2x-y=3\tag{1}$$

$$4x+y=9\tag{2}$$

$$5x-3y=7\tag{3}$$

where $x$ and $y$ are the number of oranges and apples respectively. Collectively, these equations would be called a **system of linear equations** of variables $x$ and $y$.

We can also represent this system of linear equations using matrices as follows.

$$\begin{bmatrix} 2x - y \\ 4x+y \\ 5x-3y \end{bmatrix} = \begin{bmatrix} 3 \\ 9 \\ 7\end{bmatrix}$$

# Row Picture

The representation of a system of linear equations as a matrix multiplication product of the coefficients and the variable matrix is called the **row picture**. Each row represents a different linear equation.

$$\begin{bmatrix} 2 & -1 \\ 4 & 1 \\ 5 & -3 \end{bmatrix} \times \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 3 \\ 9 \\ 7\end{bmatrix}$$

As a linear algebra equation, this could be written as $\textbf{Ax=b}$. Where $\textbf{A}$ is the matrix of coefficients, $\textbf{x}$ is the vector of variables, and $\textbf{b}$ is the vector of constants.

# Column Picture

Alternatively, the coefficients of the variable $x$ and $y$ could be separated into two matrices as follows.

$$\begin{bmatrix} 2 \\ 4 \\ 5 \end{bmatrix} x \ + \begin{bmatrix} -1 \\ 1 \\ -3 \end{bmatrix}y = \begin{bmatrix} 3 \\ 9 \\ 7\end{bmatrix}$$

this is the **column picture** of the system of linear equations.

# Solution of Linear Equations

The value of variables that satisfies all equations is called the **solution** (or solutions if there are multiple) of the system of linear equations.

## One Solution

If we plot equations $(1)$, $(2)$, and $(3)$ on a 2D graph

The point at which all three lines intersect will be the solution of the linear equations i.e. $(2, 1)$.

## Infinitely Many Solutions

Consider the following system of linear equations.

$$x+3y=9 \tag{4}$$

$$2x+6y=18\tag{5}$$

If we plot them on a 2D graph, both lines overlap over each other.

The set of values for $x$ and $y$ for which both equations are satisfied is infinitely large. We can also observe this from the fact that if we multiply the equation $(4)$ by $2$ we get the equation $(5)$.

$$2 \times (x+3y = 9)$$

$$2x + 2\cdot3y = 2\cdot 9$$

$$2x+6y=18$$

Thus, the equation $(5)$ is just the equation $(4)$ scaled up by 2.

## No Solution

It is also possible for a system of linear equations that none of the variable values satisfy all the equations, like the following.

$$x+y=4 \tag{6}$$

$$x+y=8\tag{7}$$$$x-y=0 \tag{8}$$

Although we have multiple points of intersection between the lines, there is no single point where all three lines intersect. Thus, for no common values of $x$ and $y$ equations $(6)$, $(7)$, and $(8)$ are satisfied.

# Elimination Method

To find the values of $x$ and $y$ in the system of linear equations $(1)$, $(2)$, and $(3)$, we can start by eliminating one of the variables from any of the equations.

If we multiply the equation $(2)$ by $3$

$$3 \times (4x+y=9) $$

$$12x + 3y = 27 \tag{9}$$

and add it to the equation $(3)$

$$(5x - 3y)+(12x+3y) = 7+27$$

$$5x+12x-3y+3y=34$$

$$17x=34$$

$$x=2$$

Now that we know the value of $x$ we can substitute it into any equation (like equation $(2)$) to find the value of $y$.

$$4 \times 2 + y = 9$$

$$8 + y = 9$$

$$y=9-8$$

$$y=1$$

To verify if $(2, 1)$ is indeed the solution of the system of linear equations $(1)$, $(2)$, and $(3)$ we can test the values in the equation $(1)$.

$$2x-y=3$$

$$2 \times 2 - 1 = 3$$

$$4-1 = 3$$

$$3=3$$

Thus, we can confirm that $(2, 1)$ is the solution.

# Gaussian Elimination

The **Gaussian Elimination** is an algorithm for finding the solution of a system of linear equations by performing row-wise operation on the matrix of coefficients and constants. It is named after Carl Friedrich Gauss.

It is similar to the *elimination method* discussed above, the difference is that the operations are performed collectively on the matrix. It involves the following steps.

- Expressing the system of linear equations with matrices, in the row picture form.
- Creating an augmented matrices of coefficients and constants.
- Reducing the augmented matrix to its row echelon form.
- Breaking the row echelon form of the augmented matrix back to its row picture form.
- Solving the reduced equations to find the values of variables.

Let’s apply the Gaussian Elimination on the row picture of equations $(1)$, $(2)$, and $(3)$

$$\begin{bmatrix} 2 & -1 \\ 4 & 1 \\ 5 & -3 \end{bmatrix} \times \begin{bmatrix} x \\ y \end{bmatrix} = \begin{bmatrix} 3 \\ 9 \\ 7\end{bmatrix}$$

## Augmented Matrix of Coefficients and Constants

First, we have to create an augmented matrix from the coefficient and constants matrix of the row picture.

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 4 & 1 & | & 9 \\ 5 & -3 & | & 7\end{bmatrix}$$

Then, we reduce this augmented matrix to its row echelon form.

## Row Echelon Form

The **row echelon form** of a matrix is an upper-triangular matrix representation (the last row of the matrix could be just $0$s) of the augmented matrix.

To obtain the row echelon form, we can perform matrix addition, scalar multiplication (with values other than $0$) and swaps between the rows of the augmented matrix.

Initially, the first element in the diagonal of the matrix is the **pivot**. All the elements below the pivot have to be reduced to $0$s by performing scalar multiplication and matrix addition/subtraction between the pivot row and the rows below it.

$$\begin{bmatrix} {\color{blue} 2} & -1 & | & 3 \\ 4 & 1 & | & 9 \\ 5 & -3 & | & 7\end{bmatrix}$$

After that, we move on to the next pivot (next element in the diagonal) and repeat the process until we obtain the row echelon form. If the next pivot element candidate is zero then we won’t be able to reduce the elements below it to zero by just scalar multiplication and matrix addition/subtraction. In such cases, we perform a swap between the next row and any other row below it to obtain a non-zero element as the pivot.

If we multiply row 1 of the augmented matrix with the scalar value ${5 \over 2}$

$${5 \over 2} \times \begin{bmatrix} 2 & -1 & | & 3\end{bmatrix} = \begin{bmatrix} 5 & {-5 \over 2} & | & {15 \over 2}\end{bmatrix}$$

and subtract it from row 3 we will obtain the following matrix.

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 4 & 1 & | & 9 \\ 5-5 & -3+{5 \over 2} & | & 7-{15 \over 2}\end{bmatrix}$$

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 4 & 1 & | & 9 \\ 0 & {-1 \over 2} & | & {-1 \over 2}\end{bmatrix}$$

Next, to reduce the last element under the pivot to $0$, we can multiply row 1 with the scalar value $2$

$$2 \times \begin{bmatrix} 2 & -1 & | & 3 \end{bmatrix} = \begin{bmatrix} 4 & -2 & | & 6\end{bmatrix}$$

and subtract it from row 2.

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 4-4 & 1+2 & | & 9-6 \\ 0 & {-1 \over 2} & | & {-1 \over 2}\end{bmatrix}$$

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 0 & 3 & | & 3 \\ 0 & {-1 \over 2} & | & {-1 \over 2}\end{bmatrix}$$

Now, we move on to the next pivot.

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 0 & {\color{blue} 3} & | & 3 \\ 0 & {-1 \over 2} & | & {-1 \over 2}\end{bmatrix}$$

To reduce the element below the pivot to zeros we can multiply row 2 with the scalar value $1 \over 6$

$${1 \over 6} \times \begin{bmatrix} 0 & 3 & | & 3 \end{bmatrix} = \begin{bmatrix} 0 & {1 \over 2} & | & {1 \over 2} \end{bmatrix}$$

and add it to row 3

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 0 & 3 & | & 3 \\ 0+0 & {-1 \over 2}+{1 \over 2} & | & {-1 \over 2}+{1 \over 2}\end{bmatrix}$$

$$\begin{bmatrix} 2 & -1 & | & 3 \\ 0 & 3 & | & 3 \\ 0 & 0 & | & 0\end{bmatrix}$$

This is the row echelon form the augmented matrix created by equation $(1)$, $(2)$, and $(3)$. Notice that the number of non-zero elements in the diagonal ($2$ and $3$) equals to the number of variables in the equations ($x$ and $y$).

## Back Substitution

If we break the row echelon form of the augmented matrix back into the row picture we will obtain the reduced linear equations.

$$\begin{bmatrix} 2 & -1 \\ 0 & 3 \end{bmatrix} \times \begin{bmatrix} x \\ y\end{bmatrix} = \begin{bmatrix} 3 \\ 3\end{bmatrix}$$

$$\begin{bmatrix} 2x-y \\ 3y \end{bmatrix} = \begin{bmatrix} 3 \\ 3\end{bmatrix}$$

By solving these equations for the values of $y$

$$3y=y$$

$$y=1$$

and $x$

$$2x-y=3$$

$$2x - 1 = 3$$

$$2x = 3+1$$

$$2x=4$$

$$x=2$$

we have obtained the solution of the system of linear equations i.e. $(2, 1)$ which is the same solution that we got from the elimination method and the graph.

## Infinitely many solutions

Applying Gaussian Elimination to the system of linear equations $(4)$ and $(5)$.

- Creating the augmented matrix

$$\begin{bmatrix} 1 & 3 & | & 9 \\ 2 & 6 & | & 18 \end{bmatrix}$$

- Selecting the pivot element.

$$\begin{bmatrix} {\color{blue} 1} & 3 & | & 9 \\ 2 & 6 & | & 18 \end{bmatrix}$$

- Calculating the row echelon form by multiplying row 1 by the scalar value $2$ and subtracting it from row 2.

$$\begin{bmatrix} 1 & 3 & | & 9 \\ 0 & 0 & | & 0\end{bmatrix}$$

The number of non-zero elements in the diagonal ($1$) is lower than the number of variables in the equation ($x$ and $y$).

After converting the row echelon form back to the row picture we get back the equation $(4)$ which can have infinitely many solutions like $(1, 2)$, $(0, 3)$, $(9, 0)$, etc.

## No Solution

Following is the application of Gaussian elimination on the system of linear equations $(6)$, $(7)$, and $(8)$

- Creating the augmented matrix.

$$\begin{bmatrix} 1 & 1 & | & 4 \\ 1 & 1 & | & 8 \\ 1 & -1 & | & 0\end{bmatrix}$$

- Selecting the pivot element.

$$\begin{bmatrix} {\color{blue} 1} & 1 & | & 4 \\ 1 & 1 & | & 8 \\ 1 & -1 & | & 0\end{bmatrix}$$

- Subtracting row 1 from row 2

$$\begin{bmatrix} 1 & 1 & | & 4 \\ 0 & 0 & | & -4 \\ 1 & -1 & | & 0\end{bmatrix}$$

- Subtracting row 1 from row 3

$$\begin{bmatrix} 1 & 1 & | & 4 \\ 0 & 0 & | & -4 \\ 0 & -2 & | & -4\end{bmatrix}$$

- Since the next pivot candidate is $0$, we’ll have to swap rows 2 and 3 and make $-2$ the new pivot element.

$$\begin{bmatrix} 1 & 1 & | & 4 \\ 0 & {\color{blue} -2} & | & -4 \\ 0 & 0 & | & -4 \end{bmatrix}$$

We can’t reduce this further without disrupting the row echelon form. The number of non-zero elements in the diagonal ($1$, $-2$, and $-4$) is higher than the number of variables in the equations ($x$ and $y$).

The reduced equations obtained after converting this back to row picture are:

$$x+y=4 \tag{10}$$

$$-2y=-4 \tag{11}$$

$$0=-4 \tag{12}$$

The equation $(12)$ is a fallacy. Thus, we can confirm that there is no solution for the system of linear equations $(10)$, $(11)$, and $(12)$.

# Resources

2. Elimination with Matrices.

Part 1 : Linear equation of two variables and Matrices

Part 5 : Row Picture and Column Picture

Part 6 : Gaussian Elimination