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 }
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}}
σ
3
{\displaystyle {}\sigma ^{3}}
cycle representation
of these three permutations.
We consider the permutation
τ
∈
S
7
{\displaystyle {}\tau \in S_{7}}
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 }
Compute
τ
3
{\displaystyle {}\tau ^{3}}
τ
3
{\displaystyle {}\tau ^{3}}
Determine the inversions of
τ
{\displaystyle {}\tau }
sign
of
τ
{\displaystyle {}\tau }
Express
τ
{\displaystyle {}\tau }
τ
{\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 }
τ
σ
{\displaystyle {}\tau \sigma }
inversions
and the
sign
of
τ
{\displaystyle {}\tau }
σ
{\displaystyle {}\sigma }
σ
3
{\displaystyle {}\sigma ^{3}}
σ
{\displaystyle {}\sigma }
We consider the permutation
F
{\displaystyle {}F}
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}}
bijective .
Determine, for every
x
∈
M
{\displaystyle {}x\in M}
n
∈
N
+
{\displaystyle {}n\in \mathbb {N} _{+}}
F
n
(
x
)
=
x
{\displaystyle {}F^{n}(x)=x\,}
holds.
Determine the minimal
n
∈
N
+
{\displaystyle {}n\in \mathbb {N} _{+}}
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}
F
:
M
⟶
M
{\displaystyle F\colon M\longrightarrow M}
be a
mapping .
Show that
F
{\displaystyle {}F}
fixed point
if and only if the intersection of the
graph
of
F
{\displaystyle {}F}
△
=
{
(
x
,
x
)
∈
M
×
M
∣
x
∈
M
}
{\displaystyle {}\triangle ={\left\{(x,x)\in M\times M\mid x\in M\right\}}}
Compute the determinant of all the
3
×
3
{\displaystyle {}3\times 3}
1
{\displaystyle {}1}
0
{\displaystyle {}0}
Let
M
=
{
1
,
…
,
n
}
{\displaystyle {}M=\{1,\ldots ,n\}}
π
{\displaystyle {}\pi }
permutation
on
M
{\displaystyle {}M}
permutation matrix
M
π
{\displaystyle {}M_{\pi }}
a
π
(
i
)
,
i
=
1
,
{\displaystyle {}a_{\pi (i),i}=1\,,}
all other entries being
0
{\displaystyle {}0}
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}
a
11
=
1
{\displaystyle {}a_{11}=1}
Let
K
{\displaystyle {}K}
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}
matrix multiplication
as operation, a
group .
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}
M
=
⨄
i
∈
I
M
i
{\displaystyle {}M=\biguplus _{i\in I}M_{i}}
M
{\displaystyle {}M}
M
i
{\displaystyle {}M_{i}}
M
{\displaystyle {}M}
M
{\displaystyle {}M}
M
i
{\displaystyle {}M_{i}}
∏
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}
3
{\displaystyle {}3}
Let
σ
{\displaystyle {}\sigma }
cycle
of length
n
{\displaystyle {}n}
σ
{\displaystyle {}\sigma }
n
−
1
{\displaystyle {}n-1}
transpositions ,
but not with a smaller number of transpositions.
Let
m
≥
n
{\displaystyle {}m\geq n}
{
1
,
…
,
n
}
{\displaystyle {}\{1,\ldots ,n\}}
{
1
,
…
,
m
}
{\displaystyle {}\{1,\ldots ,m\}}
{
1
,
…
,
n
}
{\displaystyle {}\{1,\ldots ,n\}}
{
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}
Is
f
{\displaystyle {}f}
Is
f
{\displaystyle {}f}
Does
f
{\displaystyle {}f}
fixed point ?
