General Solution

Elimination and other factorizations offer a method for obtaining the particular solutions (x_p) of a linear system. The complete solution (x_c) is the generalized answer.

Introduction

First Example

The example used here here:

x + 2y + z = 2
3x + 8y + z = 12
4y + z = 2

Is rewritten as a linear system and eliminated into:

┌           ┐ ┌  ┐   ┌   ┐
│[1]  2   1 │ │ x│   │  2│
│ 0  [2] -2 │ │ y│ = │  6│
│ 0   0  [5]│ │ z│   │-10│
└           ┘ └  ┘   └   ┘

This system solved to x=2, y=1, z=-2. For a matrix with full column rank, the system can usually be solved like this.

Second Example

Consider a system with free variables:

w + 2x + 2y + 2z = 1
2w + 4x + 6y + 8z = 5
3w + 6x + 8y + 10z = 6

This system is rewritten as a linear system and eliminated into:

┌           ┐ ┌  ┐   ┌  ┐
│[1] 2  2  2│ │ w│   │ 1│
│ 0  0 [2] 4│ │ x│ = │ 3│
│ 0  0  0  0│ │ y│   │ 0│
└           ┘ │ z│   └  ┘
              └  ┘

The columns without a pivot correspond to free variables. For any set of values in the free variable positions, there is some particular solution that satisfies the system. So aim for the simplest particular solution, where every free variable is set to 0. Then solve algebraically for the pivot variables:

2y + 4z = 3
2y + 4(0) = 3
2y = 3
y = 3/2

w + 2x + 2y + 2z = 1
w + 2(0) + 2y + 2(0) = 1
w + 2y = 1
w + 2(3/2) = 1
w + 3 = 1
w = -2

w=-2, x=0, y=3/2, z=0 is a solution. There is also the unstated zero vector solution of w=0, x=0, y=0, z=0. But there are also infinitely many other solutions making use of the free variables.

Complete Solution

The complete solution is defined as x_c = x_p + x₀. That is, the null space must be solved and added to the particular solution.

The null space solutions are [-2 1 0 0] and [2 0 -1 1] for the second example above.

The null space solution is any linear combination of the null space solutions. Again, for the second example above:

       ┌    ┐     ┌    ┐
       │ -2 │     │  2 │
x  = C │  1 │ + C │  0 │
 0    1│  0 │    2│ -1 │
       │  0 │     │  1 │
       └    ┘     └    ┘

Altogether, the complete solution for the second example above is:

┌    ┐     ┌    ┐     ┌    ┐
│ -2 │     │ -2 │     │  2 │
│  0 │ + C │  1 │ + C │  0 │
│ 3/2│    1│  0 │    2│ -1 │
│  0 │     │  0 │     │  1 │
└    ┘     └    ┘     └    ┘

CategoryRicottone