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!
What is a vector?
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.
Cartesian vector spaces
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
2 + (-3) = -1.
Similarly, multiplying the vector
2 by a scalar, say, by
0.5 is just regular multiplication:
0.5 * 2 = 1.
Note that the numbers here are very simple, but, in general, can be anything that comes to mind. Even the pesky
π from circle calculations.
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
A = (2,1) and
B = (-1, 7), then
A + B = (2,1) + (-1,7) = (2 + (-1), 1 + 7) = (1,8).
Similarly, if we want to multiply
A by, say,
½ * A = ½ * (2,1) = (½ * 2, ½ * 1) = (1,½).
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.
What does orthogonal mean?
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
v = (a₁, a₂, a₃,..., aₙ) and
w = (b₁, b₂, b₃,..., bₙ) is the number
v ⋅ w given by
v ⋅ w = a₁*b₁ + a₂*b₂ + a₃*b₃ + ... + aₙ*bₙ.
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
w are orthogonal vectors if
v ⋅ w = 0. For instance, if the vector space is the one-dimensional Cartesian line, then the dot product is the usual number multiplication:
v ⋅ w = v * 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.
Orthogonal and orthonormal basis
vₙ be some vectors in a vector space. Every expression of the form
𝛼₁*v₁ + 𝛼₂*v₂ + 𝛼₃*v₃ + ... + 𝛼ₙ*vₙ
𝛼ₙ are some arbitrary real numbers is called a linear combination of vectors. The space of all such combinations is called the span of
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
e₁ = (1,0),
e₂ = (0,1), and
v = (1,1). Here we see that
v = e₁ + e₂ so we don't really need
v for the linear combinations since we can already create any multiple of it by using
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.
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
v above, the pair
e₂ 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
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.
Gram-Schmidt orthogonalization process
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:
- Take vectors
vₙwhose orthonormal basis you'd like to find.
u₁ = v₁and set
e₁to be the normalization of
u₁(the vector with the same direction but of length
u₂to be the vector orthogonal to
e₂to be the normalization of
u₃are orthogonal vectors, and set
e₃to be the normalization of
- Repeat the process vector by vector until you run out of vectors, motivation, or when time before something interesting is on the TV.
- The non-zero
e'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. For a vector
v we often denote its length by
|v| (not to be confused with the absolute value of a number!) and calculate it by
|v| = √(v ⋅ v),
i.e., the square root of the dot product with itself. For instance, if we'd want to normalize
v = (1,1), then we'd get
u = (1 / |v|) * v = (1 / √(v ⋅ v)) * (1,1) = (1 / √(1*1 + 1*1)) * (1,1) =
= (1 / √2) * (1,1) = (1/√2, 1/√2) ≈ (0.7,0.7).
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
uₖ, and would like to make
v into an element
u orthogonal to all of them, then we apply the formula:
u = v - [(v ⋅ u₁)/(u₁ ⋅ u₁)] * u₁ - [(v₂ ⋅ u₂)/(u₂ ⋅ u₂)] * u₂ - [(v ⋅ u₃)/(u₃ ⋅ u₃)] * u₃ - ... - [(v ⋅ uₖ)/(uₖ ⋅ uₖ)] * uₖ.
With this, we can rewrite the Gram-Schmidt process in a way that would make mathematicians nod and grunt their approval.
- Take vectors
vₙwhose orthonormal basis you'd like to find.
u₁ = v₁and set
e₁ = (1 / |u₁|) * u₁.
u₂ = v₂ - [(v₂ ⋅ u₁)/(u₁ ⋅ u₁)] * u₁, and set
e₂ = (1 / |u₂|) * u₂.
u₃ = v₃ - [(v₃ ⋅ u₁)/(u₁ ⋅ u₁)] * u₁ - [(v₃ ⋅ u₂)/(u₂ ⋅ u₂)] * u₂, and set
e₃ = (1 / |u₃|) * u₃.
- 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.
- The non-zero
e'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. Oh, it feels like we've won the lottery now that we have the Gram-Schmidt calculator to help us!
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?
Example: using the Gram-Schmidt calculator
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!
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
v = (a₁, a₂, a₃). Therefore, since in our case the first one is
(1, 3, -2) we input
a₁ = 1,
a₂ = 3,
a₃ = -2.
Similarly for the two other ones we get:
b₁ = 4,
b₂ = 7,
b₃ = 1,
c₁ = 3,
c₂ = -1,
c₃ = 12.
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
v₁ = (1, 3, -2),
v₂ = (4, 7, 1), and
v₃ = (3, -1, 12). Then, according to the Gram-Schmidt process, the first step is to take
u₁ = v₁ = (1, 3, -2) and to find its normalization:
e₁ = (1 / |u₁|) * u₁ = (1 / √(1*1 + 3*3 + (-2)*(-2))) * (1, 3, -2) =
= (1 / √14) * (1, 3, -2) ≈ (0.27, 0.8, -0.53).
Next, we find the vector
u₂ orthogonal to
u₂ = v₂ - [(v₂ ⋅ u₁)/(u₁ ⋅ u₁)] * u₁ =
= (4, 7, 1) - [(4*1 + 7*3 + 1*(-2))/(1*1 + 3*3 + (-2)*(-2))] * (1, 3, -2) =
= (4, 7, 1) - (23/14) * (1, 3, -2) ≈ (4, 7, 1) - (1.64, 4.93, -3.29) =
= (2.36, 2.07, 4.29),
and normalize it:
e₂ = (1 / |u₂|) * u₂ = (1 / √(5.57 + 4.28 + 18.4)) * (2.36, 2.07, 4.29) ≈
≈ (0.44, 0.39, 0.8).
Lastly, we find the vector
u₃ orthogonal to both
u₃ = v₃ - [(v₃ ⋅ u₁)/(u₁ ⋅ u₁)] * u₁ - [(v₃ ⋅ u₂)/(u₂ ⋅ u₂)] * u₂ =
= (3, -1, 12) - [(3 + (-3) + (-24))/14] * (1, 3, -2) - [(7.08 + (-2.07) + 51.48)/28.26] * (2.36, 2.07, 4.29) =
= (3, -1, 12) + (12/7) * (1, 3, -2) - (56.49/28.26) * (2.36, 2.07, 4.29) ≈
≈ (0, 0, 0).
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.
Hmm, maybe it's time to delete some of those silly cat videos? After all, they do take a lot of space and, once they're gone, we can go back to the Omni Calculator website and use the Gram-Schmidt calculator.
Maybe we'll burn no calories by walking around, but sure enough, we will catch 'em all!