Theorem: Every non-zero Euclidean vector space V (with inner product I) has an orthonormal basis.

Lemma: Given an orthonormal system B := (b1, b2, ..., bk) in V and a vector a in V, the vector

P(a) := I(a,b1)*b1 + I(a,b2)*b2 + ... + I(a,bk)*bk

is a member of the span of B with the property that the vector a - P(a) is orthogonal to every vector in the span of B.

Proof of Lemma:
We must check that I(a-P(a), b)=0 for every b in the span of B. I will show that a-P(a) is orthogonal to each of the vectors in B, (b1, b2, ..., bk). The result follows directly.
For brevity, let ci := I(a,bi). Thus, P(a) = c1*b1+c2*b2+...+ck*bk.
Let some n in {1,2,...k} be given. By bilinearity of the inner product, we have

I(a-P(a), bn) = I(a,bn)-I(P(a),bn) = cn-I(c1*b1+c2*b2+...+cn*bn,bn) = cn-c1*I(b1,bn)-c2*I(b2,bn)-...-cn*I(bn,bn)

But since B is orthonormal, I(bi,bj) = 0 if i is different from j, and I(bi,bi)=1, so we have:
I(a-P(a),bn) = cn-cn = 0.

Proof of Theorem:
Since V is not zero, we may choose a unit vector b1 (i.e. choose b1 such that I(b1,b1)=1). If V = span of (b1), then B := b1 is an orthonormal basis for V. Otherwise, we may choose a vector a' not in the span of (b1), and by the lemma, we may construct from a' a vector b2 such that (b1, b2) is orthonormal. Continuing in this way, construct b3, b4,...,bn where n=dim V. By the definition of dimension, we may choose a basis B':=(b'1,b'2,...,b'n) which, of course, spans V. By the Steinitz Exchange Lemma (see Noether's Dimension of a Vector Space writeup for proof), B must also span V. Thus, B is an orthonormal basis for V.


Cool Man Eddie just told me this writeup had been C!'ed, so I came back to look at it, and, to be honest, I was as struck by the gruesome formula-filled proof as it seems rp was. The above proof is valid, but, as Yuri Prime mentions below, not very informative/illuminating, especially for someone who didn't already know basic ideas behind the proof. Yuri's writeup below has what mine lacks (i.e. a conceptual explanation), and s/he's done a better job with that than I ever could.

Hmm, formulas. I guess that's good. After all, formulas are what mathematics is all about, aren't they?

Still, I prefer to read stories. I'll tell you my story on this theorem: how to spoil geometry.

You see, in primary school I thought learning was all about concepts and principles. You can say I had a Platonic mind. I knew how to add and subtract before I went to school; it may have taken me a short while to understand the principle of multiplication and that of division; I completely missed the point of having to practise these things for years on end. The ideas of mistakes and of acquiring skills were unknown to me. As soon as I thought I understood something, I would simply stop and refuse to do any more exercise on the subject.

So mathematics was incredibly boring. I remember asking my uncle whether there was a 'next step' that is to multiplication and division as they are to addition and subtraction, and he explained exponentiation and square roots to me. Since I remember the occasion, I can put a date to it and I realise I was 8 at the time. It was years before we ever heard of these things in school. Looking back, I was fascinated by mathematical laws, but bored stiff by calculations.

(Sorry, this self-rant was reserved for the unfinished school algebra writeup and some of it should move to my home node. I'll reorganise it when I have more time.)

So imagine my delight when in sixth grade - I was 11 - the world of Euclidean geometry was unfolded to us. Looking back, the exercises in geometry - proving theorems about triangles, lines, circles, etcetera - are easily my favourite subject among everything we ever learnt in school, including high school. It's not that I was particularly good at it, but abstract mathematics was my favourite subject. Why oh why does 99% of all mathematics have to consist of the hard and boring manual labour, the calculations! I hate calculations! I can't be bothered, and even when I try, I'm too sloppy to ever do them right.

In high school, the pattern continued: in mathematics and physics, some fundamental laws and their relationships would be introduced, after which you would get weeks, months or even years of exercises doing mindless calculations with those rules. Where was the insight? There was no place for that. After a while I became convinced that the calculations were the essence of physics, that my idea of 'insight' was a stupid romantic craving I had to shake off. Thanks to our teachers and books, I didn't leave school with the same feeling about mathematics: they never made me forget about the incredible world of pure and undiluted ideas that is in there, and I realized there would be more space for them in university, but, pathetic as I was at calculations, I didn't have the guts to study mathematics.

But in the first two years of high school, algebra and geometry almost had equal time. The algebra part - calculations calculations calculations - was just boring routine, but there was the wonderful part, the part that everybody else hated, the geometry - proving theorems, discovering things, using your imagination! (I think they no longer teach geometry in high school. Abstract thought is no longer considered a tenable goal of teaching these days.)

So what happened to geometry? They turned it into algebra! It's straightforward: you map out your geometrical objects in n-dimensional space, write down all the numbers you can think of, calculate, and the answer will appear. There's no need for your fancy theorem proving, just do the math, stupid!

Now read the theorem above, because this is what it says, albeit in formal mathematical terms: if a problem is subject to the laws of Euclidean geometry, it can be mapped out into an n-dimensional Cartesian coordinate system where the laws of linear algebra apply, and you can just 'do the math'.

It's not fair! Where did the abstract thinking go! Why does everything have to be boring calculations in the end! Mommy, they are cheating on me!

I'm exaggerating, of course: the abstract mathematics of algebra is just as rich and fascinating as geometry, intelligence and insight can be of use in doing proper calculations, and without any level of proficiency, without mastery of basic skills, you probably won't make much progress in understanding abstract theory. So there really isn't a full opposition between 'pure ideas' and 'do the math' in the way that I felt at the time. And I was aware of that, but it left me feeling sour with the exact subjects, and disappointed with my own abilities, and I never really recovered from that.

Don't get me wrong, I'm not blaming Gram or Schmidt for my problems with mathematics in highschool. You can't blame truth! Actually, we're dealing with a beautiful and useful principle. But it is a principle that more than anything else represents the loss of my faith in my own mathematical abilities.

If you're still here, I've been trying to convince you that mathematics is more than formulas: these formulas actually mean something - not just in an objective sense, but even in a personal sense. This is true for brillant and famous mathematicians - read Simon Singh's account of the story of Andrew Wiles and Fermat's Last Theorem - but also for the pathetic whiners who never even tried - as this writeup tries to explain.

Come on, rp, that's a bit of a violent objection. Admittedly, the above proof isn't very illuminating, but what you need to do when looking at reasoning presented in this manner is to spend a moment to work out what it's actually saying, and then rebuild your concepts and understanding from this.

Firstly the lemma isn't very important (although symbolically it accounts for most of the proof) - it just states a property of orthonormal bases that we (mathematicians) wanted to be true anyway (otherwise they'd not be of much use): you can expand any vector out over an orthonormal basis in a way that the coefficients come out to be about the simplest possible thing they could be. In fact, the lemma, when extended to Hilbert Spaces, makes good intuitive sense in The Dirac Formalism of Quantum Mechanics.

Now, as for the theorem (which, incidentally, some people prefer to call an algorithm): it says that if you take a bunch of linearly independent vectors that span a space (a basis), you can convert it into one where they're all at right angles. Firstly, imagine you're just doing this with a pair of vectors (a and b) to form a pair of vectors at right angles (u and v). You can take one of them as it is (u = a, divided by its length since we wanted an orthonormal basis), and construct the other by starting with b and taking away its component which is in the direction of a (I(a,b) a in thax' notation): i.e., v = b - I(b,a) a (again, now divide v by its length). Also, because the original vectors were LI, this guarantees that w is not zero. Makes sense, yeah?

But we were doing this in n dimensions, of course. So we start with vectors (a,b,c...) and want to end up with (u,v,w...). (I know I will run out of alphabet, but I don't know how to do subscripts.) We find u and v in exactly the same way as before. As for w, we have to take away the components in the directions of both u and v, and so now w = c - I(c,b) b - I(c,a) a (...divided by its length). At this point I think you'll be able to guess the general formula, so I'll say et cetera at this point. Note again that in every case the linear independence of the original vectors ensures that none of the new vectors is zero, and indeed they are LI themselves.

Now have another look back at the above proof: it says exactly the same thing!

After going through reasoning like this in such a carefree manner, it's a good idea to have another look over it and see how each of the assumptions in the statement of the Theorem was used:

  • The non-zero space part is a bit of a formality really.
  • Euclidean vector space: we wanted a space in which the concept of length was meaningful.
  • We needed the inner product to compute the lengths. Technically, we also need it to be non-degenerate to prevent (say) distances being measured in 3-space by distances when projected onto some plane, so length means what we think it means.
  • Non-degenerate: we divided by lengths, so didn't want any of them to be zero when they ought not to be.

...and then note that each of these appeared in the reasoning I gave. All is well.

I personally find it fascinating how very advanced and abstract mathematical arguments tie in with the mental ideas that are used to produce and subsequently understand them. The way I see it the frustration you are expressing above is at the way it is taught - all rigour and formalism but no conceptual meaning (lecturers of my degree course are particularly guilty of this).

In saying all this I'm not in favour of arm waving proofs; I'm saying that understanding and intellectual rigour complement each other, and should be taught in this way.

Post script: much though I try, I can't come up with a way of doing this for every theorem I encounter!

Log in or register to write something here or to contact authors.