# Tag Info

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

### 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
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

### 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
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
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
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

### 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

### 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
Accepted

• 23.5k
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

### 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
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

### 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

• 915
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
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
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 ...