Gaussian Elimination with back-substitution is an algorithm for solving systems of linear equations using matrices and row-echelon form. The order in which the elementary row operations are performed is important. Always operate from left to right, column by column using elementary row operations to obtain zeros in all entries directly below leading 1’s. Only after a column has been completed do we continue to the next right column.

The advantage of using matrices to solve systems of linear equations is that it is a procedural and rule-based process. When the rules are followed exactly, the solving of a complex system of linear equations, equations that each has multiple terms with coefficients, is simplified.

To solve the following system of linear equations using Gaussian Elimination with Back-Substitution:

First, write the linear equations system to be solved.

Linear Equations System to be Solved

y + z − 2w = −3

x − 4y − 7z − w = −19

x + 2y − z = 2

2x +4y + z − 3w = −2

Next, transform the linear equation’s coefficients to a matrix.

Matrix of Linear Equations Transformed to Array

4×5 | x | y | z | w | = c |

R1: | 0 | 1 | 1 | −2 | −3 |

R2: | 1 | −4 | −7 | −1 | −19 |

R3: | 1 | 2 | −1 | 0 | 2 |

R4: | 2 | 4 | 1 | −3 | −2 |

(c is the constant term of each equation, Rn is row)

Interchange R1 with another row so the first column is a 1 in the upper left column. We will interchange R1 with R3. The reason for choosing R3 to place a leading 1 upper-left in the matrix is that the coefficients and constant are smaller then R2.

Augmented Matrix (iteration 1)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 1 | −4 | −7 | −1 | −19 |

R3: | 0 | 1 | 1 | −2 | −3 |

R4: | 2 | 4 | 1 | −3 | −2 |

Whenever rows in the matrix are interchanged the linear equations corresponding to the interchanged matrix rows do not need to be interchanged. This will become apparent after all row operations are complete, the matrix is a row-echelon form and we back-substitute to discover the value of each equation term variable.

Now continue using matrix row operations column by column and top-down. Move to the next rightward column only after completing the column directly to its left.

Interchange R2 & R3 to place the leading zero of R3 column 1 beneath the 1 of R1 column 1.

Matrix (iteration 2)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 1 | −4 | −7 | −1 | −19 |

R4: | 2 | 4 | 1 | −3 | −2 |

Matrix (iteration 3)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | −6 | −6 | −1 | −21 |

R4: | 2 | 4 | 1 | −3 | −2 |

−1R1 + R3

Matrix (iteration 4)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | −6 | −6 | −1 | −21 |

R4: | 0 | 0 | 3 | −3 | −6 |

−2R1 + R4

Interchange R3 & R4 to place the leading zero of R4 column 2 beneath the 1 of R2 column 2.

Matrix (iteration 5)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | 0 | 3 | −3 | −6 |

R4: | 0 | 0 | 0 | −13 | −39 |

6R2 + R4

The first completed columns are highlighted in red. Row-echelon completed columns will be highlighted red as matrix iterations continue.

Continue the Gaussian Elimination process until the matrices result in row-echelon form.

Matrix (iteration 6)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | 0 | 1 | −1 | −2 |

R4: | 0 | 0 | 0 | −13 | −39 |

Multiply R3 by 1/3

Matrix (final iteration)

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | 0 | 1 | −1 | −2 |

R4: | 0 | 0 | 0 | 1 | 3 |

Multiply R4 by −1/13

The matrix is now in row-echelon form. It is from this matrix we discover the value of each variable by back-substitution:

Matrix in Row-Echelon form

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | 0 | 1 | −1 | −2 |

R4: | 0 | 0 | 0 | 1 | 3 |

To use back-substitution begin from the bottom-right of the row-echelon matrix and proceed upward:

(1)x + (2)y − (1)z = (2) when x = −1

(1)y + (1)z − (2)w = (−3) when y = 2

(1)z − (1)w = (−2) when z = 1

(1)w = (3) when w = 3

(Ignore zero array elements beneath 1’s of each column)

y + z − 2w = −3

x − 4y − 7z − w = −19

x + 2y − z = 2

2x +4y + z − 3w = −2

= 2 + 1 − 2(3) = −3

= −1 − 4(2) − 7(1) − 3 = −19

= −1 + 2(2) − 1 = 2

= 2(−1) + 4(2) + 1 − 3(3) = −2

The system of equations has been solved by Gaussian Elimination with Back-Substitution.

A system of linear equations might not have a solution. Excluding the constant term matrix column, c, this can be seen as a row of an augmented matrix that has zeros.

Inconsistent Equations Matrix

4×5 | x | y | z | w | = c |

R1: | 1 | 2 | −1 | 0 | 2 |

R2: | 0 | 1 | 1 | −2 | −3 |

R3: | 0 | 0 | 0 | 0 | −2 |

R4: | 0 | 0 | 0 | 2 | 3 |

This tells us that the third equation result is impossible (z − w = 0 − 0 = −2). The original equations to be solved together as a system is inconsistent.

z − w = −2 is impossible.

As a final note for solving a system of equations using matrices, matrix elimination procedures sometimes result in fractional coefficients. Fractional coefficients can often be avoided by careful choice the order in which you apply elementary row operations.

Copyright © DigitMath.com

All Rights Reserved.