Exercises on 𝓢n

  1. Calculate the inverses and the order of the following permutations in 𝓢8, then decompose them in disjoint cycles.

    σ = |1 2 3 4 5 6 7 8|
    |8 5 6 3 2 7 1 4|
    τ = |1 2 3 4 5 6 7 8|
    |4 3 6 2 8 7 1 5|
    υ = |1 2 3 4 5 6 7 8|
    |8 3 2 4 7 6 5 1|
    φ = |1 2 3 4 5 6 7 8|
    |2 3 1 5 6 8 7 4|

  2. Verify if the following subset T is a subgroup of 𝓢4.

    T = {id, (1 3 2), (1 2 3), (1 2), (3 4), (2 3), (1 3) (2 4), (1 2) (3 4), (1 2 3 4), (1 3 2 4), (2 1 3 4), (2 1 4 3)}

  3. In 𝓢4 find the subgroup generated by the subset X = {(1 2 3), (1 4)}.

  4. Let X = {(1, 2, 3, 4), (1, 4) (2, 3)}, and consider the problem of finding ⟨X⟩ in 𝓢4.

  5. Prove that the subset of 𝓢n made by even permutations, is a subgroug, whilst the subset made by odd permutations is not.

  6. What are the cyclic structures of 𝓢14 with order 20? Which of these permutations are even and which are odd? Verify whether the subset S of the permutation of 𝓢14 with order 20 is a subgroup of 𝓢14.

  7. Verify whether 𝓢30 possesses a subgroup of order 209.

  8. Prove that An is generated by 3-cycles.

  9. Verify whether with the ordinary rules of the 15 Puzzle is possible to transform the left configuration into the right one.

    2 1 10 9
    11 8 7 5
    4 12 6 3
    13 15 14
    1 5 4 8
    10 3 13 6
    11 15 14 12
    7 9 2

Solutions

    • σ = (1 8 4 3 6 7) (2,5). σ−1 = (1 7 6 3 4 8) (2 5). The order of a permutation is the lcm of the orders of the cycles in its disjoint cycle decomposition hence lmc(6,2) = 6.

    • τ = (1 4 2 3 6 7) (5 8). τ−1 = (1 7 6 3 2 4) (5 8). The order is lcm(6,2) = 6.

    • υ = (1 8) (2 3) (5 7). The order is lcm(2,2,2) = 2, hence it coincides with υ−1.

    • φ = (1 2 3) (4 5 6 8), φ−1 = (1 3 2) (4 8 6 5). The order is lcm(3, 4) = 12.

  2. It is not a subgroup: for example (1 2 3 4) (2 3) = (1 2 4) ∉ 𝓢4.

  3. We begin by computing the distinct powers of the elements of X:

    α = (1 2 3),   α2 = (1 3 2),   α3 = e.

    β = (1 4),   β2 = e.

    Starting a multiplication table using e, α, α2, α3, β, we find the following new elements of ⟨X⟩

    αβ = (1 2 3) (1 4) = (1 4 2 3),   α2β = (1 3 2) (1 4) = (1 4 3 2).

    We then enlarge the table so as to use all eight elements

    S = {id, (1 2 3), (1 4), (1 4 2 3), (1 4 3 2)}

    is the subgroup of 𝓢4 generated by X.

  4. The product of two even permutations is an even permutation, hence is a subgroup, whilst the product of two odd permutations is even.

  5. We start by computing the distinct powers of the elements of X:

    α = (1, 2, 3, 4),   α2 = (1, 3)(2, 4),   α3 = α−1 = (1, 4, 3, 2),
    β = (1, 4)(2, 3),   β2 = e

    Setting up a multiplication table using e, α α2, α3, β, we find the following new elements of ⟨X⟩

    αβ = (1, 2, 3, 4)(1, 4)(2, 3) = (2, 4)
    α2β = (1, 3)(2, 4)(1, 4)(2, 3) = (1, 2)(3, 4)
    α3β = (1, 4, 3, 2)(1, 4)(2, 3) = (1, 3)

    We then enlarge the table so as to use all eight elements

    ⟨X⟩ = {e, α, α2, α3, β, αβ, α2β, α3β}

    is the subgroup of 𝓢4, generated by X.

  6. The possible cyclic structures are

    (10-cycle) ⋅ (4-cycle), even;   (5-cycle) ⋅ (5-cycle) ⋅ (4-cycle), odd   (5-cycle) ⋅ (4-cycle) ⋅ (4-cycle). even;   (5-cycle) ⋅ (4-cycle) ⋅ (2-cycle) ⋅ (2-cycle), odd;   (5-cycle) ⋅ (4-cycle) ⋅ (2-cycle), even; (5-cycle) ⋅ (4-cycle), odd.

    The elements having order 20 are not a subgroup of 𝓢14, because the identity of 𝓢14is order 1 not order 20 so not in S by definition of S: idk = id and the order is the least positive element, i.e. k = 1). Furthermore the product of the following two elements of order 20

    (1 2 3 4 5) (6 7 8 9) (1 2 3 4 5) (6 7 8 9) = (1 3 5 2 4) (6 8) (7 9)

    is an element with period 10.

  7. It suffices to show that there exists in 𝓢30 a permutation of order 209. Since 209 = 11 ⋅ 19, such a permutation is formed by a disjoint product of the form (11-cycle) ⋅ (19-cycle) (which exists in 𝓢30 e.g. σ = (1 2 3 4 5 6 7 8 9 10 11)(12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30) has order 209). This means that we can consider the subgroup S = ⟨g | g209 = e⟩.

  8. By definition every σ ∈ An is an even permutation, that is product of an even number of transpositions. We've to show that the product of two transpositions is always either a 3-cycle or a product of 3-cycles. If the two transpositions coincide then their product is the identity, which can be expressed as a 3-cycle by its inverse. If the two transpositions are disjoint, e.g σ = (1 2), τ = (3 4) then we can write στ = (1 2 3) (2 3 4). If the two transposition are not disjoint, they a number in common, e.g. σ = (1 2), τ = (2 3): then (1 2)(2 3) = (1 2 3).

  9. Think of the empty space as being occupied by the number 16. Now the puzzle consists of sixteen tiles in sixteen locations, and a legal move interchanges the black tile with one of its neighbors, keeping all the other tiles fixed. Thus a legal move is a transposition. The attempted rearrangement corresponds to this permutation

    σ = |1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16|
    |1 5 4 8 10 3 13 6 11 15 14 12 7 9 2 16|

    Then σ is odd, since

    σ = (1 5 6 14 2) (3 12 15 9 8) (4 11 10) (7 13).

    Therefore any effort that produces the desired rearrangement must involve an odd number of legal moves. On the other hand, each legal move requires a horizontal or vertical move of the blank tile. For that tile to return to its initial position, it must be subjected to an even number of vertical moves and an even number of horizontal moves, hence to an even number of moves altogether. Thus the desired rearrangement is impossible.

«The transformation group Index Exercises on permutations»