## Common Groups and Notations ### Generic Groups - $C_n$: the cyclic group of order $n$. - $\langle S\rangle$: the group generated by $S\subseteq G$ of some group. - $\langle g\rangle$: $\langle\{g\}\rangle$ for some $g\in G$. - If $o(g)<\infty$, $\left< g \right>\cong C_{o(g)}$; otherwise $\left< g \right>\cong\mathbb{Z}$ - $G/H$: the quotient group of a normal subgroup $H\triangleleft G$, containing the cosets of $H$. - $\text{Aut}(G)$: the automorphisms of $G$, i.e. isomorphisms $G \to G$. ### Numbers - $\mathbb{Z},\mathbb{Q},\mathbb{R},\mathbb{C}$: the number sets under addition. - $\mathbb{Q}^*,\mathbb{R}^*,\mathbb{C}^*$: their non-zero elements under multiplication. - $\mathbb{Z}_n=\left< 1 \right>$: the integers modulo $n$ under addition. - $\mathbb{Z}_n^*:$ the integers coprime with $n$, modulo $n$ under multiplication ### Matrices - $GL(n,\mathbb{R})$: general linear group, $n\times n$ invertible real matrices under matrix multiplication - $SL(n,\mathbb{R})$: special linear group, matrices with determinant $1$. - $O(n)$: real, orthogonal $n\times n$ matrices. - $SO(n)$: real, orthogonal matrices with $\det=1$. - $U(n)$: complex unitary matrices ($A^{-1}=\bar A^T$). ### Symmetry - $D_{2n}$: the dihedral group, the symmetries of the $n$-gon. - $V$ (or $V_4$): the Klein four-group, the symmetries of a non-square rectangle. ### Permutation - $\text{Sym}(S)$: the permutation group of the set $S$. - $S_n$: $\text{Sym}(\{1,2,\dots n\})$. - $A_n$: subgroup of $S_n$, containing elements with even parity only. ## Group Axioms ### Binary operations - A **binary operation** $*$ on a set $S$ is a map $S\times S\to S$. - By definition, $Slt;u> must be closed to the operation</u>: subtraction is not a binary operation on $\mathbb{N}$. - A binary operation $*$ can be **associative** and/or **commutative** (aka **Abelian**) - An element $e$ is an **identity** if $\forall s \in S:(e*s)=(s*e)=s$ - An element $s$ has an **inverse** $s^{-1}$ if $(s^{-1}*s)=(s*s^{-1})=1$. * Inverses under associative operations are unique. - A subset $T$ of $S$ is **closed** under $*$ if $\forall t_{1},t_{2} \in T: (t_{1} * t_{2}) \in T$ ### Group axioms - A **group** is a set $G$ paired with a binary operation $*$ on it, satisfying the following axioms: - $G$ is closed under $*$, implied by $*$ being a binary operation over $G$. - $*$ is associative. - There exists an identity $e\in G$. - All elements in $G$ have inverses. ### Cyclic Groups - A group $G$ is **cyclic** if there exists $g ∈ G$ such that $G = \{g^k : k ∈ \mathbb{Z}\}$, where $g$ is called the **generator**. - e.g. $\mathbb{Z}$ is cyclic with generators $1,-1$ (either works) - The **order of an element** $g\in G$, $o(g)$, is the least positive integer $r$ such that $g^r = e$. If no such integer exists then $g$ has infinite order ### Group relations - With groups $(G, ∗_G),(H, ∗_H )$, their **product group** is $G × H$, with the operation $∗$ defined by $(g_1,h_1)*(g_2,h_2)=\big((g_1 *_G g_2),(h_1 *_H h_2)\big)$ - $H \subseteq G$ is a **subgroup** of $G$, denoted $H\le G$, if $(H,*|_{H})$ is a group: - $e\in H$. - $H$ closed under $*$. - all elements of $H$ have inverses in $H$ too. - A map $\phi:G\to H$ is an **isomorphism** between the groups if: - $\phi$ is bijective. - $\phi$ preserves operations: $\phi(g_1 ∗_G g_2) = \phi(g_1) ∗_H \phi(g_2)$. - If such a map exists, $G\cong H$ are **isomorphic**. ## Permutation Groups ### Permutations - A permutation $\sigma$ is a bijection $S\to S$, and the set of all permutations is $\text{Sym}(S)$ - $\text{Sym}(\{1,2,\dots n\})$ is written as $S_n$ - ***permutations are done from left to right (in Oxford)***: $a\sigma\tau=(a\sigma)\tau$, where $a\in S$, and $\sigma,\tau\in \text{Sym}(S)$ - $\text{Sym}(S)$ forms a group under composition, with cardinality $(n!)$ - the array notation writes the permutation as a matrix with originals in the first row, and their images under permutation in the second: $ \begin{pmatrix}s_1,\dots ,s_n\\ s_1\sigma,\dots,s_n\sigma\end{pmatrix} $ - array notations are not unique for a permutation (swapping columns do not matter) - an $n × n$ matrix is a **permutation matrix** if each row and each column contain a single entry 1 and all other entries are 0 - all $σ ∈ S_n$ can be associated with a permutation matrix $P_σ$ such that the 1 entry in row $i$ of $P_σ$ is in column $iσ$. - e.g. $P_{(12)}=\begin{pmatrix}0&1&0\\1& 0& 0\\0&0&1\end{pmatrix}$ - left-multiplying $P$ to $(1,2,\dots,n)^T$ gives a column vector representing the permutation ### Cycles - A permutation in $S_n$ is a **cycle** if it cycles some subset of $\{1,\dots,n\}$, while keeping the remaining unchanged - a $k$-cycle cycles $k$ elements - for cycles, **the cycle notation** lists the elements it cycles, while the unchanged elements are omitted $ \sigma=(s_1,\dots,s_n):\ \ s_{k-1}\sigma =s_{k}\ \ \forall k< n \\(s_n\text{ goes to }s_1 \text{ instead}) $ - two cycles are **disjoint** if they operate on completely different elements - disjoint cycles commute (see lecture notes for proof) ### Decomposing permutations as cycles - all permutations can be uniquely written as the product of disjoint cycles (up to commuting) - proof: for an element $a$, the set $\{a,a\sigma,a\sigma^2,\dots\}$ will eventually have repetitions, since the original set $\{1,\dots,n\}$ is finite. take $k+1$ as the first time a repeat occurs, then $(a,a\sigma,\dots,a\sigma^k)$ is a part of the permutation now take $b$ not attained in $(a,a\sigma,\dots,a\sigma^k)$, repeat to get $(b,b\sigma,\dots,b\sigma^l)$, which is disjoint from the cycle of $a$ for otherwise $b$ would be attained somewhere in it repeat to get more disjoint cycles till $\{1,\dots,n\}$ is exhausted since the cycle in which one element appears is unique, the entire expression of the permutation as cycles is unique - in writing the permutation as disjoint cycles, unchanged elements (1-cycles) are omitted - the **cycle decomposition type** (or just **cycle type**) of a permutation is the number of cycles of each length in its decomposition as disjoint cycles (not the cycles themselves) - the **order (of a permutation)** is the least common multiple of the cycle lengths of its cycle types - two permutations $\sigma,\tau\in S_n$ are **conjugates** if there is $\rho\in S_n:\sigma=\rho^{-1}\tau\rho$ - conjugate permutations have the same cycle type ### Parity of permutations - A **transposition** is another term for a 2-cycle - a transposition has permutation matrix of determinant -1 - Every permutation can be written as a product of transpositions - proof: write the permutation as disjoint cycles, then write the cycles as consecutive transpositions - A permutation is odd (even) if it can be written as a product of an odd (even) number of transpositions - The parity (even-or-odd-ness) of a permutation is well-defined, since the cycle decomposition is unique, and each cycle of length $k$ always decomposes into $k-1$ transpositions, so the total number is determined - Alternatively, the $\det$ of the permutation matrix of the permutation is the product of its transpositions, so equals $(-1)^k$, where $k$ is the number of transposition in some decomposition, and since the $\det$ is unique, so is the parity --- ## Subgroups and Cyclic Groups ### More on subgroups - **The subgroup test**: with group $(G,*)$, $H\subseteq G$ forms a subgroup if and only if: - $H$ non-empty, - and $\forall x,y\in H, x^{-1}y\in H$ - Intersections of subgroups are also subgroups ### Generators - for group $G$ and $S\subseteq G$, **the subgroup generated by $S$**, $\langle S\rangle$, is the smallest subgroup that contains $S$, and for $p\in G$, $\langle p\rangle$ is short hand for $\langle\{ p\}\rangle$ - the elements $S$ are the **generators** of $\langle S\rangle$ > Proving minimality of some set $\Sigma$ that might be $\langle S\rangle$: > > - (1) show that all the elements of $\Sigma$ are combinations of elements of $S$, so they must be in $\langle S\rangle$ *(i.e. $\Sigma$ is a subset of any candidate for $\langle S\rangle$)* > - (2) show that $S\subseteq\Sigma$, and $\Sigma$ is a subgroup *(i.e. $\Sigma$ is itself a candidate, so it must be the smallest candidate)* > - in practice, this requires $\Sigma$ to be equal the set of all combinations of elements of $S$, no more and no less - Example: $\langle g,h\rangle = \{g^a h^b: a,b\in\Z\}$ if $gh=hg$ - proof: obviously RHS $\subseteq$ LHS, and RHS is a subgroup by the subgroup test when $g,h$ commute ### Cyclic subgroups - a single element $p$ is the generator of its **cyclic group**: $\langle p\rangle=\{p^k:k\in\Z\}$ and if $o(p)$ finite, then $\langle p\rangle =\{ e,p,p^2,...,p ^{o(p)-1}\}$ - if $P=\langle p\rangle$, i.e. $P$ is cyclic... - $P$ is isomorphic to the (generic) cyclic group $C_n$ if $|P|=n$ finite - $P$ is isomorphic to $\Z$ under addition if $|P|$ infinite (by mapping $p^k\lrarr k,k\in\Z$) - subgroups of cyclic groups are also cyclic - proof: suppose $G=\langle g\rangle$ cyclic, $H\le G$, and $n\equiv \min\{k>0:g^k\in H\}$ obviously $\langle g^n\rangle\subseteq H$, since $H$ is closed and $g^n\in H$ $H\subseteq\langle g^n\rangle$ too: for any $g^a\in H$, $a=kn+r$ for some $k,r\in\Z,0\le r<n$ so $g^r=g^a(g^n)^{-k}\in H$, by closure minimality of $n$ contradicts the choice of $0\le r<n$ unless $r=0$, so $g^a=g^{-nk}\in \langle g^n\rangle$ for all $g^a\in H$, so $H\subseteq\langle g^n\rangle$ so $H=\langle g^n\rangle$ cyclic. - Corollary: for non-zero integers $m,n$, they have HCF $h$ and LCM $l$ defined as following: (existence of $h,l$ given by $\langle m,n\rangle,\langle m\rangle\cap\langle n\rangle$ are both subgroups of the cyclic $\Z$, so they must be cyclic too) - **Chinese Remainder Theorem**: if $m,n\in\N$ coprime, then $C_m\times C_n\cong C_{mn}$ specifically, with $\langle g\rangle=C_m,\langle h\rangle =C_n,$ there is $\langle (g,h)\rangle = C_m\times C_n$ with order $mn$ - proof: $k\equiv o((g,h))=|C_m\times C_n|=mn$, since: clearly $k\le mn$, so it is sufficient to show that $mn|k$ since $(g,h)^k=(g^k,h^k)=(e,e)$, both $m,n|k$ since $m,n$ coprime, their HCF $h=1$, and Bezout’s lemma gives $u,v\in\Z: um+vn=1$ then $mn|(umk+vnk)=k$, so $mn=o((g,h))$ since $\langle (g,h)\rangle \le C_m\times C_n$, the two, having the same cardinality, must equal since $\langle (g,h)\rangle$ has order $mn$, it must be isomorphic to $C_{mn}$ so $C_m\times C_n=\langle(g,h)\rangle\cong C_{mn}$ --- ## Equivalence Relations ### Definition - an **equivalence relation** is a binary relation that is - reflexive ($a=a$), - symmetric ($[a=b]\iff [b=a]$), - and transitive ($[a=b,b=c]\Rarr [a=c]$) - **conjugacy**: for $g,h\in G$, they are conjugate in $G$ if $\exist k\in G: g=k^{-1}hk$. - conjugacy is an equivalence relation - given the equivalence relation $\sim$, the **equivalence class** of $g\in G$, denoted $\bar g$ or $[g]$, is $\{h\in G: g\sim h\}$ - a **partition** of the set $S$ is a collection of subsets of $S$ that (1) are all non-empty, (2) cover the entire $S$ in their union, and (3) pairwise disjoint - given a partition $P$ of $S$, for $a\in S$, $P_a$ is the unique subset in the partition that contains $a$ - the collection of equivalence classes $P$ of $\sim$ in $S$ form a partition of $S$ - proof: non-empty: for any equivalence class $[a],a\in S$, there is $a\sim a\Rarr a\in [a]$, so $[a]$ non-empty. complete coverage: for every $a\in S$, $a\in[a]\in P$. disjoint: if $x\in[a],x\in[b]$, then transitivity gives $a\sim b$, so $[a]=[b]$, so distinct equivalence classes have no overlaps (else they are identical, contradiction) - in the set $S$, an equivalence relation $\sim$ uniquely defines a partition $P$, and vice versa ### Modular arithmetic - under modular arithmetic, sums, differences, and products are defined to be the remainder of what we get in ordinary arithmetic - $\Z_n$ is the set $\{\bar0,\bar1,\dots,\overline{n-1}\}$, i.e. the equivalence classes defined by remainders in $\text{mod } n$ - $(\Z_n,+_{\text{mod n}})$ is an Abelian and isomorphic to $C_n$ - proof: $+_{\text{mod n}}$ has all the properties inherited from ordinary arithmetics, and $(\Z_n,+_{\text{mod n}})=\langle \bar1\rangle$, where $\bar1$ has order $n$ - $\bar x\in\Z_n$ has multiplicative inverse $\iff \gcd(x,n)=1$, and $x$ is called a **unit** of $\Z_n$ - proof: ($\Rarr$) $[\bar x\bar y=\bar 1]$ means $[xy=mn+1]$ for some $m\in\N$, so $k\equiv \gcd(x,n)$ has $k|xy-mn=1$, so $k=\gcd(x,n)=1$. ($\Larr$) $\gcd(x,n)=1$ means in $(\Z,+)$, $\langle x,n\rangle=\langle\gcd(x,n)\rangle=\langle 1\rangle$ Take $\text{mod }n$ gives $\{(x^a+n^b)\text{ mod }n:a,b\in \Z\}=\{x^a\text{ mod }n\}=\langle \bar x\rangle=\langle \bar 1\rangle$, so $\exist k: \bar x^k=\bar1$, and $\bar x^{k-1}$ is the multiplicative inverse of $\bar x$ (note that the ‘exponent’ $x^a$ here is just multiplication $a\times x$, since the operation here is addition) - the units of $\mathbb{Z}_n$ form a group $\Z^*_n$ under modular multiplication --- ## Order and Lagrange’s Theorem ### Definition - Again, for $g$ in a group, the **order** $o(g)=\min\{k>0:g^k=e\}$ - for $g$ with $o(g)$ finite, $g^k=e\iff o(g)|k$ - ($\Rarr$) division algorithm gives $k=m\cdot o(g)+r$ so $g^k=(g^{o(g)})^mg^r=g^r=e$, and minimality of $o(g)$ gives $r=0$, so $o(g)|k$. ($\Larr$) immediate. - isomorphisms preserve order: with an isomorphism $\phi:G\to H,g\in G$, $o(g)=o(\phi(g))$. ### Cosets - with $H\le G$, the **left cosets** of ****$H$ are the sets $gH=\{gh:h\in H\},g\in G\backslash H$ the right cosets are similarly defined with $Hg$ - We write $G/H$ for the set of (left) cosets of $H$ in $G$ (note the direction of the slash...), and $|G/H|$ is the **index** of $H$ in $G$ - **Coset Equality Lemma**: Let $H\le G$ and $g, k ∈ G$, then $gH = kH \iff k^{−1}g ∈ H$. for right cosets, $kg^{-1}\in H$. ### The theorem - **Lagrange’s Theorem**: if $H\le G$, $G$ finite, then $|H|$ divides $|G|$. - proof: (1) the left cosets of $H$ is a partition of $G$: non-empty: there is always $e\in H$, and $g\in gH$ complete coverage: any $g_0\in G$ is in $g_0H$, since $e\in H$ disjoint: $[x\in g_1H,x\in g_2H]\iff[x=g_1h_1=g_2h_2]$ $\Longrightarrow [g_2^{-1}g_1=h_1^{-1}h_2\in H]\iff [g_1H=g_2H]$ by coset equality lemma, so any overlap means that the two cosets are identical so the cosets are a partition of $G$ (2) each coset have the same size as $H$ clearly $\gamma:h\to gh$ is a bijection of $H\to gH$ (surjective by construction of $gH$, and injective by applying $g^{-1}$), so $|H|=|gH|$ (both finite since $G$ is) so (1) and (2) give $|G|=|G/H|\times |H|$. - the converse is not true: $k$ divides $|G|$ does not mean that there is necessarily a subgroup with size $k$. - true in cyclic groups though: if $k|n,\Z_n$ always has $\langle n/k \rangle$ with order $k$ - true if $k$ prime though: see Cauchy’s Theorem - Corollary: $g\in G$ has $o(g)$ divides $|G|$, since $\langle g\rangle$ is a subgroup of $G$ with order $o(g)$. - Corollary of corollary: $g^{|G|}=g^{n\cdot o(g)}=e$ ### Results in number theory - **Fermat’s Little Theorem**: for prime $p$, and $a\in \Z, p\nmid a$, then $a^{p-1}=1 \text{ mod }p$. - proof: $\Z^*_p$ has cardinality $p-1$, so $\bar a^{p-1}=e=\bar 1$, so $a^{p-1}=1 \text{ mod }p$ - **Euler’s Theorem**: for $n\ge 2$, if $a$ coprime with $n$, then $a^{\phi(n)}=1 \text{ mod }n$ - where the phi function (totient function) $\phi(n)$ is the number of positive integers less than $n$ that are coprime with $n$ - proof: same but for $\Z^*_n$ in general, which has cardinality $\phi(n)$. - **Wilson’s Theorem**: for prime $p$, $(p-1)!=-1 \text{ mod }p$. - proof: define the equivalence class $\sim:x=y \text{ or } x=y^{-1}$ if $p=2$, direct verification proves the case if $p>2$, note that in $\mathbb Z_p^*,\,\{\bar1\}$ and $\{\overline{-1}\}=\{\overline{p-1}\}$ are the only classes with one element, so: - If $G:|G|$ even, then $G$ has a element of order 2 (i.e. is its own inverse) - proof: by pairing each element with its inverse, $e$ would be left as the only element left (so $|G|$ odd, contradiction) unless there is another element who is its own inverse. (rigorous argument done with the same equivalence class introduced in the proof of Wilson’s Theorem) - also an immediate corollary of Cauchy Theorem since $2$ prime --- ## Homomorphisms and Isomorphisms ### Definitions - A map $\phi:G\to H$ is **homomorphism** if it preserves products: $\phi(g_1)*\phi(g_2)=\phi(g_1*g_2)$ - no requirement on bijection: hence isomorphism is just a bijective homomorphism - an automorphism is an isomorphism $G\to G$, and endomorphism for homomorphism analogues - given $g\in G$, the conjugation map $\theta_g(h)=g^{-1}hg$ is an automorphism - given homomorphism $\phi$, its **kernel** is $\ker\phi=\{g\in G:\phi(g)=e_H\}$ - given homomorphism $\phi$, its **image** is $\text{Im }\phi=\{\phi(g):g\in G\}$ - a subgroup $H\le G$ is **normal**, denoted $H\triangleleft G$, if: $ gH=Hg \ \ \ \forall g\in G\\ \iff g^{-1}hg\in H \ \ \ \forall h\in H, g\in G $ - clearly $\{e\},G$ are normal subgroups of $G$, and $G$ is called **simple** if they are the only normal subgroups - by the second definition, $H$ has to be a union of conjugacy classes of $G$ to be normal, and in the context of permutation groups, the union of cycle type classes - the center $Z(G)$ of group $G$ is the set $\{h\in G: gh=hg\ \ \forall g\in G\}$ - $Z(G)\triangleleft G$ for obvious reasons ### Quotient Groups - define $*$ in $G/H:g_1H*g_2H=(g_1g_2)H$ , then $[\ *$ is well-defined$\ ]\iff[H\triangleleft G]$ - proof: ($\Rarr$) easy by verifying $(g^{-1}hg) H=(g^{-1}eg)H$ to get $g^{-1}hg\in H$ ($\Larr$) if $g_1H=g_2H, k_1H=k_2H$, then $g_1g_2^{-1},k_1k_2^{-1}\in H$ so normality of $H$ gives $g_2k_1k_2^{-1}g_2^{-1}\in H$ left multiply by $g_1g_2^{-1}$ gives $g_1k_1k_2^{-1}g_2^{-1}\in H$, so $g_1k_1H=g_2k_2 H$, and the operation is well-defined - if $H\triangleleft G$, then the **quotient group** $(G/H,*)$ is a group ### The first isomorphism theorem - for homomorphism $\phi:G\to H,\ker\phi\ \triangleleft \ G$ - proof: (1) prove the kernel is a subgroup, (2) prove it is closed to conjugation - for homomorphism $\phi:G\to H,\text{Im }\phi\ \le H$ - proof: apply the subgroup test - there is isomorphism $\theta: g\ker\phi\to\phi(g)$, and hence $G/\ker\phi\cong\text{Im }\phi$ - proof: just verify $\theta$ is well-defined, bijective, and a homomorphism --- ## Group Actions, Orbit-Stabilizer Theorem ### Definitions - A **left group action** $\rho: G\times S\to S$ satisfies: - $\rho (e,s)=s$ for all $s\in S$ - $\rho(g_1,\rho(g_2,s))=\rho(g_1g_2,s)$ - A **right group action** is similarly defined, but with $S\times G\to S$ - Alternatively, $\rho(g,s)$ can be denoted as $g\cdot s$ - Note that $G$ can act on itself, e.g. $*_G$ and conjugations are both group actions $G\times G\to G$. ### Orbits and Stabilizers - Given group action $\rho:G\times S\to S$, the **orbit** of $s\in S$ is $ \text{Orb}(s)=\{gs:g\in G\} $and the **stabilizer** of $s$ is$ \text{Stab}(s)=\{g\in G:gs=s\} $ - for the conjugation, the orbit of $g$ is its conjugacy class, and the stabilizer is its **centralizer** $C_G(g)=\{h\in G: hg=gh\}$ - Stabilizers are subgroups: $\text{Stab}(s)\le G$ - proof: apply the subgroup test ### Orbit-Stabilizer Theorem, Cauchy’s Theorem - The theorem states: given a group action and $s\in S$, $ |G|=|\text{Stab}(s)|\times|\text{Orb}(s)| $ - proof: there is a bijection between $[$the cosets of $\text{Stab(s)}]$ and $[\text{Orb}(s)]$: define map $\phi: \phi(g\text{Stab}(s))=g\cdot s$ $\phi$ well-defined and bijective since $ g\text{Stab}(s)=h\text{Stab}(s)\iff g^{-1}h\in \text{Stab}(s)\iff g\cdot s=h\cdot s $ so $|\text{Orb}(s)|=|G/\text{Stab}(s)|$, and applying Lagrange’s Theorem completes the proof - Corollary: $|C_G(g)|\times |C(g)|=|G|$, where $C_G(g)$ is the centralizer of $g$, and $C(g)$ the conjugacy class - **Cauchy’s Theorem**: if $p$ prime, $p$ divides $|G|$, then there is an element of order $p$ in $G$ - proof: see notes --- ## Orbit Counting (Burnside’s) Formula - the theorem states: given $G$ finite group acting on $S$, then: $ \#\text{orbits}=\frac{1}{|G|}\sum_{g\in G}\text{fix}(g),\ \ \ \text{fix}(g)=|\{s\in S:g(s)=s\}| $ - proof: write LHS as $N$. $\sum_{g\in G}\text{fix}(g)=\sum_{s\in S}|\text{Stab}(s)|=\sum_{s\in S}|G|/|\text{Orb}(s)|=|G|\times N$ last equality is because each orbit $O_n$ has $|O_n|$ elements, each of which contributes $|G|/|O_n|$ to the sum, so there is exactly one $|G|$ in the sum for each distinct orbit (see notes for the same proof with rigorous notations) - with $\text{fix}(g)$ defined above, conjugate elements have the same $\text{fix}$, so with $C_i$ denoting the conjugacy classes of $G$ and arbitrary $g_i\in C_i$, $ \#\text{orbits}=\frac{1}{|G|}\sum_{C_i\in G}\text{fix}(g_i)|C_i| $ ### Applying the Orbit Counting Formula Problems like... > How many distinct ways of painting a triangle’s edges with $n$ colors are there? > are essentially... > How many orbits are there, when we apply $D_6$ to triangles with edges colored with $n$ possible colors? > so we can use the orbit-counting formula on this: - Step 1: find all the conjugacy classes > in $D_6$, there is $\{e\},\{r,r^2\},\{s,sr,sr^2\}$ > - Step 2: find the $\text{fix}$ for each class > $\{e\}$ fixes everything, so $n^3$ > > > $C(r)$ fixes monochrome triangles, so $n$ (times two members) > > $C(s)$ fixes triangles with two colors, so $n^2$ (times three members) > - Step 3: apply the orbit counting formula (conjugacy class version) $ \#\text{orbits}=\frac{1}{6}\sum_{C_i\in G}\text{fix}(g_i)|C_i|=\frac{n^3+2n+3n^2}{6} $ - Sanity check: check that you get an integer, e.g. plug in some easy integers when $n$ is not specified --- ## Representations and Cayley’s Theorem - for group $G$ operating on a set $S$, $G$ has a homomorphism $\rho:G\to\text{Sym}(S)$. This is the **representation** of $G$ - proof: for any $g\in G$, $\rho_g$ defined by $\rho_gs=g\cdot s$ is a bijection, hence a permutation of $S$ then $\rho_g\in\text{Sym}(S)$, and define $\rho:\rho(g)=\rho_g$ gives the homomorphism - **Cayley’s Theorem**: for finite group $G$, $G\cong H_G\le S_n$ for some $n$ and subgroup $H_G$ of $S_n$ - proof: $G$ acting on $G$ has homomorphism $\rho: G\to\text{Sym}(G)$ given by left multiplication （that is, $g$ is mapped to a function $\theta_g:\theta_g(h)=gh$, the left-multiply-by-$g$ map) in fact $\rho$ is injective since $[\rho(g)=\rho(h)]\Rarr [\rho(g)(e)=\rho(h)(e)]\Rarr [g=h]$ so $G\cong\text{Im }\rho\le \text{Sym}(G)\cong S_{|G|}$