MathOverflow will be down for maintenance for approximately 3 hours, starting Monday evening (06/24/2013) at approximately 9:00 PM Eastern time (UTC-4).

## When to pick a basis?

Picking a specific basis is often looked upon with disdain when making statements that are about basis independent quantities. For example, one might define the trace of a matrix to be the sum of the diagonal elements, but many mathematicians would never consider such a definition since it presupposes a choice of basis. For someone working on algorithms, however, this might be a very natural perspective.

What are the advantages and disadvantages to choosing a specific basis? Are there any situations where the "right" proof requires choosing a basis? (I mean a proof with the most clarity and insight -- this is subjective, of course.) What about the opposite situation, where the right proof never picks a basis? Or is it the case that one can very generally argue that any proof done in one manner can be easily translated to the other setting? Are there examples of proofs where the only known proof relies on choosing a basis?

-
"For example, one might define the trace of a matrix to be the sum of the diagonal elements, but many mathematicians would never consider such a definition since it presupposes a choice of basis." This <b> is </b> the standard definition of trace. I am not aware of a single mathematician who would <i> never </i> consider such a definition. – Gil Kalai Nov 8 2009 at 17:42
"I am not aware of a single mathematician who would <i> never </i> consider such a definition." Except Bourbaki, of course :) There the trace, as a function from endomorphisms of a finite dimensional $k$-vector space $V$ to $k$ is defined as the composition of the canonical isomorphism $End(V) \cong V \otimes V^*$ followed by the dual pairing $V \otimes V^* \to k$. You've got to admit that it has its charm :) – José Figueroa-O'Farrill Nov 8 2009 at 17:55
Bourbaki may be better than anyone else at hiding bases, but they are surely in there somewhere. For instance, how do you know that $V^*$ is non-trivial? – Greg Kuperberg Nov 8 2009 at 17:59
It's probably not worth saying, but the issue with the definition given in terms of sum of the diagonal entries is that it's not at all clear that such a definition is independent of basis, whereas the dual pairing, if it exists, is totally canonical. – Qiaochu Yuan Nov 8 2009 at 19:05
I don't think pedagogically you should introduce the determinant in order to define the trace. Traces can be defined when determinants aren't. – Qiaochu Yuan Nov 9 2009 at 14:31

One answer to your question is already hinted at in the question. At the level of algorithms, basis-independent vector spaces don't really exist. If you want to compute a linear map $L:V \to W$, then you're not really computing anything unless both $V$ and $W$ have a basis. This is a useful reminder in our area, quantum computation, that has come up in discussion with one of my students. In that context, a quantum algorithm might compute $L$ as a unitary operator between Hilbert spaces $V$ and $W$. But the Hilbert spaces have to be implemented in qubits, which then imply a computational basis. So again, nothing is being computed unless both Hilbert spaces have distinguished orthonormal bases. The reminder is perhaps more useful quantumly than classically, since serious quantum computers don't yet exist.

On the other hand, when proving a basis-independent theorem, it is almost never enlightening (for me at least) to choose bases for vector spaces. The reason has to do with data typing: It is better to write formulas in such a way that the two sides of an incorrect equation are unlikely to even be of the same type. In algebra, there is a trend towards using bases as sparingly as possible. For instance, there is widespread use of direct sum decompositions and tensor decompositions as a way to have partial bases.

I think that your question about examples of proofs can't have an explicit answer. No basis-independent result needs a basis, and yet all of them do. If you have a reason to break down and choose a basis, it means that the basis-independent formalism is incomplete. On the other hand, anything that is used to build that formalism (like the definition of determinant and trace and the fact that they are basis-independent) needs a basis.

There is an exception to the point about algorithms. A symbolic mathematics package can have a category-theoretic layer in which vector spaces don't have bases. In fact, defining objects in categories is a big part of the interest in modern symbolic math packages such as Magma and SAGE.

-
I really like your "data typing" explanation of how basis avoidance helps. – Andrew Critch Nov 8 2009 at 22:07

If we restrict ourselves to the field of linear algebra, my personal point of view, which I do not want to force on anybody, is that one should never use bases, matrices, or coordinates.

The main reason is that you lose geometric intuition whenever you introduce a basis, and geometric intuition in linear algebra is extremely important for me, not only in definitions but also in theorems and their proofs.

When I learned linear algebra I made sure I understood the geometric meaning of every single definition, theorem, and proof. For example, an element of a vector space is a vector or a 1-dimensional subspace with an oriented metric, an element of the dual vector space is a hyperplane with an oriented metric on its “complement”, i.e., the factor space, an element of the exterior algebra is a formal sum of vector subspaces (dimension equals degree) equipped with oriented metrics, an element of the exterior algebra of the dual space is a formal sum of vector subspaces (codimension equals degree) with an oriented metric on their “complement”, i.e., the factor space, the exterior product of two elements of the exterior algebra is the direct sum of the corresponding spaces (or zero if they have nontrivial intersection) with the obvious choice of an oriented metric, the inner product of an element of the exterior algebra and an element of the dual exterior algebra is the intersection or the sum (depends on the type of the inner product) of the corresponding subspaces with the obvious choice of an oriented metric, Hodge star is a particular case of the previous construction (if you have a subspace with an oriented metric and also an oriented metric on the entire space then you can canonically produce an oriented metric on the “complement”, i.e., the factor space), trace and determinant also have an obvious geometric meaning in this framework etc. etc. etc.

All of this is fully rigorous and all theorems and their proofs become trivial once you have a geometric intuition for all definitions, and you don't need any bases, coordinates, or matrices, even when you prove something.

Ironically, the best source for geometric intuition in linear algebra for me was Bourbaki's Algebra, which is often blamed for its abstractness. Actually it is the only source known to me that (indirectly) explains the geometric meaning of exterior algebra (please tell me if you know other sources).

I badly want to see a sufficiently advanced textbook on linear algebra that at least includes all the notions mentioned above (and many others, of course) and satisfies the following two conditions: (1) It explains the geometric meaning of every single definition, theorem, and proof (or states them in such a way that their geometric meaning is evident); (2) It never uses bases, coordinates, or matrices and does not even define these notions.

-
I think this isn't a tenable position to take unless you also talk about trace diagrams, which are also independently interesting. – Qiaochu Yuan Nov 10 2009 at 20:44
Well, one can use either trace diagrams or the usual algebraic notation, whatever is more convenient. I do not see how this affects the validity of my point. – Dmitri Pavlov Nov 11 2009 at 17:15
This answer is great :) – Jan Weidner Apr 22 2010 at 21:36
Have you looked at any of the books on Geometric Algebra/Calculus by Hestenes and his collaborators. They try and do all of analytic geometry and linear algebra using Clifford Algebras to do coordinate free computations. Hestenes even wrote a book on classical mechanics from this perspective. – Justin Hilburn Jan 25 2011 at 3:51

In my opinion, there is absolutely nothing wrong with picking a basis whenever it exists and using it makes the proof more understandable. I personally would prefer a proof that uses an arbitrarily (or conveniently) chosen basis to a proof that avoids bases at the cost of raising the level of abstraction to the sky. The definition of a finite-dimensional space in the post Reid Barton referred to can send almost any linear algebra student running into the night screaming. We can enjoy the "independent formalism" and even find it "enlightening" but for a huge group of finite-dimensional linear algebra users out there the "basis dependent" considerations are the most understandable ones.

-
The problem is, most linear algebra students think only in terms of bases. Bases are useful, but can also be a crutch. Stressing basis independent thinking discourages being stuck in one paradigm. – Richard Dore Nov 10 2009 at 19:21

Brian Conrad has a handout (pdf) in which he talks about tensorial maps. In it he notes that one should construct maps independently of bases, but that in order to prove the properties of such maps it made sense to choose bases or spanning sets.

I think this is generally applicable: it seems to me that picking bases should be the last part of your work on a problem, and that it mostly comes in at the level of computation. Bases provide a useful structure to a vector space that enables one to start somewhere, and proofs can be easier to do with them. But if you choose a basis too early on, you have to carry it around for the whole problem, and you might have to show how it transforms. Perhaps you could come up with ideas and proofs using bases, and then edit them to show what's really going on at the level of maps?

In class we recently constructed the determinant of a linear transformation $T:V\rightarrow V$ over and $n$-dimensional vector space V, and to do this we defined the exterior power and used the fact that $T$ became multiplication by a scalar in $\wedge^n(V)$. To be sure, we showed that given a basis $v_1, ...v_n$ of $V$, one would make the single basis element $v_1\wedge\ldots\wedge v_n$ of $\wedge^n(V)$, and used this to give the combinatorial formula for determinant. But the properties of determinant are invariant under change of basis, so we didn't prove them using a basis.

-
 It's a good point that you can prove facts in tensor algebra without using bases. I personally think though that most people need bases to work out examples when you introduce tensors, dual space, etc. Hard to build intuition if you don't have a specific example in mind. – Ilya Nikokoshev Nov 8 2009 at 19:55 Yes, that's what I intended to suggest: use bases to work out ideas, then edit the proofs. – Elizabeth S. Q. Goodman Nov 9 2009 at 4:54

One example when you should "choose" a basis for your proofs is when there is an obvious choice of basis, e.g., group algebras and path algebras (paths on a Bratteli diagram give an orthonormal basis for a Hilbert space).

The subfactor equivalent to a basis is called a Pimsner-Popa basis. As of yet, there is no way to define the canonical planar algebra associated to a subfactor without choosing a basis (even though the result is independent of the choice).

Another example of the "right proof" requiring picking a basis is Michael Burns' proof that the rotation is periodic on the relative commutants of a finite index $II_1$-subfactor. There is a way to show this basis independently (see Planar Algebras I, arXiv:math/9909027, pages 84-85), but Burns' treatment is more elegant.

-

Although the first definition of "finite dimensional" is usually "there is a finite basis", this isn't the only way to characterise finite dimensional vector spaces and often a different way to characterise them can lead to a more elegant statement and proof of the theorem under consideration.

1. A vector space is finite dimensional if it is isomorphic to some Euclidean space. This is quite close to the notion of a basis and it is obvious that choosing such an isomorphism is tantamount to choosing a basis. However, it explains one of the roles of bases as explained in Greg's answer: to make an abstract vector space look like Euclidean space (and thus also make abstract linear transformations look like matrices).

2. There's Todd Trimble's definition in this question which relates finite dimensionality to duality.

3. A definition that doesn't use a "there exists" property (which implies that at some point you might want to make a choice) starts in the category of locally convex topological vector spaces, wherein a LCTVS is finite dimensional if it is a nuclear Banach space.

This is particularly relevant to the definition of trace, since a space $V$ is nuclear if every continuous linear map $V \to E$, where $E$ is a Banach space, is trace class. Thus if $V$ is nuclear and Banach, every continuous linear map $V \to V$ must admit a trace.

4. A vector space is finite dimensional if its exterior algebra has finite grading. Moreover, it has dimension $n$ if $\Lambda^n V$ is 1-dimensional. Thus we only need to know what 1-dimensional means for this to work.

In so far as defining trace is concerned, if one accepts that there is a way of defining determinants that doesn't involve defining bases (say, by using the top exterior power) then one can equally well define trace by differentiating the determinant:

$$\frac{\det(I + tA) - 1}{t} \to \operatorname{Tr} A$$

Basically, choosing a basis is evil and should only be done when no-one is watching you and with proper precautions. More seriously, my answer to the original question "when to choose a basis" is:

1. When you need to do a computation (as Greg says)
2. When you want to convince yourself that a particular result is true before setting about the task of finding an elegant proof thereof.

Edit: I've thought of two more reasons to choose a basis:

1. When the question is already evil.
2. To avoid complicated convergence issues in Hilbert spaces: basically (pardon the pun), it's really easy to see when a sequence in which the terms are pairwise orthogonal converges so orthonormal bases (and orthonormal families) allow one to separate out the messy convergence from the elegant geometry.
-

Just to throw an idea out (where it will no doubt sink forlornly) - the first proof I was ever shown that the Fourier transform on L^1(R) has a unique continuous extension to a unitary operator on L^2(R) was done by checking on appropriate eigenfunctions (i.e., a basis was chosen for L^2(R)).

None of this gainsays the remarks above about avoiding a choice of basis; I would only say (as I think people already have hinted) that when judiciously chosen, bases can be rather useful.

(I also get the impression in the study of classical Banach spaces that, in addition to the general coordinate-free principles of linear functional analysis, you really have to hack around with bases.)

-

I agree with Elizabeth's answer and Brian Conrad's philosophy: avoid bases in theorem statements if possible, and use them sparingly for proofs.

More generally, when a definition of something says "something exists" (like a finite basis!), then at some point in your theory you'll essentially have to "choose" one of those things in order to complete a proof.

The definition of "finite-dimensional" means "a finite basis exists", so there's really no way around it. To illustrate this, we could work with "finite length as a k-module" as an alternative equivalent definition of finite dimensional vector space, but this just means "A finite maximal chain of vector subspaces exists," and what you find is that somewhere early in the foundations you have to "choose" such a chain in order complete a proof.

Edit: I'm not suggesting here that there are no equivalent characterizations of finite dimensional vector spaces; rather, I'm claiming that proving some of the properties of finite-dimensional vector spaces will involve the existence of "choices" in some way or another (as a trivial example, the property of having a finite basis). Of course making this claim rigorous and proving it would be a lot of work, but unfortunately I think the same is true for its negation.

-
I strongly disagree with the last paragraph, especially with the “there's really no way around it” part. There are many ways to define finite-dimensionality without ever mentioning bases. One can say that the canonical embedding V → V** is an isomorphism. Equivalently one can say that a vector space is finite-dimensional if it is fully dualizable (i.e., there are maps V ⊗ V* → k and k → V* ⊗ V with the obvious properties). And one does not need to “choose” anything because all maps are completely canonical. – Dmitri Pavlov Nov 10 2009 at 18:01
Are you sure about that? Although the properties you mention are provably equivalent to having a basis, certainly not every consequence of having a finite basis follows formally from these abstract definitions without choosing a basis (or doing something extremely similar to it). An easy example is the consequence of having a finite basis itself. – Andrew Critch Nov 10 2009 at 20:20
Your last example explicitly mentions bases and sounds a bit like a tautology to me. How you can choose a (finite) basis without choosing a (finite) basis? If one interprets your question as referring to the proof of the fact that the commutative rig of isomorphism classes of finite-dimensional vector spaces is isomorphic to the rig of natural numbers, then this can be done without using bases. – Dmitri Pavlov Nov 11 2009 at 20:34
There is also an interesting fact that the free vector space functor from the category of finite sets with matrices as morphisms to the category of finite-dimensional vector spaces is essentially surjective and fully faithful. However, to construct the inverse functor we must use some form of the axiom of choice. (I think that the existence of the inverse functor is actually equivalent to some weak form of the axiom of choice.) Thus if one interprets your question this way then we can prove that we must make some arbitrary choice (i.e., the choice of a basis for every vector space). – Dmitri Pavlov Nov 11 2009 at 20:40
Existence of basis for arbitrary vector space is equivalent to the axiom of choice, the proof can be found in Herrlich's book. I think it might be adapted to this case, but I am not sure about this. One must also be careful to distinguish different variants of the category of matrices. For example, the free vector space functor defined on the category of natural numbers and matrices is essentially surjective and fully faithful, and the existence of its inverse implies the axiom of choice for families of finite sets. I am not sure how to adapt this construction to finite sets and matrices. – Dmitri Pavlov Nov 12 2009 at 14:42
show 1 more comment

Let K be a field and V a K-vector space of infinite dimension (some infinite cardinal). Then the dual V* of V has dimension [which is much bigger than , and in particular proves that V* is not isomorphic to V].

This is stated by Bourbaki in his Algebra I, Chapters 1-3 , Exercise 3 for Chapter 2 §7, page 400 (the reference is to Springer's English translation), where the result is attributed to Erdös-Kaplansky.

In the hints to this exercise, Bourbaki makes heavy use of bases (but what is dimension anyway ?) and this might be relevant to Steve's question.

-