Up Main page

Before we look at determinants, we need to learn a little about permutations. Loosely speaking, a permutation of a set is a specific arrangement of the elements of the set. For example, a permutation of the set \(\{1,2,3\}\) could be 3, 1, 2. Here, we consider only permutations of finite sets.

Mathematically, a permutation is a one-to-one and onto mapping \(\sigma:S\rightarrow S\) where \(S\) is a set. For the example above, we can define \(\sigma\) to be given by \(\sigma(1)=3\), \(\sigma(2)=1\), and \(\sigma(3) = 2\). We usually denote such a permutation as a two-row array such that each element in the bottom row represents the output of the element immediately above it. Using this notation, \(\sigma = \left(\begin{array}{ccc} 1& 2&3\\ 3&1 &2\end{array}\right)\). (This should not be confused with matrix notation.)

The set of all the permutations on the set \(\{1,2,\ldots,n\}\) is denoted by \(S_n\). Note that \(|S_n| = n!\). The table below gives all the elements in \(S_2\) and \(S_3\).

\(S_2\) \(\left(\begin{matrix} 1 & 2\\ 1 & 2\end{matrix}\right)\), \(\left(\begin{matrix} 1 & 2\\ 2 & 1\end{matrix}\right)\)
\(S_3\) \(\left(\begin{matrix} 1 & 2 & 3\\ 1 & 2 & 3\end{matrix}\right)\), \(\left(\begin{matrix} 1 & 2 & 3\\ 1 & 3 & 2\end{matrix}\right)\), \(\left(\begin{matrix} 1 & 2 & 3\\ 2 & 1 & 3\end{matrix}\right)\), \(\left(\begin{matrix} 1 & 2 & 3\\ 2 & 3 & 1\end{matrix}\right)\), \(\left(\begin{matrix} 1 & 2 & 3\\ 3 & 1 & 2\end{matrix}\right)\), \(\left(\begin{matrix} 1 & 2 & 3\\ 3 & 2 & 1\end{matrix}\right)\)

The permutation \(\sigma \in S_n\) such that \(\sigma(i) = i\) for \(i = 1,\ldots, n\) is called the identity permutation.

Composing permutations

Let \(\sigma\) and \(\gamma\) be two permutations of \(\{1,\ldots,n\}\). Then \(\gamma \circ \sigma\) is again a permutation of \(\{1,\ldots,n\}\).

Example

Let \(\sigma = \left(\begin{array}{ccc} 1& 2&3\\ 3&1 &2\end{array}\right)\) and let \(\gamma = \left(\begin{array}{ccc} 1& 2&3\\ 3&2 &1\end{array}\right)\). What is \(\gamma \circ \sigma\)?

Note that \begin{eqnarray*} (\gamma\circ\sigma)(1) & = & \gamma(\sigma(1)) = \gamma(3) = 1, \\ (\gamma\circ\sigma)(2) & = & \gamma(\sigma(2)) = \gamma(1) = 3, \\ (\gamma\circ\sigma)(3) & = & \gamma(\sigma(3)) = \gamma(2) = 2 \end{eqnarray*} Hence, \(\gamma \circ \sigma\) is the permutation \(\left(\begin{array}{ccc} 1& 2&3\\ 1& 3 &2\end{array}\right)\).

But if \(\gamma = \left(\begin{array}{ccc} 1& 2&3\\ 2& 3 &1\end{array}\right)\), then \(\gamma \circ \sigma\) is the identity permutation. (Verify this.) We call \(\gamma\) the inverse permutation (or simply inverse) of \(\sigma\). Every permutation has an inverse.

Prelude to the determinant of a square matrix

We will see later that the definition of the determinant of an \(n\times n\) matrix \(A\) consists of a sum of terms, each of which contains a product of the form \(A_{1,\sigma(1)} A_{2,\sigma(2)}\cdots A_{n,\sigma(n)}\) for some permutation \(\sigma \in S_n\).

Remember that in \(A_{i,j}\), \(i\) is the row index and \(j\) is the column index. So the product \(A_{1,\sigma(1)} A_{2,\sigma(2)}\cdots A_{n,\sigma(n)}\) has exactly one entry from each row of \(A\). Since \(\sigma(1),\ldots,\sigma(n)\) is a permutation of the numbers \(1,\ldots, n\), the product \(A_{1,\sigma(1)} A_{2,\sigma(2)}\cdots A_{n,\sigma(n)}\) has exactly one entry from each column of \(A\).

Example

Let \(A = \begin{bmatrix} a & b & c \\ d & e & f \\ u & v & w\end{bmatrix}\). Let \(\sigma = \left(\begin{array}{ccc} 1& 2&3\\ 3&1 &2\end{array}\right)\). Then \[A_{1,\sigma(1)} A_{2,\sigma(2)} A_{3,\sigma(3)} = A_{1,3} A_{2,1} A_{3,2} = c d v.\]

Quick Quiz

Exercises

Let \(A = \begin{bmatrix} 6 & 2 & 3 \\ 0 & 1 & -1 \\ -5 & 7 & 4\end{bmatrix}\). Let \(\sigma = \left(\begin{array}{ccc} 1& 2&3\\ 3& 2 &1\end{array}\right)\). What is the value of \(A_{1,\sigma(1)} A_{2,\sigma(2)} A_{3,\sigma(3)}\)?