We saw that a 2-by-2 matrix a, b; c, d has an inverse if and only if a d minus b c is nonzero. 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 is nonzero.
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 a d or b c).
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 plus or minus a d plus or minus b c).
Before we explain the signs, let's see how many choices there would be if n = 3, so M is a 3-by-3 matrix with entries M_{i j} If you pick M_{1 1} from the top row, you can't pick anything in the first column for your other choices, so the only possibilities are M_{2 2}, M_{3 3} or M_{2 3}, M_{3 2} from the second and third rows. In this way, the possible choices give: M_{1 1} M_{2 2} M_{3 3}, M_{1 1} M_{2 3} M_{3 2}, M_{1 2} M_{2 1} M_{3 3}, M_{1 2} M_{2 3} M_{3 1}, M_{1 3} M_{2 1} M_{3 2}, M_{1 3} M_{2 2} M_{3 1} 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_{1 1} M_{2 2} M_{3 3} corresponds to choosing entry 1 from row 1, entry 2 from row 2 and entry 3 from row 3, so you'd write down 1 2 3;
M_{1 1} M_{2 3} M_{3 2} corresponds to choosing entry 1 from row 1, entry 3 from row 2 and entry 2 from row 3, so you'd write down 1 3 2.
This gives a permutation of 1 up to 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 factorial.
Signs
Having made a choice as above and written down the corresponding permutation of 1 up to n, the sign you assign to this choice is:
plus 1 if your permutation is even (i.e. can be written as an even number of transpositions);
minus 1 if your permutation is odd (i.e. can be written as an odd number of transpositions).
Suppose you picked M_{1 1} M_{2 2} M_{3 3}, corresponding to the permutation 1 2 3. To get from 1 2 3 back to 1 2 3, 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_{1 1} M_{2 2} M_{3 3} contributes with a plus sign to the determinant.
Suppose you picked M_{1 1} M_{2 3} M_{3 2} corresponding to the permutation 1 3 2. To get from 1 3 2 back to 1 2 3 you need to transpose 2 and 3, so that's one transposition, and the permutation is odd. Therefore M_{1 1} M_{2 3} M_{3 2} contributes with a minus sign.
Here are the permutations and signs for the other choices when n = 3:
Product
Permutation
Sign
M_{1 1} M_{2 2} M_{3 3}
1 2 3
plus
M_{1 1} M_{2 3} M_{3 2}
1 3 2
minus
M_{1 2} M_{2 1} M_{3 3}
2 1 3
minus
M_{1 2} M_{2 3} M_{3 1}
2 3 1
plus
M_{1 3} M_{2 1} M_{3 2}
3 1 2
plus
M_{1 3} M_{2 2} M_{3 1}
3 2 1
minus
so det M = M_{1 1} M_{2 2} M_{3 3} minus M_{1 1} M_{2 3} M_{3 2} minus M_{1 2} M_{2 1} M_{3 3} + M_{1 2} M_{2 3} M_{3 1} + M_{1 3} M_{2 1} M_{3 2} minus M_{1 3} M_{2 2} M_{3 1}.
If M is the 2-by-2 matrix a, b; c, d then our two choices are a d (permutation 1 2, even so plus sign) and b c (permutation 2 1, odd so minus sign), giving det M = a d minus b c.
Index notation
We have a nice formula in index notation: det M equals the sum over permutations sigma of 1 up to n of the sign of sigma times the product M_{1 sigma(1)} times M_{2 sigma(2)} times dot dot dot times M_{n sigma(n)} Here:
the sum is over all permutations sigma of 1 up to n
sign sigma means the sign (plus 1 if sigma is even, minus 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 be the 3-by-3 matrix 0, 0, 1; 0, 1, 0; 1, 0, 0. There's only one valid choice which doesn't involve any zeros, namely M_{3 1} M_{2 2} M_{1 3} = 1 times 1 times 1. This corresponds to the permutation 3 2 1. To get back to 1 2 3 we'd have to transpose 1 and 3, which is an odd number of transpositions, so it has a minus sign. Therefore det M equals minus 1.
Remark:
To get back from 3 2 1 to 1 2 3, we could also have flipped 2 and 3 (getting to 2 3 1) then 1 and 3 (getting to 2 1 3) then 1 and 2 (getting to 1 2 3). 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 be the 3-by-3 matrix 5, 0, 0; 0, 1, 0; 0, 0, 3. Again, there's only one valid choice which has no zeros, and this choice corresponds to the permutation 1 2 3, so the only contribution to the determinant is plus 5 times 1 times 3, which equals 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 = 1, 2, 3; 0, 1, 2; 0, 0, 1 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_{i j}(lambda) is upper triangular (if i is less than j, or lower triangular if i is greater than j), and has all its diagonal entries equal to 1, we see that det E_{i j}(lambda) = 1.
Since the elementary matrix E_i(lambda) is a diagonal matrix with all diagonal entries 1 except one which is lambda, we get det of E_i(lambda) = lambda.