Redshift Academy


Basic Group Theory
------------------

Symbols
-------

∈ = is in
∉ = not in
∀ = for all
∅ = empty
∃ = exists
⊂ = subset of
ℤ = set of all integers 
ℂ = set of all complex numbers
ℝ = set of real numbers
ℚ = set of rational numbers

Definition
----------

A group, (G,*) is a set of elements g_i = {a,b,c ...} that 
satisfy the following axioms:

Note:  * is the operation + or x (only 1 operation is allowed).

1. Closure:  a and b are elements then their composition must 
             also be a member of the group. Thus,
 
             a, b ∈ G -> a*b ∈ G

2. Identity:  There is some element, e, such that e*a = a.  Thus,

              e ∈ G -> e*a ∈ G for any a ε G

3. Inverse:  For any element, a, there is an inverse element a^-1 
             such that a*a^-1 = e.  Thus,

             a, a^-1 ∈ G then aa^-1 ∈ G

4. Associativity:  a*(b*c) = (a*b)*c

Example 1.

(ℤ,+) = {... -3,-2,-1,0,1,2,3,4 ...}

✔ Closure:  a,b ∈ ℤ -> a + b ∈ ℤ

✔ Identity: a + 0 = 0 + a = a

✔ Inverse: a^-1 = -a since a^-1 + a = e

✔ Associativity:  (a + b) + c = a + (b + c)


Example 2.

(ℤ,x) = {... -3,-2,-1,0,1,2,3,4 ...}

✔ Closure:  a,b ∈ ℤ -> a x b ∈ ℤ

✔ Identity: a x 1 = 1 + a = a

x Inverse: 2 x integer = 1 has no solution in ℤ

Associativity:  (a x b) x c = a x (b x c)

Example 3.

GL(n,ℝ) is the group of all n x n matrices with 
non zero determinants under matrix multiplication.

            -   -  -   -     -               -
 Closure:  | a b || e f | = | ae + bg af + bh |   ✔
           | c d || g h | = | ce + dg cf + dh |
            -   -  -   -     -               -
             
                 -   -
 Identity:  I = | 1 0 | ∴  A x I = I x A   ✔
                | 0 1 |
                 -   -

            -   -                 -     -
 Inverse:  | a b |^-1 = 1/(ad- bc)|  d -b |   ✔
           | c d |             | -c  a |
            -   -                 -     -

 Associativity:  (A x B) x C = A x (B x C)   ✔

 Commutativity:  A x B ≠ B x A   x

Commutativity
-------------

ABELIAN: [g_i,g_j] = 0 

NON-ABELIAN: [g_i,g_j] ≠ 0 
             
Examples:  Integer multiplication is Abelian.
           Matrix multiplication is generally
           non-Abelian.

Cayley Tables
-------------

Cayley tables allow us to construct verify the
group closure property.  They have the following 
properties.

1.  Square

2.  No duplicate elements allwed in rows or columns.
    This dictates how the rows and columns are formed
    regardless of the group operation.

3.  Symmetric about diagonal indicates the group 
    is abelian.

* = group operation.

2nd order group:

* | e | a
--+---+----
e | e | a           
--+---+----
a | a | e

This is the same as (isomorphic to) ℤ (mod 2) 
(or ℤ₂).

3rd order group:

* | e | a | b
--+---+---+---   
e | e | a | b        
--+---+---+---
a | a | b | e
--+---+---+---
b | b | e | a

This is the same as (isomorphic to) ℤ (mod 3) 
(or ℤ₃).

4th order groups are a little more complicated 
because there is more than one way to organize 
the Cayley, but the same principles apply.

Klein 4 group:

+ | e | a | b | c
--+---+---+---+---
e | e | a | b | c    
--+---+---+---+---
a | a | e | c | b
--+---+---+---+---
b | b | c | e | a
--+---+---+---+---
c | c | b | a | e


ℤ (mod 4) (or ℤ₄)

+ | e | a | b | c
--+---+---+---+---
e | e | a | b | c    
--+---+---+---+---
a | a | b | c | e
--+---+---+---+---
b | b | c | e | a
--+---+---+---+---
c | c | e | a | b

4th roots of unity {1,-1,i,-i}:

x | e | a | b | c
--+---+---+---+---
e | e | a | b | c    
--+---+---+---+---
a | a | e | c | b
--+---+---+---+---
b | b | c | a | e
--+---+---+---+---
c | c | b | e | a

Modular Additive and Multiplicative Inverses
--------------------------------------------

In modular arithmetic, the modular additive and
multiplicative inverses are also defined.  It is 
the number a such that a + x = 0 (mod n) or ax = 0
(mod n). These inverse always exist. For example, 
consider the group ℤ₃


+ | 0 1 2 
--+------
0 | 0 1 2
1 | 1 2 0
2 | 2 0 1

1 + 2 = 0 (mod 3) 

and,

x | 0 1 2 
--+------
0 | 0 0 0
1 | 0 1 2
2 | 0 2 1

2 x 2 = 1 (mod 3)

The modular additive and multiplicative inverses
should not be confused with the ordinary inverses
i.e. 2 + (-2) = 0 and 2(1/2) = 1.


Subgroups
---------

(G,*) = {a,b,c,d, ...} then (H,*) = {a,b} form a subgroup.
              
Note: e and the inverse must be in the subgroup.

Example 1.

(ℤ,+)

Consider the even integers (2ℤ,+)

✔ Closure:  a,b ∈ 2ℤ -> a + b &eisin; 2ℤ

✔ Identity: a + 0 = 0 + a = a

✔ Inverse: a^-1 = -a

✔ Associativity:  (a + b) + c = a + (b + c)

It turns out that all we need to show is closure
and the existence of inverses to show that we have
found a subgroup.

What about the odd integers (2ℤ + 1,+)

x Closure:  a + b = even number

✔ Inverse: a^-1 = -a

Example 2.

Consider rotations by 90° of a square in 2D with composition 
equal to the addition of rotation angles.  Therefore, G = {I, R₉₀, 
R₁₈₀, R₂₇₀}.  This is the symmetry group of a square.

A      B
 ------
|      |  {I, R₉₀, R₁₈₀, R₂₇₀}
|      |
 ------
D      C

We can represent all of the rotation operations 
by:

     I   R₉₀   R₁₈₀  R₂₇₀
     ---------------------
I |  I R₉₀  R₁₈₀  R₂₇₀
R₉₀ |  R₉₀ R₁₈₀  R₂₇₀  I
R₁₈₀ |  R₁₈₀ R₂₇₀  I  R₉₀
R₂₇₀ |  R₂₇₀ I  R₉₀  R₁₈₀  

Notes:

* | e 
--+--- is the trivial subgroup.
e | e 

The group itself is a subgroup.  A subgroup that is not
the group itself is called a proper subgroup.

Group Extensions
----------------

Consider the symmetry group of the square again.

Reflection about vertical center line:

B      A         
 -------         y
|       |        ^      {m_v}
|   O   |        |
|       |         -->x
 -------
C       D
             
     -    -
m_v = | -1 0 |
    |  0 1 |
     -    -

 -    -  - -     -  -
| -1 0 || x | = | -x |
|  0 1 || y |   |  y |
 -    -  - -     -  -


Reflection about horizontal center line:

D       C
 -------
|       |  {R₁₈₀m_v}
|   O   |
|       |
 -------
A       B

 -          -  - -     -    -  - -      -  -   
| cosθ -sinθ || x | = | -1  0 || x | = | -x |  
| sinθ  cosθ || y |   |  0 -1 || y |   | -y |
 -          -  - -     -    -  - -      -  -
 -    -  -  -     -  -     
| -1 0 || -x | = |  x |
|  0 1 || -y |   | -y |
 -    -  -  -     -  -     

Reflection about upper-left to lower-right diagonal:

A      D
 -------
|       |  {R₉₀m_v}
|   O   |
|       |
 -------
B      C

Remembering that a clockwise roation of 90° corresponds 
to a terminal angle of 270°, we get:

 -          -  - -     -    -  - -     -  -
| cosθ -sinθ || x | = |  0 1 || x | = |  y |
| sinθ  cosθ || y |   | -1 0 || y |   | -x |
 -          -  - -     -    -  - -     -  -
 -    -  -  -     -  -     
| -1 0 ||  y | = | -y |
|  0 1 || -x |   | -x |
 -    -  -  -     -  -   

Therefore:
  
   A        B
(-1,1)    (1,1)
    -------
   |       |  
   |   O   |
   |       |
    -------
(-1,-1)   (1,-1)
   D        C

x -> -y
y -> -x

A: (-1,1) -> (1,-1) = C
B: (1,1) -> (-1,-1) = B
C: (1,-1) -> (-1,1) = A
D: (-1,-1) -> (1,1) = D


   A        D
(-1,1)    (1,1)
    -------
   |       |  
   |   O   |
   |       |
    -------
(-1,-1)   (1,-1)
   B        C

Reflection about lower-left to upper-right diagonal:

C       B
 -------
|       |  {R₂₇₀m_v}
|   O   |
|       |
 -------
D       A

Remembering that a clockwise roation of 270° corresponds 
to a terminal angle of 90°, we get:

 -          -  - -     -    -  - -     -  -
| cosθ -sinθ || x | = | 0 -1 || x | = | -y |
| sinθ  cosθ || y |   | 1  0 || y |   |  x |
 -          -  - -     -    -  - -     -  -
 -    -  -  -     -  -     
| -1 0 || -y | = |  y |
|  0 1 ||  x |   |  x |
 -    -  -  -     -  -    

Therefore:
  
   A        B
(-1,1)    (1,1)
    -------
   |       |
   |   O   |  
   |       |
    -------
(-1,-1)   (1,-1)
   D        C

x -> y
y -> x

A: (-1,1) -> (1,-1) = C
B: (1,1) -> (1,1) = B
C: (1,-1) -> (-1,1) = A
D: (-1,-1) -> (-1,-1) = D


   C        B
(-1,1)    (1,1)
    ------=
   |       |  
   |   O   |
   |       |
    -------
(-1,-1)   (1,-1)
   D        A