System of homogeneous linear equations with coefficients in a field

Question

In the book I started to read, at almost the very beginning it is stated (without proof):

If $m<n$ and we have a system $$a_{11}x_1+...+a_{1n}x_n=0$$

$$\vdots$$

$$a_{m1}x_1+...+a_{mn}x_n=0$$

of homogeneous linear equations, with coefficients in a field, then there is a non-trivial solution in the field.

So, I have some questions about this:

Where a proof can be found? Does this also holds for finite fields (or it is implicitly assumed that we talk about infinite fields)? Is this just an application of matrix algebra (that is, this matrix of coefficients will always have an inverse if $m<n$?

Answer 1

This is true over any field, and is just basic linear algebra. Let $F$ be the field in question, and let $T:F^n\to F^m$ be the linear map given by the matrix $(a_{ij})$. Since $n>m$, the dimension of the domain of $T$ is greater than the dimension of the codomain, so $T$ cannot be injective (if you like, by the rank-nullity theorem, the nullity of $T$ is at least $n-m$ since the rank of $T$ is at most $m$). So the kernel of $T$ is nontrivial, which means exactly that there is some $(x_1,\dots,x_n)$, not all $0$, which is a solution to your system of equations.

Answer 2

If $A$ is the matrix of this system of equations, note that $L_A:x\mapsto Ax$, where $x$ is a column-matrix, is a linear map of $F^n$ to $F^m$. Thus, by rank-nullity theorem, $n=\dim\ker L_A+\dim L_A(F^n)$. Because $L_A(F^n)\lt F^m$, we have $\dim L_A(F^n)\le m$, so $\dim\ker L_A=n-\dim L_A(F^n)\ge n-m\ge 1$ as $n\gt m$. Now this means that $\ker L_A$ is nontrivial (being of dimension $\ge 1$), therefore there is $x\ne 0$ such that $Ax=0$, in other words the system of equations has a non-trivial solution.

Answer 3

If $a_{1n}=a_{2n}=\dots=a_{mn}=0$, you get a nontrivial solution by choosing $$ x_1=x_2=\dots=x_{n-1}=0,\quad x_n=1. $$ Suppose now one of the coefficients of $x_n$ is nonzero. Without loss of generality, we can assume $a_{mn}\ne0$ (otherwise we just reorder the equations) and now we can also assume $a_{mn}=1$ (by multiplying the first equation by $a_{mn}^{-1}$).

Now do the following operations: sum to the $i$-th equation (for $1\le i<m$) the last equation multiplied by $-a_{in}$. These operations don't change the solution set of the system. After performing these transformations, your system becomes $$ \begin{cases} \begin{array}{rcrcrcrccc} b_{11}x_1&+&b_{12}x_2&+&\dots&+&b_{1,n-1}x_{n-1}&&&=&0 \\ b_{21}x_1&+&b_{22}x_2&+&\dots&+&b_{2,n-1}x_{n-1}&&&=&0 \\ &\vdots \\ b_{m-1,1}x_1&+&b_{m-1,2}x_2&+&\dots&+&b_{m-1,n-1}x_{n-1}&&&=&0\\ a_{m1}x_1&+&a_{m2}x_2&+&\dots&+&a_{m,n-1}x_{n-1}&+&x_n&=&0 \end{array} \end{cases} $$ for suitable coefficients $b_{ij}$. The linear system has a nontrivial solution by induction hypothesis; once we find it, we can substitute the values in the last equation and get the value for $x_n$.

The base step for the induction, $m=1$, should be clear.

This is essentially Gaussian elimination starting from the last column. The assumption that $m<n$ is decisive, because we can safely isolate $x_n$ and still get equations after the elimination step.

Answer 4

To start, your last sentence is not correct in that if a matrix has an inverse it will only have the trivial solution to the homogenous system. Also, an invertable matrix must be square.

The result itself follows from the fact that the system is underdetermined and will have multiple solutions (proof via Gaussian algorithm). You could also likely view it from a linear dependence argument.

Any introductory linear algebra text should show this result (you could just replace the real numbers with an arbitrary field). Lay's Linear Algebra is a good one.