Manuel Kauers Hagenberg, April 29, 2004 RISC-Linz

Algorithmic Combinatorics

Homework 7

Exercise 1 Let (G, ∘) and (H, ∗) be groups and define

·: (G × H) × (G × H) → (G × H), (g, h) · (g′, h′) = (g ∘ g′, h ∗ h′).

Show that (G × H, ·) is a group.

Check the group laws:

(g, h) · (1_{G}, 1_{H}) = (g ∘ 1_{G}, h ∗ 1_{H}) = (g, h)
((g, h) · (g′, h′)) · (g′′, h′′) = (g ∘ g′, h ∗ h′) · (g′′, h′′) = ((g ∘ g′) ∘ g′′, (h ∗ h′) ∗ h′′)
= (g ∘ (g′ ∘ g′′), h ∗ (h′ ∗ h′′)) = (g, h) · (g′ ∘ g′′, h′ ∗ h′′)
= (g, h) · ((g′, h′) · (g′′, h′′))
(g, h) · (g^{−1}, h^{−1}) = (g ∘ g^{−1}, h ∗ h^{−1}) = (1_{G}, 1_{H}).

Exercise 2 Let N = [n], X = {a_{1}, …, a_{n}} and define

(S_{X} × S_{N}) × X^{N} → X^{N} ((σ, π), f) ↦ (σ, π)f

by

((σ, π)f)(k) := σ(f(π^{−1}(k))) (k ∈ N).

Show that this is a group action.

Check the group action laws:

(1_{X}, 1_{N})f = 1_{X} ∘ f ∘ 1_{N} = f
((σ, π)(σ′, π′))f(k) = (σ ∘ σ′, π ∘ π′)f(k) = ((σ ∘ σ′) ∘ f ∘ (π′^{−1} ∘ π^{−1}))(k)

= (σ ∘ (σ′ ∘ f ∘ π′^{−1}) ∘ π^{−1})(k) = ((σ, π)(σ′ ∘ f ∘ π^{−1}))(k)

= (σ, π)((σ′, π′)f)(k)

Exercise 2^{∗} In the notation of the lecture, does there exist a permutation σ ∈ S_{X} with f_{2} = (σ, π)f_{1}, when

f_{1} = \{ \begin{matrix}1 & 2 & 3 & 4 \\ a_{2} & a_{4} & a_{2} & a_{1} \end{matrix} \}, f_{2} = \{ \begin{matrix}1 & 2 & 3 & 4 \\ a_{1} & a_{2} & a_{3} & a_{3} \end{matrix} \}, π = \{ \begin{matrix}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{matrix} \}?

Yes:

\underbrace{\{ \begin{matrix}1 & 2 & 3 & 4 \\ a_{1} & a_{2} & a_{3} & a_{3} \end{matrix} \}}_{=f_{2}} = σ ∘ \underbrace{\{ \begin{matrix}1 & 2 & 3 & 4 \\ a_{2} & a_{4} & a_{2} & a_{1} \end{matrix} \}}_{=f_{1}} ∘ \underbrace{\{ \begin{matrix}1 & 2 & 3 & 4 \\ 4 & 2 & 3 & 1 \end{matrix} \}}_{=π=π^{−1}}

= σ ∘ \{ \begin{matrix}1 & 2 & 3 & 4 \\ a_{1} & a_{4} & a_{2} & a_{2} \end{matrix} \}

gives the constraints

σ(a_{1}) =^{!} a_{1},  σ(a_{4}) =^{!} a_{2},  σ(a_{2}) =^{!} a_{3},  σ(a_{2}) =^{!} a_{3}

which are satisfied by

σ = \{ \begin{matrix}a_{1} & a_{2} & a_{3} & a_{4} \\ a_{1} & a_{3} & a_{4} & a_{2} \end{matrix} \} .

Exercise 3 Consider the group action G × G → G, (g, g′) ↦ gg′. Show that δ: G → S_{G} is an injective group homomorphism.

First, δ is a homomorphism: For arbitrary h ∈ G we have

δ(g ∘ g′)(h) = g ∘ g′ ∘ h = g ∘ δ(g′)(h) = δ(g)(δ(g′)(h)) = (δ(g) ∘ δ(g′))(h).

Next, δ is injective: Let g, g′ ∈ G with δ(g) = δ(g′). Then

∀ h ∈ G : δ(g)(h) = δ(g′)(h),

therefore gh = g′h for all h ∈ G, and therefore g = g′.

Exercise 4 Let X be a G-set and δ: G → S_{X} the induced permutation representation. Prove:

a) δ is a group homomorphism.

b) Ḡ := δ(G) ≤ S_{X} acts on X as a subgroup of S_{X}.

c) Ḡ ≅ G/ker δ

d) G \\ X = Ḡ \\ X.

Ad a) For g, g′ ∈ G and x ∈ X, we have

δ(g · g′)(x) = (g · g′)x = g(g′h) = δ(g)(δ(g′)(x)) = (δ(g) ∘ δ(g′))(x).

Ad b) By a) it is clear that Ḡ ≤ S_{X}. Ḡ acts on X: First,

1Ḡx = δ(1_{G})(x) = id(x) = x.

Secondly, for π, π′ ∈ Ḡ we have certain g, g′ ∈ G with δ(g) = π, δ(g′) = π′, and for all those choices of g, g′ we have

(π ∘ π′)(x) = (δ(g) ∘ δ(g′))(x) = δ(g · g′)(x) = (g · g′)(x) = g(g′x)
= δ(g)(δ(g′)(x)) = π(π′(x)).

Ad c) Define δ̄: G/ker δ → Ḡ by

δ̄(g ker δ) := δ(g) (g ∈ G).

(1) δ̄ is well defined. For h ∈ g ker δ we have h = g · h̄ with h̄ ∈ ker δ and so

δ̄(h ker δ) = δ(h) = δ(g · h̄) = δ(g) ∘ \underbrace{δ(h̄)}_{=1_{G}} = δ(g) = δ̄(g ker δ).

(2) δ̄ is injective. Let g, h ∈ G with δ̄(g ker δ) = δ̄(h ker δ), i.e., δ(g) = δ(h). We have to show g ker δ = h ker δ, or, w.l.o.g. g ker δ ⊆ h ker δ. Let g′ = g · ḡ ∈ g ker δ. Then h̄ = h^{−1} · g · ḡ ∈ ker δ (note δ(h) = δ(g)) witnesses that g′ = h · h′ ∈ h ker δ.

(3) δ̄ is surjective. Clear by Ḡ = δ(G).

Ad d) It suffices to show gX = δ(g)X for all g ∈ G, which indeed is evident by the definition of δ(g)x.

Exercise 5 Define C_{4} × [4] → [4], (g, k) ↦ gk := g^{2}(k).

a) Show that this is a group action

b) Determine C̄_{4} and C̄_{4} \\ [4]

Ad a) We have 1_{C_{4}}(k) = k and, by the commutativity of C_{4},

(π ∘ σ)k = (π ∘ σ)^{2}(k) = (π^{2} ∘ σ^{2})(k) = π^{2}(σ^{2}(k)) = π(σk).

Ad b) Let π = (1 2 3 4). We have

C̄_{4} = δ(C_{4}) = {δ(π), δ(π^{2}), δ(π^{3}), δ(id)} = {π^{2}, π^{4}, π^{6}, π^{8}} = {π^{2}, id}
= {(1 3)(2 4), id},
C̄_{4} \\ [4] = {{k, (1 3)(2 4)k} : k ∈ [4] } = {{1, 3}, {2, 4}}.

Exercise 6 Define C_{5} × [5] → [5], (g, k) ↦ gk := g^{2}(k).

a) Show that this is a group action

b) Determine C̄_{5} and C̄_{5} \\ [5]

Ad a) see Exercise 5 a).

Ad b) Let π = (1 2 3 4 5). We have

C̄_{5} = δ(C_{5}) = {δ(π), δ(π^{2}), δ(π^{3}), δ(π^{4}), δ(id)} = {π^{2}, π^{4}, π, π^{3}, id} = C_{5},
C̄_{5} \\ [5] = {{ π^{i}(k) : i ∈ [5] } : k ∈ [5] } = {{1, 2, 3, 4, 5}}.