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.

Filter by
Sorted by
Tagged with
2 votes
1 answer
35 views

Coloring $5 \times5$ transparent chessboard in space.

We have $5 \times 5$ chessboard floating in space , so rotation and reflection are allowed. We want to color it using $m$ distinct colors such that when we color a square , the both sides of that ...
user avatar
2 votes
1 answer
81 views

Placing red and black colors on $2 \times 4$ chessboards

Suppose that two chessboards are also considered equivalent (aside from rotational symmetry) if one can be obtained from the other by complementing red and black colors. How many different $2 × 4$ ...
user avatar
1 vote
1 answer
58 views

Rotations of cube.

Here shows a cube with base touching face edges' vertices as: $\{3,7\},\{7,8\}, \{8,4\}, \{4,3\}.$ The opposite face has edges' vertices $\{1,2\},\{2,6\}, \{6,5\}, \{5,1\}.$ It states the below : $$x =...
user avatar
  • 4,135
2 votes
1 answer
217 views

Any algebraic way to check valid permutations on a cube?

Want to check if a given permutation: $(17)(35)(28)(46)$ is valid? By a valid permutation mean a permutation, which is also a symmetry of the cube (or oriented cube). The only way I know is: drawing a ...
user avatar
  • 4,135
-2 votes
1 answer
138 views

Compute the number of distinct actions of cyclic group $C_n$ on a set $X,$ s.t $|X|= n+1.$

There are $n+1C_n = n+1$ combinations possible, with $n!/n= (n-1)! $ orderings possible in each; leading to a total of $(n+1).(n-1)!$. Let $n= 6.$
user avatar
  • 4,135
0 votes
1 answer
117 views

Number of different ways to get permutations of disjoint cycles of given length.

This question is derived (as want to derive the formula for below problem, and also general approach) from : Compute the number of distinct actions of $C_m$ on set $X,$ s.t. $|X|= n= 2m+1.$ Let ...
user avatar
  • 4,135
2 votes
0 answers
29 views

Central Limit Theorem for number of cycles. Proof Lloyd and Shepp

I am studying the proof of Lloyd and Shepp of the central limit theorem for number of cycles in random permutations. (paper can be found here https://www.ams.org/journals/tran/1966-121-02/S0002-9947-...
user avatar
  • 369
-1 votes
0 answers
19 views

Factorize permutation matrix for Lex-order permutations

Lexicographical order permutations of numbers $1...n$ are the following (for $n = 4$): $1234, 1243, 1324, 1342, 1423, 1432, 2134, 2143, ... 4321$ My goal is to quickly compute the k-th lex-order ...
user avatar
  • 231
1 vote
2 answers
34 views

Permutation of set

Suppose I have a set which contain finite elements from $1,2,\dots,n$, where $n$ is odd. Let there are two permutations $(a_1,a_2,\dots,a_n)$ and $(b_1,b_2,b_3,\dots,b_n)$ defined on this set. Now I ...
user avatar
  • 11
2 votes
1 answer
52 views

Permutation property of "law of cosines" stated more compactly through abstract algebra

The law of cosines, stated: $c^2 = a^2 + b^2 - |a||b|\cos(\gamma)$ is a result that still holds if we swap the side-lengths and the corresponding angle. Is there a way to capture this symmetry from a ...
user avatar
1 vote
1 answer
50 views

Mastery over the groups $S_n,A_n,D_n$ and $Q_8$

I am a graduate student and currently preparing for PHD entrance in the leading institutes of India. For that I have to strengthen my group theory. But I must admit that I have a shaky foundation in ...
user avatar
0 votes
2 answers
69 views

Show $(abcde)$ is the cube of a $5$-cycle.

Show $(abcde)$ is the cube of a $5$-cycle. Let $x^3= (abcde).$ $$x^3 = \begin{pmatrix} a & b & c & d & e \\ b & c & d & e & a\end{pmatrix} \implies (abcde)$$ Taking ...
user avatar
  • 4,135
2 votes
1 answer
63 views

Number of permutations of $\{1, 2, \dots, n\}$ with $1$ in an even cycle?

How many permutations of $\{1, 2, \dots, n\}$ are there, such that $1$ is in a cycle of even length? I tried to solve it by using canonical cycle decomposition (i.e. we rotate every cycle so that it ...
user avatar
3 votes
1 answer
93 views

Conjugation of a permutation

Let $$ \sigma = (1\ 2\ 4), \tau =(1 \ 2 \ 5 \ 3) \ (4\ 7\ 6) $$ where $\sigma, \tau \in S_7$. Based on e.g. this answer, I think it should be the case that: $$ \tau \sigma \tau^{-1} = (\tau(1)\ \tau(...
user avatar
2 votes
1 answer
118 views

4 different colour balls, each of number four have to be arranged in a circular manner so that adjacent 3 balls are of different colour.

I have 4 red balls, 4 green balls, 4 Blue balls and 4 Yellow balls with me. I have to arrange them in a circular manner. The condition is that if we take any 3 adjacent balls, they should have to be ...
user avatar
  • 151
2 votes
1 answer
55 views

Subgroup of $A_n$ generated by a 3-cycle and an n-cycle

As pointed out here, an $n$-cycle $a=(12\ldots n)$ and a 3-cycle $b=(147)$ won't generate $A_n$ if n is an odd multiple of 3, at least for $n=9$. How do we calculate the structure and order of this ...
user avatar
  • 511
0 votes
0 answers
23 views

Faces of soccer/football as cycles of vertices?

In this question, I asked for help finding the adjacency matrix for a truncated icosahedron. (There are two good answers there). Now I have a related question. Is there a resource for listing the ...
user avatar
  • 133
10 votes
2 answers
221 views

Prove that $\Gamma_{abc}=\frac{1}{2}\left(\partial_bg_{ac} + \partial_cg_{ab}-\partial_ag_{bc}\right)$

I am tasked with the following problem Use the equation $$\nabla_ag_{bc}=\partial_ag_{bc}-\Gamma_{cba}-\Gamma_{bca}=0\tag{1}$$ where $$\Gamma_{abc}=g_{ad}\Gamma^d_{bc}\tag{A}$$ and the (no torsion) ...
user avatar
  • 565
1 vote
0 answers
41 views

Counting permutation cycle types

I have a permutation matrix $\sigma_\alpha$, corresponding to a permutation $\alpha \in S_n$, from which I construct the larger permutation matrix $\sigma_2 = \left[\begin{array}{cc} 1& \mathbf{0}^...
user avatar
  • 245
2 votes
2 answers
69 views

Need Help With Using Cycle Permutation to Rotate Squares

I'm a high school math teacher and I'm working with some calculus students who are exploring other areas of math for an end-of-year project. I thought I would introduce them to some basic group theory ...
user avatar
  • 21
0 votes
0 answers
70 views

Alternating groups and linear groups

I learned from the literature that the symmetric group $S_n$ can be viewed a subgroup of permutation matrices of $GL_n(q)$ (where $q$ is a prime power), the general linear group of invertible $n\times ...
user avatar
4 votes
0 answers
99 views

Average number of the maximum amount of fixed points of permutation in a partition of $S_n$

Consider the symmetric group $S_n$ and, for each $\sigma \in S_n$, let $f(\sigma)$ be the number of fixed points of $\sigma$. Now let $g$ be the permutation such that $g(i)=i+1$ for $i=1,...,n-1$ and $...
user avatar
2 votes
2 answers
78 views

Given a permutation $\sigma = (13)(254)$, state $\sigma^2$.

Given a permutation $\sigma = (13)(254)$, state $\sigma^2$. $\sigma = (13)(254), \sigma^2=(13)(254)(13)(254) = (13)(13)(254)(254) = (425) $ Or, in two row format, get: $$ \sigma = \begin{pmatrix} 1 &...
user avatar
  • 4,135
0 votes
0 answers
77 views

How many permutations $\theta$ on $\{1,2,3,4\}$ have $\theta(4)=4$.

How many permutations $\theta$ on $\{1,2,3,4\}$ have $\theta(4)=4$. Request vetting In permutations, always have bijective mappings. After fixing one element have options available: $=3,$ for first ...
user avatar
  • 4,135
1 vote
1 answer
28 views

Solving equations in permutation group

Given a relation on a permutation group $S_n$, I'm interested in solving for an unknown permutation. For a concrete example, let's say $\sigma_1=(12)\in S_3$ (in cycle notation), and the relation is $$...
user avatar
  • 2,491
1 vote
0 answers
108 views

Find the permutation $\sigma$ given the permuation $\sigma^n$

Given a permutation $\sigma^n$ for certain $n$ in $N$, find the permutation $\sigma$ This is the proof, but i dont seem to understand it fully. Given $\sigma^n$ for a certain $n$, how do we find $\...
user avatar
  • 31
0 votes
0 answers
26 views

Pseudorandom permutation of 60000 elements with a long period

I have a programming assignment that asks me to do mini-batch training. In particular, we are working with the MNIST dataset, which contains 60000 training samples. I would like to figure out the most ...
user avatar
  • 674
0 votes
0 answers
35 views

Help understanding products of permutation cycles.

In Thomas Hungerford's "Abstract Algebra - An Introduction" he is giving following examples of products of cycles of permutations: $(567)^2=(576)$ $(1234)=(12)(23)(34)$ $(1243)(243)=(23)(34)...
user avatar
  • 183
0 votes
0 answers
33 views

Diagonalizing a matrix that is close to a circulant one in symmetry

Recently encountered a matrix that looks similar to a circulant, and in case of a $5\times 5$ matrix, we have: $$ A = \begin{pmatrix} \omega^0 c_0 & \omega^1 c_1 & \omega^2 c_2 & \omega^3 ...
user avatar
  • 446
-1 votes
1 answer
46 views

Prove that $S_n=⟨(12),(23),...,((n-1)n)⟩$.

Assume we know that $S_n=⟨(12),(13),...,(1n)⟩$, then prove $S_n=⟨(12),(23),...,((n-1)n)⟩$ I didn't understand this proof below: For $i=2$ at $(1 \ i)$ so $(1 \ i) \in S_n$, then assuming that $(1 \ i)$...
user avatar
0 votes
0 answers
35 views

show that $x^3 = (1234)$ in $S_7$ has three solutions (and find them?) [duplicate]

As title. This is question 52 in Chapter 5 of Gallian’s Abstract Algebra, 10th edition. My current line of logic is as follows. We have $x^3 = (1234)$, which gives us $|x^3| = 4$, implying that $|x| = ...
user avatar
9 votes
1 answer
141 views

Permutation Groups: Find $x$ such that $x^5 = (12345)$

I am wondering about how to solve question 35 from chapter 5 (Permutation Groups) from the 10th edition of Gallian’s Abstract Algebra. The full question is as follows: What is the smallest $n$ for ...
user avatar
0 votes
1 answer
47 views

group presentation with circularly shifted relator

Let $G=\langle S \mid R_1 \cup R_2 \cup R_3 \rangle$ be a group presentation with $S=\{a,b,c\}$, $R_1=\{aa{^{\text{-}1}}, bb{^{\text{-}1}}, c^2\}$, $R_2$ the set of all circular shifts of the word $w=...
user avatar
  • 35
0 votes
1 answer
36 views

Multiplication of permutation Cycles

I was doing example 1 Page 94 from Joseph A Gallian , In question it was given $\alpha = (231)$ and $\beta = (132) $ and then on next page there is $$ \alpha\beta = (21) $$ . So if we think ...
user avatar
  • 968
0 votes
0 answers
16 views

Need help in understanding that any permutation can be written as transposition [duplicate]

Can someone help me understand the following theorem? Every cycle of length greater than 2 can be expressed as a product of transpositions.
user avatar
  • 107
0 votes
0 answers
33 views

How do I represent hexagons (or any polygon really) so that they are equal independent of rotation?

I am working on a private coding project. My program works with hexagons, which edges have certain features. I currently represent these hexagons using arrays with one entry for each edge. There is a ...
user avatar
  • 1
1 vote
0 answers
47 views

Enigma and Rejewski's theorems (Permutation-Cycles)

Rejewski stated the following Theorem on the Products of Transpositions If two permutations of the same degree consist solely of disjoint transpositions, then their product will consist of disjoint ...
user avatar
0 votes
1 answer
42 views

Can the matrix representation of a product of disjoint cycles be made up of the matrix representation of each cycle?

Let $\rho \in S_n$ be a permutation and its matrix representation be $M(\rho)$ where $M: S_n \rightarrow GL(\mathbb{C}^n)$. Then writing out $M(\rho)$ is very easy. But now if we represent $\rho$ as ...
user avatar
  • 55
1 vote
0 answers
28 views

How does the cycle structure of a sub-set of permutations change under a particular mapping?

Let $n \ge 1$ be an integer. Denote by $\Pi^n $ the group of permutations of $\left\{1,\cdots,n\right\}$ and by $\Pi^{(2)}_{2n}$ the subset of all permutations of $\{1,\cdots, 2n \}$ that are composed ...
user avatar
  • 9,143
2 votes
1 answer
40 views

Choose a sitting order that is fine for all people, with privacy

I'm looking for a pen and paper algorithm that will output (if possible) a way to sit around a table that is acceptable to all participants, while preserving as much privacy as possible in who finds ...
user avatar
  • 269
0 votes
0 answers
33 views

How can I find the order of a function defined on a symetric group?

I have the following question, but don't know how to start for finding order of a function defined on a symetric group. Question: Consider the symetric group $S_X$ on the set $ X = \mathbb{R} - \{0, 1\...
user avatar
  • 47
0 votes
0 answers
23 views

Prove or disprove: $S_4$ can be generated by two 3-cycles. [duplicate]

Prove or disprove: $S_4$ can be generated by two 3-cycles. So I think this is a proof. Since 3-cycles can be written as the product of simple transpositions, 2 3-cycles can make up the simple ...
user avatar
  • 377
0 votes
1 answer
38 views

Cyclic notation and product of transpositions

$p=(1234)$ means that $p$ sends $1$ to $2$, $2$ to $3$, $3$ to $4$ and $4$ to $1$. But I dont understand why $p$ is also equal to $(12)(13)(14)$. Isn't that imply $p(1)=2=3=4$?
user avatar
0 votes
1 answer
59 views

show $(k\:\:k+1)$ generates $(1\:\:x)$

Show $A=\{(k\:\: k+1), 1≤ k<n\}$ generates $B=\{(1\:\:x), 1<x≤ n\},$ where $B$ is a minimal generating sets for $S_n$. So I want to show $(k\:\:k+1)$ generates $(1\:\:x)$. I want to use ...
user avatar
  • 409
1 vote
1 answer
84 views

Show least generating set of $S_n$

Let $n ≥ 2$ and define $V =$ { $x , x+1: 1 ≤ x < n$}. Show $V$ generates $S_n$ and that it is a minimal generating set for $S_n$. I'm having a hard time with this. But I do have some ideas on how ...
user avatar
  • 409
1 vote
0 answers
45 views

How do I show that any cycle of length $n$ can be rewritten as a product of $n-1$ transpositions $(1 \; \; 2),(2 \; \; 3),...,(n-1 \; \; n)$?

The problem is from "Notes on Geometry" by Rees. Show that any $\sigma \in S_n$ can be writen as a product involving only the $(n-1)$ transpositions $(1,2),(2,3),...,((n-1),n)$. Note: In ...
user avatar
  • 1,220
0 votes
1 answer
56 views

Find the conjugacy classes of $(123), (132) \in S_3$

Find the conjugacy classes of $(123), (132) \in S_3$. I could work out for {e} and [(12)]={(12),(13),(23)}. But I'm struggling to compute the conjugacy class for (123).. Can somebody point out any ...
user avatar
2 votes
1 answer
206 views

Prove that the number of even and odd permutations in $S_n$ is equal using maps

So I'm looking to prove that the number of even permutations is equal to the number of odd permutations in $S_n$ I want to prove this using the fact that the map: $\alpha: S_n \to C_2$ defined as $(\...
user avatar
0 votes
0 answers
20 views

Conjugated elements of $S_n$ for $n\geq 1.$

If $n\geq 5.$ Prove for all $(ab)(cde)$ of $S_n$ (with different $a,b,c,d,e$) are conjugated. My proof is the following: Given $\alpha=(a_1b_1)(c_1d_1e_1)$ y $\beta=(a_2b_2)(c_2d_2e_2)$, then \begin{...
user avatar
-1 votes
1 answer
39 views

Find $k>0$ such that two permutations conjugate and are different from the identity permutation

I am given two permutations in $S_{10}$: $$\alpha = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\ 5 & 4 & 8 & 6 & 7 & 10 &...
user avatar

1
2 3 4 5
11