Evaluating Determinants with Inversions of Permutations

Evaluating Determinants with Inversions of Permutations

Recall from the Inversions of Permutations page that if $A = \{1, 2, ..., n \}$ is a finite $n$-element set of positive integers then an inversion of the $n$-permutation $(x_1, x_2, ..., x_n)$ occurs when $j < k$ and $x_j > x_k$. On the Even and Odd Permutations page, we noted that a permutation $(x_1, x_2, ..., x_n)$ is even if the number of inversions of that permutation is even and the permutation is odd if the number of inversions of that permutation is odd.

We will now look at an application of inversions of permutations with respect to matrix determinants. We first define an Elementary Product of a matrix.

Definition: If $A$ is a square $n \times n$ matrix then an Elementary Product of $A$ is the product of $n$ entries from $A$ that are in different rows and columns of $A$.

For example, consider the following $2 \times 2$ matrix:

(1)
\begin{align} \quad A = \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix} \end{align}

There are two elementary products that can be formed with the matrix above, namely $a_{11} \cdot a_{22}$ and $a_{12} \cdot a_{22}$.

Theorem 1: If any $n \times n$ matrix $A$ there is exactly $n!$ elementary products.
  • Proof: Consider a generic $n \times n$ matrix $A$. For $p_1, p_2, ..., p_n, q_1, q_2, ..., q_n \in \{ 1, 2, ..., n \}$ we have all elementary products of $A$ will be of the form:
(2)
\begin{align} \quad \prod_{i=1}^n a_{p_iq_i} = a_{p_1q_1} \cdot a_{p_2q_2} \cdot ... \cdot a_{p_nq_n} \end{align}
  • We must have that $p_j \neq p_k$ for all $j, k \in \{ 1, 2, ..., n \}$ otherwise the entries $a_{p_jq_j}$ and $a_{p_kq_k}$ are on the same row and hence the form above is not an elementary product. Similarly, we must have that $q_k \neq q_j$ otherwise the entries $a_{p_jq_j}$ and $a_{p_kq_k}$ are on the same column and once again the form above is not an elementary product.
  • Set $p_1$ to be equal to any number in $\{1, 2, ..., n \}$ to which there are $n$ choices. Now choose $p_2$ to equal to any number in $\{1, 2, ..., n \} \setminus \{ p_1 \}$ to which there are $n - 1$ choices. Continue on in this manner. Choose $p_n$ to be equal to the remaining number in $\{1, 2, ..., n \} \setminus \{ p_1, p_2, ..., p_{n-1} \}$ to whih there is $1$ choice. Hence there are $n!$ ways to accomplish this.
  • Note that for each elementary product above we have satisfied the requirements for the form above to be an elementary product provided that we choose any arbitrary combination of $q_1, q_2, ..., q_n$ to fill the form in below, that is, for $q_1, q_2, ..., q_n$ as distinct numbers from $\{1, 2, ..., n \}$ we have (from the assignment of the values of $p$ above) that $a_{p_1q_1} \cdot a_{p_2q_2} \cdot ... \cdot a_{p_nq_n}$ will always be an elementary product. Thus there are $n!$ elementary products for the $n \times n$ matrix $A$. $\blacksquare$
Definition: If $A$ is a square $n \times n$ matrix and $\prod_{i=1}^{n} a_{p_iq_i} =$ is an elementary product of $A$ with $1 = p_1 < p_2 < ... < p_n = n$ then the Associated Permutation of this elementary product is the permutation of the column numbers of the multiplied entries of the elementary product, i.e., $(q_1, q_2, ..., q_n)$.

The order of the entries in the elementary product matters! Hence we require that the row numbers of the entries from left to right in the elementary product are ascending, i.e., $1 = p_1 < p_2 < ... < p_n = n$.

For example, we saw that $A = \begin{bmatrix} a_{11} & a_{12}\\ a_{21} & a_{22} \end{bmatrix}$ has $2! = 2$ elementary products, namely $a_{11} \cdot a_{12}$ which has an associated permutation $(1, 2)$, and $a_{12} \cdot a_{21}$ which has an associated permutation $(2, 1)$. It's not hard to see that for any $n \times n$ matrix $A$ that the $n!$ elementary products of $A$ each have a unique associated permutation.

We are now ready to formula combinatorial theorem for the determinant of a square matrix.

Theorem 1: If $A$ is a square $n \times n$ matrix and if for each elementary product $\prod_{i=1}^{n} a_{p_iq_i}$ we have that $1 = p_1 < p_2 < ... < p_n = n$ then $\displaystyle{\det (A) = \sum_{(q_1, q_2, ..., q_n) \: \mathrm{is \: even}} \left ( \prod_{i=1}^{n} a_{p_iq_i} \right ) - \sum_{(q_1, q_2, ..., q_n) \: \mathrm{is \: odd}} \left ( \prod_{i=1}^{n} a_{p_iq_i} \right )}$.

Theorem 1 says that the determinant of $A$ is equal to the sum of the elementary products whose associated permutations are even MINUS the sum of the elementary products whose associated permutations are odd.

We will not prove Theorem 1, however, we will show that the formula above generates the standard determinant formula for a $2 \times 2$ matrix. We have that the elementary products of any $2 \times 2$ matrix $A$ is $a_{11} \cdot a_{22}$ and $a_{12} \cdot a_{21}$ which have associated permutations $(1, 2)$ and $(2, 1)$ as we have noted before. The permutation $(1, 2)$ has $0$ inversions and so it is even. Th permutation $(2, 1)$ has $1$ inversion and so it is odd. Thus from the formula above we obtain the standard formula for the determinant of a $2 \times 2$ matrix:

(3)
\begin{align} \quad \det (A) = a_{11}a_{22} - a_{12}a_{21} \end{align}
Unless otherwise stated, the content of this page is licensed under Creative Commons Attribution-ShareAlike 3.0 License