The exchange lemma and Gaussian elimination

By gowers

Thanks to this comment, I have finally decided to try to understand in what sense Gaussian elimination and the Steinitz exchange lemma are “basically the same thing”. It’s not at all hard to spot similarities, but it seems to be a little trickier to come up with a purely mechanical process for translating proofs in one language into proofs in the other.

It might be of some interest to know how I approached this post. Rather than working everything out in advance, I started with an incomplete understanding of the connection. I had thought about it enough to convince myself that I could get to the end, but found that as I proceeded there were a few surprises, and the eventual connection was not quite as close as I was expecting. (Actually, this paragraph is slightly misleading. I am writing it while in the middle of writing the rest of the post. I’ve had a few surprises, and though I am fairly sure I’ll get to the end I am not quite sure what the end will look like. [Note added after I'd got to the end: it was nothing like what I expected.])

I am choosing as my example of a statement to be proved the one I mentioned in this comment, namely the fact that $n+1$ vectors in $\mathbb{R}^n$ cannot be linearly independent. Let me briefly sketch the two proofs I want to consider.

First, let us do it by Gaussian elimination. We write the vectors as rows of an $(n+1)\times n$ matrix and then apply Gaussian elimination to those rows. We could either get the matrix into upper triangular form, which makes the last row entirely zero, and then observe that this row of zeros is, by the way we have produced it, a linear combination of the original $n+1$ rows. Alternatively, we could put the matrix into reduced row-echelon form and draw the same conclusion. At this stage we can’t really be sure which is more likely to correspond to the use of the Steinitz exchange lemma. So it is probably best to stick with the general thought that there are many ways of using Gaussian elimination to get a row of zeros, and we hope that at least one such way is what the proof of the Steinitz exchange lemma will give if we examine it carefully.

And what is the Steinitz exchange lemma proof? We prove the slightly more abstract fact that if a vector space $V$ can be spanned by $n$ vectors $v_1,\dots,v_n$ , then no $n+1$ vectors $w_1,\dots,w_{n+1}$ in $V$ can be linearly independent. The basic idea of the proof is to replace one of the $v_i$ by $w_1$ , then another one by $w_2$ , and so on, all the while making sure that the set of vectors we now have is still a spanning set. Eventually, we have replaced $v_1,\dots,v_n$ by $w_1,\dots,w_n$ . Therefore $w_1,\dots,w_n$ span $V$ , which means that they contain $w_{n+1}$ in their linear span, which contradicts the independence of the $w_i$ .

Of course, it remains to prove that we really can do this exchanging process. So let’s suppose, without loss of generality, that we’ve replaced $v_1,\dots,v_{i-1}$ by $w_1,\dots,w_{i-1}$ and are now trying to replace some other $v_j$ by $w_i$ . Our inductive hypothesis tells us that the vectors $w_1,\dots,w_{i-1},v_i,v_{i+1},\dots,v_n$ span $V$ , so we can write $w_i$ in the form $\lambda_1w_1+\dots+\lambda_{i-1}w_{i-1}+\lambda_iv_i+\dots+\lambda_nv_n$ . Since the $w_j$ are linearly independent, there must exist $h\geq i$ such that $\lambda_h\ne 0$ . But that allows us to write $v_h$ in terms of $w_1,\dots,w_i$ and the $v_j$ for which $j\geq i$ and $j\ne h$ . Therefore, if we replace $v_h$ by $w_i$ we still have a spanning set. This completes the proof.

Now one way to try to relate this to the previous proof is to convert it into an algorithm. It would be quite a surprise if the algorithm did not closely resemble Gaussian elimination, so once we have produced the algorithm it should be a smallish task to modify it and/or Gaussian elimination until they become the same.

A preliminary question to sort out is what the vectors are to which we will apply the algorithm. We are trying to show that $n+1$ row vectors in $\mathbb{R}^n$ must have some linear dependence, so we would like to replace $n$ of them by some vectors from a spanning set. So it’s obvious what we take as our set that will turn out not to be linearly independent. But what about the spanning set? There are two ways of arriving at the right answer to this question. One is to take the simplest spanning set we can think of, namely the standard basis of $\mathbb{R}^n$ , which, if we write it as a matrix of row vectors, gives us the identity matrix. Alternatively, we could note that Gaussian elimination is a process for replacing a matrix by something closely related to the identity matrix, so this seems a good choice. In fact, looking back at the exchange-lemma proof, we see that we can ignore $w_{n+1}$ in the exchanging process. It’s enough just to show that we can replace $v_1,\dots,v_n$ by $w_1,\dots,w_n$ . So now, if we’re assuming that the $w_i$ are linearly independent, Gaussian elimination really will give us the identity matrix.

A small worry we might feel is that with these vectors the exchange lemma is actually replacing the identity matrix by the matrix of the $w_i$ rather than the other way round. But let’s go ahead and do it anyway and worry about that later.

So, the situation we’re in is that we have an $n\times n$ matrix $W$ with linearly independent rows and we would like to prove that these rows span $\mathbb{R}^n$ . Our method will be to start with the identity matrix, where we know that the rows span, and replace its rows by the rows of $W$ , maintaining a spanning set at each stage. To harmonize with the previous notation, let’s write $w_i$ for the $i$ th row of $W$ and $v_i$ for the $i$ th row of the identity matrix.

The first step is to find one of the $v_i$ that we can replace by $w_1$ . Following the proof above, we begin by writing $w_1$ in terms of the $v_i$ . Of course, since the $v_i$ are just the standard basis of $\mathbb{R}^n$ , this is not very hard: one might even say that $w_1$ is already written in terms of the $v_i$ .

The next step is to find some $h$ such that the coefficient of $v_h$ in the expansion of $w_1$ , which we called $\lambda_h$ before, is not zero. Here, $\lambda_h$ is just the $h$ th entry of $w_1$ , so all we are doing is finding a non-zero entry in the first row of the matrix $W$ .

Having found this, we comment that this $v_h$ can be written in terms of $w_1$ and the other $v_i$ . To prove this, we write $w_1=\lambda_1 v_1+\dots+\lambda_nv_n$ and then rearrange by subtracting all the $\lambda_i v_i$ apart from $\lambda_hv_h$ from both sides and dividing through by $\lambda_h$ . We now know that if we replace $v_h$ by $w_1$ then we can still span $v_h$ . Obviously, we can also span all the other $v_j$ since they are still in the set, so the set is still a spanning set.

The problem is that merely replacing a row of the identity matrix by the first row of $W$ doesn’t seem to correspond to part of the Gaussian elimination process. And that is particularly the case as we continue the process: we replace rows one by one, but the calculations don’t do the replacement for us, so much as provide some assurance that we still have a spanning set at each stage.

In order to keep the calculations on board, so to speak, we should keep track not just of the fact that our set is a spanning set, but also of how it is a spanning set. That could mean various things, but a natural choice presents itself. We justified the replacement of $v_h$ by $w_1$ by showing how to span $v_h$ by the other $v_j$ and $w_1$ . This we did by writing $v_h$ as a linear combination of these other vectors. So as we continue the operation, we could keep track of how each replaced $v_i$ is a linear combination of the new set of vectors. If we can do this right to the end, then we will have shown how each $v_i$ is a linear combination of the vectors $w_j$ . Equivalently, we will have worked out the inverse of the matrix $W$ . Since Gaussian elimination is ideal for working out inverses (as you convert $W$ into the identity using row operations, the same row operations applied to the identity will produce $W^{-1}$ ), there seems to be a good chance of seeing Gaussian elimination in action.

With this thought in mind, let’s see if we can describe what we know after the first step of applying the exchange process to the identity matrix. We obtain a new matrix, with $v_h$ replaced by $w_1$ , and we also know what the inverse of this matrix is. Why do we know the inverse? Well, if $M$ is any square matrix, then the $i$ th row of $M^{-1}$ consists of coefficients that are needed to express $v_i$ in terms of the rows of $M$ . (To see this, consider the product $M^{-1}M$ rather than $MM^{-1}$ .) For us, if $j\ne h$ it is obvious how to write $v_j$ in terms of $v_1,\dots,v_{h-1},w_1,v_{h+1},\dots,v_n$ . As for $v_h$ , it can be calculated as follows. You start with $w_1=\lambda_1v_1+\dots+\lambda_nv_n$ , then subtract $\lambda_i v_i$ for every $i\ne h$ , and finally divide by $\lambda_h$ .

Now a little difficulty seems to be emerging, which is that as this process continues it will be less and less obvious what to do. It was very easy to write $w_1$ in terms of $v_1,\dots,v_n$ , but if we’ve already removed a few $v_i$ s and replaced them by $w_1,\dots,w_k$ then it will no longer be obvious how to write $w_{k+1}$ in terms of the current spanning set. One way we might do it is to write $M_k$ for the matrix corresponding to the spanning set at the $k$ th stage of the process, and to multiply $w_{k+1},\dots,w_n$ by the inverse of that matrix before continuing with the exchanging process. In other words, at each stage we would change basis to the spanning set we currently had, and rewrite $w_{k+1},\dots,w_n$ in terms of that basis. Then, perhaps, we would find that the calculations we did were Gaussian elimination in reverse (as we hope, since we are turning the identity matrix into a complicated matrix, rather than the other way round).

That I cannot check without going away and doing it with a sheet of paper in front of me. So maybe I’ll do that and report back. For now, here are a couple of other thoughts. First, we could have considered a different exchange process in order for things to work forwards rather than backwards. That is, suppose that $v_1,\dots,v_m$ is a spanning set and $w_1,\dots,w_n$ is an independent set. Now let us try to replace the $w_i$ by $v_j$ while preserving independence.

It turns out to be convenient to assume that $v_1,\dots,v_m$ is an independent set too. This is reasonable, since we can simply pass to a minimal spanning subset. Now we start by trying to find $w_h$ that we can replace by $v_1$ . To do this, we first try to write $v_1$ as a linear combination of the $w_i$ . If we can’t, then the set $v_1,w_1,\dots,w_n$ is linearly independent, so we can remove $w_1$ from it and we have done the replacement we want. If we can, then we have $v_1=\lambda_1w_1+\dots+\lambda_nw_n$ , and we choose $h$ such that $\lambda_h\ne 0$ . It is now straightforward to check that the vectors $w_1,\dots,w_{h-1},v_1,w_{h+1},\dots,w_n$ are linearly independent. At later stages of this process, one makes the additional remark that, since the $v_i$ are independent, there must always be a non-zero $\lambda_h$ that is a coefficient of one of the remaining $w_i$ .

This again proves the theorem, since once we have replaced $m$ of $w_1,\dots,w_n$ by $v_1,\dots,v_m$ we have a linearly independent set, and we also know that $v_1,\dots,v_m$ span. Therefore, $m=n$ . This argument did not at any point assume that the vectors belonged to $\mathbb{R}^n$ , so it also proves that you can’t have $n+1$ linearly independent vectors in $\mathbb{R}^n$ (just replace $n$ by $n+1$ and $m$ by $n$ and get a contradiction).

But a disturbing feature of the above argument is that it is not very algorithmic. Indeed, look at the very first stage: we argue by contradiction. Either the vectors $w_1,\dots,w_n$ do not span $v_1$ , in which case we are done, or they do, in which case we look for a non-zero coefficient. But all we are told here is that if we are not done then there must exist a linear combination of the $w_i$ that gives $v_1$ . We are not told a way of finding it. Indeed, to find it involves solving $n$ simultaneous equations in $n$ unknowns, and we are simply not bothering with that task. This is quite unlike Gaussian elimination, which very definitely tells us how to find such linear combinations.

So it begins to look as though the two proofs are significantly different, contrary to what somebody once told me (which I have taken on trust ever since). As one final attempt to bridge the gap between the two, let’s try to turn Gaussian elimination into a more theoretical argument. I’d like to argue that if $W$ is an $n\times n$ matrix with linearly independent rows, then these rows span $\mathbb{R}^n$ (which implies that $n+1$ vectors in $\mathbb{R}^n$ cannot be linearly independent). If I can invert $W$ then this will be proved, since I’ll then know how to produce all the vectors in the standard basis. Once again, I’ll write $w_1,\dots,w_n$ for the rows of $W$ and $v_1,\dots,v_n$ for the rows of the identity matrix.

Gaussian elimination starts by finding a non-zero entry in the first column. In terms of the vectors, we are assuming that $v_1,\dots,v_n$ is a basis, and looking for $w_h$ such that its first coefficient with respect to that basis is non-zero. (This seems to be sort of similar to what we have done before, but not identical.) Usually, for convenience, we then permute the $w_i$ so that $h=1$ . This is not a significant difference since we could have done that with the exchange process too. Let’s do it here to make the matrix easier to visualize. The next step is to “make all the other entries in the first column zero.” More precisely, let $\lambda_{i1}$ be the first coefficient of the expansion of $w_i$ in terms of $v_1,\dots,v_n$ (which equals the $i1$ -entry of the matrix $W$ ). Then we replace $w_1$ by $w_1/\lambda_{11}$ and for $i>1$ we replace $w_i$ by $w_i-\lambda_{i1}w_1/\lambda_{11}$ . Let us call these new vectors $w_1',w_2',\dots,w_n'$ . It is not hard to check that they are still linearly independent, and that $w_2',\dots,w_n'$ belong to the linear span of $v_2,\dots,v_n$ . By induction, we can do some more replacements of this kind (but involving linear combinations rather than straight exchanges) in such a way that we end up with an independent set $u_1,\dots,u_n$ with $u_i$ in the linear span of $v_i,v_{i+1},\dots,v_n$ for every $i$. (In matrix terms, we’ve made $W$ upper triangular. Also, the way we did it we gave ourselves $1$ s down the diagonal.)

Now I claim that the $u_1,\dots,u_n$ span $\mathbb{R}^n$ . To do this, I observe that $u_n=v_n$ and prove inductively that $v_i$ belongs to the span of $u_i,\dots,u_n$ . Indeed, if I’ve proved it for $v_{i+1}$ , then I argue as follows. I know that $u_i$ belongs to the span of $v_i,\dots,v_n$ . I also know that the coefficient of $v_i$ is 1 and that I can write $v_{i+1},\dots,v_n$ in terms of $u_{i+1},\dots,u_n$ . Therefore, $u_i$ equals $v_i$ plus a linear combination of $u_{i+1},\dots,u_n$ , which proves that $v_i$ is a linear combination of $u_i,\dots,u_n$ .

Of course, all this is much easier to see in its original matrix form. But again, it seems not to be the same proof as the exchange lemma since it involves linear combinations.

As I have said and written many times, I think mathematicians should be more explicit about their thought processes. So although this post is a bit of a failure in one sense, it’s going up anyway. Perhaps somebody else will see something that I have missed. For the time being I could summarize my thoughts as follows.

1. If you turn Gaussian elimination into a “theoretical” argument in the most obvious way, then it doesn’t look much like an exchange-lemma proof, even if there are some superficial similarities.

2. At least one exchange-lemma argument appears to be strongly non-algorithmic.

3. The best hope of showing that the two are “essentially the same” seems to be to use the exchange lemma to convert the identity into a more complicated matrix $W$ with independent rows, but to keep changing basis as one does so, so that the calculations remain simple. It might be that the result of this process is to do calculations very similar to those of Gaussian elimination, but backwards. I hope to investigate this possibility before too long.

Tags: linear algebra

This entry was posted on October 3, 2007 at 11:56 am and is filed under Demystifying proofs. You can follow any responses to this entry through the RSS 2.0 feed. You can leave a response, or trackback from your own site.

12 Responses to “The exchange lemma and Gaussian elimination”

Terence Tao Says:
October 3, 2007 at 6:40 pm | Reply
Dear Tim,

It seems to me that the key fact that underlies exchange lemma is in fact the adjoint of the key fact that underlies Gaussian elimination; the difficulty you are having in equating the two is thus the same difficulty one encounters when trying to identify a vector space with its dual.

To explain, let me use ${\Bbb R}^A = \{ (x_i)_{i \in A}: x_i \in {\Bbb R} \}$ to denote the real vector space indexed by a finite set A. The exchange lemma algorithm is based on iterating the following:

Lemma 1. If $T: {\Bbb R} \to {\Bbb R}^A$ is non-zero, then there exists $i \in A$ such that ${\Bbb R}^A$ is the direct sum of $T({\Bbb R})$ (which is isomorphic to ${\Bbb R}^{\{i\}}$ ) and ${\Bbb R}^{A \backslash \{i\}}$ (i.e. these spaces are complementary).

(Proof: expand $T(1) \in {\Bbb R}^A$ in coordinates. There must exist i such that the $i^{th}$ coordinate of T(1) is non-zero. The claim then easily follows for this choice of i.)

This lemma is what lets you exchange $w_1$ for one of the $v_1,\ldots,v_n$ . (To exchange $w_i$ for one of the $v_i,\ldots,v_n$ , one can first quotient out by the span of $w_1,\ldots,w_{i-1}$ and then argue as before.)

In contrast, the ability to use Gaussian elimination to reduce any matrix to row-echelon form is based on iterating the following:

Lemma 2. If $T: {\Bbb R}^A \to {\Bbb R}$ is non-zero, then there exists $i \in A$ such that ${\Bbb R}^A$ is the direct sum of $\hbox{ker}(T)$ (which is isomorphic to ${\Bbb R}^{A \backslash \{i\}}$ ) and ${\Bbb R}^{\{i\}}$ .

(Proof: there must exist a basis element $e_i$ such that $T(e_i)$ is non-zero. One can then express all the other $e_j$ as a linear combination of $e_i$ and something in the kernel of T.)

To see how row-echelon form follows from this, consider n vectors $v_1,\ldots,v_n$ in a standard vector space ${\Bbb R}^d$ , and let $T: {\Bbb R}^n \to {\Bbb R}$ be defined by setting $T(x_1,\ldots,x_n)$ to be the first coordinate of $x_1 v_1 + \ldots + x_n v_n$ . If T is non-zero, then by Lemma 2 we can use Gaussian elimination to extract one row $v_i$ with a non-vanishing first coordinate, and n-1 other vectors with vanishing first coordinate; if instead T is zero, then all rows already have vanishing first coordinate. Throwing away $v_i$ and the first column and iterating, one eventually gets row echelon form.

It is not hard to see that Lemma 1 and Lemma 2 are essentially adjoints of each other.

This strongly suggests that the exchange lemma should in fact be related to the use of column operations to place a matrix in column-echelon form. If we let $u_1,\ldots,u_d \in {\Bbb R}^n$ denote the rows of an $d \times n$ matrix, column operations correspond to “passive” transformations which change the basis for the vector space ${\Bbb R}^d$ without affecting the vectors $u_1,\ldots,u_d$ themselves (in contrast, the “active” row transformations modify those vectors but leave the coordinate basis unchanged). To formulate the exchange lemma in this language, I think what one needs to do is express the r independent vectors $w_1,\ldots,w_r$ , together with the n spanning vectors $v_1,\ldots,v_n$ , as linear combinations of the n spanning vectors $v_1,\ldots,v_n$ , leading to a $r+n \times n$ matrix which has an $n \times n$ identity matrix at the bottom. If one applies adjoint Gaussian elimination to this matrix to place it in column-echelon form, I believe that one obtains all of the $w_1,\ldots,w_r$ rows and n-r of the $v_1,\ldots,v_n$ rows as pivot rows (because of the linear independence of the $w_1,\ldots,w_r$ ), and that these pivot rows span the whole space, thus yielding the exchange lemma.

Incidentally, over a finite field F, it is trivial to show by a counting argument that a vector space V spanned by n vectors cannot contain n+1 independent vectors, since the former hypothesis easily implies $|V| \leq |F|^n$ and the latter hypothesis would imply $|V| \geq |F|^{n+1}$ . One can adapt this counting argument to vector spaces over the reals by various discretisation tricks (e.g. using metric entropy, or Minkowski dimension, or taking a numerical perspective and rounding off to some finite degree of accuracy). Alternatively, one can argue more algebraically (or model-theoretically) by invoking a “Lefschetz principle” or “compactness principle” to equate linear algebra assertions over the reals with linear algebra assertions over fields of sufficiently large characteristic.

It seems difficult (though perhaps not entirely impossible) to recast these arguments in algorithmic form.
gowers Says:
October 3, 2007 at 10:09 pm | Reply
Dear Terry,

That’s very interesting. I had vaguely wondered about similar ideas, but I was thinking more about inverses than adjoints. I still haven’t got my head completely round what you’ve written, but will at some stage try to convert it into a very explicit demonstration of how the exchange lemma can yield an algorithm that is more or less the same as Gaussian elimination (but probably applied to columns rather than rows).

The last thing you mentioned reminds me of a fascinating fact that I learned as a result of editing an article on model theory for the Princeton Companion. It’s the most gorgeous proof (which, from what you write, you probably know of) of the following fact: if $P$ is an injective polynomial map from $\mathbb{C}^n$ to $\mathbb{C}^n$ then it must be surjective. The rough idea of the proof is the same as what you say above. By model-theoretic considerations one can show that the statement is true in $\mathbb{C}$ if and only if it is true in a finite field $\mathbb{F}$ of sufficiently high characteristic. But there the statement is trivial. It’s a great example of a non-obvious statement that doesn’t seem to have anything to do with logic, but which is proved by logical means. (The proof was discovered by Ax, apparently. For more details, see the PCM when it comes out.)

Another thing that’s interesting about your remark is that it is connected with a question that I like and that I intend to pursue more on this blog, namely what it means for two proofs to be “essentially the same.” It’s an intriguing phenomenon, because it so often happens that two rather different-looking proofs eventually turn out to be less different than they at first appear, as you make very clear in your article, “What is good mathematics?” Given that, it’s all the more interesting to find two proofs that really do seem to be genuinely different. And the model-theoretic argument that $n+1$ vectors in $\mathbb{R}^n$ cannot be independent appears to fall into that category (which is not to say that it wouldn’t be worth trying to “expand it out,” just to check).
Kevin Says:
October 4, 2007 at 4:44 am | Reply
Here are some blog posts related to “homotopies between proofs”. Maybe you’ll find them interesting. The idea of somehow using ideas from topology to study proofs doesn’t seem all that crazy …

Week 227 of This Week’s Finds
Neighborhood of Infinity
Orange Juice Files
When are two proofs essentially the same? « Gowers’s Weblog Says:
October 4, 2007 at 10:12 am | Reply
[...] is, methods for transforming a proof into another that is not interestingly different. See this comment for some interesting links, though here I am not so much looking for a formal theory right down at [...]
Jason Dyer Says:
October 4, 2007 at 2:41 pm | Reply
I’m still trying to parse everything here, but since it was my comment I wanted to thank you for posting this!
Top Posts « WordPress.com Says:
October 4, 2007 at 2:52 pm | Reply
[...] The exchange lemma and Gaussian elimination Thanks to this comment, I have finally decided to try to understand in what sense Gaussian elimination and the Steinitz […] [...]
derek hacon Says:
October 4, 2007 at 10:33 pm | Reply
Easier than using Steinitz seems to be to do things matricially: use row and colummn operations (rather than just row operations) to show easily that any matrix is PAQ equivalent (P and Q being square invertible matrices) to canonical form (having least number of nonzero entries). To prove facts like linear dependence of the columns of any matrix which has less rows than columns, first check the statement is invariant by PAQ equivalence (P and Q being square invertible matrices) and then that it´s obviously true for canonical form. From this the corresponding vectors property (i.e. the linear dependence of n+1 vectors, each of which is a linear combination of n vectors) is easily deduced.
The interest of Steinitz seems to be that it pops up in other contexts…for example, in the proof that Kruskal´s algorithm works (i.e. provides a minimal spanning tree for a weighted graph).
Kay Says:
October 5, 2007 at 8:08 pm | Reply
1. This is all fascinating and quite above me (at least for the moment!)

2. Terry, my linear algebra is growing by leaps and bounds, and I am seeing why your comment “As regards the identification between matrices and linear transformations … it’s important to understand both perspectives, and how to swap back and forth.” makes much more sense than my first naive impression.
nugae Says:
October 12, 2007 at 12:22 pm | Reply
This is what mathematics ought to be, not the sterile freeze-dried stuff you see in published papers. Mathematics is about intuition, surprise, and delight: why else do we do it?

I’m having a go at conveying these things in writing about a relatively infantile problem in number theory. It’s a challenge – I keep on slipping into mathematical-paper mode – but rewarding when it works.
Joerg Liesen Says:
October 30, 2007 at 4:09 pm | Reply
Dear Timothy,

I have a comment/question concerning the history of the subject. In your blog you speak of the “Steinitz” exchange theorem. Terence Tao uses the same name in his blog, so it seems that this is the common name for this result. Do you know how this name got attached to this result? Who used this name first?

The result of Ernst Steinitz (1871-1928) was published 1913 in Crelles Journal. There he writes that (rough translation follows) “the basics of n-dimensional geometry could have been assumed as well known, but I prefer to rederive them here.” Apparently, the result was already known to Steinitz. Indeed, the result — in almost the exact form as in your blog — already appears in Hermann Grassmann’s Ausdehnungslehre of 1862, a book that was completed in the summer of 1861, i.e. 10 years before Steinitz was born. Steinitz does not cite Grassmann, which is fortunate for him, as now the result is known under his name.
gowers Says:
October 30, 2007 at 6:30 pm | Reply
I’m afraid I just tend to use the standard names for things and don’t look into the history. But it’s always interesting to hear from people who do know about it. To make up (partially at any rate) for my laziness in this respect, when I give lectures I tell people that a good rule of thumb is that if somebody’s name is attached to a result (at least if the result is sufficiently simple) then they probably weren’t the first person to prove it. I’ve always wondered how Vandermonde’s theorem came to be known as that: if only all theorems were as easy to obtain …
Mark Meckes Says:
October 30, 2007 at 10:03 pm | Reply
Regarding names, I’ve always found it curious that almost every mention of Burnside’s lemma seems to be accompanied by the comment that it wasn’t first proved by Burnside. Given that the same is true of most results with a person’s name attached, I don’t understand why Burnside is singled out for such abuse.

Gowers’s Weblog

The exchange lemma and Gaussian elimination

12 Responses to “The exchange lemma and Gaussian elimination”

Leave a Reply