I know of a proof using the exchange lemma, but I am trying to relate this approach to the approach using row reduction. The proof from my text (Linear Algebra Done Wrong) goes something like: since the vectors are linearly independent, the echelon form of the matrix with the $n$ vectors as columns has $n$ pivots. But there are only $m$ rows, so the number of pivots cannot exceed $m$. Hence $m\leq n$. However, I feel uneasy about the step, because it seems so much easier than the proof the exchange lemma. Where is the difficulty hidden in the proof using row reduction?


The proof uses the fact that every matrix can be transformed to echelon form. The transformation to echelon form is done via row operations, and it requires a proof that it actually works. You may regard this as the "hidden" part. In fact, the procedure of row reduction is closely related to the exchange process in the Steinitz exchange lemma.

  • $\begingroup$ Could you elaborate on what you mean by 'closely related'? $\endgroup$ – Aubree Walters Jul 15 '18 at 10:44
  • $\begingroup$ The rows $r_1,..., r_n$ of a $n \times m$-matrix can be regarded as vectors in $\mathbb{R}^m$. They generate a subspace $V \subset \mathbb{R}^m$. In a row operation a row $r_k$ is replaced by a linear combination $\Sigma_{i=1}^n a_i r_i$ with $a_k \ne 0$ (a row exchange of $r_k$ and $r_l$ is the combinaton of three such operations: $r'_l = r_l + r_k$, $r'_k = -r_k + r'_l = r_l$, $r''_l = r'_l - r'_k = r_k$). Via row operations $\{ r_1,..., r_n \}$ is transformed into a certain basis $\{ b_1,...,b_k \}$ of $V$. $\endgroup$ – Paul Frost Jul 15 '18 at 12:47
  • $\begingroup$ The same idea (replacement of a vector $v_k$ by a linear combination $\Sigma_{i=1}^n a_i v_i$ with $a_k \ne 0$ ) is used in the exchange lemma. $\endgroup$ – Paul Frost Jul 15 '18 at 12:47

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.