We saw that a 2-by-2 matrix $\left(\begin{array}{cc}\hfill a\hfill & \hfill b\hfill \\ \hfill c\hfill & \hfill d\hfill \end{array}\right)$
has an inverse if and only if $ad-bc\ne 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)\ne 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 $\pm ad\pm bc$
).

Before we explain the signs, let's see how many choices there would be if $n=3$
, so $$M=\left(\begin{array}{ccc}\hfill {M}_{11}\hfill & \hfill {M}_{12}\hfill & \hfill {M}_{13}\hfill \\ \hfill {M}_{21}\hfill & \hfill {M}_{22}\hfill & \hfill {M}_{23}\hfill \\ \hfill {M}_{31}\hfill & \hfill {M}_{32}\hfill & \hfill {M}_{33}\hfill \end{array}\right).$$
If you pick ${M}_{11}$
from the top row, you can't pick anything in the first column for your other choices, so the only possibilities are ${M}_{22},{M}_{33}$
or ${M}_{23},{M}_{32}$
from the second and third rows. In this way, the possible choices give: $${M}_{11}{M}_{22}{M}_{33},{M}_{11}{M}_{23}{M}_{32},{M}_{12}{M}_{21}{M}_{33},{M}_{12}{M}_{23}{M}_{31},{M}_{13}{M}_{21}{M}_{32},{M}_{13}{M}_{22}{M}_{31},$$
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:

${M}_{11}{M}_{22}{M}_{33}$
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$
;

${M}_{11}{M}_{23}{M}_{32}$
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,\mathrm{\dots},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,\mathrm{\dots},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 ${M}_{11}{M}_{22}{M}_{33}$
, 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 ${M}_{11}{M}_{22}{M}_{33}$
contributes with a plus sign to the determinant.

Suppose you picked ${M}_{11}{M}_{23}{M}_{32}$
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 ${M}_{11}{M}_{23}{M}_{32}$
contributes with a minus sign.

Here are the permutations and signs for the other choices when $n=3$
:

Product

Permutation

Sign

${M}_{11}{M}_{22}{M}_{33}$

$123$

$+$

${M}_{11}{M}_{23}{M}_{32}$

$132$

$-$

${M}_{12}{M}_{21}{M}_{33}$

$213$

$-$

${M}_{12}{M}_{23}{M}_{31}$

$231$

$+$

${M}_{13}{M}_{21}{M}_{32}$

$312$

$+$

${M}_{13}{M}_{22}{M}_{31}$

$321$

$-$

so $$det(M)={M}_{11}{M}_{22}{M}_{33}-{M}_{11}{M}_{23}{M}_{32}-{M}_{12}{M}_{21}{M}_{33}+{M}_{12}{M}_{23}{M}_{31}+{M}_{13}{M}_{21}{M}_{32}-{M}_{13}{M}_{22}{M}_{31}.$$

If $M=\left(\begin{array}{cc}\hfill a\hfill & \hfill b\hfill \\ \hfill c\hfill & \hfill d\hfill \end{array}\right)$
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)=\sum _{\sigma \in {S}_{n}}\mathrm{sgn}(\sigma ){M}_{1\sigma (1)}{M}_{2\sigma (2)}\mathrm{\cdots}{M}_{n\sigma (n)}.$$
Here:

the sum is over all permutations $\sigma $
of $1,2,\mathrm{\dots},n$

$\mathrm{sgn}(\sigma )$
means the sign ($+1$
if $\sigma $
is even, $-1$
if $\sigma $
is odd).

to understand the product, note that ${M}_{1\sigma (1)}$
is the choice from the first row (which is why the first index is 1) and it lives in column $\sigma (1)$
(remember $\sigma $
is the permutation which tells us which column our choices live in). Similarly, ${M}_{2\sigma (2)}$
is the choice from the second row, etc.

Examples

Let $M=\left(\begin{array}{ccc}\hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 1\hfill & \hfill 0\hfill & \hfill 0\hfill \end{array}\right)$
. There's only one valid choice which doesn't involve any zeros, namely ${M}_{31}{M}_{22}{M}_{13}=1\times 1\times 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=\left(\begin{array}{ccc}\hfill 5\hfill & \hfill 0\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 0\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 3\hfill \end{array}\right)$
. 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\times 1\times 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=\left(\begin{array}{ccc}\hfill 1\hfill & \hfill 2\hfill & \hfill 3\hfill \\ \hfill 0\hfill & \hfill 1\hfill & \hfill 2\hfill \\ \hfill 0\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right).$$
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 ${E}_{ij}(\lambda )=\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill \mathrm{\cdots}\hfill & \hfill \hfill & \hfill \hfill \\ \hfill 0\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \hfill & \hfill \lambda \hfill & \hfill \hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \hfill & \hfill 1\hfill & \hfill \hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \mathrm{\ddots}\hfill & \hfill 0\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \mathrm{\cdots}\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$
is upper triangular (if $$
, or lower triangular if $i>j$
), and has all its diagonal entries equal to $1$
, we see that $det({E}_{ij}(\lambda ))=1$
.

Since the elementary matrix ${E}_{i}(\lambda )=\left(\begin{array}{ccccc}\hfill 1\hfill & \hfill 0\hfill & \hfill \mathrm{\cdots}\hfill & \hfill \hfill & \hfill \hfill \\ \hfill 0\hfill & \hfill \mathrm{\ddots}\hfill & \hfill \hfill & \hfill \hfill & \hfill \hfill \\ \hfill \mathrm{\vdots}\hfill & \hfill \hfill & \hfill \lambda \hfill & \hfill \hfill & \hfill \mathrm{\vdots}\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \hfill & \hfill \mathrm{\ddots}\hfill & \hfill 0\hfill \\ \hfill \hfill & \hfill \hfill & \hfill \mathrm{\cdots}\hfill & \hfill 0\hfill & \hfill 1\hfill \end{array}\right)$
is a diagonal matrix with all diagonal entries $1$
except one which is $\lambda $
, we get $det({E}_{i}(\lambda ))=\lambda $
.