-
Notifications
You must be signed in to change notification settings - Fork 4
/
03-00-SignatureOfAPermutation.tex
61 lines (57 loc) · 1.94 KB
/
03-00-SignatureOfAPermutation.tex
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
\documentclass[12pt]{article}
\usepackage{pmmeta}
\pmcanonicalname{SignatureOfAPermutation}
\pmcreated{2013-03-22 13:29:19}
\pmmodified{2013-03-22 13:29:19}
\pmowner{rspuzio}{6075}
\pmmodifier{rspuzio}{6075}
\pmtitle{signature of a permutation}
\pmrecord{9}{34061}
\pmprivacy{1}
\pmauthor{rspuzio}{6075}
\pmtype{Definition}
\pmcomment{trigger rebuild}
\pmclassification{msc}{03-00}
\pmclassification{msc}{05A05}
\pmclassification{msc}{20B99}
\pmsynonym{sign of a permutation}{SignatureOfAPermutation}
%\pmkeywords{permutation}
\pmrelated{Transposition}
\pmdefines{inversion}
\pmdefines{signature}
\pmdefines{parity}
\pmdefines{even permutation}
\pmdefines{odd permutation}
\endmetadata
\usepackage{amssymb}
\usepackage{amsmath}
\usepackage{amsfonts}
\begin{document}
\PMlinkescapeword{proposition}
Let $X$ be a finite set, and let $G$ be the group of permutations of $X$ (see
permutation group). There exists a unique homomorphism $\chi$ from $G$ to the
multiplicative group $\{-1,1\}$ such that $\chi(t)=-1$ for any transposition
(loc. sit.) $t\in G$. The value $\chi(g)$, for any $g\in G$, is called the
\emph{signature} or \emph{sign} of the permutation $g$. If
$\chi(g)=1$, $g$ is said to be of even \emph{parity}; if
$\chi(g)=-1$, $g$ is said to be of odd parity.
\textbf{Proposition:} If $X$ is totally ordered by
a relation $<$, then for all $g\in G$,
\begin{equation}
\chi(g)=(-1)^{k(g)}
\end{equation}
where $k(g)$ is the number of pairs $(x,y)\in X\times X$ such that
$x<y$ and $g(x)>g(y)$. (Such a pair is sometimes called an \emph{inversion}
of the permutation $g$.)
\textbf{Proof:} This is clear if $g$ is the identity map $X\to X$.
If $g$ is any other permutation, then for some
\emph{consecutive} $a,b\in X$ we have $a<b$ and $g(a)>g(b)$. Let $h\in G$
be the transposition of $a$ and $b$. We have
\begin{eqnarray*}
k(g \circ h)&=&k(g)-1 \\
\chi(g \circ h)&=&-\chi(g)
\end{eqnarray*}
and the proposition follows by induction on $k(g)$.
%%%%%
%%%%%
\end{document}