$$ \begin{matrix} a_{11}x_1 & + & \ldots & + & a_{1n}x_n & = 0 \\ \vdots & & & & \vdots\\ a_{m1}x_1 & + & \ldots & + & a_{mn}x_n & = 0 \\ \end{matrix} $$

be a system of $m$ linear equations in $n$ unknowns, and assume that $n > m$. Then the system has a non-trivial solution.


Consider first the case of one equation in $n$ unknowns, $n > 1$:

$a_{1}x_1 + \ldots + a_{n}x_n = 0$

If all coefficients $a_1, \ldots, a_n$ are equal to $0$, then any value of the variables will be a solution, and a non-trivial solution certainly exists. Suppose that some coefficient $a_i \neq 0$. After renumbering the variables and the coefficients, we may assume that it is $a_i$ Then we give $x_2, \ldots, x_n$ arbitrary values, for instance we let $x_2, \ldots, x_n = 1$ and solve for $x_1$ letting

$x_1 = \frac {-1}{a_1} (a_2 + \ldots + a_n)$

In that manner, we obtain a non-trivial solution for our system of equations. Let us now assume that our theorem is true for a system of $m - 1$ equations in more than $m - 1$ unknowns. We shall prove that it is true for $m$ equations in $n$ unknowns when $n > m$. We consider the system $(**)$.

If all coefficients $(a_{ij})$ are equal to $0$, we can give any non-zero value to our variables to get a solution. If some coefficient is not equal to $0$, then after renumbering the equations and the variables, we may assume that it is $a_{11}$. We shall subtract a multiple of the first equation from the others to eliminate $x_1$. Namely, we consider the system of equations

$ (A_2 - \frac {a_{21}}{a_{11}} A_1) \cdot X $

$ (A_m - \frac {a_{m1}}{a_{11}} A_1) \cdot X $


We shall subtract a multiple of the first equation from the others to eliminate $x_1$.

Can you, please, explain why?

$ (A_2 - \frac {a_{21}}{a_{11}} A_1) \cdot X $

How did they come up with the part inside parenthesis?



$A_2$ is the row vector of coefficients for the second equation. It's first entry is "$a_{21}$". So the second equation looks like $a_{21}x_1+\cdots=0$.

Notice that the first equation looks like $a_{11}x_1+\cdots=0$. If we wish to eliminate the variable $x_1$ from the second equation, we can do so by subtracting the appropriate multiple of the first equation.

Specifically: $\dfrac{a_{21}}{a_{11}}\left(a_{11}x_1+\cdots\right)=0$ which is $a_{21}x_1+\cdots=0$. When this is subtracted from the second equation, the resulting equation will no longer have an "$x_1$".

So $A_2 - \dfrac{a_{21}}{a_{11}}A_1$ has zero as its leading entry.

  • $\begingroup$ Oh, I see. Thank you very much. $\endgroup$ – Tacoma Apr 7 '14 at 14:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.