How to write the set of all permutations on a set $n=\{1, 2, \ldots, n\}$

Question

Let $n ∈ N$. Let $S_n$ denote the set of permutations on $\{1, . . . , n\}$.

For any $σ ∈ S_n$, define $sign(σ) := (−1)^N$ , where $σ$ can be written as the product of $N$ transpositions.

Now, let $A$ be an $n \times n$ matrix with entries $A_{ij},i,j∈\{1,...,n\}$. Consider the expression:

• $F(A) := \sum_{σ ∈ S_n}sign(σ) \prod_{i=1}^{n} A_{iσ(i)}.$

QUESTION:

If we have a $2 \times 2$ matrix $A$, we have $n =2$. I want to know how the set $S_n$ would look like.

Thank you.

Answer 1

Say you have the matrix $$A= \begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix},$$ a very normal $2\times 2$ matrix.

As you said $S_n$ is the set of all the permutations of the set $\{1,\dots,n\}$. So $S_2$ is the set of all the permutations of $\{1,2\}$, hence

$$S_2 = \{[12],[21]\}.$$

You can think at the function $\sigma$ as follows: $\sigma(i)=j$ means the permutation $\sigma$ sends the number $i$ to $j$.

The permutation $\sigma_1:=[12]$ is the identity of the set $S_2$, since the number $1$ and the number $2$ do not change their position. Hence we have $\sigma_1(1)=1$ and $\sigma_1(2)=2$. The permutation $\sigma_2:=[21]$ actually says that $1$ goes to $2$ and that $2$ goes to $1$, so $\sigma_2(1)=2$ and $\sigma_2(2)=1$. These two are the only possible permutations of the set $\{1,2\}$. This is how $S_2$ looks like.

We can also look at how $$F(A) := \sum_{σ ∈ S_2}\text{sign}(σ) \prod_{i=1}^{2} A_{iσ(i)}$$ looks like. First of all the term $\sum_{σ ∈ S_2}$ tells you that you need to sum $2$ elements, since you have only $2$ permutations in $S_2$. As a second step you want to evaluate the signum of the permutations in $S_2$. You defined it as $\text{sign}(\sigma) = (-1)^N$, where $N$ is the number of transpositions of your permutation. We have two signum to evaluate:

$$\text{sign}(\sigma_1)= (-1)^0=1; \qquad \text{sign}(\sigma_2) = (-1)^1=-1.$$

(ask if you have problem with this step). Now we can finally evaluate $F(A)$:

\begin{align*} F(A) &= \sum_{σ ∈ S_2}\text{sign}(σ) \prod_{j=1}^{2} A_{jσ(j)} \\ &= \sum_{i=1}^2 \text{sign}(\sigma_i) \prod_{j=1}^2 A_{j\sigma_i(j)} \\ &= \text{sign}(\sigma_1)(A_{1\sigma_1(1)}A_{2\sigma_1(2)}) + \text{sign}(\sigma_2)(A_{1\sigma_2(1)}A_{2\sigma_2(2)}) \\ &= A_{11}A_{22}-A_{12}A_{21}. \end{align*}

This is actually the determinant of the matrix $A$. Indeed $F(A)$, in general, is exactly the determinant of an $n\times n$ matrix. Don't esitate to ask if you have problems.

Answer 2

S_2 has only two elements: the identity ( $ \sigma(1)=1, \sigma(2)=2 $ ) and a 'flip' ($ \sigma(1)=2, \sigma(2)=1 $). One typical way to write permutations is as cycles, then these would look like $(1)(2)$ and $(12)$, so you could write $S_2=\{ (1)(2),(12) \}$.

Answer 3

$S_n$ has $n!$ members. There are many ways to represent permutations. One is simply to list the elements in the order they are taken to under the permutations. This would give $S_3=\{(123),(132),(231),(213),(312),(321)\}$

Answer 4

It might help to realize that a permutation is a kind of bijection; an invertible map. In this case, the map is from a set to itself.

So, there are a few popular ways to write bijections between $[n] = \{1,2, \ldots, n\}$ and itself (that is, "permutations of" $[n]$).

To specify any $\sigma \in S_n$, we need to know where each $i \in S_n$ gets sent; we have to decide what $\sigma(i)$ is for each $i$, thinking of $\sigma$ as a function $\sigma: [n] \to [n]$.

A very explicit way to do this is by writing our permutation $\sigma$ like

$$\begin{pmatrix}1 & 2 & \ldots & n \\ \sigma(1) &\sigma(2) & \ldots & \sigma(n)\end{pmatrix},$$

so that the number directly below $i$ is $\sigma(i)$; where $\sigma$ sends $i$.

This often gets shortened to simply $( \sigma(1)\ \sigma(2)\ \ldots\ \sigma(n))$, as in Ross's answer. So in this notation, $(1\ 2\ 3)$ is the "identity" permutation, which sends each $i$ to itself.

An alternative way of writing permutations is in cycle notation. An example would be $\sigma = (1\ 3\ 4)(2\ 5)$, which is meant to illustrate that

$$1 \overset{\sigma}{\mapsto} 3 \overset{\sigma}{\mapsto} 4 \overset{\sigma}{\mapsto} 1, \qquad 2 \overset{\sigma}{\mapsto} 5 \overset{\sigma}{\mapsto} 2.$$

The latter is the notation supinf is referring to. It's a little trickier to write down all of $S_n$ using (disjoint) cycle notation, but it has its advantages: For example, it's much easier to determine the sign of a permutation, $\operatorname{sign}(\sigma)$, when it's written in cycle notation: $\operatorname{sign}(\sigma) = (-1)^k$, where $k$ is the number of cycles of even length (thus $(1\ 3\ 4)(2\ 5)$ above is immediately seen to be odd/have sign $-1$).