Linear algebra (Osnabrück 2024-2025)/Part I/Exercise sheet 18

Exercise for the break

Exercise

Show that one can represent every finite permutation by an arrow diagram without crossings.

Exercises

Exercise

Compute, for the permutation

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$\sigma (x)$	$2$	$5$	$7$	$3$	$1$	$4$	$8$	$6$

the number of inversions and the sign.

Exercise

Compute, for the permutation $\sigma$ given by

$P$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$	$9$	$10$
$\sigma (P)$	$7$	$10$	$3$	$9$	$5$	$2$	$4$	$1$	$8$	$6$

the powers ${\sigma }^2$ and ${\sigma }^3$, and determine the cycle representation of these three permutations.

Exercise

We consider the permutation $\tau \in S_7$, given by the value table

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$
$\tau (x)$	$1$	$3$	$5$	$7$	$6$	$4$	$2$

1. Determine the cycle representation of $\tau$, and the range of action.
2. Compute ${\tau }^3$ and the order of ${\tau }^3$.
3. Determine the inversions of $\tau$ and the sign of $\tau$.
4. Express $\tau$ as a product of transpositions, and determine again the sign of $\tau$

Exercise

We consider the two permutations given by

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$\sigma (x)$	$2$	$5$	$3$	$7$	$1$	$4$	$8$	$6$

and

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$\tau (x)$	$4$	$5$	$2$	$8$	$6$	$7$	$1$	$3$

Compute $\sigma \tau$ and $\tau \sigma$. Determine the number of inversions and the sign of $\tau$. Describe the cycle representation of $\sigma$ and of ${\sigma }^3$. What is the order of $\sigma$?

Exercise

We consider the permutation $F$ on

$M=\{1,2,\dots ,8\}$

given by

$x$	$1$	$2$	$3$	$4$	$5$	$6$	$7$	$8$
$F(x)$	$3$	$5$	$1$	$7$	$8$	$2$	$6$	$4$

1. Establish a value table for $F^2=F\circ F$.
2. Establish a value table for $F^3=F\circ F\circ F$.
3. Show that all iterated compositions $F^n$ are bijective.
4. Determine, for every $x\in M$, the minimal $n\in {\mathbb{N}}_{+}$ such that

   $F^n(x)=x$

   holds.

5. Determine the minimal $n\in {\mathbb{N}}_{+}$ such that

   $F^n(x)=x$

   holds for all $x\in M$.

Exercise

Show that the assignment

$S_n\times \{1,\dots ,n+1\}⟶S_{n+1},(\phi ,x)⟼\tilde{\phi },$

given by

$\tilde{\phi }(k)=\{\begin{array}{c}\phi (k)\text{ for }k\le n\text{ and }\phi (k)<x,\\ \phi (k)+1\text{ for }k\le n\text{ and }\phi (k)\ge x,\\ x\text{ for }k=n+1,\end{array}$

is well-defined and bijective.

Exercise

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?

Exercise

Determine the fixed points of the mapping

$f:ℝ⟶ℝ,x⟼x^2.$

Exercise

Let $M$ denote a set, and let

$F:M⟶M$

be a mapping. Show that $F$ has an fixed point if and only if the intersection of the graph of $F$ with the diagonal $\mathrm{△}=\{(x,x)\in M\times M\mid x\in M\}$ is not empty.

Exercise

Compute the determinant of all the $3\times 3$-matrices, such that in each column and in each row, there are exactly one $1$ and two $0$s.

Exercise

Let $M=\{1,\dots ,n\}$ and let $\pi$ be a permutation on $M$. The corresponding permutation matrix $M_{\pi }$ is given by

$a_{\pi (i),i}=1,$

all other entries being $0$. Show that

$det{M}_{\pi }=\mathrm{sgn}(\pi ).$

Exercise

a) Give an example of an $4\times 4$-permutation matrix such that in every diagonal (diagonal and antidiagonal, including all parallel diagonals), there is at most one $1$.

b) Show that there is no solution for a) where $a_{11}=1$ holds.

Exercise

Let $K$ a field, and let

$M=\{\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)\mid a,b,c,d\in K,ad-bc\ne 0\}$

the set of all invertible $2\times 2$-matrices.

a) Show that (without referring to the determinant), $M$ is, with matrix multiplication as operation, a group.

b) Show that (without referring to the determinant), the mapping

$M⟶K^{\times },\left(\begin{array}{cc}a& b\\ c& d\end{array}\right)⟼ad-bc,$

is a group homomorphism.

Exercise

Determine with the Leibniz-formula the determinant of the matrix

$\left(\begin{array}{ccc}3& 4& 5\\ 9& 8& 7\\ 1& 2& 3\end{array}\right).$

Let $(G,e,\circ )$ be a group. A subset $H\subseteq G$ is called a subgroup of $G$, when the following conditions hold.

1. $e\in H$.
2. If $g,h\in H$, then also $g\circ h\in H$.
3. If $g\in H$, then also $g^{-1}\in H$.

Hand-in-exercises

Exercise (2 marks)

Determine the sign of the permutation given by the image (the left hand represents the domain, the right hand represents the codomain).

Exercise (2 marks)

Let $M$ be a set, and let $M=\underset{i\in I}{⨄}{M}_i$ be a partition of $M$, that is, every $M_i$ is a subset of $M$, and $M$ is the disjoint union of the $M_i$. Show that the product group

$\prod _{i\in I}\mathrm{Perm}(M_i)$

is a subgroup of $\mathrm{Perm}(M)$.

Exercise (3 marks)

Show that every even permutation $\sigma \in S_n$, $n\ge 3$, can be written as a product of cycles of length $3$.

Exercise (5 marks)

Let $\sigma$ be a cycle of length $n$. Show that $\sigma$ can be written as a product of $n-1$ transpositions, but not with a smaller number of transpositions.

Exercise (3 marks)

Let $m\ge n$. How many injective mappings do exist from $\{1,\dots ,n\}$ to $\{1,\dots ,m\}$, and how many surjective mappings do exist from $\{1,\dots ,n\}$ to $\{1,\dots ,m\}$?

Exercise (3 marks)

Determine with the Leibniz-formula the determinant of the matrix

$\left(\begin{array}{ccc}6& 3& 1\\ 6& 8& 2\\ 7& 5& 4\end{array}\right).$

<< | Linear algebra (Osnabrück 2024-2025)/Part I | >> PDF-version of this exercise sheet Lecture for this exercise sheet (PDF)