6.2 Determinants - ESE 2030 📏

1Reading¶

Material related to this page, as well as additional exercises, can be found in ALA 1.9.

2Learning Objectives¶

By the end of this page, you should know:

some key facts of the determinant,
several ways to find the determinant of a matrix,
(optional) the formal definition of a determinant.

3Determinants¶

We assume that you have already seen determinants in Math 1410, and focus here on reviewing the key properties. Before proceeding, we pause to note that determinants have very deep meanings, especially in differential calculus, as they keep track of volumes as they are transformed via (linear or otherwise) functions. They are indeed very useful theoretical tools, but much like matrix inverses, are rarely computed by hand, except for $2 \times 2$ cases. Below is a helpful link if you need a refresher on the determinant.

Math 1410 video lecture (geometric interpretation of the determinant for small matrices)

3.1Key Properties of the Determinant¶

First, we’ll state a couple of key facts about the determinant.

Definition 1 (Key Properties of the Determinant)

The determinant of a matrix $A$ , written $\det A$ or $|A|$ , is only defined if $A$ is square.
The determinant of a $1\times 1$ matirx $A = [a]$ is $\det [a] = a$ . The determinant of a $2 \times 2$ matrix is $\det \bm a & b\\ c & d \em= ad - bc$ . You may recognize this expression from our formula for the inverse of a $2\times 2$ matrix:

\bm a & b\\c&d \em^{-1} = \frac{1}{ad -bc}\bm d&-b\\-c&a \em.

(1)

In this case, $\bm a & b\\c&d \em^{-1}$ exists if and only if $ad - bc \neq 0$ i.e. $\det \bm a & b\\c&d \em \neq 0$ . This observation is true in general for matrices of any size. This means that that $A$ is singular if and only if $\det A = 0$ , a fact that we will use in our eigenvalue computations later.
If $U$ is a block upper diagonal matrix, i.e., if $U = \bm U_{11} & U_{12} \\ 0 & U_{22}\em$ for $U_{ij}$ of compatible dimension, then $\det U = \det{U_{11}} \cdot\det{U_{22}}$ , i.e., the determinant of $U$ is given by the products of the determinants of its block diagonals.
The determinant of a matrix is equal to the determinant of its transpose, $\det A = \det A^\top$ .

These facts (and more) are all derivable from a basic principles of the determinant, but, as with many other topics in mathematics, the rabbit hole goes incredibly deep. For the purpose of studying eigenvalues and eigenvectors this is all we need, but for sake of completeness we included the rest of this page as further information on determinants.

3.2Optional: An Algebraic Definition of the Determinant¶

As mentioned above, we don’t really spend much time working with determinants in this course aside from for computing eigenvalues/vectors. However, for interested students, we will give an algebraic definition of the determinant as well as some methods of finding the determinant of a matrix. This definition is taken from these notes, which explain the connection between the geometric and algebraic interpretations of the determinant.

Definition 2 (The Determinant of a Matrix)

The determinant is the unique alternating, multilinear map $\det : \mathbb{R}^n \to\mathbb R$ defined on the columns of a matrix which is equal to 1 when given the standard basis vectors in order. The determinant of a matrix $A$ with columns $a_1, a_2, \dots, a_n$ is denoted as $|A| = \det A = \det(a_1, a_2, \dots, a_n)$ .

A multilinear function is a function which, when keeping all of the arguments except one constant, is linear in the last argument, i.e.,

\begin{align*} &\det(\vv a_1, \dots, \vv a_{i - 1}, \vv a_i + \vv b_i, \vv a_{i + 1}, \dots, \vv a_n) \\ &= \det(\vv a_1, \dots, \vv a_{i - 1}, \vv a_i, \vv a_{i + 1}, \dots, \vv a_n) + \det(\vv a_1, \dots, \vv a_{i - 1}, \vv b_i, \vv a_{i + 1}, \dots, \vv a_n) \end{align*}

(2)

(A familiar special case of multilinearity is bilinearity, which is satisfied by inner products.)

An alternating function is a function whose output is negated after swapping two of its arguments, i.e.,

\begin{align*} &\det(\vv a_1, \dots, \vv a_{i}, \dots, \vv a_{j}, \dots, \vv a_n) \\ &= -\det(\vv a_1, \dots, \vv a_{j}, \dots, \vv a_{i}, \dots, \vv a_n) \end{align*}

(3)

The last condition, that the determinant is equal to 1 when given the standard basis vectors in order, is equivalent to the statement

\begin{align*} \det I = 1 \end{align*}

(4)

where $I$ is the identity matrix.

Finally, these properties uniquely define the determinant; any function satisfying the above 3 properties must be the determinant function.

From this definition, we can compute the determinants of the elementary matrices!

To see why, note that the determinants of scaling and switching follow immediately from the multilinear and alternating properties of the determinant, respectively. To prove that the determinant of a row addition matrix is 1, we’ll show this is the case for a specific elementary matrix, and then you should convince yourself this is true for all row addition matrices:

\begin{align*} \det \bm 1&0&0\\2&1&0\\0&0&1\em &= \det \bm 1&0&0\\0&1&0\\0&0&1\em + \det \bm 0&0&0\\2&1&0\\0&0&1\em \quad\text{(multilinearity)}\\ &= 1 + \bm 0&0&0\\2&1&0\\0&0&1\em \quad\text{(determinant of identity is $1$)}\\ &= 1 + 2\bm 0&0&0\\1&1&0\\0&0&1\em \quad\text{(multilinearity)}\\ \end{align*}

(5)

Using the alternating property, you can show that $\det \bm 0&0&0\\1&1&0\\0&0&1\em = 0$ . Therefore, we have that $\det \bm 1&0&0\\2&1&0\\0&0&1\em = 1$ .

Equipped with these results, we can see how right multiplying by an elementary matrix changes the determinant. Recall that right multiplication by an elementary matrix defines a column operation; we’ll also extend these results to left multiplication by an elementary matrix (which defines a row operation).

Theorem 2 (Determinant after an elementary operation)

Let $E_1, E_2, E_3$ be elementary matrices corresponding to addition, swapping, and scaling, respectively. Then, for any square matrix $A$ :

Right multiplication by $E_1$ preserves the determinant: $\det AE_1 = \det A$ .
Right multiplication by $E_2$ negates the determinant: $\det AE_2 = -\det A$ .
Right multiplication by $E_3$ (where $E_3$ scales by a factor of $c$ ) scales the determinant: $\det AE_1 = c \det A$ .

In particular, we are beginning to work towards one of the most important properties of the determinant. For now, note that $\det AE = \det A \det E$ for any elementary matrix $E$ ! In fact, we can immediately use this result, and the commutativity of multiplication, to show that:

\begin{align*} \det AE = \det A \det E = \det E \det A = \det EA \end{align*}

(6)

In other words:

Left multiplication by $E_1$ preserves the determinant: $\det AE_1 = \det A$ .
Left multiplication by $E_2$ negates the determinant: $\det AE_2 = -\det A$ .
Left multiplication by $E_3$ (where $E_3$ scales by a factor of $c$ ) scales the determinant: $\det AE_1 = c \det A$ .

So we’ve characterized how elementary row and column operations affect the determinant!

The proof of these properties is not hard, and follows from a few applications of the defining properties of the determinant. Try to prove these yourself!

Now, we are ready to prove a lot of useful facts about determinants! We’ll state and prove them one by one.

To prove this theorem, start by proving it for just upper triangular matrices $U$ with all nonzero pivots. Try to come up with a series of row addition operations to reduce $U$ to diagonal form, and then apply multilinearity to easily find the determinant of a diagonal matrix!

The case where $U$ has a zero on its diagonal is trickier. One way is to show that you can come up with a series of row addition and column scaling operations to reduce $U$ to a form with two identical columns, then apply the alternating property of the determinant to prove that $U$ must have zero determinant!

Next, we’ll state and prove the key property of the determinant used for computing eigenvalues.

To prove this statement, we’ll use the row echelon form of a matrix, in combination with our result on triangular matrices (recall that any matrix can be written as a product of elementary matrices followed by a matrix in row echelon form):

If $A$ is singular, then its row echelon form will have a zero on its diagonal. By our result on triangular matices, this implies that $\det A = 0$ (since row echelon matrices are triangular).
If $A$ is nonsingular, then its row echelon will have $n$ nonzero pivots (which must be diagonal elements). By our result on triangular matrices, and the fact that the product of nonzero numbers is nonzero, this implies that $\det A \neq 0$ .

Next, we’ll prove another extremely important property of determinants!

First, we’ll prove that this holds for invertible matrices. To prove this, recall that any invertible square matrix can be factored as a product of elementary matrices:

\begin{align*} A &= E_1E_2 \dots E_m\\ B &= F_1F_2\dots F_n \end{align*}

(7)

Then, we can cleverly use our knowledge of how elementary operations change the determinant:

\begin{align*} \det AB &= \det (E_1E_2 \dots E_mF_1F_2\dots F_n) \\ &= \det E_1 \det E_2 \dots \det E_m \det F_1 \det F_2 \dots F_n\\ &= \det (E_1 E_2 \dots E_m) \det (F_1 F_2 \dots F_n)\\ &= \det A \det B \end{align*}

(8)

Next, we’ll consider the case where $A$ or $B$ , or both, is noninvertible. In this case, the result follows easily because a matrix product with a noninvertible factor is also noninvertible, and thus has zero determinant.

Try to prove this yourself! As a start, observe from the determinants of elementary matrices that transposing an elementary matrix does not change its determinant. Then, just like we did for matrix products, either write $A$ and $A^\top$ as products of elementary matrices or show that $A$ is noninvertible.

To prove this, start from the condition that $AA^{-1} = I$ , then apply this theorem!

Try to prove this yourself using the properties we have already proven!

3.3Optional: Methods of Computing the Determinant¶

In the section, we will review/introduce two way of computing the determinant: the Laplace expansion and the PLU-factorization.

Definition 3 (The Laplace Expansion)

The Laplace expansion is a recursive definition of the determinant of an $n\times n$ matrix in terms of the weighted sums of determinants of $(n - 1) \times (n - 1)$ matrices, and can be derived from our characterization of the determinant of an alternating multilinear map.

More specifically, to find the determinant of an $n\times n$ matrix $A$ , we choose any arbitrary row $i$ (or arbitrary column $j$ ) and write the Laplace expansion along row $i$ :

\begin{align*} \det A = \sum_{j = 1}^{n}{(-1)^{i + j}}a_{ij}m_{ij} \end{align*}

(9)

The base case of this recursive relationship is that the determinant of any $1\times 1$ matrix $\bm s \em$ is just $s$ .

Here, $a_{ij}$ is the element at row $i$ and column $j$ of $A$ ; $m_{ij}$ is the minor at row $i$ and column $j$ , and is equal to the determinant of the $(n-1)\times (n - 1)$ submatrix of $A$ obtained by deleting row $i$ and column $j$ .

This is quite an abstract definition, so let’s see it at work!

Example 1 (Finding the determinant of a

3\times 3

matrix)

Consider the $3\times 3$ matrix $A = \bm 1&2&3\\4&5&6\\7&8&9\em$ . Applying the laplace expansion along row 1, and then using the $2\times 2$ formula for determinants, we have:

\begin{align*} \left| \bm 1&2&3\\4&5&6\\7&8&9\em \right| &= (1) \left| \bm 5&6\\8&9\em \right| - (2) \left| \bm 4&6\\7&9\em \right| + (3)\left| \bm 4&5\\7&8\em \right|\\ &= (1) (45 - 48) - (2) (36 - 42) + (3)(32 - 35)\\ &= 0 \end{align*}

(10)

Note that in the Laplace expansion, the row or column chosen to compute the expansion is arbitrary! Thus, it makes sense to expand along rows and columns with lots of zeros; if the coefficient multiplying a submatrix determinant is zero, then we don’t have to actually compute that submatrix determinant!

For small matrices, the Laplace expansion works fine. However, for larger matrices (even with $n \geq 10$ ), this method of naively applying the Laplace will require a HUGE number of addition and multiplication operations (on the order of $n!$ , or $n$ factorial)!

However, by applying our results for triangular matrices, we can come up with a much more computationally efficient method for computing the determinant.

Python Break!¶

Below are 3 code snippets demonstrating a few ways to compute the determinant. First, we run an implementation of the Laplace expansion (taken from this article). Second, we implement a determinant function based on the PLU factorization. Finally, we show how to use the built in determinant function from the scipy.linalg library.

import numpy as np
from scipy import linalg
import time

np.random.seed(2030)

# This code is from https://en.wikipedia.org/wiki/Laplace_expansion#Computational_expense
def laplace_det(M):
    # Base case of recursive function: 1x1 matrix
    if M.shape[0] == 1: 
        return M[0, 0]

    total = 0
    for column, element in enumerate(M[0]):
        # Exclude first row and current column.
        K = np.stack([np.concatenate((x[:column], x[column + 1 :]), axis=0) for x in M[1:]], axis=1)
        s = 1 if column % 2 == 0 else -1 
        total += s * element * laplace_det(K)
    return total

# Generate a random matrix
A = np.random.rand(9, 9) 
B = np.random.rand(10, 10)

# Find the determinant of A and B using Laplace expansion; also time how long it takes
start_time_A = time.time()
det_A = laplace_det(A)
end_time_A = time.time()

start_time_B = time.time()
det_B = laplace_det(B)
end_time_B = time.time()

print(f"Determinant (for 9x9): {det_A}")
print(f"Elapsed time (for 9x9): {end_time_A - start_time_A} seconds")
print(f"Determinant (for 10x10): {det_B}")
print(f"Elapsed time (for 10x10): {end_time_B - start_time_B} seconds")

Determinant (for 9x9): -0.007502281817950991
Elapsed time (for 9x9): 4.375511169433594 seconds
Determinant (for 10x10): -0.0334246928386742
Elapsed time (for 10x10): 40.4918212890625 seconds

Above is a recursive implementation of the Laplace expansion. As you can see, this implementation isn’t very fast! On this specific machine, it took ~4s to find the determinant for a $9\times 9$ matrix; and ~40s to find the determinant for a $10\times 10$ matrix!

For anything longer, this implementation will take forever to finish. Luckily, using our linear algebra knowledge, we can give a much more efficient implementation of the determinant!

import numpy as np
from scipy import linalg
import time

np.random.seed(2030)

def sign(P):
    sign = 1
    visited = [0 for _ in range(len(P))]
    for i in range(len(P)):
        if visited[i] == 1:
            continue
        if P[i] == i:
            continue
        curr = P[i]
        visited[curr] = 1
        cycle_length = 1
        while curr != i:
            curr = P[curr]
            visited[curr] = 1
            cycle_length += 1
        if cycle_length % 2 == 0:
            sign = -sign
    return sign

def plu_det(M):
    P, L, U = linalg.lu(M, p_indices=True)
    return sign(P) * np.prod(np.diag(L)) * np.prod(np.diag(U))

# Generate a random matrix
A = np.random.rand(9, 9) 
B = np.random.rand(10, 10)

# Find the determinant of A and B using Laplace expansion; also time how long it takes
start_time_A = time.time()
det_A = plu_det(A)
end_time_A = time.time()

start_time_B = time.time()
det_B = plu_det(B)
end_time_B = time.time()

print(f"Determinant (for 9x9): {det_A}")
print(f"Elapsed time (for 9x9): {end_time_A - start_time_A} seconds")
print(f"Determinant (for 10x10): {det_B}")
print(f"Elapsed time (for 10x10): {end_time_B - start_time_B} seconds")

Determinant (for 9x9): -0.007502281817951028
Elapsed time (for 9x9): 0.0 seconds
Determinant (for 10x10): -0.033424692838674074
Elapsed time (for 10x10): 0.0 seconds

As you can see, with the PLU method, this method is much quicker; as you can see, for smaller matrices it was near instantaneous. A few notes; to find the PLU decomposition of $A$ , we used the scipy.linalg.lu function, which returns the $L$ and $U$ matrices, as well as either the $P$ matrix or its representation in one-line notation (this is because permutation matrices are mostly zeros, and can be encoded as just a list of numbers). Also, note the sign function we defined; the details aren’t important, but this function is essentially a fast way to compute the determinant of a permutation matrix given in one-line notation.

Finally, let’s see how to use the built in functions from scipy.linalg (or numpy.linalg) to find determinants!

import numpy as np
from scipy import linalg
import time

np.random.seed(2030)

# Generate a random matrix
A = np.random.rand(9, 9) 
B = np.random.rand(10, 10)

# Find the determinant of A and B using Laplace expansion; also time how long it takes
start_time_A = time.time()
det_A = linalg.det(A)
end_time_A = time.time()

start_time_B = time.time()
det_B = linalg.det(B)
end_time_B = time.time()

print(f"Determinant (for 9x9): {det_A}")
print(f"Elapsed time (for 9x9): {end_time_A - start_time_A} seconds")
print(f"Determinant (for 10x10): {det_B}")
print(f"Elapsed time (for 10x10): {end_time_B - start_time_B} seconds")

Determinant (for 9x9): -0.007502281817951028
Elapsed time (for 9x9): 0.0 seconds
Determinant (for 10x10): -0.033424692838674094
Elapsed time (for 10x10): 0.0 seconds

As you can see, it’s really easy, just a single call to the scipy.linalg.det function!