Chapter 5

Linear Algebra

Perhaps the most universal tools of graphics programs are the matrices that change or transform points and vectors. In the next chapter, we will see how a vector can be represented as a matrix with a single column, and how the vector can be represented in a different basis via multiplication with a square matrix. We will also describe how we can use such multiplications to accomplish changes in the vector such as scaling, rotation, and translation. In this chapter, we review basic linear algebra from a geometric perspective, focusing on intuition and algorithms that work well in the two- and three-dimensional case.

This chapter can be skipped by readers comfortable with linear algebra. However, there may be some enlightening tidbits even for such readers, such as the development of determinants and the discussion of singular and eigenvalue decomposition.

5.1 Determinants

We usually think of determinants as arising in the solution of linear equations. However, for our purposes, we will think of determinants as another way to multiply vectors. For 2D vectors a and b, the determinant |ab| is the area of the parallelogram formed by a and b (Figure 5.1). This is a signed area, and the sign is positive if a and b are right-handed and negative if they are left-handed. This means |ab| = −|ba|. In 2D we can interpret “right-handed” as meaning we rotate the first vector counterclockwise to close the smallest angle to the second vector. In 3D, the determinant must be taken with three vectors at a time. For three 3D vectors, a, b, and c, the determinant |abc| is the signed volume of the parallelepiped (3D parallelogram; a sheared 3D box) formed by the three vectors (Figure 5.2). To compute a 2D determinant, we first need to establish a few of its properties. We note that scaling one side of a parallelogram scales its area by the same fraction (Figure 5.3):

$\left|\left(ka\right)b\right|=\left|a\left(kb\right)\right|=k\left|\mathrm{ab}\right|.$

Also, we note that “shearing” a parallelogram does not change its area (Figure 5.4):

$\left|\left(a+kb\right)b\right|=\left|a\left(b+ka\right)\right|=\left|\mathrm{ab}\right|.$

Finally, we see that the determinant has the following property:

$\left|a\left(b+c\right)\right|=\left|\mathrm{ab}\right|+\left|\mathrm{ac}\right|,\text{ (5.1)}$

because as shown in Figure 5.5 we can “slide” the edge between the two parallelograms over to form a single parallelogram without changing the area of either of the two original parallelograms.

Now let’s assume a Cartesian representation for a and b:

$\begin{array}{cc}\hfill \left|\mathrm{ab}\right|& =\left|\left(x_{a}x+y_{a}y\right)\left(x_{b}x+y_{b}y\right)\right|\hfill \\ \hfill & =x_a{x}_b\left|\mathrm{xx}\right|+x_a{y}_b\left|\mathrm{xy}\right|+y_a{x}_b\left|\mathrm{yx}\right|+y_a{y}_b\left|\mathrm{yy}\right|\hfill \\ \hfill & =x_a{x}_b\left(\text{0}\right)+x_a{y}_b\left(+\text{1}\right)+y_a{x}_b\left(-1\right)+y_a{y}_b\left(\text{0}\right)\hfill \\ \hfill & =x_a{y}_b-y_a{x}_b.\hfill \end{array}$

This simplification uses the fact that |vv| = 0 for any vector v, because the parallelograms would all be collinear with v and thus without area.

In three dimensions, the determinant of three 3D vectors a, b, and c is denoted |abc|. With Cartesian representations for the vectors, there are analogous rules for parallelepipeds as there are for parallelograms, and we can do an analogous expansion as we did for 2D:

$\begin{array}{cc}\hfill \left|\mathrm{ab}\right|& =\left|\left(x_{a}x+y_{a}y+z_{a}z\right)\left(x_{b}x+y_{b}y+z_{b}z\right)\left(x_{c}x+y_{c}y+z_{c}z\right)\right|\hfill \\ \hfill & =x_a{y}_b{z}_c-x_a{z}_b{y}_c-y_a{x}_b{z}_c+y_a{z}_b{x}_c+z_a{x}_b{y}_c-z_a{y}_b{x}_c.\hfill \end{array}$

As you can see, the computation of determinants in this fashion gets uglier as the dimension increases. We will discuss less error-prone ways to compute determinants in Section 5.3.

Example.

Determinants arise naturally when computing the expression for one vector as a linear combination of two others—for example, if we wish to express a vector c as a combination of vectors a and b:

$c=a_{c}a+b_{c}b\text{.}$

We can see from Figure 5.6 that

$\left|\left(b_{c}b\right)a\right|=\left|\mathrm{ca}\right|,$

because these parallelograms are just sheared versions of each other. Solving for bc yields

$b_c=\frac{\left|\mathrm{ca}\right|}{\left|\mathrm{ba}\right|}.$

An analogous argument yields

$a_c=\frac{\left|\mathrm{bc}\right|}{\left|\mathrm{ba}\right|}.$

This is the two-dimensional version of Cramer’s rule which we will revisit in Section 5.3.2.

5.2 Matrices

A matrix is an array of numeric elements that follow certain arithmetic rules. An example of a matrix with two rows and three columns is

$\left[\begin{array}{rrr}\hfill 1.7& \hfill -1.2& \hfill 4.2\\ \hfill 3.0& \hfill 4.5& \hfill -7.2\end{array}\right].$

Matrices are frequently used in computer graphics for a variety of purposes including representation of spatial transforms. For our discussion, we assume the elements of a matrix are all real numbers. This chapter describes both the mechanics of matrix arithmetic and the determinant of “square” matrices, i.e., matrices with the same number of rows as columns.

5.2.1 Matrix Arithmetic

A matrix times a constant results in a matrix where each element has been multiplied by that constant, e.g.,

$2\left[\begin{array}{rr}\hfill 1& \hfill -4\\ \hfill 3& \hfill 2\end{array}\right]=\left[\begin{array}{rr}\hfill 2& \hfill -8\\ \hfill 6& \hfill 4\end{array}\right].$

Matrices also add element by element, e.g.,

$\left[\begin{array}{rr}\hfill 1& \hfill -4\\ \hfill 3& \hfill 2\end{array}\right]+\left[\begin{array}{rr}\hfill 2& \hfill 2\\ \hfill 2& \hfill 2\end{array}\right]=\left[\begin{array}{rr}\hfill 3& \hfill -2\\ \hfill 5& \hfill 4\end{array}\right].$

For matrix multiplication, we “multiply” rows of the first matrix with columns of the second matrix:

So the element pij of the resulting product is

$p_{ij}=a_{i1}{b}_{1j}+a_{i2}{b}_{2j}+\cdots +a_{im}{b}_{mj}.\text{ (5.2)}$

Taking a product of two matrices is only possible if the number of columns of the left matrix is the same as the number of rows of the right matrix. For example,

$\left[\begin{array}{ll}0\hfill & 1\hfill \\ 2\hfill & 3\hfill \\ 4\hfill & 5\hfill \end{array}\right]\left[\begin{array}{llll}6\hfill & 7\hfill & 8\hfill & 9\hfill \\ 0\hfill & 1\hfill & 2\hfill & 3\hfill \end{array}\right]=\left[\begin{array}{rrrr}\hfill 0& \hfill 1& \hfill 2& \hfill 3\\ \hfill 12& \hfill 17& \hfill 22& \hfill 27\\ \hfill 24& \hfill 33& \hfill 42& \hfill 51\end{array}\right].$

Matrix multiplication is not commutative in most instances:

$\mathrm{AB}\ne \mathrm{BA}\text{.}\text{ (5.3)}$

Also, if AB = AC, it does not necessarily follow that B = C. Fortunately, matrix multiplication is associative and distributive:

$\begin{array}{cc}\hfill \left(\mathrm{AB}\right)C& =A\left(\mathrm{BC}\right),\hfill \\ \hfill A\left(B+C\right)& =\mathrm{AB}+\mathrm{AC},\hfill \\ \hfill \left(A+B\right)C& =\mathrm{AC}+\mathrm{BC}\text{.}\hfill \end{array}$

5.2.2 Operations on Matrices

We would like a matrix analog of the inverse of a real number. We know the inverse of a real number x is 1/x and that the product of x and its inverse is 1. We need a matrix I that we can think of as a “matrix one.” This exists only for square matrices and is known as the identity matrix; it consists of ones down the diagonal and zeroes elsewhere. For example, the four by four identity matrix is

$I=\left[\begin{array}{llll}1\hfill & 0\hfill & 0\hfill & 0\hfill \\ 0\hfill & 1\hfill & 0\hfill & 0\hfill \\ 0\hfill & 0\hfill & 1\hfill & 0\hfill \\ 0\hfill & 0\hfill & 0\hfill & 1\hfill \end{array}\right].$

The inverse matrix A−1 of a matrix A is the matrix that ensures AA−1 = I. For example,

${\left[\begin{array}{ll}\text{1}\hfill & 2\hfill \\ \text{3}\hfill & 4\hfill \end{array}\right]}^{-1}=\left[\begin{array}{rr}\hfill -2.0& \hfill 1.0\\ \hfill 1.5& \hfill -0.5\end{array}\right]\text{because}\left[\begin{array}{ll}1\hfill & 2\hfill \\ 3\hfill & 4\hfill \end{array}\right]\left[\begin{array}{rr}\hfill -2.0& \hfill 1.0\\ \hfill 1.5& \hfill -0.5\end{array}\right]=\left[\begin{array}{ll}1\hfill & 0\hfill \\ 0\hfill & 1\hfill \end{array}\right].$

Note that the inverse of A−1 is A. So AA−1 = A−1 A = I. The inverse of a product of two matrices is the product of the inverses, but with the order reversed:

${\left(\mathrm{AB}\right)}^{-1}=B^{-1}{A}^{-1}.\text{ (5.4)}$

We will return to the question of computing inverses later in the chapter.

The transpose AT of a matrix A has the same numbers but the rows are switched with the columns. If we label the entries of AT as ${a^{\prime }}_{ij}$ then

$a_{ij}={a^{\prime }}_{ij}.$

For example,

${\left[\begin{array}{ll}1\hfill & 2\hfill \\ 3\hfill & 4\hfill \\ 5\hfill & 6\hfill \end{array}\right]}^{\text{T}}=\left[\begin{array}{lll}1\hfill & 3\hfill & 5\hfill \\ 2\hfill & 4\hfill & 6\hfill \end{array}\right].$

The transpose of a product of two matrices obeys a rule similar to Equation (5.4):

${\left(\mathrm{AB}\right)}^{\text{T}}=B^{\text{T}}{A}^{\text{T}}.$

The determinant of a square matrix is simply the determinant of the columns of the matrix, considered as a set of vectors. The determinant has several nice relationships to the matrix operations just discussed, which we list here for reference:

$\left|\mathrm{AB}\right|=\left|A\right|\left|B\right|,\text{ (5.5)}$

$\left|A^{-1}\right|=\frac{1}{\left|A\right|},\text{ (5.6)}$

$\left|A^{\text{T}}\right|=\left|A\right|.\text{ (5.7)}$

5.2.3 Vector Operations in Matrix Form

In graphics, we use a square matrix to transform a vector represented as a matrix. For example, if you have a 2D vector a = (xa,ya) and want to rotate it by 90 degrees about the origin to form vector a' = (−ya, xa), you can use a product of a 2 × 2 matrix and a 2 × 1 matrix, called a column vector. The operation in matrix form is

$\left[\begin{array}{rr}\hfill 0& \hfill -1\\ \hfill 1& \hfill 0\end{array}\right]\left[\begin{array}{c}{x}_a\\ y_a\end{array}\right]=\left[\begin{array}{r}\hfill -y_a\\ \hfill x_a\end{array}\right].$

We can get the same result by using the transpose of this matrix and multiplying on the left (“premultiplying”) with a row vector:

$\left[x_a{y}_a\right]\left[\begin{array}{rr}\hfill 0& \hfill 1\\ \hfill -1& \hfill 0\end{array}\right]=\left[-y_a{x}_a\right].$

These days, postmultiplication using column vectors is fairly standard, but in many older books and systems you will run across row vectors and premultiplication. The only difference is that the transform matrix must be replaced with its transpose.

We also can use matrix formalism to encode operations on just vectors. If we consider the result of the dot product as a 1 × 1 matrix, it can be written

$a\cdot b=a^{\text{T}}b\text{.}$

For example, if we take two 3D vectors we get

$\left[x_a{y}_a{z}_a\right]\left[\begin{array}{l}{x}_b\hfill \\ y_b\hfill \\ z_b\hfill \end{array}\right]=\left[x_a{x}_b+y_a{y}_b+z_a{z}_b\right].$

A related vector product is the outer product between two vectors, which can be expressed as a matrix multiplication with a column vector on the left and a row vector on the right: abT. The result is a matrix consisting of products of all pairs of an entry of a with an entry of b. For 3D vectors, we have

$\left[\begin{array}{l}{x}_a\hfill \\ y_a\hfill \\ z_a\hfill \end{array}\right]\left[x_b{y}_b{z}_b\right]=\left[\begin{array}{lll}{x}_a{x}_b\hfill & x_a{y}_b\hfill & x_a{z}_b\hfill \\ y_a{x}_b\hfill & y_a{y}_b\hfill & y_a{z}_b\hfill \\ z_a{z}_b\hfill & z_a{y}_b\hfill & z_a{z}_b\hfill \end{array}\right].$

It is often useful to think of matrix multiplication in terms of vector operations. To illustrate using the three-dimensional case, we can think of a 3 × 3 matrix as a collection of three 3D vectors in two ways: either it is made up of three column vectors side-by-side, or it is made up of three row vectors stacked up. For instance, the result of a matrix-vector multiplication y = Ax can be interpreted as a vector whose entries are the dot products of x with the rows of A. Naming these row vectors ri, we have

$\left[\begin{array}{c}|\\ y\\ \text{|}\end{array}\right]=\left[\begin{array}{c}-r_{\text{1}}-\\ -r_{\text{2}}-\\ -r_{\text{3}}-\end{array}\right]\left[\begin{array}{c}|\\ x\\ \text{|}\end{array}\right];$

Alternatively, we can think of the same product as a sum of the three columns ci of A, weighted by the entries of x:

$\begin{array}{l}\left[\begin{array}{c}|\\ y\\ \text{|}\end{array}\right]=\left[\begin{array}{ccc}|& |& |\\ c_{\text{1}}& c_{\text{2}}& c_{\text{3}}\\ \text{|}& \text{|}& \text{|}\end{array}\right]\left[\begin{array}{c}{x}_1\\ x_2\\ x_3\end{array}\right];\hfill \\ y=x_1{c}_{\text{1}}+x_2{c}_{\text{2}}+x_3{c}_{\text{3}}.\hfill \end{array}$

Using the same ideas, one can understand a matrix-matrix product AB as an array containing the pairwise dot products of all rows of A with all columns of B (cf. (5.2)); as a collection of products of the matrix A with all the column vectors of B, arranged left to right; as a collection of products of all the row vectors of A with the matrix B, stacked top to bottom; or as the sum of the pairwise outer products of all columns of A with all rows of B. (See Exercise 8.)

These interpretations of matrix multiplication can often lead to valuable geometric interpretations of operations that may otherwise seem very abstract.

5.2.4 Special Types of Matrices

The identity matrix is an example of a diagonal matrix, where all nonzero elements occur along the diagonal. The diagonal consists of those elements whose column index equals the row index counting from the upper left.

The identity matrix also has the property that it is the same as its transpose. Such matrices are called symmetric.

The identity matrix is also an orthogonal matrix, because each of its columns considered as a vector has length 1 and the columns are orthogonal to one another. The same is true of the rows (see Exercise 2). The determinant of any orthogonal matrix is either +1 or −1.

A very useful property of orthogonal matrices is that they are nearly their own inverses. Multiplying an orthogonal matrix by its transpose results in the identity,

$R^{\text{T}}R=I={\mathrm{RR}}^{\text{T}}\text{for}\text{orthogonal}R\text{.}$

This is easy to see because the entries of RTR are dot products between the columns of R. Off-diagonal entries are dot products between orthogonal vectors, and the diagonal entries are dot products of the (unit-length) columns with themselves.

Example.

The matrix

$\left[\begin{array}{lll}\text{8}\hfill & \text{0}\hfill & \text{0}\hfill \\ \text{0}\hfill & \text{2}\hfill & \text{0}\hfill \\ \text{0}\hfill & \text{0}\hfill & \text{9}\hfill \end{array}\right]$

is diagonal, and therefore symmetric, but not orthogonal (the columns are orthogonal but they are not unit length).

The matrix

$\left[\begin{array}{lll}\text{1}\hfill & \text{1}\hfill & \text{2}\hfill \\ \text{1}\hfill & \text{9}\hfill & \text{7}\hfill \\ \text{2}\hfill & \text{7}\hfill & \text{1}\hfill \end{array}\right]$

is symmetric, but not diagonal or orthogonal.

The matrix

$\left[\begin{array}{lll}\text{0}\hfill & \text{1}\hfill & \text{0}\hfill \\ \text{0}\hfill & \text{0}\hfill & \text{1}\hfill \\ \text{1}\hfill & \text{0}\hfill & \text{0}\hfill \end{array}\right]$

is orthogonal, but neither diagonal nor symmetric.

5.3 Computing with Matrices and Determinants

Recall from Section 5.1 that the determinant takes n n-dimensional vectors and combines them to get a signed n-dimensional volume of the n-dimensional parallelepiped defined by the vectors. For example, the determinant in 2D is the area of the parallelogram formed by the vectors. We can use matrices to handle the mechanics of computing determinants.

If we have 2D vectors r and s, we denote the determinant |rs|; this value is the signed area of the parallelogram formed by the vectors. Suppose we have two 2D vectors with Cartesian coordinates (a, b) and (A, B) (Figure 5.7). The determinant can be written in terms of column vectors or as a shorthand:

$\left|\left[\begin{array}{c}a\\ b\end{array}\right]\left[\begin{array}{c}A\\ B\end{array}\right]\right|\equiv \left|\begin{array}{ll}a\hfill & A\hfill \\ b\hfill & B\hfill \end{array}\right|=aB-Ab.\text{ (5.8)}$

Note that the determinant of a matrix is the same as the determinant of its transpose:

$\left|\begin{array}{ll}a\hfill & A\hfill \\ b\hfill & B\hfill \end{array}\right|=\left|\begin{array}{ll}a\hfill & b\hfill \\ A\hfill & B\hfill \end{array}\right|=aB-Ab.$

This means that for any parallelogram in 2D there is a “sibling” parallelogram that has the same area but a different shape (Figure 5.8). For example, the parallelogram defined by vectors (3, 1) and (2, 4) has area 10, as does the parallelogram defined by vectors (3, 2) and (1, 4).

Example.

The geometric meaning of the 3D determinant is helpful in seeing why certain formulas make sense. For example, the equation of the plane through the points (xi, yi, zi) for i = 0, 1, 2 is

$\left|\begin{array}{lll}x-x_0\hfill & x-x_1\hfill & x-x_2\hfill \\ y-y_0\hfill & y-y_1\hfill & y-y_2\hfill \\ z-z_0\hfill & z-z_1\hfill & z-z_2\hfill \end{array}\right|=0.$

Each column is a vector from point (xi, yi, zi) to point (x, y, z). The volume of the parallelepiped with those vectors as sides is zero only if (x, y, z) is coplanar with the three other points. Almost all equations involving determinants have similarly simple underlying geometry.

As we saw earlier, we can compute determinants by a brute force expansion where most terms are zero, and there is a great deal of bookkeeping on plus and minus signs. The standard way to manage the algebra of computing determinants is to use a form of Laplace’s expansion. The key part of computing the determinant this way is to find cofactors of various matrix elements. Each element of a square matrix has a cofactor which is the determinant of a matrix with one fewer row and column possibly multiplied by minus one. The smaller matrix is obtained by eliminating the row and column that the element in question is in. For example, for a 10 × 10 matrix, the cofactor of a82 is the determinant of the 9 × 9 matrix with the 8th row and 2nd column eliminated. The sign of a cofactor is positive if the sum of the row and column indices is even and negative otherwise. This can be remembered by a checkerboard pattern:

$\left[\begin{array}{lllll}+\hfill & -\hfill & +\hfill & -\hfill & \cdots \hfill \\ -\hfill & +\hfill & -\hfill & +\hfill & \cdots \hfill \\ +\hfill & -\hfill & +\hfill & -\hfill & \cdots \hfill \\ -\hfill & +\hfill & -\hfill & +\hfill & \cdots \hfill \\ ⋮\hfill & ⋮\hfill & ⋮\hfill & ⋮\hfill & \ddots \hfill \end{array}\right].$

So, for a 4 × 4 matrix,

$A=\left[\begin{array}{llll}{a}_{11}\hfill & a_{12}\hfill & a_{13}\hfill & a_{14}\hfill \\ a_{21}\hfill & a_{22}\hfill & a_{23}\hfill & a_{24}\hfill \\ a_{31}\hfill & a_{32}\hfill & a_{33}\hfill & a_{34}\hfill \\ a_{41}\hfill & a_{42}\hfill & a_{43}\hfill & a_{44}\hfill \end{array}\right].$

The cofactors of the first row are

$\begin{array}{ll}{a}_{11}^c=\left|\begin{array}{lll}{a}_{22}\hfill & a_{23}\hfill & a_{24}\hfill \\ a_{32}\hfill & a_{33}\hfill & a_{34}\hfill \\ a_{42}\hfill & a_{43}\hfill & a_{44}\hfill \end{array}\right|,\hfill & a_{12}^c=-\left|\begin{array}{lll}{a}_{21}\hfill & a_{23}\hfill & a_{24}\hfill \\ a_{31}\hfill & a_{33}\hfill & a_{34}\hfill \\ a_{41}\hfill & a_{43}\hfill & a_{44}\hfill \end{array}\right|,\hfill \\ a_{13}^c=\left|\begin{array}{lll}{a}_{21}\hfill & a_{22}\hfill & a_{24}\hfill \\ a_{31}\hfill & a_{32}\hfill & a_{34}\hfill \\ a_{41}\hfill & a_{42}\hfill & a_{44}\hfill \end{array}\right|,\hfill & a_{14}^c=-\left|\begin{array}{lll}{a}_{21}\hfill & a_{22}\hfill & a_{23}\hfill \\ a_{31}\hfill & a_{32}\hfill & a_{33}\hfill \\ a_{41}\hfill & a_{42}\hfill & a_{43}\hfill \end{array}\right|.\hfill \end{array}$

The determinant of a matrix is found by taking the sum of products of the elements of any row or column with their cofactors. For example, the determinant of the 4 × 4 matrix above taken about its second column is

$\left|A\right|=a_{12}{a}_{12}^c+a_{22}{a}_{22}^c+a_{32}{a}_{32}^c+a_{42}{a}_{42}^c.$

We could do a similar expansion about any row or column and they would all yield the same result. Note the recursive nature of this expansion.

Example.

A concrete example for the determinant of a particular 3 × 3 matrix by expanding the cofactors of the first row is

$\begin{array}{cc}\hfill \left|\begin{array}{lll}0\hfill & 1\hfill & 2\hfill \\ 3\hfill & 4\hfill & 5\hfill \\ 6\hfill & 7\hfill & 8\hfill \end{array}\right|& =0\left|\begin{array}{ll}4\hfill & 5\hfill \\ 7\hfill & 8\hfill \end{array}\right|-1\left|\begin{array}{ll}3\hfill & 5\hfill \\ 6\hfill & 8\hfill \end{array}\right|+2\left|\begin{array}{ll}3\hfill & 4\hfill \\ 6\hfill & 7\hfill \end{array}\right|\hfill \\ \hfill & =0\left(32-35\right)-1\left(24-30\right)+2\left(21-24\right)\hfill \\ \hfill & =0.\hfill \end{array}$

We can deduce that the volume of the parallelepiped formed by the vectors defined by the columns (or rows since the determinant of the transpose is the same) is zero. This is equivalent to saying that the columns (or rows) are not linearly independent. Note that the sum of the first and third rows is twice the second row, which implies linear dependence.

5.3.1 Computing Inverses

Determinants give us a tool to compute the inverse of a matrix. It is a very inefficient method for large matrices, but often in graphics our matrices are small. A key to developing this method is that the determinant of a matrix with two identical rows is zero. This should be clear because the volume of the n-dimensional parallelepiped is zero if two of its sides are the same. Suppose we have a 4 × 4 A and we wish to find its inverse A−1. The inverse is

$A^{-1}=\frac{1}{\left|A\right|}\left[\begin{array}{llll}{a}_{11}^c\hfill & a_{21}^c\hfill & a_{31}^c\hfill & a_{41}^c\hfill \\ a_{12}^c\hfill & a_{22}^c\hfill & a_{32}^c\hfill & a_{42}^c\hfill \\ a_{13}^c\hfill & a_{23}^c\hfill & a_{33}^c\hfill & a_{43}^c\hfill \\ a_{14}^c\hfill & a_{24}^c\hfill & a_{34}^c\hfill & a_{44}^c\hfill \end{array}\right].$

Note that this is just the transpose of the matrix where elements of A are replaced by their respective cofactors multiplied by the leading constant (1 or -1). This matrix is called the adjoint of A. The adjoint is the transpose of the cofactor matrix of A. We can see why this is an inverse. Look at the product AA−1 which we expect to be the identity. If we multiply the first row of A by the first column of the adjoint matrix we need to get |A| (remember the leading constant above divides by |A|:

$\left[\begin{array}{llll}{a}_{11}\hfill & a_{12}\hfill & a_{13}\hfill & a_{14}\hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right]\left[\begin{array}{llll}{a}_{11}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{12}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{13}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{14}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right]=\left[\begin{array}{llll}\left|A\right|\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right].$

This is true because the elements in the first row of A are multiplied exactly by their cofactors in the first column of the adjoint matrix which is exactly the determinant. The other values along the diagonal of the resulting matrix are |A| for analogous reasons. The zeros follow a similar logic:

$\left[\begin{array}{llll}\cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{21}\hfill & a_{22}\hfill & a_{23}\hfill & a_{24}\hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right]\left[\begin{array}{llll}{a}_{11}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{12}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{13}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ a_{14}^c\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right]=\left[\begin{array}{llll}\cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ 0\hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \\ \cdot \hfill & \cdot \hfill & \cdot \hfill & \cdot \hfill \end{array}\right].$

Note that this product is a determinant of some matrix:

$a_{21}{a}_{11}^c+a_{22}{a}_{12}^c+a_{23}{a}_{13}^c+a_{24}{a}_{14}^c.$

The matrix in fact is

$\left[\begin{array}{llll}{a}_{21}\hfill & a_{22}\hfill & a_{23}\hfill & a_{24}\hfill \\ a_{21}\hfill & a_{22}\hfill & a_{23}\hfill & a_{24}\hfill \\ a_{31}\hfill & a_{32}\hfill & a_{33}\hfill & a_{34}\hfill \\ a_{41}\hfill & a_{42}\hfill & a_{43}\hfill & a_{44.}\hfill \end{array}\right].$

Because the first two rows are identical, the matrix is singular, and thus, its determinant is zero.

The argument above does not apply just to four by four matrices; using that size just simplifies typography. For any matrix, the inverse is the adjoint matrix divided by the determinant of the matrix being inverted. The adjoint is the transpose of the cofactor matrix, which is just the matrix whose elements have been replaced by their cofactors.

Example.

The inverse of one particular three by three matrix whose determinant is 6 is

$\begin{array}{cc}\hfill {\left[\begin{array}{lll}1\hfill & 1\hfill & 2\hfill \\ 1\hfill & 3\hfill & 4\hfill \\ 0\hfill & 2\hfill & 5\hfill \end{array}\right]}^{-1}& =\frac{1}{6}\left[-\begin{array}{rrr}\hfill \left|\begin{array}{rr}\hfill 3& \hfill 4\\ \hfill 2& \hfill 5\end{array}\right|& \hfill -\left|\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 2& \hfill 5\end{array}\right|& \hfill \left|\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 3& \hfill 4\end{array}\right|\\ \hfill \left|\begin{array}{rr}\hfill 1& \hfill 4\\ \hfill 0& \hfill 5\end{array}\right|& \hfill \left|\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 0& \hfill 5\end{array}\right|& \hfill -\left|\begin{array}{rr}\hfill 1& \hfill 2\\ \hfill 1& \hfill 4\end{array}\right|\\ \hfill \left|\begin{array}{rr}\hfill 1& \hfill 3\\ \hfill 0& \hfill 2\end{array}\right|& \hfill -\left|\begin{array}{rr}\hfill 1& \hfill 1\\ \hfill 0& \hfill 2\end{array}\right|& \hfill \left|\begin{array}{rr}\hfill 1& \hfill 1\\ \hfill 1& \hfill 3\end{array}\right|\end{array}\right]\hfill \\ \hfill & =\frac{1}{6}\left[\begin{array}{rrr}\hfill 7& \hfill -1& \hfill -2\\ \hfill -5& \hfill 5& \hfill -2\\ \hfill 2& \hfill -2& \hfill 2\end{array}\right].\hfill \end{array}$

You can check this yourself by multiplying the matrices and making sure you get the identity.

5.3.2 Linear Systems

We often encounter linear systems in graphics with “n equations and n unknowns,” usually for n = 2 or n = 3. For example,

$\begin{array}{cc}\hfill 3x+7y+2z& =4,\hfill \\ \hfill 2x-4y-3z& =-1,\hfill \\ \hfill 5x+2y+z& =1.\hfill \end{array}$

Here x, y, and z are the “unknowns” for which we wish to solve. We can write this in matrix form:

$\left[\begin{array}{rrr}\hfill 3& \hfill 7& \hfill 2\\ \hfill 2& \hfill -4& \hfill -3\\ \hfill 5& \hfill 2& \hfill 1\end{array}\right]\left[\begin{array}{r}\hfill x\\ \hfill y\\ \hfill z\end{array}\right]=\left[\begin{array}{r}\hfill 4\\ \hfill -1\\ \hfill 1\end{array}\right].$

A common shorthand for such systems is Ax = b where it is assumed that A is a square matrix with known constants, x is an unknown column vector (with elements x, y, and z in our example), and b is a column matrix of known constants.

There are many ways to solve such systems, and the appropriate method depends on the properties and dimensions of the matrix A. Because in graphics we so frequently work with systems of size n ≤ 4, we’ll discuss here a method appropriate for these systems, known as Cramer’s rule, which we saw earlier, from a 2D geometric viewpoint, in the example on page 90. Here, we show this algebraically. The solution to the above equation is

$x{=}_{\left|\begin{array}{rrr}\hfill 3& \hfill 7& \hfill 2\\ \hfill 2& \hfill -4& \hfill -3\\ \hfill 5& \hfill 2& \hfill 1\end{array}\right|}^{\underset{¯}{\left|\begin{array}{rrr}\hfill 4& \hfill 7& \hfill 2\\ \hfill -1& \hfill -4& \hfill -3\\ \hfill 1& \hfill 2& \hfill 1\end{array}\right|}};y{=}_{\left|\begin{array}{rrr}\hfill 3& \hfill 7& \hfill 2\\ \hfill 2& \hfill -4& \hfill -3\\ \hfill 5& \hfill 2& \hfill 1\end{array}\right|}^{\underset{¯}{\left|\begin{array}{rrr}\hfill 3& \hfill 4& \hfill 2\\ \hfill 2& \hfill -1& \hfill -3\\ \hfill 5& \hfill 1& \hfill 1\end{array}\right|}};z{=}_{\left|\begin{array}{rrr}\hfill 3& \hfill 7& \hfill 2\\ \hfill 2& \hfill -4& \hfill -3\\ \hfill 5& \hfill 2& \hfill 1\end{array}\right|}^{\underset{¯}{\left|\begin{array}{rrr}\hfill 3& \hfill 7& \hfill 4\\ \hfill 2& \hfill -4& \hfill -1\\ \hfill 5& \hfill 2& \hfill 1\end{array}\right|}}.$

The rule here is to take a ratio of determinants, where the denominator is |A| and the numerator is the determinant of a matrix created by replacing a column of A with the column vector b. The column replaced corresponds to the position of the unknown in vector x. For example, y is the second unknown and the second column is replaced. Note that if |A| = 0, the division is undefined and there is no solution. This is just another version of the rule that if A is singular (zero determinant) then there is no unique solution to the equations.

5.4 Eigenvalues and Matrix Diagonalization

Square matrices have eigenvalues and eigenvectors associated with them. The eigenvectors are those nonzero vectors whose directions do not change when multiplied by the matrix. For example, suppose for a matrix A and vector a, we have

$\mathrm{Aa}=\text{λa}\text{.}\text{ (5.9)}$

This means we have stretched or compressed a, but its direction has not changed. The scale factor λ is called the eigenvalue associated with eigenvector a. Knowing the eigenvalues and eigenvectors of matrices is helpful in a variety of practical applications. We will describe them to gain insight into geometric transformation matrices and as a step toward singular values and vectors described in the next section.

If we assume a matrix has at least one eigenvector, then we can do a standard manipulation to find it. First, we write both sides as the product of a square matrix with the vector a:

$\mathrm{Aa}=\text{λIa,}\text{ (5.10)}$

where I is an identity matrix. This can be rewritten

$\mathrm{Aa}-\text{λIa}=0.\text{ (5.11)}$

Because matrix multiplication is distributive, we can group the matrices:

$\left(A-\text{λI}\right)a=0.\text{ (5.12)}$

This equation can only be true if the matrix (A − λI) is singular, and thus its determinant is zero. The elements in this matrix are the numbers in A except along the diagonal. For example, for a 2 × 2 matrix the eigenvalues obey

$\left|\begin{array}{ll}{a}_{11}-\text{λ}\hfill & a_{12}\hfill \\ a_{21}\hfill & a_{22}-\text{λ}\hfill \end{array}\right|={\text{λ}}^{\text{2}}-\left(a_{11}+a_{22}\right)\text{λ}+\left(a_{11}{a}_{22}-a_{12}{a}_{21}\right)=0.\text{ (5.13)}$

Because this is a quadratic equation, we know there are exactly two solutions for λ. These solutions may or may not be unique or real. A similar manipulation for an n × n matrix will yield an nth-degree polynomial in λ. Because it is not possible, in general, to find exact explicit solutions of polynomial equations of degree greater than four, we can only compute eigenvalues of matrices 4 × 4 or smaller by analytic methods. For larger matrices, numerical methods are the only option.

An important special case where eigenvalues and eigenvectors are particularly simple is symmetric matrices (where A = AT). The eigenvalues of real symmetric matrices are always real numbers, and if they are also distinct, their eigenvectors are mutually orthogonal. Such matrices can be put into diagonal form:

$A={\mathrm{QDQ}}^{\text{T}},\text{ (5.14)}$

where Q is an orthogonal matrix and D is a diagonal matrix. The columns of Q are the eigenvectors of A and the diagonal elements of D are the eigenvalues of A. Putting A in this form is also called the eigenvalue decomposition, because it decomposes A into a product of simpler matrices that reveal its eigenvectors and eigenvalues.

Example.

Given the matrix

$A=\left[\begin{array}{ll}2\hfill & 1\hfill \\ 1\hfill & 1\hfill \end{array}\right],$

the eigenvalues of A are the solutions to

${\text{λ}}^{\text{2}}-3\text{λ}+1=0.$

We approximate the exact values for compactness of notation:

$\text{λ}=\frac{3\pm \sqrt{5}}{2},\approx \left[\begin{array}{c}2.618\\ 0.382\end{array}\right].$

Now we can find the associated eigenvector. The first is the nontrivial (not x = y = 0) solution to the homogeneous equation,

$\left[\begin{array}{cc}2-2.618& 1\\ 1& 1-2.618\end{array}\right]\left[\begin{array}{c}x\\ y\end{array}\right]=\left[\begin{array}{c}0\\ 0\end{array}\right].$

This is approximately (x, y) = (0.8507, 0.5257). Note that there are infinitely many solutions parallel to that 2D vector, and we just picked the one of unit length. Similarly the eigenvector associated with λ2 is (x, y) = (−0.5257, 0.8507). This means the diagonal form of A is (within some precision due to our numeric approximation):

$\left[\begin{array}{cc}2& 1\\ 1& 1\end{array}\right]=\left[\begin{array}{rr}\hfill 0.8507& \hfill -0.5257\\ \hfill 0.5257& \hfill 0.8507\end{array}\right]\left[\begin{array}{cc}2.618& 0\\ 0& 0.382\end{array}\right]\left[\begin{array}{rr}\hfill 0.8507& \hfill 0.5257\\ \hfill -0.5257& \hfill 0.8507\end{array}\right].$

We will revisit the geometry of this matrix as a transform in the next chapter.

5.4.1 Singular Value Decomposition

We saw in the last section that any symmetric matrix can be diagonalized, or decomposed into a convenient product of orthogonal and diagonal matrices. However, most matrices we encounter in graphics are not symmetric, and the eigenvalue decomposition for nonsymmetric matrices is not nearly so convenient or illuminating, and in general involves complex-valued eigenvalues and eigenvectors even for real-valued inputs.

There is another generalization of the symmetric eigenvalue decomposition to nonsymmetric (and even non-square) matrices; it is the singular value decomposition (SVD). The main difference between the eigenvalue decomposition of a symmetric matrix and the SVD of a nonsymmetric matrix is that the orthogonal matrices on the left and right sides are not required to be the same in the SVD:

$A={\mathrm{USV}}^{\text{T}}.$

Here U and V are two, potentially different, orthogonal matrices, whose columns are known as the left and right singular vectors of A, and S is a diagonal matrix whose entries are known as the singular values of A. When A is symmetric and has all nonnegative eigenvalues, the SVD and the eigenvalue decomposition are the same.

There is another relationship between singular values and eigenvalues that can be used to compute the SVD (though this is not the way an industrial-strength SVD implementation works). First we define M = AAT. We assume that we can perform a SVD on M:

$M={\mathrm{AA}}^{\text{T}}=\left({\mathrm{USV}}^{\text{T}}\right){\left({\mathrm{USV}}^{\text{T}}\right)}^{\text{T}}=\mathrm{US}\left(V^{\text{T}}V\right){\mathrm{SU}}^{\text{T}}={\mathrm{US}}^{\text{2}}{U}^{\text{T}}.$

The substitution is based on the fact that (BC)T = CTBT, that the transpose of an orthogonal matrix is its inverse, and the transpose of a diagonal matrix is the matrix itself. The beauty of this new form is that M is symmetric and US2UT is its eigenvalue decomposition, where S2 contains the (all nonnegative) eigenvalues. Thus, we find that the singular values of a matrix are the square roots of the eigenvalues of the product of the matrix with its transpose, and the left singular vectors are the eigenvectors of that product. A similar argument allows V, the matrix of right singular vectors, to be computed from ATA.

Example.

We now make this concrete with an example:

$A=\left[\begin{array}{ll}1\hfill & 1\hfill \\ 0\hfill & 1\hfill \end{array}\right];M={\mathrm{AA}}^{\text{T}}=\left[\begin{array}{ll}2\hfill & 1\hfill \\ 1\hfill & 1\hfill \end{array}\right].$

We saw the eigenvalue decomposition for this matrix in the previous section. We observe immediately

$\left[\begin{array}{ll}1\hfill & 1\hfill \\ 0\hfill & 1\hfill \end{array}\right]=\left[\begin{array}{rr}\hfill 0.8507& \hfill -0.5257\\ \hfill 0.5257& \hfill 0.8507\end{array}\right]\left[\begin{array}{cc}\sqrt{2.618}& 0\\ 0& \sqrt{0.382}\end{array}\right]V^{\text{T}}.$

We can solve for V algebraically:

$V={\left(S^{-1}{U}^{\text{T}}A\right)}^{\text{T}}.$

The inverse of S is a diagonal matrix with the reciprocals of the diagonal elements of S. This yields

$\begin{array}{cc}\hfill \left[\begin{array}{ll}1\hfill & 1\hfill \\ 0\hfill & 1\hfill \end{array}\right]& =U\left[\begin{array}{ll}{\sigma }_1\hfill & 0\hfill \\ 0\hfill & {\sigma }_2\hfill \end{array}\right]V^{\text{T}}\hfill \\ \hfill & =\left[\begin{array}{rr}\hfill 0.8507& \hfill -0.5257\\ \hfill 0.5257& \hfill 0.8507\end{array}\right]\left[\begin{array}{cc}\hfill 1.618& 0\hfill \\ \hfill 0& 0.618\hfill \end{array}\right]\left[\begin{array}{rr}\hfill 0.5257& \hfill 0.8507\\ \hfill -0.8507& \hfill 0.5257\end{array}\right].\hfill \end{array}$

This form used the standard symbol σi for the ith singular value. Again, for a symmetric matrix, the eigenvalues and the singular values are the same (σi = λi). We will examine the geometry of SVD further in Section 6.1.6.

Frequently Asked Questions

• Why is matrix multiplication defined the way it is rather than just element by element?

  Element by element multiplication is a perfectly good way to define matrix multiplication, and indeed it has nice properties. However, in practice it is not very useful. Ultimately, most matrices are used to transform column vectors, e.g., in 3D you might have

  $\mathbf{b}\mathbf{=}\mathbf{Ma},$

  where a and b are vectors and M is a 3×3 matrix. To allow geometric operations such as rotation, combinations of all three elements of a must go into each element of b. That requires us to either go row-by-row or column-by-column through M. That choice is made based on composition of matrices having the desired property,

  $M_{\text{2}}\left(M_{\text{1}}a\right)=\left(M_{\text{2}}{M}_{\text{1}}\right)a$

  which allows us to use one composite matrix C = M2M1 to transform our vector. This is valuable when many vectors will be transformed by the same composite matrix. So, in summary, the somewhat weird rule for matrix multiplication is engineered to have these desired properties.

• Sometimes I hear that eigenvalues and singular values are the same thing and sometimes that one is the square of the other. Which is right?

  If a real matrix A is symmetric, and its eigenvalues are nonnegative, then its eigenvalues and singular values are the same. If A is not symmetric, the matrix M = AAT is symmetric and has nonnegative real eignenvalues. The singular values of A and AT are the same and are the square roots of the singular/eigenvalues of M. Thus, when the square root statement is made, it is because two different matrices (with a very particular relationship) are being talked about: M = AAT.

Notes

The discussion of determinants as volumes is based on A Vector Space Approach to Geometry (Hausner, 1998). Hausner has an excellent discussion of vector analysis and the fundamentals of geometry as well. The geometric derivation of Cramer’s rule in 2D is taken from Practical Linear Algebra: A Geometry Toolbox (Farin & Hansford, 2004). That book also has geometric interpretations of other linear algebra operations such as Gaussian elimination. The discussion of eigenvalues and singular values is based primarily on Linear Algebra and Its Applications (Strang, 1988). The example of SVD of the shear matrix is based on a discussion in Computer Graphics and Geometric Modeling (Salomon, 1999).

Exercises

1. Write an implicit equation for the 2D line through points (x0, y0) and (x1, y1) using a 2D determinant.
2. Show that if the columns of a matrix are orthonormal, then so are the rows.
3. Prove the properties of matrix determinants stated in Equations (5.5)-(5.7).
4. Show that the eigenvalues of a diagonal matrix are its diagonal elements.
5. Show that for a square matrix A, AAT is a symmetric matrix.
6. Show that for three 3D vectors a, b, c, the following identity holds: |abc| = (a × b) ⋅ c.
7. Explain why the volume of the tetrahedron with side vectors a, b, c (see Figure 5.2) is given by |abc|/6.

8. Demonstrate the four interpretations of matrix-matrix multiplication by taking the following matrix-matrix multiplication code, rearranging the nested loops, and interpreting the resulting code in terms of matrix and vector operations.

   function mat-mult(in a[m][p], in b[p][n], out c[m][n]) {

    // the array c is initialized to zero

    for i = 1 to m

      for j = 1 to n

      for k = 1 to p

       c[i][j] += a[i][k] * b[k][j]

   }

9. Prove that if A, Q, and D satisfy Equation (5.14), v is the ith row of Q, and λ is the ith entry on the diagonal of D, then v is an eigenvector of A with eigenvalue λ.
10. Prove that if A, Q, and D satisfy Equation (5.14), the eigenvalues of A are all distinct, and v is an eigenvector of A with eigenvalue λ, then for some i, v is the ith row of Q and λ is the ith entry on the diagonal of D.
11. Given the (x, y) coordinates of the three vertices of a 2D triangle, explain why the area is given by

$\frac{1}{2}\left|\begin{array}{lll}{x}_0\hfill & x_1\hfill & x_2\hfill \\ y_0\hfill & y_1\hfill & y_2\hfill \\ 1\hfill & 1\hfill & 1\hfill \end{array}\right|.$