応用線形代数演習 I ( 塩田教官 ) No.6

テーマ : 写像の全射性・単射性、置換の定義と計算法

—— 次回行列式を定義する為に、今回は置換を学ぶ。 ——

【全射・単射・全単射】写像 f : X ⟶ Y は、

• ∀ y ∈ Y に対し「 y = f(x) となる x ∈ X が必ず存在する」とき、全射 (ぜんしゃ) であると言う。

• ∀ y ∈ Y に対し「 y = f(x) となる x ∈ X が高々ひとつしか存在しない」とき、単射 (たんしゃ) であると言う。

• 全射であり単射でもある写像を全単射または一対一写像と言う。

⋄ 全単射には逆写像が存在する。

【証明の基本パターン】 • 全射であること : ∀ y ∈ Y に対して y = f(x) を満たす x ∈ X

を提示する。

• 全射でないこと : 「 ∀ x ∈ X に対して y ≠ f(x) 」となる y ∈ Y の例を挙げる。 • 単射であること : 式「 f(a) = f(b) 」から式「 a = b 」を導く。

• 単射でないこと : 「 a ≠ b かつ f(a) = f(b) 」なる a, b ∈ X の例を挙げる。

【59】任意の集合 X に対して、恒等写像 f : X → X; f(x) = x は全単射であることを示せ。

【60〜62】整数全体の集合を Z と表す。次の式で与えられる写像 f : Z → Z について、それぞれ全射であるか否か、単射であるか否か理由を付けて述べよ。【60】f(x) = x^{3} 【61】 f(x) = 1 − x 【62】f(x) = ( \frac{x}{2} を越えない最大の整数)

【63】X が有限集合ならば、写像 f : X → X の全射性と単射性は同値であることを示せ。

【64〜69】以下、ふたつの写像 f : X → Y と g : Y → Z を考える。【64】f と g が共に全射ならば合成写像 g ∘ f : X → Z も全射であることを示せ。【65】f と g が共に単射ならば合成写像 g ∘ f も単射であることを示せ。【66】合成写像 g ∘ f が全射ならば g は全射であることを示せ。【67】合成写像 g ∘ f が単射ならば f は単射であることを示せ。【68】g ∘ f は全射だが f は全射でない様な X, Y, Z, f, g の例を作れ。【69】g ∘ f は単射だが g は単射でない様な X, Y, Z, f, g の例を作れ。【注意】上の問題より次のことがわかる。

(1) f と g が共に全単射ならば合成写像 g ∘ f も全単射である。

(2) ふたつの写像 f : X ⟶ Y, g : Y ⟶ X があって、合成写像 g ∘ f : X → X と f ∘ g : Y → Y が共に全単射ならば f, g はいずれも全単射である。

【置換】 • 集合 M = { 1, 2, ⋯, n } から M への全単射を n 文字の置換と呼ぶ。 • n 文字の置換全体の集合を S_{n} と書き、 n 次対称群と呼ぶ。

• σ ∈ S_{n} が σ(1) = a_{1}, σ(2) = a_{2}, ⋯, σ(n) = a_{n} なる置換のとき、

σ = ( \begin{matrix}1 & 2 & ⋯ & n \\ a_{1} & a_{2} & ⋯ & a_{n} \end{matrix} )

と表す。 ( 行列の記号とまぎわらしいが、置換は置換と思って計算する。 )

• 列の並べ方は自由に変えて良い : ( \begin{matrix}1 & 2 & 3 \\ 2 & 3 & 1 \end{matrix} ) = ( \begin{matrix}1 & 3 & 2 \\ 2 & 1 & 3 \end{matrix} ) 等々。

• a_{1} ↦ a_{2} ↦ ⋯ ↦ a_{m} ↦ a_{1} なる置換 σ を ( 長さ m の ) 巡回置換と言い、簡単に σ = ( a_{1} a_{2} ⋯ a_{m}) と表す。

• k ↦ ℓ ↦ k なる置換 ( 2 文字のみ入れ換える置換 ) σ を互換と言い、簡単に σ = ( k ℓ) と表す。

• 写像の合成により置換の積を定義する : στ := σ ∘ τ.

この積により、恒等写像 1_{M} を単位元として S_{n} は群を成す。 ⋄ 任意の置換は幾つかの互換の積として表すことができる。 ⋄ σ ∈ S_{n} を互換の積として表すとき、互換の個数 s の偶奇は表し方に依らない。

このとき sgn(σ) := (−1)^{s} を σ の符号と言う。

• sgn(σ) = 1 なる置換を偶置換、 sgn(σ) = −1 なる置換を奇置換と言う。 ⋄ sgn(1_{M}) = 1, sgn(στ) = sgn(σ)sgn(τ), sgn(σ) = sgn(σ^{−1}) が成り立つ。

【70】巡回置換 σ = ( 1 2 ⋯ n ) について σ^{n} = 1_{M} を示せ。

【71】巡回置換 σ = ( 1 2 ⋯ n ) の符号を計算せよ。

【72】置換 σ = ( \begin{matrix}1 & 2 & ⋯ & n \\ n & n−1 & ⋯ & 1 \end{matrix} ) の符号を計算せよ。

【73】n ≧ 2 のとき n 文字の偶置換、奇置換はそれぞれ\frac{n!}{2} 個ずつあることを示せ。

【74】任意の置換は ( k k+1 ) の形の幾つかの互換の積として表すことができることを示せ。

【75】阿弥陀くじ\begin{matrix}1 & 2 & 3 & 4 & 5 & 6 \\ | & | & | & | & | & | \\ 〜〜〜〜〜〜〜〜 \\ 〜〜〜〜〜〜〜〜 \\ | & | & | & | & | & | \\ 5 & 2 & 6 & 1 & 4 & 3 \end{matrix} を完成せよ。