2
$\begingroup$

I just started going through Jim Hefferon's book on Linear Algebra, and I'm having trouble with one of the proofs. I understand its overall structure but some of the indexing in the proof seems off by 1. Below is his proof with my proposed corrections in bold in brackets. This seems so simple, just not sure what I'm missing here.


Lemma: For any homogeneous linear system there exist vectors $\beta_1, . . . , \beta_k$ such that the solution set of the system is $\{ c_1 \beta_1 + ... + c_k \beta _k | c_1,...,c_k \in \mathbb{R} \}$ where k is the number of free variables in an echelon form version of the system.

Proof: Apply Gauss’s Method to get to echelon form. There may be some 0 = 0 equations; we ignore these (if the system consists only of 0 = 0 equations then the lemma is trivially true because there are no leading variables). But because the system is homogeneous there are no contradictory equations.

We will use induction to verify that each leading variable can be expressed in terms of free variables. That will finish the proof because we can use the free variables as parameters and the $\beta$ ’s are the vectors of coefficients of those free variables.

For the base step consider the bottom-most equation $a_{m,l_m} x_{l_m} + a_{m,l_{m+1}} x_{l_{m+1}} + ... + a_{m,n} x_n = 0 $ where $a_{m,l_m} \neq 0$. This is the bottom row so any variables after the leading one must be free. Move these to the right hand side and divide by $a_{m,l_m}$

$x_{l_m} = (-a_{m,l_{m+1}}/a_{m,l_m}) x_{l_{m+1}} + ... + (-a_{m,n}/a_{m,l_m})x_n$

to express the leading variable in terms of free variables.

For the inductive step assume that the statement holds for the bottom-most t rows, with $0 \leq t < m- 1$ [0 < t $\leq$ m- 1]. That is, assume that for the m-th equation, and the (m- 1)-th equation, etc., up to and including the (m- t)-th [(m-t+1)-th] equation, we can express the leading variable in terms of free ones. We must verify that this then also holds for the next equation up, the (m - (t + 1))-th [(m-t)-th] equation. For that, take each variable that leads in a lower equation $x_{l_m}, . . . , x_{l_{m-t}}$ [$...x_{l_{m-t+1}}$] and substitute its expression in terms of free variables. We only need expressions for leading variables from lower equations because the system is in echelon form, so the leading variables in equations above this one do not appear in this equation. The result has a leading term of $a_{m-(t+1),l_{m-(t+1)}} x_{m-(t+1)}$ with $a_{m-(t+1),l_{m-(t+1)}} \neq 0$, and the rest of the left hand side is a linear combination of free variables. Move the free variables to the right side and divide by $a_{m-(t+1),l_{m-(t+1)}}$ to end with this equation’s leading variable $x_{l_{m-(t+1)}}$ in terms of free variables.

We have done both the base step and the inductive step so by the principle of mathematical induction the proposition is true. QED

Edit: For example, if m = 10 and t = 2, it means that we have parameterized the bottom 2 rows of a 10-row matrix in terms of the free variables. His proof seems to say that the 8th through the 10th rows (m-t) have been completed, whereas my thinking is that only the 9th and 10th (m-t+1) have been completed and we are now going to use induction on the 8th.

$\endgroup$
  • $\begingroup$ and trouble in your question $\endgroup$ – zeraoulia rafik Jul 13 '15 at 17:17
  • $\begingroup$ This is my first question, sorry if it is confusing. I added an example at the end to try to clarify. $\endgroup$ – GreenCheck Jul 13 '15 at 18:18
0
$\begingroup$

I don't see what the issue is... You want to find the solution to $$ Ax = 0 $$ where $A$ is a $m \times n$ matrix. If you look at the last row you'll have (assuming $a_{m1}\neq 0$ without the loss of generality) $$ a_{m1} x_1 + a_{m2} x_2 +\ldots + a_{mn} x_n = 0 \implies x_1 = - \frac{a_{m2} x_2 + \ldots +a_{mn} x_n}{a_{m1}}$$ Repeat this process for the $m-1$ remaining rows...Thus you'll have $n-m=k$ free variables at the end. These will form a basis for the solution space... which proves the claim.

$\endgroup$
  • $\begingroup$ Thanks for the response, Jeb. I understand the approach, what has me confused is the description of rows in the induction part. For example, he says that if the statement holds for the bottom t rows that means it holds for the m-th through the (m-t)-th, whereas to me it seems to mean only that it holds for the m-th through the (m-t+1)-th. For example the bottom t=2 rows of a m=10-row matrix corresponds to the 9th (m-t+1) and 10th, not the 8th (m-t) through the 10th. $\endgroup$ – GreenCheck Jul 13 '15 at 20:33
  • $\begingroup$ It'll hold for every row... if $n-m\leq0$, the statement fails since the induction doesn't apply. If $n-m = k >0$ you'll be able to do this with every row. I suggest writing it our for a $2 \times 3$ matrix to see what's going on. $\endgroup$ – Jeb Jul 14 '15 at 14:13
  • $\begingroup$ Thanks Jeb. I'm understanding the process, I'm just not sure the subscripts in the proof are correct. I will continue to look at it, perhaps it will come to me. $\endgroup$ – GreenCheck Jul 14 '15 at 18:37

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.