# Permutations and cycles - linear algebra

1. Jan 24, 2010

### Kate2010

1. The problem statement, all variables and given/known data
Let $$\rho$$ $$\in$$Sym(n), p be prime, r be the remainder when n is divided by p (so 0$$\leq$$r<p and n=qp+r for some integer q).

1. Show that $$\rho$$^p = $$\iota$$ iff the cycles of $$\rho$$ all have lengths 1 or p.

2. Show that if $$\rho$$^p = $$\iota$$ then |Supp($$\rho$$)| is a multiple of p and |Fix($$\rho$$)|$$\equiv$$ r(mod p).

2. Relevant equations
Fix($$\rho$$) := {x|x$$\rho$$ = x}
Supp($$\rho$$) := {x|x$$\rho$$ $$\neq$$ x}

3. The attempt at a solution

I really don't have many ideas on these at all.

1) If all cycles have length 1 then it is clear that $$\rho$$p is the identity.
I don't know what I can deduce from all cycles having length p. The other way around, I can see if we have the identity that all cycles could be length 1, but I don't know how to go about getting length p.

2) I have no idea how to start this.

Thanks.

2. Jan 24, 2010

### JSuarez

When you write a permutation $$\rho$$, of lenght n, in terms of cycles, you have:

$$\rho = \left(a_1...a_{k_1}\right)\left(a_{k_1}...a_{k_2}\right)...\left(a_{k_i}...a_{k_j}\right)$$

The cycles' lengths must sum to n and, if $$\rho^d = I$$, then all cycles must have undergone a full rotation after d iterations.

But this implies that d must divide your prime p. Now, what are the possible divisors of p?

As for (2), it's just a translation of the division n = qp + r in terms of the cycles: the cycles oh lenght p correspond to a factor in qp, and r = 1+1+...+1 (r times) are the cycles of lenght one.

3. Jan 24, 2010

### Kate2010

Thank you so much! I've just started with permutations and as of yet I haven't really grasped it, but I do understand that now.

Another question:

If t1 and t2 are transpositions in Sym(n), then show that t1t2 = I, (t1t2)2 = I or (t1t2)3 = I (I is the identity permutation).

What condition on t1 and t2 determines which of these occurs?

What is the cycle structure of t1t2 in each case?

4. Jan 24, 2010

### JSuarez

A transposition is a permutation that exchanges just two elements; in terms of cycles, a transposition has a cycle of lenght 2, and all the others of lenght 1.

It's immediate that any transposition t verify t^2=I; it's less immediate that they generate the symmetric group, but they do: any permutation is the product of transpositions.

For any two transpositions t1 and t2, your three cases correspond to:

(1) t1 = t2; this gives t1t2=t2t1=I.

(2) t1 and t2 are disjoint (their 2-cycles don't affect each other); in this case t1t2 is a permutation with exactly two 2-cycles (the others are 1-cycles).

(3) The 2-cycles of t1 and t2 share one common element, so t1t2 has one 3-cycle (and the rest are 1-cycles).

5. Jan 24, 2010

### Kate2010

Thank you again!

One last question:

Let $$\rho$$ be in Sym(n). For which values of n is it true that if $$\rho$$ is even then $$\rho$$^m = I for some odd integer m?

Is this true for n=km where k is a natural number?

:)