Determinant is well-defined
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 effective_permutations, illustrate_det
In this section, we will review our treatment on the definition and the properties of the determinant function.
In 405, we defined the determinants of elementary matrices and define
$$ \det(A) = \det(F_1) \cdots \det(F_k) $$if $A = F_1\cdots F_k$ for some elementary matrices,
and $\det(A) = 0$ if $A$ is not invertible.
This help us to find the value of $\det(A)$
but it is not certain whether this definition is well-defined since $A$ can be written as different products of elementary matrices.
Based on the definition, we realized that the determinant, if well-defined, must satisfies the following properties:
Thanks to the Laplace expansion, we noticed that $\det(A)$, again, if well-defined, must equal to the value
$$ \sum_{\sigma\in\mathfrak{S}_n}\sgn(\sigma) w(\sigma). $$We tentatively call this formula of the permutation expansion as $\det_p(A)$.
If we focus only on the definition of $\det_p(A)$, then it is obviously well-defined.
And it is known if $\det(A)$ is well-defined, meaning there is no internal violation of the four rules in its definition, then $\det(A) = \det_p(A)$.
Therefore, all we need to do is to make sure $\det_p(A)$ satisfies the four rules in the definition of $\det(A)$.
### code
set_random_seed(0)
print_ans = False
n = 6
b = 20
while True:
l = random_int_list(n^2 - b, 3) + [0]*b
shuffle(l)
A = matrix(n, l)
perms = effective_permutations(A)
if len(perms) >= 3 and len(perms) <= 8 and A.det() != 0:
break
B = copy(A)
B.swap_rows(0,1)
pretty_print(LatexExpr("A ="), A)
pretty_print(LatexExpr("B ="), B)
if print_ans:
print("elementary subgraphs of Gamma(A):")
illustrate_det(A)
print("elementary subgraphs of Gamma(B):")
illustrate_det(B)
print("Take one elementary subgraph H_A for A.")
print("If (1,i) and (2,j) are directed edges in H_A,")
print("then changing them to (1,j) and (2,i) will result in an elementary subgraph H_B for B.")
print("This builds up a bijection between the elementary subgraphs of Gamma(A) and Gamma(B).")
畫出 $\Gamma(A)$ 的所有基本子圖,並標上每條邊的權重。
Draw all elementary subgraphs of $\Gamma(A)$ and mark the weight on each edge.
畫出 $\Gamma(B)$ 的所有基本子圖,並標上每條邊的權重。
Draw all elementary subgraphs of $\Gamma(B)$ and mark the weight on each edge.
找一個 $\mathfrak{E}(\Gamma(A))$ 到 $\mathfrak{E}(\Gamma(B))$ 的一對一對應。
這個對應會把 $\mathfrak{E}(\Gamma(A))$ 對到 $\mathfrak{E}(\Gamma(B))$ 的一個權重一樣的基本子圖,
但是圈數差一,因此正負號會變號。
Find a bijection between $\mathfrak{E}(\Gamma(A))$ and $\mathfrak{E}(\Gamma(B))$ such that the corresponding elementary subgraphs have the same weight but their numbers of cycles are off by $1$, which flips their signs.
找出 $\Gamma(I_n)$ 中的基本子圖,
並說明 $\det_p(I_n) = 1$。
Find the elementary subgraphs of $\Gamma(I_n)$ and explain why $\det_p(I_n) = 1$.
令 $A$ 是一矩陣,
而 $B$ 是由 $A$ 矩陣將第 $i$ 列和第 $j$ 列交換得來,且 $i \neq j$。
令 $\mathfrak{E}_A = \mathfrak{E}(\Gamma(A))$ 且 $\mathfrak{E}_B = \mathfrak{E}(\Gamma(B))$。
找一個對射函數 $f: \mathfrak{E}_A \rightarrow \mathfrak{E}_B$ 使得
因此 $\det_p(B) = -\det_p(A)$。
Let $A$ be a matrix and $B$ the matrix obtained from $A$ by swapping the $i$-th and the $j$-th rows, where $i \neq j$. Let $\mathfrak{E}_A = \mathfrak{E}(\Gamma(A))$ and $\mathfrak{E}_B = \mathfrak{E}(\Gamma(B))$. Find a bjection $f: \mathfrak{E}_A \rightarrow \mathfrak{E}_B$ such that
Therefore, $\det_p(B) = -\det_p(A)$.
令 $A$ 是一矩陣,
而 $B$ 是由 $A$ 矩陣將第 $i$ 列乘上 $k$ 倍得來。
令 $\mathfrak{E}_A = \mathfrak{E}(\Gamma(A))$ 且 $\mathfrak{E}_B = \mathfrak{E}(\Gamma(B))$。
找一個對射函數 $f: \mathfrak{E}_A \rightarrow \mathfrak{E}_B$ 使得
因此 $\det_p(B) = k\cdot\det_p(A)$。
Let $A$ be a matrix and $B$ the matrix obtained from $A$ by rescaling the $i$-th by $k$. Let $\mathfrak{E}_A = \mathfrak{E}(\Gamma(A))$ and $\mathfrak{E}_B = \mathfrak{E}(\Gamma(B))$. Find a bjection $f: \mathfrak{E}_A \rightarrow \mathfrak{E}_B$ such that
Therefore, $\det_p(B) = k\cdot\det_p(A)$.
若 $A$ 中有一列是另一列的倍數,則 $\det_p(A) = 0$。
If a row of $A$ is the multiple of the other row, then $\det_p(A) = 0$.
令 $M$ 是一矩陣,且其第一列可以寫成兩向量相加 $\ba + \bb$。
將 $M$ 的第一列改為 $\ba$ 並稱之為矩陣 $A$。
將 $M$ 的第一列改為 $\bb$ 並稱之為矩陣 $B$。
令 $\mathfrak{E}_M = \mathfrak{E}(\Gamma(M))$、$\mathfrak{E}_A = \mathfrak{E}(\Gamma(A))$ 且 $\mathfrak{E}_B = \mathfrak{E}(\Gamma(B))$。
找兩個對射函數 $f_A: \mathfrak{E}_M \rightarrow \mathfrak{E}_A$ 及 $f_B: \mathfrak{E}_M \rightarrow \mathfrak{E}_B$ 使得
因此 $\det_p(M) = \det_p(A) + \det_p(B)$。
Let $M$ be a matrix whose first row has the form $\ba + \bb$. Replace the first row by $\ba$ and call the resulting matrix as $A$. Similarly, replace the first row by $\bb$ and call the resulting matrix as $B$. Let $\mathfrak{E}_M = \mathfrak{E}(\Gamma(M))$、$\mathfrak{E}_A = \mathfrak{E}(\Gamma(A))$ and $\mathfrak{E}_B = \mathfrak{E}(\Gamma(B))$. Find two bijections $f_A: \mathfrak{E}_M \rightarrow \mathfrak{E}_A$ and $f_B: \mathfrak{E}_M \rightarrow \mathfrak{E}_B$ such that
Therefore, $\det_p(M) = \det_p(A) + \det_p(B)$.
令 $A$ 是一矩陣,
而 $B$ 是由 $A$ 矩陣將第 $j$ 列乘上 $k$ 倍後加到第 $i$ 列得來,且 $i \neq j$。
利用前兩題的性質說明 $\det_p(B) = \det_p(A)$。
Let $A$ be a matrix and $B$ the matrix obtained from $A$ by adding $k$ times the $j$-th row to the $i$-th row, where $i \neq j$. Use the previous two exercises to show that $\det_p(B) = \det_p(A)$.