$$ \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?



1 Answer 1


$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, 2014 at 14:36

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .