Today we will discuss a couple final properties of the determinant, and then look at an application of the determinant to a field close to my research, namely graph theory.

Multiplicativity of the determinant

An essential property of the determinant is that it is multiplicative:

Theorem (determinant is multiplicative)

For any two \(n \times n\) matrices \(A\) and \(B,\) we have \(\det(AB) = \det(A) \det(B).\)

In my opinion, this fact is very surprising: we defined \(\det(A)\) as a big summation of many terms (one for each pattern in \(A\)), so there's no reason to expect that the determinant has a nice property with respect to multiplication. Nevertheless, it's true!

There are several proofs of this theorem, at various levels of abstraction. Here is one possible proof, based loosely on the textbook's version. (Feel free to skip the proof; it is rather technical and not super important for us.)

Proof: Let's first deal with the case where \(A\) is not invertible. In this case, we know that \(\det(A) \det(B) = 0,\) so we just want to show that \(\det(AB) = 0,\) that is, \(AB\) is also not invertible. A good way to see this is to write \[B = \begin{bmatrix} | & & | \\ \mathbf{b}_1 & \dotsm & \mathbf{b}_n \\ | & & | \end{bmatrix}.\] Then, using our very first definition of matrix multiplication, we have \[AB = \begin{bmatrix} | & & | \\ A\mathbf{b}_1 & \dotsm & A\mathbf{b}_n \\ | & & | \end{bmatrix}.\] We want to show that the columns of \(AB\) are linearly dependent. If \(A\) is not invertible, its column space is not all of \(\mathbb{R}^n\); therefore, it is a subspace of \(\mathbb{R}^n\) with dimension less than \(n.\) But the \(n\) vectors \(A\mathbf{b}_1,\) \(\dots,\) \(A\mathbf{b}_n\) all lie in that column space by definition, so they must be linearly dependent. This finishes our first case.

For the rest of the proof, we can assume that \(A\) is invertible. We use what we know about determinants and row reduction. Let's set up the augmented matrix \( \left[ AB \;\; | \;\; A \right].\) This may remind you of how we compute inverses of matrices. Specifically, this augmented matrix represents \(n\) different linear systems: \(AB \mathbf{x}_1 = A\mathbf{e}_1,\) \(AB \mathbf{x}_2 = A\mathbf{e}_2,\) etc., up to \(AB \mathbf{x}_n = A\mathbf{e}_n.\) For each of these systems \(AB \mathbf{x}_i = A\mathbf{e}_i,\) we can multiply on the left by \(A^{-1}\) to get \(B \mathbf{x}_i = \mathbf{e}_i.\) This implies that by using row operations, we can go from \[\left[ AB \;\; | \;\; A \right] \qquad \text{to} \qquad \left[ B \;\; | \;\; I_n \right].\] (This is the hardest claim to justify in this proof. Implicitly, we are saying that row operations are really the same as multiplying on the left by certain matrices. However, we didn't cover this fact in class; the textbook describes this process in terms of elementary matrices if you want more details.)

Now here is the key point: row operations multiply the determinant by a (nonzero) constant. (Recall that we showed this for each type of row operation.) Therefore, in our augmented matrix, the ratio between the determinants of the two sides stays the same under row operations. In other words, \[\frac{\det(AB)}{\det(A)} = \frac{\det(B)}{\det(I_n)}.\] (We assumed that \(A\) is invertible, so \(\det(A)\) is nonzero and it makes sense to divide by it.) Since \(\det(I_n) = 1,\) this simplifies to \(\det(AB) = \det(A) \det(B),\) as desired.

Let's see an example of this property in action.

Example (determinant of a product)

We have \[\begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix}.\] This should imply that \[\det \begin{bmatrix} 1 & 2 \\ 3 & 4 \end{bmatrix} \det \begin{bmatrix} 5 & 6 \\ 7 & 8 \end{bmatrix} = \det \begin{bmatrix} 19 & 22 \\ 43 & 50 \end{bmatrix}.\] Computing each determinant, we get \[(1 \cdot 4 - 2 \cdot 3) (5 \cdot 8 - 6 \cdot 7) = (19 \cdot 50 - 22 \cdot 43),\] which simplifies to just \((-2)(-2) = 4.\) True!

Determinants of powers and inverses

By iterating the multiplicativity property, we get the following fact for powers of a matrix:

Corollary (determinant of matrix power)

For any \(n \times n\) matrix \(A\) and any positive integer \(k,\) we have \(\det(A^k) = \det(A)^k.\)

We can also use multiplicativity to deduce a formula for the determinant of the inverse of a matrix:

Corollary (determinant of inverse matrix)

For any invertible \(n \times n\) matrix \(A,\) we have \(\det(A^{-1}) = \frac{1}{\det(A)}.\)

To prove this, we use the fact that \(A A^{-1} = I_n.\) Because the determinant is multiplicative, this means that \(\det(A) \det(A^{-1}) = \det(I_n) = 1,\) so we indeed get \(\det(A^{-1}) = \frac{1}{\det(A)}.\)

We can also use multiplicativity to establish a fact about the invertibility of a product of a matrices.

Corollary (invertibility of product)

Let \(A\) and \(B\) be \(n \times n\) matrices. Then \(AB\) is invertible if and only if both \(A\) and \(B\) are invertible. Furthermore, if \(AB\) is invertible, then \((AB)^{-1} = B^{-1} A^{-1}.\)

To prove the first statement, we use the fact that \(\det(AB) = \det(A) \det(B).\) So, \(\det(AB)\) is nonzero if and only if both \(\det(A)\) and \(\det(B)\) are nonzero. Proving the second statement does not actually involve determinants; we can simply compute \[(AB)(B^{-1}A^{-1}) = A(BB^{-1})A^{-1} = AI_nA^{-1} = AA^{-1} = I_n.\] This means that \(AB\) and \(B^{-1}A^{-1}\) are inverses, as claimed.

Warning: the determinant is NOT additive

By contrast, it is not true in general that \(\det(A+B) = \det(A) + \det(B).\) For example, \[\begin{bmatrix} 1 & 0 \\ 0 & 0 \end{bmatrix} + \begin{bmatrix} 0 & 0 \\ 0 & 1 \end{bmatrix} = \begin{bmatrix} 1 & 0 \\ 0 & 1 \end{bmatrix},\] but if we were to try to replace each matrix with its determinant, we would get \[0 + 0 = 1,\] which is of course not true.

Determinants and volumes

To finish off our discussion of determinants, we will briefly touch on an interesting geometric interpretation of the determinant: the determinant of (the matrix of) a linear transformation tells you by how much volumes get scaled under the transformation.

Specifically, consider an \(n \times n\) matrix \[A = \begin{bmatrix} | & & | \\ \mathbf{v}_1 & \dotsm & \mathbf{v}_n \\ | & & | \end{bmatrix}.\] The \(n\) vectors \(\mathbf{v}_1, \dots, \mathbf{v}_n\) determine an \(n\)-dimensional solid called a parallelepiped.

In \(\mathbb{R}^2,\) this is more familiar: two vectors \(\mathbf{v}_1\) and \(\mathbf{v}_2\) determine a parallelogram, whose vertices are at the points \(\mathbf{0},\) \(\mathbf{v}_1,\) \(\mathbf{v}_2,\) and \(\mathbf{v}_1 + \mathbf{v}_2.\) Below is a picture of a parallelepiped in \(\mathbb{R}^3\) determined by three vectors, \(\mathbf{a},\) \(\mathbf{b},\) and \(\mathbf{c}.\) (Image adapted from this link.)

It turns out that the volume of this parallelepiped is essentially given by the determinant of the matrix.

Theorem (determinant and parallelepiped volumes)

Let \(\mathbf{v}_1, \ldots, \mathbf{v}_n\) be vectors in \(\mathbb{R}^n\) and let \(A = \begin{bmatrix} | & & | \\ \mathbf{v}_1 & \dotsm & \mathbf{v}_n \\ | & & | \end{bmatrix}.\) Then the volume of the \(n\)-dimensional parallelepiped determined by \(\mathbf{v}_1, \dots, \mathbf{v}_n\) is equal to \(|\det(A)|.\)

In particular, consider the case where \(A\) is not invertible. Then, its columns \(\mathbf{v}_1, \ldots, \mathbf{v}_n\) do not span all of \(\mathbb{R}^n,\) so they must lie in some subspace of \(\mathbb{R}^n\) with lower dimension. This means that the parallelepiped they determine is "flat": its \(n\)-dimensional volume is zero. This corresponds to the fact that \(\det(A) = 0,\) since \(A\) is not invertible.

Determinants and linear transformations

We can also think of this in terms of linear transformations. If \(T(\mathbf{x}) = A\mathbf{x},\) remember that each of the columns of \(A\) is the image under \(T\) of one of the standard basis vectors: \[T(\mathbf{e}_i) = \mathbf{v}_i.\] Now, the parallelepiped determined by the standard basis vectors is the unit hypercube \(H_n.\) As you may expect, the unit hypercube has volume \(1.\) Therefore, \(T\) maps the unit hypercube, which has volume \(1,\) to the parallelepiped determined by \(\mathbf{v}_1, \dots, \mathbf{v}_n,\) which has volume \(|\det(A)|.\) The ratio of the volume of the image and the volume of the original is \(|\det(A)|.\)

In fact, this is true for any solid region in \(\mathbb{R}^n\):

Theorem (determinant and volume ratios)

Let \(T \colon \mathbb{R}^n \to \mathbb{R}^n\) be a linear transformation with matrix \(A.\) Then, for any region \(E \subseteq \mathbb{R}^n,\) we have \[\frac{\text{Vol } T(E)}{\text{Vol } E} = |\det(A)|,\] where \(\text{Vol}\) denotes \(n\)-dimensional volume.

Here is a basic example of this.

Example (determinant of a scaling matrix)

Suppose that the linear transformation \(T \colon \mathbb{R}^2 \to \mathbb{R}^2\) is defined by \(T(\mathbf{x}) = 5 \mathbf{x}.\) In other words, \(T\) scales every vector up by a factor of 5. What does \(T\) do to volumes, or as they're known in the 2-dimensional case, areas?

Because area is a 2-dimensional quantity, we would expect the area of a region to be scaled by a factor of \(5^2,\) or \(25.\) In fact, we can check this intuition against the determinant. By computing what \(T\) does to the standard basis, we can see that its matrix is \[A = \begin{bmatrix} 5 & 0 \\ 0 & 5 \end{bmatrix}.\] Then, \(\det(A) = 5 \cdot 5 - 0 \cdot 0 = 25,\) which matches our intuition about areas.

This also gives another reason that the determinant should be multiplicative, or at least its absolute value. This is because \(AB\) represents the composition of the linear transformations represented by \(A\) and \(B.\) Therefore, if these linear transformations multiply volumes by \(|\det(A)|\) and \(|\det(B)|,\) then the linear transformation for \(AB\) should multiply volumes by \(|\det(A)| \cdot |\det(B)|.\) This means that \[|\det(AB)| = |\det(A)| \cdot |\det(B)|.\]

The sign of the determinant

Finally, you may wonder: if the absolute value of \(\det(A)\) tells us the "scaling ratio" of a linear transformation \(T(\mathbf{x}) = A\mathbf{x},\) what does the sign (\(+\) or \(-\)) of \(\det(A)\) indicate? It turns out that this indicates whether or not \(T\) is orientation-preserving (if \(\det(A) > 0\)) or orientation-reversing (if \(\det(A) < 0\)). These terms have formal definitions (in fact, they are often defined using the sign of the determinant!), but for our purposes we can just think intuitively:

• For example, if \(T\) represents a scaling, then \(T\) is orientation-preserving. A region in \(\mathbb{R}^n\) will change size when \(T\) is applied, but it won't undergo any "flips." Therefore, the matrix of \(T\) should have positive determinant.
• On the other hand, if \(T\) represents a reflection, then \(T\) is orientation-reversing, and so the matrix of \(T\) should have negative determinant.

(You'll get a chance to see this for yourself on the homework!)

Application: graphs and spanning trees

For the rest of this class, we're going to pivot to a topic that is not entirely within the scope of the course, but which is close to my area of research, combinatorics.

Combinatorics is essentially the science/art of counting, and the study of discrete things like networks and data structures (as opposed to continuous things like functions and integrals). Perhaps surprisingly, there are many examples of things in combinatorics that can be counted using determinants. This is great because, as we've seen, we know a lot about determinants, including relatively fast ways to compute them.

This material won't be covered on homework or exams, but I think that it's worth it to see an interesting application of what we've learned so far.

Graphs

A graph is a collection of vertices, with some pairs of edges connected by lines called edges. (Note: we also use the word "graph" to refer to a plot, as in the "graph of a function," but this is a different concept.)

Below is an example of a graph. (Image taken from this link.) The vertices of the graph are drawn as small circles, and labeled 1 through 5. There are 5 edges, labeled \(e_1\) through \(e_5,\) each of which connects a different pair of vertices.

We will assume that no two edges connect the same pair of vertices, and no edge connects a vertex to itself. Therefore, we are only considering what are called simple graphs: for every unordered pair of two different vertices, there is either one edge between them, or none.

Graphs are extremely common in applied mathematics and throughout the sciences. They can be used to represent roads, Internet connections, molecular bonds, relationships between people, the spread of a disease, and so on.

Trees and spanning trees

A graph is called connected if one can get from any vertex to any other vertex by following a path of edges. The graph above is connected; for example, you can get from \(2\) to \(4\) by following edges \(e_1,\) \(e_3,\) and \(e_5.\)

For a graph with \(n\) vertices to be connected, it must have at least \(n-1\) edges. To see why, imagine starting with no edges, so that the graph consists of \(n\) separate vertex "components." Each edge we add to the graph can only connect two of these components, thereby reducing the number of components by \(1.\) So, in order to get to a single connected component, we need to add at least \(n-1\) edges.

A tree is defined to be a connected graph with \(n\) vertices and exactly \(n-1\) edges. In other words, a tree is a graph that is connected using as few edges as possible. An equivalent definition of trees is that they are connected graphs that do not have cycles: groups of edges that form a loop.

Given a graph, a spanning tree is a way to choose some of the edges of the graph so that the graph with those edges is a tree. In other words, a spanning tree is a tree that exists within a given graph.

Spanning trees are very important in optimization. If a graph represents a bunch of towns and the locations of possible highways that can be built between them, then a spanning tree gives a way to construct as few highways as possible while having all the towns are connected to each other by highways. (When each highway has a cost associated with building it, this becomes the problem of finding a minimal spanning tree.)

Combinatorialists love to count things, so given a graph, we might ask: how many different spanning trees does it have? For example, here is the graph from earlier:

There are 3 spanning trees: one where we take all the edges except \(e_2,\) one where we take all the edges except \(e_3,\) and one where we take all the edges except \(e_4.\)

This graph is pretty small, so counting the spanning trees is easy. However, how can we determine the number of spanning trees in general? A beautiful theorem by Gustav Kirchhoff (1824–1887) says that we can do so simply by computing the right determinant. (You may recognize the name Kirchhoff from his two laws governing electrical circuits.)

Kirchhoff's matrix-tree theorem

To use Kirchhoff's theorem, we take our graph and use it to construct a certain matrix called the Laplacian matrix of the graph.

Definition (Laplacian matrix)

Let \(G\) be a graph with vertices numbered \(1, 2, \dots, n.\) The Laplacian matrix \(L\) of the graph \(G\) is the \(n \times n\) matrix defined as follows:

(1) For all \(i,\) the diagonal entry \(L_{i,i}\) equals the number of edges touching vertex \(i.\) (This is called the degree of vertex \(i.\))

(2) For \(i \neq j,\) the entry \(L_{i,j}\) equals \(-1\) if vertices \(i\) and \(j\) have an edge between them, otherwise it equals zero.

As an example, consider the graph from earlier:

Kirchhoff proved that the cofactors of \(L\) tell us the number of spanning trees of the graph:

Theorem (Kirchhoff's matrix-tree theorem)

Let \(G\) be a graph and let \(L\) be the Laplacian matrix of \(G.\) Then any cofactor of \(L\) equals the number of spanning trees of \(G.\)

(I won't give a proof of this; it involves yet more facts about the determinant than we've learned.)

In our running example, we can take the \((1,1)\)-cofactor of \(L\) (which has a positive sign attached, according to the formula for cofactors.) This is the determinant \[C_{1,1}(L) = \left|\begin{matrix} 1 & 0 & 0 & 0 \\ 0 & 3 & -1 & -1 \\ 0 & -1 & 1 & 0 \\ 0 & -1 & 0 & 2 \end{matrix} \right|. \] Let's compute this determinant. Because the first row (or first column) has so many zeroes, let's do cofactor expansion along the first row; that gives us  \[C_{1,1}(L) = 1 \left|\begin{matrix} 3 & -1 & -1 \\ -1 & 1 & 0 \\ -1 & 0 & 2 \end{matrix} \right|. \] Now we can use our shortcut method for \(3 \times 3\) determinants, which gives \[C_{1,1}(L) = (3)(1)(2) + (-1)(0)(-1) + (-1)(-1)(0) - (-1)(1)(-1) - (-1)(-1)(2) - (3)(0)(0) = 6 + 0 + 0 - 1 - 2 - 0 = 3.\] This matches our manual count from earlier!

Cayley's formula

As another example of the matrix-tree theorem, we can derive Cayley's formula, a famous result in graph theory. Cayley's formula gives the overall number of different trees with vertices labeled \(1, 2, \dots, n.\) For instance, there are 16 trees with vertices labeled \(1, 2, 3, 4\) (image from here):

The key insight is that each of these trees is a spanning tree of the complete graph on \(n\) vertices: the graph \(K_n\) with vertices \(1, 2, \dots, n\) in which all possible edges are drawn. (Some small examples of complete graphs are below.) Then, to find the number of trees with vertices \(1, 2, \dots, n,\) we can apply the matrix-tree theorem to \(K_n.\)

In \(K_n,\) every pair of vertices is connected. Therefore, each vertex has degree \(n-1,\) and the Laplacian matrix is \[L = \begin{bmatrix} n-1 & -1 & -1 & \dotsm & -1 \\ -1 & n-1 & -1 & \dotsm & -1 \\ -1 & -1 & n-1 & \dotsm & -1 \\ \vdots & \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & -1 & \dotsm & n-1 \end{bmatrix}\] (this is an \(n \times n\) matrix). By the matrix-tree theorem, the number of spanning trees of \(K_n\) is given by any cofactor of \(L,\) such as \[C_{1,1}(L) = \left| \begin{matrix} n-1 & -1 & \dotsm & -1 \\ -1 & n-1 & \dotsm & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dotsm & n-1 \end{matrix} \right|.\] (Note that this is now an \((n-1) \times (n-1)\) matrix!) Computing this determinant is not easy, but we can do so using row operations. However, rather than do the usual row reduction algorithm, we can be sneaky: first, let's add all the other rows to the first row. This won't change the determinant, and the result will be \[C_{1,1}(L) = \left| \begin{matrix} 1 & 1 & \dotsm & 1 \\ -1 & n-1 & \dotsm & -1 \\ \vdots & \vdots & \ddots & \vdots \\ -1 & -1 & \dotsm & n-1 \end{matrix} \right|.\] (This is because in each column, there was an \(n-1\) and then \(n-2\) copies of \(-1.\)) Now, we can add the new first row to every other row. Again, this won't change the determinant, but it will cancel out almost every entry in the matrix: \[C_{1,1}(L) = \left| \begin{matrix} 1 & 1 & \dotsm & 1 \\ 0 & n & \dotsm & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dotsm & n \end{matrix} \right|.\] Now this is an (upper) triangular matrix! Therefore, its determinant is just the product of the entries along the diagonal. There is a single \(1\) and then \(n-2\) copies of \(n,\) so \[C_{1,1}(L) = n^{n-2}.\] This proves Cayley's formula:

Theorem (Cayley's formula)

The number of distinct trees with vertices labeled \(1, 2, \dots, n\) is \(n^{n-2}.\)

Not the kind of number you see every day!