Structure Theorem for the Solution Set of a Linear System

Consider the following two linear systems.

• ΣB is a nonhomogeneous linear system AX=B. Its solution set is denoted by S_B.
• ΣO is the associated homogeneous linear system AX=O. Its solution set is denoted by S_O.

Note. In matrix form, both systems have the same coefficient matrix A and the same vector of unknowns X. The only difference is the constant vector, namely B in the first system and O in the second. Since ΣO is homogeneous, its constant vector is made entirely of zeros.

In this context, two different situations may occur:

1. S_B=∅.
2. S_B=S_O+X'
   (where X' is an element of S_B).

In the second case, every solution of the nonhomogeneous system ΣB can be obtained by adding a particular solution X' to each solution of the associated homogeneous system ΣO.

A practical example

Consider the following linear system with three equations and three unknowns.

The coefficient matrix A and the augmented matrix A|B are the following:

Using Gaussian elimination, I transform the augmented matrix A|B into row echelon form.

Once the matrix is in row echelon form, the third equation becomes identically zero. This allows me to eliminate it and treat the variable x₃ as a free parameter t.

The reduced form of the augmented matrix A|B is the following:

I can now rewrite the linear system ΣB in reduced form:

This gives the solution set S_B of the system ΣB.

Next, I apply the same procedure to the associated homogeneous system ΣO.

In matrix form, the homogeneous system is written as the matrix equation AX=O.

The coefficient matrix A and the augmented matrix A|B are the following:

Again, I use Gaussian elimination to transform the augmented matrix A|B into row echelon form.

After the reduction process, the third row can be removed and the variable x₃ becomes a free parameter.

I can therefore rewrite the homogeneous system ΣO in reduced form:

This gives the solution set S_O of the homogeneous system ΣO.

According to the structure theorem, the solution set S_B is equal to the sum of the solution set S_O of the homogeneous system and a particular solution X' belonging to S_B.

Therefore, the general solution of the system is

In conclusion, the solution set S_B of the system ΣB is obtained by adding a particular solution X' to the solution set S_O of the associated homogeneous system ΣO.

Proof of the structure theorem

A proof of the structure theorem for linear systems is shown below:

Note. If the solution set S_B is empty, there is nothing to prove because no particular solution X' exists.