Gram-Schmidt Calculator

Welcome to the Gram-Schmidt calculator, where you'll have the opportunity to learn all about the Gram-Schmidt orthogonalization. This simple algorithm is a way to read out the orthonormal basis of the space spanned by a bunch of random vectors. If you're not too sure what orthonormal means, don't worry! It's just an orthogonal basis whose elements are only one unit long. And what does orthogonal mean? Well, we'll cover that one soon enough!

So, just sit back comfortably at your desk, and let's venture into the world of orthogonal vectors!

One of the first topics in physics classes at school is velocity. Once you learn the magical formula of $v = s / t$, you open up the exercise book and start drawing cars or bikes with an arrow showing their direction parallel to the road. The teacher calls this arrow the velocity vector and interprets it more or less as "the car goes that way."

You can find similar drawings throughout all of physics, and the arrows always mean which direction a force acts on an object and how large it is. The scenario can describe anything from buoyancy in a swimming pool to the free fall of a bowling ball, but one thing stays the same: whatever the arrow is, we call it a vector.

In full (mathematical) generality, we define a vector to be an element of a vector space. In turn, we say that a vector space is a set of elements with two operations that satisfy some natural properties. Those elements can be quite funky, like sequences, functions, or permutations. Fortunately, for our purposes, regular numbers are funky enough.

A Cartesian space is an example of a vector space. This means that a number, as we know them, is a (1-dimensional) vector space. The plane (anything we draw on a piece of paper), i.e., the space a pairs of numbers occupy, is a vector space as well. And lastly, so is []the 3-dimensional space of the world we live in, interpreted as a set of three real numbers.

When dealing with vector spaces, it's important to keep in mind the operations that come with the definition: addition and multiplication by a scalar (a real or complex number. Let's look at some examples of how they work in the Cartesian space.

In one dimension (a line), vectors are just regular numbers, so adding the vector $2$ to the vector $-3$ is just

Similarly, multiplying the vector $2$ by a scalar, say, by $0.5$ is just regular multiplication:

In two dimensions, vectors are points on a plane, which are described by pairs of numbers, and we define the operations coordinate-wise. For instance, if $\vec A = (2,1)$ and $\vec B = (-1, 7)$, then

Similarly, if we want to multiply $\vec A$ by, say, 1/2, then

As a general rule, the operations described above behave the same way as their corresponding operations on matrices. After all, vectors here are just one-row matrices. Additionally, there are quite a few other useful operations defined on Cartesian vector spaces, like the cross product. Fortunately, we don't need that for this article, so we're happy to leave it for some other time, aren't we?

Now, let's distinguish some very special sets of vectors, namely the orthogonal vectors and the orthogonal basis.

Intuitively, to define orthogonal is the same as to define perpendicular. This suggests that the meaning of orthogonal is somehow related to the 90-degree angle between objects. And this intuitive definition does work: in two- and three-dimensional spaces, orthogonal vectors are lines with a right angle between them.

But does this mean that whenever we want to check if we have orthogonal vectors, we have to draw out the lines, grab a protractor, and read out the angle? That would be troublesome... And what about 1-dimensional spaces? How to define orthogonal elements there? Not to mention the spaces of sequences. What does orthogonal mean in such cases? For that, we'll need a new tool.

The dot product (also called the scalar product) of two vectors $\vec v = (a_1, a_2, a_3,..., a_n)$ and $\vec w = (b_1, b_2, b_3,..., b_n)$ is the number $v\cdot w$ given by:

Observe that indeed the dot product is just a number: we obtain it by regular multiplication and addition of numbers. With this tool, we're now ready to define orthogonal elements in every case.

We say that $\vec v$ and $\vec w$ are orthogonal vectors if $\vec v \cdot \vec w = 0$. For instance, if the vector space is the one-dimensional Cartesian line, then the dot product is the usual number multiplication: $\vec v \cdot \vec w = |\vec v| \times |\vec w|$. So what does orthogonal mean in that case? Well, the product of two numbers is zero if, and only if, one of them is zero. Therefore, any non-zero number is orthogonal to $0$ and nothing else.

Now that we're familiar with the meaning behind orthogonal let's go even deeper and distinguish some special cases: the orthogonal basis and the orthonormal basis.

Let $\vec v_1$, $\vec v_2$, $\vec v_3$,..., $\vec v_n$ be some vectors in a vector space. Every expression of the form

where $\alpha_1$, $\alpha_2$, $\alpha_3$,..., $\alpha_n$ are some arbitrary real numbers is called a linear combination of vectors. The space of all such combinations is called the span of $\vec v_1$, $\vec v_2$, $\vec v_3$,..., $\vec v_n$.

Think of the span of vectors as all possible vectors that we can get from the bunch. A keen eye will observe that, quite often, we don't need all $n$ of the vectors to construct all the combinations. The easiest example of that is when one of the vectors is the zero vector (i.e., with zeros on every coordinate). What good is it for if it stays as zero no matter what we multiply it by, and therefore doesn't add anything to the expression?

A slightly less trivial example of this phenomenon is when we have vectors $\vec e_1 = (1,0)$, $\vec e_2 = (0,1)$, and $\vec v = (1,1)$. Here we see that $\vec v = \vec e_1 + \vec e_2$ so we don't really need $v$ for the linear combinations since we can already create any multiple of it by using $\vec e_1$ and $\vec e_2$.

All the above observations are connected with the so-called linear independence of vectors. In essence, we say that a bunch of vectors are linearly independent if none of them is redundant when we describe their linear combinations. Otherwise, as you might have guessed, we call them linearly dependent. You can explore this concept in depth at the linear independence calculator and the related angle between two vectors calculator!

Finally, we arrive at the definition that all the above theory has led to. The maximal set of linearly independent vectors among a bunch of them is called the basis of the space spanned by these vectors. We can determine linear dependence and the basis of a space by considering the matrix whose consecutive rows are our consecutive vectors and calculating the rank of such an array.

For example, from the triple $\vec e_1$, $\vec e_2$, and $\vec v$ above, the pair $\vec e_1$, $\vec e_2$ is a basis of the space. Note that a single vector, say e₁, is also linearly independent but it's not the maximal set of such elements.

Lastly, an orthogonal basis is a basis whose elements are orthogonal vectors to one another. Who'd have guessed, right? And an orthonormal basis is an orthogonal basis whose vectors are of length $1$.

So how do we arrive at an orthonormal basis? Well, how fortunate of you to ask! That's exactly what the Gram-Schmidt process is for, as we'll see in a second.

The Gram-Schmidt process is an algorithm that takes whatever set of vectors you give it and spits out an orthonormal basis of the span of these vectors. Its steps are:

1. Take vectors $\vec v_1$, $\vec v_2$, $\vec v_3$,..., $\vec v_n$, whose orthonormal basis you'd like to find.

2. Take $\vec u_1 = \vec v_1$ and set $\vec e_1$ to be the normalization of $\vec u_1$ (the vector with the same direction but of length $1$).

3. Take $\vec u_2$ to be the vector orthogonal to $\vec u_1$ and set $\vec e_2$ to be the normalization of $\vec u_2$.

4. Choose $\vec u_3$ so that $\vec u_1$, $\vec u_2$, and $\vec u_3$ are orthogonal vectors, and set $\vec e_3$ to be the normalization of $\vec u_3$.

5. Repeat the process vector by vector until you run out of vectors, motivation, or time before something interesting is on the TV.

6. The non-zero $\vec e_i$'s are your orthonormal basis.

Now that we see the idea behind the Gram-Schmidt orthogonalization, let's try to describe the algorithm with mathematical precision.

First of all, let's learn how to normalize a vector. To do this, we simply multiply our vector by the inverse of its length, which is usually called its magnitude: you can learn how to calculate it at Omni's vector magnitude. For a vector $\vec v$ we often denote its length by $|\vec v|$ (not to be confused with the absolute value of a number!) and calculate it by:

i.e., the square root of the dot product with itself. For instance, if we'd want to normalize $\vec v = (1,1)$, then we'd get

Next, we need to learn how to find the orthogonal vectors of whatever vectors we've obtained in the Gram-Schmidt process so far. Again, dot product comes to help out.

If we have vectors $\vec u_1$, $\vec u_2$, $\vec u_3$,..., $\vec u_k$, and would like to make $\vec v$ into an element $\vec u$ orthogonal to all of them, then we apply the formula:

With this, we can rewrite the Gram-Schmidt process in a way that would make mathematicians nod and grunt their approval.

1. Take vectors $\vec v_1$, $\vec v_2$, $\vec v_3$,..., $\vec v_n$ whose orthonormal basis you'd like to find.

2. Take $\vec u_1 = \vec v_1$ and set $\vec e_1 = (1 / |\vec u_1|) \cdot \vec u_1$.

3. Take $\vec u_2 = \vec v_2 - [(\vec v_2 \cdot \vec u_1)/(\vec u_1 \cdot \vec u_1)] \cdot u_1$, and set $\vec e_2 = (1 / |\vec u_2|) \cdot u_2$.

4. Take $\vec u_3 = \vec v_3 - [(\vec v_3 \cdot \vec u_1)/(\vec u_1 \cdot \vec u_1)] \cdot u_1$, and set $\vec e_3 = (1 / |\vec u_3|) \cdot \vec u_3$.

5. Repeat the process vector by vector until you run out of vectors, motivation, or patience before finding out what happens next in the novel you're reading.

6. The non-zero $\vec e_i$'s are your orthonormal basis.

Arguably, the Gram-Schmidt orthogonalization contains only simple operations, but the whole thing can be time-consuming the more vectors you have.

Alright, it's been ages since we last saw a number rather than a mathematical symbol. It's high time we had some concrete examples, wouldn't you say?

Say that you're a huge Pokemon GO fan but have lately come down with the flu and can't really move that much. Fortunately, your friend decided to help you out by finding a program that you plug into your phone to let you walk around in the game while lying in bed at home. Pretty cool, if you ask us.

The only problem is that in order for it to work, you need to input the vectors that will determine the directions in which your character can move. We are living in a 3-dimensional world, and they must be 3-dimensional vectors. You close your eyes, roll the dice in your head, and choose some random numbers: $(1, 3, -2)$, $(4, 7, 1)$, and $(3, -1, 12)$.

"Error! The vectors have to be orthogonal!" Oh, how troublesome... Well, it's a good thing that we have the Gram-Schmidt calculator to help us with just such problems!

We have $3$ vectors with $3$ coordinates each, so we start by telling the calculator that by choosing the appropriate options under "Number of vectors" and "Number of coordinates." This will show us a symbolic example of such vectors with the notation used in the Gram-Schmidt calculator. For instance, the first vector is given by $\vec v = (a_1, a_2, a_3)$. Therefore, since in our case the first one is $(1, 3, -2)$ we input:

Similarly for the two other ones we get:

And:

Once we input the last number, the Gram-Schmidt calculator will spit out the answer. Unfortunately, just as you were about to see what it was, your phone froze. Apparently, the program is taking too much space, and there's not enough for the data transfer from the sites. When it rains, it pours... Oh well, it looks like we'll have to calculate it all by hand.

Let's denote our vectors as we did in the above section: $\vec v_1 = (1, 3, -2)$, $\vec v_2 = (4, 7, 1)$, and $\vec v_3 = (3, -1, 12)$. Then, according to the Gram-Schmidt process, the first step is to take $\vec u_1 = \vec v_1 = (1, 3, -2)$ and to find its normalization:

Next, we find the vector $\vec u_2$ orthogonal to $\vec u_1$:

and normalize it:

Lastly, we find the vector $\vec u_3$ orthogonal to both $\vec u_1$ and $\vec u_2$:

Oh no, we got the zero vector! That means that the three vectors we chose are linearly dependent, so there's no chance of transforming them into three orthonormal vectors... Well, we'll have to change one of them a little and do the whole thing again.