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.
 A: 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 :-)
A: Dear Matthew, I have a couple of different remarks about the question and about the assumptions you seem to be making.


*

*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?".

*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. 

*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.
A: 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".
A: "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).
A: 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.
A: 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:


*

*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.

*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.

*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?

*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".

*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.

*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).

*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


*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.

*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.)
A: 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!
