自然数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)$だと思われる。これが全単射を示そう。

証明

逆関数

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

1. $-x$を$b$で割り算する。商と余りをを$\mu , \nu$とする。
   • $-x = \mu b + \nu$ と表示
2. $m := -\mu $とする
3. $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'}$となる。

いくつかの計算

メモ

• 余りを$0, \cdots , s-1$でなく、$1, \cdots s$にして割り算を実行すれば作れないかと思うが、商も$0$になってほしくないためそれは合致しない。
• 適切に商と余りを1だけずらせばよいはずですが、場合分けで書くと計算がちょっと手間です。その部分は割り算に全てお任せしたい。