Talk:Parity of a permutation/Archive 1

Archive 1

inversions and transpositions

Are inversions the same as transpositions? If so then we should write transpositions everywhere to avoid confusion. —Preceding unsigned comment added by 203.143.165.250 (talk) 06:22, 7 November 2008 (UTC)

These are related but not identical concepts. Transpositions are permutations exchanging two elements while inversions are structural features of a permutation. Maxal (talk) 16:26, 8 November 2008 (UTC)

Hi,

This might just be some stupid mistake of my own, but I think (135)(24) is not equal to (35)(13)(24) in the first example. Better would be (135)(24)=(13)(35)(24), wouldn't it?

Jacob —Preceding unsigned comment added by 145.97.206.168 (talk) 18:44, 13 September 2009 (UTC)

Proof error

The proof of the fact that the sign of the composition of two permutation is the product of the signs is wrong: we need to multiply and divide by P(x_\tau(1),...,x_\tau(n)) so that we obtain the desired product. Please someone confirm this and I wil make the change. Alberto

I think you're right. It does appear sgn(tau) isn't right. Go ahead as far as I'm concerned. - grubber 14:48, 26 October 2006 (UTC)

I am a student in a course in Abstract Algebra, and we also spotted the error, our professor agreed that the proof needs to be corrected. (Johnny Panrike, Sweden. Google for my name and you'll find my email if you wish to contact me.) Today is the 14 of April 2013. — Preceding unsigned comment added by 79.102.145.224 (talk) 13:08, 14 April 2013 (UTC)

question/concern about proof 1

Why, if we apply k adjacent swaps to a permutation sigma and get the identity, should it be the case that "N(sigma) - k" is necessarily even? As observed in the proof, some of the k swaps increase N() and some decrease N(). It seems that this assertion needs at least a sentence or two of proof.

Here's a proposed alternative.

Claim: Any finite sequence of adjacent swaps that starts at a permutation S1 and ends at permutation S2 will be even in length if S1 and S2 have the same parity, and odd in length otherwise.

Proof: Trivial induction on length of sequence. Base: length zero (perform zero swaps) is even, and S1 equals S2 so they have the same parity. Induction: Assume true for all paths of length N. For any sequence of length N+1, trim the last permutation and use the inductive hypothesis. Then note that the N+1'th permutation has opposite parity, and length of the sequence of swaps also has opposite parity.

Then, we can assert that for any permutation sigma and any sequence from it to the identity, sigma is an even iff the sequence has an even number of adjacent swaps.

Wingandaprayer (talk) 03:54, 27 April 2009 (UTC)wingandaprayer

Not only proof 1 seems to assume the "hard part" of showing that identity is always "even"... but the "*adjacent* transpositions" seem to play no role at all!!! I guess it is just lots of complications to show something very trivial: you can invert a sequence of transpositions by applying the same transpositions in reverse order, producing the identity with even transpositions.

André Caldas (talk) 17:37, 14 January 2018 (UTC)

Another short point in Proof 1

Replace σ (i, i + 1) with (i, i + 1)σ

Mungbean (talk) 11:43, 20 March 2012 (UTC)

Missing From Proof 1

I have found several versions of this proof, e.g opentopia All use nearly identical wording and symbols, but they include a critical definition missing from our proof:

_______________________________________

We define an inversion pair for σ to be a pair of indices (i,j) such that i<j and σ(i)>σ(j). Let N(σ) be the number of inversion pairs of σ. _______________________________________

Since N(σ) is otherwise undefined, this is presumably an inadvertent error, and should be restored to the proof. Since it is a word for word copy, a reference would be appropriate.

Careful examination of this proof suggests it is an abstraction of the more usual polynomial proof, i.e. the same arguments, but without the polynomial. Harder to follow. Calochortus (talk) 05:01, 6 September 2009 (UTC)

The definition of N(σ) is given in the beginning of the article. Repeating it in the proof section is redundant. Maxal (talk) 14:06, 6 September 2009 (UTC)

Well... there is no such a thing: "number of inversions in σ". So, N(σ) is quite ill-defined. André Caldas (talk) 17:41, 14 January 2018 (UTC)

Confusing Introduction

The first paragraph is confusing defining parity in terms of parity (even though the latter seems to refer to something different). I went to the MathWorld definition cited in this article and found the definition very clear and in accord with what I always understood. I suggest you lead off with it (or a similar simple and straightforward wording) and then go to the more technical definition. — Preceding unsigned comment added by Skinnerd (talk • contribs) 12:42, 16 April 2011 (UTC)

Two Fallacies

Hi all,

All three "proofs" are based on the fact that the identity is exactly even. Meanwhile, the identity could be both even and odd !

There are correct proofs, and the alternating group exists for each n.

I am afraid to write here the names of the mathematicians that have taken the parity of identity granted as even.

pls do something about this. Nicolae-boicu (talk) 02:03, 26 July 2012 (UTC)

The first proof just uses the fact that under any ordering, the identity has no inversions. David815 (talk) 01:11, 2 September 2015 (UTC)

This is not true. It uses the fact that whatever way you write the identity with (adjacent) transpositions, the number of transpositions used is always even. This missing part is the hard part of the proof. André Caldas (talk) 17:43, 14 January 2018 (UTC)

Fallacy A, adjiacent transpositions

I will try to replace in the original proof σ with a particular case of σ that is Identity.

---

Then apply the inverses of T_2', T_3', ... T_k' in the same way, "unraveling" the Identity. At the end we get the Identity permutation, whose N is zero.

---

If this were a proof, the above shoud make sense; and it does not. Why unraveling the Identity one gets the Identity whose N is zero?

Anyway, one has still to proof that zero inversions is an even number of inversions. For this, he has to produce explicit examples of adding and substracting various numbers of inversions. If not, it has not the right to apply the Natural Numbers machine.

take physics. We all have the intuition of acceleration, speed, time, distance. For example, the acceleration is meters/square second. Then, what square second stands for ? Nevermind, is physics. Here, an even number of inversions, like zero inversions, has to be proved it is an even number. The existence of the Alternating Group is too important.Nicolae-boicu (talk) 03:55, 30 July 2012 (UTC)

Fallacy B - adjacent transpositions again, and bases the existence of the altenating group on the existence of infinte sets

again, the length of 1 that has no length is assumed to be even, why ? when it could be both even and odd. Take for example, the symmetric group on 100 symbols. There are 99 adjiacent transpositions that generate the group. Then take the 99! words that one can write using these different transpositions. Nothing in the "proof" grants that we not find the identity among them, since it is not indicated how to shorten the 99 word .

The identity permutation is even and not odd. — Arthur Rubin (talk) 06:50, 26 July 2012 (UTC)

Thank you, I have retired discriminant proof 2 from my list. It bothered me that one needs a field of fractions in this proofNicolae-boicu (talk) 14:55, 26 July 2012 (UTC)

0 is a number of transpositions used to generate the identity permutation, and 0 is even. If you don't like that argument, use id = TT where T is any of the 99 permutations. (Finally, 99! is completely irrelevant. regardless of reduction rules, (12)(23)(12) is a perfectly allowable representation of (13).) — Arthur Rubin (talk) 15:03, 26 July 2012 (UTC)

There are plenty of words that could stand for the identity. If t and s are adjacent, e.g. 1 = tt = tsst = tsstss = tststs. But this remark does not logicaly grant that one day someone will not find an odd word for the identity. This kind of situation occurs in the Fifteen puzzle. If one can cycle every three pieces, this not imply a simple transposition is not reachable. I do not see here some limitation axiom like the 9th on of Peano axioms that would affirm that the only acceptable words are those constructed by the three rules.

On the other hand, if I take a closer look to the definition by presentation, I find that the symmetric group is no more what it was, but a factor of the free group. This way, one should notice first the "even subgroup" of the free group then to extract by some isomorphism theorems the finite alternating group. Nicolae-boicu (talk) 16:12, 26 July 2012 (UTC)

Proof 1 - signature

Uses the signature or the ratio between the discriminant of σ and the discriminant of the identity.

Proof 2 - sketch, variant for Jacobson, Rotman

Jacobson

If (i₁i₂...i_r)(j₁j₂...j_s)...(l₁l₂...l_s) is the unique decomposition in cycles of σ, the discriminant is defined as :

N(σ) = (r-1) + (s-1)+...+ (u-1)

When a ransposition (ab) is applied to a permutation, one of the two situations below occurs :

Either a and b are in different cycles and

(ac₁c₂...c_kbd₁d₂...d_k)(ab) = (ac₁c₂...c_k)(bd₁d₂...d_k)

Or a and b are in the same cycle and

(ac₁c₂...c_k)(bd₁d₂...d_k)(ab) = (ac₁c₂...c_kbd₁d₂...d_k)(ab)

In both cases, N(σ(ab)) = N(σ)± 1

By applying m transpositions to the unique cycle decomposition, one gets the identity (whose N is zero) only if m is even. Hence a permutation that has one even length decomposition cannot have other odd ones. Nicolae-boicu (talk) 16:09, 31 July 2012 (UTC)

drawings, induction

whe the transposition `hits` two cycles the C-parity switches

whe the transposition `hits` one cycle the C-parity switches

— Preceding unsigned comment added by Nicolae-boicu (talk • contribs) 02:37, 27 July 2012 (UTC)

Based on fact that a permutation has a unique decomposition in cycles, define the C-parity as the parity of the sum of the lengths of cycle plus the number of cycles.

Thus the identity is clearly even and a transposition is clearly odd. There is no way for a permutation to have both even and odd parities.

Now try to define L-parity, a new parity based on the length of a decomposition in traspositions.

Suppose by reductio ad absurdum that someone has found two decompositions of a permutation, one having even length and the other having an odd length.

Say that the decomposition that has the same L-parity with the C-parity is a normal one, and the the other is an ab-normal one.

Take the shortest ab-normal (or one of them) decomposition for all permutations, let be s = t.t₁.t₂...t_n of lenght n+1.

Take the permutation ts. When hitting the permutation s with the transposition t, the structure of cycles modifies. Either t hits one cycle, spliting it into two, or hits two cycles, reuniting them and also modifying the sum of lengtsh. Overall, the C-parity switches.

This means that we have found a shorter ab-normal representation t₁.t₂...t_n for some permuation; this contradicts the hypothesis.

In conclusion, since there are not shortest ab-normal decompositions, also there are no ab-normal decompositions, and the L-parity follows exactly the C-parity. Nicolae-boicu (talk) 16:12, 31 July 2012 (UTC)

Proof 3 discriminant

The discriminant is the Vandermonde Polynomial.

The signature (the ratio of two discriminants) was not yet introduced.

• William Burnside, 1911, page 9

• Marshall Hall (mathematician), 1959, p 59 we may verify directly

• Michael Aschbacher 1986, p 55

• Bartel Leendert van der Waerden 1991, Algebra p 20

Proof 4 - vandermonde determinant

seems to be the shortest,

• Robert Daniel Carmichael 1937 p 9, the discriminant is written as a vandermond determinant. A transposition of entries swap the value of the determinant. "But a given permutation, however expressed, must have always one and the same effect on D"

afterproof, Parity is defined as the parity of decomposition ; Identity is even since Identity = t.t

0-free mathematics

by the way fellows, did you ever thought at a zero-free mathematics ? as a Wiki project ?

The fallacy in the proof 1 :

0 is a number that make sense not by denoting an empty quantity, but in the context of adding and substracting other numbers. In the case of adding and substracting inversions, the sum and the difference of different amounts of inversions was not defined. Without this context, the use of zero is an ab-use

The bright solution in proof 2

Using the discriminant

$P(x_{1},\ldots ,x_{n})=\prod _{i<j}(x_{i}-x_{j})\;$

the ab-use of zero is avoided. The explicit inversion counter takes into account both inversions and non-inversions. Zero inversions is replaced by n.(n-1)/2 noninversions. Nicolae-boicu (talk) 13:35, 29 July 2012 (UTC)

Latest edit

Nicolae-boicu, I can't make any sense of this:

... Here the amount of zero inversions N(σ)= 0 has a meaning as the presence of the other n(n+1)/2 non-inversions of σ.

Doesn't N(σ)= 0 simply mean there are no inversions?
What are non-inversions?
Please make this comprehensible, or explain what you're trying to say so that someone who's more fluent in English can rephrase it. As it stands I will revert. - Virginia-American (talk) 15:47, 29 July 2012 (UTC)

hello, thanks for your comment. I will not insist my change. The simple mention on the talk page is good enough.

I have remarked ab-use of 0 of the proof 1 in a period when I hardly work to de-conceptualise the 1 of a group and the O of a vectorial space.

Even usualy someone who see an empty box has the reflex to say : there are O objects there, this is because he can add and take objects from it, and there are clear addition and substaction aritmetical rules.

In this case, there is no definition for the addition and substraction of inversions. If you add n inversions to k inversions, you will not obtain n+k inversions, but a possible number between n-k and n+k. Hence the expresion "zero inversions" has no sense, and also any proof based on it.

Overall it is not a huge mistake, since the existence of the alterating group is proved in at least two corect ways.

(It is quite probable that the very first author of the proof 2 to have remarked, once upon a time, the weakness of the proof 1).

My personal opinion is that such fundamental articles as this one, on the existence of the alternating group, should avoid "elegancy". Moreover, elegancy, in this case, covers a logical fallacy.

There is nothing to rephrase for me. I put enough information there to underline the ab-use of zero.Nicolae-boicu (talk) 17:24, 29 July 2012 (UTC)

OK, here are some guys whom were tough at remarking fallacies :

0 (number)#Greeks_and_Romans

Records show that the ancient Greeks seemed unsure about the status of zero as a number. They asked themselves, "How can nothing be something?",

The solution is that zero does not stands for nothing, but stands for nothing in a clear addition and substraction context. By writing the explicit discriminant in proof 2, there is no need to define the addition and substraction of inversions, and then the zero. For example, Burnside uses this discriminant.Nicolae-boicu (talk) 18:01, 29 July 2012 (UTC)

hi again, I have verified the references. The only proofs are 2 and 4. Best regards, Nicolae-boicu (talk) 19:09, 29 July 2012 (UTC)

and again, more explicit. In actual math, zero is an existing pair of two existing things [n,n]. In the proof A, zero inversions should stand for the n(n-1)/2 existing non-inversions (that were not defined, as you remarked), after the arithmetic of non-inversions was established. Instead of doing this, reference authors ground the existence of the alternating groups on more solid things, like the vandermond determinant. In the case for some n the alternating group would not exist, this will bring down also vandermond determinant and a huge amount of math with it. — Preceding unsigned comment added by Nicolae-boicu (talk

and again, I have added the Jacobson's proof, that has a zero. The Jacobson's zero has an algebraical meaning and does not stands for the lack of inversions, or the lack of somthing elss. By having a meaning, the Jacobson's discriminant is easy to modify, for example take (r+1)+(s+1)....+(u+1) that is never zero, but even and it works fine.

OK, I give up

the segment [0..n(n-1)/2] with < is more fundamental then (N, <) that is more fundamental than (N, <, +) It is more important to count inversions than applying the advanced algebra of integers or Vandermond polynomials when proving the existence of the Alternating Group; even in the conditions of no other refereces than tradition. — Preceding unsigned comment added by Nicolae-boicu (talk • contribs) 18:17, 1 August 2012 (UTC)

@Arthur > Important ? Just imagine some extraterrestrial brothers not having the concept of "linear order", and reading the article; or not liking too much "linear orders". Just to be polite, I would try to minimize the use of "linear orders".66.130.132.143 (talk) 20:05, 4 August 2012 (UTC)

(1 3 5) = ?

After I reverted an IP edit [1], another similar “correction” [2] was found in the history. I am not familiar with notational convention in this theory, particularly about the ordering of composition when it is mapped to algebraic left/right multiplication, but IMHO a half-year ago another IP editor introduced a mistake. Why wiki mathematicians show so weak zeal about fighting “corrections”? Incnis Mrsi (talk) 05:15, 20 May 2013 (UTC)

Because the article is doomed. It started with some proofs based on the even parity of zero. Any facts about zero, like 0!=1 are conventional and should be used only after thorough and exhaustive verifications.

Meanwhile, the reference books on subject avoid systematically the use of zero, as even quantity, standing for the lack of whatever.

The Jacobson discriminant also may be easily put out of zero by taking

$n+{\text{number of disjoint cycles in the decomposition of }}\sigma$

with + instead of –

The first proofs only prove that yes, yet another time, zero acts like an even number; and nothing else.

Let us see the good part, that this talk was classified into foundation, logic, sets... Nicolae-boicu (talk) 15:34, 26 August 2014 (UTC)