3.3 The structure of the set of solutions
In this section we will study the general structure of the set of solutions to a system of linear equations, when it has solutions at all. In the next section we will then look at methods to actually solve a system of linear equations.
One often distinguishes between two types of systems of linear equations based on their constant terms.
If the system is inhomogeneous, then it doesn’t necessarily have a solution. But for the ones which have a solution we can determine the structure of the set of solutions. The key observation is that if we have one solution, say \(x_0\in \mathbb{R}^n\) which satisfies \(Ax_0=b\), then we can create further solutions by adding solutions of the corresponding homogeneous system, \(Ax=\mathbf{0}\), since if \(Ax=\mathbf{0}\) \[A(x_0+x)=Ax_0+Ax=b+\mathbf{0}=b,\] and so \(x_0+x\) is another solution to the inhomogeneous system.
Let \(A\in M_{m,n}(\mathbb{R})\) and \(b\in \mathbb{R}^m\) and assume there exists \(x_0\in \mathbb{R}^n\) with \(Ax_0=b\). Then \[S(A,b)=\{x_0\}+S(A,\mathbf{0}):=\{x_0+x: x\in S(A,\mathbf{0})\}\]
As we noticed above, if \(x\in S(A,\mathbf{0})\), then \(A(x_0+x)=b\), hence \(\{x_0\}+S(A,\mathbf{0})\subseteq S(A,b)\).
On the other hand, if \(y\in S(A,b)\) then \(A(y-x_0)=Ay-Ax_0=b-b=\mathbf{0}\), and so \(y-x_0\in S(A,\mathbf{0})\). Therefore \(S(A,b)\subseteq \{x_0\}+S(A,\mathbf{0})\) and so \(S(A,b)=\{x_0\}+S(A,\mathbf{0})\).□
Remarks:
The structure of the set of solutions is often described as follows: The general solution of the inhomogeneous system \(Ax=b\) is given by a special solution \(x_0\) to the inhomogeneous system plus a general solution to the corresponding homogeneous system \(Ax=\mathbf{0}\).
The case that there is unique solution to \(Ax=b\) corresponds to \(S(A,\mathbf{0})=\{\mathbf{0}\}\), in which case \(S(A,b)=\{x_0\}\).
At first sight the definition of the set \(\{x_0\}+ S(A,\mathbf{0})\) seems to depend on the choice of the particular solution \(x_0\) to \(Ax_0=b\). But this is not so; another choice \(y_0\) just corresponds to a different labelling of the elements of the set.
Let us look at an example of three equations with three unknowns: \[\begin{aligned} 3 x +z&= 0,\\ y-z& =1,\\ 3x+y&=1. \end{aligned}\] This set of equations corresponds to \[A=\begin{pmatrix}3 & 0 & 1\\ 0 & 1 &-1\\ 3 & 1 &0\end{pmatrix}\quad\text{and}\quad b=\begin{pmatrix}0\\1\\1\end{pmatrix}.\] To solve this set of equations we try to simplify it: if we subtract the first equation from the third the third equation becomes \(y-z=1\) which is identical to the second equation. Hence the initial system of three equations is equivalent to the following system of two equations: \[3 x +z= 0 ,\quad y-z=1 .\] In the first one we can solve for \(x\) as a function of \(z\) and in the second for \(y\) as a function of \(z\), hence \[\begin{equation} x=-\frac{1}{3}z ,\quad y=1+z. \tag{3.7}\end{equation}\] So \(z\) is arbitrary, but once \(z\) is chosen, \(x\) and \(y\) are fixed, and the set of solutions is given by \[S(A,b)=\{(-z/3,1+z,z): z\in \mathbb{R}\} .\] A similar computation for the corresponding homogeneous system of equations \[\begin{aligned} 3 x +z&= 0,\\ y-z& =0,\\ 3x+y&=0 \end{aligned}\] gives us the solutions \(x=-z/3\), \(y=z\), and \(z\in \mathbb{R}\) arbitrary, hence \[S(A,\mathbf{0})=\{(-z/3,z,z): z\in \mathbb{R}\} .\]
A particular solution to the inhomogeneous system is given by choosing \(z=0\) in (3.7), i.e., \(x_0=(0,1,0)\), and then the relation \[S(A,b)=\{x_0\}+S(A,\mathbf{0})\] can be seen directly, since for \(x=(-z/3,z,z)\in S(A,\mathbf{0})\) we have \(x_0+x=(0,1,0)+(-z/3,z,z)=(-z/3,1+z,z)\) which was the general form of an element in \(S(A,b)\). But what happens if we choose another element of \(S(A,b)\)? Let \(\lambda\in \mathbb{R}\), then \(x_{\lambda}:=(-\lambda/3,1+\lambda,\lambda)\) is in \(S(A,b)\) and we again have \[S(A,b)=\{x_{\lambda}\}+S(A,\mathbf{0}) ,\] since \(x_{\lambda}+x=(-\lambda/3,1+\lambda ,\lambda)+(-z/3,z,z)=(-(\lambda+z)/3,1+(\lambda+z),(\lambda+z))\). Then if \(z\) runs through \(\mathbb{R}\) we again obtain the whole set \(S(A,b)\), independent of which \(\lambda\) we chose initially. The choice of \(\lambda\) only determines the way in which we label the elements in \(S(A,b)\).
Finally we should notice that the set \(S(A,\mathbf{0})\) is spanned by one vector, namely we have \((-z/3,z,z)=z(-1/3,1,1)\) and hence with \(v=(-1/3,1,1)\) we have \(S(A,\mathbf{0})=\operatorname{span}\{v\}\) and \[S(A,b)=\{x_{\lambda}\}+\operatorname{span}\{v\} .\]In the next section we will develop systematic methods to solve large systems of linear equations.