This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
Permutation matrix
This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.
$\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
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
### 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())
寫出 $\sigma$ 的雙行表示法、以及循環表示法。
說明如何將 $\sigma$ 單行表示法經過元素互換變回 $12\ldots n$。
最後求出 $\sgn(\sigma)$。
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)$.
畫出 $\sigma$ 的圖表示法 $G_\sigma$、
計算 $G_\sigma$ 上的圈數、
並求出 $\sgn(\sigma)$。
Draw the graph representation $G_\sigma$ for $\sigma$, count the number of cycles on $G_\sigma$, and then find $\sgn(\sigma)$.
寫下 $\sigma$ 的排列矩陣 $P_\sigma$，
並求出 $\det(P_\sigma)$。
Find the permutation matrix $P_\sigma$ for $\sigma$ and then find $\det(P_\sigma)$.
當 $n = 2$ 時，
下表列出所有 $\mathfrak{S}_n$ 中排列、
其單行表示法、循環表示法、及其正負號：
| one-line repr | cycle repr | sign |
|---|---|---|
| $12$ | $(1)(2)$ | $1$ |
| $21$ | $(12)$ | $-1$ |
分別建立 $n = 3$ 及 $n = 4$ 的表格。
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$.
以下練習討論將一個排列變回單位排列所需的置換數。
The following exercises study the number of steps of switching elements in order to obtain the identity permutation.
令 $\sigma$ 的循環表示法為 $(1,2,3)$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $123$。
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$.
令 $\sigma$ 的循環表示法為 $(1,2,3,4)$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $1234$。
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$.
若 $\sigma$ 的循環表示法中只有一個循環且長度為 $n$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $12\cdots n$。
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$.
若 $\sigma$ 的循環表示法中包含 $k$ 個循環，
且每個循環且長度分別為 $n_1, n_2, \ldots, n_k$。
令 $n = n_1 + \cdots + n_k$。
求要經過幾次置換（元換互換）才能將 $\sigma$ 的單行表示法變回 $12\cdots n$。
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$.
說明對任意 $[n]$ 上的排列 $\sigma$，
所需的置換數和 $n + c(\sigma)$ 的奇偶性一致。
For any permutation $\sigma$ on $[n]$, explain why the number of steps of switching elements and $n + c(\sigma)$ have the same parity.
若 $\sigma$ 為 $[n]$ 上的一個排列。
說明 $f(\sigma) = (-1)^{n + c(\sigma)}$ 符合以下性質：
則 $f(\tau) = -f(\sigma)$。
因此 $\sgn(\sigma) = f(\sigma)$ 是一個定義完善的函數。
Let $\sigma$ be a permutation on $[n]$. Explain why $f(\sigma) = (-1)^{n + c(\sigma)}$ has the following properties:
Therefore, $\sgn(\sigma) = f(\sigma)$ is well-defined function.
給定兩個整數 $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 中矩陣的關係。
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.