A permutation of a collection C is just a monic mapping (C|f|C); that is, for every c in C, there is exactly one s in C for which f relates c to s and exactly one s in C for which f relates s to c. Consequently, reverse(f) is also a permutation of C and the composite f&on;reverse(f) is just (the identity on) C itself, which is fatuously a permutation of C. Furthermore, the composite of any two permutations is trivially a permutation (because every composite of monics is monic and every composite of mappings is a mapping). Thus, for any given C, {permutations of C} forms a group under composition.
In general, {permutations of C} is the intersection of {mapping (C|:C)} and {monic (C:|C)}, which are one another's images under reverse; and C is finite precisely if these two collections are equal, in which case they also coincide with their intersection. This makes the finite case straightforward and helps greatly in rendering useful results provable for it. Consequently, my attention shall mostly be focussed on the finite case. Because every finite collection may be set into one-to-one correspondence with some natural number, albeit one may have some choice of which correspondence to use, the theory of finite permutations is most conveniently examined in terms of the permutations of natural numbers; and any such is simply a monic list (n||n) for some natural n.
Every permutation of a collection C may be tacitly extended to a permutation of any collection S which subsumes C by having it act as the identity on every member of S which isn't a member of C. Thus every permutation tacitly acts on the collection of all possible values; however, where context makes clear that it is discussing permutations of some given collection, it tacitly restricts the domain to which permutations are extended, so that each only acts on the given collection.
Note that every output of a permutation is also an input of it, and vice versa. Thus every (left or right) value of a permutation which is not a fixed point of the permutation necessarily: is the output the permutation yields when given some input which is also not a fixed point, and; yields an output which is not a fixed point. Thus a permutation is specified by its action on those values which aren't its fixed points; albeit context must indicate the domain on which it is to act, tacitly extending it as the identity on the remainder of this domain.
For any distinct values i, j define swap(i,j), a.k.a. i↔j, to be the
mapping which maps i to j and j to i; as above, it tacitly acts as the
identity on all other values under discussion. A mapping of form swap(i,j),
for distinct i and j, is known as a swap; for a given
collection n, swap(i, j) is known as a swap within n
precisely if i, j
are in n (and, of course, distinct). Note that, by construction, every swap
is self-inverse; it is its own reverse.
For any natural n, we can classify the permutations of 1+n by considering where they map n; there are 1+n possibilities. If a permutation s of 1+n maps n to n, then s is effectively just a permutation of n. Otherwise, it maps n to some s(n) in n, covering the other n possibilities; composing it before swap(n, s(n)) yields a permutation of 1+n with n as a fixed point, i.e. a permutation of n. Consequently, for each j in n, composing swap(j, n) with each of the permutations of n yields a distinct permutation of 1+n; taken together with the permutations of n, each extended to 1+n by having n as a fixed point, we thus find that the number of permutations of 1+n is just 1+n times the number of permutations of n. Given that there is exactly one permutation, the identity, of the empty set or of any set with only 1 member, we may thus infer that the permutations of a set of size n is simply the factorial of n.
Now, for finite n, {permutations of n} is finite (it has n! members, when n is natural). For any permutation s of n, we can construct the sequence S = (: (n| repeat(i, s) |n) ←i :{naturals}). Every output of this is a composite of permutations of n, hence also a permutation of n; and there are only finitely many of these. Consequently, S cannot be monic (since {naturals} is infinite) and there must be distinct naturals i, j for which S(i) = S(j). Select the least natural j for which there is some i in j with S(i) = S(j); so there is some positive natural m with j = i+m. Let r = repeat(i, reverse(s)); then (the identity on) n = S(0) = r&on;S(i) = r&on;S(j) = r&on;repeat(i+m, s) = repeat(m, s) = S(m). Since m is positive, 0 is in m; since j is the least m for which S(j) in (|S:j), and S(m) is in (|S:m), we may infer m≥j; but j = i+m for some natural i implies j≥m; whence j = m, i = 0. Furthermore, the members of (|S:m) are all distinct, hence m is at most n!, the number of distinct permutations of n. Therefore, for any permutation s of n, there is some finite positive m≤n! for which repeat(m, s) is the identity; and there is a least such m (in the case where s is the identity, the least positive such m is of course 1). This is known as the period of the permutation s.
Note that only the identity has period 1, since repeat(1, s) = s can only be the identity if s is; and that every swap has period 2.
Theorem: any permutation of a finite collection n may be written as a composite of finitely many swaps within n. Proof:
The identity permutation on any collection is the restriction, to that collection, of bulk(&on;, []), the composite of an empty list of swaps within the given collection; so every identity permutation is indeed a composite of finitely many swaps within the identity. Any finite set may be identified with a natural number via a chosen monic mapping, so it suffices to prove the result for the permutations of an arbitrary natural number. The only permutation of the empty collection or of a collection with only one member is the identity, so our result certainly holds true for n = 0 or n = 1. Suppose then, inductively, that we are given i for which every permutation of i is a composite of finitely many swaps within i; and consider any permutation (1+i|s|1+i). If s is the identity on 1+i, we already know it is a composite of finitely many swaps within 1+i.
Otherwise, 1+i has some member which is not a fixed point of s. If s(i) is i, then: for each j in i, s(j) isn't i (because s is monic) but is in 1+i, so is in i; and j is s(k) for some k in 1+i, but s(i) = i so k is not i, so in fact k is in i; thus j is in (|s:i). Thus (:s:i) is a permutation of i and we already know that it's a composite of finitely many swaps within i, hence within 1+i. Otherwise, s(i) is in i, so compose swap(i, s(i)) after s. Both s and (: swap(i, s(i)) :1+i) are permutations of 1+i, so swap(i, s(i))&on;s is a permutation of 1+i; and it maps i via s(i) to i, so is of the form considered previously, hence a composite of finitely many swaps within 1+i. If we compose swap(i, s(i)) after it, the result shall necessarily also be a composite of finitely many (one more than finite is always finite) swaps within 1+i; but this composite is swap(i, s(i))&on;swap(i, s(i))&on;s = s since every swap is self-inverse. Thus s is also a composite of finitely many swaps within 1+i – Q.E.D.
Scrutiny of the proof reveals that a permutation of 1+i may be written as a composite of at most i swaps; the only permutation of 1+0 is a composite of 0 swaps; and the proof only adds one swap in going from each natural to its successor.
In the proof, observe that swap(i, s(i))&on;s only had to have i as a fixed point; consequently, we could replace swap(i, s(i)) with any other permutation which maps s(i) to i. Since s(i) is in i, there is some j in i for which 1+j+s(i) = i; let h = (: swap(k+s(i), 1+k+s(i)) ←k :j). Then y = (: h(k) ←e; e+k+1 = j :j) is just the list h in reversed order, with h(0) as its last entry; then bulk(&on;, y) maps s(i) via 1+s(i) and each higher natural up to, finally, i, so is a suitable replacement for swap(i, s(i)). Thus bulk(&on;, y)&on;s has i as a fixed point. Now, consider bulk(&on;, h)&on;bulk(&on;, y); for each k in j, given inductively that the last k entries in h compose with the first k entries in y to yield the identity, observe that the last-but-k entry in h and the k-th entry in y are both swap(e, 1+e) with e+k+1 = i, composed with an identity between them, so simply composed together in effect; but this is a swap, so self-inverse, so the last 1+k entries in h and the first 1+k entries in y yield the identity; so we can induce that bulk(&on;,h)&on;bulk(&on;,y) is simply the identity. Thus bulk(&on;,y)&on;s has i as a fixed point; and composing bulk(&on;,h) to the left of this yields s. We can thus follow the same structure of proof as above to induce that every permutation of n can be expressed as a composite of swaps of adjacent naturals within n.
Theorem: for some given collection C, let
φ be a group homomorphism between permutations of C, under composition,
and a multiplicative group A, with identity +1, in which a.a = +1
iff a in {±1}
; then either φ is the fatuous homomorphism
({1}:φ|{permutations of C}) or φ maps every swap to
−1. Proof:
If a permutation s has period m – i.e. if bulk(&on;, ({s}:|m)) is the identity – then power(m, φ(s)) must be +1. Every swap has period two, so must map to ±1; and every permutation is a composite of swaps, so must be mapped to some product in which each factor is ±1; hence the product is ±1; hence ({±1}: φ |{permutations of C}) and A is, without loss of generality, simply {±1}; i.e. all other members of A can be ignored. If φ maps a permutation of order m to −1, then power(m, −1) must be +1, whence m must be even; so φ must map every permutation of odd order to +1. If C is empty or if C has only one member, then the only possible permutation of C is the identity; which a homomorphism inevitably maps to the identity, +1. In all other cases, we have at least two members of C to permute.
Now suppose we have some distinct i, j in C with φ(swap(i, j)) = u in {±1}, so u = +1/u. Let k be any other member of C; then swap(i,j)&on;swap(j,k) maps i to j, j to k and k via j to i; it is thus a three-cycle, with period three, which is odd; so φ maps it to +1. Consequently, φ(swap(j,k)) = +1/u = u. We can now use the same argument for any other member, h, of C, to infer that swap(h, k) = u for all h, k in C; so φ maps all swaps to the same member of {±1}. If φ maps all swaps to +1, then it is simply ({+1}:φ|{permutations of C}); otherwise, it maps every swap to −1 – Q.E.D.
It remains to prove that such a homomorphism can, consistently, map every swap to −1. I can define the relation ({±1}: sign |{finite permutations}) by: sign relates +1 to the composite of any even-length list of swaps; sign relates −1 to the composite of any odd-length list of swaps, i.e.
and clearly this must be a homomorphism, known as the signature
homomorphism
, if it's a mapping; but I need to prove that it is indeed a
mapping. This is true precisely if two lists of swaps can only have equal
composite if either both are of even length or both are of odd length; which,
in turn, is true precisely if no odd-length list of swaps has, as composite,
an identity.
Theorem: the composite of any odd-length list of swaps has at least one non-fixed point (i.e. some right value that it maps to some different value). Proof:
I proceed by a double induction, on the length of list and on the range of
indices available to swap. Let P(n, m) stand for every odd-length list, of
length < 2.n, of swaps within m, has at least one non-fixed point
. We
can fatuously assert P(0, m) for all naturals m and P(n, 1) for all naturals
n, since (in each case) there are no candidate lists of swaps; only the empty
list is available and its length is even, not odd. Suppose P(n, m) given,
then, for all naturals m, for some specific natural n (e.g. n = 0).
We can also take P(n+1, k) as given, for some natural k (e.g. k = 1). Now consider any list ({swaps within k+1}: f |2.n+1). None of the following operations changes the composite of the list, changes the fact that its length is odd, makes the list longer, moves the first swap implicating k further from the list's end or increases the number of swaps implicating k:
Applying these operations until none of them is applicable, we obtain a list in which there is at most one swap implicating k and, if there is such a swap, it is last in the list. The resulting list has odd length ≤ 2.n+1, consists entirely of swaps within k+1 and has the same composite as f. If we ever eliminated duplicates (the first operation), we reduced the list's length and P(n, k+1) tells us the composite has a non-fixed point. If no remaining swap implicates k, P(n+1, k) tells us the composite has a non-fixed point. Otherwise, no swap but the last implicates k and the last does implicate k, so the composite maps k to some i in k, in particular i≠k, so k is not a fixed point of the composite. We thus establish P(n+1, k+1) given P(n+1, k) and, inductively, P(n+1, m) for all natural m.
Since P(n, m) for all naturals m thus suffices to let us establish P(n+1, m) for all naturals m, we can induce P(n, m) for all naturals n and m – Q.E.D.
This implies that no odd-length list of swaps has an identity as its composite; which, in turn, implies that no odd-length list and even-length list have equal composite; which implies that sign is a mapping.
Written by Eddy.