43
votes
Accepted
What are the properties of eigenvalues of permutation matrices?
A permutation matrix is an orthogonal matrix (orthogonality of column vectors and norm of column vectors = 1).
As such, because an orthogonal matrix "is" an isometry
$$\tag{1}\|PV\|=\|V\|$$
...
- 84.5k
18
votes
What are the properties of eigenvalues of permutation matrices?
A permutation may be written as a unique product of primitive cycles $\pi = (c_1)\cdots(c_k)$. This corresponds to writing the matrix in block form with each cycle representing a block. Each cycle of ...
- 35.4k
16
votes
Accepted
Number of homomorphisms between two arbitrary groups
Suppose $f:A_5 \to S_4$ be a homomorphism. Then $\ker f$ is a normal subgroup of $A_5$. But $A_5$ is simple, so $$\ker f \in \Big\{ \{e\},A_5\Big\}$$
$\ker f=\{e\}$ implies $$A_5/\{e\} \sim f(A_5)$$ ...
- 11.7k
14
votes
Secret-Santa: Probability of two people drawing each other.
Here's a fun fact: you might know that the probability that a random permutation has no fixed points is approximately $e^{-1}$ (and approaches this value quite rapidly). This generalizes: the ...
- 441k
13
votes
Accepted
Find all Sylow 2-subgroups of $S_4$ using Sylow's theorems
1) Yes, you've got it. There are three unique ways to write $\{1,2,3,4\}$ as a union of two sets of size two. These are $\{1,2\}\cup\{3,4\}$, $\{1,3\}\cup\{2,4\}$, and $\{1,4\}\cup\{2,3\}$. These ...
- 3,387
11
votes
Accepted
What is the fractal dimension of the image given by a combinatorial sequence about permutation cycles?
$\def\FF{\mathbb{F}}$I want to make three points.
(1) The generating function for this sequence $\bmod 2$ is a rational function.
(2) There are good tools for understanding the fractal behavior of the ...
- 62.8k
11
votes
Accepted
How can I tell if a permutation can be expressed as the commutator of another 2 permutations?
For the question in the post (now edited):
In any group other than the trivial group and the group of two elements, every element can be written as the product of two nontrivial elements. In ...
- 407k
10
votes
Elements of $S_n$ can be written as a product of $k$-cycles.
The conjugate of a $k$-cycle is a $k$-cycle. So $G$, the group generated by
$k$-cycles is a normal subgroup of $S_n$. For $n\ne 4$, the normal subgroups
of $S_n$ are $S_n$, $A_n$ and $\{\text{id}\}$. ...
- 159k
8
votes
Elements of $S_n$ can be written as a product of $k$-cycles.
Here is a direct proof, requiring no knowledge of the normal subgroups of the symmetric group.
Since we know that every permutation is a product of transpositions, it will suffice to show that, for ...
- 79.6k
8
votes
Accepted
how to determine the number of moved points of a commutator [g,h] from the shared moved points of g and h
This answer uses the convention that $[g,h] = g^{-1}h^{-1}gh$. If $g$ is a permutation, the support of $g$, denoted $\mathrm{supp}(g)$, is the set of points that $g$ moves.
Proposition. Let $g$ and $...
- 49.8k
8
votes
Accepted
Any algebraic way to check valid permutations on a cube?
The question you ask is a special case of what is called the membership problem.
The membership problem: Let $G$ be a group, and $H$ a subgroup. Is there an algorithm which takes an element $g\in G$ ...
- 2,402
7
votes
Accepted
How to show that $\mathbb{Z}_{12} $ is isomorphic to a subgroup of $S_7$?
Hint: look at $(1 \ 2 \ 3)(4 \ 5 \ 6 \ 7)$. What is its order?
- 50.4k
7
votes
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$.
Consider $\sigma=(1234)$ and $\tau=(13)$ in $S_4$. Viewed geometrically, we have four objects in a square where $\sigma$ rotates the square by $90^\circ$ and $\tau$ reflects the square on a fixed axis....
- 104k
7
votes
Accepted
How to calculate the Galois group of $x^5+15x+12$?
Hint The polynomial $f(x) := x^5 + 15 x + 12$ is Einstein at $3$, so is irreducible, and thus $\operatorname{Gal}(f)$ is a transitive subgroup of $S_5$, namely, one of $S_5, A_5, F_{20}, D_{10}, C_5$. ...
- 103k
7
votes
Accepted
Question in discrete mathematics about group permutations
$1 \xrightarrow{\text{(246)}} 1 \xrightarrow{\text{(1357)}} 3 \xrightarrow{\text{(1234567)}}4 $
$4 \xrightarrow{\text{(246)}} 6 \xrightarrow{\text{(1357)}} 6 \xrightarrow{\text{(1234567)}}7 $
$7 \...
- 23.5k
7
votes
Accepted
Does there exist any $x\in S_{10}$ such that $x(1\ \ 2\ \ 3)x=(9\ \ 10)$?
$x(1\,2\,3)x$ must be an even permutation. But $(9\,10)$ isn't.
In general, to solve $xax=b$ in $S_n$where $a$ and $b$ are given permutations, note that this is the same as $(xa)^2=ba$, so this is ...
- 159k
7
votes
How to know if a 8 puzzle is solvable
An inversion is an unordered pair of distinct numbers, such as $\{5,7\}$, where the two numbers are not placed in the order they are supposed to be in the puzzle (in this case, listing the numbers row-...
- 202k
7
votes
Accepted
How to know if a 8 puzzle is solvable
Label the empty cell $9$. Then the above diagram represents the permutation
$$(1\ 2\ 3\ 6\ 8)(4\ 5\ 9)(7).$$
The sign of this permutation equals $1$.
Every move consists of swapping the empty cell ...
- 65k
7
votes
How does $(abc) = (ac)(ab)$?
These cycles are effectively functions (think $f\circ g$). Since you are asking what the composition of functions $(ac)(ab)$ does to the elements $a$, $b$, and $c$, you need to read right to left, ...
- 1,365
7
votes
Why is $(12345) = (54)(53)(52)(51)$?
This is cycle notation, which is ideal for many types of calculations with permutations. For example, the notation $(1\,2\,3\,4\,5)$ stands for the transformation
that sends
$$
1 \mapsto 2 \mapsto 3 \...
- 26.5k
7
votes
Accepted
Cycle notation: Inverse of $(1348)$ in $S_9$ ( Find the mistake)
Here $1 \mapsto 3 \mapsto 4 \mapsto 8$ is the result of applying the permutation $3$ times.
So this means in $(1348)^3$, $1$ is mapped to $8$. Reading the others, we get $3\mapsto 1, 4\mapsto 3, 8\...
- 489
7
votes
Accepted
Prove that $\Gamma_{abc}=\frac{1}{2}\left(\partial_bg_{ac} + \partial_cg_{ab}-\partial_ag_{bc}\right)$
There seems to be something wrong with the cyclic renaming of indices in (2) and (3) as well as in (4) and (5). The main thing to keep in mind is that you cannot just cycle indices, but you must ...
- 661
6
votes
Accepted
Permutation group equation: $x^{20} = \sigma$
Well, cycles of odd length are even permutations, and cycles of even length are odd permutations. Here we have three cycles of even length and one cycle of odd length, and so $\operatorname{sign}(\...
- 5,690
6
votes
Finding a presentation of a permutation group given the generators
$\langle x,y \mid x^7,y^2,(xyx^{-1}yx)^2,(xyx^{-3}yx^2)^2 \rangle$ is a presentation on the two given generators.
Or better, $\langle x,y \mid y^2,(xyx^{-1}yx)^2,x^7(xyx^{-3}yx^2)^2 \rangle$ is a ...
- 92.7k
6
votes
Accepted
Decomposing a permutation into 3-cycles
First, notice that, since 3-cycles are even, and products of even permutations are even themselves (if you know what it means, this comes from the fact that the map sending each permutation to its ...
6
votes
Secret-Santa: Probability of two people drawing each other.
Define an $r$-derangement to be a permutation whose smallest cycle has length strictly greater than $r$. Let $D_{n,r}$ denote the number of $r$-derangements in $S_n$. It is a standard result that for ...
6
votes
Why does $(13)(47)(13)(23)=(47)(23)$?
The key insight that you need is that disjoint cycles commute. This means that:
$$ (1 3)(4 7)(1 3)(2 3) = (1 3)(1 3)(4 7)(2 3) = (4 7)(2 3) $$
- 915
6
votes
Accepted
Algorithm for finding the cycle-decomposition of a permutation.
Yes, there is a linear time algorithm. Skipping seen entries ensures each permutation entry is referenced at most $2$ times, so this is linear time.
You cannot determine the number of cycles a ...
- 79.8k
6
votes
Accepted
Method to determine an order of an arbitrary permutation matrix
Here is how you can do it, assume the matrix is $n\times n$.
Obtain the permutation $f:\{1,\dots, n\} \rightarrow \{1,\dots, n\}$ where $f(j)$ is equal to the row $x$ such that $A_{x,j} = 1$.
...
- 106k
6
votes
Accepted
Fixed-Point Free Involutions
An involution is a permutation that is its own inverse, but that can be a bit hard to parse at first. Let's see a concrete example:
The map $x \mapsto -x$ from $\mathbb{Z} \to \mathbb{Z}$ is an ...
- 39.1k
Only top scored, non community-wiki answers of a minimum length are eligible