Permutation Group: Understanding Elementary Permutations

[Buri]

My text defines an elementary permutation as follows:

Give 1 <= i < k, let e_i be the element of S_k (where S_k is the set of all permutations of {1,...,k}) defined by setting e_i (j) = j for j not equal to i,i+1; and e_i (i) = i + 1 and e_i (i + 1) = i.

It goes on to say that if f is in S_k, then it can be written as a composite of elementary permutations. But I don't see how {k,2,3,...,k-1,1} can be written as a composite of elementary permutations? I thought of starting from {1,2,...,k} then moving the 1 as follows {2,1,3,...,k} -> {2,3,1,4,...,k} and so on until {2,3,...,k-1,1,k} and then doing the same with k "backwards", but switching the 1 and the k isn't an elementary permutation. So what's the right idea?

Thanks for the help!

 

[Buri]

Here's the page from my text where elementary permutations are defined.

 

[Buri]

See what does the i and i+1 represent in the above? Does it represent the slot of where the numbers are located in the permutation or the actual number in the slot. So if it represented the actual number in the slot, then that would mean that I can only perform elementary permutations on consecutive numbers. So let's say on {1,2,3,4,6,5,...,k} I wouldn't be able to switch the 4 and 6 by using an elementary permutation. But if it represents the slots then I would since the 4 and 6 are in consecutive slots. See for example I have this:

123
213

This one is e_1 as it switches the spots of the 1 and 2. And I also have:

123
132

This is e_2 as it switches the spots of the 2 and 3. But if I compose them e_1 (e_2)

123|123
213|132

=

123
231

But then how would I do this 'by hand'? What I'm doing above is e_1 (e_2). I'd apply e_2 to the permutation to get : {1,3,2}. But then how would I apply e_1 to this? When 1 and the 3 aren't consecutive? Or would I be able to apply e_1 because the 1 and 3 are in consecutive slots? So I would get {3,1,2} which doesn't happen to agree with the above. Whats going wrong here!?

 

[Buri]

I've noticed that if I compose it the other way, I get {3,1,2} which is supposed to be e_1(e_2) but instead I'm getting its e_2(e_1). This is confusing...

 

[Buri]

Wait a second. I just really really did it by hand and I do get the correct answer. I actually evaluated e_2(1), e_2(2) and e_2(3) and then applied e_1 to each and I get 2,3,1 respectively. So I suppose that you're not supposed to do it as above when I said I did it by hand. It doesn't work to apply e_2 on {1,2,3} to get {1,3,2} and then apply e_1 on {1,3,2} to get {3,1,2}.

Can someone please help me out? I would really appreciate it!

 

[Buri]

I guess these elementary permutations only act on {1,2,...,k} and on nothing else?

 

[HallsofIvy]

? Thats what all permutations act on!

 

[Buri]

Yes I've realized that now lol Could you maybe help me out with the other posts in the thread? But I guess then the i and i+1 actually represent consecutive numbers rather than consecutive slots. But still I don't see how I could write {k,2,3,...,k-1,1} as a composition of elementary permutations. Could you help? I've tried using the method in the proof for {4,2,3,1} but I still can't.

 

[Buri]

Anyone?

 

[Deveno]

? Thats what all permutations act on!

no, permutations act on ANY set. it is customary to represent the elements of such a set as:

{1,2,3,...} instead of {a,b,c,...} because the names of the permuted elements aren't important, just their POSITIONS.

but through a standard abuse of notation, the position names are given to the elements.

this is the distinction between "first" and "one", "second" and "two", etc.

anyway, the thing to realize is that one should not confuse the image of a permutation with the permutation itself. this is a permutation:

a-->a
b-->c
c-->d
d-->b

writing this as {a,c,d,b} can be confusing, especially when one considers the possible confusion with cycle notation.

the above permutation is also the same as:

1-->1
2-->3
3-->4
4-->2, it is the functional shuffling that represents the permutation, not the domain/image set.

another thing to be aware of, is that permutation multiplication is defined differently by different authors. so take ab to mean first do b, then do a (in accordance with functional composition), but some authors mean the opposite.

let's see if we can get:

1-->4
2-->3
3-->2
4-->1 just by swapping adjacent (numerical) elements.

first, we swap 1 and 2:

1-->2
2-->1
3-->3
4-->4, then we'll swap 2 and 3:

1-->2-->3
2-->1-->1
3-->3-->2
4-->4-->4, now we'll swap 3 and 4:

1-->2-->3-->4
2-->1-->1-->1
3-->3-->2-->2
4-->4-->4-->3, 4 is in the correct place now, so we should leave it alone, so now we swap 1 and 2 again:

1-->2-->3-->4-->4
2-->1-->1-->1-->2
3-->3-->2-->2-->1
4-->4-->4-->3-->3, and swap 2 and 3 again:

1-->2-->3-->4-->4-->4
2-->1-->1-->1-->2-->3
3-->3-->2-->2-->1-->1
4-->4-->4-->3-->3-->2, now 3 is in the correct place, so swap 1 and 2 one last time, and voila!

1-->2-->3-->4-->4-->4-->4
2-->1-->1-->1-->2-->3-->3
3-->3-->2-->2-->1-->1-->2
4-->4-->4-->3-->3-->2-->1

 

[Buri]

no, permutations act on ANY set. it is customary to represent the elements of such a set as:

{1,2,3,...} instead of {a,b,c,...} because the names of the permuted elements aren't important, just their POSITIONS.

but through a standard abuse of notation, the position names are given to the elements.

this is the distinction between "first" and "one", "second" and "two", etc.

anyway, the thing to realize is that one should not confuse the image of a permutation with the permutation itself. this is a permutation:

a-->a
b-->c
c-->d
d-->b

writing this as {a,c,d,b} can be confusing, especially when one considers the possible confusion with cycle notation.

the above permutation is also the same as:

1-->1
2-->3
3-->4
4-->2, it is the functional shuffling that represents the permutation, not the domain/image set.

I'm not exactly sure what you're saying. So does it mean that they act on a set that has some order defined on it? Like if I'm looking at S_k and looking at the permutations of {1,2,...,k} the permutations always act on this set in this exact order. So it wouldn't make sense for me to apply a permutation f to a set {1,3,2,...,k}. Am I'm getting this?

 

[Deveno]

no, a permutation of the set {1,2,3,...,k} will still be the same set. but the permutations are FUNCTIONS on this set, in particular bijections. it usually isn't the case that f(k) = k, for example. now, how does one indicate a function?

well, one way is to list the pairs (x,f(x)) in the function. that is what i have done above.

1-->n means the permutation f maps 1 to n. the SET of images, and the SET of domain elements are the same set. but if you impose an order on the set, by listing them in some way, a permutation "changes the ordering".

writing permutations as:

1-->2
2-->3
3-->4
4-->1

or as:

1234
2341

is a cumbersome notation. a much more compact notation is cycle notation, where you write (1 2 3 4) for the permutation i have written above. this is interpreted as 1-->2, 2-->3, 3-->4, 4-->1.

 

[Deveno]

in cycle notation, the permutation you asked about:

1-->4
2-->2
3-->3
4-->1

is (1 4) (2 and 3 are "fixed"). as a product of transpositions of the form (i i+1) this is:

(1 4) = (1 2)(2 3)(3 4)(2 3)(1 2).

 

[Buri]

Okay, I understand that in sets order doesn't matter but since they're permutations and frankly the notation {1,2,...,k} is wrong, but with the order the permutation premutes the elements of the set (assuming some initial order). But then another permutation is always acting on this set to which I've assigned some order. Never on another set that has a different order right?

 

[Buri]

I don't know transpositions...see all I know about permutations is basically what's on the page I posted. Its not a course in group theory, but analysis and the permutations are only being introduced to develop the alternating tensor.

 

[Deveno]

you would do better not to think of "ordering" and think instead of permutations as functions which have a source, and an image. an ordering of a set is a somewhat arbitrary thing, but the function which is constant on a set except for i, i+1, and sets:

i-->i+1
i+1-->i is unambigous.

well permutations are used throughout all kinds of things, in the definition of determinants, for example.

a transposition is just a generalization of the idea of an elementary permutation. instead of swapping adjacent numerical values, it exchanges any 2, adjacent or not.

 

[Buri]

So the i's in the above refers to the position of the numbers? Or does that literally mean f(i) = i + 1 so for example f(2) = 2 + 1 = 3. Or does that refer to, a is in position 2 and b is position 3 so therefore, f(a) = b and f(b) = a.

 

[Deveno]

your second interpretation is more accurate. usually, the set of things being permuted in tensor analysis are indices, so these will often be just numbers.

but the indexing set might be something else, so that you have v_a1 etc. for some index set A.

 

[Buri]

So the i and i+1 aren't the values of the permutation? But rather the position (that is adjacent values)?

See like {1,2,3,5,6,7}. Would an elementary permutation be able to swap the 3 and 5? Because I'm confused as to what exactly is meant by the e_i (i + 1) = i and e_i (i) = i + 1. Does that mean it swaps the value in the ith position with the value of the i + 1 position. Or does it mean that the value at a certain position is i and the one next to it is i + 1 and so it swaps these two. But like in the example I gave above 3 and 5 aren't consecutive so I wouldn't be able to do it in one step if that what it meant...

 

[Buri]

But I guess if it means position and value, in my case since its the set I = (1,2,3, ..., k) that I'm permuting the position and the value are the exact same thing.

 

[Deveno]

i understand your confusion. i do. if your set was {1,2,3,5,6,7} then swapping 3 and 5 would indeed be an "elementary permutation".

but in practice, the set being permuted is just called {1,2,3,4,5,6} with the understanding that "1" means "1st thing", "2" means "2nd thing" etc.

in your book, as near as i can ascertain, the "underlying set" being permuted is actually {1,2,3,...,k} so the author would not allow swapping 3 and 5 as "elementary"

 

[Buri]

I see. So how would I then be able to write {k,2,3,...,k-1,1} as a composite of elementary permutations? It just seems that I'll have to swap two non-consecutive numbers to do so. And just a question about compositions. if I have to permutations f and g. g will permute {1,2,...,k} some set A'. But fog is NOT applying f to A' right? But rather once again to {1,2,...,k}?

 

[Deveno]

remember you are composing functions, not positions.

you should think of terms of what f does to each element, not what it does to "the order".

so if g maps the integer k to m, and f maps the integer m to r, then fog maps k to r:

k--->m--->r

 

[Buri]

Ahhhh this is starting to make more sense to me now :) So I guess that's what I was doing wrong before and it only worked until I actually wrote these functions out like you just did. So I guess I should really just think of these as functions and ignore the entire position thing because its what's been confusing me. But I guess I still don't see how to permute the set I asked about earlier. I even tried with smaller numbers, but don't see why. Thats why I tried finding a "geometric" sort of understanding of permutations with all this positions stuff I've been going on about to somehow find the elementary permutations. Would you any idea how about doing that?

 

[Deveno]

here, in excruciating detail is what we get when the set is {1,2,3}. first, the identity map:

1-->1
2-->2
3-->3

then the elementary permutation e1,2:

1-->2
2-->1
3-->3

then the elementary permutation e2,3:

1-->1
2-->3
3-->2

next, we have (e1,2)o(e2,3):

1-->1-->2
2-->3-->3
3-->2-->1 (to see the overall effect, just "erase the middle")

next we have (e2,3)o(e1,2):

1-->2-->3
2-->1-->1
3-->3-->2

there is just one more:

1-->3
2-->2
3-->1, which is (e1,2)o(e2,3)o(e1,2)

 

[Deveno]

for certain subsets of permutations, you can see these as geometric isometries. but these are quite limited. for example, the symmetries in the plane of the triangle correspond to the full set of symmetries on 3 objects, but the symmetries in the plane of the square are just a subset of the full set of symmetries on 4 objects (for example, twisting a square into a bow-tie leaves the vertices intact, but destroys the "squareness"). to get the full symmetry set on 4 objects, you need to consider a tetrahedron in 3-space, and the higher symmetry groups require higher dimensional objects.

 

[Deveno]

where all this is going, is that eventually your book will develop a notion of the "sign" or "parity" of an alternating tensor, which is crucial to their definition. and that depends on the sign or parity of an associated permutation of indices.

 

[Buri]

I see how this works now. I'll work out a longer one just to do it myself. Thanks a lot for you help. I feel like I understand this stuff a lot better now :) I appreciate your help :) Thanks :)

 

[Buri]

I have to head out right now, but I'll read your further posts later today. Thanks.

 

[Buri]

I've read your lasts post and thanks a lot. I get it now. Thanks for your help :)