Solution Spaces to Systems of Linear Equations

We will now begin to look more in-depth into solution spaces for both homogenous and nonhomogenous linear systems of $m$ equations and $n$ unknowns.

Consider the following transformation $T : \mathbb{F}^{n} \to \mathbb{F}^{m}$ defined by:

(1)

\begin{align} \quad T((x_1, x_2, ..., x_n)) = \left ( \sum_{k=1}^{n} a_{1,k}x_k, \sum_{k=1}^{n} a_{2,k}x_k, ..., \sum_{k=1}^{n} a_{m,k}x_k \right ) \end{align}

Homogenous Linear Systems

Suppose that the equation $T((x_1, x_2, ..., x_n)) = \underbrace{(0, 0, ..., 0)}_{\mathrm{m-times}}$. We can thus write this equation as a system of linear equations given as:

(2)

\begin{align} \sum_{k=1}^{n} a_{1,k}x_k = a_{1,1}x_1 + a_{1,2}x_2 + ... + a_{1,n}x_n = 0 \\ \sum_{k=1}^{n} a_{2,k}x_k = a_{2,1}x_1 + a_{2,2}x_2 + ... + a_{2,n}x_n = 0\\ \vdots \quad \quad \quad \quad\quad \quad\quad \quad \\ \sum_{k=1}^{n} a_{m,k}x_k = a_{m,1}x_1 + a_{m,2}x_2 + ... + a_{m,n}x_n = 0\\ \end{align}

Of course, this homogenous system of linear equations can be represented in matrix form as $\begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} = \begin{bmatrix} 0\\ 0\\ \vdots \\ 0\end{bmatrix}$

In earlier linear algebra pages, we noted that a homogenous system always has a solution, namely the trivial solution $(x_1, x_2, ..., x_n) = (0, 0, ..., 0)$, however, we were more interested in determining whether nontrivial solutions exist. We can easily answer this question in terms of linear transformations.

Theorem 1: A homogenous linear system of $m$ equations of $n$ unknowns has nontrivial solutions if $n > m$.

• Proof: Let $T \in \mathcal L (\mathbb{F}^{n}, \mathbb{F}^{m})$ be defined by $T((x_1, x_2, ..., x_n)) = \left ( \sum_{k=1}^{n} a_{1,k}x_k, \sum_{k=1}^{n} a_{2,k}x_k, ..., \sum_{k=1}^{n} a_{m,k}x_k \right )$. If $n > m$, then by Corollary 2 of The Dimension of The Null Space and Range page, we have that $T$ is not injective, and therefore $\mathrm{null} (T) \neq \{0\}$ and so there exists another vector $(x_1, x_2, ..., x_n) \in \mathbb{F}^{n}$ such that $T((x_1, x_2, ..., x_n)) = 0$ where not all $x_j$, $1 ≤ j ≤ n$ are zero, and so the system of linear equations has a nontrivial solution. $\blacksquare$

Nonhomogenous Linear Systems

Now consider the equation $T((x_1, x_2, ..., x_n)) = \underbrace{(b_1, b_2, ..., b_m)}_{\mathrm{m-times}}$ where not all $b_j$, $1 ≤ j ≤ n$ are zero. We can thus write this equation is a system of linear equations given as:

(3)

\begin{align} \sum_{k=1}^{n} a_{1,k}x_k = a_{1,1}x_1 + a_{1,2}x_2 + ... + a_{1,n}x_n = b_1 \\ \sum_{k=1}^{n} a_{2,k}x_k = a_{2,1}x_1 + a_{2,2}x_2 + ... + a_{2,n}x_n = b_2\\ \vdots \quad \quad \quad \quad\quad \quad\quad \quad \\ \sum_{k=1}^{n} a_{m,k}x_k = a_{m,1}x_1 + a_{m,2}x_2 + ... + a_{m,n}x_n = b_m\\ \end{align}

Similarly, we can write this nonhomogenous system of linear equations in matrix form as $\begin{bmatrix} a_{1,1} & a_{1,2} & \cdots & a_{1,n}\\ a_{2,1} & a_{2,2} & \cdots & a_{2,n}\\ \vdots & \vdots & \ddots & \vdots \\ a_{m,1} & a_{m,2} & \cdots & a_{m,n} \end{bmatrix} \begin{bmatrix} x_1\\ x_2\\ \vdots\\ x_n \end{bmatrix} = \begin{bmatrix} b_1\\ b_2\\ \vdots\\ b_m\end{bmatrix}$.

In such a case, we're not always guaranteed a solution as with homogenous linear systems. The question then becomes if a solution $(x_1, x_2, ..., x_n)$ always exists for any choice of a vector $(b_1, b_2, ..., b_m)$. The answer is not necessarily as summarized in the following theorem.

Theorem 2: There exists a vector $(b_1, b_2, ..., b_m)$ for which there is no solution $(x_1, x_2, ..., x_n)$ to the system of nonhomogenous linear equations of $m$ equations and $n$ unknowns if $n < m$.

• Proof: Let $T \in \mathcal L (\mathbb{F}^{n}, \mathbb{F}^{m})$ be defined by $T((x_1, x_2, ..., x_n)) = \left ( \sum_{k=1}^{n} a_{1,k}x_k, \sum_{k=1}^{n} a_{2,k}x_k, ..., \sum_{k=1}^{n} a_{m,k}x_k \right )$. If $n < m$, then by Corollary 3 The Dimension of The Null Space and Range page, we have that $T$ is not surjective, and so $\mathrm{range} (T) \neq \mathbb{F}^{m}$. Therefore, there exists a vector $(b_1, b_2, ..., b_n) \in \mathbb{F}^{m}$ such that no vector $(x_1, x_2, ..., x_n) \in \mathbb{F}^{n}$ maps to it, in other words, the nonhomogenous linear system $T((x_1, x_2, ..., x_n)) = (b_1, b_2, ..., b_m)$ has no solution. $\blacksquare$