# 排列矩陣

Permutation matrix

This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/).

$\newcommand{\trans}{^\top}
\newcommand{\adj}{^{\rm adj}}
\newcommand{\cof}{^{\rm cof}}
\newcommand{\inp}[2]{\left\langle#1,#2\right\rangle}
\newcommand{\dunion}{\mathbin{\dot\cup}}
\newcommand{\bzero}{\mathbf{0}}
\newcommand{\bone}{\mathbf{1}}
\newcommand{\ba}{\mathbf{a}}
\newcommand{\bb}{\mathbf{b}}
\newcommand{\bc}{\mathbf{c}}
\newcommand{\bd}{\mathbf{d}}
\newcommand{\be}{\mathbf{e}}
\newcommand{\bh}{\mathbf{h}}
\newcommand{\bp}{\mathbf{p}}
\newcommand{\bq}{\mathbf{q}}
\newcommand{\br}{\mathbf{r}}
\newcommand{\bx}{\mathbf{x}}
\newcommand{\by}{\mathbf{y}}
\newcommand{\bz}{\mathbf{z}}
\newcommand{\bu}{\mathbf{u}}
\newcommand{\bv}{\mathbf{v}}
\newcommand{\bw}{\mathbf{w}}
\newcommand{\tr}{\operatorname{tr}}
\newcommand{\nul}{\operatorname{null}}
\newcommand{\rank}{\operatorname{rank}}
%\newcommand{\ker}{\operatorname{ker}}
\newcommand{\range}{\operatorname{range}}
\newcommand{\Col}{\operatorname{Col}}
\newcommand{\Row}{\operatorname{Row}}
\newcommand{\spec}{\operatorname{spec}}
\newcommand{\vspan}{\operatorname{span}}
\newcommand{\Vol}{\operatorname{Vol}}
\newcommand{\sgn}{\operatorname{sgn}}
\newcommand{\idmap}{\operatorname{id}}
\newcommand{\am}{\operatorname{am}}
\newcommand{\gm}{\operatorname{gm}}
\newcommand{\mult}{\operatorname{mult}}
\newcommand{\iner}{\operatorname{iner}}$

from gnm import random_permutation

## Main idea

Let $[n] = \{1,\ldots,n\}$.
A **permutation** is a bijection from $[n]$ to itself.
The identity map $\idmap_n: [n]\rightarrow [n]$ with $\idmap_n(x) = x$ is called the **identity permutation** .
Let $\mathfrak{S}_n$ be the set of all permutations on $[n]$.
There are several ways to represents a permutation $\sigma: [n]\rightarrow [n]$.

**Two-line representation**:

$$
\begin{array}{cccc}
1 & 2 & \cdots & n \\
\sigma(1) & \sigma(2) & \cdots & \sigma(n)
\end{array}
$$

This notation is a bit lengthy but it is easy to see the inverse.

**One-line representation**:

$$
\sigma(1)\sigma(2)\cdots\sigma(n)
$$

This one is short but hard to see the connection between $i$ and $\sigma(i)$.

**Cycle representation**:

$$
\big(i_1\sigma(i_1)\sigma^2(i_1)\cdots\big)\big(i_2\sigma(i_2)\sigma^2(i_2)\cdots\big) \cdots
$$

It shows the cycle behavior of a permutation but is less easy to calculate the composition of two permutations.

**Graph representation**:

$$
\begin{aligned}
V &= [n] \\
E &= \{(i,\sigma(i)): i\in [n]\} \\
G_\sigma &= (V,E)
\end{aligned}
$$

This is a **digraph** on $n$ **vertices** and $n$ **directed edges**.
Note that the digraph $G$ is composed of several cycles.

The **sign** of a permutation $\sigma$ is

$$
\sgn(\sigma) = (-1)^k = (-1)^{n + c(\sigma)}.
$$

where $k$ is the number of swaps of two values on the one-line representation so that it can becomes $12\ldots n$,
while $c(\sigma)$ is the number of cycles in $G_\sigma$.

Let $\sigma$ be a permutation on $[n]$.
The **permutation matrix** $P_\sigma$ of $\sigma$ is the $0,1$-matrix whose $i,\sigma(i)$-entries are $1$ for $i = 1,\ldots,n$.
Therefore, a permutation matrix is a matrix such that there is a unique $1$ one each row and each column.
It turns out that

$$
\det(P_\sigma) = \sgn(\sigma).
$$

## Side stories

- well-defined
- Stirling numbers

## Experiments

##### Exercise 1

執行以下程式碼。

<!-- eng start -->
Run the code below.
<!-- eng end -->

### code
set_random_seed(0)
print_ans = False

n = 5
sigma = random_permutation(n)
print("n = ", n)
print("one-line representation of sigma =", sigma.one_line)

if print_ans:
    print("Two-line representation:")
    print(sigma.two_line_repr())
    print("Cycle representation:")
    print(sigma.cycle_repr())
    print("One may convert sigma back to 12...n by the following swaps:")
    print(sigma.sort())
    print("sgn(sigma) =", sigma.sign())
    sigma.digraph().show()
    P = sigma.matrix()
    print("permutation matrix =")
    pretty_print(P)
    print("det(P) =", P.det())

##### Exercise 1(a)

寫出 $\sigma$ 的雙行表示法、以及循環表示法。
說明如何將 $\sigma$ 單行表示法經過元素互換變回 $12\ldots n$。
最後求出 $\sgn(\sigma)$。

<!-- eng start -->
Find the two-line representation and the cycle representation of $\sigma$. Explain how to start from its one-line representation and reach $12\ldots n$ by switching elements. Then find $\sgn(\sigma)$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 1(a)
> Set `seed=324`, we get
$n=5$\
one-line representation of $\sigma=[3,4,5,1,2]$

Two-line representation of $\sigma$ is :
$$\begin{array}{cccc}
1 & 2 & 3 & 4 & 5 \\
3 & 4 & 5 & 1 & 2
\end{array}
$$

Cycle representation of $\sigma$ is : $(13524)$.
Do following swiches step by step :
1. $5\leftrightarrow 2$ $\longrightarrow$ $34215$
2. $4\leftrightarrow 1$ $\longrightarrow$ $31245$
3. $3\leftrightarrow 2$ $\longrightarrow$ $21345$
4. $2\leftrightarrow 1$ $\longrightarrow$ $12345$

Because we have changed the order for four times, we get to know that $\sgn(\sigma)=(-1)^4=1$.

:::warning

Sigma defines the mapping:
$1\rightarrow 3\rightarrow 5\rightarrow 2\rightarrow 4\rightarrow 1$
so the cycle representation is $(13524)$

:::

##### Exercise 1(b)

畫出 $\sigma$ 的圖表示法 $G_\sigma$、
計算 $G_\sigma$ 上的圈數、
並求出 $\sgn(\sigma)$。

<!-- eng start -->
Draw the graph representation $G_\sigma$ for $\sigma$, count the number of cycles on $G_\sigma$, and then find $\sgn(\sigma)$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 1(b)

By definition : $\sgn(\sigma) = (-1)^{n + c(\sigma)}$.
According to the picture, there's one cycle, so $c(\sigma)=1$.
And knowing $n=5$, $\sgn(\sigma) = (-1)^{5 + 1}=(-1)^{6}=1$.

##### Exercise 1(c)

寫下 $\sigma$ 的排列矩陣 $P_\sigma$，
並求出 $\det(P_\sigma)$。

<!-- eng start -->
Find the permutation matrix $P_\sigma$ for $\sigma$ and then find $\det(P_\sigma)$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 1(c)

Let $\sigma(i)$ denote the entry in the $i$th row of $P_\sigma$ that equals $1$.
We have $\sigma(1)=3$, $\sigma(2)=4$, $\sigma(3)=5$, $\sigma(4)=1$, $\sigma(5)=2$, and all other entries in $P_\sigma$ are $0$.

$$
P_\sigma=\begin{bmatrix}
0 & 0 & 1 & 0 & 0 \\
0 & 0 & 0 & 1 & 0 \\
0 & 0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 & 0 \\
0 & 1 & 0 & 0 & 0 \end{bmatrix}.
$$

By performing row switches $4$ times to transform $P_\sigma$ into the identity matrix, we get $\det(P_\sigma)=(-1)^4=(-1)^{2\times 2}=1.$

:::info
What do the experiments try to tell you? (open answer)

A permutation can be written in many ways, but it is not difficult to observe that it has a bijection property.
:::

:::success
Nice.
:::

## Exercises

##### Exercise 2

當 $n = 2$ 時，
下表列出所有 $\mathfrak{S}_n$ 中排列、
其單行表示法、循環表示法、及其正負號：

one-line repr | cycle repr | sign
--------|--------|--------
$12$ | $(1)(2)$ | $1$
$21$ | $(12)$ | $-1$

分別建立 $n = 3$ 及 $n = 4$ 的表格。

<!-- eng start -->
For $n = 2$, list all permuatations in $\mathfrak{S}_n$ can find the one-line representation, cycle representation, and the sign for each of them.

one-line repr | cycle repr | sign
--------|--------|--------
$12$ | $(1)(2)$ | $1$
$21$ | $(12)$ | $-1$

Also build the table for $n = 3$ and $n = 4$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 2

When $n=3$, there are $3!$ probabilities :
one-line repr | cycle repr | sign
--------|--------|--------
$123$ | $(1)(2)(3)$ | $1$
$132$ | $(1)(23)$ | $-1$
$213$ | $(12)(3)$ | $-1$
$231$ | $(123)$ | $1$
$312$ | $(132)$ | $1$
$321$ | $(2)(13)$ | $-1$

When $n=4$, there are $4!$ probabilities :
one-line repr | cycle repr | sign
--------|--------|--------
$1234$ | $(1)(2)(3)(4)$ | $1$
$1243$ | $(1)(2)(34)$ | $-1$
$1324$ | $(1)(4)(23)$ | $-1$
$1342$ | $(1)(234)$ | $1$
$1423$ | $(1)(432)$ | $1$
$1432$ | $(1)(3)(24)$ | $-1$
$2134$ | $(12)(3)(4)$ | $-1$
$2143$ | $(12)(34)$ | $1$
$2314$ | $(123)(4)$ | $1$
$2341$ | $(1234)$ | $-1$
$2413$ | $(1243)$ | $-1$
$2431$ | $(124)(3)$ | $1$
$3124$ | $(321)(4)$ | $1$
$3142$ | $(1342)$ | $-1$
$3214$ | $(13)(2)(4)$ | $-1$
$3241$ | $(134)(2)$ | $1$
$3412$ | $(13)(24)$ | $1$
$3421$ | $(1324)$ | $-1$
$4123$ | $(1432)$ | $-1$
$4132$ | $(142)(3)$ | $1$
$4213$ | $(143)(2)$ | $1$
$4231$ | $(14)(2)(3)$ | $-1$
$4312$ | $(1423)$ | $-1$
$4321$ | $(14)(23)$ | $1$

---
##### Exercise 3

以下練習討論將一個排列變回單位排列所需的置換數。

<!-- eng start -->
The following exercises study the number of steps of switching elements in order to obtain the identity permutation.
<!-- eng end -->

##### Exercise 3(a)

令 $\sigma$ 的循環表示法為 $(1,2,3)$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $123$。

<!-- eng start -->
Let $\sigma$ be the permutation with its cycle representation $(1,2,3)$. How many steps of switching elements are required to make it back to the identity permutation with the one-line representation $123$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 3(a)

Cycle representation shows that the corresponding order is

$$
\begin{array}{cccc}
1 & 2 & 3 \\
2 & 3 & 1
\end{array}
$$

Switching two times will get $123$.

---
##### Exercise 3(b)

令 $\sigma$ 的循環表示法為 $(1,2,3,4)$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $1234$。

<!-- eng start -->
Let $\sigma$ be the permutation with its cycle representation $(1,2,3,4)$. How many steps of switching elements are required to make it back to the identity permutation with the one-line representation $1234$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 3(b)
Cycle representation shows that the corresponding order is
$$
\begin{array}{cccc}
1 & 2 & 3 & 4\\
2 & 3 & 4 & 1
\end{array}
$$

Switching three times will get $1234$.

---
##### Exercise 3(c)

若 $\sigma$ 的循環表示法中只有一個循環且長度為 $n$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $12\cdots n$。

<!-- eng start -->
Suppose $\sigma$ be a permutation with only one cycle of length $n$. How many steps of switching elements are required to make it back to the identity permutation with the one-line representation $12\cdots n$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 3(c)

Without loss of generality, suppose that the one-line notation of $\sigma$ is $2 \ 3 \cdots n \ 1$, and we can obtain $1 \ 2 \cdots n$ by performing $n-1$ transpositions of $1$ to the front.

---
##### Exercise 3(d)

若 $\sigma$ 的循環表示法中包含 $k$ 個循環，
且每個循環且長度分別為 $n_1, n_2, \ldots, n_k$。
令 $n = n_1 + \cdots + n_k$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $12\cdots n$。

<!-- eng start -->
Suppose $\sigma$ be a permutation with $k$ cycles and their lengths are $n_1, n_2, \ldots, n_k$. Let $n = n_1 + \cdots + n_k$. How many steps of switching elements are required to make it back to the identity permutation with the one-line representation $12\cdots n$.
<!-- eng end -->

**[由 :cloud: 提供]**
##### Ans 3(d)

Suppose $\sigma$ can be decomposed into $k$ cycles, where the length of the $i$-th cycle is $n_i$. For each cycle, if we move its elements forward $n_i-1$ times, we can obtain a new cycle where all the elements are arranged in order.

Therefore, each cycle needs to be permuted $n_i-1$ times, equal to its own length $n_i$, in order for all cycles in the cycle representation of a permutation to become $1$. Next, we just need to add up the permutation times of all cycles to obtain the total number of permutations required to transform $\sigma$ into $1\ 2\ \cdots n$.

Therefore, if $\sigma$ is decomposed into $k$ cycles, the number of permutations required to transform $\sigma$ into $1\ 2\ \cdots n$ is:
$$
(n_1 - 1) + (n_2 - 1) + \cdots + (n_k - 1)
$$
This result can be simplified as:
$$
n_1 + n_2 + \cdots + n_k - k
$$
Because all elements in each cycle appear exactly once, so the total number of elements in the $k$ cycles is $n_1+n_2+\cdots+n_k$.
The last element of each cycle does not need to be permuted again, so we need to subtract $k$.

---
##### Exercise 3(e)

說明對任意 $[n]$ 上的排列 $\sigma$，
所需的置換數和 $n + c(\sigma)$ 的奇偶性一致。

<!-- eng start -->
For any permutation $\sigma$ on $[n]$, explain why the number of steps of switching elements and $n + c(\sigma)$ have the same parity.
<!-- eng end -->

##### Exercise 4

若 $\sigma$ 為 $[n]$ 上的一個排列。
說明 $f(\sigma) = (-1)^{n + c(\sigma)}$ 符合以下性質：

1. $f(\idmap_n) = 1$。
2. 若將 $\sigma$ 的單行表示法中的 $\sigma(i)$ 和 $\sigma(j)$ 互換而得到一個新的排列 $\tau$，
則 $f(\tau) = -f(\sigma)$。

因此 $\sgn(\sigma) = f(\sigma)$ 是一個定義完善的函數。

<!-- eng start -->
Let $\sigma$ be a permutation on $[n]$. Explain why $f(\sigma) = (-1)^{n + c(\sigma)}$ has the following properties:

1. $f(\idmap_n) = 1$。
2. Suppose $\tau$ is obtained from $\sigma$ by switching the elements $\sigma(i)$ and $\sigma(j)$ in the one-line representation. Then $f(\tau) = -f(\sigma)$.

Therefore, $\sgn(\sigma) = f(\sigma)$ is well-defined function.
<!-- eng end -->

##### Exercise 5

給定兩個整數 $n\geq k \geq 0$。
**第一類斯特靈數（Stirling numbers of the first kind）** $s(n,k)$
指的是 $\mathfrak{S}_n$ 中恰有 $k$ 個循環的排列的個數
乘上 $(-1)^{n-k}$。
**第二類斯特靈數（Stirling numbers of the second kind）** $S(n,k)$
指的是要把 $[n]$ 分成非空的 $k$ 堆的分法數。

對於 $i,j \in \{0,1,2,3\}$ 將 $s(i,j)$ 寫成一個 $4\times 4$ 矩陣 $S_1$。
對於 $i,j \in \{0,1,2,3\}$ 將 $S(i,j)$ 寫成一個 $4\times 4$ 矩陣 $S_2$。
寫出 $S_1$ 和 $S_2$，並觀察其和 410-7 中矩陣的關係。

<!-- eng start -->
Let $n \geq k \geq 0$ be integers. The **Stirling numbers of the first kind** $s(n,k)$ is the number of permutations in $\mathfrak{S}_n$ that has exactly $k$ cycles along with the sign $(-1)^{n-k}$. The **Stirling numbers of the first kind** $S(n,k)$ is the number of ways to partition $[n]$ into $k$ indistinguishable nonempty sets.

For each combination of $i,j \in \{0,1,2,3\}$, find $s(i,j)$ and record them into a $4\times 4$ matrix $S_1$. For each combination of $i,j \in \{0,1,2,3\}$, find $S(i,j)$ and record them into a $4\times 4$ matrix $S_2$. Write down $S_1$ and $S_2$ and compare them with what those in 410-7.
<!-- eng end -->