Stack Exchange Network

Stack Exchange network consists of 174 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [permutation-cycles]

For elementary questions concerning permutation cycles and permutation groups. This includes all representations of permutations (two-line arrays, cycles, bipartite graphs); transpositions and the sign/parity of a permutation; the Symmetric group and the Alternating group. To be used with the (permutations) tag to make the distinction between abstract algebra permutation questions and combinatoric permutation questions.

0
votes
2answers
26 views

Compositions & Transpositions of permutations

Consider the set of all permutations $S_n$. Fix an element $\tau\in S_n$. Then the sets $\{\sigma\circ\tau\mid \sigma\in S_n\}= \{\tau \circ\sigma\mid \sigma\in S_n\}$ have exactly $n!$ elements. ...
1
vote
1answer
21 views

Given a cycle $c \in S_n $ with $ ord(c) = s $ and $ s = kt $, prove that $c^k$ is a product of $k$ cycles of length $t$. [on hold]

I came across this question in a recent exam. Given that $ ord(c) = s $, we assume that $c^s = c^{kt} = (id) \implies (c^{k})^t = (id)$. That means that $c^k$ is a cycle of order $t$. Can you ...
2
votes
1answer
19 views

On terminology; what is meaning of the “decrement” of a permuation? (or what is the alternative word or phrase used for this definition)

I am currently studying some lecture notes in Russian and I frequently look up the theorems and topics in English for better understanding (I'm not a native Russian so I merely just use the Russian ...
1
vote
2answers
63 views

In how many ways can 3 employees visit 40 locations

Three employees need to visit 40 different cities under the following conditions: each location should be visited by exactly one employee, and no location should be visited multiple times. The travel ...
0
votes
1answer
25 views

Permutation as string position recording in Wilson's FSG book

I'm reading Wilson's The Finite Simple Group book, mainly the Alternating group chapter, which explains the splitting criterion quite in detail. While heading there, I came across a possible ...
1
vote
1answer
34 views

On the product of two cycles (and its conjugates)

So this is from Charles C. Pinter's "A Book of Abstract Algebra"- specifically, it's from the second chapter on permutations. The question is: Let $\alpha_1$ and $\alpha_2$ be cycles of the same ...
1
vote
1answer
28 views

Geometrical meaning of A4 conjugacy classes of elements of order 3

I know that elements of order 3 in A4 group split into two separate conjugacy classes, due to lack of odd elements to form a unique class like happens in the full S4. Since A4 is the rotation ...
0
votes
1answer
16 views

Proving the sign map is a homomorphism

Definition: A transposition is a 2-cycle permutation. Definition: A permutation $\sigma$ is called even if its decomposition into transpositions has even number of transpositions; analogously for odd ...
1
vote
1answer
52 views

The centralizer of a cycle is the group generated by the elements of $S_n$ that are disjoint from the cycle and the group generated by the cycle.

I am having a hard time trying to prove that the centralizer of a cycle is the group generated by the elements of $S_n$ that are disjoint from the cycle and the group generated by the cycle. It is ...
4
votes
1answer
131 views

Number of homomorphisms between two arbitrary groups

How many homomorphisms are there from A5 to S4 ? This is how I tried to solve it. If there is a homomorphism from A5 to S4 , then order of element of S4 should divide the order of its preimage. Now ...
0
votes
1answer
16 views

commutativity of cycle permutations [closed]

How is the following true, (given two cycle permutations a and b) $(a)^{-1} (b)^{-1} = ((b)(a))^{-1}$ where b and a contain one of the same elements. isn't it only disjoint cycles that are commutative?...
4
votes
3answers
46 views

Explanation of an unexpected observation in modular arithmetic

Let the multiplication graph $n:m$ be the graph with $m$ points equally distributed on a circle and a line between points $a$ and $b$ when $n\cdot a \equiv b\operatorname{mod} m$. Looking at the ...
0
votes
1answer
26 views

Alternate definition of symmetric group action [duplicate]

Let $S_3$ act on $\Re^3$ by the permutation matrices P(σ), where P(σ) permutes the basis vectors: $$P(σ)(e_i) = e_{σ(i)}$$ Show that, with this formula, $$\sigma(x_1,x_2,x_3) = P(\sigma)(x_1e_1 + ...
2
votes
3answers
52 views

Let $n$ be an odd positive integer and $a\in S_n$ be an $n$-cycle. Show that the order of $C(a)$ must be odd.

I am working on the following problem from group theory: If $n$ is odd and $a\in S_n$ is an $n$-cycle, $a=(a_1,a_2,......,a_n)$, show that no element of the centralizer $C(a)=\{g\in S_n \mid ga=ag\}...
2
votes
1answer
35 views

Find the conjugacy class $O_{(234)}$ if $G=A_{4}$ is acting on itself by conjugation.

Find the conjugacy class $O_{(234)}$ if $G=A_{4}$ is acting on itself by conjugation. I calculated $(x)(234)$ for all $x\in A_{4}$ and got the set $O_{(234)}=\left \{(234), (143), (142), (123), (132)\...
1
vote
1answer
19 views

Compute all $X_{g}$ and all $G_{x}$ for $X = \left \{1, 2, 3\right \}$, $G = S_{3} = \left \{(1), (12), (13), (23), (123), (132)\right \}$.

Compute all $X_{g}$ and all $G_{x}$ for $X = \left \{1, 2, 3\right \}$, $G = S_{3} = \left \{(1), (12), (13), (23), (123), (132)\right \}$. Can someone give me a head start to this problem? $X_{g}=\...
0
votes
1answer
21 views

Order and sign of a cycle

I would usually show workings or attempts of a method when posting a question here, but for this I am completely lost. I don't believe it to be a very hard question but it is as follows: Determine ...
1
vote
2answers
66 views

Cycle structure of the permutation $x \mapsto p·x\operatorname{mod}q$ for coprime $p,q$

Let $[q] = \{0,\dots,q-1\}$, $p < q$. Consider the function $\mathbf{p}: [q] \rightarrow [q]$ which sends $x \mapsto p·x\operatorname{mod}q$, i.e. the multiplication by $p$ modulo $q$ on $[q]$. ...
1
vote
1answer
65 views

Permutations and terminology

Say I have the following permutation $$\sigma ={\begin{pmatrix}1&2&3&4&5&6&7&8\\1&2&3&8&4&5&6&7\end{pmatrix}}$$ which consists to let ...
0
votes
1answer
17 views

find all $x \in S_5$ such that $x^3 = (12)$

So I have to find all $x \in S_5$ such that $x^3 = (12)$. For example, one solution would be $(12)$ itself, because its order is $2$. How can I find all of the solutions though? Is it just trial and ...
1
vote
1answer
51 views

Express (1,…,n) as a product of 2-cycles

In Alan F. Beardon's "Algebra and geometry" he asks in an exercise to express $(1\ \ldots\ n)$ as a product of two cycles: Show that $(1\ 2\ 3\ 4)=(1\ 4)(1\ 3)(1\ 2)$. Express $(1\ 2\ 3\ 4\ 5)$ as ...
0
votes
1answer
29 views

Definition of a permutation as product of cycles

I am having trouble with the following passage of "Algebra and Geometry" by Alan F. Beardon in the highlighted part. I've read it several times but I do not understand what he is saying. Can you give ...
5
votes
3answers
184 views

Passing a binary message to a friend where one of the components is always “turned on”

Suppose I want to communicate an integer to a friend between 1 and 1000. In order to pass this message I use a $k$-vector whose entries can be set to $0$ or $1$. So for example if $k=3$, a natural way ...
1
vote
1answer
19 views

(Permutations) For $n ≥ 2$,there are at least n subgroups of Sn of order $(n − 1)!$

For $n ≥ 2$, show that there are at least n subgroups of Sn of order $(n − 1)!$
0
votes
0answers
15 views

Number of derangements using PIE

The statement of Principle of Inclusion and Exclusion that I have been given is $card(X$ \ $(\bigcup\limits_{i=1}^{\infty} A_{i}))=\sum\limits_{I\subseteq[n]}(-1)^{card(I)}card(A_I)$ $A_I=\...
0
votes
0answers
60 views

How many cuboids can be created using 125 unit cubes

A $5\times 5\times 5$ cube is built using unit cubes.How many different cuboids(that differ in at least one unit cube) can be formed using the same number of unit cubes. My Attempt: Let $x_{i}$ units,...
0
votes
1answer
22 views

Show that $\tau (18632)(47) \tau^{-1} = (12345)(67)$.

Example 4.7. of Aluffi's Algebra says In $S_8$, $(18632)(47)$ and $(12345)(67)$ must be conjugate since they have the same type. So there there exist $\tau$ such that $\tau (18632)(47) \tau^{-1} = (...
1
vote
1answer
47 views

Combinatorics: Number of permutations from $1$ to $60$, with cyclic permutation of length $l > 30$

In a game, $60$ kids have the chance to win presents. The organiser gives every kid a number between $1$ and $60$, so that all kids have different numbers. In a room, there is a cupboard with $60$ ...
4
votes
3answers
79 views

How to prove that an even permutation of $A_n$ is a square of another permutation from $S_n$?

I am trying to go through a proof which contains a statement that an even permutation from $A_n$ is a square of another permutation from $S_n$. My basic ideas are like this: Suppose an even ...
-1
votes
1answer
46 views

Prove: two elements in the group of permutations satisfy A^2 = B^2 then A = B.

How does one prove when two cycles in the group of permutations satisfy A^2 = B^2 that A = B? I think the fact the inverses A_*A = e and A_ = A^(l-1) and A = A^(l+1) is useful. l is the length of ...
2
votes
2answers
19 views

How is the permutation relationship interpreted

I was given the example as an illustration of structure of permutations in my lecture notes on algebra as shown below: $\bigl(\begin{smallmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 &...
0
votes
0answers
45 views

All permutations carrying the set {1,2} into the set {1,2}

Book question: Describe the following subgroups of $S_4$ and determine the number of elements in each subgroup: a) All permutations carrying the set {1,2} into the set {1,2} My question: ...
2
votes
0answers
27 views

Help understanding the permutation group action .

I'm trying to understand actions in regards to group theory . specifically in my notes I found the following example : Say G=$A_4$, for $x \in \{1,2,3,4\}$, and $\tau \in A_4$ We let $x^{\tau}$ be ...
0
votes
1answer
43 views

Existence of a permutation consisting of exactly two cycles for odd prime

Is it true that if p is an odd prime number, then there exists some integer a such that the permutation of Ф(p) induced by multiplication by a mod p consists of exactly 2 cycles?
1
vote
1answer
31 views

Counting permutation cycle types in $S_n$

Consider the sym group $S_4$, We write the elements of $S_4$ in a given "form" such as \begin{align*} e = (1)(2)(3)(4) &\sim 1,1,1,1 \\ (12)(34) &\sim 2,2 \\ (123)(4) &\sim 3,1 \end{...
1
vote
1answer
42 views

number of permutations of length 20 whose longest cycle is of length 11?

What is the number of permutations of length 20 whose longest cycle is of length 11? We first choose 11 from 20 in $\binom{20}{11}$ and the cyclic ordering can be done in $10!$ ways, for the ...
0
votes
2answers
45 views

Permutations that commute with a given transposition

I have to count how many permutations $\sigma \in S_n$ commute with a transposition $(i, j), i \neq j$. My guess is that any $\sigma$ that doesn't contain $(i, j) $ in its cycle decomposition works, ...
1
vote
1answer
71 views

What is the number of $(2n)$-permutations whose longest cycle is of length $n$? (verification)

There are ${\large{\binom{2n}{n}}}$ ways to choose $n$ elements for an $n$-cycle, and there are $(n-1)!$ ways to arrange the elements of this cycle. The rest can be arranged in any number of cycles, ...
0
votes
1answer
27 views

Left cosets of $S_4, H= \lbrace \epsilon, (12)(34), (13)(24), (14)(23) \rbrace$

These are my left cosets so far, according to Lagrange's Theorem I am missing one more left coset right? \begin{align*} \\(1234)H=&\lbrace (1234), (13), (1432), (24) \rbrace=(13)H=(1432)H=(24)H \\...
1
vote
4answers
53 views

Permutation group products (23)(12)(34)=(1243)?

I just wanted to ask why it makes sense that $(23)(12)(34)=(1243)$. Note I'm going from right to left. I'm trying to understand the concepts trying to find a true "method" to follow in all cases. My ...
0
votes
0answers
13 views

Using WolframAlpha to check cycle products for figuring out L/R cosets

I've been told and have noticed that WolframAlpha computes the order of elements a little differently than my class. How would I plug in multiple cycles so that I can check my work? I have noticed ...
1
vote
1answer
40 views

Let $\sigma\in S_n$ be an $n$-cycle, and let $\tau\in S_n$ be a $2$-cycle.Then, $\sigma$ and $\tau$ need not generate $S_n$.

Let $\sigma\in S_n$ be an $n$-cycle, and let $\tau \in S_n$ be a $2$-cycle. Show by constructing a counterexample that $\sigma$ and $\tau$ need not generate $S_n$. This problem is driving me crazy. I ...
9
votes
2answers
78 views

Elements of $S_n$ can be written as a product of $k$-cycles.

Let $k\leq n$ be even. Prove that every element in $S_n$ can be written as a product of $k$-cycles. I really have no idea how to go about this. My initial intuition was to proceed by induction first ...
1
vote
1answer
32 views

Relationship between order of $(x,y)$ in $G \times G'$ and order of disjoint permutations, which both involve LCMs?

The following is an exercise from Artin's Algebra: (Kiefer Sutherland's voice) Let x be an element of order r of a group G, and let y be an element of G' of order s. What is the order of $(x, y)$ ...
1
vote
1answer
44 views

Why did this reversal from the left cosets of $\langle (1, 2, 3) \rangle$ in $A_4$ give me the right cosets?

In this question How to derive the cosets of $A_4$? I derived that the left cosets are $$\{ 1\langle (1, 2, 3) \rangle, (143)\langle (1, 2, 3) \rangle, (142)\langle (1, 2, 3) \rangle, (341)\langle (1,...
1
vote
0answers
49 views

Abstract Algebra Proof with cycles and transpositions

Let s be a permutation from Sn, for some n. Consider standard (unique) representation of s as a product s1s2...sk of independent cycles and let dec(s) be the decrement of s. Let (ij) be arbitrary ...
0
votes
3answers
65 views

Prove $(\rho_1 \rho_2 \cdots \rho_r)^u = e \implies e=\rho_1^u=\rho_2^u=\cdots=\rho_r^u$

In the proofwiki page: Order of Product of Disjoint Permutations We have a product of disjoint permutations $\pi = \rho_1 \rho_2 \cdots \rho_r$. Why exactly is it that if $\pi^u=e$, then for each $\...
0
votes
1answer
31 views

Question on generating sets of $S_n$

This is the question: Decide whether the following sets generate $S_n$ or not: The set of 2-cycles in $S_n$ The set of even permutations in $S_n$ The set of odd permutations in $S_n$ ...
2
votes
2answers
32 views

Products of permutation cycles

Hey guys im having trouble understanding how to calculate products of permutation cycles, especially when its several 2 or 3 cycles in a row, I have a few short questions here with the answers, but I ...
1
vote
0answers
38 views

If P is an nxn permutation matrix, is there an upper bound on k such that $P^k = I$?

So if P is an nxn permutation matrix, then because there are only finitely many ways to permute finitely many elements, we know that the sequence $P, P^2, P^3, ...$ eventually has to repeat, between ...