Mathematics Stack Exchange
Mathematics 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.

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 to make the distinction between abstract algebra permutation questions and combinatoric permutation questions.

613 questions
26
votes
2 answers

How to find the square root of a permutation

Observe that $$\begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix} \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 2 & 4 & 1 & 5 & 3 \end{pmatrix} = \begin{pmatrix} 1 & 2 & 3 & 4 & 5 \\ 4 & 5 & 2 & 3 & 1 \end{pmatrix},$$ so…
Ashot
  • 4,673
  • 3
  • 32
  • 57
23
votes
2 answers

What are the properties of eigenvalues of permutation matrices?

Up till now, the only things I was able to come up/prove are the following properties: $\prod\lambda_i = \pm 1$ $ 0 \leq \sum \lambda_i \leq n$, where $n$ is the size of the matrix eigenvalues of the permutation matrix lie on the unit circle I am…
Salvador Dali
  • 2,525
  • 5
  • 25
  • 43
13
votes
2 answers

What is the fractal dimension of the image given by a combinatorial sequence about permutation cycles?

OEIS sequence A186759 is a triangle read by rows: $T(n,k)$ is the number of permutations of $\{1,2,\dots,n\}$ having $k$ nonincreasing cycles or fixed points, where a cycle $(b_1\ b_2\ \cdots\ b_m)$ is said to be increasing if, when written with…
Peter Kagey
  • 4,930
  • 10
  • 34
  • 87
13
votes
2 answers

Number of homomorphisms between two arbitrary groups

How many homomorphisms are there from $A_5$ to $S_4$ ? This is how I tried to solve it. If there is a homomorphism from $A_5$ to $S_4$ , then order of element of $S_4$ should divide the order of its preimage. Now what are the possible order of…
Karthik
  • 301
  • 2
  • 12
12
votes
2 answers

Why do the triangular numbers initially form long cycles mod $2^k$?

As discussed at Triangular numbers ($\text{mod } 2^n$) as a permutation of $\{0,1,2,\dots,2^n-1\}$ and What is the set of triangular numbers mod $n$?, mapping the integer $n$ for $0\le n\lt2^k$ to the residue of the corresponding triangular number…
joriki
  • 227,898
  • 14
  • 283
  • 497
10
votes
2 answers

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) condition $$\Gamma_{abc}=\Gamma_{acb}\tag{i}$$ to…
FutureCop
  • 103
  • 12
10
votes
1 answer

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-subgroups has form 1+2k and divides 3, the…
jacob
  • 530
  • 4
  • 11
10
votes
2 answers

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 on $n$ for the base case of $k=2$ (i.e. first…
gaj
  • 111
  • 5
9
votes
1 answer

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 which there is a solution in $S_n$ to the equation…
adam dhalla
  • 823
  • 2
  • 9
9
votes
3 answers

Secret-Santa: Probability of two people drawing each other.

When playing Secret Santa this year, where a group of $n$ people buy presents and these $n$ presents get randomly distributed to the other people, excluding the possibility of someone getting his or her own present (we did it with a…
Jonathan Clancy
  • 91
  • 2
9
votes
0 answers

If $\beta^{11}=(12893)$ in $S_{20}$.Find $\beta$

Order of $\beta^{11}$ is 5. hence, $\frac{n}{(n, 11)}=5$. If $11|n \implies n=55$.So $\beta$ is a combination of 2 cycles 5 and 11. Let $\beta =(a_1, a_2,a_3,a_4,a_5)(a_6,a_7,a_8,a_9,a_{10},a_{11},a_{12},a_{13},a_{14},a_{15},a_{16})$.Now the first…
Guria Sona
  • 1,535
  • 5
  • 13
9
votes
1 answer

In how many ways can a permutation cycle be decomposed as a product of transpositions?

I know that every permutation of a finite set can be decomposed into product of disjoint cycles and every cycle can be decomposed into product of transpositions (cycles of length 2). However the decomposition into transpositions is not unique. I'm…
Jan Hrcek
  • 219
  • 1
  • 9
7
votes
4 answers

Involutions of $S_n$

How am I able to find how many involutions are in $S_n$ for any nonnegative integer $n$? Let's say for $S_4$. Is there an equation or anything that allows me to find this with ease?
jerry2144
  • 643
  • 8
  • 14
7
votes
5 answers

What is the maximum value of $\sum_{i=1}^{n} \vert \sigma(i) - i \vert, $ where $\ \sigma\ $ is a permutation of $\ [n]\ ?$

What is the maximum value of $\ \displaystyle\sum_{i=1}^{n} \vert \sigma(i) - i \vert, $ where $\ \sigma\ $ is a permutation of $\ [n]:= \{1,2,\ldots, n\}\ ?$ Based on a program I ran in Python, the answer seems to be: $ f(n)= \begin{cases} …
Adam Rubinson
  • 16,434
  • 4
  • 24
  • 48
7
votes
0 answers

Primitive permutation groups containing a cycle

I am trying to prove the following result: Let $G$ be a primitive permutation group on $\Omega$ of degree $n$ that contains a cycle $g$ fixing $k \geq 3$ points. Then, $A_n \leq G$ where $A_n$ is the alternating subgroup of degree $n$. This is a…
TissuePaper
  • 91
  • 3
1
2 3
…
40 41