# Please, help me locate the steps in this induction problem

I am having hard time locating $p(n)$, $p(1)$, $p(n + 1)$, $p(n) \to p(n + 1)$ in the proof below. Please, help me find the borders of induction steps. Thanks.

Let

$(**)$

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

$Proof:$

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_1$. 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$

Which can be written also in the form

$(***)$

$A_2 \cdot X - \frac {a_{21}}{a_{11}} A_1 \cdot X = 0$

$\vdots$

$A_m \cdot X - \frac {a_{m1}}{a_{11}} A_1 \cdot X = 0$

In this system, the coefficient of $x_1$ is equal to $0$. Hence we may view $(***)$ as a system of $m - 1$ equations in $n - 1$ unknowns, and we have $n-1 > m-1$.

According to our assumption, we can find a non-trivial solution $(x_2, ... ,x_n)$ for this system. We can then solve for $x_1$ in the first equation, namely

$x_1 = \frac {-1}{a_{11}} (a_{12}x_2 + \ldots + a_{1n}x_n)$.

In that way, we find a solution of $A_1 \cdot X = 0$. But according to $(***)$, we have

$A_i \cdot X = \frac {a_{i1}}{a_{11}} A_1 \cdot X$

for $i = 2, \ldots ,m$. Hence $A_i \cdot X = 0$ for $i = 2, \ldots ,m$, and therefore we have found a non-trivial solution to our original system $(**)$. The argument we have just given allows us to proceed stepwise from one equation to two equations, then from two to three, and so forth. This concludes the proof.

• Welcome to MathSE! You are more likely to get a good answer to your question if you follow a few guidelines in your question. In particular, what have you tried so far, and just where are you stuck? And what do you mean by "find the borders of induction steps"? – Rory Daulton Jan 1 '15 at 23:19
• In particular, is it obvious to you that the "base case" is $m=1$, i.e. the discussion of when $n \gt 1$ for a single (linear) equation with $n$ unknowns? – hardmath Jan 2 '15 at 0:41

Part of your confusion may be that here the induction is done on $m$, not $n$.
$p(m)$ is the statement that the system of equations marked (**), for $n>m$, has a non-trivial solution.
$p(1)$ is the statement that just one equation, for $n>1$, has a non-trivial solution. In other words, $m=1$. The proof of that is from the beginning of the overall proof through the sentence "In that manner, we obtain a non-trivial solution for our system of equations."
$p(m) \implies p(m + 1)$ is the rest of the proof.