System of $m$ homogeneous equations in $n$ unknowns

Question

I have to prove this:

If $m<n$, then the linear system of $m$ homogeneous equations in $n$ unknowns has a nontrivial solution.

My textbook's author proved that

Theorem. Every homogeneous system of $n$ equations in $n+1$ unknowns has a nontrivial solution.

The author proved the above using induction. I was thinking of attacking the question in a similar way.

Here's how I intend to begin the proof:

Let $m \in \mathbb{N}$ be arbitrary. Note that $m<m+k$ for every $k \in \mathbb{N}$. Then we can prove using induction on $k$ that a linear system of $m$ homogeneous equations in $(m+k)$ unknowns has a nontrivial solution. The base case follows from the theorem and I can easily prove the rest. However, is it same as proving the required?

What would be some alternative ways to prove this? (Note that this is the first chapter of my textbook and I do not have any idea about Vector Spaces and Linear Transformations).

Answer 1

You can prove it with finite-dimension theorems of vector spaces. Note that a system of homogeneous linear equations \begin{matrix} a_{11} x_1 & + & \ldots & + & a_{1n} x_n & = & 0 \\ \vdots & & \ddots & & \vdots & & \vdots \\ a_{m1} x_1 & + & \ldots & + & a_{mn} x_n & = & 0 \end{matrix} can be expressed using a linear transform $T : \mathbb{R}^n \to \mathbb{R}^m$ defined by $$T(x_1, \ldots, x_n) = (a_{11} x_1 + \ldots + a_{1n} x_n, \ldots, a_{m1}x_1 + \ldots + a_{mn} x_n).$$ In particular, the system becomes a matter of solving $T(x) = 0$ for $x \in \mathbb{R}^n$. If $n > m$, then mapping a basis of $\mathbb{R}^n$, e.g. the standard basis $(e_1, \ldots, e_n)$, will produce a list of vectors of length $n > m$ in $\mathbb{R}^m$. But, since the list is larger than the dimension, the list must be linearly dependent, in other words, there must exist $c_1,\ldots, c_n$, not all zero, such that $$c_1T(e_1) + \ldots + c_n T(e_n) = 0.$$ Since $T$ is linear, this gives us $$T(c_1, \ldots, c_n) = 0,$$ where $(c_1, \ldots, c_n) \neq (0, \ldots, 0)$.

Answer 2

An easier way to prove this is using the rank-nullity theorem:

Suppose we have a homogeneous system of $m$ equations in $n$ unknowns, with $m<n$. Then we can represent this system as $Ax=0$ where $A$ is an $(m\times n)$-matrix with $m<n$. Hence, the linear operator $T:\Bbb R^n\to\Bbb R^m$ with $T(x)=Ax$ is not injective. Indeed, by the rank-nullity theorem, we have: $$\dim(\operatorname{Im}(T))+\dim(\ker(T))=\dim(\Bbb R^n)\implies n\leq m+\dim(\ker(T))\\\implies \dim(\ker(T))\geq n-m>0$$ since $\dim(\operatorname{Im}(T))\leq m$. So the kernel of $T$ is nontrivial.