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.
1
vote
0answers
29 views
Determine the number of cycles of the form $(\underline{6})(\underline{2})(\underline{2})$ in $S_9$
Consider a product of cycles of the form $(\underline{6})(\underline{2})(\underline{2})$ in $S_9$ where $(\underline{i})$ is a cycle with length $i$. I want to determine the number of such cycles.
...
1
vote
1answer
29 views
Restoring permutation from differences of adjacent elements
Suppose a permutation $\pi \in S_n$ is encoded by a list of integers $P=(p_1, p_2, ... p_{n-1})$, where $p_i = \pi(i+1) - \pi(i)$, i.e. $P$ is the list of differences of adjacent elements. Now, given $...
5
votes
2answers
80 views
How to calculate the Galois group of $x^5+15x+12$?
How to calculate the Galois group of $x^5+15x+12$ over the field $\Bbb Q$? Using the Tchebotarov Density theorem which states that "the density of primes $p$ for which $f(x)$ splits into type $T$ ...
1
vote
1answer
45 views
Writing $2$-cycles as a product of adjacent 2-cycles.
Problem: Consider the arbitrary 2-cycle $(a\ b)$ from $S_n$. Find a way to write this permutation as a product of adjacent 2-cycles.
What I do know:
A transposition is a single cycle of length 2. An ...
3
votes
2answers
36 views
Number of different cyclic permutations in a symmetric group
So a permutation cycle is written as $(a,b,c,d)$ where $a\to b\to c\to d\to a$, I would like to know the number of permutation cycles I can express $(a,b,c,d)$ such that the permutation cycles are ...
2
votes
1answer
20 views
Generating random permutation with N cycle
Suppose we have integer list from 1 to N. I am interested in generating random permutations such that its cycle notation has only one N cycle.
What algorithms are known to generate random N-cycle ...
-1
votes
1answer
39 views
Find the number of $6 \times 7$ matrices with entries $[0,1]$ such that their row and column sums are odd.
My attempt is quite handwaivy. But I think this has something to do with permutation matrices. I am absolutely new to this topic. can anyone throw any light on this solution?
I know there are $2^{n\...
2
votes
1answer
57 views
Find permutations whose third power is known
I have to find permutations $a$ such that $a^3=(1 \ 2)(3 \ 4)(5 \ 6)(7 \ 8 \ 9 \ 10)$
and I have to find at least 3 solutions.
So first I must find disjoint cycles.
Those are:
...
3
votes
1answer
36 views
Determine if exists a subgroup of order $3$ of $H=\langle\sigma^{8440}\rangle$
Consider the following permutation of $S_{13}$.
$\sigma=(1\;3\;13\;5\;11\;8)(2\;10\;4\;6\;12\;7\;9)$
Determine if exists a subgroup of order 3 of $H=\langle\sigma^{8440}\rangle$. If yes, exhibit it ...
0
votes
0answers
22 views
Multiplying Permutation Groups in Cycle Notation
I am given that f = (1 2 3 4 5 6) and g = (1 2). I am told to compute $f^2gf^4$. I know that $f^2 = (1 3 5)(2 4 6)$ and $f^4 = (1 5 3)(2 6 4)$. But I am having trouble computing the product of all ...
4
votes
2answers
55 views
Permutation group equation: $x^{20} = \sigma$
I need some help solving the next permutations group equation:
$$ x^{20} = \sigma $$ where
$$
\sigma = \begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & ...
1
vote
0answers
40 views
How many solutions does $x$ have in $x^3 = \sigma^6$ in $S_{7}$
Let $\sigma=\begin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 & 7 \\ 2 & 3 & 5 & 7 & 1 & 4 & 6\end{pmatrix} \in S_{7}.$
How many solutions does $x^3 = \sigma^6$...
2
votes
1answer
51 views
A question about cardinality of differences of subsets of $\{1,\cdots, n\}$
Let $n\in\mathbb{N}$ and for every $1\leq i\leq n$, let $A_i=\{1,\cdots, i\}$.
For every sequence of distinct numbers $i_1,\cdots,i_k\in\mathbb{N}$, let
$$M(i_1,\cdots,i_k)=(A_{i_1}\setminus A_{i_2})...
5
votes
1answer
117 views
Sylow 2 subgroups of S4
I am trying to find all the Sylow 2 subgroups of S4 using Sylow’s theorems. Now, I know that a Sylow 2 subgroup of S4 has size 8, and that there are either 1 or 3 of them (as the number of of Sylow 2-...
1
vote
1answer
30 views
Permutation and permutation matrices
When we want to define transformations using permutations, what are the subtle differencies betwen the use of permutation matrices, and the use of permutations?
Say I want to define a way to shuffle ...
1
vote
0answers
46 views
Proof of Determinant property via definition in linear algebra
Let A=$(a_{ij})_n$ be a square matrix & B=$(b_{ij})_n$ be another square matrix obtained after interchanging two rows of A, say $p^{th}$ and $q^{th}$. Then |B|=-|A|.
Proof Given:-
We have,
$b_{...
0
votes
2answers
37 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
27 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$. [closed]
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
30 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
72 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
26 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
43 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
34 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
31 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
56 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
314 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
18 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?...
5
votes
3answers
58 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
27 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
54 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
37 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
20 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
23 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 ...
2
votes
2answers
72 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
86 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
20 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
53 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
31 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
185 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
22 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
117 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
23 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
53 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
93 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
20 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
47 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
30 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
44 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?
