Linear algebra (Osnabrück 2024-2025)/Part II/Exercise sheet 45

Exercises

Exercise

Determine whether the relation defined by the relation table

	A	B	C
A		x	x
B	x	x
C	x	x	x

on the set ${}\{A,B,C\}$ is reflexive, symmetric, transitive, antisymmetric.

Exercise

Let ${}M$ be a set with ${}n$ elements. Determine the number of relations on ${}M$ that are

1. reflexive,
2. symmetric,
3. reflexive and symmetric.

Exercise

On the integer numbers ${}\mathbb {Z}$, there lives a colony of fleas. Every jump of a flea has the width five units (in both directions). How many flea population do exists? How can we simply characterize whether two fleas belong to the same population, or not?

Exercise

We consider on the white part of the depicted maze the equivalence relation that is given in such a way that two points are equivalent if it is possible to move continuously (that is, without jumps) from one point to the other point. Show that a point outside the outer circle and a point of the inner circle are equivalent to each other.

Exercise

Let ${}B$ be a sheet of paper (or a tissue). Try to visualize the following equivalence relations on ${}B$, and the corresponding identification mappings.

1. The four corners are equivalent to each other; all other points are only equivalent to themselves.
2. All boundary points are equivalent to each other; all other points are only equivalent to themselves.
3. Every point of the left-hand boundary is equivalent to its horizontally opposite point on the right-hand side; all other points are only equivalent to themselves.
4. Every point of the left-hand boundary is equivalent to its horizontally opposite point on the right-hand side, and every point of the upper boundary is equivalent to its vertically opposite point on the lower boundary; all other points are only equivalent to themselves.
5. Every point of the boundary is equivalent to its opposite point (in the sense of point reflection at the center of the sheet); all other points are only equivalent to themselves.
6. Let ${}K$ denote a circle (that is, its circumference) on the sheet. All points of the circumference are equivalent to each other; all other points are only equivalent to themselves.
7. There exist two points ${}P\neq Q$ that are equivalent to each other; all other points are only equivalent to themselves.
8. Let ${}H$ be the horizontal line in the middle of the sheet. Two points are equivalent to each other if they are symmetric upon reflection by ${}H$.

Exercise

We consider on the set of all placental mammals the following equivalence relations: "belonging to the same genus“, "belonging to the same family“, "belonging to the same species“, "belonging to the same class“, "belonging to the same order“. Which equivalence relation are a refinement of which equivalence relation? Determine, for any two equivalence relations, two animals, that are equivalent with respect to one relation but not equivalent with respect to the other. How many equivalence classes does the equivalence relation for the order have?

Exercise

Let ${}M$ be the set of all human beings, and let ${}R$ be the blood relationship on ${}M$, which we interpret generously as being transitive. How many equivalence classes are there?

Exercise

We consider the product set ${}M=\mathbb {N} \times \mathbb {N}$. We fix the jumps

$\pm (2,1)\,\,{\text{ and }}\,\,\pm (1,3),$

and say that two points ${}P=(a,b),\,Q=(c,d)\in M$ are equivalent if, starting in ${}P$, we can reach the point ${}Q$ with a sequence of these jumps (staying inside ${}M$). This is a equivalence relation. Determine the equivalence classes of this equivalence relation, and give for every equivalence class one simple representative. Describe also an algorithm that finds, for a given point ${}(a,b)\in M$, the equivalent representative.

Exercise

Let ${}M$ and ${}N$ be sets, and let ${}f\colon M\rightarrow N$ be a mapping. Let ${}\sim$ denote an equivalence relation on ${}N$. Show that via ${}x\equiv x'$ if ${}f(x)\sim f(x')$ holds, an equivalence relation on ${}M$ is defined.

Exercise

Let ${}G$ be a group. We consider the relation ${}\sim$ on ${}G$ given by

$x\sim y{\text{ if and only if }}x=y{\text{ or }}x=y^{-1}.$

Show that ${}\sim$ is an equivalence relation.

Exercise

Let ${}K$ be a field, and let ${}V$ denote a ${}K$-vector space. Show that the relation on ${}V$ given by

$v\sim w{\text{ if there exists a }}\lambda \in K,\lambda \neq 0,{\text{ such that }}v=\lambda w$

is an equivalence relation. What are the equivalence classes?

Exercise

We consider a triangle as a triple in ${}\mathbb {R} ^{2}$. Show that the congruence of triangles is an equivalence relation.

Exercise

Let ${}K$ be a field, and ${}n\in \mathbb {N}$. We consider the following relation on ${}\operatorname {Mat} _{n}(K)$.

$M\sim N{\text{ if there exists an invertible matrix }}B{\text{ such that }}M=BNB^{-1}.$

Show that ${}\sim$ is an equivalence relation.

Exercise

We consider the relation on the set of all ${}n\times n$-matrices, where the matrices ${}M$ and ${}N$ are considered to be equivalent if there exist elementary matrices ${}E_{1},\ldots ,E_{k}$ such that ${}M=E_{k}\circ \cdots \circ E_{1}\circ N$ holds. Show that this is an equivalence relation.

Exercise

Let ${}K$ be a field, and let ${}V$ denote a ${}K$-vector space, and ${}m\in \mathbb {N}$. We consider on the product set ${}V^{m}$ the following relation.

$(v_{1},\ldots ,v_{m})\sim (w_{1},\ldots ,w_{m}){\text{ if }}\langle v_{1},\ldots ,v_{m}\rangle =\langle w_{1},\ldots ,w_{m}\rangle$

Show that this is an equivalence relation. Give an bijection between the corresponding quotient set and the set of linear subspaces of ${}V$ of dimension ${}\leq m$. Moreover, show that two tuples ${}(v_{1},\ldots ,v_{m})$ and ${}(w_{1},\ldots ,w_{m})$ are equivalent in this relation if and only if there exists an invertible ${}m\times m$-matrix ${}M={\left(a_{ij}\right)}_{ij}\in \operatorname {Mat} _{m}(K)$ such that

${}v_{i}=\sum _{j=1}^{m}a_{ij}w_{j}\,$

holds for all ${}i$.

Exercise

We consider on the sets of all linear mappings ${}\varphi \colon \mathbb {C} ^{n}\rightarrow \mathbb {C} ^{n}$ the relation ${}\sim$ given by ${}\varphi \sim \psi$ if there exist bases ${}v_{1},\ldots ,v_{n}$ and ${}w_{1},\ldots ,w_{n}$ such that ${}M_{\mathfrak {v}}^{\mathfrak {v}}(\varphi )=M_{\mathfrak {w}}^{\mathfrak {w}}(\psi )$ holds. Show that this is an equivalence relation. How can we interpret the Theorem about the Jordan normal form in the context of this equivalence relation?

Exercise

We consider on ${}\mathbb {N} _{+}$ the relation ${}\sim$ given by

${}m\sim n\,$

if ${}m$ divides a power of ${}n$, and ${}n$ divides a power of ${}m$.

1. Show that ${}\sim$ is an equivalence relation.
2. Determine which of the following elements are equivalent to each other, and which not.

   $100,\,1000,\,9,\,125,\,500,\,27,\,10,\,210.$

3. Let ${}Q$ be the quotient set for this equivalence relation, and let ${}\mathbb {P}$ denote the set the of all prime numbers, and let ${}{\mathfrak {P}}\,({\mathbb {P} })$ denote its power set. Show that there exists a natural mapping

   $\varphi \colon \mathbb {N} _{+}\longrightarrow {\mathfrak {P}}\,({\mathbb {P} })$

   that yields an injective mapping

   ${\tilde {\varphi }}\colon Q\longrightarrow {\mathfrak {P}}\,({\mathbb {P} }).$

   Is ${}{\tilde {\varphi }}$ surjective?

4. How does a simple system of representatives for this equivalence relation look like?

Exercise

Let ${}M$ be the set of all twice continuously differentiable functions from ${}\mathbb {R}$ to ${}\mathbb {R}$. Define on ${}M$ a relation by

$f\sim g{\text{ if }}f(0)=g(0),\,f'(0)=g'(0){\text{ and }}f^{\prime \prime }(1)=g^{\prime \prime }(1).$

a) Show that this is an equivalence relation.

b) Find for every equivalence class of this equivalence relation a polynomial representative.

c) Show that this equivalence relation is compatible with the addition of functions.

d) Show that this equivalence relation is not compatible with the multiplication of functions.

Exercise

Let ${}I\subseteq \mathbb {R}$ be an interval. We consider the set

${}C^{1}(I,\mathbb {R} ):={\left\{f:I\rightarrow \mathbb {R} \mid f{\text{ is differentiable}}\right\}}\,.$

For ${}f,g\in C^{1}(I,\mathbb {R} )$, we define

$f\sim g,{\text{ if there exists a }}c\in \mathbb {R} {\text{ such that }}f(x)=g(x)+c{\text{ for all }}x\in I.$

Is this an equivalence relation? If so, describe the equivalence classes.

Exercise

Let ${}K$ be a field, and let

${}\operatorname {Map} \,{\left(K,K\right)}={\left\{f:K\rightarrow K\mid f{\text{ function}}\right\}}\,$

be the set of all mappings from ${}K$ to ${}K$. We consider the relation on ${}\operatorname {Map} \,{\left(K,K\right)}$ defined by ${}f\sim g$ if there exist ${}c,d\in K$ such that

${}f(x)=g(x+c)+d\,$

holds for all ${}x\in K$. Show that this is an equivalence relation.

Exercise

Let ${}K$ be a field, and let ${}K[X]$ be the polynomial ring in one variable ${}X$ over ${}K$. For a polynomial ${}P\in K[X]$ and a linear form

${}L=aX+b\,$

with ${}a\neq 0$, we denote by

$P{\frac {L}{X}}$

the polynomial that arises when ${}X$ is replaced everywhere in ${}P$ by ${}aX+b$. This process is compatible with the addition and the multiplication. We consider the relation ${}\sim$ on ${}K[X]$, given by

${}P\sim Q\,$

if there exists a linear form ${}aX+b$ with ${}a\neq 0$ such that

${}Q=P{\frac {aX+b}{X}}\,$

holds.

a) Compute

${\left(3X^{2}-4X+7\right)}{\frac {3X-5}{X}}.$

b) Show that ${}\sim$ is an equivalence relation.

c) Let ${}K=\mathbb {C}$. Show that every polynomial has a representative ${}Q$ with

${}Q(0)=0\,.$

d) Let ${}K=\mathbb {C}$. Show that every polynomial ${}\neq 0$ has a normed representative.

e) Show that the number of zeroes of a polynomial ${}P\neq 0$ does only depend on the equivalence class ${}[P]$.

Exercise

Show that the relation

$(a,b)\sim (c,d){\text{ if }}a+d=b+c,$

on ${}\mathbb {N} \times \mathbb {N}$ introduced in Example 45.19 is an equivalence relation.

Exercise

Show that the addition and the multiplication on ${}\mathbb {Z}$ introduced in Example 45.19 are well-defined.

The following exercise describes the construction of ${}\mathbb {Q}$, starting from ${}\mathbb {Z}$, with the help of equivalence classes and quotient sets.

Exercise

We consider on ${}\mathbb {Z} \times (\mathbb {Z} \setminus \{0\})$ the relation

$(a,b)\sim (c,d),\,{\text{ if }}ad=bc{\text{ ist}}.$

a) Show that ${}\sim$ is an equivalence relation.

b) Show that for every ${}(a,b)$ there exists an equivalent pair ${}(a',b')$ with ${}b'>0$.

c) Let ${}M$ be the set of all equivalence classes of this equivalence relation. We define a mapping

$\varphi \colon \mathbb {Z} \longrightarrow M,z\longmapsto [(z,1)].$

Show that ${}\varphi$ is injective.

d) Define on ${}M$ (from part c) an operation ${}+$ such that ${}M$, together with this operation and with ${}[(0,1)]$ as neutral element, is a group, and such that for the mapping ${}\varphi$ the relation

${}\varphi (z_{1}+z_{2})=\varphi (z_{1})+\varphi (z_{2})\,$

holds for all ${}z_{1},z_{2}\in \mathbb {Z}$.

Exercise

Let ${}M\times N$ be a product set. Show that the equality in the first component is an equivalence relation ${}\sim$ on ${}M\times N$. Show that every equivalence class can be identified with ${}N$, and that the quotient set ${}M\times N/\sim$ can be identified with ${}M$.

Exercise

Let ${}M_{1}$ and ${}M_{2}$ be sets, and let ${}\sim _{1}$ denote an equivalence relation on ${}M_{1}$, and ${}\sim _{2}$ an equivalence relation on ${}M_{2}$. We consider the relation ${}\sim$ on the product set ${}M_{1}\times M_{2}$ given by

$(a_{1},a_{2})\sim (b_{1},b_{2}),{\text{ if }}a_{1}\sim _{1}b_{1}{\text{ and }}a_{2}\sim _{2}b_{2}{\text{ holds}}.$

Show that ${}\sim$ is an equivalence relation.

Moreover, show that the relation on ${}M_{1}\times M_{2}$ defined by

$(a_{1},a_{2})\sim (b_{1},b_{2}),{\text{ if }}a_{1}\sim _{1}b_{1}{\text{ or }}a_{2}\sim _{2}b_{2}{\text{ holds}},$

is not an equivalence relation.

Exercise

Let ${}M$ be a set, and ${}P\subseteq {\mathfrak {P}}\,(M)$. Then ${}P$ is called a partition of ${}M$ if the following conditions are satisfied.

1. For all ${}A\in P$, we have ${}A\neq \emptyset$.
2. For ${}A,B\in P$ and ${}A\neq B$, we have ${}A\cap B=\emptyset$.
3. The elements from ${}P$ form a covering of ${}M$, that is, every element of ${}M$ belongs to at least one element of ${}P$.

Prove that the quotient set ${}M/\sim ={\left\{[x]\mid x\in M\right\}}$ to an equivalence relation ${}\sim$ is a partition of the set ${}M$.

Exercise

Let ${}M$ be a set, and let ${}P\subseteq {\mathfrak {P}}\,(M)$ denote a partition. Show that ${}P$ induces via

$x\sim y{\text{ if there exists an }}A\in P{\text{ such that }}x\in A{\text{ and }}y\in A,$

an equivalence relation on ${}M$. Compute this relation for the partition ${}\{\{1\},\{2,3,4\},\{5,6\},\{7\}\}$ of the set ${}\{1,2,3,4,5,6,7\}$.

Exercise

Let ${}M$ be a set, and let ${}(R_{i})_{i\in I}$ be a family of equivalence relations on ${}M$. Show that the intersection ${}R:=\bigcap _{i\in I}R_{i}$ defines an equivalence relation on ${}M$. Does this also hold for ${}\bigcup _{i\in I}R_{i}$?

Hand-in-exercises

Exercise (2 marks)

Determine whether the relation defined by the relation table

${}\,$	${}A$	${}B$	${}C$	${}D$
${}A$	${}\times$	${}\,$	${}\times$	${}\,$
${}B$	${}\times$	${}\times$	${}\,$	${}\,$
${}C$	${}\,$	${}\,$	${}\times$	${}\,$
${}D$	${}\,$	${}\times$	${}\,$	${}\times$

on the set ${}\{A,B,C,D\}$ is reflexive, symmetric, transitive, antisymmetric.

Exercise (2 marks)

We consider the chess pieces rook, bishop, knight, and donkey, together with their allowed moves on a ${}8\times 8$-chess board. A donkey is allowed to move a double step forwards, backwards, to the right, and to the left. Every piece defines an equivalence relation on the ${}64$ square; two squares are equivalent if one square can be reached from the other square by finitely many moves of this piece. Determine for every of these chess pieces the corresponding equivalence relation, and the equivalence classes. How does it look on a ${}3\times 3$-chess board?

Exercise (2 marks)

We consider, for any two subsets ${}A,B\subseteq \mathbb {N}$, the symmetric difference

${}A\triangle B:=(A\setminus B)\cup (B\setminus A)\,.$

We set ${}A\sim B$ ifs ${}A\triangle B$ is finite. Show that this defines an equivalence relation on ${}{\mathfrak {P}}\,(\mathbb {N} )$.

Exercise (2 marks)

Let ${}G$ be a group. We consider the relation ${}R$ on ${}G$, where ${}xRy$ means that there exists an inner automorphism ${}\kappa _{g}$ with ${}x=\kappa _{g}(y)$. Show that this relation is an equivalence relation.

The equivalence classes of this equivalence relation get a name on their own:

For a group ${}G$, we call the equivalence classes to the equivalence relation, where two elements are considered to be equivalent (or conjugated) if there exists an inner automorphism

mapping one element to the other, the conjugacy classes.

Exercise (2 marks)

Let ${}S_{3}$ be the group of bijective mappings on the set ${}\{1,2,3\}$ to itself. Determine the conjugacy classes of this group.

Exercise (3 marks)

Let ${}\operatorname {GL} _{n}\!{\left(K\right)}$ be the set of all invertible ${}n\times n$-matrices over a field ${}K$. Show that for matrices ${}M$ and ${}N$ from ${}\operatorname {GL} _{n}\!{\left(K\right)}$ that are conjugated to each other, the following properties and invariants coincide: The determinant, the eigenvalues, the dimension of the eigenspace of an eigenvalue, the diagonalizability, the trigonalizability.

Exercise (2 marks)

Let ${}M\subseteq \mathbb {R} ^{n}$ be a subset with the induced metric. Consider the relation ${}R$ on ${}M$, where ${}xRy$ means that there exists a continuous mapping

$\gamma \colon [0,1]\longrightarrow M,t\longmapsto \gamma (t),$

with ${}\gamma (0)=x$ and ${}\gamma (1)=y$, Show that this is an equivalence relation on ${}M$.

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