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.
541
questions
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 ...
user1086846
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$ ...
user1086846
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 =...
- 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 ...
- 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.$
- 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 ...
- 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-...
- 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 ...
- 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 ...
- 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 ...
- 35
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 ...
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 ...
- 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 ...
- 563
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(...
- 265
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 ...
- 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 ...
- 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 ...
- 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) ...
- 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}^...
- 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 ...
- 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 ...
- 23
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 $...
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 &...
- 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 ...
- 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
$$...
- 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 $\...
- 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 ...
- 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)...
- 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 ...
- 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)$...
- 79
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| = ...
- 605
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 ...
- 605
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=...
- 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 ...
- 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.
- 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 ...
- 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 ...
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 ...
- 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 ...
- 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 ...
- 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\...
- 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 ...
- 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$?
- 65
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 ...
- 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 ...
- 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 ...
- 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 ...
- 369
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 $(\...
- 101
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{...
-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 &...
- 133