Visualizing linear algebra: Eigenvectors

Figure 1: Before transformation

This is Part 8 in a series on linear algebra [1].

A vector that remains on its span [2] when a linear transformation is applied to it is termed an eigenvector of that transformation. The amount that it is scaled is called an eigenvalue.

For example, Figure 1 shows a yellow arrow that will be transformed by the indicated matrix. The purple line is the span of the yellow arrow.

Figure 2: After transformation

Figure 2 shows the yellow arrow after the transformation. Note that the yellow arrow has remained on its span, so it is an eigenvector of the transformation. It has been scaled by a factor of 2, so 2 is the eigenvalue. The eigenvalue is shown as the coefficient of the original vector.

Notice that i-hat is also an eigenvector and its eigenvalue is 3 (i.e., it is scaled by 3). However j-hat has not remained on its span, so it is not an eigenvector of the transformation.

Any vector that lies on the span of either the yellow arrow or the green arrow is an eigenvector and it will also have the eigenvalues 2 and 3 respectively. Any vector, such as the red arrow, that does not lie on either of those spans will be rotated off the line that it spans.

Figure 3: 3D rotation around an axis

Eigenvalues can be negative which means that after the transformation the arrow will point in the opposite direction along its span.

For one example of where finding an eigenvector is useful, consider a 3D dimensional rotation as in Figure 3. If you can find an eigenvector for that transformation, a vector that remains on its own span, then you have found the axis of rotation. For rotations the eigenvalue is always 1 since the length of the vector remains the same.

Note that the columns of a matrix describe the landing spots for the basis vectors. However, as illustrated by the 3D rotation, finding the eigenvectors and eigenvalues describes what the transformation does independent of the particular basis vectors used.

An eigenvector equation can be represented as:

Av = λv

where A is the matrix representing a transformation, v is the eigenvector and λ (lambda) is the corresponding eigenvalue (a number). This expression says that the matrix-vector product (A times v) gives the same result as just scaling the eigenvector v by some value λ. So finding the eigenvectors and their eigenvalues of a matrix A comes down to finding the values of v and λ that make this expression true.

The first step is to convert the right-hand-side of the equation so that it represents a matrix-vector product like the left-hand-side of the equation. This is done by multiplying λ by the identity matrix I, as follows:

Av = (λI)v

Now subtracting the right-hand-side and factoring out v:

Av - λIv = 0
(A - λI)v = 0

We're now looking for a non-zero vector v such that this new matrix times v gives the zero vector. The only way it is possible for the product of a matrix with a non-zero vector to become zero is if the transformation associated with that matrix reduces space to a lower dimension, say, from a plane to a line. In that case, the matrix has a determinant of zero. That is:

det(A - λI) = 0

For example, consider the matrix from Figures 1 and 2:

[3 1]
[0 2]

Now think about subtracting a variable amount λ from each diagonal entry:

[3 1] - λ[1 0] = [3-λ   1]
[0 2]    [0 1]   [  0 2-λ]

The goal is to find any values of λ that will make the determinant of the matrix zero. That is:

det([3-λ   1]) = ad - bc = (3-λ)(2-λ) - 1*0 = (3-λ)(2-λ) = 0
    [  0 2-λ]

Solving this equation, the only possible eigenvalues are λ = 2 and λ = 3.

So when λ equals 2 or 3, the matrix (A - λI) transforms space onto a line. That means there are non-zero vectors v such that (A - λI) times v equals the zero vector. Recall the reason we care about that is because it means Av = λv. That is, the vector v is an eigenvector of A.

To figure out the eigenvectors that have one of these eigenvalues, plug that value of λ into the matrix and then solve for which vectors this diagonally-altered matrix sends to zero. Solving with λ = 2:

[3-2   1][x] = [1 1][x] = x[1] + y[1] = [x+y] = [0]
[  0 2-2][y]   [0 0][y]    [0]    [0]   [  0]   [0]

Since the determinant is zero, there is no unique solution. The solutions are all the vectors on the line described by y = -x which is the diagonal line spanned by [-1;1] or the yellow arrow in Figure 1. Similarly, solving with λ = 3:

[3-3   1][x] = [0  1][x] = x[0] + y[ 1] = [ y] = [0]
[  0 2-3][y]   [0 -1][y]    [0]    [-1]   [-y]   [0]

In this case, the solutions are all the vectors on the line described by y = 0 which is the horizontal line spanned by [1;0] or i-hat in Figure 1.

Figure 4: 90° rotation

Not all transformations have eigenvectors. One example is a 2D 90° counterclockwise rotation which rotates all vectors off their spans as shown in Figure 4. Consider computing the eigenvalues of this rotation. Subtract λ from the diagonal elements and look for when the determinant is zero.

det([-λ -1]) = (-λ)(-λ) - -1*1 = 0
    [ 1 -λ]
             = λ² + 1 = 0

∴ λ = i or λ = -i

The only roots of that polynomial are the imaginary numbers i and -i. Assuming we are only looking for real number solutions, there are no eigenvectors for that transformation. However note that eigenvalues that are complex numbers generally correspond to some kind of rotation in the transformation.

Whenever a matrix has zeroes everywhere other than the diagonal, it is called a diagonal matrix. The way to interpret this is that all the basis vectors are eigenvectors with the diagonal entries of the matrix being their eigenvalues. That is, a diagonal matrix simply scales the basis vectors. A diagonal matrix can be represented as a vector times the identity matrix I. For example:

Figure 5: Change of basis

[-1 0] = [1 0][-1]
[ 0 2]   [0 1][ 2]

Therefore, whenever we want to apply a matrix multiplication to a diagonal matrix, it is the same as applying a matrix-vector multiplication, converting an O(N²) operation into O(N).

If a transformation has enough eigenvectors such that you can choose a set that spans the full space, then you can change your coordinate system so that these eigenvectors are your basis vectors. For example, using the eigenvectors for the matrix from Figure 1 as the change of basis matrix (the green and yellow arrows):

[1 -1]^-1[3 1][1 -1] = [3 0]
[0  1]  [0 2][0  1]   [0 2]

This new matrix is guaranteed to be diagonal with its corresponding eigenvalues down that diagonal. The new basis is called an eigenbasis with Figure 5 showing the change of basis. Applying the transformation will scale the new basis vectors by those eigenvalues, that is, the green arrow by 3 and the yellow arrow by 2.

Next up: vector spaces

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] A vector that remains on its span either points in the same direction or points in the opposite direction (the negative direction).

Visualizing linear algebra: Change of basis

Figure 1: Alternative basis vectors

This is Part 7 in a series on linear algebra [1].

Any given vector can be understood as the scaling of the unit vectors i-hat and j-hat. These special vectors are the standard basis vectors in a coordinate system.

However it is also possible to use different basis vectors. In Figure 1, the basis vectors b₁ and b₂ point in different directions and have different lengths to i-hat and j-hat.

Figure 2: Alice and Bobs' coordinate systems

Suppose that Alice uses the standard basis vectors i-hat and j-hat while Bob uses the alternative basis vectors b₁ and b₂. While Alice and Bob are looking at the same vectors in space, they can be considered to be using different languages to refer to them.

In Figure 2, Alice would describe b₁ with the vector coordinates [2;1] and b₂ with the vector coordinates [-1;1].[2] Whereas from Bob's perspective, b₁ and b₂ have coordinates [1;0] and [0;1]. They are what define the meaning of the coordinates [1;0] and [0;1] in his system. To reiterate, both Alice and Bob are looking at the same vectors in space, but they use different words and numbers to describe them.

Figure 3: Vector [-1;2] in Bob's system

To translate between Alice and Bobs' coordinate systems, consider Figure 3. Suppose Bob describes a vector with coordinates [-1;2] in his system. That is, b₁ is scaled by -1 and b₂ is scaled by 2 as represented by the yellow arrow. From Alice's perspective, the coordinates for b₁ and b₂ in her system can be similarly scaled to describe the vector in her system. That is:

-1[2] + 2[-1] = [-4]

  [1]    [ 1]   [ 1]

Note that this is just matrix-vector multiplication with a matrix whose column vectors represent Bob's basis vectors in Alice's language. That is:

[2 -1][-1] = -1[2] + 2[-1] = [-4]

[1  1][ 2]     [1]    [ 1]   [ 1]

In effect, a matrix whose column vectors represent Bob's basis vectors can be thought of as a transformation that moves Alice's basis vectors, i-hat and j-hat, to Bob's basis vectors, b₁ and b₂. So the vector [-1;2] is a certain linear combination of Alice's basis vectors (-1î + 2ĵ ). The resulting vector after the transformation will be that same linear combination but of the new basis vectors (-1b₁ + 2b₂). This transformation, in essence, enables Alice to describe vectors in Bob's language.

It is similarly possible for Bob to describe vectors in Alice's language. This requires taking the inverse of the matrix which corresponds to playing the transformation backwards. The inverse of the matrix is:

[2 -1]^-1 = [ 1/3 1/3]

[1  1]     [-1/3 2/3]

Let's go in the other direction, taking the vector that Alice describes in her language above as [-4;1] and describe it in Bob's language:

[ 1/3 1/3][-4] = -4[ 1/3] + 1[1/3] = [-1]

[-1/3 2/3][ 1]     [-1/3]    [2/3]   [ 2]

The result is [-1;2] in Bob's language which is verified by the yellow arrow in Figure 3.

That is how to translate the descriptions of individual vectors back and forth between coordinate systems. The matrix whose columns represent Bob's basis vectors but written in Alice's coordinates translates vectors from Bob's language into Alice's. And the inverse matrix does the opposite.

Linear transformations involving matrices can also be described in different coordinate systems. For example, a 90° counterclockwise rotation can be described in Alice's system as:

[0 -1]
[1  0]

That is, i-hat ends up at coordinates [0;1] and j-hat ends up at coordinates [-1;0]. To translate this into Bob's system, first consider a vector in Bob's language, say, the vector [-1;2] from above. That vector needs to be translated to Alice's language using the change of basis matrix, then the rotation applied in Alice's language, then translated back to Bob's language using the inverse change of basis matrix. This can be represented, from right-to-left, as:

[2 -1]^-1[0 -1][2 -1][-1]
[1  1]  [1  0][1  1][ 2]

This transformation sequence will work for any vector in Bob's language. The product of the three matrices is:

[2 -1]^-1[0 -1][2 -1] = [1/3 -2/3]

[1  1]  [1  0][1  1]   [5/3 -1/3]

If Bob applies this composition matrix to a vector in his system, it will return the rotated version of that vector expressed in his coordinate system. For example:

[1/3 -2/3][1] = [-1]

[5/3 -1/3][2]   [ 1]

With an expression like A^-1MA , the middle matrix represents a transformation M as one person sees it, the outer matrices indicate the shift in perspective, while the full matrix product represents a transformation M as someone else sees it.

Next up: eigenvectors

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] The notation [x;y] using a semicolon indicates a column vector.

Visualizing linear algebra: Cross product

Figure 1: The red arrow is the cross product of
the purple and orange arrows

This is Part 6 in a series on linear algebra [1].

As described in the post on matrices, a 2x2 matrix encodes two column vectors that show where the two unit vectors (i-hat and j-hat) end up when the 2D vector space is transformed. The post on the determinant shows how the unit square defined by those unit vectors is transformed into a parallelogram. The determinant is a measure of the area of the parallelogram which can be negative if i-hat ends up on the left of j-hat, thus indicating the area was flipped, or zero if i-hat and j-hat end up on the same line.

The 3D cross product of two vectors is a third vector that is perpendicular to both and has a length that is their determinant (i.e., the directional area of the parallelogram defined by those vectors) as illustrated in Figure 1. [2]

Figure 2: Solve for vector p

Figure 2 shows the equation for computing a vector p that is the cross product of vectors v and w.

Algebraically, the equation asks what is the vector p such that the dot product of p and a vector [x;y;z] equals the determinant of a 3x3 matrix with column vectors [x;y;z], v and w?

Geometrically, the equation asks what is the vector p such that projecting vector [x;y;z] onto its number line and scaling by the length of p will equal the signed volume of a parallelepiped defined by the vectors [x;y;z], v and w?

The equation can be reorganized as:

p₁.x + p₂.y + p₃.z = x(v₂.w₃ - v₃.w₂) +

                     y(v₃.w₁ - v₁.w₃) +
                     z(v₁.w₂ - v₂.w₁)

The constants on the right hand side are particular combinations of the coordinates of v and w which will be the coordinates of p and thus the cross product of v and w:

            [v₂.w₃ - v₃.w₂]

p = v x w = [v₃.w₁ - v₁.w₃]
            [v₁.w₂ - v₂.w₁]

Figure 3 illustrates that the way the linear transformation works on a given vector [x;y;z] (the white arrow) is to project that vector onto a line p (the red arrow) that's perpendicular to both v and w and then to scale that projection by the area of the parallelogram spanned by v and w. This is the same thing as taking a dot product between [x;y;z] and a vector that's perpendicular to v and w with a length equal to the area of that parallelogram.

Next up: change of basis

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] The cross product is used in a 3D vector space where the third vector is computed from the first two. If used in 2D space, it would return a vector that was perpendicular to that 2D space.

Visualizing linear algebra: Dot product

Figure 1: Column vector as an arrow

This is Part 5 in a series on linear algebra [1].

Figure 1 shows a vector that is represented geometrically as a yellow arrow and numerically as a column. It scales the unit vectors i-hat and j-hat by 2 and 4 respectively. That is:

v = 2î + 4ĵ

Now suppose the column is transposed to a row, as follows:

[2]^T = [2 4]
[4]

This row is a 2x1 matrix that represents the transformation of a 2D vector space to a 1D vector space, that is, a number line. The number line is the span of the yellow arrow (i.e., it extends along the yellow arrow in both directions).

Figure 2: Row vector as a transformation matrix

The effect of this transformation on the unit vectors is shown in Figure 2 where i-hat is scaled by 2 and j-hat is scaled by 4. The length of the yellow arrow, per Pythagoras' Theorem, is √(2² + 4²) =  √20, or about 4.47.

For any given input vector, the position on the number line where the input vector ends up will be the vector's X coordinate scaled by 2 plus the vector's Y coordinate scaled by 4.

Figure 3: Calculating the dot product

For example, the purple arrow in Figure 3 is transformed to a 1D vector, or scalar, on the number line as follows:

[2 4][2] = 2[2] + 1[4] = 8
     [1]

Geometrically, this is equivalent to projecting the purple arrow onto the span of the yellow arrow (at position 8/√20, or 1.79) and scaling by the length of the yellow arrow (√20, or 4.47). The small right-angled triangle in Figure 3 shows the projection.

In the symmetrical example where the column for the purple arrow is transposed to a row (representing a transformation to the number line that is the span of the purple arrow), the yellow arrow is transformed as follows:

[2 1][2] = 2[2] + 4[1] = 8
     [4]

The scalar result is the same as for the first example - the vector order doesn't matter. However geometrically, it is equivalent to projecting the yellow arrow onto the span of the purple arrow (at position 8/√5, or 3.58) and scaling by the the length of the purple arrow (√(2² + 1²) =  √5, or 2.24). The large right-angled triangle in Figure 3 shows the projection.

More generally, this operation is the dot product (or scalar product) of two vectors and for 2D vectors is defined [2] as:

a.b = a_xb_x + a_yb_y

When the arrows are pointing in the same general direction the dot product is positive, when pointing in the opposite direction the dot product is negative, and when the arrows are orthogonal the dot product is zero.

Figure 4: Dot product = transform

Numerically the dot product multiplies two vectors, taking direction into account [3].

Geometrically, one vector encodes a linear transformation that projects space onto a number line and scales the projection by the length of the vector.

Next up: the cross product

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] The dot product is also defined as

a.b = ∥a∥∥b∥cos(θ)

where ∥v∥ denotes the magnitude of vector v. This can also be interpreted as projecting one of the vectors onto the other vector (via the cosine) and scaling by the other vector.

[3] The numerical summary comes from Better Explained which also offers further analogies.

Visualizing linear algebra: Matrix inverse

Figure 1: A linear system of equations

This is Part 4 in a series on linear algebra [1].

In the series so far, matrices have been used to transform a vector space. This is particularly useful for applications such as computer graphics and robotics. However its most general use is in the solving of linear systems of equations. In a linear equation, the only thing happening to each variable is that it is being scaled by some constant. And the only thing happening to each of those scaled variables is that they are added to each other.

Figure 1 shows two linear equations. These two equations are packaged into a single vector equation where the 2x2 matrix A contains all the constant coefficients, vector x contains the variables x and y, and vector v contains the constants. Per the equation itself, vector x multiplied by matrix A equals the vector v.

Matrix A represents a linear transformation, so solving Ax = v means we're looking for a vector x which, after applying the transformation to it, lands on vector v. The way to find vector x is by applying the transformation in reverse. That is, when the inverse transformation is applied to vector v, vector v will end up landing on vector x. The inverse of A is represented as A^-1. AA^-1 = A^-1A = I, where I is the identity matrix [2]. Geometrically, applying a transformation to a vector space and then applying the inverse transformation restores the original vector space. This is equivalent to applying the identity matrix which leaves the vector space unchanged. The identity (or unit) matrix is defined as:

[1 0]
[0 1]

Notice that the identity matrix columns are simply the unit vectors i-hat and j-hat. Now multiplying both sides of the equation Ax = v by A^-1 results in the equation A^-1Ax = Ix = x = A^-1v.

The equation for calculating the inverse of a matrix is:

[a b]^-1 = 1/(ad - bc)[ d -b]
[c d]                [-c  a]

Note that the determinant of the matrix appears in the expression (ad - bc). There will be an inverse matrix as long as the determinant is non-zero. Calculating A^-1:

[2 2]^-1 = 1/(2*3 - 2*1)[ 3 -2] = 1/4[ 3 -2]
[1 3]                  [-1  2]      [-1  2]

Figure 2: Solving the equations

Solving our vector equation:

x = A^-1v
  = 1/4[ 3 -2][-4]
       [-1  2][-1]
  = 1/4*(-4[ 3] + -1*[-2])
           [-1]      [-2]
  = 1/4[-4* 3 + -1*-2]
       [-4*-1 + -1* 2]
  = 1/4[-10]
       [  2]
  = [-2.5]
    [ 0.5]

Plugging x and y into the original linear equations:

2x + 2y = 2 * -2.5 + 2 * 0.5 = -5 + 1 = -4
1x + 3y = 1 * -2.5 + 3 * 0.5 = -2.5 + 1.5 = -1

That confirms that the correct solution has been found. Figure 2 shows the geometric representation of the vector equation.

The set of all possible outputs for a matrix, whether a plane, a line, a 3D space, and so on, is called the column space of the matrix (the span of the columns). The number of dimensions in the column space of a matrix is its rank. In the above example, the rank is two (and, since the determinant is non-zero, the matrix is full rank). If the determinant is zero and the area reduces to a line or point, then the rank is one or zero respectively. Solutions only exist in the rank one case if the vector falls on the line. The zero vector is included in the column space and the set of vectors that land on the origin is called the null space or kernel of a matrix.

Next up: the dot product

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.

[2] The inverse of a matrix is analogous to the reciprocal of a number. Just as 8*8^-1 = 1, so AA^-1 = I, where I is the identity matrix (itself analogous to the number 1).

Visualizing linear algebra: Determinant

Figure 1: The determinant of the unit matrix is 1

This is Part 3 in a series on linear algebra [1].

Consider the 1x1 unit square in Figure 1 whose sides are circumscribed by i-hat and j-hat. When a linear transformation is applied to the vector space, the unit square is transformed into a parallelogram. The factor by which the transformation scales the area is called the determinant of that transformation.

Figure 2: The determinant of any matrix is ad - bc

The equation for calculating the determinant is

det([a b]) = ad - bc

    [c d]

The determinant is a measure of the area of a parallelogram. However in the cases where i-hat switches to the left of j-hat, the determinant will be negative. This can be understood geometrically as the flipping of the area, like turning over a piece of paper (i.e., inverting the matrix).

Some transformations will result in i-hat and j-hat ending up on the same line, in which case the area and thus the determinant will be 0.

Figure 2 shows how the equation is derived. Breaking it down:

det([a b]) = (a + b)(c + d) - ac - bd - 2bc = ad - bc

    [c d]

The calculation takes the area of the rectangle circumscribing the parallelogram and then just subtracts the areas of the smaller squares and triangles surrounding the parallelogram.

When either b or c are equal to 0, the area will just be ad. This corresponds to when either i-hat or j-hat remain on their original axes. That is, when the final shape is either a rectangle (in the case of both b and c being 0) or a shear along just one dimension.

Figure 3:The determinant of this flipped area is -3

Working through some examples, the matrix in Figure 3 is

[1  2]
[1 -1]

The determinant is

ad - bc = 1*-1 - 2*1 = -3

Note that i-hat ends up to the left of j-hat which means the orientation of space has been inverted resulting in a negative determinant.

Figure 4: The determinant of a line is 0

The matrix in Figure 4 is

[4 2]
[2 1]

The determinant is

ad - bc = 4*1 - 2*2 = 0

Note that i-hat ends up on the same line as j-hat (i.e., the matrix columns are linearly dependent) which means the determinant must be 0. A matrix with a determinant of 0 is also termed a degenerate or non-invertible matrix.

Figure 5: A parallelepiped

The determinant can also be calculated for square matrices that are three dimensional or higher. In the case of a 3x3 matrix, the determinant is a measure of the volume of a parallelepiped and the equation is

det([a b c])

    [d e f]  = a det([e f]) 

    [g h i]          [g h]

             - b det([d f])

                     [h i]

             + c det([d e])

                     [g i]

The determinant will be negative when the 3D space is inverted which can be determined visually using the right-hand-rule. A determinant of 0 would mean that the space is transformed to a lower dimensional space with zero volume and so would be either a plane, a line, or a point. In this special case, the columns of the matrix are linearly dependent.

Next up: the inverse of a matrix

--

[1] The figures and examples of the posts in this series are based on the Essence of Linear Algebra series by 3Blue1Brown.