同構

This work by Jephian Lin is licensed under a Creative Commons Attribution 4.0 International License.

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

執行以下程式碼。
判斷該向量空間的維度、並寫出一組基底。

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

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\) 同構。

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')\)。

\[ \begin{aligned} f(\bv) + f(\bv') &= (x,y) + (x', y') \\ &=(x+x', y+y')\\ &=f(\bv + \bv') \end{aligned} \]

\[ \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}\) 同構。

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}\) 同構。

\(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)\)。

Ans:
我們要證明 \(f(\alpha)\) 是 \(U\) 的一組基底。

Claim: \(f(\alpha)\) 線性獨立。
因為 \(f\) 是嵌射，所以當 \(\alpha\) 獨立時 \(f(\alpha)\) 也是獨立。
（參考 302-5a。）

Claim: \(f(\alpha)\) 可以生成出 \(U\)。
因為 \(f\) 是映射，且 \(\vspan(\alpha) = V\)，所以 \(\vspan(f(\alpha)) = U\)。
（參考 302-5b。）

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\) 是對射。

\(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，\(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

證明向量空間的同構是一個等價關係。

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