representation of permutation group

Group Theory

Lagrange’s Theorem

Cyclic Groups

Up to Order 8

Product Theorem

Permutations

Normal Subgroups

Quotient Groups

Isomorphisms

Jordan-Holder

Abelian Groups

Finitely Generated

The set of all permutations of \(n\) objects forms a group \(S_n\) of order \(n!\). It is called the \(n\)th symmetric group .

A permutation that interchanges \(m\) objects cyclically is called circular permutation or a cycle of degree \(m\). Denote the object by the positive integers. Then the cycle that moves 1 to 2, 2 to 3, \(..., m-1\) to \(m\) and \(m\) to \(1\) is written \((1 2 ... m)\).

Every permutation can be unique represented into cycles operating on disjoint sets.

Example: \((1 2 3 4 5 6)^2 = (1 3 5)(2 4 6)\)

So we may write a given permutation \(P = C_1 ... C_r\) where the \(C_i\) are cycles. Since cycles on disjoint sets commute, we have \(P^m = C_1^m ... C_r^m\), and we see that the order of a permutation is the lowest common multiple of the orders of its component cycles. A permutation is regular if all of its cycle are of the same degree.

Two permutations \(a, b \in S_n\) are conjugate or similar if there exists \(t\in S_n\) with \(b = t^{-1} a t\). Let \(a = C_1 ... C_r\) where the \(C_i\) are cycles. Then the cycle decomposition of \(b\) is obtained by applying \(t\) to the elements inside the brackets of the strings representing each cycle, that is, if \(C_i = (a_1 a_2 ... a_m)\) then \(t^{-1} C_i t = (t(a_1) t(a_2) ... t(a_m))\) where \(t(a_i)\) represents the element \(t\) maps \(a_i\) to.

Let \(a\in S_n\), and write \(a = C_1 ... C_r\) such that the cycles are arranged in non-decreasing order, that is, if we write \(\mu_i\) for the cycle length of \(C_i\), then \(1 \le \mu_1 \le ... \le \mu_r\), and \(\mu_1 +...+\mu_r = n\). Thus every permutation is associated with a partition of \(n\) into positive integers. Two permutations that belong to the same partition are said to belong to the same class of \(S_n\).

It is clear that two permuations of \(S_n\) are conjugate if and only if they belong to the same class.

Now let us count how many partitions belong to a given class. Say a permutation has \(\alpha_i\) cycles of degree \(i\), so that \(\alpha_1 + 2 \alpha_2 + ... + n\alpha_n = n\). Then a set of nonnegative integers \(\{\alpha_1 ,..., \alpha_n\}\) determines a class which we shall denote \(\alpha\). When writing down the cycles, we need to use up \(n\) numbers, and there are \(n!\) ways to do this. But since for any \(i\), we may permute the \(i\)-cycles amongst themselves, we must divide by \(\alpha_1 ! ... \alpha_n !\) times. Lastly, a cycle of length \(i\) can be written in \(i\) different ways, so if \(h_\alpha\) denotes the number of permutations in the class \(\alpha\), we have

A 2-cycle is called a transposition .

Let \(x_1,...,x_n\) be indeterminates and consider the product of differences

Then applying a permutation \(\pi \in S_n\) to the variables will either preserve this value or negate it. We write

A permutation \(\pi\) is said to be even if \(\zeta(\pi) = 1\), and odd otherwise, that is, if \(\zeta(\pi) = {-1}\). The function \(\zeta\) is called the alternating character of \(S_n\).

Theorem: Let \(a,b \in S_n\). Then \(\zeta(a b) = \zeta(a)\zeta(b)\).

Proof: Write \(\Delta_\pi\) for \(\Delta(\pi(x_1,...,x_n))\).

Note all permutations of the same class have the same alternating character: by the theorem we have \(\zeta(b) \zeta(b^{-1}) = \zeta(1) = 1\), and \(\zeta(b^{-1}a b) = \zeta(a)\) after applying the theorem again.

Theorem: All transpositions are odd permutations.

Proof: The permutation \((1 2)\) negates the factor \((x_1 - x_2)\) in \(\Delta\) but leaves the other factors unchanged, thus we have \(\zeta((1 2)) = {-1}\). Then the results follows after using the identities

Every permutation \(\pi\) can be written as a product of transpositions, because a cycle \((a_1 ... a_m)\) can be written as \((a_1 a_2)(a_1 a_3) ... (a_1 a_m)\). By the above theorem, the number of transpositions in such a representation is odd or even depending on whether \(\pi\) is odd or even.

Note \(S_n\) can be generated by the \(n-1\) transpositions \((1 2), (1 3),..., (1 n)\).

Theorem: In any group of permutations \(G\), either all or exactly half the elements are even. The even permutations of \(G\) form a subgroup.

Proof: It is clear that the even permutations form a subgroup.

If \(G\) contains no odd permutations, there is nothing to prove. Otherwise let \(q\in G\) be an odd permutation, so that \(\zeta{q} ={-1}\). Then as \(q G = G\), we have

Since \(\zeta\) is multiplicative we have

hence \(\sum \zeta(g) = 0\), proving the result.

The set of all even permutation of degree \(n\) forms a group \(A_n\) of order \(\frac{1}{2} n!\), called the alternating group of degree \(n\).

Since \((1 i)(1 j) = (1 i j)\) for distinct \(1, i, j\), and since \((1 i j) = (1 2 j)(1 2 i)(1 2 j)\) we see that \(A_n\) may be generated from the \(n-2\) 3-cycles

Cayley’s Theorem: Let \(G = \{g_1,...,g_{|G|}\}\) be any group. Each \(g_i \in G\) can be associated with the permutation of \(S_n\) that takes \(g_j\) to \(g_j g_i\). The set of these permutations forms a subgroup \(G'\) of \(S_n\), and \(G' \cong G\).

The permutation group \(G'\) associated with a group \(G\) is called the regular representation of \(G\). In general, if an abstract group \(G\) is isomorphic to some concrete mathematical group (e.g. permutations, matrices) then we say we have a faithful representation of \(G\).

A group of permutations \(G \subset S_n\) is said to be transitive if for every \(\alpha,\beta \in \{1,...,n\}\) there exists \(g\in G\) with \(g(\alpha) = \beta\), that is, for any two objects, there exists a permutation that maps one to the other. Otherwise the group is intransitive .

Example: \(\{(1), (1 2), (3 4), (1 2)(3 4)\}\) is intransitive because no permutations takes 1 to 3. It is isomorphic to the transitive group \(\{ (1), (1 2)(3 4), (1 3)(2 4), (1 4)(2 3) \}\).

Write \(G_\alpha\) for the subgroup of permutations of \(G\) that fix \(\alpha\).

Theorem: A group of permutations \(G \subset S_n\) is transitive if and only if the subgroup \(G_1\) is of index \(n\) relative to \(G\).

Proof: If \(G\) is transitive, then there exists element

that map \(1\) to \(2,3,...,n\) respectively. Consider the sets

The sets are disjoint because each acts differently on the element 1. Futhermore, any \(q \in G\) transforms \(1\) to \(k\), say, hence \(q \in G_1 g_{1 k}\) because \(q g_{1 k}\) leaves 1 unchanged so must lie in \(G_1\). So these disjoint cosets partition \(G\), showing that \(G_1\) has index \(n\) in \(G\).

Conversely, if \(G_1\) has index \(n\), decompose \(G\) into cosets \(G_1 g_1,...,G_1 g_n\). Then if \(g_i , g_j\) transform 1 to the same object \(\alpha\), we have that \(g_i g_j^{-1} \in G_1\), implying that \(G_1 g_i = G_1 g_j\) and hence \(i = j\). Thus we may label the \(g_i\) such that \(g_i(1) = i\).

Lastly, if \(\alpha,\beta \in \{1,...,n\}\) then \(g_\alpha^{-1} g_\beta\) transforms \(\alpha\) into \(\beta\).

Corollary: The order of a transitive groups of permuations of degree \(n\) is divisible by \(n\).

A group of permutations \(G\) is said to be \(k\)-ply transitive if for any sets of size \(k\) \(\{\alpha_1,...,\alpha_k\}, \{\beta_1,...,\beta_k\} \subset \{1,...,n\}\) there exists \(g\in G\) with \(g(\alpha_i) = \beta_i\) for all \(i\).

The number of distinct subsets of size \(k\) in a set of size \(n\) is given by \(n(n-1)...(n-k+1)\). Thus we have:

Theorem: The order of a \(k\)-ply transitive group of degree \(n\) is divisible by \(n(n-1)...(n-k+1)\).

Theorem: The group \(G\) is \(k\)-ply transitive if \(G\) is simply transitive and \(G_1\) is \((k-1)\)-ply transitive with respect to \(\{2,3,...,n\}\).

Let \(G\) be a transitive group in \(S_n\). Suppose it is possible to place \(1,...,n\) in an \(r \times s\) matrix where \(r s = n, r,s> 1\) such that the permutations of \(G\) either permute the objects of any one row amongst themselves or else interchange objects of one row with another. In other words, two objects that start in the same row are never transformed to objects in different rows, and vice versa. Then \(G\) is said to be imprimitive , and the rows are called imprimitive systems . Otherwise \(G\) is said to be primitive. Note all doubly-transitive groups are primitive, and in particular, \(S_n\) is primitive.

• school Campus Bookshelves
• menu_book Bookshelves
• perm_media Learning Objects
• login Login
• how_to_reg Request Instructor Account
• hub Instructor Commons

Margin Size

• Download Page (PDF)
• Download Full Book (PDF)
• Periodic Table
• Physics Constants
• Scientific Calculator
• Reference & Cite
• Tools expand_more
• Readability

selected template will load here

This action is not available.

6.1: Permutation Groups

• Last updated
• Save as PDF
• Page ID 6120

• Kenneth P. Bogart
• Dartmouth University

\( \newcommand{\vecs}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vecd}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash {#1}}} \)

\( \newcommand{\id}{\mathrm{id}}\) \( \newcommand{\Span}{\mathrm{span}}\)

( \newcommand{\kernel}{\mathrm{null}\,}\) \( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\) \( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\) \( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\inner}[2]{\langle #1, #2 \rangle}\)

\( \newcommand{\Span}{\mathrm{span}}\)

\( \newcommand{\id}{\mathrm{id}}\)

\( \newcommand{\kernel}{\mathrm{null}\,}\)

\( \newcommand{\range}{\mathrm{range}\,}\)

\( \newcommand{\RealPart}{\mathrm{Re}}\)

\( \newcommand{\ImaginaryPart}{\mathrm{Im}}\)

\( \newcommand{\Argument}{\mathrm{Arg}}\)

\( \newcommand{\norm}[1]{\| #1 \|}\)

\( \newcommand{\Span}{\mathrm{span}}\) \( \newcommand{\AA}{\unicode[.8,0]{x212B}}\)

\( \newcommand{\vectorA}[1]{\vec{#1}}      % arrow\)

\( \newcommand{\vectorAt}[1]{\vec{\text{#1}}}      % arrow\)

\( \newcommand{\vectorB}[1]{\overset { \scriptstyle \rightharpoonup} {\mathbf{#1}} } \)

\( \newcommand{\vectorC}[1]{\textbf{#1}} \)

\( \newcommand{\vectorD}[1]{\overrightarrow{#1}} \)

\( \newcommand{\vectorDt}[1]{\overrightarrow{\text{#1}}} \)

\( \newcommand{\vectE}[1]{\overset{-\!-\!\rightharpoonup}{\vphantom{a}\smash{\mathbf {#1}}}} \)

We begin by studying the kinds of permutations that arise in situations where we have used the quotient principle in the past.

6.1.1: The Rotations of a Square

In Figure 6.1.1 we show a square with its four vertices labeled \(a\), \(b\), \(c\), and \(d\). We have also labeled the spots in the plane where each of these vertices falls with the label \(1\), \(2\), \(3\), or \(4\). Then we have shown the effect of rotating the square clockwise through \(90\), \(180\), \(270\), and \(360\) degrees (which is the same as rotating through \(0\) degrees).

Underneath each of the rotated squares we have named the function that carries out the rotation. We use \(ρ\), the Greek letter pronounced “row,” to stand for a \(90\) degree clockwise rotation. We use \(ρ^2\) to stand for two \(90\) degree rotations, and so on. We can think of the function \(ρ\) as a function on the four-element set 1 \(\{1, 2, 3, 4\}\). In particular, for any function \(\varphi\) (the Greek letter phi, usually pronounced “fee,” but sometimes “fie”) from the plane back to itself that may move the square around but otherwise leaves it in the same location, we let \(\varphi (i)\) be the label of the place where vertex previously in position i is now. Thus \(ρ(1) = 2\), \(ρ(2) = 3\), \(ρ(3) = 4\) and \(ρ(4) = 1\). Notice that \(ρ\) is a permutation on the set \(\{1, 2, 3, 4\}\).

\(\bullet\) Exercise \(248\)

The composition \(f \circ g\) of two functions \(f\) and \(g\) is defined by \(f \circ g(x) = f(g(x))\). Is \(ρ^3\) the composition of \(ρ\) and \(ρ^2\)? Does the answer depend on the order in which we write \(ρ\) and \(ρ^2\)? How is \(ρ^2\) related to \(ρ\)?

\(\bullet\) Exercise \(249\)

Is the composition of two permutations always a permutation?

In Problem 248 you see that we can think of \(ρ^2 \circ ρ\) as the result of first rotating by \(90\) degrees and then by another \(180\) degrees. In other words, the composition of two rotations is the same thing as first doing one and then doing the other. Of course, there is nothing special about \(90\) degrees and \(180\) degrees. As long as we first do one rotation through a multiple of \(90\) degrees and then another rotation through a multiple of \(90\) degrees, the composition of these rotations is a rotation through a multiple of \(90\) degrees.

If we first rotate by \(90\) degrees and then by \(270\) degrees then we have rotated by \(360\) degrees, which does nothing visible to the square. Thus we say that \(ρ^4\) is the “identity function.” In general, the identity function on a set \(S\), denoted by \(ι\) (the Greek letter iota, pronounced eye-oh-ta) is the function that takes each element of the set to itself. In symbols, \(ι(x) = x\) for every \(x\) in \(S\). Of course the identity function on a set is a permutation of that set.

6.1.2: Groups of Permutations

\(\bullet\) Exercise \(250\)

For any function \(\varphi\) from a set \(S\) to itself, we define \(\varphi^{n}\) (for nonnegative integers n) inductively by \(\varphi^{0} = ι\) and \(\varphi^{n} = \varphi^{n−1} ◦ \varphi \) for every positive integer \(n\). If \(\varphi\) is a permutation, is \(\varphi^{n}\) a permutation? Based on your experience with previous inductive proofs, what do you expect \(\varphi^{n} ◦ \varphi^{m}\) to be? What do you expect \((\varphi^{m})^n\) to be? There is no need to prove these last two answers are correct, for you have, in effect, already done so in Chapter 2 .

\(\bullet\) Exercise \(251\)

If we perform the composition \(ι ◦ \varphi\) for any function \(\varphi\) from \(S\) to \(S\), what function do we get? What if we perform the composition \(\varphi ◦ ι\)?

What you have observed about iota in Problem 251 is called the identity property of iota. In the context of permutations, people usually call the function \(ι\) “the identity” rather than calling it “iota.”

Since rotating first by \(90\) degrees and then by \(270\) degrees has the same effect as doing nothing, we can think of the \(270\) degree rotation as undoing what the \(90\) degree rotation does. For this reason, we say that in the rotations of the square, \(ρ^3\) is the “inverse” of \(ρ\). In general, a function \(\varphi: T → S\) is called an inverse of a function \(σ: S → T\) (\(σ\) is the lower case Greek letter sigma) if \(\varphi ◦ σ = σ ◦ \varphi = ι\). For a slower introduction to inverses and practice with them, see Section A.1.3 in Appendix A . Since a permutation is a bijection, it has a unique inverse, as in Section A.1.3 of Appendix A . And since the inverse of a bijection is a bijection (again, as in the Appendix), the inverse of a permutation is a permutation.

We use \(\varphi^{−1}\) to denote the inverse of the permutation \(\varphi\). We’ve seen that the rotations of the square are functions that return the square to its original location but may move the vertices to different places. In this way, we create permutations of the vertices of the square. We’ve observed three important properties of these permutations.

• (Identity Property) These permutations include the identity permutation.
• (Inverse Property) Whenever these permutations include \(\varphi\), they also include \(\varphi^{−1}\).
• (Closure Property) Whenever these permutations include \(\varphi\) and \(σ\), they also include \(\varphi ◦ σ\).

A set of permutations with these three properties is called a permutation group 2 or a group of permutations. We call the group of permutations corresponding to rotations of the square the rotation group of the square. There is a similar rotation group with \(n\) elements for any regular \(n\)-gon.

\(\bullet\) Exercise \(252\)

If \(f: S → T\), \(g: T → X\), and \(h: X → Y\), is \(h ◦ (g ◦ f) = (h ◦ g) ◦ f\)? What does this say about the status of the associative law \(ρ ◦ (σ ◦ \varphi) = (ρ ◦ σ) ◦ \varphi\) in a group of permutations?

\(\bullet\) Exercise \(253\)

• How should we define \(\varphi^{−n}\) for an element \(\varphi\) of a permutation group? (Hint) .
• Will the two standard rules for exponents \(a^ma^n = a^{m+n}\) and \((a^m)^n = a^{mn}\) still hold in a group if one or more of the exponents may be negative? (No proof required yet.)
• Proving that \(\varphi^{−m})^n = \varphi^{−mn}\) when \(m\) and \(n\) are nonnegative is different from proving that \(\varphi^m)^{−n} = \varphi^{−mn}\) when \(m\) and \(n\) are nonnegative. Make a list of all such formulas we would need to prove in order to prove that the rules of exponents of Part 253b do hold for all nonnegative and negative \(m\) and \(n\).
• If the rules hold, give enough of the proof to show that you know how to do it; otherwise give a counterexample.

\(\bullet\) Exercise \(254\)

If a finite set of permutations satisfies the closure property is it a permutation group? (Hint) .

\(\bullet\) Exercise \(255\)

There are three-dimensional geometric motions of the square that return it to its original location but move some of the vertices to other positions. For example, if we flip the square around a diagonal, most of it moves out of the plane during the flip, but the square ends up in the same location. Draw a figure like Figure 6.1.1 that shows all the possible results of such motions, including the ones shown in Figure 6.1.1. Do the corresponding permutations form a group?

Exercise \(256\)

Let \(σ\) and \(\varphi\) be permutations.

• Why must \(σ ◦ \varphi\) have an inverse?
• Is \((σ ◦ \varphi)^{−1} = σ^{−1} \varphi^{−1}\)? (Prove or give a counter-example.) (Hint) .
• Is \((σ ◦ \varphi)^{−1} = \varphi^{−1} σ^{−1}\)? (Prove or give a counter-example.)

\(\bullet\) Exercise \(257\)

Explain why the set of all permutations of four elements is a permutation group. How many elements does this group have? This group is called the symmetric group on four letters and is denoted by \(S_4\).

6.1.3: The Symmetric Group

In general, the set of all permutations of an \(n\)-element set is a group. It is called the symmetric group on \(n\) letters . We don’t have nice geometric descriptions (like rotations) for all its elements, and it would be inconvenient to have to write down something like “Let \(σ(1) = 3\), \(σ(2) = 1\), \(σ(3) = 4\), and \(σ(4) = 1\)” each time we need to introduce a new permutation. We introduce a new notation for permutations that allows us to denote them reasonably compactly and compose them reasonably quickly. If \(σ\) is the permutation of \(\{1, 2, 3, 4\}\) given by \(σ(1) = 3\), \(σ(2) = 1\), \(σ(3) = 4\) and \(σ(4) = 2\), we write

\[σ = \binom{1 \; 2 \; 3 \; 4}{3 \; 1 \; 4 \; 2} .\]

We call this notation the two row notation for permutations. In the two row notation for a permutation of \(\{a_1, a_2, . . . , a_n\}\), we write the numbers \(a_1\) through \(a_n\) in one row and we write \(σ(a_1)\) through \(σ(a_n)\) in a row right below, enclosing both rows in parentheses. Notice that

\[\binom{1 \; 2 \; 3 \; 4}{3 \; 1 \; 4 \; 2} = \binom{2 \; 1 \; 4 \; 3}{1 \; 3 \; 2 \; 4},\]

although the second ordering of the columns is rarely used.

If \(\varphi\) is given by

\[\varphi = \binom{1 \; 2 \; 3 \; 4}{4 \; 1 \; 2 \; 3}\],

then, by applying the definition of composition of functions, we may compute σ ◦ ϕ as shown in Figure 6.2.

We don’t normally put the circle between two permutations in two row notation when we are composing them, and refer to the operation as multiplying the permutations, or as the product of the permutations. To see how Figure 6.1.2 illustrates composition, notice that the arrow starting at \(1\) in \(\varphi\) goes to \(4\). Then from the \(4\) in \(\varphi\) it goes to the \(4\) in \(σ\) and then to \(2\). This illustrates that \(\varphi(1) = 4\) and \(σ(4) = 2\), so that \(σ(\varphi(1)) = 2\).

Exercise \(258\)

For practice, compute \(\binom{1 \; 2 \; 3 \; 4 \; 5}{3 \; 4 \; 1 \; 5 \; 2} = \binom{1 \; 2 \; 3 \; 4 \; 5}{4 \; 3 \; 5 \; 1 \; 2} .\)

6.1.4: The Dihedral Group

We found four permutations that correspond to rotations of the square. In Problem 255 you found four permutations that correspond to flips of the square in space. One flip fixes the vertices in the places labeled \(1\) and \(3\) and interchanges the vertices in the places labeled \(2\) and \(4\). Let us denote it by \(\varphi_{1|3}\). One flip fixes the vertices in the positions labeled \(2\) and \(4\) and interchanges those in the positions labeled \(1\) and \(3\). Let us denote it by \(\varphi_{2|4}\). One flip interchanges the vertices in the places labeled \(1\) and \(2\) and also interchanges those in the places labeled \(3\) and \(4\). Let us denote it by \(\varphi_{12|34}\). The fourth flip interchanges the vertices in the places labeled \(1\) and \(4\) and interchanges those in the places labeled \(2\) and \(3\). Let us denote it by \(\varphi_{14|23}\). Notice that \(\varphi_{1|3}\) is a permutation that takes the vertex in place \(1\) to the vertex in place \(1\) and the vertex in place \(3\) to the vertex in place \(3\), while \(\varphi_{12|34}\) is a permutation that takes the edge between places \(1\) and \(2\) to the edge between places \(2\) and \(1\) (which is the same edge) and takes the edge between places \(3\) and \(4\) to the edge between places \(4\) and \(3\) (which is the same edge). This should help to explain the similarity in the notation for the two different kinds of flips.

\(\bullet\) Exercise \(259\)

Write down the two-row notation for \(ρ^3\), \(\varphi_{2|4}\), \(\varphi_{12|34}\) and \(\varphi_{2|4} ◦ \varphi_{12|34}\). Remember that \(σ(i)\) stands for the position where the vertex that originated in position \(i\) is after we apply \(σ\).

Exercise \(260\)

(You may have already done this problem in Problem 255, in which case you need not do it again!) In Problem 255, if a rigid motion in three-dimensional space returns the square to its original location, in how many places can vertex number one land? Once the location of vertex number one is decided, how many possible locations are there for vertex two? Once the locations of vertex one and vertex two are decided, how many locations are there for vertex three? Answer the same question for vertex four. What does this say about the relationship between the four rotations and four flips described just before Problem 259 and the permutations you described in Problem 255?

The four rotations and four flips of the square described before Problem 259 form a group called the dihedral group of the square. Sometimes the group is denoted \(D_8\) because it has eight elements, and sometimes the group is denoted by \(D_4\) because it deals with four vertices! Let us agree to use the notation \(D_4\) for the dihedral group of the square. There is a similar dihedral group, denoted by \(D_n\), of all the rigid motions of three-dimensional space that return a regular \(n\)-gon to its original location (but might put the vertices in different places).

Exercise \(261\)

Another view of the dihedral group of the square is that it is the group of all distance preserving functions, also called isometries , from a square to itself. Notice that an isometry must be a bijection. Any rigid motion of the square preserves the distances between all points of the square. However, it is conceivable that there might be some isometries that do not arise from rigid motions. (We will see some later on in the case of a cube.) Show that there are exactly eight isometries (distance preserving functions) from a square to itself. (Hint) .

Exercise \(262\)

How many elements does the group \(D_n\) have? Prove that you are correct.

Exercise \(263\)

In Figure 6.1.3 we show a cube with the positions of its vertices and faces labeled. As with motions of the square, we let we let \(\varphi(x)\) be the label of the place where vertex previously in position \(x\) is now.

• Write in two row notation the permutation \(ρ\) of the vertices that corresponds to rotating the cube \(90\) degrees around a vertical axis through the faces \(t\) (for top) and \(u\) (for underneath). (Rotate in a right-handed fashion around this axis, meaning that vertex \(6\) goes to the back and vertex \(8\) comes to the front.)
• Write in two row notation the permutation \(\varphi\) that rotates the cube \(120\) degrees around the diagonal from vertex \(1\) to vertex \(7\) and carries vertex \(8\) to vertex \(6\).
• Compute the two row notation for \(ρ ◦ \varphi\).
• Is the permutation \(ρ ◦ \varphi\) a rotation of the cube around some axis? If so, say what the axis is and how many degrees we rotate around the axis. If \(ρ ◦ \varphi\) is not a rotation, give a geometric description of it.

\(\rightarrow \; \cdot\) Exercise \(264\)

How many permutations are in the group \(R\)? \(R\) is sometimes called the “rotation group” of the cube. Can you justify this? (Hint) .

Exercise \(265\)

As with a two-dimensional figure, it is possible to talk about isometries of a three-dimensional figure. These are distance preserving functions from the figure to itself. The function that reflects the cube in Figure 6.1.3 through a plane halfway between the bottom face and top face exchanges the vertices \(1\) and \(5\), \(2\) and \(6\), \(3\) and \(7\), and \(4\) and \(8\) of the cube. This function preserves distances between points in the cube. However, it cannot be achieved by a rigid motion of the cube because a rigid motion that takes vertex \(1\) to vertex \(5\), vertex \(2\) to vertex \(6\), vertex \(3\) to vertex \(7\), and vertex \(4\) to vertex \(8\) would not return the cube to its original location; rather it would put the bottom of the cube where its top previously was and would put the rest of the cube above that square rather than below it.

• How many elements are there in the group of permutations of \([8]\) that correspond to isometries of the cube? (Hint) .
• Is every permutation of \([8]\) that corresponds to an isometry either a rotation or a reflection? (Hint) .

6.1.5: Group Tables (Optional)

We can always figure out the composition of two permutations of the same set by using the definition of composition, but if we are going to work with a given permutation group again and again, it is worth making the computations once and recording them in a table. For example, the group of rotations of the square may be represented as in Table 6.1.1. We list the elements of our group, with the identity first, across the top of the table and down the left side of the table, using the same order both times. Then, in the row labeled by the group element \(σ\) and the column labeled by the group element \(\varphi\), we write the composition \(σ ◦ \varphi\), expressed in terms of the elements we have listed on the top and on the left side. Since a group of permutations is closed under composition, the result \(σ ◦ \varphi\) will always be expressible as one of these elements.

Exercise \(266\)

In Table 6.1.1, all the entries in a row (not including the first entry, the one to the left of the line) are different. Will this be true in any group table for a permutation group? Why or why not? Also, in Table 6.1.1, all the entries in a column (not including the first entry, the one above the line) are different. Will this be true in any group table for a permutation group? Why or why not?

Exercise \(267\)

In Table 6.1.1, every element of the group appears in every row (even if you don’t include the first element, the one before the line). Will this be true in any group table for a permutation group? Why or why not? Also in Table 6.1.1 every element of the group appears in every column (even if you don’t include the first entry, the one before the line). Will this be true in any group table for a permutation group? Why or why not?

\(\bullet\) Exercise \(268\)

Write down the group table for the dihedral group \(D_4\). Use the \(\varphi\) notation described earlier to denote the flips. (Hints: Part of the table has already been written down. Will you need to think hard to write down the last row? Will you need to think hard to write down the last column? When you multiply a product like \(\varphi_{1|3} ◦ ρ\) remember that we defined \(\varphi_{1|3}\) to be the flip that fixes the vertex in position \(1\) and the vertex in position \(3\), not the one that fixes the vertex on the square labeled \(1\) and the vertex on the square labeled \(3\).)

You may notice that the associative law, the identity property, and the inverse property are three of the most important rules that we use in regrouping parentheses in algebraic expressions when solving equations. There is one property we have not yet mentioned, the commutative law , which would say that \(σ ◦ \varphi = \varphi ◦ σ\). It is easy to see from the group table of the rotation group of a square that it satisfies the commutative law.

Exercise \(269\)

Does the commutative law hold in all permutation groups?

6.1.6: Subgroups

We have seen that the dihedral group \(D_4\) contains a copy of the group of rotations of the square. When one group \(G\) of permutations of a set \(S\) is a subset of another group \(G_0\) of permutations of \(S\), we say that \(G\) is a subgroup of \(G_0\).

\(\bullet\) Exercise \(270\)

Find all subgroups of the group \(D_4\) and explain why your list is complete. (Hint) .

Exercise \(271\)

Can you find subgroups of the symmetric group \(S_4\) with two elements? Three elements? Four elements? Six elements? (For each positive answer, describe a subgroup. For each negative answer, explain why not.)

6.1.7: The Cycle Decomposition of a Permutation

The digraph of a permutation gives us a nice way to think about it. Notice that the product in Figure 6.1.2 is \(\binom{1 \;2 \;3\; 4}{2\; 3\; 1\; 4}\). We have drawn the directed graph of this permutation in Figure 6.1.4.

You see that the graph has two directed cycles, the rather trivial one with vertex \(4\) pointing to itself, and the nontrivial one with vertex \(1\) pointing to vertex \(2\) pointing to vertex \(3\) which points back to vertex \(1\). A permutation is called a cycle if its digraph consists of exactly one cycle. Thus \(\binom{1\; 2\; 3}{2\; 3\; 1}\) is a cycle but \(\binom{1 \;2 \;3 \;4}{2\; 3\; 1\; 4}\) is not a cycle by our definition. We write \((1\; 2\; 3)\) or \((2\; 3\; 1)\) or \((3\; 1\; 2)\) to stand for the cycle \(σ = \binom{1\; 2\; 3}{2\; 3\; 1}\).

We can describe cycles in another way as well. A cycle of the permutation \(σ\) is a list \((i σ(i) σ^2 (i) . . . σ^n (i))\) that does not have repeated elements while the list \((i σ(i) σ^2 (i) . . . σ^n (i) σ^{n+1}(i))\) does have repeated elements.

Exercise \(272\)

If the list \((i σ(i) σ^2 (i) . . . σ^n (i))\) does not have repeated elements but the list \((i σ(i) σ^2 (i) . . . σ^n (i) σ^{n+1}(i))\) does have repeated elements, then what is \(σ^{n+1}(i)\)? (Hint) .

We say \(σ^j (i)\) is an element of the cycle \((i σ(i) σ^2 (i) . . . σ^n (i))\). Notice that the case \(j = 0\) means \(i\) is an element of the cycle. Notice also that if \(j > n\), \(σ^j (i) = σ^{j−n−1} (i)\), so the distinct elements of the cycle are \(i\), \(σ(i)\), \(σ^2 (i)\), through \(σ^n (i)\). We think of the cycle \((i σ(i) σ^2 (i) . . . σ^n (i))\) as representing the permutation \(σ\) restricted to the set of elements of the cycle. We say that the cycles \((i σ(i) σ^2 (i) . . . σ^n (i))\) and \((j σ(j) σ^2(j) ... σ^n(j))\) are equivalent if there is an integer \(k\) such that \(j = σ^k (i)\).

\(\bullet\) Exercise \(273\)

Find the cycles of the permutations \(ρ\), \(\varphi_{1|3}\) and \(\varphi_{12|34}\) in the group \(D_4\).

Exercise \(274\)

Find the cycles of the permutation.

\(\binom{1\; 2\; 3\; 4\; 5\; 6\; 7\; 8\; 9}{3\; 4\; 6\; 2\; 9\; 7\; 1\; 5\; 8}\)

Exercise \(275\)

If two cycles of σ have an element in common, what can we say about them?

Problem 275 leads almost immediately to the following theorem.

Theorem \(\PageIndex{1}\)

For each permutation \(σ\) of a set \(S\), there is a unique partition of \(S\) each of whose blocks is the set of elements of a cycle of \(σ\).

More informally, we may say that every permutation partitions its domain into disjoint cycles. We call the set of cycles of a permutation the cycle decomposition of the permutation. Since the cycles of a permutation \(σ\) tell us \(σ(x)\) for every \(x\) in the domain of \(σ\), the cycle decomposition of a permutation completely determines the permutation. Using our informal language, we can express this idea in the following corollary to Theorem 6.1.1

Corollary \(\PageIndex{1}\)

Every partition of a set \(S\) into cycles determines a unique permutation of \(S\).

Exercise \(276\)

Prove Theorem 6.1.1.

In Problems 273 and 274 you found the cycle decompositions of typical elements of the group D4 and of the permutation

\(\binom{1\; 2\; 3\; 4\; 5\; 6\; 7\; 8\; 9}{3\; 4\; 6 \;2 \;9 \;7 \;1 \;5 \;8}\).

The group of all rotations of the square is simply the set of the four powers of the cycle \(ρ = (1 \;2 \;3\; 4)\). For this reason, it is called a cyclic group 3 and often denoted by \(C_4\). Similarly, the rotation group of an \(n\)-gon is usually denoted by \(C_n\).

\(\rightarrow\) Exercise \(277\)

Write a recurrence for the number \(c(k, n)\) of permutations of \([k]\) that have exactly \(n\) cycles, including \(1\)-cycles. Use it to write a table of \(c(k, n)\) for \(k\) between \(1\) and \(7\) inclusive. Can you find a relationship between \(c(k, n)\) and any of the other families of special numbers such as binomial coefficients, Stirling numbers, Lah numbers, etc. we have studied? If you find such a relationship, prove you are right. (Hint) .

\(\rightarrow \; \cdot\) Exercise \(278\)

(Relevant to Appendix C .) A permutation \(σ\) is called an involution if \(σ^2 = ι\). When you write down the cycle decomposition of an involution, what is special about the cycles?

1. What we are doing is restricting the rotation \(ρ\) to the set \(\{1, 2, 3, 4\}\)

2. The concept of a permutation group is a special case of the concept of a group that one studies in abstract algebra. When we refer to a group in what follows, if you know what groups are in the more abstract sense, you may use the word in this way. If you do not know about groups in this more abstract sense, then you may assume we mean permutation group when we say group.

3. The phrace cyclic group applies in a more general (but similar) situation. Namely the set of all powers of any member of a group is called a cyclic group.

Representations of Permutation Groups I

Representations of Wreath Products and Applications to the Representation Theory of Symmetric and Alternating Groups

• © 1971
• Adalbert Kerber

You can also search for this author in PubMed   Google Scholar

Part of the book series: Lecture Notes in Mathematics (LNM, volume 240)

3093 Accesses

90 Citations

3 Altmetric

This is a preview of subscription content, log in via an institution to check access.

Access this book

• Available as PDF
• Read on any device
• Instant download
• Own it forever
• Compact, lightweight edition
• Dispatched in 3 to 5 business days
• Free shipping worldwide - see info

Tax calculation will be finalised at checkout

Other ways to access

Licence this eBook for your library

Institutional subscriptions

Table of contents (4 chapters)

Front matter, introduction, wreath products of groups, representations of wreath products, application to the representation theory of symmetric and alternating groups, back matter.

• Alternierende Gruppe
• Kranzprodukt
• Representation theory
• Symmetric Groups
• Symmetrische Gruppe

Bibliographic Information

Book Title : Representations of Permutation Groups I

Book Subtitle : Representations of Wreath Products and Applications to the Representation Theory of Symmetric and Alternating Groups

Authors : Adalbert Kerber

Series Title : Lecture Notes in Mathematics

DOI : https://doi.org/10.1007/BFb0067943

Publisher : Springer Berlin, Heidelberg

eBook Packages : Springer Book Archive

Copyright Information : Springer-Verlag Berlin Heidelberg 1971

Softcover ISBN : 978-3-540-05693-5 Published: 01 January 1971

eBook ISBN : 978-3-540-37004-8 Published: 15 November 2006

Series ISSN : 0075-8434

Series E-ISSN : 1617-9692

Edition Number : 1

Number of Pages : X, 186

Topics : Group Theory and Generalizations

• Publish with us

Policies and ethics

• Find a journal
• Track your research

Help | Advanced Search

Mathematics > Representation Theory

Title: homogeneous spaces of semidirect products and finite gelfand pairs.

Abstract: Let $K\leq H$ be two finite groups and let $C\leq A$ be two finite abelian groups, with $H$ acting on $A$ as a group of isomorphisms admitting $C$ as a $K$-invariant subgroup. We study the homogeneous space $X\coloneqq\left(H\ltimes A\right)/\left(K\ltimes C\right)$ and determine the decomposition of the permutation representation of $H\ltimes A$ acting on $X$. We then characterize when this is multiplicity-free, that is, when $\left(H\ltimes A,K\ltimes C\right)$ is a Gelfand pair. If this is the case, we explicitly calculate the corresponding spherical functions. From our general construction and related analysis, we recover Dunkl's results on the $q$-analog of the nonbinary Johnson scheme.

Submission history

Access paper:.

• Other Formats

References & Citations

• Google Scholar
• Semantic Scholar

BibTeX formatted citation

Bibliographic and Citation Tools

Code, data and media associated with this article, recommenders and search tools.

• Institution

The Unique Burial of a Child of Early Scythian Time at the Cemetery of Saryg-Bulun (Tuva)

<< Previous page

Pages:  379-406

In 1988, the Tuvan Archaeological Expedition (led by M. E. Kilunovskaya and V. A. Semenov) discovered a unique burial of the early Iron Age at Saryg-Bulun in Central Tuva. There are two burial mounds of the Aldy-Bel culture dated by 7th century BC. Within the barrows, which adjoined one another, forming a figure-of-eight, there were discovered 7 burials, from which a representative collection of artifacts was recovered. Burial 5 was the most unique, it was found in a coffin made of a larch trunk, with a tightly closed lid. Due to the preservative properties of larch and lack of air access, the coffin contained a well-preserved mummy of a child with an accompanying set of grave goods. The interred individual retained the skin on his face and had a leather headdress painted with red pigment and a coat, sewn from jerboa fur. The coat was belted with a leather belt with bronze ornaments and buckles. Besides that, a leather quiver with arrows with the shafts decorated with painted ornaments, fully preserved battle pick and a bow were buried in the coffin. Unexpectedly, the full-genomic analysis, showed that the individual was female. This fact opens a new aspect in the study of the social history of the Scythian society and perhaps brings us back to the myth of the Amazons, discussed by Herodotus. Of course, this discovery is unique in its preservation for the Scythian culture of Tuva and requires careful study and conservation.

Keywords: Tuva, Early Iron Age, early Scythian period, Aldy-Bel culture, barrow, burial in the coffin, mummy, full genome sequencing, aDNA

Information about authors: Marina Kilunovskaya (Saint Petersburg, Russian Federation). Candidate of Historical Sciences. Institute for the History of Material Culture of the Russian Academy of Sciences. Dvortsovaya Emb., 18, Saint Petersburg, 191186, Russian Federation E-mail: [email protected] Vladimir Semenov (Saint Petersburg, Russian Federation). Candidate of Historical Sciences. Institute for the History of Material Culture of the Russian Academy of Sciences. Dvortsovaya Emb., 18, Saint Petersburg, 191186, Russian Federation E-mail: [email protected] Varvara Busova  (Moscow, Russian Federation).  (Saint Petersburg, Russian Federation). Institute for the History of Material Culture of the Russian Academy of Sciences.  Dvortsovaya Emb., 18, Saint Petersburg, 191186, Russian Federation E-mail:  [email protected] Kharis Mustafin  (Moscow, Russian Federation). Candidate of Technical Sciences. Moscow Institute of Physics and Technology.  Institutsky Lane, 9, Dolgoprudny, 141701, Moscow Oblast, Russian Federation E-mail:  [email protected] Irina Alborova  (Moscow, Russian Federation). Candidate of Biological Sciences. Moscow Institute of Physics and Technology.  Institutsky Lane, 9, Dolgoprudny, 141701, Moscow Oblast, Russian Federation E-mail:  [email protected] Alina Matzvai  (Moscow, Russian Federation). Moscow Institute of Physics and Technology.  Institutsky Lane, 9, Dolgoprudny, 141701, Moscow Oblast, Russian Federation E-mail:  [email protected]

Shopping Cart Items: 0 Cart Total: 0,00 € place your order

Price pdf version

student - 2,75 € individual - 3,00 € institutional - 7,00 €

Copyright В© 1999-2022. Stratum Publishing House

635th Anti-Aircraft Missile Regiment

635-й зенитно-ракетный полк

Military Unit: 86646

Activated 1953 in Stepanshchino, Moscow Oblast - initially as the 1945th Anti-Aircraft Artillery Regiment for Special Use and from 1955 as the 635th Anti-Aircraft Missile Regiment for Special Use.

1953 to 1984 equipped with 60 S-25 (SA-1) launchers:

• Launch area: 55 15 43N, 38 32 13E (US designation: Moscow SAM site E14-1)
• Support area: 55 16 50N, 38 32 28E
• Guidance area: 55 16 31N, 38 30 38E

1984 converted to the S-300PT (SA-10) with three independent battalions:

• 1st independent Anti-Aircraft Missile Battalion (Bessonovo, Moscow Oblast) - 55 09 34N, 38 22 26E
• 2nd independent Anti-Aircraft Missile Battalion and HQ (Stepanshchino, Moscow Oblast) - 55 15 31N, 38 32 23E
• 3rd independent Anti-Aircraft Missile Battalion (Shcherbovo, Moscow Oblast) - 55 22 32N, 38 43 33E

Disbanded 1.5.98.

Subordination:

• 1st Special Air Defence Corps , 1953 - 1.6.88
• 86th Air Defence Division , 1.6.88 - 1.10.94
• 86th Air Defence Brigade , 1.10.94 - 1.10.95
• 86th Air Defence Division , 1.10.95 - 1.5.98

• Yekaterinburg
• Novosibirsk
• Vladivostok

• Tours to Russia
• Practicalities
• Russia in Lists

Rusmania • Deep into Russia

Out of the Centre

Savvino-storozhevsky monastery and museum.

Zvenigorod's most famous sight is the Savvino-Storozhevsky Monastery, which was founded in 1398 by the monk Savva from the Troitse-Sergieva Lavra, at the invitation and with the support of Prince Yury Dmitrievich of Zvenigorod. Savva was later canonised as St Sabbas (Savva) of Storozhev. The monastery late flourished under the reign of Tsar Alexis, who chose the monastery as his family church and often went on pilgrimage there and made lots of donations to it. Most of the monastery’s buildings date from this time. The monastery is heavily fortified with thick walls and six towers, the most impressive of which is the Krasny Tower which also serves as the eastern entrance. The monastery was closed in 1918 and only reopened in 1995. In 1998 Patriarch Alexius II took part in a service to return the relics of St Sabbas to the monastery. Today the monastery has the status of a stauropegic monastery, which is second in status to a lavra. In addition to being a working monastery, it also holds the Zvenigorod Historical, Architectural and Art Museum.

Belfry and Neighbouring Churches

Located near the main entrance is the monastery's belfry which is perhaps the calling card of the monastery due to its uniqueness. It was built in the 1650s and the St Sergius of Radonezh’s Church was opened on the middle tier in the mid-17th century, although it was originally dedicated to the Trinity. The belfry's 35-tonne Great Bladgovestny Bell fell in 1941 and was only restored and returned in 2003. Attached to the belfry is a large refectory and the Transfiguration Church, both of which were built on the orders of Tsar Alexis in the 1650s.  

To the left of the belfry is another, smaller, refectory which is attached to the Trinity Gate-Church, which was also constructed in the 1650s on the orders of Tsar Alexis who made it his own family church. The church is elaborately decorated with colourful trims and underneath the archway is a beautiful 19th century fresco.

Nativity of Virgin Mary Cathedral

The Nativity of Virgin Mary Cathedral is the oldest building in the monastery and among the oldest buildings in the Moscow Region. It was built between 1404 and 1405 during the lifetime of St Sabbas and using the funds of Prince Yury of Zvenigorod. The white-stone cathedral is a standard four-pillar design with a single golden dome. After the death of St Sabbas he was interred in the cathedral and a new altar dedicated to him was added.

Under the reign of Tsar Alexis the cathedral was decorated with frescoes by Stepan Ryazanets, some of which remain today. Tsar Alexis also presented the cathedral with a five-tier iconostasis, the top row of icons have been preserved.

Tsaritsa's Chambers

The Nativity of Virgin Mary Cathedral is located between the Tsaritsa's Chambers of the left and the Palace of Tsar Alexis on the right. The Tsaritsa's Chambers were built in the mid-17th century for the wife of Tsar Alexey - Tsaritsa Maria Ilinichna Miloskavskaya. The design of the building is influenced by the ancient Russian architectural style. Is prettier than the Tsar's chambers opposite, being red in colour with elaborately decorated window frames and entrance.

At present the Tsaritsa's Chambers houses the Zvenigorod Historical, Architectural and Art Museum. Among its displays is an accurate recreation of the interior of a noble lady's chambers including furniture, decorations and a decorated tiled oven, and an exhibition on the history of Zvenigorod and the monastery.

Palace of Tsar Alexis

The Palace of Tsar Alexis was built in the 1650s and is now one of the best surviving examples of non-religious architecture of that era. It was built especially for Tsar Alexis who often visited the monastery on religious pilgrimages. Its most striking feature is its pretty row of nine chimney spouts which resemble towers.

Plan your next trip to Russia

Ready-to-book tours.

Your holiday in Russia starts here. Choose and book your tour to Russia.

REQUEST A CUSTOMISED TRIP

Looking for something unique? Create the trip of your dreams with the help of our experts.