Why are an even number of flips required to get back to the original list?

Question

Consider the list of numbers $[1, \cdots, n]$ for some positive integer $n$. Two distinct elements $i$ and $j$ of the list can be switched in a so-called flip. For example, let $f$ be a flip that switches $2$ and $4$. Then $f([1,2,3,4]) = [1,4,3,2]$. Now consider a sequence of $k$ flips $f_1, \cdots, f_k$ of the list $[1, \cdots, n]$ such that $f_1(f_2(\cdots f_k([1,\cdots,n])\cdots)) = [1,\cdots, n]$, i.e. performing all flips gives the original list. Then $k$ must be even.

I would like to find a proof of this proposition that is elementary as possible. I already came up with a justification using permutation groups which goes as follows:

Each flip $f_i$ corresponds to a transposition of the list $[1, \cdots, n]$. Since the composition $f_1f_2\cdots f_k$ results in the identity, it must be an even permutation. Thus any representation of $f_1f_2\cdots f_k$ as a product of transpositions must contain an even number of transpositions. In particular, since each $f_i$ is a transposition, it follows that $k$ must be even.

This "proof" trivializes the problem statement as it is by using relatively high-powered facts about permutation groups. Is there a lower-level proof that avoids using theses results? (Ideally such a proof would avoid permutation groups altogether and be understandable to the layman.)

Edit: to clarify (since this question hasn't been getting as much attention as I had hoped), any proof that avoids re-deriving these powerful results about permutations would suffice. Basically I would want a proof that does not prove much more than the question requires, i.e. doesn't have a part where it says "in particular".

Answer 1

Here is a combinatoric proof (which I am not sure if it is from permutation group).

Count the number of 'reversed pair' in the list. What I mean by reversed pair is pair of numbers which the one bigger in value comes before the smaller one. For example, in $[2,1,3,4]$, $(2,1)$ is a reversed pair but $(1,3)$ is not.

Now observe the change of the number of reversed pair when a flip is taken. Let's say the list is $[\cdots,a,\cdots,b,\cdots]$ and we flip $a,b$, turning it into $[\cdots,b,\cdots,a,\cdots]$. It should be obvious that those in front or behind does not contribute any changes. Also, for those in between, lets call one of it $c$, will only contribute if $a<c<b$ or $a>c>b$. $+2$ for the former and $-2$ for the latter. And finally, the $a,b$ pair. $+1$ if $a<b$ and $-1$ if $a>b$. Anyway, the total number changes by an odd number. Since you have total number of $0$ at beginning and you want $0$ at the end, you have to flip even number of times.

Hope this helps you.

Answer 2

The value of k will be positive since to get back two numbers back to its position we have to do two flips.

For ex - for[1,2,3,4,5] we have first flip it once i.e.2 and 5 now to get back the original set again we again have to flip 2 and 5. Now if we use k flips then it must be even since the have to be reversed that are reversed by k-1 flips.

Answer 3

The complete transposition graph $X_n$ is defined to be the graph whose vertex set is the symmetric group $S_n$ and two vertices are adjacent whenever they differ by a transposition. It is easy to see that this graph is bipartite, with bipartition the set of even permutations and the set of odd permutations. You want to prove that any walk in this graph that starts at the identity vertex and returns to the identity vertex has even length (this is true for any initial vertex, not just the identity permutation). This is clear because a bipartite graph does not contain odd cycles, but the proof that the complete transposition graph is bipartite uses the notion of even and odd permutations.

Perhaps you can draw (to the layman) such a complete transposition graph in the form of a bipartite graph (for small values of $n$), and then explain that in a bipartite graph if one starts from a vertex in the left vertex set and returns back to a vertex in the left vertex set (it can even be a vertex which is different from the initial vertex), then one must have traversed an even number of edges.

Instead of using the concept of even permutations, perhaps you can use the concept of the number of inversions of a permutation. You can restrict yourself to doing swaps of just adjacent elements. Each adjacent swap changes the number of inversions by 1. And so returning back to the same permutation must have used an even number of adjacent swaps. The corresponding graph on vertex set $S_n$ is called the bubble-sort graph and it is bipartite (in fact, it is a subgraph of the complete transposition graph), with bipartition the set of permutations having an even number of inversions and those with an odd number of inversions. Now you can show that any arbitrary (ie including non-adjacent) swap changes the number of inversions by an odd number and therefore corresponds to going from one part of the bipartition to the other in this bubble-sort graph. (You are essentially using the fact that a permutation is even iff it has an even number of inversions.)

Answer 4

Your flips of $[1,\ldots,n]$ are precisely transpositions of $\{1,\ldots,n\}$, so proving your statement about flips is immediately equivalent to proving the powerful statement about permutation groups that the identity is not the product of any odd number of transpositions. So it is inevitable to either rely on these powerful results or rederive them. I'll try to rederive them in an elementary way.

---

Let $f_1,\ldots,f_k$ flips of $[1,\ldots,n]$ such that $f_1\circ\cdots\circ f_k$ is the identity. We want to show $k$ is even. This is evidently true for $k=2$, and we proceed from here by induction, so let $k>2$ and suppose the above holds for all $k'<k$. I'll use cycle notation here and there for brevity.

A key observation that can be illustrated to the layman clearly by example, are the identities $$(cd)(ab)=(ab)(cd)\qquad\text{ and }\qquad(bc)(ab)=(ac)(bc),$$ meaning that a flip that does move $a$ followed by a flip that doesn't move $a$ has the same result as some flip that doesn't move $a$ followed by a flip that does move $a$. A picture illustrates this: $$\texttt{These aren't the most illustrative pictures.}$$ In the identities above it is important to observe that the number of flips stays the same, and the number of flips that move $a$ also stays the same, while pushing the flip that moves $a$ to the left.

Let $a$ be a number switched by $f_1$. Because the sequence of flips results in the identity there must be another flip that switches $a$. Let $f_i$ be the next one, i.e. the one with the lowest $i$. Using the identities above we can push this flip left to get a sequence starting with $f_1$ followed by another flip that moves $a$, which still results in the identity. All the while keeping the same total number of flips, and the same number of flips switching $a$. If now the first two flips are distinct then the identity $$(a\ b)(a\ c)=(a\ c)(b\ c),$$ which holds for distinct $a$, $b$, $c$, yields a sequence of the same length with one less flip switching $a$, and still starting with a flip switching $a$. We can repeat this process for the next flip $f_j$ switching $a$, and keep repeating it until the first two flips are not distinct. Every time we repeat this process the number of flips moving $a$ decreases by $1$, and this number cannot be $1$, so we will get a sequence starting with two flips that are not distinct. This means the first two flips cancel, and hence that the remaining sequence of $k-2$ flips also results in the identity. Then by induction hypothesis $k-2$ is even, and therefore $k$ is even.

Answer 5

Let $\ell=(x_1,x_2,\ldots, x_n)$ be a list of the numbers in $[n]$. For each $k\in[n]$ denote by $p_k$ the number of $x_i\ (1\leq i<k)$ with $x_i>x_k\,$, and call $\beta(\ell):=\sum_{k=1}^n p_k$ the badness of $\ell$. It is easy to convince oneself that a transposition ("flip") $\tau:\>\ell\mapsto\ell'$ changes the badness by $\pm1$. It follows that an odd number of flips cannot restore a given $\ell$ to its original version.