Back Substitution

In Echelon form a system can be easily solved (say using a computer) using back-substitution, which is essentially going from the bottom equation and moving up. At each stage the current set of solutions is intersected with the set of solution that satisfy the equation that is processed.

To solve a single equation with more that one variable assigns a parameter to each free variable and represent the leading variable via the assigned parameters.

Consider

x1 + 3⁢ x2 + 3⁢ x3 + 2⁢ x4 + x5 = 7 -15⁢ x3 - 2⁢ x4 = -28 x4 = -1

The third equation has solution

𝒮3 = { ( s1, s2, s3, -1, s5 ) | s1, s2, s3, s5 ∈𝕂 }

The second equation has solution

𝒮2 = { ( w1, w2, -28+2⁢ w4 -15 , w4, w5 ) | w1, w2, w4, w5 ∈𝕂 }

Back substitution first intersects 𝒮2 with 𝒮3. The leading variable of the second equation is to left of the leading variable of the third equation thus the component of 𝒮2 which has a restriction corresponds to a non-restricted component in 𝒮3. Intersecting the two solutions is nothing more than taking the restriction of the third equation and substituting it in the set of solutions of the second equation.

𝒮2 ∩ 𝒮3 = { ( s1, s2, -28+2⁢ (-1) -15 , -1 ,s5 ) | s1, s2, s5 ∈𝕂 } = { ( s1, s2, 2 , -1 ,s5 ) | s1, s2, s5 ∈𝕂 }

The first step of back substitution is complete. Next is intersection with the set of solutions of the first equation which is

𝒮1 = { ( 7 -3⁢u2 -3⁢u3 -2⁢u4 -u5 , u2, u3, u4, u5 ) | u2, u3, u4, u5 ∈𝕂 }

Again all restrictions of the first equation are to the left of the restrictions of the set of solution obtained so far thus intersecting the two sets is straightforward substitution:

𝒮1 ∩ ( 𝒮2 ∩ 𝒮3 ) = { ( 7 -3⁢s2 -3⁢ (2) -2⁢ (-1) -s5 , s2, 2, -1, s5 ) | s2, s5 ∈𝕂 } = { ( 3 -3⁢s2 -s5 , s2 , 2 , -1 ,s5 ) | s2, s5 ∈𝕂 }

The above is the set of solutions. It can be hard to parse so let us first write the value of each variable separately

x1 = 3 - 3⁢ s2 - s5 x2 = s1 x3 = 2 x4 = -1 x5 = s2

Let us also include the zeroes:

x1 = 3 - 3⁢ s2 - s5 x2 = 0 + s2 + 0⁢ s5 x3 = 2 + 0⁢ s2 + 0⁢ s5 x4 = -1 + 0⁢ s2 + 0⁢ s5 x5 = 0 + 0⁢ s2 + s5

We can write the so called vector form of the solution.

{ ( 3 0 2 -1 0 ) + ( -3 1 0 0 0 ) ⁢s2 + ( -1 0 0 0 1 ) ⁢s5 ∣ s2 ,s5 ∈𝕂 }

Restrictions in the set of solutions need not be just constants, but there is no change in back-substitution.

Consider the following modified example

x1 + 3⁢ x2 + 3⁢ x3 + 2⁢ x4 + x5 = 7 -15⁢ x3 - 2⁢ x4 = -28 x4 - 30⁢ x5 = -1

The third equation has solution

𝒮3 = { ( s1, s2, s3, -1+30⁢s5 , s5 ) | s1, s2, s3, s5 ∈𝕂 }

The second equation has solution

𝒮2 = { ( w1, w2, -28+2⁢ w4 -15 , w4, w5 ) | w1, w2, w4, w5 ∈𝕂 }

Back substitution first intersects 𝒮2 with 𝒮3.

𝒮2 ∩ 𝒮3 = { ( s1, s2, -28+2⁢ (-1 +30⁢ s5 ) -15 , -1+30⁢s5 ,s5 ) | s1, s2, s5 ∈𝕂 } = { ( s1, s2, 2-4⁢s5 , -1+30⁢s5 ,s5 ) | s1, s2, s5 ∈𝕂 }

Next intersect with the set of solutions of the first equation

𝒮1 = { ( 7 -3⁢u2 -3⁢u3 -2⁢u4 -u5 , u2, u3, u4, u5 ) | u2, u3, u4, u5 ∈𝕂 }

to obtain:

𝒮1 ∩ ( 𝒮2 ∩ 𝒮3 ) = { ( 7 -3⁢s2 -3⁢ ( 2-4⁢s5 ) -2⁢ ( -1+30⁢s5 ) -s5 , s2, 2-4⁢s5 , -1+30⁢s5 ,s5 ) | s2, s5 ∈𝕂 } = { ( 3 -3⁢s2 -52⁢s5 , s2, 2-4⁢s5 , -1+30⁢s5 ,s5 ) | s2, s5 ∈𝕂 }

The above is the set of solutions to the system of linear equations. In vector form:

{ ( 3 0 2 -1 0 ) + ( -3 1 0 0 0 ) ⁢s2 + ( -52 0 -4 30 1 ) ⁢s5 ∣ s2 ,s5 ∈𝕂 }

If the system of linear equations is in Reduced Echelon form then there is even less bookkeeping in back-substitution.

Consider

x1 + 3⁢ x2 + x5 = 3 x3 = 2 x4 = -1

The third equation has solution

𝒮3 = { ( s1, s2, s3, -1, s5 ) | s1, s2, s3, s5 ∈𝕂 }

The second equation has solution

𝒮2 = { ( w1, w2, 2, w4, w5 ) | w1, w2, w4, w5 ∈𝕂 }

Intersecting those give:

𝒮2 ∩ 𝒮3 = { ( s1, s2, 2 , -1 ,s5 ) | s1, s2, s5 ∈𝕂 }

The set of solutions of the first equation is

𝒮1 = { ( 3 -3⁢u2 -u5 , u2, u3, u4, u5 ) | u2, u3, u4, u5 ∈𝕂 }

Intersecting with the set of solutions so far:

𝒮1 ∩ ( 𝒮2 ∩ 𝒮3 ) = { ( 3 -3⁢s2 -s5 , s2 , 2 , -1 ,s5 ) | s2, s5 ∈𝕂 }

The above is the set of solutions and as illustrated the Reduced Echelon form dispenses with the simplifications in each intersection. Those simplifications are essentially changing an Echelon form into a Reduced Echelon form.

Recall the first example

x1 + 3⁢ x2 + 3⁢ x3 + 2⁢ x4 + x5 = 7 -15⁢ x3 - 2⁢ x4 = -28 x4 = -1

which has shape

( * × × × × × 0 0 * × × × 0 0 0 * × × )

If we flip it horizontally

( 0 0 0 * × × 0 0 * × × × * × × × × × )

the result is not an Echelon form since the stair shape is not inverted. However, such shape is still easy to solve using forward substitution which is essentially back-subsitution but starting with the first equation of the system of linear equations and going down the equations. We focus on back-substitution only.