24. Determinants

24. Determinants

Definition

We saw that a 2-by-2 matrix (abcd) has an inverse if and only if ad-bc0 . 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 :

ProductPermutationSign
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(λ)=(100λ1001) 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(λ)=(100λ001) is a diagonal matrix with all diagonal entries 1 except one which is λ , we get det(Ei(λ))=λ .