Graphics Reference
In-Depth Information
B.3.1. Lemma.
Every permutation s in S
n
, n ≥ 2, can be written as a product of
transpositions, that is,
stt
=
◊◊◊
12
k
,
t
where t
i
is a transposition.
Proof.
We use induction on n. The lemma is clearly true if n = 2. Note that the iden-
tity map is the composition t
t for any transposition t. Assume that the lemma is true
for n - 1, n ≥ 3, and let s be a permutation in S
n
.
Case 1.
s(n) = n.
In this case, s can be thought of as belonging to S
n-1
. The inductive hypothesis
implies that s is a product of transpositions in S
n-1
. Since transpositions of
{1,2, ...,n - 1} can be thought of as transpositions of {1,2, . . . ,n}, we are done.
Case 2.
s(n) = i, i π n.
Let t
1
be the transposition in S
n
defined by t
1
(n) = i and t
1
(i) = n. Then
(
)( )
=
(
()
)
=
()
=
ts
n
ts
n
t
i
n.
1
1
1
By Case 1, t
1
s=t
2
t
3
···
t
k
, for some transpositions t
i
. It follows that
s=t
1
t
2
···
t
k
, which proves Case 2 and hence the Lemma.
The way in which a permutation can be written as a product of transpositions is
not unique, but we have
B.3.2. Theorem.
Let s be a permutation in S
n
and suppose that
stt
=
◊◊◊
t
12
s
=
hh
◊◊◊
h
t
,
12
where t
i
and h
j
are transpositions in S
n
. Then s and t are either both even or both
odd.
If f :
R
n
Æ
R
and sŒS
n
, then define f
s
:
R
n
Outline of Proof.
Æ
R
by
(
)
=
(
)
fxx
,
,...,
x
fx
,
x
,...,
x
.
(B.1)
s
12
n
s
()
1
s
()
2
s
( )
n
Now consider the function D :
R
n
Æ
R
given by
'
(
)
=
(
)
D xx
,
,...,
x
x x
-
.
12
n
j
i
ij
<
One can show that D and D
s
(as defined by equation (B.1)) satisfies the following two
properties:
