# Linear algebra (Osnabrück 2024-2025)/Part II/Lecture 46

An equivalence relation $\sim$ on a set $M$ defines the quotient set $M/\sim$ and the canonical projection $M\rightarrow M/\sim$. If there are further structures on $M$, and if the equivalence relation respects this, then it is often possible to define on $M/\sim$ the same structure. As the main example for this process, we consider those equivalence relations on a group that are defined by a subgroup.
    Cosets

## Definition

Let $G$ be a group, and let $H\subseteq G$ be a subgroup. We set $x\sim _{H}y$ (and say that $x$ and $y$ are equivalent) if
$x^{-1}y\in H$
This is indeed an equivalence relation: From $x^{-1}x=e_{G}\in H$ we get that this relation is reflexive. From $x^{-1}y\in H$ we get immediately $y^{-1}x=(x^{-1}y)^{-1}\in H$, and from $x^{-1}y\in H$ and $y^{-1}z\in H$ we get $x^{-1}z\in H$.
Two group elements $x$ and $y$ are equivalent if and only if there exists an element $h\in H$ of the subgroup with $y=xh$. In accordance with example *****, we can interpret this situation in the sense that the subgroup $H$ provides a set of possible moves, and two elements are equivalent if and only if they can be moved to each other by a movement from $H$.

## Example

In an (additively written) commutative group like $\mathbb {Z}$ or a vector space $V$, and of a given subgroup $H$, the equivalence relation $x\sim _{H}y$ means $y-x\in H$, that is, there exists a $h\in H$ such that
    $y=x+h\,.$
The equivalence classes are of the form $x+H={\left\{x+h\mid h\in H\right\}}$. In case $H=\mathbb {Z} d\subseteq \mathbb {Z}$ with a fixed $d$, the equivalence classes have the form
    $H=\mathbb {Z} d,\,1+H=\{\ldots ,1-d,1,1+d,1+2d,\ldots \},\,2+H=\{\ldots ,2-d,2,2+d,2+2d,\ldots \},\ldots .$
These classes encompass those integer numbers that have, upon division by $d$, the remainder $0$, or $1$, or $2$, etc. They form a partition of $\mathbb {Z}$.
If $H=U\subseteq V$ is a linear subspace, then the equivalence classes have the form $v+U={\left\{v+u\mid u\in U\right\}}$ for a vector $v\in V$. This is ther affine space with starting point $v$ and the translating space $U$ (in the sense of definition). The equivalence classes form a family of affine subspaces parallel to each other.

## Definition

Let $G$ be a group, and let $H\subseteq G$ be a subgroup. For every $x\in G$, the subset
    $xH={\left\{xh\mid h\in H\right\}}\,$
is called the left coset of $x$ in $G$ with respect to $H$. Every subset of this form is called a left coset. Accordingly, a set of the form
    $Hx={\left\{hx\mid h\in H\right\}}\,$
is called the right coset
$x$
The equivalence classes to the equivalence relation defined above are, because of
    ${\begin{aligned}{x}&={\left\{y\in G\mid x\sim y\right\}}\\&={\left\{y\in G\mid x^{-1}y\in H\right\}}\\&={\left\{y\in G\mid {\text{there exists }}h\in H{\text{ with }}x^{-1}y=h\right\}}\\&={\left\{y\in G\mid {\text{there exists }}h\in H{\text{ with }}y=xh\right\}}\\&=xH,\end{aligned}}$
the left cosets. The coset to the neutral element is the subgroup $H$ itself. Therefore, the left cosets form a disjoint decomposition (a partition) of $G$. This holds for the right cosets as well. In the commutative case, one does not have to distinguish between left cosets and right cosets.

## Lemma

Let $G$ be a group, and let $H\subseteq G$ be a subgroup. Let $x,y\in G$ be elements. Then the following statements are equivalent.
* $x\in yH$.
* $y\in xH$.
* $y^{-1}x\in H$.
* $x^{-1}y\in H$.
* $xH\cap yH\neq \emptyset$.
* $x\sim _{H}y$.
* $xH=yH$.

### Proof

The equivalence between $(1)$ and $(3)$ (and between $(2)$ and $(4)$) follows by multiplication with $y^{-1}$ and with $y$. The equivalence between $(3)$ and $(4)$ follows by going to the inverse elements. From $(1)$ we get $(5)$ because of $1\in H$. If $(5)$ holds, then this means that $xh_{1}=yh_{2}$ holds with certain $h_{1},h_{2}\in H$. Therefore, $x=yh_{2}h_{1}^{-1}$, and $(1)$ is satisfied. (4) and (6) are equivalent due to the definition. Since the left cosets are the equivalence classes, the equivalence between (5) and (7) follows.
$\Box$
    Lagrange's theorem

## Definition

For a finite group $G$, its cardinality is called the group order, written as
    $\operatorname {ord} \,(G)={\#\left(G\right)}\,.$
With this concept, we can say that the order of a subgroup divides the order of the group.

## Lemma

Let $G$ be a finite group. Then every element $g\in G$ has finite order. The powers
    $g^{0}=e_{G},\,g^{1}=g,\,g^{2},\ldots ,g^{\operatorname {ord} \,(g)-1}$

### Proof

$\Box$

## Theorem

Let $G$ be a finite group, and let $H\subseteq G$ denote a
subgroup
$G$
${\#\left(H\right)}$
${\#\left(G\right)}$

### Proof

We consider the left cosets $gH:={\left\{gh\mid h\in H\right\}}$ for all $g\in G$. The mapping
    $H\longrightarrow gH,h\longmapsto gh,$
is a bijection between $H$ and $gH$, so that all cosets have the same number of elements (namely ${\#\left(H\right)}$). The cosets form (as they are the equivalence classes) a partition of $G$. Hence, ${\#\left(G\right)}$ is a multiple of ${\#\left(H\right)}$.
$\Box$

## Corollary

Let $G$ be a finite group, and let $g\in G$ denote an element. Then the order of $g$ divides the

### Proof

Let $H$ be the subgroup generated by $g$. Due to Fact *****, we have
    $\operatorname {ord} \,(g)=\operatorname {ord} \,(H)\,.$
Therefore, due to Fact *****, this number divides the group order of $G$.
$\Box$

## Definition

For a subgroup $H\subseteq G$, the cardinality of the (left- or right--)cosets is called the index of $H$ in $G$, denoted as
    $\operatorname {ind} _{G}H.$
In the preceding definition, the number is in general to be understood as the cardinality of a set. However, the index is mainly used if it is finite, that is, if there are only finitely many cosets. This is, for finite $G$, always the case but can also hold for infinite $G$, as already the example $\mathbb {Z} n\subseteq \mathbb {Z}$, $n\geq 1$, shows. If $G$ is a finite group, and $H\subseteq G$ is a subgroup, then Lagrange's theorem yields the simple index formula
    ${\#\left(G\right)}={\#\left(H\right)}\cdot \operatorname {ind} _{G}H\,.$
Even if $G$ is not finite, it is still true that the different equivalence classes are "similar“ to each other, as there is always a natural bijective mapping
    $H\longrightarrow gH,h\longmapsto gh.$
    Normal subgroup

## Definition

Let $G$ be a group, and let $H\subseteq G$ denote a subgroup. $H$ is called a normal subgroup if
    $xH=Hx\,$
holds for all $x\in G$, that is, if every left coset
$x$
$x$
For a normal subgroup, it is not necessary to distinguish between left cosets and right cosets; we just talk about cosets. Instead of $xH$ or $Hx$, we write usually $[x]$. The equality $xH=Hx$ does not mean that $xh=hx$ for all $h\in H$; it only means that for every $h\in H$, there exists a ${\tilde {h}}\in H$ fulfilling $xh={\tilde {h}}x$.

## Lemma

Let $G$ be a group, and let $H\subseteq G$ be a subgroup. Then the following statements are equivalent.
* $H$ is a normal subgroup of $G$.
* We have $xhx^{-1}\in H$ for all $x\in G$ and $h\in H$.
* $H$ is invariant under every inner automorphism of $G$.

### Proof

(1) means for given $h\in H$ that we can write $xh={\tilde {h}}x$ with some ${\tilde {h}}\in H$. Multiplication by $x^{-1}$ from the right yields $xhx^{-1}={\tilde {h}}\in H$; therefore, $(2)$ holds. Reading this argument backwards gives the implication $(2)\Rightarrow (1)$. Moreover, $(2)$ is an explicit reformulation of $(3)$.
$\Box$

## Example

We consider the permutation group $G=S_{3}$ for a set with three elements, that is, $S_{3}$ consists of all bijective mappings of the set $\{1,2,3\}$ to itself. The trivial group $\{\operatorname {id} \}$ and the whole group are normal subgroups. The subset $H=\{\operatorname {id} \,,\varphi \}$, where $\varphi$ is the element that swops $1$ and $2$ and fixes $3$, is a subgroup. However, it is not a normal subgroup. To show this, let $\psi$ denote the bijection that fixes $1$ and swops $2$ and $3$. The inverse of $\psi$ is $\psi$ itself. The conjugation $\psi \varphi \psi ^{-1}=\psi \varphi \psi$ is the mapping that sends $1$ to $3$, $2$ to $2$, and $3$ to $1$. This bijection does not belong to $H$.

## Lemma

Let $G$ and $H$ be groups, and let
    $\varphi \colon G\longrightarrow H$
be a group homomorphism. Then the kernel $\operatorname {kern} \varphi$ is a normal subgroup
$G$

### Proof

By Fact *****, we know that the kernel is a subgroup. We use Fact *****. Hence, let $x\in G$ be arbitrary, and $h\in \operatorname {kern} \varphi$. Then
    $\varphi {\left(xhx^{-1}\right)}=\varphi (x)\varphi (h)\varphi {\left(x^{-1}\right)}=\varphi (x)e_{H}\varphi {\left(x^{-1}\right)}=\varphi (x)\varphi (x)^{-1}=e_{H}\,,$
therefore, $xhx^{-1}$ belongs to the kernel.
$\Box$
    Residue class formation
We show now that every normal subgroup can be realized as the kernel of a suitable surjective group homomorphism. Instead of $G/\sim _{H}$, we just write $G/H$.

## Theorem

Let $G$ be a group, and let $H\subseteq G$ be a normal subgroup. Let $G/H$ be the set of all cosets (the quotient set), and let
    $q\colon G\longrightarrow G/H,g\longmapsto [g],$
denote the canonical projection. Then there exists a uniquely determined group structure on $G/H$ such that $q$ is a

### Proof

Since the canonical projection shall be a group homomorphism, the operation must fulfill
    $[x][y]=[xy]\,.$
We have to show that this rule gives a well-defined operation on $G/H$, that is, is independent of the choice of representatives. Hence, we have to show for $[x]=[x']$ and $[y]=[y']$ that $[xy]=[x'y']$ holds. Due to the condition, we can write $x'=xh$ and $hy'={\tilde {h}}y=yh'$ with $h,{\tilde {h}},h'\in H$. Therefore,
    $x'y'=(xh)y'=x(hy')=x(yh')=xyh'\,.$
This means $[xy]=[x'y']$. From this, the group property, the homomorphism property of the projection and the uniqueness follows.
$\Box$

## Definition

Let $G$ be a group, and let $H\subseteq G$ be a normal subgroup. The quotient set
    $G/H,$
endowed with the (according to Fact *****) uniquely determined group structure, is called the factor group of $G$ modulo $H$. The elements $[g]\in G/H$ are called residue classes. For a residue class $[g]$, every element $g'\in G$ with $[g']=[g]$
$[g]$

## Example

The subgroups of the integers are of the form $\mathbb {Z} n$ with $n\geq 0$, due to Fact *****. The factor group are denoted by
    $\mathbb {Z} /(n)$
("$\mathbb {Z}$ modulo $n$“). For $n=0$, this is just $\mathbb {Z}$ itself; for $n=1$, this is the trivial group. In general, the equivalence relation on $\mathbb {Z}$ defined by the subgroup $\mathbb {Z} n$ is given in the way that $a$ and $b$ are equivalent if and only if their difference $a-b$ belongs to $\mathbb {Z} n$, that is, if it is a multiple of $n$. Therefore, ($n\geq 1$), every integer number is equivalent to exactly one of the $n$ numbers
    $0,1,2,\ldots ,n-1$
(or, as we also say, congruent modulo $n$), namely to the remainder upon division through $n$. These remainders form a system of representatives for the factor group, and contains $n$ elements. The fact that the quotient mapping
    $\mathbb {Z} \longrightarrow \mathbb {Z} /(n),a\longmapsto [a]=a\!\!\!\mod n,$
is a homomorphism might be expressed by saying that the remainder of a sum of two integers depends only on their remainders, not on the numbers themselves. As an image of the cyclic group $\mathbb {Z}$, the group $\mathbb {Z} /(n)$ is also cyclic; $1$ (but also $-1$) is always a generator.