Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

MATH 4A - Linear Algebra with Applications

Lecture 11: A better approach to computing determinants

24 April 2019

Reading: §3.1-3.3 from Lay, 5th ed.

Recommended problems from §3.2: 1, 3, 5, 7, 11, 15, 17, 19, 21,
25, 27, 28, 31-36
Announcement: I’ve updated the slides from Lecture 10 to better
reflect what we did on Monday.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Lecture plan

1 Review of cofactor expansion

2 3 × 3 mnemonic

3 Multiplicative property

4 A better way to compute determinants

5 Invertibility and determinants

Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Cofactor expansion formulae

Recall that if A is a matrix, the (i, j)-cofactor of A is the number

Cij = (−1)i+j det Aij

where Aij is the matrix we get by deleting the i th row and j th

column from A.
Theorem
The determinant of a n × n matrix A can be computed by a
cofactor expansion across any row or down any column. The
expansion across the i th row is

det A = ai1 Ci1 + ai2 Ci2 + · · · + ain Cin

and the cofactor expansion down the j th column is

det A = a1j C1j + a2j C2j + · · · + anj Cnj .

Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Why is this theorem helpful?

Recall that we defined the determinant to be the cofactor

expansion along the first row.

The theorem says we can compute this quantity in different ways,

which allows for some tricks to speed up calculations of
determinants, e.g. if
 
4 2 0 1
3 1 0 3
B= 9 1 −1 3 


2 −5 0 −1

we “should” do cofactor expansion down the third column, because

it has lots of zeros.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Another application of cofactor expansion tricks

An upper triangular matrix is any square matrix that has only 0’s
below its diagonal, for example
   
  1 1 1 321 4231 −54
2 3 0 1 0   0 1 2 
0 4
0 0 32 0 0 0

Using the cofactor expansion formulae and being clever about

which columns or rows we expand down recursively, we can show
Theorem
If A is a triangular matrix, then det A is the product of the entries
on the main diagonal of A. That is,

det A = a11 a22 · · · ann .

Thus, in the examples above, the matrices have determinants
8, 32, and 0, respectively. There is a similar theorem for lower
triangular matrices.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

iClicker 1

What’s the determinant of

 
0 0 0 0 1
0 0 0 2 234 
 
B= 0 0 3 624 98 
?
0 4 5428 −234 −952
5 −24 57 −1 0

(a) 0
(b) -120
(c) 702
(d) something else
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Note: computing determinants from cofactors is not easy!

Despite the tricks we just discussed above, they only apply to very
special matrices (basically, they need lots of zeros).

In general, cofactor expansion can always be done, but it’s

exhausting. More precisely, the algorithm that computes det A for
any square matrix A using cofactor expansion is extremely slow:
using cofactor expansion on a 25 × 25 could require up to 1025
multiplications. This would require 500,000 years to compute, even
on a machine that could perform one trillion multiplications per
second.

Fortunately, we’ll find better ways to compute determinants shortly.

Before that, I want to give you a visual mnemonic for the formula
for the determinant of a 3 × 3 matrix.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Mnemonic

− − −

a11 a12 a13 a11 a12

a21 a22 a23 a21 a22

a31 a32 a33 a31 a32

+ + +

det A = a11 a22 a33 +a12 a23 a31 +a13 a21 a32 −a31 a22 a13 −a32 a23 a11 −a33 a21 a12
WARNING: there is no similar formula for n × n matrices with
n > 3!
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Multiplicative property of determinants

Here’s a useful algebraic property of determinants:

Theorem
If A and B are n × n matrices, then det(AB) = (det A)(det B).

We will use this property to devise a better algorithm for

determinants using row operations.

WARNING: there is no additive version of this: for most matrices

A and B, det(A + B) does not equal det A + det B.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

iClicker 2

Let    
1 1 0 0
A= B= .
0 1 1 0
What is det AB?
(a) 1
(b) 0
(c) -1
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

iClicker 3

Let    
1 1 0 0
A= B= .
0 1 1 0
What is det(A + B)? Does this equal det A + det B?
(a) 1, yes
(b) 0, yes
(c) -1, no
(d) 1, no
(e) 0, no
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Determinants and row operations

To recap, we defined the determinant of a matrix using the
recursive cofactor expansion formula along the first row, but the
calculations are a little tedious. A better way to understand and
compute determinants is to consider how they behave with respect
to row operations:
Theorem
Let A be a square matrix.
(a) Row replacement of A keeps the determinant constant. More
precisely, if a multiple of one row of A is added to another row
of A to produce the matrix B, then det B = det A.
(b) Swapping two rows introduces a negative. More precisely, if
two rows of A are interchanged to produce B, then
det B = − det A.
(c) Scaling a row scales the determinant. More precisely, if one
row of A is multiplied by r to produce B, then det B = r det A.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Proof of (a)
Recall that each row operation can be understood as multiplying A
on the left by an elementary matrix E . We shall prove each of the
three cases separately using the multiplicative property of
determinants.

When we row replace A (that is, add a multiple of one row to

another row) the matrix E is either upper triangular or lower
triangular with 1’s on the diagonal, e.g. if A is 4 × 4, adding 4R4
to R2 is the same as taking the matrix product EA where
 
1 0 0 0
0 1 0 4
E =0 0 1 0 .


0 0 0 1

In particular, note det E = 1, so by the multiplicative property of

determinants det EA = (det E )(det A) = det A.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Proof of (b)

When we swap two rows, the elementary matrix E has precisely

one 1 in every column and every row, and 0 everywhere else, e.g. if
A is 4 × 4, swapping R1 and R3 is the same as taking the matrix
product EA where
 
0 0 1 0
0 1 0 0
E = 1 0 0 0 .


0 0 0 1

It’s not hard to check using cofactor expansion tricks that

det E = −1, hence

det EA = (det E )(det A) = − det A.

Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Proof of (c)

Scaling row i of A by the scalar r in R is the same as taking the

matrix product EA where E is a diagonal matrix with 1s on the
diagonal except in the i th spot, where instead there is an r , e.g. if
A is 4 × 4, scaling R3 by a factor of 2.5 is the same as taking the
matrix product EA where
 
1 0 0 0
0 1 0 0
E = 0 0 2.5 0 .


0 0 0 1

In particular, note det E = r ., so by the multiplicative property of

determinants

det EA = (det E )(det A) = r (det A).

Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Most important slide of the day: a better algorithm for

computing det A
We can use the previous theorem to design an algorithm to
compute det A:
1 Apply the usual row reduction procedure to put A in any

echelon form E . Let N be the number of times you swapped

two rows, and let k1 , . . . , ks be the nonzero scalars you scaled
rows by (so s is the number of times you scaled a row).
2 The echelon form E = (e ) is upper triangular, so, by a
ij
theorem from earlier today, det E = e11 e22 · · · enn .
3 By the previous theorem,

det E e11 e22 · · · enn

det(A) = (−1)N = (−1)N .
k1 k2 · · · ks k1 k2 · · · ks
Putting matrices in echelon form is much, much, much easier than
cofactor expansions (especially for large matrices, say 100 × 100).
So this algorithm is a much more efficient way to compute det A
than the cofactor expansion.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

iClicker 4
Let A be some 4 × 4 matrix that can be put in the echelon form
 
1 −4 2 42
0 3 2 8 
E =0 0 −5

432
0 0 0 2

with the following sequence of row operations: swap R1 and R4 ,

add 3R2 to R4 , swap R3 and R4 , scale R4 by 2, scale R3 by 7.
What is det A? (Fun observation: for this calculation, the order of
the row operations doesn’t matter.)
(a) −30 · 14
30
(b) 14
(c) − 3014
(d) 30 · 14
(e) − 1014
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Can we understand invertibility in terms of determinants?

Recall that a n × n square matrix A is invertible if and only if it is

row equivalent to the identity matrix In . Of course, In is invertible
because
In In = In
implies (In )−1 = In . And because In is upper triangular, we can
compute that
det In = 1 · 1 · · · 1 = 1n = 1.
If A is invertible, when we row reduce A to In , we can replace rows,
scale rows by nonzero scalars k1 , . . . , ks , and swap rows N times.
Thus, by the formula from two slides ago,
det In 1
det A = (−1)N = (−1)N
k1 k2 · · · ks k1 k2 · · · ks
is not zero! In other words, if A is invertible, then det A 6= 0.
Review of cofactor expansion 3 × 3 mnemonic Multiplicative property A better way to compute determinants Invertibility and det

Invertible is equivalent to det 6= 0

In fact, we could easily argue the converse is true as well: if

det A 6= 0, then A is invertible (basically, if det a 6= 0, then the
reduced echelon form of A must be In ). Thus, we arrive at our
promised generalization of what we already knew about 2 × 2
matrices:
Theorem
A square matrix A is invertible if and only if det A 6= 0.