We saw that a 2-by-2 matrix (abcd)
has an inverse if and only if ad-bc≠0
. This condition generalises to bigger matrices as follows. To each n
-by-n
matrix M
, we will define a number det(M)
(the determinant of M
) such that M
has an inverse if and only if det(M)≠0
.
Definition:
Let M
be an n
-by-n
matrix. The number det(M)
is defined as follows.
Pick an entry from each row in such a way that no two of your choices are in the same column. (If M
were 2-by-2 then you could either pick a
and d
or b
and c
).
Multiply your chosen entries together (if M
were 2-by-2 this would give us ad
or bc
).
Do the same for every other choice you could have made, and add up the results with signs (I'll explain the signs later). (If M
were 2-by-2, we would get ±ad±bc
).
Before we explain the signs, let's see how many choices there would be if n=3
, so M=(M11M12M13M21M22M23M31M32M33).
If you pick M11
from the top row, you can't pick anything in the first column for your other choices, so the only possibilities are M22,M33
or M23,M32
from the second and third rows. In this way, the possible choices give: M11M22M33,M11M23M32,M12M21M33,M12M23M31,M13M21M32,M13M22M31,
so there are six possibilities.
More generally:
Lemma:
Let M
be an n
-by-n
matrix. The number of ways of choosing something from each row so that no two are in the same column is n!
.
For each choice, write down the column numbers in the order you chose them. For example:
M11M22M33
corresponds to choosing entry 1 from row 1, entry 2 from row 2 and entry 3 from row 3, so you'd write down 123
;
M11M23M32
corresponds to choosing entry 1 from row 1, entry 3 from row 2 and entry 2 from row 3, so you'd write down 132
.
This gives a permutation of 1,2,…,n
. Every permutation arises and a choice is determined by the permutation you wrote down, so the number of choices is the same as the number of permutations, which is n!
.
Signs
Having made a choice as above and written down the corresponding permutation of 1,2,…,n
, the sign you assign to this choice is:
+1
if your permutation is even (i.e. can be written as an even number of transpositions);
-1
if your permutation is odd (i.e. can be written as an odd number of transpositions).
Suppose you picked M11M22M33
, corresponding to the permutation 123
. To get from 123
back to 123
, I don't have to do anything (i.e. 0 transpositions) and 0 is an even number so this is an even permutation, and M11M22M33
contributes with a plus sign to the determinant.
Suppose you picked M11M23M32
corresponding to the permutation 132
. To get from 132
back to 123
you need to transpose 2
and 3
, so that's one transposition, and the permutation is odd. Therefore M11M23M32
contributes with a minus sign.
Here are the permutations and signs for the other choices when n=3
:
Product
Permutation
Sign
M11M22M33
123
+
M11M23M32
132
-
M12M21M33
213
-
M12M23M31
231
+
M13M21M32
312
+
M13M22M31
321
-
so det(M)=M11M22M33-M11M23M32-M12M21M33+M12M23M31+M13M21M32-M13M22M31.
If M=(abcd)
then our two choices are ad
(permutation 12
, even so plus sign) and bc
(permutation 21
, odd so minus sign), giving det(M)=ad-bc.
Index notation
We have a nice formula in index notation: det(M)=∑σ∈Snsgn(σ)M1σ(1)M2σ(2)⋯Mnσ(n).
Here:
the sum is over all permutations σ
of 1,2,…,n
sgn(σ)
means the sign (+1
if σ
is even, -1
if σ
is odd).
to understand the product, note that M1σ(1)
is the choice from the first row (which is why the first index is 1) and it lives in column σ(1)
(remember σ
is the permutation which tells us which column our choices live in). Similarly, M2σ(2)
is the choice from the second row, etc.
Examples
Let M=(001010100)
. There's only one valid choice which doesn't involve any zeros, namely M31M22M13=1×1×1
. This corresponds to the permutation 321
. To get back to 123
we'd have to transpose 1
and 3
, which is an odd number of transpositions, so it has a minus sign. Therefore det(M)=-1
.
Remark:
To get back from 321
to 123
, we could also have flipped 2
and 3
(getting to 231
) then 1
and 3
(getting to 213
) then 1
and 2
(getting to 123
). This would have been three transpositions, which is still an odd number. The reason the definition of odd vs even permutations makes sense is that any permutation can be written as either an odd number of transpositions or an even number, but never as both. We won't prove that here.
Let B=(500010003)
. Again, there's only one valid choice which has no zeros, and this choice corresponds to the permutation 123
, so the only contribution to the determinant is +5×1×3=15
. Therefore det(B)=15
.
This applies to any diagonal matrix, i.e. a matrix whose off-diagonal entries are all zero: the determinant is the product of diagonal entries (with no extra signs).
Consider an upper triangular matrix (where all entries strictly below the diagonal are zero) like C=(123012001).
From the last row you have to pick the last entry. Therefore from the penultimate row you have to pick the penultimate entry, and so on, and you end up being forced to pick only the diagonal entries. So you get the product of diagonal entries with no extra sign (in this example, det(C)=1
).
Since the elementary matrix Eij(λ)=(10⋯0⋱λ⋮1⋮⋱0⋯01)
is upper triangular (if i<j
, or lower triangular if i>j
), and has all its diagonal entries equal to 1
, we see that det(Eij(λ))=1
.
Since the elementary matrix Ei(λ)=(10⋯0⋱⋮λ⋮⋱0⋯01)
is a diagonal matrix with all diagonal entries 1
except one which is λ
, we get det(Ei(λ))=λ
.