Homogeneous systems of linear equations

We call a system of equations homogeneous if the right-hand side of every equation is zero.

Definition of a homogeneous system

The general form of a homogeneous system of equations looks like this:

$$\begin{array}{ccccccccc}{a}_{11}{x}_1& +& a_{12}{x}_2& +& \dots & +& a_{1n}{x}_n& =& 0\\ a_{21}{x}_1& +& a_{22}{x}_2& +& \dots & +& a_{2n}{x}_n& =& 0\\ ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& ⋮& =& ⋮\\ a_{m1}{x}_1& +& a_{m2}{x}_2& +& \dots & +& a_{mn}{x}_n& =& 0\end{array}$$

This system contains m equations in n unknowns, and the right-hand sides of all the equations are zero. If they were not zero, it would not be a homogeneous system. We can rewrite the system above as a matrix by copying all the coefficients, that is, all the terms a_ij, into the same positions they have in the system. We leave out the right-hand column of zeros, because it is unnecessary. Like this:

$$A=\left(\begin{array}{cccc}{a}_{11}& a_{12}& \dots & a_{1n}\\ a_{21}& a_{22}& \dots & a_{2n}\\ ⋮& ⋮& \ddots & ⋮\\ a_{m1}& a_{m2}& \dots & a_{mn}\end{array}\right)$$

This matrix represents the system of m equations in n unknowns described above. Each row of the matrix corresponds to one equation. The whole system can then be written as

$$Ax=0$$

Basic properties of the system

From the article on systems of linear equations and from the Rouché–Capelli theorem we can get several useful statements about homogeneous systems of equations.

• Every homogeneous system has a solution.
• The set of all solutions of a homogeneous system always contains the trivial (zero) solution. If we substitute zero for all the variables, we get m equations 0 = 0.
• From the Rouché–Capelli theorem we know that writing the general solution of a system of equations requires n − k parameters, where n is the number of variables and k is the rank of the augmented matrix of the system, which in our case is k = rank(A). If n = k, we need no parameters and the system has only one solution, the trivial one. Moreover, n = k if and only if the matrix A contains no linearly dependent column (for a square matrix this means it is non-singular).
• It also follows from the previous point that the system has a non-trivial solution if and only if the matrix A contains a linearly dependent column.
• If the system has more unknowns than equations, it has a non-trivial solution. If there are more unknowns than equations, then k = rank(A) can be at most the number of equations, that is, m. And if k < n, then n − k > 0, so there will be further solutions, which we describe using n − k parameters.

Properties of the solution set

• The sum of any two solutions of the system Ax = 0 is also a solution of the system. If x₁ and x₂ are solutions of the system, then Ax₁ = 0 and Ax₂ = 0, and by the statement above A(x₁ + x₂) = 0 as well.

The proof is simple. Assume that Ax₁ = 0 and Ax₂ = 0, and we will prove A(x₁ + x₂) = 0. Addition and multiplication of matrices satisfy the distributive law, so we can write

$$A(x_1+x_2)=A{x}_1+A{x}_2.$$

By assumption, however, Ax₁ = 0 and Ax₂ = 0, so the expression Ax₁ + Ax₂ can be rewritten as 0+0. We get the equation 0 = 0, so the statement holds.

For example, if we have two solutions of a system, x₁ = (0, 5, 6) and x₂ = (7, 3, 5), then x₃ = x₁ + x₂ = (0 + 7, 5 + 3, 6 + 5) = (7, 8, 11) is also a solution of the system.

• For every constant c ∈ ℝ, c times a solution of the system is also a solution. If x₁ is a solution of the system Ax = 0, then c · x₁ is also a solution of the system.

Again the proof is simple. Assume that x₁ is a solution of the system Ax = 0 and c ∈ ℝ. We will prove that the equality

$$A(c{x}_1)=0$$

holds. Since c is a numerical constant, we can take it out as a common factor in front of the whole expression:

$$A(c{x}_1)=c\cdot A{x}_1$$

By assumption Ax₁ = 0, so from c · Ax₁ we get c · 0 = 0.

• A consequence of the previous two points is that any linear combination of solutions of the system is also a solution of that system.

Now a question arises. If some solutions are just linear combinations of other solutions, is there a set of solutions from which we can generate all the other solutions?

Let’s try writing the solutions of the system into a matrix. That is, if x₁ = (x₁₁, x₁₂, …, x_1n) is a solution, x₂ = (x₂₁, x₂₂, …, x_2n) is a solution, and so on for x_i, we create a matrix F that contains these solutions as its columns:

$$F=\left(\begin{array}{ccc}{x}_{11}& x_{21}& \dots \\ x_{12}& x_{22}& \dots \\ ⋮& ⋮& \ddots \\ x_{1n}& x_{2n}& \dots \end{array}\right)$$

Since we can form infinitely many different linear combinations, and therefore infinitely many solutions, the matrix F will be infinite. What interests us now is whether we can shrink the matrix F so that it contains only finitely many columns, from which we can generate all the other solutions.

How many columns will be left? The matrix F has n rows, because the original system had n variables and each column represents one solution. The largest possible rank of the matrix F is therefore exactly n. If the matrix F has more than n columns, at least one column is certainly linearly dependent. It follows that we can write the whole solution set into a matrix of size at most n × n and work out the other solutions using linear combinations. Any further column would certainly be redundant. The question remains whether we can reduce the size of the matrix F even further.

Fundamental set of solutions

From the Rouché–Capelli theorem we know that the general solution of the system Ax = 0 can be expressed using n − k parameters, where n is the number of variables and k = rank(A). We label the parameters t₁, t₂, …, t_{n − k}. How could we use these parameters to generate two linearly independent solutions?

In the first case we substitute 1 for the parameter t₁ and zero for the others. That is, t₁ = 1 and t₂ = t₃ = … = t_{n − k} = 0. In the second case we do the same, only moving the 1 to the second parameter: t₂ = 1 and t₁ = t₃ = t₄ = … = t_{n − k} = 0. If we substitute these parameters into the general solution, we get two different solutions that are linearly independent.

Example: let

$$(t_1,t_2,t_3,2t_1,4t_3)$$

be the general solution of some homogeneous system of equations with three parameters. For the choice of parameters t₁ = 1, t₂ = t₃ = 0 we get the particular solution x₁ = (1, 0, 0, 2, 0), for t₁ = t₃ = 0, t₂ = 1 we get x₂ = (0, 1, 0, 0, 0), and for t₁ = t₂ = 0, t₃ = 1 we get x₃ = (0, 0, 1, 0, 4). We write the particular solutions into the matrix F:

$$F=\left(\begin{array}{ccc}1& 0& 0\\ 0& 1& 0\\ 0& 0& 1\\ 2& 0& 0\\ 0& 0& 4\end{array}\right)$$

From the first three rows alone it is clear that the columns are linearly independent. We have therefore built three different particular solutions that are linearly independent of one another. At the same time, any further solution is linearly dependent on them. If we choose the parameters t₁ = 1, t₂ = 2, t₃ = 0 and work out the solution, we get x₄ = (1, 2, 0, 2, 0).

But we can also express this solution as x₁ + 2x₂ = (1, 0, 0, 2, 0) + 2(0, 1, 0, 0, 0) = (1, 2, 0, 2, 0). The same works for the other solutions. We have thus obtained a matrix with three columns that defines all the solutions of the system of equations.

The procedure can be generalised. If we have a system Ax = 0 and its general solution, which uses n − k parameters, then we can express the solutions of the system using n − k linearly independent particular solutions of the system. We call such a set of solutions a fundamental set of solutions.

We can obtain these solutions, for example, by substituting 1 for each of the parameters t₁, t₂, …, t_{n − k} in turn, with all the other parameters equal to zero. This gives n − k solutions of the system that are linearly independent.

This is not the only way to build n − k linearly independent particular solutions of the system. Instead of 1, we can substitute any non-zero number for the parameter t_i and we still get linearly independent solutions.

Once more, the definition of a fundamental set of solutions of the system Ax = 0: it is a set of particular solutions {x₁, x₂, …, x_{n − k}} such that

• x₁, x₂, …, x_{n − k} are linearly independent,
• any solution of the system Ax = 0 can be expressed as a linear combination of the particular solutions x₁, x₂, …, x_{n − k}.

Example

Solve the homogeneous system of equations and find a fundamental set of solutions:

$$\begin{array}{ccccccccc}2x_1& -& 5x_2& +& 7x_3& +& x_4& =& 0\\ 4x_1& +& 3x_2& +& x_3& & & =& 0\\ 2x_1& -& 18x_2& +& 20x_3& +& 3x_4& =& 0\\ 8x_1& -& 20x_2& +& 28x_3& +& 4x_4& =& 0\end{array}$$

The coefficient matrix A of the system has the form

$$A=\left(\begin{array}{cccc}2& -5& 7& 1\\ 4& 3& 1& 0\\ 2& -18& 20& 3\\ 8& -20& 28& 4\end{array}\right)$$

We can work out the determinant of this matrix. It is equal to zero. The matrix of the system is therefore singular and the system has a non-trivial solution. We find the general solution of the system using Gaussian elimination. The last, fourth, row is equal to the sum of the first three rows, so the whole fourth row becomes zero. Then we multiply the first row by three and the second row by minus one, and the third row will be equal to the sum of the first two rows:

$$\begin{array}{rcl}\left(\begin{array}{cccc}2& -5& 7& 1\\ 4& 3& 1& 0\\ 2& -18& 20& 3\\ 8& -20& 28& 4\end{array}\right)& \sim & \left(\begin{array}{cccc}2& -5& 7& 1\\ 4& 3& 1& 0\\ 2& -18& 20& 3\\ 0& 0& 0& 0\end{array}\right)\\ & \sim & \left(\begin{array}{cccc}6& -15& 21& 3\\ -4& -3& -1& 0\\ 2& -18& 20& 3\\ 0& 0& 0& 0\end{array}\right)\\ & \sim & \left(\begin{array}{cccc}6& -15& 21& 3\\ -4& -3& -1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\\ & \sim & \left(\begin{array}{cccc}2& -5& 7& 1\\ 4& 3& 1& 0\\ 0& 0& 0& 0\\ 0& 0& 0& 0\end{array}\right)\end{array}$$

There is no point in simplifying further. We can see that the matrix has rank two, rank(A) = 2. To write the general solution of the system we need two parameters, which we call s and t. To write the fundamental set of solutions we need two particular solutions.

We have now arrived at this system of equations:

$$\begin{array}{ccccccccc}2x_1& -& 5x_2& +& 7x_3& +& x_4& =& 0\\ 4x_1& +& 3x_2& +& x_3& & & =& 0\end{array}$$

From the second equation we make x₃ the subject.

$$x_3=-4x_1-3x_2$$

We substitute parameters for x₁ and x₂, so s = x₁ and t = x₂. Then we can write x₃ = −4s − 3t. It remains to work out x₄. We find it from the first equation:

$$\begin{array}{rcl}{x}_4& =& -2s+5t-7(-4s-3t)\\ x_4& =& -2s+5t+28s+21t\\ x_4& =& 26s+26t\\ x_4& =& 26(s+t)\end{array}$$

The general solution is therefore (s, t, −4s − 3t, 26(s + t)). To obtain a fundamental set of solutions, we must find two particular solutions (that is, two specific solutions) that are linearly independent. We find them by substituting first s = 1, t = 0 and then s = 0, t = 1 for the parameters. For the first pair of parameters we have the particular solution

$$X_1=(x_1,x_2,x_3,x_4)=(1,0,-4,26)$$

and for the second pair

$$X_2=(x_1,x_2,x_3,x_4)=(0,1,-3,26).$$

These solutions are linearly independent. Since we used two parameters in the general solution, two particular solutions are enough to form the fundamental set. The fundamental set of solutions therefore looks like this

$$\{(1,0,-4,26),(0,1,-3,26)\}.$$

We can also check that these two solutions are valid by substituting them into the original equations. For X₁ we get these equations:

$$\begin{array}{ccccccccc}2\cdot 1& -& 5\cdot 0& +& 7\cdot (-4)& +& 26& =& 0\\ 4\cdot 1& +& 3\cdot 0& -& 4& & & =& 0\\ 2\cdot 1& -& 18\cdot 0& +& 20\cdot (-4)& +& 3\cdot 26& =& 0\\ 8\cdot 1& -& 20\cdot 0& +& 28\cdot (-4)& +& 4\cdot 26& =& 0\end{array}$$

After simplifying we have:

$$\begin{array}{rcl}2-28+26& =& 0\\ 4-4& =& 0\\ 2-80+78& =& 0\\ 8-112+104& =& 0\end{array}$$

We can see that every equation comes out as 0 = 0. It seems we have worked it out correctly.