同構 - HackMD

# 同構 ![Creative Commons License](https://i.creativecommons.org/l/by/4.0/88x31.png) This work by Jephian Lin is licensed under a [Creative Commons Attribution 4.0 International License](http://creativecommons.org/licenses/by/4.0/). {%hackmd 5xqeIJ7VRCGBfLtfMi0_IQ %} ```python from linspace import random_nvspace ``` ## Main idea Let $V$ and $U$ be two vector space. An **isomorphism** from $V$ to $U$ is a bijective linear function from $V$ to $U$. If there is an isomorphism from $V$ to $U$, then $V$ is **isomorphic** to $U$. Suppose $f$ is an isomorphism from $V$ to $U$. Since $f$ a bijective function, the inverse $f^{-1}$ of $f$ exists. One may show that $f^{-1}$ is also linear, so $V$ is isomorphic to $U$ if and only if $U$ is isomorphic to $V$. Suppose $f$ is an isomorphism from $V$ to $U$. If $\alpha$ is a basis of $V$, then $f(\alpha)$ is a basis of $U$, so $\dim(V) = \dim(U)$. On the other hand, suppose $\dim(V) = \dim(U)$. If $\alpha$ is a basis of $V$ and $\beta$ is a basis of $U$, then there is an isomorphism sending $\alpha$ to $\beta$, so $V$ and $U$ is isomorphic. In summary, two finite-dimensional vector spaces are isomorphic if and only if they have the same dimension. Therefore, all finite-dimensional vector spaces can be partitioned by isomorphism, and the partition is the same as the partition by the dimension. ## Side stories - classification of isomorphic vector spaces - equivalence relation ## Experiments ##### Exercise 1 執行以下程式碼。判斷該向量空間的維度、並寫出一組基底。 ```python ### code set_random_seed(0) print_ans = False d = choice(range(21)) V = random_nvspace(d) print(V) if print_ans: print("dim =", V.dim) ``` :::warning - [x] 題目給的資訊要貼過來排好 - [x] seed(0) --> `seed(0)` - [x] $dim = 3$ --> 其維度為 $3$， ::: Ans：當 `seed(0)` 時，題目給的向量空間為： The vector space of all 3 x 3 skew-symmetric matrices. 因此其維度為 $3$，基底為： $$\alpha = \left\{\left( \begin{array}{c} 1 \\ 0 \\ 0 \\ \end{array} \right), \left( \begin{array}{c} 0 \\ 1 \\ 0 \\ \end{array} \right), \left( \begin{array}{c} 0 \\ 0 \\ 1 \\ \end{array} \right)\right\}. $$ ## Exercises ##### Exercise 2 令 $V = \operatorname{span}\{(1,1,1)\}^\perp$。證明 $V$ 和 $\mathbb{R}^2$ 同構。 :::warning 請用定義證明 ::: **Ans:** 若 $V$ 和 $\mathbb{R}^2$ 之間存在 isomorphism，則 $V$ 和 $\mathbb{R}^2$ 之間為 isomophic。我們知道 $$\begin{aligned} V &= \{(x, y, z) : x + y + z = 0\} \\ &= \{(x, y, -x -y) : x, y\in\mathbb{R}\}. \end{aligned} $$ 考慮函數 $f: V \rightarrow \mathbb{R}^2$ 定義為 $f(x,y, -x-y) = (x,y)$。 **Claim:** $f$ 線性。我們需要證明對於 ${\bf v}, {\bf v}' \in V$, $k \in \mathbb{R}$ 以下等式成立： 1. $f({\bf v}) + f({\bf v}') = f({\bf v} + {\bf v}')$ 2. $f(k{\bf v}) = kf({\bf v})$ 方便起見，我們統一定義 $x, y, x', y' \in \mathbb{R}$ 使得 ${\bf v} = (x, y, -x-y), {\bf v}' = (x', y', -x'-y')$。 1. $$ \begin{aligned} f(\bv) + f(\bv') &= (x,y) + (x', y') \\ &=(x+x', y+y')\\ &=f(\bv + \bv') \end{aligned} $$ 2. $$ \begin{aligned} f(k\bv) &= (kx,ky)\\ &=k(x, y)\\ &=kf(\bv) \end{aligned} $$ 因此 $f$ 線性。 **Claim:** $f$ 是嵌射。 Suppose there are two different vectors $\bv_1, \bv_2 \in V$，$\bv_1 = (x_1, y_1, -x_1-y_1)$, $\bv_2 = (x_2, y_2, -x_2-y_2)$, $(x_1 \neq x_2$, $y_1 \neq y_2)$. Then $f(\bv_1) = (x_1, y_1)$，$f(\bv_2) = (x_2, y_2)$ should be two different vectors in $\mathbb{R}^2$ as well. Therefore, $f: V \rightarrow \mathbb{R}^2$ is injective. **Claim:** $f$ 是映射。設 $\bx = (x,y) \in \mathbb{R}^2$. 則我們可以製造 $p = (x, y, -x-y)$ 使得 $f(p) = \bx$。所以 $f$ 是映射.  ##### Exercise 3 證明 $\mathcal{P}_d$ 和 $\mathbb{R}^{d+1}$ 同構。 :::warning - [x] $e_1$ --> $\be_1$ 等等 - [x] Suppose that $\mathcal{P}_d$ is isomorphic to $\mathbb{R}^{d+1}$ and that $f : \mathcal{P}_d \rightarrow \mathbb{R}^{d+1}$ is an isomorphism from $\mathcal{P}_d$ to $\mathbb{R}^{d+1}$. --> Let $f : \mathcal{P}_d \rightarrow $\mathbb{R}^{d+1}$ be a function defined as $$ f(c_1 + c_2x + \ldots + c_{d+1}x^d) = c_1e_1 + c_2e_2 + \ldots + c_{d+1}e_{d+1} = \begin{bmatrix} c_1 \\ \vdots \\ c_{d+1} \end{bmatrix}. $$ We will show $f$ is an isomorphism. - [x] Claim 1 裡大型數學式用 `aligned` 排整齊 ::: **Ans:** Let $\alpha = \{1, x, \ldots, x^d\}$ and $\beta = \{\be_1, \be_2, \ldots, \be_{d+1}\}$ be bases for $\mathcal{P}_d$ and $\mathbb{R}^{d+1}$. Let $f : \mathcal{P}_d \rightarrow \mathbb{R}^{d+1}$ be a function defined as $$ f(c_1 + c_2x + \ldots + c_{d+1}x^d) = c_1\be_1 + c_2\be_2 + \ldots + c_{d+1}\be_{d+1} = \begin{bmatrix} c_1 \\ \vdots \\ c_{d+1} \end{bmatrix}. $$ We will show $f$ is an isomorphism. **1. Claim:** $f: U\rightarrow V$ is linear fuction. That is, $$\begin{aligned} f({\bf u}_1 + {\bf u}_2) &= f({\bf u}_1) + f({\bf u}_2) \\ f(k{\bf u}) &= kf({\bf u}) \\ \end{aligned} $$ for any vectors ${\bf u}, {\bf u}_1, {\bf u}_2\in U$ and scalar $k\in\mathbb{R}$. Let ${\bf u}_1 = \{c_1 + c_2x + \ldots + c_{d+1}x^d\}$, ${\bf u}_2 = \{k_1 + k_2x + \ldots + k_{d+1}x^d\}$. Then $$\begin{aligned} & \mathrel{\phantom{=}}f(c_1 + c_2x + \ldots + c_{d+1}x^{d} + k_1 + k_2x + \ldots + k_{d+1}x^{d}) \\ &= f((c_1+k_1) + (c_2+k_2)x + \ldots + (c_{d+1}+k_{d+1})x^{d}) \\ &= \begin{pmatrix} c_1 + k_1\\ c_2 + k_2\\ \vdots \\ c_{d+1} + k_{d+1} \end{pmatrix} = \begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_{d+1} \\ \end{pmatrix} + \begin{pmatrix} k_1 \\ k_2 \\ \vdots \\ k_{d+1} \\ \end{pmatrix} \\ &= f(c_1 + c_2x + \ldots + c_{d+1}x^{d}) + f(k_1 + k_2x + \ldots + k_{d+1}x^{d}). \end{aligned} $$ On the other hand, $$\begin{aligned} f(k{\bf u}) &= f(k(c_1 + c_2x + \ldots + c_{d+1}x^{d})) \\ &= f(kc_1 + kc_2x + \ldots + kc_{d+1}x^{d}) \\ &= {\begin{pmatrix} kc_1 \\ kc_2 \\ \vdots \\ kc_{d+1} \end{pmatrix}} = k\begin{pmatrix} c_1 \\ c_2 \\ \vdots \\ c_{d+1} \\ \end{pmatrix} \\ &= kf({\bf u}). \end{aligned} $$ **2. Claim:** $f$ is surjective. Let $\by = (c_1,\ldots, c_{d+1}) \in \mathbb{R}^{d+1}$. Then pick $p = c_1 + c_2x + \cdots + c_{d+1}x^d$. Thus, we have $f(p) = \by$. Therefore, $f$ is surjective.  **3. Claim:** $f$ is injective. Equivalently, $\operatorname{ker}(f) = \{{\bf 0}\}$. Let $p = c_1 + c_2x + \ldots + c_{d+1}x^d$. Suppose $f(p) = \bzero$. Since $f(p) = (c_1,\ldots, c_{d+1})$, $f(p) = \bzero$ implies $p = 0$. Therefore, $\ker(f) = \{0\}$ and $f$ is injective.  Hence, $f$ is surjective, injective and linear function. So $f$ is an isomorphism, and $\mathcal{P}_d$ and $\mathbb{R}^{d+1}$ are isomorphic. ##### Exercise 4 證明 $\mathcal{M}_{m,n}$ 和 $\mathbb{R}^{mn}$ 同構。 :::warning - [x] $f({\bf M}) = (c_1, c_2, \ldots, c_{mn}) = c_1r_1 + c_2r_2 + \ldots + c_{mn}r_{mn}$ <-- $r$ 要粗體，後面還一次 - [x] 2-1 大型數式排版 ::: $Ans$ 設 $\alpha = \begin{Bmatrix} {\bf m}_{11}, &\ldots, & {\bf m}_{1j}, &\ldots, & {\bf m}_{1n},\\ \vdots &\ddots & \ddots &\ddots & \vdots\\ {\bf m}_{i1}, &\ddots, & {\bf m}_{ij}, &\ddots, & {\bf m}_{in},\\ \vdots &\ddots & \ddots &\ddots & \vdots\\ {\bf m}_{m1}, &\ldots, & {\bf m}_{mj}, &\ldots, & {\bf m}_{mn} \end{Bmatrix}$ 為 $\mathcal{M}_{m,n}$ 之一組基底，其中 ${\bf m}_{mn}$ 代表一 $m \times n$ 矩陣中除第 $(i,j)$ 項為 $1$ 外其餘皆為 $0$ ，與 $\beta = \{{\bf r}_1, {\bf r}_2, \ldots, {\bf r}_{mn}\}$ 為 $\mathbb{R}^{mn}$ 之標準基底。則不難發現我們可以找到一函數 $f: \mathcal{M}_{m,n} \mapsto \mathbb{R}^{mn}$ 使 $f({\bf M})$ 之第 $(i-1) \cdot n + j$ 個分量為一給定 ${\bf M} \in \mathcal{M}_{m,n}$ 的第 $(i,j)$ 項之值，即當 ${\bf M} = c_1 \cdot {\bf m}_{11} + \ldots + c_n \cdot {\bf m}_{1n} + c_{n+1} \cdot {\bf m}_{21} + \ldots + c_{mn} \cdot {\bf m}_{mn}$ 時 $f({\bf M}) = (c_1, c_2, \ldots, c_{mn}) = c_1{\bf r}_1 + c_2{\bf r}_2 + \ldots + c_{mn}{\bf r}_{mn}$ 。\ \ 1\. 證明其為對射函數由於我們也可以很容易得找到 $f^{-1}$ ，即當 ${\bf v} \in \mathbb{R}^{mn} = c_1{\bf r}_1 + c_2{\bf r}_2 + \ldots + c_{mn}{\bf r}_{mn}$ 時 $f^{-1}({\bf v}) = c_1 \cdot {\bf m}_{11} + \ldots + c_n \cdot {\bf m}_{1n} + c_{n+1} \cdot {\bf m}_{21} + \ldots + c_{mn} \cdot {\bf m}_{mn}$ 。因此 **$f$ 為一對射函數**。 2\. 證明其為線性函數 2-1. 對於所有 ${\bf M}, {\bf M}^{\prime} \in \mathcal{M}_{m,n}$ 都滿足 $f({\bf M} + {\bf M}^{\prime}) = f({\bf M}) + f({\bf M}^{\prime})$ 由於 $\alpha$ 為 $\mathcal{M}_{m,n}$ 之一組基底，我們可以將 ${\bf M}, {\bf M}^{\prime}$ 表示成： \begin{align} {\bf M} = c_1 \cdot {\bf m}_{11} + \ldots + c_n \cdot {\bf m}_{1n} + c_{n+1} \cdot {\bf m}_{21} + \ldots + c_{mn} \cdot {\bf m}_{mn},\\ {\bf M}^{\prime} = c^{\prime}_1 \cdot {\bf m}_{11} + \ldots + c^{\prime}_n \cdot {\bf m}_{1n} + c^{\prime}_{n+1} \cdot {\bf m}_{21} + \ldots + c^{\prime}_{mn} \cdot {\bf m}_{mn}. \end{align} 則 $$\begin{aligned} f({\bf M} + {\bf M}^{\prime}) &= (c_1 + c^{\prime}_1, c_2+ c^{\prime}_2, \ldots, c_{mn}+c^{\prime}_{mn}) \\ &= (c_1, c_2, \ldots, c_{mn}) + (c^{\prime}_1, c^{\prime}_2, \ldots, c^{\prime}_{mn})\\ &=f({\bf M})+f({\bf M}^{\prime}). \end{aligned} $$ 2-2. 對於所有 ${\bf M} \in \mathcal{M}_{m,n}, k \in \mathbb{R}$ 都滿足 $kf({\bf M}) = f(k{\bf M})$ 由於 $\alpha$ 為 $\mathcal{M}_{m,n}$ 之一組基底，我們可以將 ${\bf M}$ 表示成： $${\bf M} = c_1 \cdot {\bf m}_{11} + \ldots + c_n \cdot {\bf m}_{1n} + c_{n+1} \cdot {\bf m}_{21} + \ldots + c_{mn} \cdot {\bf m}_{mn}. $$ 則 \begin{aligned} kf({\bf M}) &= k(c_1, c_2, \ldots, c_{mn}) \\ &= (kc_1, kc_2, \ldots, kc_{mn}) \\ &= f(k{\bf M})。 \end{aligned} 因此 **$f$ 為一線性函數**。由於 $f: \mathcal{M}_{m,n} \mapsto \mathbb{R}^{mn}$ 為一對射線性函數，因此 $\mathcal{M}_{m,n}$ 和 $\mathbb{R}^{mn}$ 同構。 ##### Exercise 5 令 $V$ 和 $U$ 為兩有限維度的向量空間。依照以下步驟證明兩敘述等價： 1. $V$ 和 $U$ 同構。 2. $V$ 和 $U$ 的維度相同。 ##### Exercise 5(a) 證明若 $f: V\rightarrow U$ 是一個對射且 $\alpha$ 是 $V$ 的一組基底﹐ 則 $f(\alpha)$ 是 $U$ 的一組基底。因此 $\dim(V) = \dim(U)$。 :::warning 這題要證明 $f(\alpha)$ 是獨立的而且 $\vspan(f(\alpha)) = U$。 ::: **Ans:** 我們要證明 $f(\alpha)$ 是 $U$ 的一組基底。 **Claim:** $f(\alpha)$ 線性獨立。因為 $f$ 是嵌射，所以當 $\alpha$ 獨立時 $f(\alpha)$ 也是獨立。（參考 [302-5a](https://hackmd.io/qwIw35kFT1OyWO2yJGjLfg)。） **Claim:** $f(\alpha)$ 可以生成出 $U$。因為 $f$ 是映射，且 $\vspan(\alpha) = V$，所以 $\vspan(f(\alpha)) = U$。（參考 [302-5b](https://hackmd.io/qwIw35kFT1OyWO2yJGjLfg)。）  ##### Exercise 5(b) 證明若 $\dim(V) = \dim(U)$、 $\alpha = \{ {\bf v}_1, \ldots, {\bf v}_n \}$ 為 $V$ 的一組基底、 $\beta = \{ {\bf u}_1, \ldots, {\bf u}_n \}$ 為 $U$ 的一組基底﹐ 則存在一個線性函數符合 $$\begin{array}{rcl} f : V & \rightarrow & U \\ {\bf v}_1 & \mapsto & {\bf u}_1 \\ & \vdots & \\ {\bf v}_n & \mapsto & {\bf u}_n \\ \end{array} $$ 且 $f$ 是對射。 :::warning 這題要把 $f$ 定義出來，並證明它是 bijection。 ::: $Ans$ 我們可以定義 $f: V\rightarrow U$ 使得 $$f(c_1\bv_1 + \cdots + c_n\bv_n) = c_1\bu_1 + \cdots + c_n\bu_n. $$ 根據 [302-6](https://hackmd.io/qwIw35kFT1OyWO2yJGjLfg)，$f$ 是一個定義完善的線性函數。 **Claim:** $f$ 是嵌射。假設 $f(c_1\bv_1 + \cdots + c_n\bv_n) = c_1\bu_1 + \cdots + c_n\bu_n = \bzero$。因為 $\beta$ 是線性獨立，所以 $c_1 = \cdots = c_n = 0$。因此 $c_1\bv_1 + \cdots + c_n\bv_n = \bzero$，而 $f$ 是嵌射。 **Claim:** $f$ 是映射。由於 $c_i$ 可以是任意的數，觀察 $f$ 可發現 $\range(f)$ 裡的元素都是 $\beta$ 的線性組合。因為 $\beta$ 可以生成整個 $U$，所以 $\range(f) = U$。  ##### Exercise 6 證明向量空間的同構是一個等價關係。 :::warning 這題我直接改過了。 ::: Ans: To prove that isomorphism is an equivalence relation, we need to verify that it is reflexive, symmetric, and transitive respectively. First of all, let the set $X$ contain all vector spaces. **Reflexivity:** Let $V$ be a vector space. Define the identity function $f:V\rightarrow V$ as $f(\bx) = \bx$. Then $f$ is an isomorphism and $V$ is isomorphic to $V$ itself.  Therefore, each vector space in $X$ is isomorphic to itself, and isomorphism is reflexive. **Symmetry:** Let $X$ and $Y$ be two vector spaces such that $X$ is isomorphic to $Y$. By definition, there is an isomorphism $f: X \rightarrow Y$. Since $f$ is an isomorphism and is bijective, $f^{-1}:Y\rightarrow X$ exists and is bijective. One may check that $f^{-1}$ is also linear, so $f^{-1}$ is an isomorphism and $Y$ is isomorhic to $X$.  Therefore, isomorphism is symmetric. **Transitivity:** Suppose $V$ is isomorphic to $U$ and $U$ is isomorphic to $W$. Then there are isomorphisms $f: V\rightarrow U$ and $g: U\rightarrow W$. Thus, $g\circ f: V\rightarrow W$ is also an isomorphism, and $V$ is isomorphic to $W$.  Therefore, if $V$ is isomorphic to $U$ and $U$ is isomorphic to $W$ then $V$ is isomorphic to $W$. It's proved that isomorphism is transitive. **Conclusion:** Since isomorphism is reflexive, symmetric, and transitive, we can conclude that it is an equivalence relation. Q.E.D :::info 目前分數 5.5 :::

Syntax	Example	Reference
# Header	Header	基本排版
- Unordered List	Unordered List
1. Ordered List	Ordered List
- [ ] Todo List	Todo List
> Blockquote	Blockquote
Bold font	Bold font
Italics font	Italics font
~~Strikethrough~~	~~Strikethrough~~
19^th^	19^th
H~2~O	H₂O
++Inserted text++	Inserted text
==Marked text==	Marked text
[link text](https:// "title")	Link
![image alt](https:// "title")	Image
`Code`	`Code`	在筆記中貼入程式碼
```javascript var i = 0; ```	`var i = 0;`
:smile:		Emoji list
{%youtube youtube_id %}	Externals
$L^aT_eX$	L^aT_eX
:::info This is a alert area. :::	This is a alert area.