Linear algebra in a nutshell

Matt Helm

Part I. Vectors & scalars

To understand vectors and scalars, let's look at the definition of a vector space from Wikipedia:

A vector space (also called a linear space) is a collection of objects called vectors, which may be added together and multiplied ("scaled") by numbers, called scalars. Scalars are often taken to be real numbers, but there are also vector spaces with scalar multiplication by complex numbers, rational numbers, or generally any field.

Let's start by looking at a graph of a two-dimensional vector space along with a vector originating from the origin. The vector below can be represented as

where the first element in the vector represents the value of the end point and the second element represents the value of the end point.

We can see that our vector is simply a list of numbers. And because it is just a list of numbers, we can represent all sorts of things as vectors. The vectors below hold the red, green, and blue (RGB) values for the particular shades displayed beside them:

We could also use a vector to represent the prices of three homes, in thousands:

Or the attributes of a car — perhaps miles per gallon, the number of doors, and the price in thousands:

So far we have been writing our vectors as column vectors, stacked vertically. We can also write them as row vectors, horizontally, like this: . That distinction will matter once we get to matrices.

Scalars

Vectors can be scaled by multiplying them by values called scalars. Multiply the vector below by a scalar and watch what happens to it:

We are simply multiplying each element of the vector by the scalar. What is interesting is that when the scalar is positive, the only thing that changes is the vector's length — we are literally scaling it up or down. When the scalar is negative, the vector points in the opposite direction, and its length is scaled by the scalar's absolute value. When the scalar is zero, the vector collapses to a point at .

What about the vectors that represented colors? Here is what scaling does to one of them:

Both vectors contain only one non-zero value, the red channel. So as we scale the vector up, only the red value increases, resulting in an increasingly red color.

Vector addition & subtraction

Below are two vectors along with their sum. At first glance it might not be obvious how adding the blue and orange vectors produces the green one. But watch what happens when, instead of drawing the orange vector from the origin, we slide it so that it starts at the tip of the blue vector:

Slid all the way over, the orange vector ends exactly where the green one does. It doesn't matter which vector you start with — start with the orange one and lay the blue one on its tip and you land in the same place, because vector addition is commutative, just like ordinary addition.

Subtraction works exactly as you would expect, element by element. Geometrically, is the same as , so we can slide the reversed orange vector onto the tip of the blue one:

There is a second, very useful way to read the green vector: is the arrow that points from the tip of to the tip of . That reading is what makes the distance formula, coming up shortly, feel natural.

Let's do the same with colors. Suppose we want to add some red to a color represented by the vector . We add a vector holding a positive red value and zeros for green and blue:

Here : we used vector addition to push the original color toward red. Subtracting from takes us right back to .

Norm

Here we will explore only the Euclidean norm, though it is worth knowing that there is also a Manhattan norm (the sum of the absolute values of the entries). The Euclidean norm — from here on just the norm — is defined as

A vector's norm can be thought of as its length:

The dashed legs make it clear that the norm in this example is nothing more than the Pythagorean theorem.

Distance

We can use the norm to define the Euclidean distance between two vectors:

This is exactly the "arrow from tip to tip" reading of subtraction: the distance between two vectors is the length of the arrow joining their tips. Revisiting the vectors from the addition example, while . The sum is closer to than the original is — scroll back to that plot and see whether it matches your eye.

Now the same idea with colors:

Which of these do you expect to be closest to red? Does orange look closer to red than green does? Let's compute:

Indeed, is closer to than is.

When distance needs a change of units

In the examples above we used the vectors as they came, which is fine when every element is measured in the same unit. When a vector mixes units, the element with the largest numbers quietly dominates the distance, so we usually standardize first.

Here are three houses described by square footage, number of bedrooms, and price in thousands. Flip the switch to replace each raw measurement with its z-score:

Untouched, the square-footage figures do nearly all of the work: house 2 comes out more than twice as close to house 1 as house 3 does. But look at what those numbers describe. Houses 1 and 3 are the two four-bedroom homes, and they are priced within $8,000 of each other; house 2 is a two-bedroom listed $45,000 to $53,000 below them. The only thing making it look like a close match is that its floor area happens to be nearer — and floor area is measured in numbers so much larger than the others that it swamps them.

Now standardize each feature across the three houses: subtract that feature's mean, divide by its standard deviation. Every feature is then measured in standard deviations rather than square feet or dollars, so no feature can dominate by units alone — and the ranking flips. House 3 is now the closer of the two, by a comfortable margin.

Dot product

The dot product of two vectors is defined as

This very simple operation lets us do some surprisingly interesting things.

Suppose we have a vector of product prices and a vector of quantities. The dot product is the total cost:

Or suppose holds the probabilities of some events whose payoffs are held in . Then the expected value is the dot product :

Angles & orthogonality

We can also recover the angle (written , "theta") between two vectors by dividing their dot product by the product of their norms and taking the inverse cosine:

Swing the second vector around and watch the dot product:

When the angle between two vectors is the vectors are said to be orthogonal — and, as the readout shows, that happens exactly when their dot product is zero. In symbols:

which says that the dot product of and is zero exactly when and are orthogonal.

Finding a vector orthogonal to a given one in 2-D takes nothing more than the dot product and a line of algebra. Given

set up and solve for :

There are infinitely many solutions — every scalar multiple of one another — so let's pick and . That gives a dot product of zero, and reproduces the orthogonal pair from the plot above.

Cross product

The cross product is another way to multiply two vectors, defined for vectors in three dimensions. Rather than a scalar, it yields a brand-new vector that is orthogonal to both of the vectors being multiplied. First, a definition: a unit vector is simply a vector of length 1. With that in hand,

where is a unit vector at right angles to both and , and is the angle between them. There are two such unit vectors, pointing in opposite directions; is the one given by the right-hand rule (curl the fingers of your right hand from toward , and your thumb points along ). Spin the camera to see it:

The result really is orthogonal to both and : its dot product with each of them is zero. Its length is worth noticing too. Here and are perpendicular vectors, each of length , so — which is exactly the area of the square they span. That holds in general: the length of the cross product is the area of the parallelogram formed by the two vectors.

Linear combinations & linear independence

From StatTrek:

If one vector is equal to the sum of scalar multiples of other vectors, it is said to be a linear combination of the other vectors. For example, suppose , as shown below. Note that 2b is a scalar multiple and 3c is a scalar multiple. Thus, a is a linear combination of b and c.

Take the two vectors from the addition example and dial in your own coefficients. Every point you can reach is a linear combination of and ; the faint lattice shows where a grid of other coefficient pairs would land:

With we get , the green vector from the addition plot — so that vector is a linear combination of and .

But what about and themselves? Can we obtain from alone? No — all we can do to by itself is scale it, and no scaling of ever lands on . When neither vector can be built from the other, we say they are linearly independent.

Here is the opposite case. These two vectors are linearly dependent, because either one can be obtained by scaling the other:

Confirm it visually by changing the scalar:

Now let's think about linear independence in terms of color vectors. Start with red, blue, and purple:

This set is linearly dependent, because the purple vector is a linear combination of the red and blue ones:

Let's swap purple for yellow and see what happens:

This set is linearly independent: none of the three can be built from a combination of the other two, because nothing here supplies the green in yellow. In the section on matrices we will see a couple of ways to check that mechanically.

Span & basis

Now that we understand linear combinations and linear independence, span and basis follow easily. Consider the set :

The span of this set is the set of all finite linear combinations of its elements. So what are all of those combinations? Let's start with four arbitrary ones:

Each of the four new vectors lands in a different quadrant. That is a hint: with this set, can we reach the entire plane?

As it turns out, the span of any two non-parallel vectors in a two-dimensional space is indeed the whole plane. We don't even need , since is already a linear combination of the other two.

Another way to say this is that and form a basis for the span of . A basis is a set of linearly independent vectors that spans the space — enough vectors to reach everything, and not one more than necessary.

Let's give and a third component and plot them in three-dimensional space:

The idea of span is much easier to see here. Two independent vectors in three dimensions span a plane — not the whole space. To span all of you would need a third vector that lies off this plane.

Orthonormal vectors

A set of vectors is orthonormal if every vector in it is orthogonal to all of the others and each one is a unit vector. If the set also forms a basis, it is an orthonormal basis. The three vectors below satisfy both conditions — they are the standard basis of :

Part II. Matrices

Now that we understand vectors, understanding matrices will be much easier. In fact, a vector is a matrix — one with a single column (or a single row). To see this, let's look at a matrix that we'll call :

Our matrix is a matrix because it has 2 rows and 3 columns. In Part I we learned that vectors can be written as row vectors or column vectors: a row vector is a matrix and a column vector is an matrix.

Just as vectors can stand in for any number of things, so can matrices. In fact, matrices are often just collections of vectors, as we'll see shortly.

Transpose

When we transpose a matrix, we simply reflect it across its diagonal — rows become columns. The transpose of , written or , is:

Our matrix is now a matrix. Transposing a row vector turns it into a column vector, and vice versa.

Norm

We can compute the norm of a matrix as

which, as with vectors, is just the square root of the sum of the squares of its entries. (This is called the Frobenius norm; matrices have other norms too, but this is the one we'll use.) For example,

Matrix addition

We can add two matrices of the same dimensions by summing their corresponding elements:

Scalar multiplication

Just as with vectors, we can multiply a matrix by a scalar:

Matrix-matrix multiplication

We can multiply a matrix by another matrix as long as their dimensions are compatible: to perform , the number of columns in must equal the number of rows in . In general

So we can multiply a matrix by a matrix, which gives a result. We could not multiply

because both are : the 3 columns of don't match the 2 rows of . Note also that, unlike multiplication of ordinary numbers, matrix multiplication is not commutative: in general .

Every entry of the product is a dot product — row of with column of . Pick an entry to see which row and column produce it:

Written out in full, that is

Matrix-vector multiplication

Given that vectors are matrices, we can multiply a matrix by a vector too. With

the dimensions are compatible, so

This result is worth staring at. Multiplying a 3-vector by produced a vector with only 2 entries. In general . What does that look like geometrically?

The result has no value: it needs only a 2-D space to live in. The multiplication transformed our vector from a 3-vector into a 2-vector. For this particular , the result happens to be with its value dropped, so if you imagine shining a light from underneath the blue vector, the orange one is the shadow it casts. That is a coincidence of this example, though: doesn't simply drop the value of every vector (it sends to , for instance).

This should be a small revelation. The matrix is acting like a function on our vector. In function notation we would write : a vector-valued function that takes a 3-vector and returns a 2-vector, represented by the matrix , with .

Let's look at some more geometric transformations we can get this way. In each plot below the faint grid shows what happens to the whole plane, not just to .

Dilation. Suppose we have the following diagonal matrix , and multiply where :

This transformation stretched the vector upward: it is longer than before and stands at a steeper angle.

Rotation. Suppose we have a matrix defined as

where is an angle in radians. Multiplying rotates by :

At radians (90 degrees) the vector rotates counter-clockwise onto .

Reflection. Now a matrix defined as

Multiplying reflects across the line through the origin at angle :

With the mirror is the axis, and reflects onto .

Identity matrix

An identity matrix is a square matrix (the same number of rows as columns) with ones on the main diagonal and zeros everywhere else:

What makes it interesting is that multiplying it by another matrix of compatible dimensions gives back that other matrix:

For example,

It is the "do nothing" transformation: as a map, leaves every vector exactly where it was. When the identity matrix is the product of two square matrices, those two matrices are said to be the inverse of each other.

Inverse & determinant

The inverse of a nonzero scalar is , which can also be written . For a matrix we write the inverse as . It is never written as a fraction, because you can never divide by a matrix. For a matrix to be invertible it must be square, and if a matrix is invertible there must be a matrix satisfying .

For a matrix the inverse is

The quantity is called the determinant. Geometrically it is the factor by which the transformation scales area — and its sign tells you whether orientation is flipped. If the determinant is zero, the matrix squashes the whole plane onto a line (or a point), no inverse exists, and there is no way back. Try it:

With the sliders at their starting values you get exactly the worked example

Checking linear independence with matrices

In Part I we met linear independence. Now we can check it mechanically. Suppose we have three vectors:

We can stack them as the rows of a matrix :

Gaussian elimination

One way to test for linear independence is an algorithm known as Gaussian elimination. The goal is simple: if, using the rules below, we can make one of the rows all zeros, the vectors are linearly dependent. If we cannot, they are linearly independent. The rules are:

Carried all the way through (a variant called Gauss–Jordan elimination), the process puts a matrix into reduced row echelon form, which means all of the following hold:

Step through it below. The first preset is our matrix ; the second is a set of genuinely independent vectors; the third is the augmented matrix from the section on systems of linear equations below.

Working through , the third row becomes all zeros — so those three vectors are linearly dependent. That makes sense once you look: the first and third columns of are identical, and .

If all of this seems tedious, don't worry — it is exactly the kind of bookkeeping we hand to computers, often via numerically better-behaved algorithms such as a QR decomposition (the idea behind it is the Gram-Schmidt process) or the singular value decomposition.

Matrix rank

We know now that the rows of a matrix are vectors, and we know how to check them for linear independence. That gives us the rank of a matrix.

The rank of a matrix is defined as

  • the maximum number of linearly independent column vectors in the matrix, or
  • the maximum number of linearly independent row vectors in the matrix.

Both definitions are equivalent. For our matrix the rank is 2, since only two nonzero rows survived the reduction. A square matrix with rank is called full rank, and it is exactly the invertible case — the same condition as a nonzero determinant.

Systems of linear equations

Gaussian elimination also solves systems of linear equations. The process is nearly identical; we just append one more column to the matrix to form an augmented matrix, where the extra column holds the right-hand side of each equation. Suppose we have

We can express this system with the augmented matrix

Choose the "Augmented system" preset in the stepper above and walk it to the end. Once the left-hand block is in reduced row echelon form, the right-hand column holds the solution:

It is also possible to solve a system with the matrix inverse. Separate the augmented matrix back into a matrix and a vector, then multiply the vector by the inverse of the matrix:

Elimination is generally the better tool in practice: it is faster, more numerically stable, and it still works when the matrix has no inverse at all.

Eigenvalues & eigenvectors

From Wikipedia:

In linear algebra, an eigenvector, or characteristic vector, of a linear transformation is a nonzero vector that changes by a scalar factor when that linear transformation is applied to it. The corresponding eigenvalue, often denoted by , is the factor by which the eigenvector is scaled.

I would add one word to that definition: an eigenvector changes only by a scalar factor when the transformation is applied. If the vector swings off its own line, it is not an eigenvector.

Let's watch it happen. We will transform the entire vector space with the matrix

As in the transformation plots above, the gridlines themselves are being transformed, not just the vectors. This time, drag the slider to apply the transformation gradually:

Did you catch it? The whole space was stretched and flipped around, but never left its dashed line — it only got longer. That is because is an eigenvector of . How much longer? Exactly 1.5 times, so for this eigenvector. is not an eigenvector: it changes both direction and length.

For a square matrix, an eigenvector (which must be nonzero) and its eigenvalue satisfy

Any nonzero scalar multiple of an eigenvector is also an eigenvector, with the same eigenvalue. The plot above used a longer one so it would be easy to see; here we use the one of length 1. For our problem,

which is the same as

A matrix has two eigenvalues (they can be repeated, or even complex numbers), and they are the roots of the characteristic polynomial , where the trace is the sum of the diagonal entries. For our :

The second eigenvalue is negative, which means vectors along that second eigenvector get flipped through the origin as well as scaled — which is why the transformed grid above appears to turn itself inside out.

Eigenvalues and eigenvectors turn up nearly everywhere applied linear algebra does: principal component analysis, PageRank, the stability of dynamical systems, and the normal modes of a vibrating structure. A tour of some concrete use cases is available here.