Talk:Parity of a permutation

Method of finding parity of a permutation based on determinant of a permuted Identity matrix

Guys, I just want to mention that there's a beautiful formula (IMHO) that finds the parity of a permutation by using determinant of an Identity matrix with rows exchanged according to the permutation. The formula follows from the fact that the determinant of an Identity matrix is "1" if there are even number of row (or column) exchanges, and "-1" otherwise. I thought it might be useful for any person looking at this page to find a quick way to compute the parity of a given permutation. Also: I do not know a link to the first source of this formula. Whaddyathink? Aravindh (talk) 16:52, 4 June 2018 (UTC)

Yes, this appears (briefly) in the article: in the penultimate paragraph of the section "properties". --JBL (talk) 19:03, 4 June 2018 (UTC)

Indeed, I see it now. Earlier, I just dismissed it as a continuation of the method based on cycles. Do you think it makes sense to highlight this or present it in more detail? Aravindh (talk) 15:52, 5 June 2018 (UTC)

I think that would be reasonable. (There are many possibly further things one could say about it.) --JBL (talk) 20:07, 5 June 2018 (UTC)

Ok, I'll try to propose something this weekend. Take care -- 78.53.16.111 (talk) 20:49, 7 June 2018 (UTC)

"The fifteen puzzle actually involves a gruopoid"

There is no need to discuss groupoids in the context of the 15 puzzle: the valid permutations of the puzzle that keep the blank square in the bottom-right form a group, with a group-action on the physical puzzle. It is through the discussion of this group that one may prove the impossibility of certain configurations.

I'm removing the comment for this reason.

Usual left versus right, positions versus values issues

@Kirstein314: Here is a consistent set of choices: 231 denotes the permutation (function) with values w(1) = 2, w(2) = 3, w(3) = 1. In cycle notation, this is written (1 2 3), and is equal to (1 2)(2 3), to (1 3)(1 2), and to (2 3)(1 3). Reading these products from right to left, they can be interpreted as follows:

• (1 2)(2 3): starting from the identity 123, first switch the values 2 and 3 (producing 132), then switch the values 1 and 2 (producing 231).
• (1 3)(1 2): first switch 1 & 2 (producing 213), then switch 1 and 3.
• (2 3)(1 3): first switch 1 & 3 (producing 321), then switch 2 and 3.

This is consistent with the usual order for functional composition, acting on the left: (2 3)(1 3) applied to 1 is (2 3) applied to 3 is 2 (which agrees with w(1)). We could also read these products from left to right:

• (1 2)(2 3): starting from the identity 123, first switch the entries in positions 1 and 2 (producing 213), then switch the entries in positions 2 and 3 (producing 231).
• (1 3)(1 2): first switch positions 1 & 3 (producing 321), then switch positions 1 and 2.
• (2 3)(1 3): first switch positions 2 & 3 (producing 132), then switch positions 1 and 3.

This is also perfectly internally consistent. I believe that, at present, the article correctly obeys this consistent set of choices, with the minimum amount of explanation necessary to rule out any other set of conventions. It is inevitable in any article with concrete examples concerning permutations that a convention must be chosen, and different textbooks use different conventions, so it would be helpful to be clear about whether the argument is with the internal consistency of what is written, or between the convention used in the article and the convention used somewhere else. Thoughts? --JBL (talk) 21:19, 6 January 2022 (UTC)

@JayBeeEll: First off, I totally agree that this boils down to a debate about notation. Your notation is internally consistent at first blush, I'll grant you. But I have three big objections:

1) It's not actually as internally consistent as you think, those are misleading examples

2) It's not consistent with the notation in the wider mathematical community

3) It is extremely misleading about the nature of permutations as abstract objects, which is why the that notation isn't favored more broadly.

First, to show how that notation breaks the consistency you were hoping for, consider the example (1 2)(1 2 3) Applied, as per your notation, left to right, we get:

• (1 2) applied to 123 becomes 213
• (1 2 3) applied to 213 becomes 132

Where as when you apply it from right to left:

• (1 2 3) applied to 123 becomes 312
• (1 2) applied to 312 becomes 321

This is actually backed up by the main page on permutations which says "In general, composition of two permutations is not commutative, that is, $\pi \sigma \neq \sigma \pi .$".

To the second point, I'll just point you at "Advanced Modern Algebra" by Rotman for which a PDF can be found on google.

His example on page 42 has (1 2)(1 3 4 2 5)(2 5 1 3) become the permutation 42513 which equals (1 4)(2)(3 5) in cycle notation. If your notation were used applying them right to left that should result in:

• (2 5 1 3) being applied to 12345 to become 53142
• (1 3 4 2 5) being applied to 53142 to become 21534
• (1 2) being applied to 21534 to become 12534

When what the author actually does is compose all three together at once by tracing the path of each value. For example, first position goes to 3 in (2 5 1 3), then from there to 4 in (1 3 4 2 5) then remains fixed in (1 2).

• 1 goes to 3 goes to 4 stays at 4
• 2 goes to 5 goes to 1 goes to 2
• 3 goes to 2 goes to 5 stays at 5
• 4 stays at 4 goes to 2 goes to 1
• 5 goes to 1 goes to 3 stays at 3

This results in the permutation 42513.

(Annoyingly, by pure coincidence, when applying your method from left to right you do get to the same result, 42513, which kind of undermines the value of this example. However the author states explicitly, "We multiply permutations from right to left, because multiplication here is composite of functions;")

To back up my point that this notation is used broadly by other mathematicians, and that this is not just a one off example, I'll pull another example from the book I used in college

In this example, the author shows that (2 4 3)(1 2 4 3) = (1 4 2 3) And I think we both agree that (1 4 2 3) = 4312. Applying your notation from left to right:

• (2 4 3) applied to 1234 makes 1342
• (1 2 4 3) applied to 1342 makes 3421

Where as, following my convention, the same as the convention of the author,

• 1 goes to 2 goes to 4
• 2 goes to 4 goes to 3
• 3 goes to 1 stays at 1
• 4 goes to 3 goes to 2

Which gives 4312 which equals (1 4 2 3)

(And, annoyingly, this example gives 4312 when applying your convention from right to left this time. I can totally see how you might assume your notation is used if you're just skimming examples. Again, the author explicitly states, "Remember that the product in $S_{n}$ is composition of functions, and so the right-hand permutation is performed first.")

Finally, my third point. Your notation does not lend itself to comprehension of permutations.

Take, for example, the permutation (1 3). What does it mean to apply this permutation to an abstract ordered set? In my notation, this is obvious. It means we swap the first and third objects. But in your notation, there is no obvious answer. Your notation would only have this permutation make sense when applied to another permutation. More importantly, it is dependent on what permutation it's being applied to. For example, under your notation,

• (1 3) applied to 123 results in 321, so in this case (1 3) denotes the permutation which swaps the first and third members of the given input permutation.
• (1 3) applied to 213 results in 231, so in this case (1 3) denotes the permutation which swaps the second and third members of the given input permutation.

Under this notation scheme, we can't really even say that (1 3) is "a permutation".

We may say that permutations are orderings of sets but, more importantly, they're also functions. This is incredibly important for abstract algebra and group theory. The arrangements "ACB" and "BCA" may each map to permutations of the set A, B, and C but they are not, in themselves, permutations. The permutations are the functions which rearrange A, B, and C from some initial arrangement into another arrangement. That's why we can compose permutations - they are functions on arrangements. What would it even mean to "compose" arrangements? That's nonsense.

So, given an initial arrangement of "ABC", the only permutation which generates "ACB" is 132 and the only permutation which generates "BCA" is 231. But, given an initial arrangement of "BCA", the permutation 132 generates "BAC" and the permutation 231 generates "CAB". But these are still the same permutations. They are independent of their inputs. We can still compose 132 with 231 and get 213 completely independent of the set on which its operating.

That's also why (1 3) must be applied to the first and third positions, never the elements equal to 1 and 3, if it is to represent a permutation. And that's also why I said that your notation hides the underlying nature of permutations. — Preceding unsigned comment added by Kirstein314 (talk • contribs)

Thanks for your response. I think it may help at the beginning if I point out that you're speaking to me as if you understand this better than I do, but almost certainly the reverse is true: I am a professor of mathematics, my research area is algebraic combinatorics, and I have had to deal with the annoying problem of choosing compatible conventions for symmetric group actions many times in my career.

You have written that the result of applying the permutation (1 2 3) to 123 is 312. This is one of two possible conventions, in which the action of a permutation on an ordered set is by rearranging elements in certain positions. This is inconsistent with the convention I've described, in which applying (1 2 3) gives 231. In this other convention, the permutation is a function (specifically a bijection) on the elements of the set, and it is applied to the values that appear, entry by entry. The distinction between these two actions is sometimes called the difference between the "passive" and "active" representations of permutations. Each convention allows for an internally consistent view of the world. The confusion arises because when we represent permutations in one-line notation, there is a canonical ordering on both the positions and the values, identified with the ordered set 1 < 2 < ... < n, and so it is unclear (just from writing down a string of numbers, or a cycle notation) which convention is being chosen, and calculations that are valid in one notation are not valid in the other. (This is related to, but not the same as, the failure of commutativity in the symmetric group.)

Anyhow it is indeed true that when one asks how a permutation acts on an ordered set, we usually mean "acts (by permuting according to position)" -- because saying "an ordered set" is to choose an identification of the positions with {1, 2, ..., n}. This isn't any better or worse than choosing an identification of the values with {1, 2, ..., n} and associating the permutation (1 2 3) with the function f such that f(A) = B, f(B) = C, and f(C) = A. (Relatedly, the answer to your question "how does one compose arrangements?" is that in this convention (that of one-line notation), the arrangement represents a function on the set of values that appear, and one composes them as functions.) Really the only error in the discussion above is the assertion that it is only allowable to consider one of the two options; particularly because, in the example, the ordered set is not at all arbitrary.

Ok none of this answers the question "what should be done?" Right now, the section of the article in question has a perfectly correct and consistent exposition on this point -- but it forces the reader to adopt one of two incompatible conventions. I would like to tentatively suggest one resolution, which is replacing the example permutation with an involution (so that the two conventions would agree). The disadvantage is that we wouldn't have the example of splitting a longer cycle into shorter cycles then. --JBL (talk) 01:35, 8 January 2022 (UTC)

"I am a professor of mathematics" - And, I'm suddenly a lot less confident that I'm right. So I've probably been miss-understanding your notation then. I'll try harder to grok it. Kirstein314 (talk) 15:07, 11 January 2022 (UTC)

As towards replacing the example permutation with an involution, I worry that might just be hiding the problem, more than fixing it. Is that notation documented on wikipedia? That seems like the ideal solution to me, though I might just be bikeshedding at this point. If this notation is what's confusing the issue, I propose gifs. It's hard to make those confusing. I've coded up the following examples. --Kirstein314 (talk) 17:31, 11 January 2022 (UTC)

• 
  The full permutation in one go.
• 
  The permutation broken down into cycles.
• 
  The permutation broken down into transpositions.

A few comments:

• It occurs to me that there is a very simple way to describe the differences in notations (that is only implicit in what I said above): if one notation represents a permutation as the word $w(1)w(2)\cdots w(n)$, the other notation represents it as $w^{-1}(1)w^{-1}(2)\cdots w^{-1}(n)$. In my opinion, the convention I'm following is the one outlined at one-line notation.
• Those figures are amazing! They also nicely avoid the issue of choosing a notation, as you say. I definitely think them (or something like them) would be a great addition to the article. But for vision-impaired readers, it's important to also have a text-based explanation.
• About hiding the problem, yes, I agree, choosing an involution hides the problem -- because fundamentally the problem can't be resolved (the two notations are equally valid & expressive, and both are widely used). Also the problem is irrelevant to the question at hand here (about parity).
• Another possibility (separate from choosing an involution) would be to remove the explicit formula as a product, because the ambiguity of notation to represent a permutation can be masked with a second ambiguity about what side to multiply the transpositions on. For example, the two different notations are compatible with the statement that the given permutation is a product of the transpositions (2 4), (1 3), and (1 5) -- in one notation you multiply those in the order they're written, whereas in the other notation you reverse the left-right order. This would also be compatible with including your beautiful gifs.
• If we do the thing in the last bullet, we could have a full discussion of the notational ambiguity in a footnote -- that would allow addressing it without overly distracting from the point of the example.

Thoughts? --JBL (talk) 18:48, 15 January 2022 (UTC)

Proof 3

Due to a technical problem using the modulus symbol | within a hidden section, most of proof 3 is invisible. This needs to be fixed. TWM03 (talk) 16:36, 31 May 2022 (UTC)

For now I have removed the modulus signs as they don't significantly change the statement but anyone who knows how to add them back in should. TWM03 (talk) 16:41, 31 May 2022 (UTC)

@TWM03: Thanks for pointing it out, I fixed it by converting to LaTeX. JBL (talk) 17:27, 31 May 2022 (UTC)

|Odd|=|Even|

I can't find a proof in the text that the number of odd permutations equals the number of even permutations for a given n.

Is there one, or should I supply one? Darcourse (talk) 06:49, 23 June 2024 (UTC)

A given $n>1$. Of course you should not add your own proof, per WP:OR. Luckily, there is a proof in the section titled "Properties", appropriately sourced. --JBL (talk) 23:39, 23 June 2024 (UTC)