Editing Parity of a permutation (section)

== Other definitions and proofs ==
The parity of a permutation of <math>n</math> points is also encoded in its [[cyclic permutation|cycle structure]].

Let ''σ'' = (''i''<sub>1</sub> ''i''<sub>2</sub> ... ''i''<sub>''r''+1</sub>)(''j''<sub>1</sub> ''j''<sub>2</sub> ... ''j''<sub>''s''+1</sub>)...(''ℓ''<sub>1</sub> ''ℓ''<sub>2</sub> ... ''ℓ''<sub>''u''+1</sub>) be the unique [[cycle notation|decomposition of ''σ'' into disjoint cycles]], which can be composed in any order because they commute. A cycle {{nowrap|(''a'' ''b'' ''c'' ... ''x'' ''y'' ''z'')}} involving {{nowrap|''k'' + 1}} points can always be obtained by composing ''k'' transpositions (2-cycles):

:<math>(a\ b\ c \dots x\ y\ z)=(a\ b)(b\ c) \dots (x\ y)(y\ z),</math>

so call ''k'' the ''size'' of the cycle, and observe that, under this definition, transpositions are cycles of size 1. From a decomposition into ''m'' disjoint cycles we can obtain a decomposition of ''σ'' into {{nowrap|''k''<sub>1</sub> + ''k''<sub>2</sub> + ... + ''k''<sub>''m''</sub>}} transpositions, where ''k''<sub>''i''</sub> is the size of the ''i''th cycle. The number {{nowrap|1=''N''(''σ'') = ''k''<sub>1</sub> + ''k''<sub>2</sub> + ... + ''k''<sub>''m''</sub>}} is called the discriminant of ''σ'', and can also be computed as

:<math>n \text{ minus the number of disjoint cycles in the decomposition of } \sigma</math>

if we take care to include the fixed points of ''σ'' as 1-cycles.

Suppose a transposition (''a'' ''b'') is applied after a permutation ''σ''. When ''a'' and ''b'' are in different cycles of ''σ'' then
:<math>(a\ b)(a\ c_1\ c_2 \dots c_r)(b\ d_1\ d_2 \dots d_s) = (a\ c_1\ c_2 \dots c_r\ b\ d_1\ d_2 \dots d_s)</math>,

and if ''a'' and ''b'' are in the same cycle of ''σ'' then

:<math>(a\ b)(a c_1 c_2 \dots c_r\ b\ d_1\ d_2 \dots d_s) = (a\ c_1\ c_2 \dots c_r)(b\ d_1\ d_2 \dots d_s)</math>.

In either case, it can be seen that {{nowrap|1=''N''((''a'' ''b'')''σ'') = ''N''(''σ'') ± 1}}, so the parity of ''N''((''a'' ''b'')''σ'') will be different from the parity of ''N''(''σ'').

If {{nowrap|1=''σ'' = ''t''<sub>1</sub>''t''<sub>2</sub> ... ''t''<sub>''r''</sub>}} is an arbitrary decomposition of a permutation ''σ'' into transpositions, by applying the ''r'' transpositions <math>t_1</math> after ''t''<sub>2</sub> after ... after ''t''<sub>''r''</sub> after the identity (whose ''N'' is zero) observe that ''N''(''σ'') and ''r'' have the same parity. By defining the parity of ''σ'' as the parity of ''N''(''σ''), a permutation that has an even length decomposition is an even permutation and a permutation that has one odd length decomposition is an odd permutation.

; Remarks:
* A careful examination of the above argument shows that {{nowrap|''r'' ≥ ''N''(''σ'')}}, and since any decomposition of ''σ'' into cycles whose sizes sum to ''r'' can be expressed as a composition of ''r'' transpositions, the number ''N''(''σ'') is the minimum possible sum of the sizes of the cycles in a decomposition of ''σ'', including the cases in which all cycles are transpositions.
* This proof does not introduce a (possibly arbitrary) order into the set of points on which ''σ'' acts.