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.$

## 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)}$$?