Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

The question is as follows

TRUE or FALSE: For n > 1, any element of $S_{n}$ has order less than or equal to n. If true, give a short proof and if false, give an explicit counter-example.

I feel a little lost ( as i often do in proofs that i cant prove via counter example)

$S_{n}$ is a Bijection so the order of $S_{n} = n$ ( as long as we are in the land of finite n)

I think im lost on the meaning of Element having an order greater then 1.

The only way i can really interpret the order of a element greater then 1 is in a finite cyclic group where the order of some element $a_{1} = <a_{1}> $ If i was in a case such as this i may make an attempt to prove that the order of $a_{1} = a_{n-1} = S_{n}$ and then try and show using some idea of sorts.

That Order of all $a_{i}$ < order of $a_{1}$ for all i that are not n-1 or 1

Could someone try and explain in.. well terms that someone who doesn't get math might understand? i would really like to understand the order of elements in this context correctly

EDIT

Above is wrong.

share|improve this question
add comment

2 Answers

up vote 4 down vote accepted

I'm going to cover some of the machinery behind this topic. You might find it heavy reading, but it is certainly relevant and has high payoff if you're willing to learn it. It is good practice for someone new to a theory to get their hands dirty with some of the basic concepts, and put pen to paper to experiment with actual numbers and small cases, so I include opportunity for this as well.

Cycle notation: It is incumbent that we have good notation for permutations, as it will help facilitate any discussion of their properties, and hinder our progress otherwise. A cycle, which we will express as $(a_1~a_2~\cdots~a_m)$, is the permutation which sends $a_1\mapsto a_2$ and $a_2\mapsto a_3$ and so forth all the way to $a_{m-1}\mapsto a_m$ and $a_m\mapsto a_1$. Thus, the elements are cycled, as the name suggests.

Note that this representation may not be unique. For instance, $(123)$, $(231)$, and $(312)$ all represent the same permutation, and in particular the same cycle, but they are not the same as the single permutation that may be represented as any of $(213)$, $(132)$, or $(321)$. Observe further that a cycle of length $m$ (that is, $m$ terms in the expression $\sigma=(a_1~\cdots~a_m)$) has order $m$ as an element of the symmetric group in which it resides. Exercise: Can you come up with an explanation as to why?

Disjoint cycle decomposition: Two cycles are called disjoint if the elements which they actually permute (so, the terms inside the parentheses in cycle notation) are disjoint sets. For instance, the cycles $(123)$ and $(24)$ are not disjoint, since each acts nontrivially on $2$, but $(13)$ and $(24)$ are in fact disjoint cycles since $\{1,3\}\cap\{2,4\}=\varnothing$ is empty. Exercise: If $\sigma$ and $\rho$ are disjoint cycles, then they commute, i.e. we have $\sigma\rho=\rho\sigma$ (writing them side-by-side indicates composition, recall); can you come up with an argument or an explanation as to why this is true?

Every permutation can be written (uniquely, in fact) as a product of disjoint cycles. It is quite straightforward to explicitly compute it. First, pick a number, say $1$, then compute the sequence of terms $1$, $\sigma(1)$, $\sigma^2(1)$, $\sigma^3(1),~\dots$ (through repeated application) until you obtain $1$ again (and here is another Exercise: explain why this sequence must come back to $1$ eventually). Form a cycle out of these terms, in the order you obtained them, then delete all of these terms from $\{1,2,\cdots,n\}$, and then you pick another term $k$ from the resulting set, compute the sequence $k,\sigma(k),\sigma^2(k),\dots$, and keep repeating this procedure until you have exhausted all the numbers in $\{1,\cdots,n\}$ and obtained a nice collection of cycles $\tau_1,\tau_2,\cdots,\tau_r$. They will be disjoint, and $\sigma=\tau_1\tau_2\cdots\tau_n$. (Ex. Why?)

Orders and LCMs: Suppose we have a permutation $\pi$ with disjoint cycle representation given by the product $\pi=\pi_1\pi_2\cdots\pi_r$, where each cycle $\pi_r$ has length $\ell_r$. What is the order of this cycle? The key to finding out a general formula is to utilize disjointness:

$$e=\pi^a=\pi_1^a\cdots\pi_r^a\quad\iff\quad e=\pi_j^a\textrm{ for each }1\le j\le r.$$

The equality given on the left hand side follows from the fact that the cycles $\pi_i$ are pairwise disjoint and hence all commute with each other, so taking powers distributes through their product in the way depicted above. The $\Longleftarrow$ direction is clear; Exercise: can you prove the $\implies$ direction?

Now, $e=\pi_j^a\iff {\rm ord}(\pi_j)=\ell_j\mid a$, and $\ell_j\mid a$ for each $1\le j\le n$ iff ${\rm lcm}(\ell_1,\cdots,\ell_r)\mid a$. The order of $\pi$ must be the least nonnegative $a$, so we have ${\rm ord}(\pi)={\rm lcm}(\ell_1,\cdots,\ell_r)$.

The question: We can go further and find more than one $n$ for which $S_n$ contains an element of order strictly exceeding $n$. The orders of elements of $S_n$ are precisely the LCMs of the integer partitions of $n$. (If we include the $1$-cycles in the disjoint cycle decomposition of a permutation, then the sum of the lengths of its cycles is $n$ since every number in $\{1,\cdots,n\}$ appears in precisely one of the cycles.) So our problem is reinvented as a number theory question: for which $n$ do there exist $\ell_1,\cdots,\ell_r\ge1$ such that $\ell_1+\cdots+\ell_r=n$ and ${\rm lcm}(\ell_1,\cdots,\ell_r)>n$?

Exercise: Work out the cases $n=1,2,3,4,5,6$ by hand; for each case either convince yourself there do not exist $\{\ell_i\}$ with such properties or find some explicit examples.

Ideally, if you wished, these exercises can be interactive. I'll help you with them if you want to do them and you get stuck, don't understand something, want a hint etc.

share|improve this answer
add comment

Recall that the order of $S_n = n!$ The group symmetric group $S_n$ on $n$ "letters" is the set of all permutations on the set $A = \{1, 2, 3, \cdots, n\}$. Each permutation is a bijection between $A$ and $A$.

  • There exist permutations of from $A \to A$ which are of order $n$, e.g. $(1 2 3 4 ... n)$
  • There also exists at least one permutation of order $m$ for every $m$ such that $m \mid n$, by the Theorem of Lagrange.
  • Try to think of an example in which the order of a permutation is actually greater than $n$. See comment below for a suggested counter-example from the helpful "anon".

You need only one counterexample for some $n$, $S_n$, where the order of the permutation is greater than $n$.

share|improve this answer
    
(123)(45) has order 6 in S5. –  anon Mar 3 '13 at 0:29
    
Rectified, thanks again, @anon ! –  amWhy Mar 3 '13 at 0:30
    
Seems i have a much more fundamental misunderstanding of whats going on then i first anticipated. –  Faust7 Mar 3 '13 at 0:43
    
In the permutation $(123)(45)\in S_5$ the order is the least common multiple of the lengths of the cycles, which is $3\cdot 2 = 6 > 5$. The cycle notation means 1 maps to 2, 2 maps to 3, 4 maps to 5, and 5 maps to 4. –  amWhy Mar 3 '13 at 0:46
    
The only thing you need to worry about in this question is finding a counterexample, like the one given, selecting n = 5, so for $S_5$ there exists this permutation of order 6. Hence it cannot be the case that the order of a permutation in $S_n$ is always less than or equal to $n$. –  amWhy Mar 3 '13 at 0:49
show 4 more comments

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.