Talk:Permutation group

Article needs more exposition

I find the (very brief) introduction of cyclic form still rather opaque. We ought to aim for a clearer explanation of what, for example, " (1,2,4)(3)" means.

152.3.68.83 (talk) 14:33, 25 July 2013 (UTC)

Two points: 1. I know quite a lot of mathematics, but this introduction is opaque, FULL of jargon, and of little value. The purpose of an article in Wikipedia is to teach and inform. it is not a place for people to expound what they know. This article puts me off utterly. 2. The intro to this and many math wikis omits the 'So what' factor. For example permutation groups are very important to physics, apparently. How? Meaning in what way?

Centroyd (talk) 09:44, 19 July 2014 (UTC)

Examples of permutation groups

I added two examples from my own work. Others may argue that this is too egocentric. Cullinane 21:54, 10 August 2005 (UTC)

Permutations of infinite sets?

I would be interested to know about permutations (and permutation groups) of infinite sets (eg: Z or Q). The article says that "if M is any finite or infinite set, then the group of all permutations of M is often written as Sym(M)". I'm interested to know how a permutation would be defined for an uncountable set like R.

If you know anything about this topic please include some information here (or start another article about it).

Sorry, forgot to sign that last commentDonkeyKong the mathematician (in training) 06:48, 28 May 2006 (UTC)

A permutation of M may be defined as a bijection of M into itself (an automorphism in the category of sets), thus S(M) is the set of all such permutations for a given set M. Of course one cannot "explicitely" write the correspondence table

    [  x1     x2    ... ]
f = [                   ]
    [ f(x1)  f(x2)  ... ]

of such a permutation, if it has an infinite support; however, this is possible if it has a finite support (supp f = { x | f(x) <> x }), in which case one would only write the elements on which it acts nontrivially. In that case, one can also decompose it into cycles and define its order etc. in the usual manner. It's easy to see that the subset So(M) = { f ∈ S(M) | suppf is finite } is a (normal) subgroup of S(M). — MFH:Talk 03:02, 11 November 2006 (UTC)

Inversions and transpositions

{NOTE that the permutation 4,3,1,2 has five inversions but only three transpositions. There is an error in the text} —Preceding unsigned comment added by 01001 (talk • contribs)

Isomorphisms and the symmetric group

I disagree with the following paragraph:

"If (G,M) and (H,M) such that both G and H are isomorphic as groups to Sym(M), then (G,M) and (H,M) are isomorphic as permutation groups; thus it is appropriate to talk about the symmetric group Sym(M) (up to isomorphism)."

If M is finite and a group G of permutations of M is isomorphic to Sym(M) as a group, then it has the same cardinality and hence it contains all the permutations of M, hence it is also equal to Sym(M). Using this argument, we can conclude that the symmetric group Sym(M) is simply unique. However, the uniqueness of Sym(M) was already clear in the introduction when it was defined as (the) group of all the permutations of M with function composition as an operation.

If M is infinite, I think the statement is false in general, but anyway I think the paragraph wasn't meant to address this case.

In conclusion, I would delete the paragraph. Marcosaedro (talk) 07:00, 7 March 2009 (UTC)

I agree that the statement is either trivial or false, so not very informative in either case. There is even a finite counterexample to the less trivial claim for permutation representations (Sym(6) has two non-isomorphic permutation representations on 6 element sets), so I think that even if the statement were corrected, it would still be confusing and still would not say anything enlightening. JackSchmidt (talk) 15:22, 7 March 2009 (UTC)

I also don't understand your example. It's the first time I hear about permutation representations.

Update: I found a definition in the article on group representation. It says that a group representation of a group G on a set M is an homomorphism from G to Sym(M). This definition seems counterintuitive to me, because it doesn't require the homomorphism to be inyective, and it therefore doesn't encode all the knowledge of G.

Update: What I would have called representation is actually called faithful representation.

Do you mean that there are two morphisms from G=Sym(6) to Sym(X) (being X a six-element set) whose images are isomorphic as groups but are not conjugates of each other? I would expect those morphisms to be non-injective, because with a cardinality argument we can see that injectivity implies surjectivity. Anyway, which is the claim that this example intends to disprove?

MetaWiki: I'm quite new to Wikipedia. I understand that with this comment I'm drifting away from the purpose of improving the article, because the paragraph is unlikely to reappear. Is this talk page suitable for this kind of discussion? (And do you have the time?) Marcosaedro (talk) 22:44, 7 March 2009 (UTC)

If X is a six element set, then there are two injective homomorphisms f, g from Sym(6) to Sym(X) such that there is at least one π in Sym(6), where f(π) is not conjugate in Sym(X) to g(π). Of course the full image of f and g are conjugate (even identical), it is just the conjugating element doesn't match up the same elements of Sym(6). This happens precisely because Sym(6) has an outer automorphism (and no other finite symmetric group does). In the language of permutation representations, the images are permutation isomorphic, but the representations are not.

This would be a counterexample to "For finite sets X, every permutation representation of Sym(X) is isomorphic, so it makes sense to talk about the permutation representation of Sym(X)."

Metawiki: if the discussion drifts too far or too long, the reference desk is a better place to discuss with the community. However, a short discussion might reveal a way to add something nice to the article (or one of its relatives), and might help future editors understand our current point of view. JackSchmidt (talk) 02:50, 8 March 2009 (UTC)

Definition

I wonder if a more exact definition of a permutation group would be something along the lines of "A permutation group is a pair (G, M) where M is a set and G is a group acting on M; when no ambiguity can arise, it may be simply denoted by G. Two permutation groups are said to be isomorphic (as permutation groups) provided there exists a map blah blah blah such that blah blah blah".

Or, perhaps "A permutation group is a group G together with a set M such that G acts on (or permutes) M."

See the way topological space is defined in Topological spaces, which somehow seems both more natural and more exact.

(Of course, if every group theory book in the world does it the way the article does, then there's no leeway to make a change.) Son of eugene (talk) 08:51, 31 December 2010 (UTC)

The group operation is "composition of permutations", which ought to be defined. — Preceding unsigned comment added by 71.167.39.230 (talk) 02:50, 2 May 2014 (UTC)

(1 2 3 4) on {1, 2}

Perhaps this is a rather silly question for those who are familiar with the subject, but what is the result when a permutation g =(1 2 3 4)|g $\in$G acts on A={1,2}? This operation should be possible: we can construct G from {1,2,3,4}, abstract it out into a group, and make it act on {1,2}. I am confused because what (1 2 3 4) is telling me is that move the 2nd element to the 3rd position, but there is no 3rd position! In particular, If i assume that gA={1}(i.e that 2 is chucked out of the set), then what about g³=(1 4 3 2) acting on A? What I mean is, {}=g²(gA) ≠ (g³)A={2}, which violates the associativity of group action! Pratik.Mallya ^Talk! 23:32, 2 March 2011 (UTC)

I think perhaps the concrete example of permutation, as I have it here, can only apply to the set from which they were originally constructed? Pratik.Mallya ^Talk! 23:43, 2 March 2011 (UTC)

In order for a group G to act on a set S, each element g of G must map S to S. In other words, the set S must be fixed setwise by action of any group element. So, in your case, G does not act on A, since the permutation g does not send elements of A to elements of A. See group action. -Krasnoludek (talk) 00:05, 24 March 2011 (UTC)

Cayley's Theorem

I feel it would be worthwhile to mention Cayley's Theorem (dedicate a section/ just link) at some point on this page. To me this is the reason that these groups are so important... --ShmulikG (talk) 15:42, 11 March 2013 (UTC)

Examples section

I have temporarily moved a recent edit here. The moved section is:

While we can think of a single permutation as a rearrangement of our objects, 1,2,3 and 4 in the present case, it is easier to understand permutation groups if we think of a permutation P of n objects as a mapping of the set of objects onto itself. We can present it as a table

$P={\tbinom {a_{1}\ a_{2}\ \dots \ a_{n}}{b_{1}\ b_{2}\ \dots \ b_{n}}}.$

If Q is another permutation

$Q={\tbinom {b_{1}\ b_{2}\ \dots \ b_{n}}{c_{1}\ c_{2}\ \dots \ c_{n}}}\$

the composition or product of the permutations is defined as

$\ PQ={\tbinom {a_{1}\ a_{2}\ \dots \ a_{n}}{c_{1}\ c_{2}\ \dots \ c_{n}}}.$

Note that the convention for the composition of permutations is the opposite of the convention used when forming the composition f∘g of two functions. In PQ we apply P first and Q afterwards, but when we form f∘g we apply the second function g first.

Example. Let

$P={\tbinom {1\ 2\ 3\ 4}{2\ 1\ 4\ 3}},\ \ Q={\tbinom {2\ 1\ 4\ 3}{2\ 3\ 4\ 1}}={\tbinom {1\ 2\ 3\ 4}{3\ 2\ 1\ 4}}.$

Then $PQ={\tbinom {1\ 2\ 3\ 4}{2\ 3\ 4\ 1}}$ and $QP={\tbinom {1\ 2\ 3\ 4}{4\ 1\ 2\ 3}}.$

PQ is also called the product of the group elements P and Q. As we just saw, this kind of multiplication is not usually commutative.

I think that this attempted rewrite is meant to be a gentler explanation of what it replaces and I am in favor of that, but it is not up to the standards for WP articles. I thought that it would be better to point out the problems and fix them here before putting it back into the article.

• One problem is the non-encyclopedic tone of the passage created by the constant use of the pronoun "we".
• The first sentence refers to a four element set, but the rest of the paragraph talks about a general n element set.
• The sentence about the order of composition is misleading. Both conventions are in common use and the one being touted here (while my personal preference) has been losing ground for the past few decades.
• There are no citations given in the section and while they are not needed here for verifiability, they are needed to give readers a place to go to get more information.

These problems need to be fixed. A less serious issue is the use of the two-line notation for permutations. While not incorrect, any reference on permutation groups is going to use cyclic notation and a reader, starting from this page, will not be prepared for that. I suggest using both notation styles initially and then phase out the two-line notation. I also think that the font size used by the \tbinom command is a bit small for this display (especially for the general expessions). Bill Cherowitzo (talk) 05:25, 3 May 2014 (UTC)

Howler

The Neutral element and inverses section contained the statement:

"In cycle notation one can reverse the order of the elements in each cycle to obtain a cycle notation for its inverse. Thus,

$[(125)(34)]^{-1}=(521)(43)=(152)(34).$"

This is a case of the wrong procedure leading to the correct result. It's correct in this case because (125) and (34) have no common element, and so they commute. This is not true in general for permutations with common elements. For example:

$[(12)(13)]^{-1}=(13)(12)\neq (12)(13)$

The error here may have been to assume that cycle notation only applies to the orbits of a permutation, but it doesn't. (125)(34) can also be written as (15)(12)(34) -- a product of 2-cycles. This is also in "cycle form", but its first two terms don't commute. --Stfg (talk) 12:53, 23 July 2015 (UTC)

Assessment comment

The comment(s) below were originally left at Talk:Permutation group/Comments, and are posted here for posterity. Following several discussions in past years, these subpages are now deprecated. The comments may be irrelevant or outdated; if so, please feel free to remove this section.

Cronholm144 06:15, 21 May 2007 (UTC) I may be mistaken, but I am under the impression that there is some ambiguity on the meaning of "bijective," since it relies on "surjective" or "injective" which has ambiguity in definition. Some people require different constraints about being 1-1 and onto with those two words; can a simpler choice of language be given? —Preceding unsigned comment added by Enjolras1789 (talk • contribs) 14:00, 29 January 2010 (UTC)

Last edited at 14:00, 29 January 2010 (UTC). Substituted at 02:28, 5 May 2016 (UTC)

Complete Cayley theorem

Cayley's theorem says there is a 1 to 1 correspondence between groups and subgroups of Sn=permutation groups. As we know, permutation groups can be thought as subgroups of Sn. That means, by Cayley theorem, they are in 1 to 1 correspondence with axiomatic groups. This is extremely important to notice, because it connects this not-so used today notion directly to a fundamental concept taught today in math degrees and courses. — Preceding unsigned comment added by Santropedro (talk • contribs) 20:23, 17 January 2017 (UTC)

Merger Proposal

I'm proposing to merge Rank 3 permutation group, Oligomorphic group, and Primitive permutation group into this article. Each of the 3 articles is quite short, with Rank 3 permutation group consisting largely of examples and both Oligomorphic group and primitive permutation group being stub class articles. Each of these three articles are specific cases of permutation groups, and would make the most sense in the context of permutation groups at large. --TripleShortOfACycle (talk) 05:28, 17 May 2020 (UTC)

Oligomorphic group is a teensy article and merging seems like a no-brainer. The material at Primitive permutation group also seems like it could be comfortably covered here. The table at Rank 3 permutation group is really enormous, and I do not think that at present that article fits so well with this one -- there is no discussion of transitivity or of rank in this article. (I would be inclined to call that a significant oversight or failing of the present article that should eventually be fixed; but as long as it's not fixed, the content of Rank 3 permutation group fits poorly.) Because of the huge table, I would suggest at most a short gloss with a {{main article}} link. --JBL (talk) 12:52, 29 May 2020 (UTC)

I have merged Oligomorphic group here. --JBL (talk) 14:38, 10 June 2020 (UTC)

I changed my mind about whether Primitive permutation group can be included here: it's a short article, but it's heavily technical. Instead, I have included a short definition and example here, with a pointer back to the main article. I will try to do the same thing with rank eventually. --JBL (talk) 14:36, 5 July 2020 (UTC)

@Joel B. Lewis: I think that's probably the right thing to do. I've been contemplating the merge for the past few days and I didn't like the amount of work needed to reduce the technicality so that it would fit in this article. I also agree that the rank 3 article should remain separate, that table would never fit this article. --Bill Cherowitzo (talk) 19:41, 5 July 2020 (UTC)

Merger with Symmetric group

https://en.wikipedia.org/wiki/Symmetric_group

I believe they talk about the same topic? 100.36.227.237 (talk) 02:36, 7 October 2021 (UTC)

No: Read the first paragraph of this article. The symmetric group is a specific permutation group. It has many important properties that are not shared by other permutation groups, and justify a specific article. D.Lazard (talk) 10:00, 7 October 2021 (UTC)

No, certainly not. --JBL (talk) 10:09, 7 October 2021 (UTC)

Notation for composition

The article says (and some other articles are similar):

There are two ways to denote the composition of two permutations. In the most common notation, $\sigma \cdot \tau$ is the function that maps any element x to $\sigma (\tau (x))$. The rightmost permutation is applied to the argument first [cite to Biggs]

A different rule for multiplying permutations comes from writing the argument to the left of the function, so that the leftmost permutation acts first.[cites to Dixon&Mortimer, Cameron and Jerrum] ...In this notation, the permutation is often written as an exponent, so σ acting on x is written x^σ; then the product is defined by $x^{\sigma \cdot \tau }=(x^{\sigma })^{\tau }$. This article uses the first definition, where the rightmost permutation is applied first.

I work with permutation groups quite often and I'm pretty sure I have never seen the notation $\sigma \cdot \tau$. In particular, the source Biggs doesn't use a dot, but just writes $\sigma \tau$. None of the three cites for the second rule use a dot either. So the dot has to go.

I also object to "most common notation" as it is OR and unprovable. Maybe in some fields of mathematics or science it is the most common, but within the domain of group theory it is probably the least common. I did a quick survey of books: Here is the image of $x$ under "$\sigma \tau$" :

right-to-left inline $\sigma \tau x=(\sigma \tau )(x)=\sigma (\tau (x))$ Kerber, Representations of Permutation Groups (1971); Biggs&White, Permutation Groups and Combinatorial Structures (1979).

left-to-right inline $x\sigma \tau =(x)(\sigma \tau )=((x)\sigma )\tau$ Passman, Permutation Groups (1968); Cameron, Permutation Groups (1999).

left-to-right exponential $x^{\sigma \tau }=(x^{\sigma })^{\tau }$ Wielandt, Permutation Groups (1964); Dixon&Mortimer, Permutation Groups (1996); Bhattacharjee et al, Notes on Infinite Permutation Groups (1998); Holt et al, Handbook of Computational Group Theory (2005); Huppert, Endliche Gruppen I (1967); Praeger&Schneider, Permutation Groups and Cartesian Decompositions (2018); Seress, Permutation Group Algorithms (2003); Encyclopedia of Mathematics (2002+).

A permutation group specialist that I discussed this with believes that the preference for the exponential notation in that field derives from the enormous influence of Wielandt's little book (and also that it works very well). As I said, preferences may be different outside that field. I plan to reword that section of the article to lead with the exponential notation and mention the other two as alternatives. I'll wait a short while for comments first. McKay (talk) 06:08, 12 April 2024 (UTC)