自然数1～aと1～bの組と自然数1～abの全単射の計算

概要

$a, b$を正整数とする。全単射$\{ 1, \cdots, a\} \crossproduct \{1, \cdots , b \} \rightarrow \{1 , \cdots , a b\}$を作ります。割り算するだけで難しくはないですが、きちんと書こうとすると微妙なズレが手間です。特に逆関数の計算手順を明示しておきたい。そのためのメモです

0からの場合

$\{m \in \mathbb{N} \vert 0 \leq m < a\}\ \crossproduct \{n \in \mathbb{N} \vert 0 \leq n < b \} \rightarrow \{x \in \mathbb{N} \vert 0 \leq x < ab \}$は$(m, n) \mapsto m b + n $でよい。逆関数は$b$で割り算して商と余りを取ればいいはず。

1からの場合

とりあえず順番に書いてみる。こういう対応関係をつくる。第二成分を先に動かしています。

\begin{eqnarray} (1, 1) & \mapsto & 1 &=& 1 b + (1-b)\\ (1, 2) & \mapsto & 2 &=& 1 b + (2-b)\\ \vdots \\ (1, b) & \mapsto & b &=& 1b + (b-b)\\ (2, 1) & \mapsto & b + 1 &=& 2b + (1-b)\\ (2, 2) & \mapsto & b + 2 &=& 2b + (2-b)\\ \vdots \\ (2, b) & \mapsto & b + b &=& 2b + (b-b)\\ (3, 1) & \mapsto & 2b + 1 &=& 3b + (1-b)\\ (3, 2) & \mapsto & 2b + 2 &=& 3b + (1-b)\\ \vdots \\ (a, b) & \mapsto & ab + 0 &=& (a-1)b + b\\ \end{eqnarray}

このことから求めたい写像は$(m, n) \mapsto mb + (n-b)$だと思われる。これが全単射を示そう。

証明

単射

商集合$\mathbb{Z} / b \mathbb{Z} $の代表元を$-(b-1),\cdots ,0$でとればよい。で納得するならそれでよい。全射性のヒントにもなるので計算してみよう。$x = m b + (n - b) = m' b + (n'-b)$とする。よって両辺に$-1$をかけて、$-x = (-m)b + (b -n) = (-m')b + (b - n')$を得る。
さて剰余$b-n$の大きさを見ると、$0 < n \leq b$より$0 \leq b-n < b$である。整数の割り算の一意性から単射と言えた。

全射

定義域と値域の濃度を計算すると、一致していることは簡単にわかる。またどちらも有限集合。よって単射性より全単射、特に全射。でもいいが。今回は作り方みたい。ここで単射性を示すときにみた方法を使おう

$x \in \mathbb{N}$を $1 \leq x \leq ab$としよう。$x$を$b$で割り算する：$-x = \mu b + \nu$ と書ける。$m := -\mu , n := b - \nu $と置く。

\begin{eqnarray} m b + (b-n) &=& -\mu b +( (b-\nu ) - b)\\ &=& -(\mu b + \nu)\\ &=& x \end{eqnarray}
$m$と$n$の範囲の確認ついては省略する。

逆関数

$1 < x \leq ab$に対して$x$の逆写像の値を計算する手続きは次のようになる。

$-x$を$b$で割り算する。商と余りをを$\mu , \nu$とする。
- $-x = \mu b + \nu$ と表示
$m := -\mu $とする
$n := b - \nu$ とする

応用

前提

行列のテンソル積について既知とする。

問題

$A$を$r$次実行列とする。$E_s$を$s$次の単位行列とする。テンソル積$A \otimes E_s = (c_{\lambda \mu})$を計算する。

$E_s$の$(i', j')$成分はクロネッカーのデルタを用いて$\delta _{i'j'}$とかける。前節までの記号を使うと今は$a=r, b=s$となっている。先の逆関数を$g$としよう。$(u, u') = g(\lambda), (v, v') = g(\mu)$とする。$c_{\lambda \mu} = a_{mn} \delta_{m'n'}$となる。