Tutorial 2A

1 Show addition modulo \(p\) is associative.

Case-split every damn thing.

2 Show that \(((\mathbb{Z}/p\mathbb{Z})^\times, \star)\) forms an Abelian group.

\(p\) is prime, and \(a \star b := r\) where \(r\) is the remainder when \(ab\) is divided by \(p\).

Closure

By division algorithm \(r \leq p-1\). Claim that \(r \ne 0\), that is \(p \nmid ab\). For suppose not then \(p\mid a\) (or \(p\mid b\)) which implies \(p \leq a\) which makes no sense.

Commute

\(ab = ba\) so \(r_{ab} = r_{ba}\).

Assoc

Goal is \((ab \mod p) c \mod p = a (bc \mod p) \mod p\). Probably easier to show that both are equal to \(abc \mod p\). Let \[\begin{align*} ab &= q p + r_{ab} \\ bc &= q'p + r_{bc} \\ abc &= q''p + r \end{align*}\] Then we have \[\begin{align*} abc &= (qp + r_{ab})c \\ &= qpc + r_{ab}\,c \\ &= a(q'p + r_{bc}) \\ &= aq'p + a\,r_{bc} \end{align*}\] By division algorithm \[ a\,r_{bc} \equiv r_{ab} c \equiv r \pmod{p}. \] which entails \(a \star (b\star c) = (a\star b) \star c = r_{abc}\).

Identity

Trivial verification that \(a \star 1 = 1 \star a = a\).

Inverse

For each \(a \in (\mathbb{Z}/p\mathbb{Z})^\times\), because \(a<p\) and \(p\) prime, by Bézout’s identity, there exists \(x,y\in\mathbb{Z}\) such that \[ ax = 1 - py \] by division algorithm let \(x = qp + b\) for some \(q\in\mathbb{Z}, b\in(\mathbb{Z}/p\mathbb{Z})^\times\), note \(b\ne 0\) otherwise substituting back into above equation yields \(p(aq + y) = 1\). Now \[ ab = 1 - py - aqp \] which means \(a\star b = r_{ab} = 1\).

3 Matrix stuff

\[ G = \left\{\, A \in M_n(\mathbb{R}): A A^\top = I, \det(A) = 1 \,\right\} \] Show that \(G\) under matrix multiplication is a group.

Lemma 3.0. \(G\) under matrix multiplication is a magma.

Proof. For any \(A,B \in G\), we have \((AB)(AB)^\top = ABB^\top A^\top = AA^\top = I\). Additionally, by multiplicativity of \(\det\), \(\det(AB) = \det(A)\det(B) = 1\). \(\square\)

Lemma 3.1. \(G\) under matrix multiplication is a semigroup.

Proof. Refer to MA1101R for a proof that matrix multiplication is associative. \(\square\)

Lemma 3.2. \(G\) under matrix multiplication is a monoid.

Proof. It is known that \(I\) is the identity under matrix multiplication. \(G\) contains \(I\), for \(I I^\top = II = I\) and \(\det(I) = 1\). \(\square\)

Almost done. \(G\) under matrix multiplication is a group.

Proof. It remains to show existence of inverse. Let \(A\in G\), by characterising property of \(G\), we have \(A A^\top = I\), from MA1101R we also have \(A^\top A = I\), So we just need to show that \(A^\top \in G\).

• \(A^\top A^{\top\top} = A^\top A = I\), check.
• \(\det(A^\top) = \det(A) = 1\), check. \(\square\)

4 A binary group is Abelian.

Let \(a,b\in G\). \[\begin{align*} e &= (ab)(ab) \\ e &= abab \\ a &= bab \\ ab &= ba \tag*{$\square$} \end{align*}\]

5 Pigeonhole principle.

Let \((G, *)\) be a finite group. Show that for any \(x\in G\), there exists \(n \in\mathbb{N}\) such that \(x^n = e\).

Let \(x\in G\) be arbitrary, define the set-theoretic map \(\varphi\) as \[\begin{align*} \varphi: \mathbb{N}&\to G \\ n &\mapsto x^n \end{align*}\] As \(G\) is finite, by pigeonhole principle, there exists \(i, j\in\mathbb{N}\), \(i < j\) (WLOG) such that \[\varphi(i) = x^i = x^j = \varphi(j).\] Multiply by \(x^{-1}\) \(i\) times and we have \(e = x^{j-i}\). \(\square\)

6 \(n\times n\) multiplication table

Let \(\left\lvert G \right\rvert = \left\{\, x_1, x_2, \dots, x_n \,\right\}\).

6.1 row

Fix a row \(i\), means we fix \(x_i * -\). To show that every element \(g \in G\) occurs exactly once in the row of multiplication table, we show that for any \(g\in G\), there exists unique \(x_j \in G\) such that \(x_i * x_j = g\). This is true because \(x_i^{-1}\) is unique so we just set \(x_j := x_i^{-1}g\).

Alternatively, the claim is equivalent to the assertion that the left-multiply map \[a \mapsto x_i * a\] is a permutation on the set of \(G\), because it is a operator on a finite set with an inverse, namely \(b \mapsto x_i^{-1} * b\).

6.2 column

is analogous.

7 Farming

Too much work.

8 \((\mathbb{Z}, +, \times)\) is not a field.

Lack of multiplicative inverse.

Tutorial 2B

9 \(\mathbb{Z}/p\mathbb{Z}\) is a field under addition and multiplication \(\mod p\).

TODO!!!

10 Hamiltonian

Rewrite the definition more succinctly as \[ \mathbb{H}= \left\{\, \begin{pmatrix} a & b \\ -\overline{ b } & \overline{ a }\end{pmatrix} : a,b \in \mathbb{C} \,\right\}.\]

10.1 Real vector space

We have \(\mathbb{H}\subseteq \mathbb{M}_2(\mathbb{C})\). The set of \(2\times 2\) complex matrices already forms a complex vector space, which means it also forms a real vector space, for \(\mathbb{R}\) is a subfield of \(\mathbb{C}\). By eyeballing from the definition inspect that \(\mathbb{H}\) is indeed closed under \(+\) and scalar multiplication. \(\square\)

10.2 \((\mathbb{H}^\times, \times)\) forms a non-Abelian group.

Closure.

Let \(a,b,c,d\in\mathbb{C}\), we have \[ \begin{pmatrix} a & b \\ -\overline{ b } & \overline{ a } \end{pmatrix} \begin{pmatrix} c & d \\ -\overline{ d } & \overline{ c } \end{pmatrix} = \begin{pmatrix} ac - b\overline{ d } & ad+b\overline{ c } \\ -c\overline{ b }-\overline{ ad } & \overline{ ac }-\overline{ b }d \end{pmatrix} \] verify that RHS is in \(\mathbb{H}\).

Associative.

Follows from that of matrix multiplication.

Identity.

Trivial to see that \(I\in\mathbb{H}\).

Existence of inverse.

For any \(a,b\in\mathbb{C}\), let \[A = \begin{pmatrix} a & b \\ -\overline{ b } & \overline{ a } \end{pmatrix}\] computing determinant, get \(\det(A) = a\overline{ a } + b\overline{ b } = \left\lvert a \right\rvert^2 + \left\lvert b \right\rvert^2\). Because the size is only \(2\times 2\), the inverse matrix of \(A\) is eyeballable as \[ A^{-1} = \frac{1}{\left\lvert a \right\rvert^2 + \left\lvert b \right\rvert^2} \begin{pmatrix} \overline{ a } & \overline{ b } \\ -b & a \end{pmatrix} \] observe that \(A^{-1} \in \mathbb{H}\).

Not Abelian.

Define \[ A = \begin{pmatrix} i & i \\ i & -i\end{pmatrix} \quad B = \begin{pmatrix} 0 & 1+i \\ -1+i & 0\end{pmatrix} \] and we have \[ AB = \begin{pmatrix} -1-i & -1+i \\ 1+i & -1+i \end{pmatrix} \ne \begin{pmatrix} -1+i & 1-i \\ -1-i & -1-i \end{pmatrix} =BA \tag*{$\square$}\]

10.3 Distributivity

Follows from matrix multiplication. Refer to MA1101R notes, as \(\mathbb{R}^n\) proof in there generalises.

11 Square roots…

Let \(G\) be a finite group which for every \(x\in G\), there exists \(y\in G\) such that \(x = y^2\). Prove that every element in \(G\) has a unique square root in \(G\).

Let \(G = \left\{\, x_1,\dots,x_n \,\right\}\). We consider the map \(\varphi\) defined as \[\begin{align*} \varphi: G &\to G\\ x_i &\mapsto x_i^2 \end{align*}\] Suppose there exists a non-unique square root, say \(x,y,z\in G\), such that \(y\ne z\) but \(\varphi(y) = \varphi(z) = x\). This means that \(\varphi\) is not injective which implies \(\varphi\) is not surjective (operator on finite set). So there exists an element \(x\in G\) where for all \(x_i \in G\), \(\varphi(x_i) \ne x\). This contradicts assumption that every \(x\in G\) has a square root.

Alternatively consider the multiplication table of \(G\), the assertion “every element has a unique square root” is equivalent to the assertion that the diagonals of the multiplication table form a permutation of the elements in \(G\).

12 \(\left\lvert G \right\rvert\) is even, number of elements in \(G\) of order \(2\) is odd.

Let \(n = \left\lvert G \right\rvert\). Consider \(G \smallsetminus\left\{\, e \,\right\}\), it has \(n-1\) elements. Suppose for a contradiction that a even number of elements in \(G \smallsetminus\left\{\, e \,\right\}\) are of order \(2\). Then we have an odd number of elements that are not inverses of themselves. This is a contradiction as each element has a unique inverse, and inverses can only come in pairs.

13 Orbits

\(G\) is a subset of \(\operatorname{End}(V)\) that is a group under matrix multiplication. Let \(\mathbf{v} \in V\) be a column vector. A \(G\)-orbit of \(\mathbf{v}\) is \[ G\mathbf{v} = \left\{\, g\mathbf{v} \in V : g \in G \,\right\}. \]

13.1 If \(\mathbf{w} \in G\mathbf{v}\), then \(G\mathbf{w} = G\mathbf{v}\).

Since \(\mathbf{w} \in G\mathbf{v}\), there exists \(h\in G\) such that \(\mathbf{w} = h\mathbf{v}\). Take \(g\mathbf{w} \in G\mathbf{w}\), then \(g\mathbf{w} = gh\mathbf{v} \in G\mathbf{v}\) for \(gh \in G\) too. Similarly take \(g'\mathbf{v} \in G\mathbf{v}\), \(g'\mathbf{v} = g' h^{-1}\mathbf{w} \in G\mathbf{w}\).

13.2 Show that \(G\)-orbits are disjointed, either \(G\mathbf{w} = G\mathbf{v}\) or \(G\mathbf{v} \cap G\mathbf{w} = \emptyset\).

By law of excluded middle, either \(\mathbf{w} \in G\mathbf{v}\) or \(\mathbf{w} \notin G\mathbf{v}\). If former, we win by part 1. Otherwise, suppose for a contradiction \(G\mathbf{v} \cap G\mathbf{w} \ne \emptyset\), let \(\mathbf{u}\) inhabit that set. Then there exists \(h, h' \in G\) such that \(\mathbf{u} = h\mathbf{v} = h'\mathbf{w}\). Then we have \(\mathbf{w} = h'^{-1} h\mathbf{v}\), which contradicts fact that \(\mathbf{w} \notin G\mathbf{v}\).

13.3 Every vector \(\mathbf{v}\in V\) belongs to some \(G\)-orbit.

Take \(\mathbf{v}\in V\), we have \(\mathbf{v} = e\mathbf{v}\) so \(\mathbf{v} \in G\mathbf{v}\).

13.4 Orbits form a partition.

Easily follows from (ii) and (iii).

14 Exact

\[ \left\{\, e \,\right\} \to K \xrightarrow{i} G \xrightarrow{\varphi} H \to \left\{\, e \,\right\} \] If \((G,*)\) is a group, show that \((H,\star)\) is a group, then show that \((K,*)\) is a group.

\(\star\) is closed. For any \(h_1, h_2 \in H\), choose \(g_1, g_2\) such that \(h_i = \varphi(g_i)\), then \(h_1 \star h_2 = \varphi(g_1) \star \varphi(g_2) = \varphi(g_1 * g_2) \in H\).

Associative. Let \(h_1, h_2, h_3 \in H\), choose \(g_1, g_2, g_3\) such that \(h_i = \varphi(g_i)\). \[\begin{align*} (h_1 \star h_2) \star h_3 &= \varphi(g_1 * g_2)) \star \varphi(g_3) \\ &= \varphi((g_1 * g_2) * g_3) \\ &= \varphi(g_1 * (g_2 * g_3)) \\ &= h_1 \star \varphi(g_2 * g_3) \\ &= h_1 \star (h_2 \star h_3) \end{align*}\]

Identity and Inverse. Analogous argument shows that \(\varphi(e)\) is actually identity in \(H\).

\(K\) is a group.

Closure. Let \(k, k' \in K\), we have \(\varphi(k) = \varphi(k') = \varphi(e)\), then \[\begin{align*} \varphi(k) \star \varphi(k') &= \varphi(e) \star \varphi(e) \\ \varphi(kk') &= \varphi(e) \end{align*}\]

Associativity follows.

Existence of identity. follows as \(\varphi(e) = \varphi(e)\).

Inverse. Take \(k \in K\), suffices to show that \(k^{-1} \in K\). \[\begin{align*} \varphi(kk^{-1}) &= \varphi(e) \\ \varphi(e) \star \varphi(k^{-1}) &= \varphi(e) \\ \varphi(k^{-1}) &= \varphi(e) \end{align*}\]

15 Linear algebra

Let \[ \varphi: \left(\mathbb{F}_{13}\right)^3 \xrightarrow{\ \simeq\ } \left(\mathbb{F}_{13}\right)^3 \] be a group isomorphism

15.1 Consider those as vector spaces, show that \(\varphi\) is a linear transformation. (Invertible is free)

The operation on \((\mathbb{F}_{13})^3\) is coordinate-wise addition due to the definition of a product group, therefore \(\varphi\) preserving vector addition is also for free.

Observe that field operations in \(\mathbb{F}_{13}\) respects the law that \[ ab = \underbrace{b + b + \dots + b}_{a \text{ times}} \] then let \(v\in (\mathbb{F}_{13})^3, \alpha \in \mathbb{F}_{13}\), \[\begin{align*} \varphi(a v) &= \varphi(\underbrace{v + v + \dots + v}_{a \text{ times}}) \\ &= \underbrace{\varphi v + \varphi v + \dots + \varphi v}_{a \text{ times}} \\ &= a\, \varphi v \end{align*}\]

15.2 Counting matrices

(This feels like Tan Kai Meng’s MA2101S PYP)

Following hint, to count number of invertible \(3\times 3\) matrices, we just have to choose \(3\) basis vectors. Let \[A = \left(\begin{array}{c|c|c} v_1 & v_2 & v_3 \end{array}\right)\]

• For \(v_1\) choose anyone except zero vector, giving \(13^3 - 1\) ways,
• Choose \(v_2\) from anything except those in span of \(v_1\), giving \(13^3 - 13\) ways,
• Choose \(v_3\) from anything except those in spam of \(v_1\) and \(v_2\), giving \(13^3 - 13^2\) ways,

multiply everything to get answer which is \(9726417792\).