# Proof that bases etc. exist in early linear algebra course?

I'm currently struggling to teach a 2nd course on linear algebra (in the UK, not at an Oxbridge quality university: the students have done a 1st course which concentrated upon algorithms you can apply to matrices, and calculations involving R^2, R^3 etc.)

The syllabus suggests a very abstract approach, stating and proving the Steinitz exchange lemma, and then working up to showing that every (finite dimensional) vector space has a basis of a fixed size etc. etc.

However, I think I'm killing my students. This is all very abstract, it's going to take me weeks to do, and the end result is: All finite dimensional vector spaces look, well, exactly as you think they do. I'm tempted to skip on to linear maps, matrices etc. which seems more interesting to me (and sort of motivates why we might care about choosing a different basis...)

However, I'm also loathed to just assert these facts without proof: the students saw that before in the previous course, and in a pure maths course, I sort of want to prove things (even if I don't expect the students to understand everything).

What do people think about doing a linear algebra course in maximal abstraction early on? Is there a good book which takes a very streamlined (if perhaps hard to understand) approach to proving the existence of bases-- at least then I could get it over with quickly without lying to the students.

I read Pedagogical question about linear algebra which was very useful, but maybe concentrated upon a different problem.

• To get an idea of the problems I have, look at the Wiki entry for the Exchange Lemma: en.wikipedia.org/wiki/Exchange_lemma Now, I can follow this proof, but it's basically wrong: there's lots of implicit re-ordering going on, there's some basic lemmas invoked (to do with linear spans) and then an implicit induction is used: but it's not clear that you won't swap out v_1 at a later stage (you don't, because of linear independence). To write this up to be follow-able by my students would make it very long... – Matthew Daws Oct 6 '10 at 9:59
• I agree about the state of that wikipedia page. It's awful! Something Ought To Be Done about it. – Loop Space Oct 6 '10 at 13:28
• Does the proof really have to be so long? See the Wiki entry now. It could still be slightly lengthened for maximal clarity but I don't think it is so hard to write out a shortish intelligible proof. – Simon Wadsley Oct 6 '10 at 14:13
• Hmm. I had to stretch it by a factor of 2 to be able to follow it without pen and paper. Is there something trivial that eluded me? – darij grinberg Oct 6 '10 at 14:50
• Matt: this isn't quite what you want, I think, but have you seen this proof that in char zero any two bases must have the same cardinality? ams.org/mathscinet-getitem?mr=1328020 – Yemon Choi Oct 7 '10 at 18:02

I'm teaching such a course at the moment, and whilst my university has high aspirations, I think that the "Not Quite Oxford" appellation applies here as well.

(For those who like the answer first, I pretty much agree with Alex and Robin.)

Here's the approach I'm taking:

1. Matrices are great, but dull. They're fantastic for actually getting an answer, but doing all the manipulations yourself is fantastically boring and prone to error. Fortunately, computers are really good at doing such manipulations and (as yet) don't get bored. In summary, being able to use matrices is a really Good Thing but actually using them yourself isn't.

2. A matrix represents (note the word) a linear transformation from one Euclidean space to another. There's an obvious and easy correspondence between the two. So we can use everything we know about matrices to study linear transformations between Euclidean spaces.

3. But not everything we want to study is a linear transformation from one Euclidean space to another. How about differentiation of polynomials (of some fixed finite order)? It feels like we could do this with a matrix, but can we?

4. By considering this example, we decide that if we have an isomorphism from our arbitrary space to a Euclidean space, then we can use matrix methods. So we define "finite dimension" (as a whole concept) to mean "there is an isomorphism to some Euclidean space".

5. Using Gaussian Elimination (a la Robin), we can show that if $V \cong \mathbb{R}^n$ for some $n$ then $n$ is unique. (No hand-waving required.) This allows us to define the actual dimension.

6. So "finite dimension" means "can make it look like $\mathbb{R}^n$" which means "can use matrix methods". But this approach brings to the surface the isomorphism $V \cong \mathbb{R}^n$ and so it's really easy to focus our attention on the question: "How do I choose between the different such isomorphisms?" (for example, $\operatorname{Poly}_3 \cong \mathbb{R}^4$ by coefficients, or by evaluation at $0,1,2,3$ or some other means).

7. Finally, for those die-hard basists, I mention that an isomorphism $V \cong \mathbb{R}^n$ is the same thing as a(n ordered) basis of $V$. This comes easily from the fact that giving a(n ordered) $k$-element subset of $V$ is the same as giving a linear transformation $\mathbb{R}^k \to V$, and then we observe:

• $\mathbb{R}^k \to V$ injective if and only if $\{v_1,...,v_k\}$ linearly independent
• $\mathbb{R}^k \to V$ surjective if and only if $\{v_1,...,v_k\}$ spanning
• $\mathbb{R}^k \to V$ isomorphism if and only if $\{v_1,...,v_k\}$ basis
8. The meta-point of it all is that the students should think of an isomorphism $V \cong \mathbb{R}^n$ as a point of view: a way of looking at $V$. So being able to change ones point of view to suit the circumstances is a very good skill. And that applies as well to bases: thinking of a basis as a set of elements is useful for actually going out and finding one, but thinking of it as an isomorphism $V \cong \mathbb{R}^n$ is very good once you know it exists.

9. It's probably pretty obvious from the above, but I'll say it anyway. In this, I do consider $\mathbb{R}^n$ to have an obvious choice of basis. I mean, I'd choose it, wouldn't you? There's also a bit of category theory sitting underneath all of this which recognises that $\mathbb{R}^n$ is the free vector space on $\{1,...,n\}$. Also, later in the semester I'll talk about orthonormal bases of (separable) Hilbert spaces. Only I won't, I'll talk about isometric isomorphisms $H \cong \ell^2$.

For more on how I'm doing this, you can look at my recent lectures: here and some other details on our course wiki, in particular at the page on dimension.

(On that, I don't think that all information has to be given in lectures. I think that students should be expected to fill in some gaps by themselves. To forestall a slurry of comments about how I'm encouraging Bad Teaching Again, the gaps should be specifically chosen by the lecturer for this purpose rather than being what the lecturer happens to forget to say.)

• It seems to me that you should also prove at some point that a subspace of a finite dimensional vector space is finite dimensional, and a quotient of a finite dimensional vector space is finite dimensional. These facts are not obvious given the way you have set up the definitions. – David E Speyer Oct 6 '10 at 13:43
• When did you encourage Bad Teaching Last Time? :) – Mariano Suárez-Álvarez Oct 6 '10 at 13:45
• David, actually they are. There's various ways to do them, but one which shows the power of the technique is to observe that once these facts are established for $\mathbb{R}^n$ then they automatically hold for all finite dimensional vector spaces. And in $\mathbb{R}^n$ I can use whatever extra structure I like! For example, I can use the standard inner product to split quotient mappings. Thus both become questions about subspaces. And that's easy once I prove that if a space is not finite dimensional then it is infinite dimensional (ie contains a copy of each $\mathbb{R}^n$). (ctd) – Loop Space Oct 6 '10 at 16:05
• (ctd) The key step is the fact that Gaussian Elimination is actually a theorem about dimension. It says that if $T \colon \mathbb{R}^n \to \mathbb{R}^m$ is an injection then $n \le m$, and so on. Of course, to a certain extent, it's rearranging deck chairs on the iceberg of Linear Algebra, but the trick is to make it so that each step along the way is notable for its own sake and not just as a step towards some Big Result (which is never quite as Big or Resulty as the build-up promises). – Loop Space Oct 6 '10 at 16:07
• Mariano: apparently, I encouraged Bad Teaching here: mathoverflow.net/questions/40082/… – Loop Space Oct 6 '10 at 16:09

If a vector space had bases of two different finite sizes $m < n$ say, then expressing one in terms of the other gives $m$ by $n$ and $n$ by $m$ matrices $A$ and $B$ such that $BA=I_n$. Now use Gaussian elimination (quote their first-year course) to "prove" (with an appropriate amount of hand-waving) that $Av=0$ has a nonzero solution, and thus derive a contradiction. Surely less than a lecture :-)

• The variant of this that I use (when teaching linear algebra): Express $v_1$, $\ldots$, $v_n$ as linear combinations of $u_1$, $\ldots$, $u_m$. Then test to see whether $v_1$, $\ldots$, $v_n$ is linearly independent in the usual way by solving the system of linear equations $\alpha_1 v_1 + \cdots + \alpha_n v_n = 0$. Rearrange to get up with $m$ equations in the $n$ unknowns $\alpha_i$, the system is homogeneous so it is consistent, and as the system has free variables there are non-trivial solutions and hence the larger "basis" is not actually linearly independent. – Gordon Royle Oct 6 '10 at 23:07

Dear Matthew, I have a couple of different remarks about the question and about the assumptions you seem to be making.

1. You write "I'm tempted to skip on to linear maps, matricies etc. which seems more interesting to me (and sort of motivates why we might care about choosing a different basis...)" But what do you mean by "different basis"? It seems to me that the main point of this kind of course that the students should take home is that there is no canonical choice of basis. You can only talk about "a different basis" if you have a god-given basis that the vector space is born with. But a vector space looks the same from all directions. If the students understand that, then they will accept that in describing e.g. elements of the space or linear maps, they have to make arbitrary choices, so the next natural question is "how do things depend on my choice?".

2. Once the students accept, that there is no god-given basis, I don't think that the Steinitz exchange lemma and the invariance of dimension will be as hard as you are expecting them to be. I wouldn't have thought, that you would need "weeks" (plural!) to prove that the size of a basis is an invariant of the vector space. And anyway, with enough pictures and the constant reminder that you are just investigating, how things depend on your arbitrary choices, they should be able to get the gist of the arguments even before they see the details.

3. You are saying that the students have had a first exposition to the algorithmic/practical aspects of linear algebra. So surely, it is time for them to learn, that you can develop the subject rigorously. The situation you are describing is not actually one, where you are "doing a linear algebra course in maximal abstraction early on". Neither is it early on, if it's a second course on linear algebra, nor does the fact that finite dimensional vector spaces have a well-defined dimension exactly signify maximal abstraction.

My summary: I think you should go ahead with the syllabus and think more about how to take their fears and make things intuitively clear than where to "cheat".

I hope this helps.

• Point 1 is very good: point taken! Not so sure about the rest, but I see what you're trying to say. – Matthew Daws Oct 6 '10 at 10:19
• I doubt that the "no basis" point of view is the one of students coming in to their first abstract linear algebra class (and might not even be theirs coming out of the class). Before students have a good reason to think otherwise, a vector space will be $R^n$ for some n, and thus does come with a canonical basis. And frankly, I don't think it's such a bad place to start from; it's where a lot of the more concrete applications live. – Thierry Zell Oct 6 '10 at 12:53
• I agree that it's not a bad place to start from and it's almost certainly the place they really do start from, but it's not a good place to stay at forever, especially for maths students. That's why I was saying that the fact, that their familiar identification with $R^n$ is arbitrary should be the main insight that they take from their first abstract linear algebra course. Matthew was proposing to short change them on exactly this point, which I think is a bad idea. – Alex B. Oct 6 '10 at 14:11
• Alex: I see your point. Still, giving students a good handle on linear maps is equally important, so the choice may depend on how tight the schedule really is. – Thierry Zell Oct 7 '10 at 12:59

I do not really know what is the level of the course and what else is in the syllabus, but there are many excellent books in linear algebra that cover abstract vector spaces almost painlessly. A good book to find this stuff is Axler's "Linear Algebra Done Right".

• Hmm, our library doesn't have this sadly... – Matthew Daws Oct 6 '10 at 15:19
• Hi Matt; I looked at this book several years ago, and from memory I agree; it is indeed very good. Ask the library to order a copy! Or do an inter-library loan... One thing I particularly liked: to prove that AB=I implies BA=I for finite square matrices, use the Rank-Nullity Theorem, NOT determinants; in fact Axler does a surprising amount of stuff easily without determinants, which I certainly approve of. I hate dets!! – Zen Harper Oct 7 '10 at 14:14

"Is there a good book which takes a very streamlined (if perhaps hard to understand) approach to proving the existance of bases"

Michael Artin's Algebra Ch 3, S 3 does what you are asking for in under four pages (and is not hard to understand).

• Hmm, so actually, this seems to use the idea as Robin Chapman's answer: i.e. reduce to some matrix problem at heart. – Matthew Daws Oct 6 '10 at 15:32

This is really an answer by Yemon Choi (who put this in a comment, which is now buried) but as it's community wiki...

A very cute proof of just the fact that an bases have the same (finite) cardinality is given by Ford in http://www.ams.org/mathscinet-getitem?mr=1328020

Sadly it doesn't work in characteristic p, which my course is meant to touch upon.

• Very slick. The proof is this: if there are bases of sizes $m$ and $n$ there are matrices $A$ and $B$ with $AB=I_m$ and $BA=I_n$, But $AB$ and $BA$ have the same trace. – Robin Chapman Oct 7 '10 at 19:25

I guess I should say what I've settled on doing. Having re-written my notes again I'm now using a version of the Exchange Lemma which is very close to that in the Wikipedia article. Previously I'd been following Kaye+Wilson which builds this result up via a couple of lemmas. I think the new version is sufficiently streamlined that I can do it, and then get onto big results, all in a lecture.

The approach which Robin, Andrew et al. suggest (that is, leverage what we already know about matrices) is attractive. But I think it's too late for me this year (and we're re-writing all our syllabi at present, so the course will have to be seriously rethought next year or the one after anyway). I also have a sneaking suspicion that a proof relying upon Gaussian Elimination will fail to convince nearly as many students as the Exchange Lemma version.

Thanks for all the responses: some very useful ideas!