415-Determinant-is-well-defined

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

In [ ]:

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:

$\det(A\trans) = \det(A)$.
$\det(AB) = \det(A)\det(B)$.
distributive law on any row and any column.
Laplace expansion along any row and any column.

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)$.

Side stories¶

summary

Exercise 1¶

執行以下程式碼。

Run the code below.

In [ ]:

### 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).")

Exercise 1(a)¶

畫出 $\Gamma(A)$ 的所有基本子圖，並標上每條邊的權重。

Draw all elementary subgraphs of $\Gamma(A)$ and mark the weight on each edge.

Exercise 1(b)¶

畫出 $\Gamma(B)$ 的所有基本子圖，並標上每條邊的權重。

Draw all elementary subgraphs of $\Gamma(B)$ and mark the weight on each edge.

Exercise 1(c)¶

找一個 $\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.

Exercise 2¶

找出 $\Gamma(I_n)$ 中的基本子圖，
並說明 $\det_p(I_n) = 1$。

Find the elementary subgraphs of $\Gamma(I_n)$ and explain why $\det_p(I_n) = 1$.

Exercise 3¶

令 $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$ 使得

$w(f(H)) = w(H)$、
$|c(f(H)) - c(H)|$、且
$\sgn(f(H)) = - \sgn(H)$。

因此 $\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

$w(f(H)) = w(H)$,
$|c(f(H)) - c(H)|$, and
$\sgn(f(H)) = - \sgn(H)$.

Therefore, $\det_p(B) = -\det_p(A)$.

Exercise 4¶

令 $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$ 使得

$w(f(H)) = k\cdot w(H)$、
$c(f(H)) = c(H)$、且
$\sgn(f(H)) = \sgn(H)$。

因此 $\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

$w(f(H)) = k\cdot w(H)$,
$c(f(H)) = c(H)$, and
$\sgn(f(H)) = \sgn(H)$.

Therefore, $\det_p(B) = k\cdot\det_p(A)$.

Exercise 5¶

藉由前兩題，說明以下性質。

Based on the previous two exercises, prove the following properties.

Exercise 5(a)¶

若 $A$ 中有兩列相同，則 $\det_p(A) = 0$。

If $A$ has two rows in common, then $\det_p(A) = 0$.

Exercise 5(b)¶

若 $A$ 中有一列是另一列的倍數，則 $\det_p(A) = 0$。

If a row of $A$ is the multiple of the other row, then $\det_p(A) = 0$.

Exercise 6¶

令 $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$ 使得

$w(f_A(H)) + w(f_B(H)) = w(H)$、
$c(f_A(H)) = c(H)$ 及 $c(f_B(H)) = c(H)$、且
$\sgn(f(H)) = \sgn(H)$ 及 $\sgn(f(H)) = \sgn(H)$。

因此 $\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

$w(f_A(H)) + w(f_B(H)) = w(H)$,
$c(f_A(H)) = c(H)$ and $c(f_B(H)) = c(H)$, and
$\sgn(f(H)) = \sgn(H)$ 及 $\sgn(f(H)) = \sgn(H)$.

Therefore, $\det_p(M) = \det_p(A) + \det_p(B)$.

Exercise 7¶

令 $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)$.

行列式值是定義完善的¶

Main idea¶