# Proof that there must exist infinitely many solutions to a homogeneous system of equations when more unknowns than equations

Consider the system of simultaneous linear equations

\begin{align} a_{11} &x_1 &&\; + \;&& a_{12} x_2 &&\; + \cdots + \;&& a_{1n} x_n &&\; = \;&&& 0 \\ a_{21} &x_1 &&\; + \;&& a_{22} x_2 &&\; + \cdots + \;&& a_{2n} x_n &&\; = \;&&& 0 \\ \vdots\;&\; && && \;\;\;\vdots\;\;\; && && \;\;\;\vdots\;\;\; && &&& \vdots \\ a_{m1} &x_1 &&\; + \;&& a_{m2} x_2 &&\; + \cdots + \;&& a_{mn} x_n &&\; = \;&&& 0 \\ \end{align}

for constants $a_{ij}$ and unknowns $x_j$ , in the case where $m < n$ prove that there must exist infinitely many solutions to this system of equations.

Okay, so it's pretty easy to prove that this set of equations must have solutions because we have m equations and n values, we x_1=x_n=0 is our trivial solution and if we have more than this one solution, then out null space will be greater than {0} which implies we don't have an injective set of equations. As m is less than n we know the system is not injective, which tells us there must be non-zero solutions. But I want to show these solutions are infinite which means for x_n solutions, the solution should include a parameter. How can I go about this?

• If you set any variable to a specific real number and this becomes a system of equations with n-1 variables. This is true for any real number so there a solutions in which that variable is any number. Those are an infinite number of solutions. – fleablood Aug 18 '16 at 5:25

You can view it as a case of the rank-nullity theorem. Suppose $n \gt m$ and let $A$ denote the $m \times n$ matrix whose entries are $a_{i,j}$. We are considering whether $T:\Bbb R^n \to \Bbb R^m$ defined by $T(x) = Ax = 0$ always has solutions $x \in \Bbb R^n$. By rank-nullity,

\begin{align} \operatorname{rank} T + \operatorname{nullity} T &= \dim \Bbb R^n = n \end{align}

Since $m \lt n$, $\operatorname{rank} T < n$, so $\operatorname{nullity}T \gt 0$. In other words, there exists $k \leq n - m \in \Bbb Z^+$ such that $\ker T = \operatorname{span}(x_1, \ldots, x_k)$. It should be pretty clear now that $Ax = 0$ has infinitely many solutions.

• By the way, it should be $r(T) + n(T) = m$, and not $n$. – onurcanbektas Nov 1 '17 at 14:59
• @onurcanbektas rank-nullity tells us that the rank plus the nullity adds up to the dimension of the domain, so it’s correct as written. – Alex Ortiz Nov 1 '17 at 15:08
• Dimension of the domain is $m$ not $n$, check out the matrix given in the question. – onurcanbektas Nov 1 '17 at 15:10
• @onurcanbektas The fact that the “unknown” vector $x$ has $n$ components tells us that the domain is $\Bbb R^n$. – Alex Ortiz Nov 1 '17 at 15:13
• Apparently, I'm using the opposite convention compared to you, sorry my mistake. – onurcanbektas Nov 1 '17 at 15:16

(I'm assuming that you're excluding the case of degenerate systems where some equations are linear combinations of others.)

You can first bring the system into a row-echelon form:

\begin{align} x_1 &&\; + \;&& b_{1,2} x_2 &&\; + \cdots + \;&& b_{1,n} x_{n-1} &&\; + \;&& b_{1,n} x_{n} &&\; = \;&&& 0 \\ 0 &&\; + \;&& x_2 &&\; + \cdots + \;&& b_{2,n-1} x_{n-1} &&\; + \;&& b_{1,n} x_{n} &&\; = \;&&& 0 \\ \vdots\;&\; && &\vdots\;\;\; && && \;\vdots\;\;\; && &&& \vdots \\ 0 &&\; + \;&& 0 &&\; + \cdots + \;&& a_{m,n-1} x_{n-1} &&\; + \;&& b_{1,n} x_{n} &&\; = \;&&& 0 \\ \end{align}

Then your $m-n$ parameters can be chosen to be any combination of the $x$'s in the last equation, solving for the remaining $x$ and getting the rest by back-substitution.

(To be specific in the more general case that row-echelon forms may have more than $k-1$ leading zeroes in the $k$th equation: do a column exchange, so that this doesn't happen and you get $n-m+1$ non-zero coefficients in the last equations.)

EDIT: corrected $k-1$ from $k+1$ and $n-m+1$ from $m-n+1$

• thanks for your help!To clarify does the general case form of k+1 leading zeroes terms in our kth equation mean that our kth equation consists of all 0's or does it mean we have that one of our values is equal to 0? Also i'm a little confused as to which column exchange would get me m-n+1 non-zero coefficients in the last equations. – Kierra Aug 18 '16 at 10:17
• Sorry, that was a typo: $k+1$ should have been $k-1$, e.g. the 1st equation should have no leading zeroes, 2nd should have 1, ..., $m$th(last) should have $m-1$, and with $n$ variables that means you should have $n-m+1$ (which is another typo in the signs of $n$ and $m$ I had). '$k-1$ leading zeroes' means that the coefficients of $x_1,x_2,...,x_{k-1}$ are all zero. A column exchange (essentially swapping variable names) with any other column to the right (that has a non-zero coefficient) would work in the case when your $k$th coefficient in the $k$th equation is zero. – Ken Wei Aug 19 '16 at 4:16