Permutations of a group (Understanding Theory)

[PcumP_Ravenclaw]

Dear all,

Please read the text in the attachment. Then...

1)Explain what is meant by "fix k" and "fixed point of ρ" ?

1a) What does ρ(k) = k mean?

2) How to make the permutation of αβ?

3) What does "re-arranging α so that its top row coincides with the bottom row of β, and remembering that we apply β first" mean and how to do it??

Thank you..

 

[Stephen Tashi]

Think about the definition of a "function" as a set of ordered pairs and you can figure most of those things out
yourself. A function can be presented as a table of values. If the domain of a function is {1,2,3,4} the natural way to write the table is to write it so the domain is "in order".

For example, functions f(x) and g(x) could be defined by tables:x | f(x)

1, 3
2, 4
3, 2
4, 1

x | g(x)
1 , 1
2 , 2
3, 4
4, 3

From those tables, f(1) = 3, f(2) = 4 , g(1) = 1 etc.

You should be able to answer questions like:
What is f(g(3))? (Answer f(g(3)) = f(4) = 1 )

To say a function g "fixes" a value v in its domain means that g(v) = v.
In the example g fixes 1 since g(1) = 1.

Permutations are a special kind of function, they are "1 to 1" mappings and the doman and range are the same set. When people speak of the "multiplication" of permutations, they refer to the "composition of functions". The meaning of the "product" fg is the composition of functions f(g(x)) (or g(f(x)) depending on what book you use).Instead of writing permutations as the ordinary sort of table of values, people find it convenient to abbreviate them as arrays. So, in the above example, you could write f as
$\begin{pmatrix} 1 & 2 & 3 &4 \\ 3 & 4 & 2 & 1 \end{pmatrix}$

where the top row is x and the bottom row is f(x)

The function f could be written as a table with the elements of the domain "out of order" and this table would present the same information as an orderly table. For example, the example of f above could be presented as the table:

x | f(x)

2,4
1, 3
3, 2
4, 1

Writing the table in a different order does not change the definition of f.

If we write the above table in array notation it is:

$\begin{pmatrix} 2 & 1 & 3 &4 \\ 4 & 3 & 2 & 1 \end{pmatrix}$It may seem confusing to write a function by listing the elements in its domain "out of order", but it is useful to do this when studying some aspects of permutations.

 

[PcumP_Ravenclaw]

Hey Tashi, Thanks for the quick reply!

 

[PcumP_Ravenclaw]

Permutations of a set X forms a group means set X with respect to permutations/functions f or g ? or is it the composition of f and g?

Can you give an example of Theorem 1.3.2?? What does the set p(x) of permutations of a finite set X mean?? Does not set of p(x) contain the same elements as set X??
Theorem 1.3.2 The set p(X) of permutations of a finite non-empty set X is a
group with respect to the composition of functions.

 

[Stephen Tashi]

with respect to permutations/functions f or g ? or is it the composition of f and g?

Are you thinking that "permutations" are not functions? In elementary texts, we are told that a "permutation" of things is an "ordered arrangement of them". This is not the high-class way to look a permutations. If you want to understand the use of permutations in group theory, don't use that definition. A permutation is a special kind of function, it isn't a particular arrangement.

Let X be the set {1,2,3}. There are 6 distinct 1-to-1 functions that map X onto itself.

I'll name those functions a,b,c,d,e,f and they are defined by the following tables:

x | a(x)
1,1
2,2
3,3

x| b(x)
1,1
2,3
3,2

x| c(x)
1,2
2,1
3,3

x| d(x)
1,2
2,3
3,1

x| e(x)
1,3
2,1
3,2

x| f(x)
1,3
2,2
3,1


The set of functions G = {a,b,c,d,e,f} is a group if we define "multiplication" in the group to be the operation of composition of functions. (b)(c) is the function b(c(x)) (Some books would define the operation as c(b(x)). See what your text does.) Notice that it is the set G that is the group, not the set X = {1,2,3}.

For example , in the group (b)(c) = e because if you make table for x | b(c(x)) you get the same table as the table for e. ( For example, b(c(1)) = b(2) = 3 and e(1) = 3 )

Of course, there is a relationship between the idea of "an ordered arrangement" and "a function that arranges". It would require some thinking to state that relationship with mathematical precision! In group theory, it's best to think of permutations as functions. An "arrangement" is a static thing and the concept doesn't facilitate thinking about a "product of arrangements". By contrast, thinking of a permutation as a function that arranges allows us to think of that function being applied to any given arrangement to create another arrangement.

 

[PcumP_Ravenclaw]

:thumbs:Thank you for the detailed explanation :)

 

[PcumP_Ravenclaw]

Hey Tashi, can you explain what is in this attachment with regards to the following questions?

1) for the example set x = {1 2 3} say permutation p(x) = (2 1 3) and say integer k = 3rd element. the orbit is 3 1 2? correct?

for another permutation q(x) = (1 3 2) the orbit for k = 3rd element are (3 2 3)

These orbits cyclically permute. so how can these two orbits be identical or disjoint in order to satisfy eqn. 1.3.3??

2) what does "pairwise disjoint sets" mean??

3) what does "p0 fixes every integer that is not in O(k) mean??

4) I don't understand the remaining parts of the paragraph??

 

[Stephen Tashi]

1) for the example set x = {1 2 3} say permutation p(x) = (2 1 3) and say integer k = 3rd element. the orbit is 3 1 2? correct?

Yes. The orbit of 3 is a set, so you should denote it as {3,1,2}

for another permutation q(x) = (1 3 2)

q(x) is the same permutation as p(x) since both denote the function f(x) given by

x | f(x)
1, 3
2, 1
3, 2

Permutations are functions, not arrangements. The notation (r,s,t) denotes the function f given by the table

x f(x)
r , s
s , t
t , r

The notation (r,s,t) is an abbreviation for the above table and for the array notation
$\begin{pmatrix} r & s & t \\ s & t & r \end{pmatrix}$

The notation (1,3,2) is the same function given by the array notation $\begin{pmatrix}1&3&2 \\ 3&2&1 \end{pmatrix}$. Notation such as (1,3,2) is used to for a permutation that is a cycle..

Do you see why the permutation denoted by (1,2,3) is not the identity function?

It would be clearer notation to draw a circle and mark 1,2,3 as points on the circle and understand that the permutation is the function that rotates the circle clockwise so each mark moves to the next mark. However, that notation would take up a lot of space.

the orbit for k = 3rd element are (3 2 3)

The orbit of 3 is {3,2,1}.

These orbits cyclically permute. so how can these two orbits be identical or disjoint in order to satisfy eqn. 1.3.3??

Orbits are sets. The {3,2,1} and {1,2,3} are equal. It doesn't matter in what order you write the elements of a set.

2) what does "pairwise disjoint sets" mean??

It means that the intersection of any two of the sets is the null set.

 

[PcumP_Ravenclaw]

Hey Tashi,
I am making very slow progress in understanding this. I am wondering if Maths is for me?? LOL... Anyway let me just persevere and try to get used to it... LOL

Please see the attachment!

1) What does "Note that ρ and ρ0 have exactly the same effect on the integers in O(k), but that
ρ0 fixes every integer that is not in O(k)." mean??

2) what is "cycle P_j asssociated with the orbit O(Kj)"??

3) what are the cycles P_j? Aren't they same as orbits why are they called cycles?

4) why are P_j pairwise disjoint??

5) what is Pj(x) = p(x) and Pj(x) = x??

 

[Stephen Tashi]

I think your problem is merely with notation. If the set being permuted is {1,2,3}, it might be natural to think that when someone says "the permutation (3,2,1)" that they mean the function give by the table:

x | f(x)
1, 3
2, 2
3, 1

However, this is not the standard notation. "The permutation (3,2,1)" means the function
x | f(x)
1, 3
2, 1
3, 2

"Cycles" are important in the theory of permuations. So the standard interpretation of (3,2,1) is that it is a function that sends each number in the list to the next number in the list and sends the last number in the list to the first number in the list. You read (3,2,1) as the table
x | f(x)
3, 2
2, 1
1, 3
which is the same as the above table when you reorder the rows.

If we are speaking of permutations of the set X = {1,2,3}, the notation ( 1,2) means the function given by the table

x | f(x)
1, 2
2, 1
3, 3

We interpret the fact that "3" does not appear in the list (1,2) to mean that f(3) = 3, i.e. that f "fixes" 3.


Example:

Let X = {1,2,3}. Let p be the permutation p = (1,2) Let k = 2
Then p0 = ( p(2), p^2(2)).
p(2) = 1 and p^2(2) is the function p(p(2)) = p(1) = 2
So p is the cycle (1,2).

To make an better example of the passages, let X = {1,2,3,4}. Let p be the permutation given by the table
x | p(x)
1, 2
2, 1
3, 4
4, 3

Another way to write p is (1,2)(3,4) which exhibits it as "the product of cycles".

Let k = 2

The orbit of 2 is {1,2}
p0 = (p(2) p^2(2)) = (1,2)
Unlike p, the function p0 "fixes" 3

 

[PcumP_Ravenclaw]

Hey Tashi,
can you please explain the following questions and their answers??

compute the product of cycles of the set {1,2,3,4,5,6,7,8}

(1,4,5)(7,8)(2,5,7) = (2,1,4,5,8,7)

1 2 3 4 5 6 7 8
= ( )
4 1 3 5 8 6 2 7

Question: why does the 3rd cycle have an element common in 1st and 2nd cycles?

 

[Stephen Tashi]

You could do the problem "the long way"by writing a table for each of the 3 functions f(x), g(x), h(x) involved and then finding the table for f(g(h(x)). (The "product" of cycles is defined as the composition of functions.)

The abbreviated way to do this begins
h(x) = (2,5,7)
g(x) = (7,8)
f(x) = (1,4,5)

The first thing we see about h(x) is that it maps 2 to 5. g(x) leaves 5 fixed, f(x) maps 5 to 1. So the net effect of f(g(h(x)) is to map 2 to 1. We begin to write down the answer as "(2,1 ".

What does h(x) do t 1? h(x) leaves 1 fixed. g(x) leaves 1 fixed. f(x) maps 1 to 4. So the net effect of f(g(h(x)) is to map 1 to 4. We can further fill out the answer to be "(2,1,4 ".

Then we ask what f(g(h(x)) does to 4, etc.

It may happen that the answer to the product of cycles is not a single cycle, but must be expressed as another product of cycles. I haven't worked problems like this in a long time, but we can probably figure out a systematic procedure. Perhaps someone can give a link to the formal algorithm.

----
There is no rule that says two functions are prohibited from having common symbols when they are written as cycles. So there is no "why" required to explain common symbols.

 

[PcumP_Ravenclaw]

mutually disjoint orbits?? (please help :) )

pertaining to the post 8 by stephen tashi...

why is q(x) equal to p(x) and how do they belong to f(x)? did you just fabricate f(x)??
then is there only one function for a particular set?? e.g. x = {1,2,3} the function is f(x) = {3,1,2}

why is the permutation denoted by (1,2,3) is not the identity function?

New post...

please take a look at the attachement!

cyclically permuted means that the orbit will repeat with the same number of elements in its orbit??

e.g.

tex]
\begin{pmatrix}
1 & 2 & 3 & 4 & 5 & 6 & 7\\
5 & 7 & 2 & 1 & 4 & 3 & 6
\end{pmatrix}
[/tex]

σ = (1 5 4)(2 7 6 3)

so one of the orbits (from 1 or 5 or 4) and one of orbits (from 2 or 7 or 6 or 3) are pairwise disjoint??

what does "where each these sets is cyclically permuted by ρ"? Each set is a pairwise disjoint orbit..

what does "Note that ρ and ρ0 have exactly the same effect on the integers in O(k), but that
ρ0 fixes every integer that is not in O(k)"? what's the difference between cycle and orbit?


what is "Nowconsider the decomposition (1.3.3) of {1, . . . , n} into mutually disjoint orbits,"??

what is "let ρj be the cycle associated to the orbit O(k j )." I thought a cycle is just repetition of an orbit??

Thanks for your help!

 

[Stephen Tashi]

We should first get the elementary concepts straightened out.

is there only one function for a particular set?? e.g. x = {1,2,3} the function is f(x) = {3,1,2}

It isn't clear what you mean by that notation.

If you are asking whether the notations (1,2,3) and (3,1,2) denote the same function, the answer is yes, they do. Those notations use parentheses instead of brackets.

why is the permutation denoted by (1,2,3) is not the identity function?

The notation (1,2,3) indicates a function (which I shall call w(x) ) whose table fo values is given by:

x, w(x)
1, 2
2, 3
3, 1

w(x) is not the identity function. If w(x) were the identity function then w(1) would be 1 instead of 2.

whats the difference between cycle and orbit?

In a permutation group, a cycle is a certain type of function and an orbit is a certain type of set. "Function " and "set" are distinct mathematical concepts. Are you getting the two ideas confused? It's even more complicated that understanding the distinction between "function" and "set" as simple abstractions because in the theory of permutation groups there are several different types of "sets" involved and the basic concept of "function" involves "sets" that are associated with it.

 

[PcumP_Ravenclaw]

doubts with standard representation of permuation, p

Hello everybody,
Please take a look at the attachment from the Algebra and Geometry textbook in this post (They are both from the same page!).

I understand that the orbits O(K_i) are pairwise disjoint sets and where each of these sets is cyclically permuted by p.

This means that if

p =
$$\begin{pmatrix}<br /> 1 & 2 & 3 & 4 & 5 & 6 & 7\\<br /> 5 & 7 & 2 & 1 & 4 & 3 & 6<br /> \end{pmatrix}$$


The permuatations are (1 5 4) and (2 7 6 3). they are also the orbits of elements 1 and 2?

only these two orbits are pairwise disjoint sets. the first orbit set has 3 elements and the second has 4 elements then how they be pairwise checked?? 1 to 2 5 to 7 4 to 6 and 3 to what?

Do the orbits of other elements come from cyclically permuting orbits 1 and 2??


NOW...


what does mutually disjoint orbits mean? and what is p_j, the cycle associated to orbit O(k_j)

so in the above example how to differentiate between orbits and cycles? from my understanding cycle and orbits are the same?

Theorem 1.3.7 states that p is a product of disjoint cycles p1. p2 . . . .pm. so in the above example is p equal to 5 7 2 1 4 3 6 which is also the unique function. and p1 and p2 are (1 5 4) and (2 7 6 3)??

what does "p = p1. p2 . . . .pm that was derived from the orbit decomposition (1.3.3) is unique up to the order of the 'factors' p_j" mean??

what does "number m of factors in this product mean"??

Thank you!

 

[Stephen Tashi]

the first orbit set has 3 elements and the second has 4 elements then how they be pairwise checked??

"pairwise disjoint" refers to a relation between pairs of sets, not a relation between pairs of elements taken from these sets. If we have three sets of letters $S1 = \{a,b,c\}, \ S2= \{e,f,g,h\}, \ S3= \{p,q\}$ then to say the sets are "pairwise disjoint means that the intersection between any pair of the sets is the null set. So $S1 \cap S2 = \emptyset,\ S1 \cap S3 = \emptyset,\ S2 \cap S3 = \emptyset$, etc.

Do the orbits of other elements come from cyclically permuting orbits 1 and 2??

Orbits are sets not sequences or vectors or any mathematical object where the elements have some specified order. The set $\{1,5,4\}$ is equal to the set $\{5,4,1\}$.

You must distinguish between the notation for a set like {1,4,5} (which uses brackets) and the notation for a permutation (i.e. function) like (1,4,5) (which uses parentheses).

The sets {1,4,5} and {1,5,4} are the same set. The permutations (1,4,5) and (1,5,4) are different functions.

 

[PcumP_Ravenclaw]

pertaining to post #15

what does mutually disjoint orbits mean? and what is pj, the cycle associated to orbit O(kj)?

so in the above example how to differentiate between orbits and cycles? from my understanding cycle and orbits are the same?

Theorem 1.3.7 states that p is a product of disjoint cycles p1. p2 . . . .pm. so in the above example is p equal to 5 7 2 1 4 3 6 which is also the unique function. and p1 and p2 are (1 5 4) and (2 7 6 3)??

what does "p = p1. p2 . . . .pm that was derived from the orbit decomposition (1.3.3) is unique up to the order of the 'factors' pj" mean??

what does "number m of factors in this product mean"??

 

[Stephen Tashi]

Many authors of expositions of permutation groups are guilty of not explcity defining "disjoint cycles". Does your text give a definition? If not, your confusion is understandable.

"Orbits" are sets. Their elements are the things being permuted.

"Cycles" are special kinds of functions. A function is a special kind of "set of ordered pairs". Technically, the elements of cycles are ordered pairs. The two cycles denoted by (1,2) and (3,5) are each functions that map 4 to 4, so both cycles contain the ordered pair (4,4). So, as sets of ordered pairs, the cycles (1,2) and (3,5) are not "disjoint". However, the term "disjoint" has a special meaning in the theory of permutation groups. To say two cycles are "disjoint" refers to the fact that the two sets of symbols used to denote them are disjoint sets. So, in that sense, the cycles (1,2) and (3,5) are disjoint.

To describe a specific "orbit", you must give information that it is "the orbit of [such-and-such] under the function(s) [so-and-so]". If the set of objects being permuted is {1,2,3,4,5} then "the orbit of 3 under the cycle (1,2,3)" is the set {3,1,2} = {1,2,3}". By contrast, "the orbit of 4 under the cyle (1,2,3)" is the set {4}.

If you have an arbitrary function f(x) such as:

x ,f(x)
1 3
2,5
3,1
4,4
5,2

then talking about "the orbit of f(x)" is ambiguous. The following orbits are distinct sets:

"The orbit of 1 under the function f(x)" is the set {1,3}
"The orbit of 2 under the function f(x)" is the set {2,5}"
"The orbit of 4 under the function f(x) " is the set {4}

Your textbook makes the observation that the domain of f is the union of disjoint orbits:
{1,2,3,4,5} is the union of {1,3}, {2,5}, {4}

Your textbook says that each orbit can be associated with a unique cycle. For example {1,3} can be associated with the function c(x) given by:

x, c(x)
1,3
2,2
3,1
4,4
5,5

Under this association, you can speak of "the orbit associated with the cycle c(x)". How should we state the procedure for making the association formally? We might say "List the elements in the orbit in an arbitrary order and define the cycle to be the function that sets each element to the next one and the last element to the first".

The fact that we have associated an orbit {1,3} with a particular function c(x) doesn't invalidate the terminology that we use to describe an orbit as belonging to a particular element and a particular function.

"the orbit of 1 under c(x)" is {1,3} = {3,1}.
"the orbit of 2 under c(x)" is {2}
"the orbit of 3 under c(x)" is {3,1} = {1,3}
"the orbit of 4 under c(x)" is {4}
"the orbit of 5 under c(x) " is {5}

It is correct to think that there is a "natural" association between orbits and cycles, but stating this association is more complicated that thinking "an orbit is a cycle".

If you focus on the topic of permuting finite sets of things, you can lose track of what needs to be proved and what is "obvious" because we have good intuition for finite sets. Think for a moment about permutations of infinite sets (e.g. the set of all 1-to-1 mappings of the real numbers onto itself). If g(x) is such a function, could you show that its domain was a finite (or even countable) union of orbits? The difficulty of that question helps in understanding why claiming this is true for functions that permute finite sets does require some proof.