Confused on permutation cycles

Question

I am a bit confused on how to interpret permutation cycle notation. I am going by the Wolfram definition. My initial interpretation of $(431)(2)$ was "4 moves to position 3, 3 to position 1, 1 to 4, 2 remains in place". which would leave me at ${3, 2, 4, 1}$ which apparently is incorrect, since the solution is ${4, 2, 1, 3}$. So it would appear that the correct way to read $(431)(2)$ is "element 4 is replaced by 3, 3 by 1, 1 by 4, 2 remains in place".

I am also unclear on the definition of a cycle, which seems to mean a subset of elements which are permuted. Wolfram says, "any rotation of a given cycle specifies the same cycle", but I do not see why $(413)(2)$ cannot be considered a cycle of $(431)(2), (314)(2), (143)(2), (2)(431), (2)(314), (2)(143)$. The elements lookthe same, only permuted.

Answer 1

Your initial interpretation of $(123)$ would seem to suggest that it sends $1$ to the middleman $2$ and then to the final destination of $3$. This would make the "middleman" $2$ completely superfluous; what's the point of having a midway station if it doesn't have any consequence at all?

No, $(123)$ means that $1$ ends up at $2$. It does not go any further. And $2$ ends up at $3$. And $3$ ends up at $1$. That is, if $\sigma=(123)$, then $\sigma(1)=2$, $\sigma(2)=3$ and $\sigma(3)=1$. Why is this called a "cycle" you may ask? One thing to notice is that if you start in any particular place, say $1$, then upon repeated application we get $\sigma^0(1)=1$, $\sigma^1(1)=2$, $\sigma^2(1)=\sigma(\sigma(1))=\sigma(2)=3$, and then back to $\sigma^3(1)=\sigma(\sigma^2(1))=\sigma(3)=1$ back where we began. We do go on a "round trip" through the numbers seen in the cycle notation, in the order they're listed, upon repeated application of $\sigma$.

An equivalent way of thinking about this is as follows: if we list out the numbers from the cycle notation on a circle in the order they appear, applying $\sigma$ to the numbers is the same as rotating.

Now, the numbers appearing in the notation $(132)$ are the same as those appearing in $(123)$, however they do not denote the same permutation. The first takes $1$ to $3$, whereas the second takes $1$ to $2$, so they cannot be the same. Yet, $(231)$ also looks different than $(123)$, and we can check that they represent exactly the same function (permutation) of the set $\{1,2,3\}$: each sends $1$ to $2$ and sends $2$ to $3$ and sends $3$ to $1$, so the notations $(123)$ and $(231)$ both specify the same exact permutation. Similarly, $(312)$ is another way of specifying this same permutation.

In general, if you take the numbers that appear in a cycle's cycle notation and, well, cycle them as they appear, you will not be changing the permutation that is being denoted. However if you permute the numbers that appear in a cycle notation arbitrarily you will not, in general, end up with the same permutation you started with. We already observed $(123)\ne(132)$ for instance.

Answer 2

The notation $(431)(2)$ means the function from $\{1,2,3,4\}$ to itself that maps things as follows: $4\mapsto3$; $3\mapsto 1$; $1\mapsto4$; and $2\mapsto2$. Notice that this looks a lot like your description, except that I've avoided "position" and "moves". Despite the terminology, a permutation is, officially, a function, not a bunch of things moving around.

Nevertheless, people often describe permutations by writing things in certain positions; there are several conventions for how to do this. The clearest is the "two-line" notation, where you write the inputs to the permutation on a horizontal line and write the corresponding outputs directly below them. Thus, the function described above with $\mapsto$ could be written as $\pmatrix{4&3&1&2\\3&1&4&2}$. Usually, though, when people use two-line notation, they arrange the top line in increasing order (assuming that the entities being permuted are real numbers), so the same permutation would be written $\pmatrix{1&2&3&4\\4&2&1&3}$. This contains exactly the same information as the previous two-line notation; notice that the columns are the same (and are the same as the $\mapsto$ items in the preceding paragraph). You could write a lot of other two-line presentations of the same permutation; list $1,2,3,4$ in the top row in any order you like, and fill in, beneath each entry, the number that the permutation maps it to.

When people decide to write the top line in increasing order, they can save some space by not writing that line at all, relying on the reader to mentally fill it in. So these people just write the bottom line, which in this case is $4,2,1,3$. But for this to work, it's absolutely essential to agree that the unwritten top line is understood to be the same numbers in increasing order. This convention accounts for "the answer" that you cited in your question.

In some alternative world, people could have decided to always write two-line notation with the bottom line in increasing order. So the permutation in your example would be $\pmatrix{3&2&4&1\\1&2&3&4}$. And then they could have decided to save space by writing only the top line, relying on the reader to mentally fill in the bottom line in increasing order. So they would write your example as $3,2,4,1$, which is the answer you proposed. So you'd be right in this alternative world; unfortunately, you're in our world, where people use the conventions of the preceding paragraph, not this one.

If you follow the path from your original cycle notation $(431)(2)$ to the $\mapsto$ description, to the two-line notation with increasing top row, to the one-line notation, you'll find the following (and three more facts just like it). The fact that $4\mapsto3$ in your permutation means that $4$ is directly above $3$ in any version of two-line notation (no matter how you arrange the top row), which means in turn that $4$ is above $3$ in column $4$ of two-line notation when you arrange the top row in increasing order, which means that $3$ is in position $4$ of the one-line notation. (In the alternative world, the two-line notation would have $4$ above $3$ in column $3$, so the one-line notation would have $4$ in position $3$, as you originally expected.)