Exercise for the break
Show that one can represent every
finite permutation
by an arrow diagram without crossings.
Exercises
Compute, for the
permutation
x
{\displaystyle {}x}
1
{\displaystyle {}1}
2
{\displaystyle {}2}
3
{\displaystyle {}3}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
8
{\displaystyle {}8}
σ
(
x
)
{\displaystyle {}\sigma (x)}
2
{\displaystyle {}2}
5
{\displaystyle {}5}
7
{\displaystyle {}7}
3
{\displaystyle {}3}
1
{\displaystyle {}1}
4
{\displaystyle {}4}
8
{\displaystyle {}8}
6
{\displaystyle {}6}
the number of
inversions
and the
sign .
Compute, for the
permutation
σ
{\displaystyle {}\sigma }
given by
P
{\displaystyle {}P}
1
{\displaystyle {}1}
2
{\displaystyle {}2}
3
{\displaystyle {}3}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
8
{\displaystyle {}8}
9
{\displaystyle {}9}
10
{\displaystyle {}10}
σ
(
P
)
{\displaystyle {}\sigma (P)}
7
{\displaystyle {}7}
10
{\displaystyle {}10}
3
{\displaystyle {}3}
9
{\displaystyle {}9}
5
{\displaystyle {}5}
2
{\displaystyle {}2}
4
{\displaystyle {}4}
1
{\displaystyle {}1}
8
{\displaystyle {}8}
6
{\displaystyle {}6}
the powers
σ
2
{\displaystyle {}\sigma ^{2}}
and
σ
3
{\displaystyle {}\sigma ^{3}}
, and determine the
cycle representation
of these three permutations.
We consider the permutation
τ
∈
S
7
{\displaystyle {}\tau \in S_{7}}
,
given by the value table
x
{\displaystyle {}x}
1
{\displaystyle {}1}
2
{\displaystyle {}2}
3
{\displaystyle {}3}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
τ
(
x
)
{\displaystyle {}\tau (x)}
1
{\displaystyle {}1}
3
{\displaystyle {}3}
5
{\displaystyle {}5}
7
{\displaystyle {}7}
6
{\displaystyle {}6}
4
{\displaystyle {}4}
2
{\displaystyle {}2}
Determine the cycle representation of
τ
{\displaystyle {}\tau }
, and the range of action.
Compute
τ
3
{\displaystyle {}\tau ^{3}}
and the order of
τ
3
{\displaystyle {}\tau ^{3}}
.
Determine the inversions of
τ
{\displaystyle {}\tau }
and the
sign
of
τ
{\displaystyle {}\tau }
.
Express
τ
{\displaystyle {}\tau }
as a product of transpositions, and determine again the sign of
τ
{\displaystyle {}\tau }
We consider the two permutations given by
x
{\displaystyle {}x}
1
{\displaystyle {}1}
2
{\displaystyle {}2}
3
{\displaystyle {}3}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
8
{\displaystyle {}8}
σ
(
x
)
{\displaystyle {}\sigma (x)}
2
{\displaystyle {}2}
5
{\displaystyle {}5}
3
{\displaystyle {}3}
7
{\displaystyle {}7}
1
{\displaystyle {}1}
4
{\displaystyle {}4}
8
{\displaystyle {}8}
6
{\displaystyle {}6}
and
x
{\displaystyle {}x}
1
{\displaystyle {}1}
2
{\displaystyle {}2}
3
{\displaystyle {}3}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
8
{\displaystyle {}8}
τ
(
x
)
{\displaystyle {}\tau (x)}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
2
{\displaystyle {}2}
8
{\displaystyle {}8}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
1
{\displaystyle {}1}
3
{\displaystyle {}3}
Compute
σ
τ
{\displaystyle {}\sigma \tau }
and
τ
σ
{\displaystyle {}\tau \sigma }
. Determine the number of
inversions
and the
sign
of
τ
{\displaystyle {}\tau }
. Describe the cycle representation of
σ
{\displaystyle {}\sigma }
and of
σ
3
{\displaystyle {}\sigma ^{3}}
. What is the order of
σ
{\displaystyle {}\sigma }
?
We consider the permutation
F
{\displaystyle {}F}
on
M
=
{
1
,
2
,
…
,
8
}
{\displaystyle {}M=\{1,2,\ldots ,8\}\,}
given by
x
{\displaystyle {}x}
1
{\displaystyle {}1}
2
{\displaystyle {}2}
3
{\displaystyle {}3}
4
{\displaystyle {}4}
5
{\displaystyle {}5}
6
{\displaystyle {}6}
7
{\displaystyle {}7}
8
{\displaystyle {}8}
F
(
x
)
{\displaystyle {}F(x)}
3
{\displaystyle {}3}
5
{\displaystyle {}5}
1
{\displaystyle {}1}
7
{\displaystyle {}7}
8
{\displaystyle {}8}
2
{\displaystyle {}2}
6
{\displaystyle {}6}
4
{\displaystyle {}4}
Establish a value table for
F
2
=
F
∘
F
{\displaystyle {}F^{2}=F\circ F}
.
Establish a value table for
F
3
=
F
∘
F
∘
F
{\displaystyle {}F^{3}=F\circ F\circ F}
.
Show that all iterated compositions
F
n
{\displaystyle {}F^{n}}
are
bijective .
Determine, for every
x
∈
M
{\displaystyle {}x\in M}
,
the minimal
n
∈
N
+
{\displaystyle {}n\in \mathbb {N} _{+}}
such that
F
n
(
x
)
=
x
{\displaystyle {}F^{n}(x)=x\,}
holds.
Determine the minimal
n
∈
N
+
{\displaystyle {}n\in \mathbb {N} _{+}}
such that
F
n
(
x
)
=
x
{\displaystyle {}F^{n}(x)=x\,}
holds for all
x
∈
M
{\displaystyle {}x\in M}
.
Show that the assignment
S
n
×
{
1
,
…
,
n
+
1
}
⟶
S
n
+
1
,
(
φ
,
x
)
⟼
φ
~
,
{\displaystyle S_{n}\times \{1,\ldots ,n+1\}\longrightarrow S_{n+1},(\varphi ,x)\longmapsto {\tilde {\varphi }},}
given by
φ
~
(
k
)
=
{
φ
(
k
)
for
k
≤
n
and
φ
(
k
)
<
x
,
φ
(
k
)
+
1
for
k
≤
n
and
φ
(
k
)
≥
x
,
x
for
k
=
n
+
1
,
{\displaystyle {}{\tilde {\varphi }}(k)={\begin{cases}\varphi (k){\text{ for }}k\leq n{\text{ and }}\varphi (k)<x\,,\\\varphi (k)+1{\text{ for }}k\leq n{\text{ and }}\varphi (k)\geq x\,,\\x{\text{ for }}k=n+1\,,\end{cases}}\,}
is well-defined and bijective.
Gabi Hochster, Heinz Ngolo, Lucy Sonnenschein and Mustafa Müller want to play Secret Santa. That is, every child gets a gift from exactly one of the other
(!)
children. How many possibilities are there?
Determine the
fixed points
of the
mapping
f
:
R
⟶
R
,
x
⟼
x
2
.
{\displaystyle f\colon \mathbb {R} \longrightarrow \mathbb {R} ,x\longmapsto x^{2}.}
Let
M
{\displaystyle {}M}
denote a set, and let
F
:
M
⟶
M
{\displaystyle F\colon M\longrightarrow M}
be a
mapping .
Show that
F
{\displaystyle {}F}
has an
fixed point
if and only if the intersection of the
graph
of
F
{\displaystyle {}F}
with the
diagonal
△
=
{
(
x
,
x
)
∈
M
×
M
∣
x
∈
M
}
{\displaystyle {}\triangle ={\left\{(x,x)\in M\times M\mid x\in M\right\}}}
is not empty.
Compute the determinant of all the
3
×
3
{\displaystyle {}3\times 3}
-matrices, such that in each column and in each row, there are exactly one
1
{\displaystyle {}1}
and two
0
{\displaystyle {}0}
s.
Let
M
=
{
1
,
…
,
n
}
{\displaystyle {}M=\{1,\ldots ,n\}}
and let
π
{\displaystyle {}\pi }
be a
permutation
on
M
{\displaystyle {}M}
. The corresponding permutation matrix
M
π
{\displaystyle {}M_{\pi }}
is given by
a
π
(
i
)
,
i
=
1
,
{\displaystyle {}a_{\pi (i),i}=1\,,}
all other entries being
0
{\displaystyle {}0}
. Show that
det
M
π
=
sgn
(
π
)
.
{\displaystyle {}\det M_{\pi }=\operatorname {sgn} (\pi )\,.}
a) Give an example of an
4
×
4
{\displaystyle {}4\times 4}
-permutation matrix
such that in every diagonal
(diagonal and antidiagonal, including all parallel diagonals),
there is at most one
1
{\displaystyle {}1}
.
b) Show that there is no solution for a) where
a
11
=
1
{\displaystyle {}a_{11}=1}
holds.
Let
K
{\displaystyle {}K}
a
field ,
and let
M
=
{
(
a
b
c
d
)
∣
a
,
b
,
c
,
d
∈
K
,
a
d
−
b
c
≠
0
}
{\displaystyle {}M={\left\{{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\mid a,b,c,d\in K,\,ad-bc\neq 0\right\}}\,}
the set of all invertible
2
×
2
{\displaystyle {}2\times 2}
-matrices .
a) Show that
(without referring to the determinant),
M
{\displaystyle {}M}
is, with
matrix multiplication
as operation, a
group .
b) Show that
(without referring to the determinant),
the mapping
M
⟶
K
×
,
(
a
b
c
d
)
⟼
a
d
−
b
c
,
{\displaystyle M\longrightarrow K^{\times },{\begin{pmatrix}a&b\\c&d\end{pmatrix}}\longmapsto ad-bc,}
is a
group homomorphism .
Determine with the
Leibniz-formula
the
determinant
of the matrix
(
3
4
5
9
8
7
1
2
3
)
.
{\displaystyle {\begin{pmatrix}3&4&5\\9&8&7\\1&2&3\end{pmatrix}}.}
The Christmas exercise for the whole family
Which construction principle is behind the sequence
1
,
11
,
21
,
1211
,
111221
,
312211
,
.
.
.
?
{\displaystyle 1,\,11,\,21,\,1211,\,111221,\,312211,\,...?}
(Some people claim that this exercise is very easy for primary school children, but quite hard for mathematicians.)
Hand-in-exercises
Determine the
sign
of the permutation given by the image
(the left hand represents the domain, the right hand represents the codomain).
Let
M
{\displaystyle {}M}
be a set, and let
M
=
⨄
i
∈
I
M
i
{\displaystyle {}M=\biguplus _{i\in I}M_{i}}
be a partition of
M
{\displaystyle {}M}
, that is, every
M
i
{\displaystyle {}M_{i}}
is a subset of
M
{\displaystyle {}M}
, and
M
{\displaystyle {}M}
is the disjoint union of the
M
i
{\displaystyle {}M_{i}}
. Show that the product group
∏
i
∈
I
Perm
(
M
i
)
{\displaystyle \prod _{i\in I}\operatorname {Perm} \,(M_{i})}
is a
subgroup
of
Perm
(
M
)
{\displaystyle {}\operatorname {Perm} \,(M)}
.
Show that every
even permutation
σ
∈
S
n
{\displaystyle {}\sigma \in S_{n}}
,
n
≥
3
{\displaystyle {}n\geq 3}
,
can be written as a product of cycles of length
3
{\displaystyle {}3}
.
Let
σ
{\displaystyle {}\sigma }
be a
cycle
of length
n
{\displaystyle {}n}
. Show that
σ
{\displaystyle {}\sigma }
can be written as a product of
n
−
1
{\displaystyle {}n-1}
transpositions ,
but not with a smaller number of transpositions.
Let
m
≥
n
{\displaystyle {}m\geq n}
.
How many injective mappings do exist from
{
1
,
…
,
n
}
{\displaystyle {}\{1,\ldots ,n\}}
to
{
1
,
…
,
m
}
{\displaystyle {}\{1,\ldots ,m\}}
, and how many surjective mappings do exist from
{
1
,
…
,
n
}
{\displaystyle {}\{1,\ldots ,n\}}
to
{
1
,
…
,
m
}
{\displaystyle {}\{1,\ldots ,m\}}
?
Determine with the
Leibniz-formula
the
determinant
of the matrix
(
6
3
1
6
8
2
7
5
4
)
.
{\displaystyle {\begin{pmatrix}6&3&1\\6&8&2\\7&5&4\end{pmatrix}}.}
We consider the mapping
f
:
N
⟶
N
{\displaystyle f\colon \mathbb {N} \longrightarrow \mathbb {N} }
that is described in
Exercise 18.16
(the natural numbers are given as finite sequences in the decimal system).
Is
f
{\displaystyle {}f}
increasing?
Is
f
{\displaystyle {}f}
surjective?
Is
f
{\displaystyle {}f}
injective?
Does
f
{\displaystyle {}f}
have a
fixed point ?