Homogeneous System of Linear Equations

We saw that:

• a linear map to lower-dimensional space is not injective
• a linear map to higher-dimensional space is not surjective

These have important consequences in the theory of linear equations. The idea is to express about systems of linear equations in terms of linear maps. Let’s begin by rephrasing in terms of linear maps the questions of whether a homogeneous system of linear equations has a nonzero solution.

Fix positive integers $m$ and $n$, and let $A_{j,k}\in \mathbb{F}$ for $j=1,\dots ,m$ and $k=1,\dots ,n$. Consider the homogenous systems of linear equations (homogenous means constant term on right side is $0$):

$$\begin{array}{rl}\sum _{k=1}^n{A}_{1,k}{x}_k& =0\\ & ⋮\\ \sum _{k=1}^n{A}_{m,k}{x}_k& =0\end{array}$$

Essentially, $j$ denotes the row, $k$ denotes the column:

$$\begin{array}{rl}{A}_{1,1}{x}_1+A_{1,2}{x}_2+& \cdots +A_{1,n}{x}_n=0\\ A_{2,1}{x}_1+A_{2,2}{x}_2+& \cdots +A_{2,n}{x}_n=0\\ & \dots \\ A_{m,1}{x}_1+A_{m,2}{x}_2+& \cdots +A_{m,n}{x}_n=0\end{array}$$

Clearly, $x_1=\cdots =x_n=0$ is a solution of the system of equations above. The questions here is whether any other solutions exist.

Define $T:{\mathbb{F}}^n\to {\mathbb{F}}^m$ by

$$T(x_1,\dots ,x_n)=\left(\sum _{k=1}^n{A}_{1,k}{x}_k,,\dots ,\sum _{k=1}^n{A}_{m,k}{x}_k\right)$$

The equation $T(x_1,\dots ,x_n)=0$ is the same as the homogeneous system of linear equations above.

• Here, $0$ is the additive identity in ${\mathbb{F}}^m$, namely, the list of length $m$ of all $0$‘s.

Thus, we want to know if $\text{null }T$ is strictly bigger than $\{0\}$, which is equivalent to $T$ not being injective (injectivity implies null space is 0 and vice versa).

This next result gives an important condition for ensuring that $T$ is not injective.

Non-Zero Solutions

Solutions for homogeneous system of linear equations

A homogeneous system of linear equations with more variables than equations has nonzero solutions.

Proof. Use the notation and result from the discussion above. Thus $T$ is a linear map from ${\mathbb{F}}^n$ to ${\mathbb{F}}^m$, and we have a homogeneous system of $m$ linear equations with $n$ variables $x_1,\dots ,x_n$. We know that $T$ is not injective if $n>m$ (linear map to lower-dimensional space is not injective). $■$

An example of the result above is that a homogeneous system of four linear equations with five variables has nonzero solutions.

No Solutions

Is there a system of linear equations for some choice of constant terms?

To rephrase this in terms of a constant map, fix positive integers $m$ and $n$, and let $A_{j,k}\in \mathbb{F}$ for all $j=1,\dots ,m$ and all $k=1,\dots ,n$. For $c_1,\dots ,c_m\in \mathbb{F}$, consider the system of linear equations

$$\begin{array}{rl}\sum _{k=1}^n{A}_{1,k}{x}_k& =c_1\\ & ⋮\\ \sum _{k=1}^n{A}_{m,k}{x}_k& =c_m\end{array}$$

With this notation, the question here is whether there is some choice of the constants terms $c_1,\dots ,c_m\in \mathbb{F}$ such that no solution exists to the system above.

Define $T:{\mathbb{F}}^n\to {\mathbb{F}}^m$ the same way we did previously:

$$T(x_1,\dots ,x_n)=\left(\sum _{k=1}^n{A}_{1,k}{x}_k,,\dots ,\sum _{k=1}^n{A}_{m,k}{x}_k\right)$$

The equation $T(x_1,\dots ,x_n)=(c_1,\dots ,c_m)$ is the same as the system of equations as we have here.

Thus, we want to know if $\text{range }T\ne {\mathbb{F}}^m$. Hence, we can rephrase our question about not having a solution for some choice of $c_1,\dots ,c_m\in \mathbb{F}$ as follows: What condition ensures that $T$ is not surjective?

The next result gives one such condition:

Systems of linear equations with more equations than variables

A system of linear equations with more equations than variables has no solution for some choice of linear terms.

Proof. Use the notation from the discussion above. Thus, $T$ is a linear map from ${\mathbb{F}}^n$ to ${\mathbb{F}}^m$, and we have a system of $m$ equations with $n$ variables $x_1,\dots ,x_n$. If $n<m$, then $T$ is not surjective (linear map to higher-dimensional space is not surjective). As discussed above, this shows that if we have more equations than variables in a system of linear equations, then there is no solution for some choice of the constant terms. $■$

Example: A system of 5 linear equations with 4 variables has no solution for some choice of constant terms.