Permutations and Inversions
Before we look at the combinatorial definition of a determinant, we will first need to understand some rather simple basic definitions in combinatorics:
| Definition: A Permutation of a set $S$ is an ordered arrangement of the elements in this set without omissions or repetitions of elements. |
For example, consider the following set of numbers $S = \{ 3, 4, 0 \}$. One such permutation of this set is $(4, 0, 3)$. There are a few other permutations of this set though, in fact, there are precisely 6 permutations of these three numbers:
| Permutation Count | Permutation of $S$ |
|---|---|
| 1 | $(4, 0, 3)$ |
| 2 | $(4, 3, 0)$ |
| 3 | $(3, 0, 4)$ |
| 4 | $(3, 4, 0)$ |
| 5 | $(0, 3, 4)$ |
| 6 | $(0, 4, 3)$ |
It is rather easy to see that there are no other permutations of $S$ that aren't already listed. However, if we had $n$ many elements in the set, then how many permutations of $S$ would we have?
First consider that we will need to arrange all $n$ elements into $n$ spots. The first element could be any of the $n$ numbers, the second element could be one of the other $n - 1$ numbers (excluding the number placed in the first spot since we can't have repetition), and so forth. Eventually we will get to our last element and have only $1$ number to choose for it's location. Thus there are $n(n-1)(n-2)...2\cdot1$ permutations of an $n$ element set $S$. This product is often abbreviated as $n! = n(n-1)(n-2)...2\cdot1$ and pronounced "n factorial", that is the product of integers from $1$ to $n$.
Now let's define what an inversion in a permutation is.
| Definition: Denote a general permutation by $(j_1, j_2, ..., j_n)$. An Inversion occurs in a permutation whenever a larger number precedes a smaller number. That is if $i < k$ and $j_i > j_k$, then an inversion has occurred. If there is an even number of inversions in the permutation then we classify the permutation as Even, and if there is an odd number of inversions in the permutation then we can classify the permutation as Odd. |
To calculate the number of inversions in a permutation:
- 1. Look at the first element in the permutation, $j_1$, and count to see how many elements to the right of it are smaller.
- 2. Look at the second element in the permutation, $j_2$ and count to see how many elements to the right of it are smaller.
- 3. Repeat this process for all elements in the permutation and then sum the results to get the number of inversions in the permutation.
For example, consider the permutation $(4, 5, 1, 3, 7)$. The first element is $4$, and there are $2$ numbers smaller than it ($1$ and $3$). Now look at the second number and count the number of elements smaller than it. Once again, there are two numbers smaller than it ($1$ and $3$ again). We continue to proceed and we sum up all of our results $2 + 2 + 0 + 0 + 0 = 4$ to get that there are $4$ inversions in this permutation.
We are now ready to begin to look at the combinatorial definition of a determinant.
Elementary Products
| Definition: Given an $n \times n$ square matrix $A$, define an Elementary Product of $A$ to be any product of entries from $A$ from which no two entries come from the same row or column. Define the Associated Permutation of an Elementary Product to be the permutation of the columns of the entries in the product. Define a Signed Elementary Product to be an elementary product multiplied by either $1$ (if the associated permutation is even) or -1 (if the associated permutation is odd). |
Let's first look at some elementary products of the following $2 \times 2$ matrix $A = \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix}$
There are precisely two elementary matrices in this matrix, that is the products $a_{11}a_{22}$ and $a_{12}a_{21}$. There are no other combinations of entries that satisfy our conditions to be an elementary product of $A$.
| Elementary Product | Associated Permutation | Number of Inversions | Even / Odd | Signed Elementary Product |
|---|---|---|---|---|
| $a_{11}a_{22}$ | $(1, 2)$ | 0 | Even | $a_{11}a_{22}$ |
| $a_{12}a_{21}$ | $(2, 1)$ | 1 | Odd | $-a_{12}a_{21}$ |
We will note that for any $n \times n$ matrix, there will be exactly $n!$ many elementary products.
Consider the general $3 \times 3$ matrix $A = \begin{bmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{bmatrix}$. We know that there will be precisely $n! = 3! = 6$ elementary products for this matrix:
| Elementary Product | Associated Permutation | Number of Inversions | Even / Odd | Signed Elementary Product |
|---|---|---|---|---|
| $a_{11}a_{22}a_{33}$ | $(1, 2, 3 )$ | 0 | Even | $a_{11}a_{22}a_{33}$ |
| $a_{11}a_{23}a_{32}$ | $(1, 3, 2 )$ | 1 | Odd | $-a_{11}a_{23}a_{32}$ |
| $a_{12}a_{21}a_{33}$ | $(2, 1, 3 )$ | 1 | Odd | $-a_{12}a_{21}a_{33}$ |
| $a_{12}a_{23}a_{31}$ | $(2, 3, 1 )$ | 2 | Even | $a_{12}a_{23}a_{31}$ |
| $a_{13}a_{21}a_{32}$ | $(3, 1, 2 )$ | 2 | Even | $a_{13}a_{21}a_{32}$ |
| $a_{13}a_{22}a_{31}$ | $(3, 2, 1 )$ | 3 | Odd | $-a_{13}a_{22}a_{31}$ |
We will finally construct a formal definition of a determinant using these signed elementary products.
Combinatorial Definition of a Determinant
| Definition: If $A$ is an $n \times n$ square matrices, then $\det (A)$ is the sum of all $n!$ signed elementary products derived from $A$. |
From the example of a $2 \times 2$ elementary matrix, we get:
(1)Of course, this formula is identical to the one we learned earlier, that is $\det(A) = ad - bc$.
However, now we can derive a general formula for any $3 \times 3$ determinant $A = \begin{bmatrix} a_{11} & a_{12} & a_{13}\\ a_{21} & a_{22} & a_{23}\\ a_{31} & a_{32} & a_{33} \end{bmatrix}$, that is:
(2)While this method for evaluating determinants can be useful sometimes, there are definitely better methods for larger matrices. We note that we will need to calculate $n!$ elementary products to evaluate the determinant of an $n \times n$ matrix, however, as $n$ gets larger, $n!$ grows extremely fast. This sort of growth is known as the combinatorial explosion. For example, calculating a $10 \times 10$ matrix using elementary products would require the computation of $10! = 3628800$ elementary products - something that is definitely not practical.