15/02/2017

## Proof: the symmetry group of a complete graph is vertex transitive

Let $K_n$ be a complete graph and $\mbox{Sym}(K_n)$ its symmetry group. It will be shown that $K_n$ is vertex transitive, i.e. that for any two vertices $v_i\in K_n$ and $v_j\in K_n$ there exists a symmetry $a\in\mbox{Sym}(K_n)$ such that $a(v_i)=v_j$.

The proof is constructive. Given any two vertices $v_i\in K_n$ and $v_j\in K_n$, it suffices to provide a symmetry $a_{ij}:V(\Gamma)\bigcup E(\Gamma)\rightarrow V(\Gamma)\bigcup E(\Gamma)\in\mbox{Sym}(K_n)$ such that $a_{ij}(v_i)=v_j$. Although the suggested symmetry is different for every $v_i$ and $v_j$, the simpler notation $a$ is preferred in place of $a_{ij}$.

Given $v_i\in K_n$ and $v_j\in K_n$, a suitable symmetry can be constructed by swapping $v_i$ with $v_j$, by redirecting all edges with one end in $v_i$ to edges with one end in $v_j$ and vice versa, and by leaving all other vertices and edges intact.

To formalize the construction, given $v_i\in K_n$ and $v_j\in K_n$, the symmetry $a$ is set to satisfy the following seven properties:

• $a(v_i)=v_j$,
• $a(v_j)=v_i$,
• $a(v_k)=v_k$ for all vertices $v_k$ other than $v_i,~v_j$,
• $a(e_{ij})=e_{ij}$, where $e_{ij}$ denotes the edge connecting $v_i$ with $v_j$,
• $a(e_{ik})=e_{jk}$ for all $k$ other than $i,~j$, where $e_{ik}$ denotes the edge connecting $v_i$ with $v_k$ and $e_{jk}$ the edge connecting $v_j$ with $v_k$,
• $a(e_{jk})=e_{ik}$ for all $k$ other than $i,~j$, and
• $a(e_{kl})=e_{kl}$ for all $k,~l$ other than $i,~j$, where $e_{kl}$ denotes the edge connecting $v_k$ with $v_l$.

Note that all edges exist in the above construction since $K_n$ is complete, so the symmetry is well-defined.

It is easy to check that the proposed symmetry maps vertices to vertices, edges to edges, and preserves the connectivity of $\Gamma$ according to the definition of symmetry provided in this blog post. For instance, $\mbox{ends}(e_{ik})=\{v_i,v_k\}$, $a(e_{ik})=e_{jk}$, $a(v_i)=v_j$ and $a(v_k)=v_k$ yield $\mbox{ends}(a(e_{ik}))=\mbox{ends}(e_{jk})=\{v_j,v_k\}=\{a(v_i),a(v_k)\}$, which is an edge in $K_n$.

18/01/2017

## Group actions as group homomorphisms

I have found the interpretation of the definition of group action as a group homomorphism to be verbose. This blog post provides a formalistic exposition of the equivalence between a group action and its induced homomorphism.

Let $G$ be a group and $X$ a set. A group action $\phi$ of $G$ on $X$ is a function $\phi : G \times X \rightarrow X$ that satisfies the properties of

• identity, i.e $(\forall x\in X)\phi(e, x)=x$, where $e$ is the identity element of $G$,
• and compatibility, i.e. $(\forall g, s\in G)(\forall x\in X)\phi(gs, x)=\phi(g, \phi(s, x))$.

For convenience, the shortands $ex=x$ and $(gs)x=g(sx)$ are used in place of $\phi(e, x)=x$ and $\phi(gs, x)=\phi(g, \phi(s, x))$, respectively.

Let $\mbox{Sym}(X)$ denote the symmetric group of $X$, that is the group of bijective functions from $X$ to $X$. Consider the family of bijective functions $\left\{f_g:g\in G\right\}\subseteq\mbox{Sym}(X)$, where $f_g:X\rightarrow X$ and $f_g(x)=\phi(g, x)=gx$.

It is now possible to define the function $h:G\rightarrow \mbox{Sym}(X)$ as $h(g)=f_g$. In words, $h$ maps an element $g\in G$ to the bijective function $f_g:X\rightarrow X$ defined by $f_g(x)=\phi(g, x)=gx$.

The common representation of a group action as a homomorphism relies on the following equivalence; a function $\phi : G \times X \rightarrow X$ is a group action if and only if the function $h:G\rightarrow \mbox{Sym}(X),~h(g)=f_g$, with $f_g(x)=\phi(g, x)=gx$, is a group homomorphism. The main point of this blog post has been to formalize this statement. For the sake of completeness, its proof will be provided, albeit being simple.

Firstly assume that $\phi$ is a group action. It will be shown that $h$ is a homomorphism. By definition, $h(gs)=f_{gs}$. Moreover, $h(g)h(s)=f_gf_s$, where the product $f_gf_s$ denotes function composition, the operation of the symmetric group $\mbox{Sym}(X)$. Since $\phi$ is a group action, it follows that $(\forall x\in X) f_{gs}(x)=(gs)x=g(sx)=(f_gf_s)(x)$, therefore $h(gs)=h(g)h(s)$, so $h$ is a group homomorphism.

Conversely, assume that $h$ is a homomorphism. It will be shown that $\phi$ is a group action.

The identity $e\in G$ belongs to the kernel of $h$; $h(e)=h(ee)$, whence $h(e)=h(e)h(e)$, so $h(e)=\varepsilon$, with $\varepsilon(x)=x$ being the identity function in $\mbox{Sym}(X)$. Furthermore, $h(e)=f_e$, so $f_e=\varepsilon$, which means that $(\forall x\in X)ex=f_e(x)=\varepsilon(x)=x$. The property of identity is thus satisfied for $\phi$.

Since $h$ is a homomorphism, it follows that $h(gs)=h(g)h(s)$, so $f_{gs}=f_g f_s$. Finally, $(\forall x\in X)(gs)x=f_{gs}(x)=(f_gf_s)(x)=g(sx)$, hence the compatibility property of $\phi$ is also satisfied, and $\phi$ is a group action.

09/01/2017

## Proof: any element of a group of prime order generates the group

Let $G$ be a group of prime order $|G|=p$. It will be shown that for any $a\in G$ with $a\ne e$ it holds that $\langle a\rangle=G,$ where $\langle a\rangle$ is the set generated by $a$ and $e$ is the identity element of $G$.

Since the order of group $G$ is $|G|=p<\infty$, the order $\mbox{ord}(a)$ of element $a$ is also finite, i.e. $\mbox{ord}(a)=n<\infty$ for some positive integer $n$.

Note that the set $\langle a\rangle=\left\{a^0,a^1,\ldots,a^{n-1}\right\}$ generated by $a$ is a subgroup of $G$, since $\langle a\rangle$ is closed with respect to multiplication and with respect to inverses. Indeed, for any $a^i,a^j\in\langle a\rangle$, the division algorithm of integers ensures that there exist integers $q,r$ with $0\le r such that $a^i a^j = a^{i+j}=a^{nq+r}=(a^n)^q a^r=e a^r=a^r\in \langle a \rangle$. Moreover, the inverse of any $a^i\in \langle a \rangle$ is $(a^i)^{-1}=a^{n-i}\in \langle a \rangle$.

The order $|\langle a \rangle|$ of the cyclic subgroup$\langle a \rangle$ of $G$ is equal to the order of generator $a$, that is $|\langle a \rangle|=\mbox{ord}(a)=n$.

By Lagrange’s theorem, $n$ is a factor of $p$. Since $p$ is a prime, $n=1$ or $n=p$. It follows from $a\ne e$ that $n\ne 1$, so $n=p$, which means that $|\langle a \rangle|=|G|$.

$\langle a \rangle\subseteq G$ and $|\langle a \rangle|=|G|\Rightarrow\langle a \rangle=G$.

07/01/2017

## Clarification on the proof of isomorphism of finite cyclic groups

In order to show that any two cyclic groups of finite order $n$ are isomorphic to each other, it suffices to show that every cyclic group $\langle a\rangle=\left\{a^0,a^1,a^2,\ldots,a^{n-1}\right\}$ of finite order $n$ is isomorphic to the group $\mathbb{Z}_n$ of integers modulo $n$ with the operation of addition modulo $n$, where $\mathbb{Z}_n=\left\{0,1,2,\ldots,n-1\right\}$.

Towards this end, it can be shown that the function $f:\mathbb{Z}_n\rightarrow\langle a\rangle$ defined as $f(i)=a^i$ is a group isomorphism. Recalling the definition of group isomorphism, it suffices to show that $f$ is a bijective homomorphism. It is straightforward to check that $f$ is a bijective function. The fact that $f$ is a homomorphism is proven also easily using laws of exponents for groups, as follows: $f(i+j)=a^{i+j}=a^i a^j=f(i)f(j)$.

Proving the homomorphic property of $f$ as above works well if $f$ is taken to be $f:\mathbb{Z}\rightarrow\langle a\rangle,~f(i)=a^i,$ that is from the additive group of integers to the cyclic group $\langle a\rangle=\left\{\ldots,a^{-2},a^{-1},a^0,a^1,a^2,\ldots\right\}$ of infinite order generated by $a$. However, in the case of $f:\mathbb{Z}_n\rightarrow\langle a\rangle$ with $\langle a\rangle=\left\{a^0,a^1,a^2,\ldots,a^{n-1}\right\}$, there is a slight oversight; the addition implied by $f(i+j)$ is addition modulo $n$.

Let’s denote the addition modulo $n$ by $\oplus$. So, now the proof of homomorphic property takes the form $f(i\oplus j)=a^{i\oplus j}=a^i a^j=f(i)f(j)$. The identity$a^{i+j}=a^i a^j$ is not the same as$a^{i\oplus j}=a^i a^j$; the former is one of the common exponent laws for groups, while the latter is not.

What needs to be shown is that the exponents of addition and of addition modulo $n$ coincide, i.e. $a^{i+j}=a^{i\oplus j}$. The proof of this identity is simple, yet it is useful to be aware of such potential oversight.

According to the division algorithm for integers, there exist unique integers $q$ and $r$ such that $i+j = nq+r$ and $0\le r < n$. Thus, $a^{i+j}=a^{nq+r}=(a^n)^q a^r$. Since the cyclic group $\langle a\rangle$ is of order $n$, it holds that $a^n=e$, where $e$ is the identity element of $\langle a\rangle$. So, $a^{i+j}=a^r$.

Notice that $r$ coincides with the result of the addition modulo $n$, that is $r=i\oplus j$. It follows that $a^{i+j}=a^{i\oplus j}$, which completes the proof.

04/01/2017

## Proof: every cycle expresses as a product of transpositions

To show that a cycle $(a_1~a_2~\dots~a_{r-1}~a_r)$ can be written as a product of one or more transpositions, it suffices to prove the validity of the identity $(a_1~a_2~\dots~a_{r-1}~a_r)=(a_r~a_{r-1})\dots (a_r~a_2)(a_r~a_1)$, which will be done by using mathematical induction.

Assume that the identity holds for $k$. It will be shown that it also holds for $k+1$, as in $(a_1~a_2~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_2)(a_{k+1}~a_1)$.

Start by noticing that $(a_1~a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})(a_{k+1}~a_1)$.

Due to the induction assumption, which says that a $k$-length cycle can be decomposed into a product of transpositions, $(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})$ can be written as $(a_2~a_3~\dots~a_{k-1}~a_k~a_{k+1})=(a_{k+1}~a_k)(a_{k+1}~a_{k-1})\dots (a_{k+1}~a_3)(a_{k+1}~a_2)$.

By combining the last two equations, the conclusion follows for $k+1$.

04/01/2017

## Proof: the product of disjoint cycles of a permutation is unique

Theorem 1, page 82, in the second edition of “A Book of Abstract Algebra” by Charles C. Pinter states that “Every permutation is either the identity, a single cycle, or a product of disjoint cycles”. The theorem is proved in the book. After the proof, it is stated that it is easy to see that the product of cycles is unique, except for the order of factors.

I have seen online proofs of this claim of uniqueness based on the concept of orbit. In what follows, an alternative proof is offered without relying on orbits.

Assume that there exists a permutation $\pi$ which can be written as a product of disjoint cycles in two ways. So, there are two collections, each consisting of disjoint cycles, $C=\left\{c_1,c_2,\dots,c_n\right\}$ and $S=\left\{s_1,s_2,\dots,s_m\right\}$ such that $C\ne S$ and $\pi=\prod_{i=1}^{n}c_i=\prod_{i=1}^{m}s_i$.

$C\ne S\Rightarrow C\not\subseteq S~\mbox{or}~S\not\subseteq C$. Without loss of generality, assume that $C\not\subseteq S$. Thus, $(\exists~\mbox{cycle}~c_i \in C)(\forall~\mbox{cycles}~s_k\in S) c_i\ne s_k$.

Let $a_q$ be some element in cycle $c_i$. Since $a_q\in c_i$ and the cycles in $C$ are disjoint, $a_q$ is permuted by $\pi$. Therefore, $\exists~\mbox{cycle}~s_l\in S$ such that $a_q\in s_l$.

The cycles $c_i$ and $s_l$ are disjoint from the rest of cycles in $C$ and $S$, respectively. Thus, $c_i(a_q)=s_l(a_q)=\pi(a_q)$.

Since $c_i\ne s_l$, there exists an element $a_p$ that breaks the equality arising from the successive implementation of permutation $\pi$ in each of the two cycles $c_i$ and $s_l$ starting from $a_q$. Thereby, there exists an element $a_p$ in $c_i$ and in $s_l$ with $c_i(a_p)\ne s_l(a_p)$. This is a contradiction, since the permutation $\pi$ is a function, so $a_p$ should be mapped to a unique element $\pi(a_p)$.

30/04/2014

## Proof: the Hausdorff metric is finite under the boundedness assumption

Let $(E,\rho)$ be a metric space and $\mathcal{F}$ the family of non-empty, closed and bounded subsets of $E$. For any $X,Y\in\mathcal{F}$, define

$d(X, Y)=\max\{\sup\{\rho(x,Y):x\in X\},\sup\{\rho(y,X):y\in Y\}\},$

where $\rho(x,Y)$ denotes the distance of point $x\in X$ from set $Y$ and $\rho(y,X)$ is the distance of point $y\in Y$ from set $X$, that is

$\rho(x,Y)=\inf\{\rho(x,y):y\in Y\},~\rho(y,X)=\inf\{\rho(y,x):x\in X\}.$

It can be shown that $(\mathcal{F},d)$ is a metric space, and the metric $d$ is known as the Hausdorff metric. In order to prove that $d:\mathcal{F}\times\mathcal{F}\rightarrow \mathbb{R}$ is a metric, the following three properties of (the definition of) metric need to be shown:

1. $d(X,Y)=0\Leftrightarrow X=Y,$
2. $d(X,Y)=d(Y,X),$
3. $d(X,Y)\le d(X,Z)+d(Z,Y).$

Proofs of the validity of these three properties for the Hausdorff metric are readily available in several books of topology. However, the implicit assumption of finitness of the metric tends to receive less attention. To be precise, due to the general definition of a metric, the range of the Hausdorff metric must be the real line as opposed to the extended real line.

After struggling a bit with the proof of the finitness of the Hausdorff metric, I tried the google shortcut. It turned out that this blurred my vision even further, mostly encountering a comparison of assuming a compact metric space $(E,\rho)$ versus the assumption of a family of closed and bounded subsets (the latter is preferable by the way, since it poses a weaker assumption). After failing to find the solution the easy way via google, I resorted to my stubbornness and finally succeeded in proving that if the subsets in $\mathcal{F}$ are non-empty and bounded, then the Hausdorff metric is finite and therefore well-defined.

Although the proof is not so difficult (that’s easy to say after completing the proof and once the creative frustration is over), I decided to share it so that the next googl-er would find the e-shortcut I was looking for myself in the first place.

Proof.

Let $x\in X$ and $y\in Y$. Then, since

$\rho(X,Y)=\inf\{\rho(x,y):(x,y)\in X\times Y\}$,

it follows that for every $n\in\mathbb{N}$ there exist $z\in X$ and $w\in Y$ such that

$\rho(z,w)\le\rho(X,Y)+\frac{1}{n}.\ \ \ \ (1)$

Indeed, assume that (1) is not true. Then there exists $n_0\in\mathbb{N}$ such that for all $z\in X$ and $w\in Y$ it holds that

$\rho(z,w)>\rho(X,Y)+\frac{1}{n_0},$

whence

$\inf\{\rho(z,w):(z,w)\in X\times Y\}=\rho(X,Y)\ge \rho(X,Y)+\frac{1}{n_0}\Rightarrow\frac{1}{n_0}\le 0,$

so a contradiction has been reached, which means that (1) actually holds.

According to the triangle inequality of metric $\rho$,

$\rho(x,y)\le \rho(x,z)+\rho(z,w)+\rho(w,y).\ \ \ \ (2)$

It thus follows from (1) and (2) that for every $n\in\mathbb{N}$

$\rho(x,y)\le \delta(X)+\rho(X,Y)+\delta(Y)+\frac{1}{n}.\ \ \ \ (3)$

Note that (3) holds because the sets $X,~Y$ are bounded, which means that their respective diameters $\delta(X),~\delta(Y)$ satisfy

$\rho(x,z)\le\delta(X)=\sup\{\rho(q,q):q\in X\}<\infty,$

$\rho(w,y)\le\delta(Y)=\sup\{\rho(q,q):q\in Y\}<\infty.$

Since (3) holds for all $n\in\mathbb{N}$, it follows that

$\rho(x,y)\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (4)$

Indeed, assume that (4) is not true. Then it holds that

$\delta(X)+\rho(X,Y)+\delta(Y)<\rho(x,y),$

and, in combination with (3), it is deduced that for any $n\in\mathbb{N}$

$0<\rho(x,y)-(\delta(X)+\rho(X,Y)+\delta(Y))\le\frac{1}{n},$

which is a contradiction because it follows from the Archimedean property that there exists $n_0\in\mathbb{N}$ such that

$\frac{1}{n_0}<\rho(x,y)-(\delta(X)+\rho(X,Y)+\delta(Y)),$

hence (4) is true.

Recalling that

$\rho(x,Y)=\inf\{\rho(x,y):y\in Y\}\le\rho(x,y),$

it follows from (4) that for any $x\in X$

$\rho(x,Y)\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (5)$

Since (5) holds for any $x\in X$, it follows that the set $\{\rho(x,Y):y\in Y\}$ has an upper bound, therefore according to the completeness axiom for real numbers, $\{\rho(x,Y):y\in Y\}$ has a supremum. In particular,

$\sup\{\rho(x,Y):x\in X\}\le \delta(X)+\rho(X,Y)+\delta(Y).\ \ \ \ (6)$

By means of symmetry of (6), this also means that

$\sup\{\rho(y,X):y\in Y\}\le \delta(X)+\rho(X,Y)+\delta(Y),\ \ \ \ (7)$

which completes the proof.