§ 17. Systems of Linear Equations - Theoretical Aspects¶
Definition of Systems of Linear Equations¶
Definition 17.1 : System of Linear Equations and Solution Set
The system of equations
where \(a_{i j}\) and \(b_{i}(1 \leq i \leq m\) and \(1 \leq j \leq n)\) are scalars in a field \(F\) and \(x_{1}, x_{2}, \ldots, x_{n}\) are \(n\) variables taking values in \(F\), is called a system of \(m\) linear equations in \(n\) unknowns over the field \(F\).
The \(m \times n\) matrix
is called the coefficient matrix of the system \((S)\).
If we let
then the system \((S)\) may be rewritten as a single matrix equation
To exploit the results that we have developed, we often consider a system of linear equations as a single matrix equation.
The matrix \((A \mid b)\) is called the augmented matrix of the system \(A x=b\).
A solution to the system \((S)\) is an \(n\)-tuple
such that \(A s=b\). The set of all solutions to the system \((S)\) is called the solution set of the system. System \((S)\) is called consistent if its solution set is nonempty; otherwise it is called inconsistent.
Definition 17.2 : Homogeneous and Nonhomogeneous Systems
A system \(A x=b\) of \(m\) linear equations in \(n\) unknowns is said to be homogeneous if \(b=0\). Otherwise the system is said to be nonhomogeneous.
We refer to the equation \(A x=0\) as the homogeneous system corresponding to \(A x=b\).
Solution of Systems of Linear Equations¶
Theorem 17.3 : Solution set of a homogeneous system
Let \(A x=0\) be a homogeneous system of \(m\) linear equations in \(n\) unknowns over a field \(F\). Let \(K\) denote the set of all solutions to \(A x=0\). Then \(K=N\left(L_{A}\right)\); hence \(K\) is a subspace of \(F^{n}\) of dimension \(n-\operatorname{rank}\left(L_{A}\right)=n-\operatorname{rank}(A)\).
Proof
Clearly, \(K=\left\{s \in F^{n}: A s=0\right\}=N\left(L_{A}\right)\). The second part now follows from Theorem 8.13.
Corollary 17.4 : A homogeneous system has a nonzero solution when \(m<n\).
If \(m<n\), the system \(A x=0\) has a nonzero solution.
Proof
Proof. Suppose that \(m<n\). Then \(\operatorname{rank}(A)=\operatorname{rank}\left(L_{A}\right) \leq m\). Hence
where \(K=N\left(L_{A}\right)\). Since \(\operatorname{dim}(K)>0, K \neq\{0\}\). Thus there exists a nonzero vector \(s \in K\); so \(s\) is a nonzero solution to \(A x=0\).
Theorem 17.5 : Solution set of a nonhomogeneous system
Let \(K\) be the solution set of a system of linear equations \(A x=b\), and let \(K_{H}\) be the solution set of the corresponding homogeneous system \(A x=0\). Then for any solution \(s\) to \(A x=b\)
Proof
Let \(s\) be any solution to \(A x=b\). We must show that \(K=\{s\}+K_{H}\). If \(w \in K\), then \(A w=b\). Hence
So \(w-s \in K_{H}\). Thus there exists \(k \in K_{H}\) such that \(w-s=k\). It follows that \(w=s+k \in\{s\}+K_{H}\), and therefore
Conversely, suppose that \(w \in\{s\}+K_{H}\); then \(w=s+k\) for some \(k \in K_{H}\). But then \(A w=A(s+k)=A s+A k=b+0=b\); so \(w \in K\). Therefore \(\{s\}+K_{H} \subseteq K\), and thus \(K=\{s\}+K_{H}\).
Theorem 17.6 : Unique solution and invertibility
Let \(A x=b\) be a system of \(n\) linear equations in \(n\) unknowns. If \(A\) is invertible, then the system has exactly one solution, namely, \(A^{-1} b\). Conversely, if the system has exactly one solution, then \(A\) is invertible.
Proof
Suppose that \(A\) is invertible. Substituting \(A^{-1} b\) into the system, we have \(A\left(A^{-1} b\right)=\left(A A^{-1}\right) b=b\). Thus \(A^{-1} b\) is a solution. If \(s\) is an arbitrary solution, then \(A s=b\). Multiplying both sides by \(A^{-1}\) gives \(s=A^{-1} b\). Thus the system has one and only one solution, namely, \(A^{-1} b\).
Conversely, suppose that the system has exactly one solution \(s\). Let \(K_{H}\) denote the solution set for the corresponding homogeneous system \(A x=0\). By Theorem 17.5, \(\{s\}=\{s\}+K_{H}\). But this is so only if \(K_{H}=\{0\}\). Thus \(N\left(L_{A}\right)=\{0\}\), and hence \(A\) is invertible.
Theorem 17.7 : Consistency and Rank of the Augmented Matrix
Let \(A x=b\) be a system of linear equations. Then the system is consistent if and only if \(\operatorname{rank}(A)=\operatorname{rank}(A \mid b)\).
Proof
We first justify the claim that \(A x=b\) has a solution if and only if \(b \in R\left(L_{A}\right)\).
Let \(A\) be an \(m \times n\) matrix and define \(L_{A}:F^{n}\to F^{m}\) by \(L_{A}(x)=Ax\). The system \(A x=b\) is consistent precisely when there exists some \(x\in F^{n}\) such that \(Ax=b\), that is, such that \(L_{A}(x)=b\). This holds if and only if \(b\) lies in the range of \(L_{A}\), i.e., \(b\in R(L_{A})\).
In the proof of Theorem 16.6, we saw that
the span of the columns of \(A\). Thus \(A x=b\) has a solution if and only if \(b \in \operatorname{span}\left(\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\right)\). But \(b \in \operatorname{span}\left(\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\right)\) if and only if \(\operatorname{span}\left(\left\{a_{1}, a_{2}, \ldots, a_{n}\right\}\right)=\operatorname{span}\left(\left\{a_{1}, a_{2}, \ldots, a_{n}, b\right\}\right)\). This last statement is equivalent to
So by Theorem 16.6, the preceding equation reduces to
Example 17.8 : Example of testing whether a vector is in range of a linear transformation
We can use Theorem 17.7 to determine whether \((3,3,2)\) is in the range of the linear transformation \(T: R^{3} \rightarrow R^{3}\) defined by
Now \((3,3,2) \in R(T)\) if and only if there exists a vector \(s=\left(x_{1}, x_{2}, x_{3}\right)\) in \(R^{3}\) such that \(T(s)=(3,3,2)\). Such a vector \(s\) must be a solution to the system
Since the ranks of the coefficient matrix and the augmented matrix of this system are 2 and 3, respectively, it follows that this system has no solutions. Hence \((3,3,2) \notin R(T)\).
Exercise¶
Exercise 17.10
Prove or give a counterexample to the following statement: If the coefficient matrix of a system of \(m\) linear equations in \(n\) unknowns has rank \(m\), then the system has a solution.