Permutation expansion
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 lingeo import random_int_list
from gnm import random_permutation
One may inductively apply the Laplace expansion to any given matrix.
For example,
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
When the matrix $A$ is clear from the context, we often write $w(\sigma) = w_A(\sigma)$.
Let $A = \begin{bmatrix} a_{ij} \end{bmatrix}$ be an $n\times n$ matrix.
Then
### 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))
令
$$ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix}. $$利用拉普拉斯展開,將 $\det(A)$ 寫成 $6$ 個矩陣的行列式值和,
其中每個矩陣的每行每列都至多只有一個非零項。
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.
令
$$ 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$。
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.
令
$$ A = \begin{bmatrix} 1 & 1 & 1 \\ 1 & 2 & 4 \\ 1 & 3 & 9 \end{bmatrix}. $$依照同樣方法建立 $\mathfrak{S}_3$ 的表格,並求出 $\det(A)$。
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)$.
令
$$ 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)$。
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)$.
已知 $n = 2$ 時 $\det(A)$ 為 $2$ 項相加減、
$n = 3$ 時 $\det(A)$ 為 $6$ 項相加減。
求對於一般的 $n$來說,
$\det(A)$ 的排列展開式有幾項相加減?
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$?
在這些項中,
有幾項是要加的($\sgn(\sigma) = 1$)、
有幾項是要減的($\sgn(\sigma) = -1$)?
Among these terms, how many of them have positive signs ($\sgn(\sigma) = 1$), and how many of them have negative signs ($\sgn(\sigma) = -1$)?
在這些項中,有幾項有用到 $A$ 的 $1,1$-項?
Among these terms, how many of them have the $1,1$-entry of $A$ involved?
利用排列展開式說明 $\det(A)$ 是一個以 $A$ 中各元素為變數的整係數多項式。
(因此如果 $A$ 是整數矩陣,則 $\det(A)$ 也是整數;
而如果 $A$ 是有理數,則 $\det(A)$ 也是有理數。
令一方面,這也表示 $\det(A)$ 對 $A$ 中的元素來說是連續的。)
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$.
對以下 $n\times n$ 矩陣 $A$,
列出所有 $w_A(\sigma) \neq 0$ 的排列及其正號,
並藉此求出 $\det(A)$。
(這個方法在 $A$ 是稀疏矩陣的時候特別有效率。)
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)$.