# 排列矩陣

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

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

執行以下程式碼。

### 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())

藉由 `seed 0` 可以得到\
$n=5$\
one-line representation of $\sigma=[3,2,4,5,1]$

##### Exercise 1(a)

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

ANS
\
$\sigma$ 的雙行表示法為
$$
\begin{array}{cccc}
1 & 2 & 3 & 4 & 5 \\
3 & 2 & 4 & 5 & 1
\end{array}
$$
\
$\sigma$ 的循環表示法為
$(2)(1345)$。
\
接下來我們把 $1$ 跟 $3$ 交換，再將 $3$ 跟 $4$ 交換，最後再把 $4$ 跟 $5$ 交換後可以把 $\sigma$ 單行表示法 $3$ $2$ $4$ $5$ $1$ 變回 $1$ $2$ $3$ $4$ $5$。\
而根據定義我們可以知道 $\sgn(\sigma) = (-1)^k$，其中 $k$ 為元素交換的次數，也就是說 $k=3$，因此我們可以知道 $\sgn(\sigma) = (-1)^3=-1$。

##### Exercise 1(b)

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

ANS

根據定義我們得知 $\sgn(\sigma) = (-1)^{n + c(\sigma)}$，從圖中我們可以看到有兩個圈，因此 $c(\sigma)=2$，以及 $n=5$，因此 $\sgn(\sigma) = (-1)^{5 + 2}=(-1)^{7}=-1$。

##### Exercise 1(b)

寫下 $\sigma$ 的排列矩陣 $P_\sigma$，
並求出 $\det(P_\sigma)$。
ANS
\
首先我們可以知道\
$\sigma(1)=3$，代表$P_\sigma$第一列第三行元素為 $1$，\
$\sigma(2)=2$，代表$P_\sigma$第二列第二行元素為 $1$，\
$\sigma(3)=4$，代表$P_\sigma$第三列第四行元素為 $1$，\
$\sigma(4)=5$，代表$P_\sigma$第四列第五行元素為 $1$，\
$\sigma(5)=1$，代表$P_\sigma$第五列第一行元素為 $1$，\
其餘的每個元素都是 $0$，因此我們得到

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

而我們用拉普拉斯展開法可以算出

$$
\det(P_\sigma) =
(1)\begin{bmatrix}
0 & 1 & 0 & 0\\
0 & 0 & 1 & 0 \\
0 & 0 & 0 & 1 \\
1 & 0 & 0 & 0 \\
\end{bmatrix}
=(1)\cdot(-1) \cdot \begin{bmatrix}
0 & 1 & 0 \\
0 & 0 & 1 \\
1 & 0 & 0 \\
\end{bmatrix}=(1)\cdot(-1) \cdot 1=-1.
$$

:::success

上面這幾題都寫很清楚 :thumbsup:
附帶提一下，計算 $\det(P_\sigma)$ 的時候除了用降階以外，也可以用列運算將其換回單位矩陣。
:::

## 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$ 的表格。

#### 答:
當 $n=3$ 時，表格如下:
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$

當 $n=4$ 時，表格如下:
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$

:::success

Good 辛苦了 ：）
:::

##### Exercise 3

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

##### Exercise 3(a)

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

:::warning

- [x] one-line repr --> 單行表示法；可以的話盡量用中文，後面幾題也是
:::

答:
$\sigma$ 的單行表示法是 $231$，藉由將 $1$ 往前進行兩次置換即可得到 $123$。

##### Exercise 3(b)

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

答:
$\sigma$ 的單行表示法是 $2341$，藉由將 $1$ 往前進行三次置換即可得到 $1234$。

##### Exercise 3(c)

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

:::warning

- [x] $\sigma$ 的單行表示法不一定是 $23\cdots n1$，但可以寫：不失一般性，我們假設 $\sigma$ 的單行表示法為 ...
:::

答:
不失一般性，我們假設 $\sigma$ 的單行表示法為 $2 \ 3 \cdots n \ 1$，藉由將 $1$ 往前進行 $n-1$ 次置換即可得到 $1 \ 2 \cdots n$。

##### Exercise 3(d)

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

答:
已知每個循環需做自己長度 $n$ 的 $n-1$ 次才可得到 $12\cdots n$，因此我們將 $n$ 中的 $n_1,n_2,\cdots ,n_k$ 做相同的事情，由此可以得知 $n$ 需做
$(n_1 - 1) + (n_2 - 1) + \cdots + (n_k - 1)$ 次置換即可得到 $12\cdots n$。

##### Exercise 3(e)

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

答:
若 $\sigma$ 中包含 $k$ 個循環，由此可得 $c(\sigma)=k$，我們透過 3(d) 可以得知需要 $n-k$ 次置換才可得到 $12\cdots n$，而 $(n + c(\sigma)) + (n - k) = (n + k) + (n - k) = 2n$，而偶數會等於奇數相加或是偶數相加，由此可知 $n + c(\sigma)$ 和 $n - k$ 奇偶性一致。

:::success

這整大題寫很好
:::

##### 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)$ 是一個定義完善的函數。

$Ans:$

由於 $\idmap_n$ 為一個將 $a$ 送往 $a$ 之排列，我們可以說這個排列的循環有 $n$ 個，因此 $c(\sigma) = n$。故
$$
f(\idmap_n) = (-1)^{n + c(\sigma)} = (-1)^{n + n} = (-1)^{2n} = 1.
$$

另外，令 $\sigma$ 中有 $k$ 個循環 $( k \in \mathbb N)$，則會有以下兩種情形：

$(1)$

$\sigma(i),\sigma(j)$ 在同一個循環中。在這個情況中我們可以假設

$$
i \rightarrow \sigma(i) \rightarrow \cdots \rightarrow j \rightarrow \sigma(j) \rightarrow \cdots \rightarrow i.
$$

如果 $i$ 送到的元素變成 $\sigma(j)$，而 $j$ 送到的元素變成 $\sigma(i)$，則循環結構會變成

$$
i \rightarrow \sigma(j) \rightarrow \cdots \rightarrow i
$$

與

$$
j \rightarrow \sigma(i) \rightarrow \cdots \rightarrow j
$$

這兩個循環。那麼我們可以得到

$$
c(\tau) =c(\sigma) + 1.
$$

$(2)$

$\sigma(i),\sigma(j)$ 在不同循環中。在這個情況中我們可以假設有兩個循環分別為

$$
i \rightarrow \sigma(i) \rightarrow \cdots \rightarrow i
$$

與

$$
j \rightarrow \sigma(j) \rightarrow \cdots \rightarrow j.
$$

如果 $i$ 送到的元素變成 $\sigma(j)$，而 $j$ 送到的元素變成 $\sigma(i)$，則循環結構會變成

$$
i \rightarrow \sigma(j) \rightarrow \cdots \rightarrow j \rightarrow \sigma(i) \rightarrow \cdots \rightarrow i.
$$

這個大循環。那麼我們可以得到

$$
c(\tau) = c(\sigma) - 1.
$$

從 $(1)$ 的情形可以得到：
$$
f(\tau) = (-1)^{n+c(\tau)} = (-1)^{n+c(\sigma)+1} =(-1) \cdot (-1)^{n+c(\sigma)} = -f(\sigma).
$$

從 $(2)$ 的情形可以得到：
$$
f(\tau) = (-1)^{n+c(\tau)} = (-1)^{n+c(\sigma)-1} =\frac{1}{-1} \cdot (-1)^{n+c(\sigma)} = -f(\sigma).
$$

因此我們可以得到 $f(\tau) = -f(\sigma)$。

##### 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 first 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 中矩陣的關係。

$Ans:$

根據題目我們可以寫出
$$
\begin{array}{l}
s(0,0) = 1，s(0,1) = 0，s(0,2) = 0，s(0,3) = 0, \\
s(1,0) = 0，s(1,1) = 1，s(1,2) = 0，s(1,3) = 0, \\
s(2,0) = 0，s(2,1) = -1，s(2,2) = 1，s(2,3) = 0, \\
s(3,0) = 0，s(3,1) = 2，s(3,2) = -3，s(3,3) = 1.
\end{array}
$$

以及

$$
\begin{array}{l}
S(0,0) = 1，S(0,1) = 0，S(0,2) = 0，S(0,3) = 0, \\
S(1,0) = 0，S(1,1) = 1，S(1,2) = 0，S(1,3) = 0, \\
S(2,0) = 0，S(2,1) = 1，S(2,2) = 1，S(2,3) = 0, \\
S(3,0) = 0，S(3,1) = 1，S(3,2) = 3，S(3,3) = 1.
\end{array}
$$

依題目我們得到
$$
S_1 =
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & -1 & 2 \\
0 & 0 & 1 & -3 \\
0 & 0 & 0 & 1
\end{bmatrix}，
S_2 =
\begin{bmatrix}
1 & 0 & 0 & 0 \\
0 & 1 & 1 & 1 \\
0 & 0 & 1 & 3 \\
0 & 0 & 0 & 1
\end{bmatrix}.
$$

根據 410-7，我們得到這兩個矩陣其實就是基底轉換矩陣。

:::info
目前分數：6 ± 檢討 = 6.5
:::