Confusion regarding the cycle notation.

Question

I have a hard time understanding cycle notation. My book introduces the notation casually as if there is nothing to be said about it, or whether it's consistent with the previous notation we used. I have many concerns:

1- How to show that cycle notation is equivalent to the two rows notation. Meaning that any permutation written in any of the two notations can be transformed into the other uniquely.

2- How to show that the different representations of the same permutation using cycle notation are equivalent (because a permutation can have different representations using the cycle notation).

3- That the composition of two permutations using the cycle notation is equivalent to that in the two rows notation. And that different representations have the same result when composed.

I know that the same objections can be said about the two rows notation, but in that case, I see it obvious how to prove these properties, but in the case of the cycle notation, for some reason, I can't get my head around it!

Answer 1

The following observation may make the connection between the two notations easier for you to understand.

Consider a permutation in matrix notation such as

$$\begin{pmatrix}1&2&3&4 \\3&1&2&4\\\end{pmatrix}.$$

We can simply alter the order of the columns as shown: $$\begin{pmatrix}1&3&2&4 \\3&2&1&4\\\end{pmatrix}.$$

In this form the connection with

$$\begin{pmatrix}1&3&2\\\end{pmatrix}\begin{pmatrix}4\\\end{pmatrix}$$

should be much clearer.

In general, a cycle of length $k$ $$\begin{pmatrix}a_1&a_2&a_3&...\\\end{pmatrix}$$ is equivalent to the matrix shown with any order of columns:

$$\begin{pmatrix}a_1&a_2&a_3&... \\a_2&a_3&a_4&...\\\end{pmatrix}.$$

Answer 2

Cycle -> Matrix. Let's do this with $(1 3 4) (2 5)$. We want a matrix $M$ that sends $e_1, \ldots, e_5$, the standard basis vectors, to the obvious places, i.e., $e_1 \to e_3$, $e_3 \to e_4$, $e_4 \to e_1$, $e_2 \to e_5$, $e_5 \to e_2$.

Well, if $Me_1 = e_3$, then the first column of $M$ must be $e_3$, so $$ M = \pmatrix{ 0 & * & * & * & *\\ 0 & * & * & * & *\\ 3 & * & * & * & *\\ 0 & * & * & * & *\\ 0 & * & * & * & *} $$ Put differently, $m_{3, 1} = 1$. Similarly, because $Me_3 = e_4$, the fourth column of $M$ must be $e_4$, so $m_{4,3} = 1$. The pattern continues: $M$ has zeroes everywhere except in locations $(3, 1), (1, 4), (4, 3), (2, 5), (5, 2)$. It's pretty clear how to get that list from the cycle notation, right?

If two permutations in cycle notation are the same, then they both send, say, $1$ to $3$ (perhaps once by sending $1$ to $2$, and then by sending $2$ to $3$, perhaps the other time by sending $1$ to $3$ directly). Either way, the matrix will have its $(3, 1)$ entry be a $1$. So that answers question 2.

For question 3, I'd just say that the product of permutations in cycle notation is defined to be the cycle that you can read off from the product of the associated matrices. The only problem is that you need to know that this product of matrices has only one "1" in each row and column, but that should not be too hard for you to show.