# 排列展開式

Permutation expansion

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 lingeo import random_int_list
from gnm import random_permutation

## Main idea

One may inductively apply the Laplace expansion to any given matrix.
For example,

$$
\begin{aligned}
\det\begin{bmatrix}
1 & 2 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
&=
\det\begin{bmatrix}
1 & 0 & 0 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
+
\det\begin{bmatrix}
0 & 2 & 0 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix}
+
\det\begin{bmatrix}
0 & 0 & 3 \\
4 & 5 & 6 \\
7 & 8 & 9
\end{bmatrix} \\
&=
\det\begin{bmatrix}
1 & 0 & 0 \\
0 & 5 & 6 \\
0 & 8 & 9
\end{bmatrix}
+
\det\begin{bmatrix}
0 & 2 & 0 \\
4 & 0 & 6 \\
7 & 0 & 9
\end{bmatrix}
+
\det\begin{bmatrix}
0 & 0 & 3 \\
4 & 5 & 0 \\
7 & 8 & 0
\end{bmatrix} \\
&=
\det\begin{bmatrix}
1 & 0 & 0 \\
0 & 5 & 0 \\
0 & 0 & 9
\end{bmatrix}
+
\det\begin{bmatrix}
1 & 0 & 0 \\
0 & 0 & 6 \\
0 & 8 & 0
\end{bmatrix}
+ \\
&\mathrel{\phantom{=}}
\det\begin{bmatrix}
0 & 2 & 0 \\
4 & 0 & 0 \\
0 & 0 & 9
\end{bmatrix}
+
\det\begin{bmatrix}
0 & 2 & 0 \\
0 & 0 & 6 \\
7 & 0 & 0
\end{bmatrix}
+ \\
&\mathrel{\phantom{=}}
\det\begin{bmatrix}
0 & 0 & 3 \\
4 & 0 & 0 \\
0 & 8 & 0
\end{bmatrix}
+
\det\begin{bmatrix}
0 & 0 & 3 \\
0 & 5 & 0 \\
7 & 0 & 0
\end{bmatrix}. \\
\end{aligned}
$$

Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ matrix.
Recall that $\mathfrak{S}_n$ is the set of all permutations on $[n]$.
Define the **weight** of a permutation $\sigma\in\mathfrak{S}_n$ as

$$
w_A(\sigma) = a_{1\sigma(1)}\cdots a_{n\sigma(n)}.
$$

When the matrix $A$ is clear from the context, we often write $w(\sigma) = w_A(\sigma)$.

##### Permutation expansion

Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ matrix.
Then

$$
\det(A) = \sum_{\sigma\in\mathfrak{S}_n} \sgn(\sigma)w(\sigma).
$$

## Side stories

- continuity of determinant

## Experiments

##### Exercise 1

執行以下程式碼。

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

### code
set_random_seed(0)
print_ans = False

n = 5
A = matrix(n, random_int_list(n^2, 3))
sigma1 = random_permutation(n)
sigma2 = random_permutation(n)
sigma3 = random_permutation(n)

pretty_print(LatexExpr("A ="), A)
print("one-line representation of sigma1 =", sigma1.one_line)
print("one-line representation of sigma2 =", sigma2.one_line)
print("one-line representation of sigma3 =", sigma3.one_line)

if print_ans:
    print("sgn(sigma1) =", sigma1.sign())
    print("w_A(sigma1) =", sigma1.weight(A))
    print("sgn(sigma2) =", sigma2.sign())
    print("w_A(sigma2) =", sigma2.weight(A))
    print("sgn(sigma3) =", sigma3.sign())
    print("w_A(sigma3) =", sigma3.weight(A))

##### Exercise 1(a)

求 $\sgn(\sigma_1)$ 及 $w_A(\sigma_1)$。

<!-- eng start -->
Find $\sgn(\sigma_1)$ and $w_A(\sigma_1)$.
<!-- eng end -->

##### Exercise 1(b)

求 $\sgn(\sigma_2)$ 及 $w_A(\sigma_2)$。

<!-- eng start -->
Find $\sgn(\sigma_2)$ and $w_A(\sigma_2)$.
<!-- eng end -->

##### Exercise 1(c)

求 $\sgn(\sigma_3)$ 及 $w_A(\sigma_3)$。

<!-- eng start -->
Find $\sgn(\sigma_3)$ and $w_A(\sigma_3)$.
<!-- eng end -->

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

...
:::

## Exercises

##### Exercise 2

令

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}.
$$

利用拉普拉斯展開，將 $\det(A)$ 寫成 $6$ 個矩陣的行列式值和，
其中每個矩陣的每行每列都至多只有一個非零項。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}.
$$

Use Laplace expansion to expand $\det(A)$ into the sum of the determinant of $6$ matrices such that each of the matrices has at most one nonzero entry on each row and each column.
<!-- eng end -->

##### Exercise 3

令

$$
A = \begin{bmatrix}
1 & 1 \\
1 & 2
\end{bmatrix}.
$$

則可建立一個表格包含所有的排列、其正負號、以及其配合 $A$ 的權重。
並用其計算 $\det(A)$。

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

如此可知 $\det(A) = 1\cdot 2 + (-1)\cdot 1 = 1$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 \\
1 & 2
\end{bmatrix}.
$$

Build a table that contains all permutations as its rows use it record their one-line representations, cycle representations, signs, and weights with resepct to $A$. Find $\det(A)$ by the table.
<!-- eng end -->

##### Exercise 3(a)

令

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}.
$$

依照同樣方法建立 $\mathfrak{S}_3$ 的表格，並求出 $\det(A)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 & 1 \\
1 & 2 & 4 \\
1 & 3 & 9
\end{bmatrix}.
$$

Build the same table for $\mathfrak{S}_3$ and find $\det(A)$.
<!-- eng end -->

##### Exercise 3(b)

令

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
1 & 4 & 16 & 64
\end{bmatrix}.
$$

依照同樣方法建立 $\mathfrak{S}_4$ 的表格，並求出 $\det(A)$。

<!-- eng start -->
Let

$$
A = \begin{bmatrix}
1 & 1 & 1 & 1 \\
1 & 2 & 4 & 8 \\
1 & 3 & 9 & 27 \\
1 & 4 & 16 & 64
\end{bmatrix}.
$$

Build the same table for $\mathfrak{S}_4$ and find $\det(A)$.
<!-- eng end -->

##### Exercise 4

令 $A$ 為一 $n\times n$ 矩陣。

<!-- eng start -->
Let $A$ be an $n\times n$ matrix.
<!-- eng end -->

##### Exercise 4(a)

已知 $n = 2$ 時 $\det(A)$ 為 $2$ 項相加減、
$n = 3$ 時 $\det(A)$ 為 $6$ 項相加減。
求對於一般的 $n$來說，
$\det(A)$ 的排列展開式有幾項相加減？

<!-- eng start -->
We know that the formula of $\det(A)$ has $2$ terms for $n = 2$ and $6$ terms for $n = 3$. How many terms are there in the formula of $\det(A)$ for general $n$?
<!-- eng end -->

##### Exercise 4(b)

在這些項中，
有幾項是要加的（$\sgn(\sigma) = 1$）、
有幾項是要減的（$\sgn(\sigma) = -1$）？

<!-- eng start -->
Among these terms, how many of them have positive signs ($\sgn(\sigma) = 1$), and how many of them have negative signs ($\sgn(\sigma) = -1$)?
<!-- eng end -->

##### Exercise 4(c)

在這些項中，有幾項有用到 $A$ 的 $1,1$-項？

<!-- eng start -->
Among these terms, how many of them have the $1,1$-entry of $A$ involved?
<!-- eng end -->

##### Exercise 5

利用排列展開式說明 $\det(A)$ 是一個以 $A$ 中各元素為變數的整係數多項式。
（因此如果 $A$ 是整數矩陣，則 $\det(A)$ 也是整數；
而如果 $A$ 是有理數，則 $\det(A)$ 也是有理數。
令一方面，這也表示 $\det(A)$ 對 $A$ 中的元素來說是連續的。）

<!-- eng start -->
Use the permutation expansion to show that $\det(A)$ is actually a multi-variate polynomial based on the entries of $A$.
(Therefore, $\det(A)$ is an integer if $A$ is an integer matrix, while $\det(A)$ is a rational number if $A$ is a rational number. Moreover, $\det(A)$ is continuous with respect to the entries of $A$.
<!-- eng end -->

##### Exercise 6

對以下 $n\times n$ 矩陣 $A$，
列出所有 $w_A(\sigma) \neq 0$ 的排列及其正號，
並藉此求出 $\det(A)$。

（這個方法在 $A$ 是稀疏矩陣的時候特別有效率。）

<!-- eng start -->
For each of the following $n\times n$ matrices $A$, list all permutations with $w_A(\sigma) \neq 0$ and their signs. Then use them to find $\det(A)$.
<!-- eng end -->

##### Exercise 6(a)

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

##### Exercise 6(b)

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

##### Exercise 6(c)

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