• Finals week help hours
  • Wed & Thu afternoon Dec 13 & 14 at 12-5pm in my office and Zoom.
  • Email me to make an appointment anytime.

• Final Exam Fri Dec 15, 2023 at 7:45-9:45am in our usual classroom Wells A-228
  • Covering all material of the course.
  • Study old Quizzes, Midterm Exam, and HW. I can email you any missing papers.
  • Look over your old work to understand mistakes; compare with solutions, class notes, course page notes, and the textbook.
  • Then re-do the problems without any help, to see if you understand. Repeat until you are confident about all the answers.
  • Identify especially confusing concepts to ask me about during help hours (see above).

+1 extra point to the first person pointing out each significant typo or error on this page. Recent corrections and revisions are in red. Tentative future assignments are in gray.

• 8/28 Linear mappings, diagonalization   Text   Notes |  ⊞ HW  
  1. For each linear motion L of the plane, give its matrix [L] and the formula for L(x,y).
     1. Reflection across the y-axis
     2. Reflection across the line y = −x
     3. Rotation by 90° clockwise
  2. For each matrix, describe the corresponding motion of the plane, and give its formula L(x,y).
     1. [

        −2	0
        0	1

        ]
     2. [

        √2⁄2	−√2⁄2
        √2⁄2	√2⁄2

        ]
  3. Extra Credit: A plane rotation matrix R (other than R = ±I) clearly has no real eigenvectors. Nevertheless, diagonalize it by finding its complex eigenvalues λ ∈ C and eigenvectors v₁, v₂ ∈ C². Sketch the eigenvalues in the complex plane C with its real and imaginary axes 1 and i = √(−1).
  4. Extra Credit: Consider the spatial rotation R = R_p,θ around an axis p with |p| = 1, by an angle θ ∈ [0,2π] in the right-handed orientation (thumb along p, fingers in direction of R). Explain why this rotation is given by the Euler-Rodrigues formula, using vector dot product and cross product:
     R(v)   =   v_∥  +  cos(θ) v_⊥  +  sin(θ) p×v ,
     where v_∥ = (p•v)p is the projection of v onto p, and v_⊥ = v − (p•v)p is the projection of v perpendicular to p. Compute the corresponding 3×3 rotation matrix, given p = (a,b,c).
     Hint: The vectors p , v_⊥ , p×v form an orthogonal right-handed basis (axis vectors), with the last two vectors of the same length. In terms of this basis, v   =   v_∥  +  v_⊥ . The axis component v_∥ remains unchanged, while v_⊥ component gets rotated by θ in the plane of v_⊥ , p×v .
  ⊞ Soln  

  1a. The columns of [L] are L(1,0) = (−1,0) and L(0,1) = (0,1), so [L]  =  [

  −1	0
  0	1

  ]   and L(x,y) = (−x,y).

  1b. Sketching the line of reflection y = −x shows that L(1,0) = (0,−1) and L(0,1) = (−1,0), so [L]  =  [

  0	−1
  −1	0

  ]   and L(x,y) = (−y,−x).

  1c. Rotating 90° clockwise shows that L(1,0) = (0,−1) and L(0,1) = (1,0), so [L]  =  [

  0	1
  −1	0

  ]   and L(x,y) = (y,−x).

  2a. The columns of the matrix are L(1,0) = (−2,0), so L flips the x-axis and stretches it by a factor of 2; and L(0,1) = (0,1), fixing the y-axis. L(x,y) = (−2x, y).

  2b. The values of L(1,0) and L(0,1) are 45° counterclockwise rotations of the x- and y-axes, so L rotates all vectors by 45° counterclockwise. L(x,y) = ^√2⁄₂(x−y, x+y).

• 8/30 Rotations & reflections, plane symmetry   Text   Notes   ⊞ HW  
  1. (h) Diagonalize the following matrices: first find eigenvalues by solving p(λ) = det(L-λI) = 0; then for a given λ, find the eigenvector v = (x,y) by solving the linear system (L−λI)v = 0. Describe the corresponding motion of the plane. (Do the computations by hand, don't just look up the answer!)
     1. [

        3	4
        4	−3

        ]
     2. [

        5	2
        1	4

        ]
  2. Let R be a counterclockwise rotation of the plane around the origin by ¹⁄₃ of a full turn (120°).
     1. Explain why R is a linear mapping (using the geometric interpretation of R(v+w) = R(v) + R(w)), and find its 2×2 matrix. Hint: The columns are R(1,0) and R(0,1).
     2. Check that the matrix R = [v₁|v₂] is orthogonal: first check that its columns form an orthonormal basis, meaning
        v₁·v₁ = v₂·v₂ = 1   and   v₁·v₂ = 0;
        recall that dot product is defined by (a,b)·(c,d) = ac + bd. Equivalently, check that R^T·R = I, where R^T is the transposed matrix with columns exchanged for rows.
     3. Consider the equilateral triangle centered at the origin with one vertex at v₁ = (2,2). Explicitly compute the other two vertices as v₂ = R(v₁), v₃ = R(v₂) = R²(v₁).
  3. Let the flip (reflection mapping) F be defined by the matrix [

     √2⁄2	√2⁄2
     √2⁄2	−√2⁄2.

     ]
     1. Check that the matrix is orthogonal.
     2. Find the eigenvalues and eigenvectors of F. Use these to describe F geometrically: what are its flipped and fixed lines?
     3. In the Text notes, we gave the general formula for an orthogonal flip across the fixed line in direction v₁ = (cos α, sin α); it is
        Fl_α = [

        cos 2α	sin 2α
        sin 2α	−cos 2α

        ].
        Show that F above is of this form for the correct value of α. Match this value of α with the line of reflection corresponding to the eigenvector of λ = 1 above.
  ⊞ Soln  
  1a. The characteristic polynomial of L is:

  p(λ)  =  det(L−λI)  =  det [

  3−λ	4
  4	−3−λ

  ]  =  (3−λ)(−3−λ) − (4)(4)  =  λ² − 25.

  Solving p(λ) = 0 gives the eigenvalues λ₁ = 5, λ₂ = −5.

  To find the eigenvector v₁ = (x,y), we solve (L−λ₁I)(v) = (L−5I)(x,y) = (0,0), i.e. the linear system

  −2x+4y = 0

  4x−8y = 0.

  This gives y = ½x, so choosing x = 2 gives v₁ = (2,1). Similarly, we get v₂ = (1,−2). We can check these by computing L(v) for each, and getting the multiple λv.

  The geometric picture of L stretches direction v₁ by a factor of 5, and also stretches the perpendicular vector \v₂ by 5 as well as flipping it over the origin. This is a dilation (stretch) by a factor of 5, followed by a reflection across the direction of v₁

  1b. The characteristic polynomial of L is:

  p(λ)  =  det(L−λI)  =  det [

  5−λ	2
  1	4−λ

  ]  =  (5−λ)(4−λ) − (2)(1)  =  λ² −9λ + 18  =  (λ−3)(λ−6).

  Solving p(λ) = 0 gives the eigenvalues λ₁ = 3, λ₂ = 6.

  To find the eigenvector v₁ = (x,y), we solve (L−λ₁I)(v) = (L−3I)(x,y) = (0,0), i.e. the linear system

  2x+2y = 0

  x + y = 0.

  This gives y = −x, so choosing x = 1 gives v₁ = (1,−1). Similarly, we get v₂ = (2,1). We can check these by computing L(v) for each, and getting the multiple λv.

  The geometric picture of L stretches direction v₁ by a factor of 3, and also stretches the (non-perpendicular) vector v₂ by 6. This is not directly related to any of our familiar mappings, but you can picture it in terms of its stretching effect on the parallelogram grid generated by v₁ and v₂.

  2a. R is a linear mapping because R(v+w) = R(v) + R(w), since the rotation of a parallelogram of vectors is a parallelogram of rotated vectors; and R(cv) = c R(v), since the rotation of a stretched vector is a stretched rotated vector. R rotates the standard basis vectors e₁ = (1,0), e₂ = (0,1) by ^2π⁄₃ radians to v₁ = (cos ^2π⁄₃, sin ^2π⁄₃), v₂ = (−sin ^2π⁄₃, cos ^2π⁄₃), giving the matrix:

  R  =  Rot_2π/3  =  [

  cos 2π⁄3	−sin 2π⁄3
  sin 2π⁄3	cos 2π⁄3

  ]  =  [

  −1⁄2	−√3⁄2
  √3⁄2	−1⁄2

  ].

  2b. The matrix product R^T·R gives the matrix of dot products of the column vectors of R = [v₁ | v₂].

  R^T·R  =  [

  v1

  v2

  ]·[v₁ | v₂]  =  [

  v1·v1	v1·v2
  v2·v1	v2·v2

  ]
  
   =  [

  1⁄21⁄2+√3⁄2√3⁄2	1⁄2(−√3⁄2)+√3⁄21⁄2
  −√3⁄21⁄2+1⁄2√3⁄2	−√3⁄2(−√3⁄2)+1⁄21⁄2

  ]  =  [

  1	0
  0	1

  ].

  Thus by definition, R is orthogonal.

  2c. Wolfram gives v₂ = R(2,2) = (−1−√3, −1+√3) and v₃ = R(v₂) = (−1+√3, −1−√3). Note the symmetry across y = x.

  3a. It is easy to check R^T·R = I, so R is orthogonal.

  3b. Wolfram gives eigenvalue λ₁ = 1 with eigenvector v₁ = (1+√2, 1) and λ₂ = −1 with v₂ = (1−√2, 1). Thus, R is the orthogonal reflection across the fixed line in direction v₁, having slope  ¹⁄_(1+√2)  =  −1 + √2.

  3c. If  (cos 2α, sin 2α) = (^√2⁄₂, ^√2⁄₂),  then  2α = ^π⁄₄ = 45°  and  α = ^π⁄₈ = 22.5°. The line in this direction has slope  tan ^π⁄₈  =  ¹⁄_(1+√2) using the tangent half-angle formula. This agrees with part (b).

• 9/1 Spatial and planar symmetry  Text   Notes   ⊞ HW  
       

  1. Symmetries of a rectangle. Let X be a plane rectangle with corners at (2,1), (−2,1), (−2,−1), (2,−1), and let G = Sym(X) be its symmetry group, the set of all (orthogonal) linear mappings L : R² → R² which take X onto itself, for example a horizontal reflection. However, a 90° rotation is not a symmetry of X, since it moves the rectangle to a different (standing) position, not onto itself.
     1. Describe all the symmetries in G, assign them letter names (I, A, B, . . .), and compute their matrices.
        Hint: There are 4 symmetries. Can you show why there cannot be any more?
     2. Make a multiplication table for composition of symmetries. That is, a 4 × 4 table with rows and columns labeled by the symmetries, where the entry in row A and column B is the letter of the composite symmetry C = A ⚬ B defined by C(v) = A(B(v)).
        Hint: Compute the composite by matrix multiplication, then identify the matrix by its letter.
  2. 3D rotation matrices. These are orthogonal linear mappings L : R³ → R³, turning the points of space around an axis.
     1. Write the 3 × 3 matrix for R_x = 90° rotation around the x-axis; and similarly R_y for the y-axis.
        Hint: The matrix [R] = [R(1,0,0) | R(0,1,0) | R(0,0,1)] has column vectors which are the rotations of the standard x,y,z-axis vectors. You must visualize how each axis vector is rotated.
     2. Mutliply these matrices to get a new linear mapping L = R_x·R_y .
     3. Show that λ = 1 is the only real eigenvalue of the above L. Find an eigenvector with L(v) = v. In fact, L is a rotation around the axis v. This is pretty amazing: doing one rotation after the other has the same effect as doing a single rotation!
     4. Mulitply to find that L·L·L = I, the 3 × 3 identity matrix (no motion). Why does this imply that L is a 120° rotation?
  3. Generating twofold-symmetry objects using Mathematica. We saw that there are two ways that an object X in the plane can have exactly two symmetries, Sym(X) = {I, R}:

     (i) R = reflection across an axis (use the y-axis for simplicity);

     (ii) R = 180° rotation.

     1. As in the notes (p.5), for type (i), sketch some asymmetric object X_o on one side of the axis, the reflected object R(X_o) symmetric to it on the other side, and their union X = X_o ∪ R(X_o) which has R as a twofold symmetry. Then do the same for type (ii).
     2. Install Mathematica. Download and run this demo to draw a polygon, its reflected polygon, and their union, as for type (i) above. Experiment with more and different points to get interesting polygons.
     3. Modify the matrix R in the demo to do the same for type (ii).
  ⊞ Soln  

  1. See next week's text, p. 1.

  2a. Denote the x,y,z axes by:

  e₁ = (1,0,0),    e₂ = (0,1,0),    e₃ = (0,0,1).

  According to the Righthand Rule, if you point your thumb along the x-axis and turn ¼ in the direction of your fingers, this takes e₁ to e₁; e₂ to e₃; e₃ to −e₂. Similarly for the y-axis rotation. Thus, the rotation matrices are:

           

  Rx  =

  1   0   0 0 0 −1 0 1  0

  Ry  =

  0   0   1  0 1 0 −1  0 0

  2b. The product matrix is:

           

  L  =  Rx·Ry  =

  0   0   1  1 0 0 0 1  0

  Its characteristic polynomial is p(λ) = det(L−λI) = −λ³ + 1 = −(λ−1)(λ²−λ+1). (Recall the formulas for computing a 3×3 determinant.) The λ₁ = 1 eigenvector v₁ is a fixed axis for L. The orthogonal motion of the perpendicular plane has no fixed directions, since (λ−1) only divides p(λ) once, so it must rotate that plane, and L must be a rotation around v₁.

  2c. Use Gaussian elimination (row reduction) to solve (L−I)v = 0 for v = (x,y,z) to find v = (c,c,c) for any c ∈ R, so we may take v₁ = (1,1,1). Thus L is a rotation around axis v₁

  2d. We can check directly by matrix multiplication that L³ = L·L·L = I. Alternatively, since L cyclically permutes the three coordinate axes e₁→e₂→e₃→e₁, we have L³ = I. Since perfoming the rotation three times gives the idenity, it must be a ¹⁄₃ rotation.

  Another way to see this is by looking at the complex roots of p(λ), which are the complex cube roots of 1, namely λ₂, λ₃ = cos(^2π⁄₃) ± i sin(^2π⁄₃). These are the complex eigenvalues of a ¹⁄₃ rotation.

  3. See the text p. 5.

  ---

• 9/4 Labor Day Holiday, no class
• 9/6 Rectangle symmetries   Text   ⊞ HW  
  1. Work out the symmetry group G = Sym(X) of the rigid square X below, including rotations and reflections. (We call this the dihedral group D₄.) There are 8 symmetries, including the identity.
     
     1. Sketch how each symmetry L(x,y) moves the square, and write its matrix, which consists of the column vectors [ L(1,0) | L(0,1) ]. For example, the 90° counter-clockwise rotation R is [

        0	−1
        1	0

        ].
     2. Give each symmetry a letter: the identity I, the rotations R, R², R³, and reflections A, B, C, D. (Here R² = R·R means doing the 90° rotation twice, i.e. 180° rotation.) Write out the 8×8 multiplication table of G under the composition operation, computing the matrix products and entering each into the table as one of the 8 letters.
        Hint: You can avoid some matrix multiplication by using algebraic reasoning. For example L I = I L = L for all linear mappings L. Since R⁴ = I, you can compute R³R² = R⁵ = RR⁴ = R. If you arrange the letters so that B = AR, C = AR², D = AR³, then you can compute DR² = AR⁵ = AR = C. Another useful relation you can prove is RA = AR³, which lets you switch the order of A's and R's.
  2. Extra Credit: Constructing 3D twofold symmetry objects with Mathematica
     1. Out of wire or cardboard, construct a 3D object with spatial point symmetry. You might make the two halves with different colors to emphasize the construction as X = X₀ ∪ R(X₀). Be creative: make it at least a little different from twisted glasses. Photograph it so the symmetry is clearly visible, and upload to D2L.
     2. Adapt the Mathematica demo from the second daily HW to make a 3D polyhedron with spatial point symmetry, instead of just a 2D polygon. (Your shape should have no other symmetry.) Upload a printout of your input and output, including an output picture of the polyhedron and a list of its defining vertices.
  3. Extra Credit: 3D reflection matrices

     R1  =

     1   0   0  0 1 0 0 0 −1

     R2  =

     1⁄3

     1  −2  −2  −2   1  −2  −2  −2   1

     1. Describe R₁ as a motion of space.
     2. Show that R₂ is an orthogonal twofold symmetry by checking R^T·R = I and R² = I.
     3. Find the eigenvalues of R₂ to describe its motion geometrically.
     4. Multiply L = R₁·R₂. Find the eigenvalues of L to describe it geometrically. Show it is a rotation, and determine its axis. What about its angle?
     5. Explain the dot product formula for the reflection R_p which flips the vector p and fixes the plane orthogonal to p:
        R_p(v)  =  v − 2(^v·p⁄_p·p) p.
        Here v = (x,y,z) is the input vector. Derive the matrices R₁ and R₂ from this.
  4. Extra Credit: Composition of reflections
     1. Do a matrix computation to show that in the plane R², the composition of two flips (reflections) is equal to a rotation by twice the angle between the two lines of reflection. Is the rotation clockwise or counterclockwise?
     2. Using a geometric sketch, explain the analog of the above result for the composition of two mirror-reflections in three-dimensional space R³, across two different mirror-planes. Hint: By choosing coordinates appropriately, you may assume the mirror-planes intersect along the z-axis. Considering the motion of the xy-plane, you can easily picture the two reflections and write their matrices using the two-dimensional case from part (a).
  ⊞ Soln

  1a. The symmetries of the square are:
  
  

  I	Identity mapping, no motion	[  1   0  0 1 ]
  R	90° rotation counterclockwise	[  0  −1  1 0 ]
  R2	180° rotation	[ −1   0  0 −1  ]
  R3	270° = −90° rotation	[  0   1  −1  0 ]
  A	reflection across y-axis	[ −1   0   0   1  ]
  B	reflection across y = x	[  0   1   1   0  ]
  C	reflection across x-axis	[  1   0   0  −1  ]
  D	reflection across y = −x	[  0  −1  −1   0  ]

  
  1b. The composition table (group multiplication table) of G = D₄:
  
  

  ⚬	I	R	R2	R3	A	B	C	D
  I	I	R	R2	R3	A	B	C	D
  R	R	R2	R3	I	D	A	B	C
  R2	R2	R3	I	R	C	D	A	B
  R3	R3	I	R	R2	B	C	D	A
  A	A	B	C	D	I	R	R2	R3
  B	B	C	D	A	R3	I	R	R2
  C	C	D	A	B	R2	R3	I	R
  D	D	A	B	C	R	R2	R3	I

  
  To compute compositions, we can multiply the corresponding matrices, and also use algebraic reasoning as in the Hint.

• 9/8 Ch 2.1 Intro to groups, permutations   Text   ⊞ HW  
  Reading: Terras Ch 2.1 pp. 43-51.    

  1. Continuing the symmetries of the rigid square from the previous HW, consider the dihedral group G = Sym(X) = D₄. We previously described each symmetry by its 2×2 matrix as a linear mapping, and we computed composition of symmetries by matrix multiplication.
     
     1. For each symmetry, write the corresponding permutation of the vertices {1,2,3,4} as shown. For example, the 90° counter-clockwise rotation R is (

        1	2	3	4
        2	3	4	1

        ), where the columns mean vertex 1 moves to vertex 2, i.e. R(1) = 2, and similarly R(2) = 3, R(3) = 4, R(4) = 1. Write the permutation notation for the idenitity I, rotations R, R², R³, and reflections A, B = AR, C = AR², D = AR³.
     2. Show that the square cannot have more than 8 symmetries. Hint: Choose where vertex 1 goes; then vertex 2 must go to one of the neighbors of the previously chosen vertex, etc. In a geometric symmetry, each pair of neighboring vertices (on a side of the square) must to go another pair of neighbors, never to a diagonal pair.
     3. Use permutations instead of matrices to find some of the products in the composition table of G. For a pair of permutations P,Q, find PQ by working out P(Q(1)), . . . , P(Q(4)), and identifying this permutation as one of the known 8 symmetries.
  2. For the equilateral triangle T, work out the symmetry group G = Sym(T) = D₃.
     
     There are 6 symmetries, including the identity: give the matrix for each, and write out the multiplication table.
     Hint: First find the coordinates of its vertices v₂, v₃, which are rotations of v₁ = (1,0).
  3. Triangle symmetries as permutations. Let G = D₃ = Sym(T) be the symmetries of the above triangle.
     1. Write each symmetry in G as a permutation of the vertices {1,2,3} as shown.
     2. Prove that there can be no more than 6 rigid symmetries of X, being as specific as possible.
  4. Extra Credit: There are symmetries of the triangle which are not rigid, but rather squeeze and stretch lengths and bend angles. (These are called homeomorphisms.) For example, perform a one-to-one mapping which stretches the triangle along each radius to fill a unit circle, like a balloon swelling up. Then rotate the circle by an angle α, and finally shrink the circle back down to the triangle. The result of these three mappings is a homeomorphism, a one-to-one and onto mapping which "rotates" the triangle within itself.
     Problem: Draw an illustration of this homeomorphism mapping. Find a formula for the mapping, first in polar and then in rectangular coordinates.
  ⊞ Soln

  1a. The symmetries of the square are:
  
  

  I	Identity mapping, no motion	[  1   0  0 1 ]	(  1   2   3   4  1 2 3 4 )
  R	90° rotation counterclockwise	[  0  −1  1 0 ]	(  1   2   3   4  2 3 4 1 )
  R2	180° rotation	[ −1   0  0 −1  ]	(  1   2   3   4  3 4 1 2 )
  R3	270° = −90° rotation	[  0   1  −1  0 ]	(  1   2   3   4  4 1 2 3 )
  A	reflection across y-axis	[ −1   0   0   1  ]	(  1   2   3   4  2 1 4 3 )
  B	reflection across y = x	[  0   1   1   0  ]	(  1   2   3   4  1 4 3 2 )
  C	reflection across x-axis	[  1   0   0  −1  ]	(  1   2   3   4  4 3 2 1 )
  D	reflection across y = −x	[  0  −1  −1   0  ]	(  1   2   3   4  3 2 1 4 )

  
  1b. Claim: The above 8 are the only symmetries of the square.
  Proof: The two diagonals are the longest line segments in the square, so they must be taken to each other or themselves in any rigid symmetry (preserving distance). Hence any symmetry must also permute their endpoints, the four vertices. Consider how an arbitrary symmetry L moves the vertices 1,2,3,4.

  • Choose L(1) = 1,2,3,4.
  • Given L(1), choose L(2) = L(1) ± 1, one of the two neighbors of L(1).
  • L(3) must be the unique unused neighbor of L(2)
  • L(4) must be the unique unused neighbor of L(3).

  
  These four choices determine L completely, and give at most 4×2×1×1 = 8 choices for L. Thus there cannot be any other symmetries than the 8 we list above.

  1c. To compute compositions, we can multiply the corresponding matrices, or compose permutations. For example, doing A after R:

  A ⚬ R  =  (

  1	2	3	4
  2	1	4	3

  ) ⚬ (

  1	2	3	4
  2	3	4	1

  )   =   (

  1	2	3	4
  1	4	3	2

  )   =   B,

  since R(1) = 2, R(2) = 3, R(3) = 4, R(4) = 1 and A(1) = 2, A(2) = 1, A(3) = 4, A(4) = 3, so:

  A(R(1)) = A(2) = 1  ,  A(R(2)) = A(3) = 4  ,  A(R(3)) = A(4) = 3  ,  A(R(4)) = A(1) = 2.

  Note how the output of R becomes the input of A.

  2 & 3. The coordinates of the vertices are given by repeatedly applying the rotation symmetry R = Rot_2π/3 to v₁:

  v₁  =  (1,0)
  v₂  =  (cos(θ), sin(θ))  =  (⁻¹⁄₂ , ^√3⁄₂)  for  θ = 120°
  v₃  =  (cos(θ), sin(θ))  =  (⁻¹⁄₂ , ^−√3⁄₂)  for  θ = −120°.

  The symmetries of the triangle are:
  
  

  I	Identity mapping, no motion	[  1   0  0 1 ]	(  1   2   3  1 2 3 )
  R	120° rotation Rot2π/3	[ −1/2  −√3/2 √3/2 −1/2 ]	(  1   2   3  2 3 1 )
  R2	240° rotation Rot4π/3	[ −1/2   √3/2 −√3/2 −1/2 ]	(  1   2   3  3 1 2 )
  A	reflection across x-axis	[  1   0   0  −1  ]	(  1   2   3  1 3 2 )
  B	reflection across y = −√3 x	[ −1/2   −√3/2 −√3/2 1/2 ]	(  1   2   3  3 2 1 )
  C	reflection across y = √3 x	[ −1/2   √3/2 √3/2 1/2 ]	(  1   2   3  2 1 3 )

  
  Note that A(v₁) = v₁, B(v₂) = v₂, C(v₃) = v₃.

  Could there be other symmetries of T? No: The three sides of the triangle are the only segments of length 1, and any rigid symmetry S must take these longest segments to each other, so it takes their endpoints (the three vertices) to each other. Now, any element of G can be defined by its permutations of the three vertices, so G ⊂ S₃; but |S₃| = 3! = 6, so there cannot be more elements of G than the 6 above.

  ---

• 9/11 Ch 2.1 Abstract groups   ⊞ HW  
  Reading: Terras Ch 2.1 pp. 43-51.    

  1. Terras Ex 2.1.6 p. 49. Which of the given operations define groups, satisfying the three required properties?
  ⊞ Soln
  1a. Yes, (Z, +) is a group, with identity element e = 0, and inverses a⁻¹ = −a.

  1b. No, (Z, ×) is a not a group. It has identity e = 1, but it does not possess inverses inside the group. For example 2⁻¹ = ½ is not in Z.

  1c. Yes, (R, +) is a group.

  1d. (R, ×) is almost a group, since it has e = 1 as identity, and most elements have inverse a⁻¹ = ¹⁄_a in the group; but a = 0 does not have an inverse, so the group property fails.

  1e. Yes, (R−{0}, ×) is a group, with identity element e = 1, and inverses inverse a⁻¹ = ¹⁄_a in the group for all a ∈ R−{0}

  1f. (Z−{0}, ×) is not a group, since most elements do not have inverses inside the group. (Again, 2⁻¹ = ½ is not in Z−{0}.)

• Hand-In HW 1 due Wed 9/20. Diagram.
• 9/13 Ch 2.2 Visualizing groups, Cayley graphs   ⊞ Text   Notes  
  • For an abstract group G, there is a general way to produce an object X which has G as its symmetry group:
    G  ≅  Sym(X).
    This X is a combinatorial graph, a set of vertices connected by arrows (directed curves), also known as nodes in a network. A graph is defined solely by which vertices are connected to which others; it does not contain any geometric data about length, angle, etc.
  • Cayley graph: Suppose the group G is generated by multiplying elements a,b, . . . (and their inverses). Define the graph X to have a vertex for every g ∈ G, and an a-colored arrow from each g to ga, b-colored arrow from g to gb, etc: g

    a

    →

    ga   ,   g

    b

    →

    gb   ,    . . . .
    This graph encodes the multiplication table of G. To multiply g·h, locate g, h, and the identity e as vertices of X. Follow a sequence of arrows from e to h; the sequence of arrow labels shows how to write h in terms of the generators a,b, . . . . Finally, start from g and follow the same sequence of labeled arrows to end at the vertex gh.
  • Example:  G = D₃ = ⟨r,a⟩ = {e, r, r², a, ar, ar²}  with  r³ = a² = e  and  ra = ar⁻¹. The Cayley graph X is: Here each red double arrow denotes two opposite a-colored arrows.
    We can use the graph to multiply elements such as:  g · h  =  r² · ar.
    • Starting at e, follow the sequence of arrows colored by the generator factors gh = r·r·a·r:
      e

      r

      →

      r

      r

      →

      r²

      a

      →

      ar

      r

      →

      ar².

    • The endpoint is the product:  r²·ar = ar².
  ⊞ HW  
  Reading: Terras Ch 2.2 pp. 52-56.    

  1. Draw another Cayley graph of G = D₃, this time with respect to the reflection generators a and b = ar. That is, the vertices are the same, but the two types of arrows are  g →^a ga  and  g →^b gb .
  2. Consider the cyclic group C₆ = {e, c, . . ., c⁵}, where c is a 60° rotation, so that c⁶ = e. Draw two Cayley graphs of G with respect to two systems of generators.
     1. With respect to the single generator c.
     2. With respect to the two generators r = c² and a = c³. Compare this to the first Cayley graph of D₃. They are similar, but there is one difference.
     3. Draw the graph in (b) as a decorated triangular prism. How do the generators r,a act geometrically?
  ⊞ Soln  

  1. Recall ra = ar², r³ = a² = e.

  2a. The Cayley graph of C₆ = ⟨c⟩ is just an oriented 6-cycle, with only c-arrows going counterclockwise (or clockwise).

  2b. The Cayley graph of C₆ = ⟨r=c², a=c³⟩ is the same as that of D₃ = ⟨r,a⟩, except the three-cycles of r-arrows have the same orientation (rather than opposite).

  2c. In the geometric model of C₆ as the symmetries of a triangular prism, r again acts as a ¹⁄₃ rotation around a horizontal axis, but a acts as a reflection across a vertical plane. These two mappings move orthogonal subspaces because of the Cartesian product structure of C₆ ≅ C₃ × C₂.

• 9/15 Ch 2.2 More groups. Ch 3.2 Isomorphisms, Cayley's Theorem.  Old Notes 1 2   ⊞ Text  
  • Reading: Terras Ch 2.3 pp. 56-64; Ch 3.2 p. 89.
  • Isomorphism of groups means a one-to-one correspondence between two groups, T : G → G', each g ∈ G corresponding to a unique g' = T(g) ∈ G', such that T respects the group operation: T(gh) = T(g)T(h) for all g,h ∈ G. (Here gh is multiplied in G, but g'h' = T(g)T(h) is multiplied in G'.)
    • An isomorphism transforms the multiplication table of G into that of G', and the same with their Cayley graphs.
    • If there exists an isomorphism between G and G', we say they are isomorphic and write G ≅ G'.
    • We think of isomorphic groups as the "same" group denoted two different ways, with the isomorphism changing one set of labels for another.
  • Cyclic group is isomorphic to modular addition: There is an obvious isomorphism between the cyclic group C_n = {e, c, c², . . . , cⁿ⁻¹} with cⁿ = c⁰ = e, and the numbers modulo n under the addition operation, Z_n = {0, 1, 2, . . . , n−1 mod n} with n = 0 mod n.
    T : C_n → Z_n ,   T(cⁱ) = i mod n.
    This respects the group operations because:
    T(cⁱc^j)  =  T(c^i+j)  =  i + j  =  T(cⁱ) + T(c^j).
    Here cⁱc^j are combined (multiplied) in the first group, while T(cⁱ) + T(c^j) are combined (added) in the second group.
  • Non-isomorphic groups: We can have groups with the same number of elements which are non-isomorphic, i.e. there is no possible isomorphism between them.
    • The dihedral group of triangle symmetries is not isomorphic to the cyclic group of six elements: D₃ ≇ C₆.
    • Proof: Note that in D₃ we have non-commuting elements ra ≠ ar, while in C₆ all elements commute, cⁱc^j = c^jcⁱ. Now if there were an isomorphism T : D₃ → C₆, we would have  T(r)T(a) = T(ra) ≠ T(ar) = T(a)T(r), which would give a non-commutative multiplication in C₆. This contradiction means there can be no such T.
      Another reason the groups cannot be isomorphic: the cyclic group is generated by one element, but no single element generates the dihedral group.
  • Groups of matrices and permutations
    • When we represent elements of an abstract group G as linear mappings of the plane, i.e. matrices in GL₂(R), this means we have a set G' of matrices which under matrix multiplication forms a group isomorphic to the original G. That is, G ≅ G' ⊂ GL₂(R).
    • Similarly, when we respresent G as permutations in the symmetric group S_n, we have a set G'' of permutations which under composition are isomorphic to G: that is, G ≅ G'' ⊂ S_n .
  • Recall the Cayley graph X = X(G,S) of a group G with respect to a set of generators S. A graph symmetry of X is a permutation of the vertices, a bijection F : G → G, such that each a-colored edge h →^a aa is taken to vertices also connected by an a-colored edge, F(h) →^a F(ha), i.e. F(ha) = F(h) a. Since F permutes the elements of G = {e, g₁, . . . , g_n−1}, where n = |G|, we may consider F ∈ S_n, and Sym(X) ⊂ S_n.
  • Each g ∈ G corresponds to a permutation F_g : G → G with F_g(h) = gh;  that is, multiplying by g on the left permutes around the n elements h ∈ G. This is a graph symmetry, since it takes h →^a ha to gh →^a gha. Note that F_g multiplies each vertex on the left by g, while the a-colored arrows multiply each vertex on the right by a: acting on opposite sides, these operations don't interfere with each other.
  • Cayley's Theorem: The symmetries of the Cayley graph X are isomorphic to the group:  Sym(X) ≅ G.   ⊞
    Proof.
    • I claim the mappings F_g : G → G are the only graph symmetries of X. Let F : G → G be any graph symmetry, and g = F(e); then I claim F = F_g. First, F(e) = g = F_g(e). Now, suppose we know F(h) = F_g(h) for some h. Then by definition of a graph symmetry, the arrow h →^a ha is taken to an a-arrow by both F and F_g, namely F(h) →^a F(ha) and F_g(h) →^a F_g(ha). But since these arrows begin at the same vertex F(h) = F_g(h), and there is only one a-arrow from this vertex, the arrows must also end at the same vertex: F(ha) = F_g(ha). Thus, the zone of agreement between F(h) and F_g(h) spreads out inductively from h = e to include the whole graph, so F = F_g.
    • Now consider the mapping T : G → S_n given by T(g) = F_g , taking each group element g to the permutation of the n group elements given by left multiplication by g. Then T is a homomorphism, meaning it respects group multiplication:
      F_g1g2(h)  =  g₁g₂h  =  g₁(g₂h)  =  F_g1(F_g2(h))  =  (F_g1∘ F_g2)(h),
      which means T(g₁g₂) = T(g₁) ∘ T(g₂). (Recall that composition ∘ is the group operation on permutations in S_n, or in any symmetry group.)
    • Furthermore, T is injective (one-to-one): if T(g₁) = T(g₂), this means F_g1 = F_g1, so that g₁ = F_g1(e) = F_g2(e) = g₂. Thus, T never takes two different elements g₁ ≠ g₂ to the same permutation in S_n.
    • Now, T is an injective homomorphism, but not an isomorphism because it is not onto. Rather, it takes G to a subset G' ⊂ S_n inside the permutations, and G' is isomorphic to G:
      G  ≅  G'  =  {F_g for g ∈ G}  =  Sym(X) ⊂ S_n,
      which is what we wanted to prove.
  • Example:  Recall the Cayley graph of G = D₃ = {e, r, r², a, ar, ar²} with generators S = {r,a}, where r³ = a² = e  and  ra = ar⁻¹. The Cayley graph X = X(G,S) is: Here each red double arrow denotes two opposite a-colored arrows.
  • The symmetry group of the Cayley graph of G is isomorphic to the original group: G ≅ Sym(X). Although the graph is not geometric, we can choose a nice drawing of X as a triangular prism, as above, and see G as the geometric symmetries of this solid, obtaining a new geometric representation of G.
    • r and r² are ¹⁄₃ rotations around a horizontal axis (clockwise and counterclockwise);
    • a is a ¹⁄₂ rotation around a vertical axis;
    • the other two elements b, c are ¹⁄₂ rotations around axes which bisect the two red edges at the bottom of the prism.
    These mappings preserve the blue and red arrows; but note that reflection across a vertical plane would reverse the blue arrows, so it is not a symmetry of the decorated prism (with arrows). We can also say G is the group of only rotational symmetries of the undecorated prism.
  ⊞ HW  
  1. Consider the cyclic group C₆ = {e, c, c², . . . , c⁵}, with c⁶ = e, the rotations of a hexagon. Also consider the group (Z₆, +), the integers modulo 6 under the modular addition operation: that is, Z₆ = {0, 1, 2, . . . , 5} with 6 = 0 mod 6, like on a 6-hour clock (for example 4 + 5 = 9 = 3 mod 6).
     1. Give an explicit isomorphism T : C₆ → Z₆. Write the multiplication table of each, and observe how T takes every entry in the first table to the corresponding entry in the second.
     2. Show that we get another isomorphism T defined by T(cⁱ) = −i (mod 6). Use this T to transform the multiplication table of C₆ into that of Z₆, but with the elements listed in a different order.
  2. Let X be the Cayley graph of C₆ with respect to the single generator S = {c}.
     1. Draw the group elements and graph arrows in a hexagon, as on a 6-hour clock.
     2. Multiplying by g = c² on the left gives a symmetry F_g of the graph, a permutation of the 6 elements of the group: F_g(h) = gh. Write this permutation in 2-line notation:

        (

        e   c   c2   ···   c5   Fg(e)   Fg(c)   Fg(c2)   ···   Fg(c5)

        ).

        For example, F_g(c³) = g c⁵ = c² c⁵ = c⁷ = c.
     3. What is geometric motion of the above graph symmetry F_g on the hexagon picture?
     4. How many elements are in the symmetric group S₆ of all possible permutations of 6 objects? (The notation for the 6 objects is irrelevant: you can write them as e, c, . . . , c⁵ or as 0, 1, . . . , 5, or as 1, 2, . . . , 6.) Why don't the graph symmetries Sym(X) ⊂ S₆ produce all possible permutations?
  ⊞ Soln  

  1a. The obvious isomorphism is defined by T(cⁱ) = i (mod 6), so that T(e) = 0, T(c) = 1, . . . , T(c⁵) = 5. The group tables of C₆ and (Z₆, + ) are:

  ·  e   c    c2   c3   c4   c5 e e c   c2   c3 c4 c5 c c   c2   c3   c4   c5 e   c2   c2   c3   c4   c5 e c   c3   c3   c4   c5 e c   c2   c4   c4   c5 e c   c2   c3   c5   c5 e c   c2   c3   c4

  ·    0   1   2   3   4   5  0 0 1 2 3 4 5 1 1 2 3 4 5 0 2 2 3 4 5 0 1 3 3 4 5 0 1 2 4 4 5 0 1 2  3 5 5 0 1 2 3 4

  After writing the first table, I wrote the second via find-and-replace, relabeling each cⁱ as i.

  1b. Surprisingly, there is another isomorphism between C₆ and Z₆. The mapping T(cⁱ) = −i (mod 6) gives:

  T(e) = 0,   T(c) = 5,   T(c²) = 4,   T(c³) = 3,   T(c²) = 2,   T(c⁵) = 1.

  For example, T(c²) = −2 = −2 + 6 = 4 (mod 6). Thus T is a bijection (a one-to-one correspondence).

  Furthermore, T respects the group operations because:

  T(cⁱ c^j) = T(c^i+j) = −(i+j) = (−i) + (−j) = T(cⁱ) + T(c^j).

  That is, T takes the multiplication operation on C₆ to the addition operation on Z₆.

  Therefore, T satisfies both requirements of an isomorphism.

  2a. The Cayley graph can be drawn as regular hexagon with arrows pointing clockwise, each labeled with the generator c.

  2b. The multiplication by g = c² gives the following permutation of C₆:

  (

  e   c   c2   c3   c4   c5   c2   c3   c4   c5   e   c

  ).

  Note that the second row is identical to the c² row of the above multiplication table.

  We may relabel this as a permutation of Z₆ = {0,1,2,3,4,5}:

  (

  0   1   2   3   4   5   2   3   4   5   0   1

  ).

  2c. The above symmetry moves each vertex two steps counterclockwise (or clockwise, depending how you drew the vertices). As a geometric symmetry, this is a ⅓ rotation.

  2d. The possible permutations are all bijections P : {1,2,...,6} → {1,2,...,6}. They are constructed by 6 choices for P(1); 5 choices left for P(2), which can be anything but P(1); 4 choices left for P(3), which can be anything but P(1) or P(2); etc. Combining these choices gives 6! = 6 × 5 × 4 × 3 × 2 × 1 = 720 possible permutations in S₆.

  Only 6 of these are in Sym(X), because a graph symmetry must not only permute the vertices (group elements), but also move arrows to arrows. This restricts symmetries to be rotations only.

  ---

• 9/18 & 20 Ch 2.2 Standard groups. Ch 2.3 Tet⁺, 3D symmetry groups. ⊞ Notes  
  • Some standard families of groups which we will see often
    • Cyclic group C_n = {e, r, r², . . . , rⁿ⁻¹}, with rⁿ = e, order |G| = n
      Rotational symmetries of an n-gon (excluding reflections)
    • Dihedral group D_n = {e, r, r², . . . , rⁿ⁻¹, a, ar, . . . , arⁿ⁻¹}, with rⁿ = a² = e and ar = r⁻¹a, order |G| = 2n
      Geometric symmetries (rotations and reflections) of an n-gon
    • Symmetric group S_n = { all permutations P  =  (

      1	2	···	n
      P(1)	P(2)	···	P(n)

      ) }, order |G| = n!
      Symmetries of an unstructured set {1, 2, . . . , n}.
    • General linear group GL_n(R)  =  { invertible n×n matrices [L] }  =  { invertible linear mappings L : Rⁿ → Rⁿ }
      Symmetries of the n-dimensional vector space Rⁿ, preserving vector addition & scalar mult: L(av+bw) = a L(v) + b L(w).
    • Orthogonal group O_n  =  { M ∈ GL_n(R) with M^T M = I }
      Geometric symmetries of n-space Rⁿ, preserving lengths and angles
    • Modular addition group Z_p = {0, 1, . . . , n−1 mod n}, under the clock-addition operation with n = 0 mod n
    • Modular multiplication group Z_p^× = {1, 2, . . . , p−1} for p a prime number, under the clock-multiplication operation
    • Finite general linear group GL_n(Z_p)  =  { invertible n×n matrices with entries in Z_p }, for p a prime number
      Symmetries of the vector space Z_pⁿ with coordinates in Z_p
  • Platonic solid groups
    
    • Solids: Tetrahedron, Cube, Icosahedron
    • Geom symmetery groups G = Tet, Cub, Ico.
    • Rotations only: G = Tet⁺, Cub⁺, Ico⁺.
  • The tetrahedron is a pyramid with a triangular base and three triangular sides (all equilateral).
    
    Here it is drawn inside the cube of points (x,y,z) with coordinates −1 ≤ x,y,z ≤ 1. The 4 vertices all have an even number of −1's:
    v₁ = (1,1,1),   v₂ = (1,−1,−1),   v₃ = (−1,−1,1),   v₄ = (−1,1,−1).
    • Let G = Tet⁺ be the group of rotational symmetries of the tetrahedron (excluding reflections).
    • Some obvious symmetries are the ⅓ rotations R_i around the axis given by the vector v_i. Each of these rotations has R³ = I, so that R² = R⁻¹. (Since there are two inverse ⅓ rotations around each axis, we use the right-hand rule to determine which rotation to call R_i.)
    • In fact, there is a total of 12 symmetries: the identity and the 8 rotations mentioned, as well as 3 as yet unknown rotations which we denote A, B, C:
      G  =  { I, R₁, R₁⁻¹, R₂, R₂⁻¹, R₃, R₃⁻¹, R₄, R₄⁻¹, A, B, C }.

    • The ⅓ rotations generate G. Actually, it is enough to repeatedly multiply just R₁ and R₂ to produce all the symmetries: S = {R₁, R₂} is a generating set.
  ⊞ HW  
  1. Write the rotations R₁, . . . , R₄ and their inverses as permutations of the 4 vertices, in 2-line notation and also cycle notation.
  2. Write these rotations as 3×3 matrices.
     Hint: The rotations move the x,y,z axes to each other, either directly or flipped over, so the nonzero matrix entries are all ±1. For example R₂ is the right-handed ⅓ rotation around the axis:
     v₂  =  (1,−1,−1)  =  (1,0,0) + (0,−1,0) + (0,0,−1).
     This motion of space turns each of the x, y, z axis components of v₂ around to the next one:
     (1,0,0) → (0,−1,0) → (0,0,−1) → (1,0,0).

     Thus, since R(−v) = −R(v):

     R₂(1,0,0) = (0,−1,0),     R₂(0,1,0) = (0,0,1),     R₂(0,0,1) = (−1,0,0).
     Writing these as column vectors, we get the rotation matrix:

     [R2]   =

     0   0 −1  −1 0 0  0 1 0

     .

     The inverse R₂⁻¹ cycles the three components of v₂ in the reverse order, and its matrix is the transpose of R₂.
  3. Compose permutations to find the permutation of the mystery symmetry A = R₁R₂⁻¹. Can you picture it geometrically from its permutation?
  4. Multiply matrices to re-compute A = R₁R₂⁻¹, and verify that this gives the permutation above.
  5. For the matrix of A, compute its eigenvector with λ = 1 to find its rotational axis. (That is, solve the system of linear equations Av = v for v = (x,y,z).) What is the angle of this rotation?
  6. Find the remaining two elements B and C by multiplying appropriate generators.
  7. Give a combinatorial argument in terms of permutations to show that there cannot be any other rotational symmetries of the tetrahedron. Keep in mind that since v₁, v₂, v₃ are arranged clockwise around the front triangle of the original tetrahedron, they must also be arranged clockwise around some triangle in any rotated image. (A reflection would rearrange them counter-clockwise.)
  8. Draw the Cayley graph X(G,S) for the two generators S = {R₁, R₂}, having 12 vertices labeled with the elements of G. From each vertex P ∈ G, there is a blue arrow P→V to the vertex V = PR₁ ∈ G, and a red arrow P→W = PR₂. (Also each P has P←PR₁⁻¹ and P←PR₂⁻¹ pointing toward it.) Compute the needed group multiplications using matrices or permutations. Mathematica or other software might be helpful.
     Hint: Start with a large blue triangle with vertices I, R₁, R₁⁻¹, and draw red arrows inward from there.
  9. Extra Credit: Read about the Cuboctahedron, a polyhedron with 12 vertices, 6 triangular faces, and 6 square faces. Copy a picture of a cuboctahedron, and label its vertices to correspond to the group elements, and its edges to correpond to the red and blue Cayley graph arrows.
     Explain why G is the symmetry group of this polyhedron by relating it to the tetrahedron.
  Soln1   Soln2  
• 9/22 Ch 2.4 Subgroups.  Notes   ⊞ HW  
  Reading: Terras Ch 2.4 pp. 64-72.

  1. Recall that a subgroup H is a group inside a larger group G, sharing the same operation. Find all subgroups of the following groups G, and arrange them into a chart showing groups on top of their included subgroups.
     1. G = D₃ = {e, r, r², a, ar, ar²}, the dihedral group with r³ = a² = e, and ra = ar⁻¹.
     2. G = C₆ = {e, r, r², . . . , r⁵}, the cyclic group with r⁶ = e.
  2. Consider the set G of all invertible (one-to-one and onto) functions f : R₊ → R₊, where R₊ denotes the positive real numbers x > 0. For example, the function f(x) = e^x − 1 takes positive numbers to positive numbers, and it has inverse function f⁻¹(x) = ln(x+1) also taking positive to positive, so f is in G.
     1. Show that G is a group under the composition operation. (In fact, it is the symmetries of the unstructured set X = R₊.)
     2. Consider the functions e(x) = x, s(x) = x², r(x) = √x. Does H = {e, s, r} form a subgroup of G?
  3. In the group G = D₃ = {e, r, r², a, ar, ar²}, solve the following equations for x ∈ G.
     Hint: Look at the diagonal of its multiplication table.
     1. x² = e
     2. x² = a
     3. x²a = ar²
  ⊞ Soln  

  1a. The subgroups are: H = D₃ itself (since a subset is allowed be all of a given set); containing the cyclic subgroups H = {e, r, r²}, {e, a}, {e, ar}, {e, ar²}; and the trivial subgroup H = {e}.
  It is easy to see that putting any extra element into one of the above subgroups generates one of the others, so the list is complete.

  1b. The subgroups are: the whole cyclic group H = C₆; the cyclic subgroups H = {e, r², r⁴}, H = {e, r³}; and the trivial subgroup H = {e}.

  2a. Like all symmetry groups, G = Sym(R+) is an abstract group. It has a closed operation, since composition of two such functions gives the same kind of function; composition is always associative; the function e(x) = x is the group identity element; and the inverse function is the group inverse.

  2b. The functions in H = {e, s, r} satisfy ee = e, er = re = r, es = se = s, rs = sr = e, as they should for a subgroup. But there is one thing missing: s² and r² are not in H, so the operation is not closed (or not defined within the given set), and it cannot be a (sub)group.

  3a. The diagonal of the multiplication table shows e² = e and a² = (ar)² = (ar²)² = e. These are all the solutions to x² = e.

  3b. The only elements g² appearing on the diagonal of the multiplication table are e, r, r², so there is no solution to x² = a.

  3c. Solving x²a = ar² gives

  x²  =  ar²a⁻¹  =  ar²a  =  a²r⁻¹r²  =  r.

  Solving x² = r as above gives x = r².

  ---

• 9/25 Subgroups & symmetries   ⊞ Text   Notes  
  • Consider the dihedral group of order 8:
    G  =  D₄  =  {e, r, r², r³, a, b = ar, c = ar², d = ar³ = ra},
    where r⁴ = a² = e. (I have written the elements with small letters instead of the previous capital letters.)
  • G = Sym(X), where X is a square in the plane.

    

  • We can split G into conjugacy classes K(x) = {gxg⁻¹ for g ∈ G}:
    K(e) = {e} (identity),   K(r) = {r²} (½ rotation),   K(r) = {r, r³} (¼ rotations),
    K(a) = {a,c} (reflections across sides),   K(b) = {b,d} (reflections across diagonals).
    Note that K(x) = K(y) for any y ∈ K(x); that is, we can choose any element of a class as its representative.
  • The center Z(G) = {e,r²} contains exactly those elements with K(x) = {x}, i.e. gxg⁻¹ = x for all g.
  • Inclusion diagram of the subgroups H ⊂ G:

    

  • Every subgroup H ⊂ G is a symmetry group H = Sym(X_H) where X_H = X^~ is a decorated version of X with fewer symmetries. We can construct X_H = ∪_h∈H hX_e, where X_e is an asymmetric decoration of X which removes all symmetry.

    

  ⊞ HW  
  1. A group G is commutative or abelian whenver ab = ba for all a,b ∈ G. Try to recall all the groups we have defined, and classify them as abelian or non-abelian.
  2. An element z ∈ G is central whenever it commutes with all other elements: zg = gz for all g ∈ G. The center Z(G) is the set of all central elements of G. Prove that Z(G) is always a subgroup of G. Hint: Which properties must be checked?
  3. Explicitly determine the center Z(G) for the following groups:
     1. The cyclic group C_n.
     2. The dihedral group D₄ (symmetries of the square).
     3. The tetrahedral rotation group Tet⁺ from the previous HW.
     4. Extra Credit: The group of invertible 2×2 matrices GL₂(R).
        Hint: It's not just the identity matrix I. There is a slightly larger family of matrices which commute with all others.
  ⊞ Soln  

  1. The only abelian groups we have mentioned so far are:

  • The cyclic groups C_n ≅ (Z_n, + ) C_∞ ≅ (Z, + )
  • The symmetries of the rectangle {I, A, B, C}, where A² = B² = I and AB = BA = C.
  • The additive reals (R, + ) and multiplicative non-zero reals R^×

  2. Proposition: For any group G, its center Z(G) is a subgroup.
  Proof: To show that the center

  Z(G) = {c ∈ G with cg = gc for all g ∈ G}

  is a subgroup, we must show that it is closed under multiplication and inverses.

  To check this, suppose c, c' ∈ G, which means for any g ∈ G, we assume cg = gc and c'g = gc'. Then:

  (cc')g = c(c'g) = c(gc') = (cg)c' = (gc)c' = g(cc'),

  which means cc' ∈ Z(G). Also, cg = gc implies:

  c⁻¹(cg)c⁻¹ = c⁻¹(gc)c⁻¹.

  Simplifying the left and right sides gives gc⁻¹ = c⁻¹g, which means c⁻¹ ∈ Z(G). Hence Z(G) is a subgroup.

  3a. Z(C_n) = C_n.

  3b. Z(D₄) = {e, r²}, where r² is a ½ rotation. For each other element, it is easy to find another element which does not commute with it.

  3c. Z(Tet⁺) = {I}, the trivial subgroup. Again, all other elements fail to commute with something.

• 9/27 Ch 2.5 Cyclic groups.  Notes 1 2   ⊞ Text  
  • Cyclic group
    • C_n = ⟨a⟩ ={e, a, a², . . . , aⁿ⁻¹} with aⁿ = e
    • Isomorphism T : C_n → (Z_n, + ), T(aⁱ) = i mod n
    • aⁱ = a^j   ⇔   i = j mod n   ⇔   n | (i−j)
  • Main Theorem of Cyclic Subgroups Terras Thm 2.5.1 (p. 77)
    Let G = C_n and H ⊂ G any subgroup.
    1. H is cyclic: H = ⟨b⟩ for some b = a^m
    2. |H| = |b| = k is a divisor of n (i.e. k | n)
    3. For any divisor k | n, there is a unique subgroup with |H| = k, which is H = ⟨a^n/k⟩.
    4. For any ℓ, we have identical subgroups ⟨a^ℓ⟩ = ⟨a^m⟩ for m = gcd(ℓ,n).
  • Proof of (1). Given any subgroup H ⊂ G = ⟨a⟩, let m = min{ℓ > 0 with a^ℓ ∈ H}. Now let a^ℓ be any element of H, and use division-with-remainder to write n = km + r for 0 ≤ r < m. Then a^ℓ = a^km a^r, so
    a^r = a^ℓ((a^m)^k)⁻¹ ∈ H,
    since a^ℓ, a^m ∈ H, and H is closed under multiplication and inverses.
    Now, m is the smallest positive integer with a^m ∈ H, but a^r ∈ H with 0 ≤ r < m. Thus r can only be zero.
    Therefore a^ℓ = (a^m)^k ∈ ⟨a^m⟩, which shows H ⊂ ⟨a^m⟩, and clearly ⟨a^m⟩ ⊂ H, so H = ⟨a^m⟩.
  • Q: Which a^r generate the entire group C_n?
    A: Exactly the r which are relatively prime to n:   Z_n^×  =  { r mod n such that gcd(r, n) = 1 }.
    These exponents form a group under multiplication mod n.
    The number of relatively prime elements is called the Euler phi-function:   φ(n) = #Z_n^×
  • Symmetries of C_n
    • An automorphism of a group G is an isomorphism to itself, T : G → G with T(gg') = T(g) T(g').
      This is an invertible mapping of G to itself which preserves the group multiplication structure, an algebraic symmetry (rather than geometric).
    • The set of all automorphisms of G form a new group Γ = Sym(G).
    • For G = C_n, we have
      Γ  =  Sym(C_n)  ≅  (Z_n^×, × )
      the relatively prime elements under multiplication mod n.
    • For each such r, there is an automorphism T_r(g) = g^r.
      Composition of automorphisms corresponds to multiplication in Z_n:
      T_r(T_s(g))  =  T_rs(g)   for   g = a^ℓ.

  ⊞ HW  
  Reading: Terras Ch 2.4 pp. 64-72, Ch 2.5 pp. 72-80.
  

  1. Consider the cyclic group G = C₂₄ = ⟨c⟩ = {e, a, a², . . . , a²³} with a²⁴ = e.
     1. Write all the elements of each cyclic subgroup H = ⟨a^m⟩
     2. Put the subgroups ⟨a^m⟩ in a diagram showing inclusion (with G on top and {e} on the bottom).
     3. Experiment to verify that there are no other subgroups of G besides the cyclic ones. Try adding some other element a^ℓ to one of the cyclic subgroups, and show that this generates one of the other cyclic subgroups (perhaps the whole G).
     4. Verfy that for each ℓ = 1, . . . , 24, we have ⟨a^ℓ⟩ = ⟨a^m⟩ for m = gcd(ℓ,n).
  2. Generators and automorphisms of G = C₂₄
     1. Find all the generators of G: the elements a^r with G = ⟨a^r⟩. These form the set Z₂₄^×.
     2. Recall that the Euler phi-function φ(n) gives the number of generators for each C_n. Verify that your result in above agrees with the following general formula: if n has prime decomposition n = p₁^ℓ₁p₂^ℓ₂ ··· , then
        φ(n)  =  (p₁−1) p₁^ℓ₁−1 (p₂−1) p₂^ℓ₂−1 . . .

     3. Since r = 5 ∈ Z₂₄^×, we have the automorphism (algebraic symmetry)
        T₅ : G → G   defined by   T₅(g) = g⁵   or   T₅(a^ℓ) = a^5ℓ.
        Show that this mapping preserves group multiplication:

        T₅(gh)  =  T₅(g) T₅(h)   for any   g = a^ℓ,  h = a^m.

        Draw a diagram of the T₅ automorphism, starting with the 24 elements g = a^ℓ in a circle, and an arrow connecting each g with T₅(g). How does the diagram show that T₅ is one-to-one and onto?
        Given the above diagram for T₅, how would you draw the diagram of the inverse automorphism T₅⁻¹? Looking at this inverse diagram, deduce which of the other symmetries T_r is equal to T₅⁻¹?
  3. Extra Credit: Prove that for a general cyclic group C_n and any m, we have ⟨a^m⟩ = ⟨a^d⟩ for d = gcd(m,n).
     Hint: Assume Bezout's Lemma (Thm 1.5.2 p. 23): For integers m,n, we have
     gcd(n,m)  =  min { am + bn, where a,b ∈ Z and an + bm > 0 }.
     If you feel ambitious, also give the proof of Bezout's Lemma.
  ⊞ Soln  

  1a,b. The diagram of subgroups of C₂₄, written in terms of the isomorphic group (Z₂₄, + ), is on Terras p. 78: each ⟨m⟩, with m a divisor of 24, corresponds to H = ⟨a^m⟩ ⊂ C₂₄, a subgroup with ²⁴⁄_m elements.

  1c. For example, if we start with

  H = ⟨a⁶⟩ = {e, a⁶, a¹², a¹⁸}

  and multiply by a new element a¹⁰, we generate:

  a¹⁰, a¹⁶, a²², a²⁸ = a⁴,
  a²⁰, a², a⁸, a¹⁴,
  a⁶, a¹², a¹⁸, e.

  These are precisely the elements of the cyclic subgroup ⟨a²⟩ so ⟨a⁶, a¹⁰⟩ = ⟨a²⟩.

  More generally, if we start with a cyclic subgroup in ⟨a^m⟩ ⊂ C₂₄ for m | 24, and add a generator a^ℓ, we get:

  ⟨a^m, a^ℓ⟩  =  { a^{sm + tℓ} for s,t ∈ Z }  =  ⟨a^d⟩   for   d = gcd(m,ℓ).

  This method can be proven in general using Bezout's Lemma described above. See Terras Ch 2.5 pp. 76-77.

  1d. We can verify that ⟨a^ℓ⟩ = ⟨a^d⟩ for d = gcd(ℓ, 24) by checking each ℓ which are not divisors of 24. For example,

  ⟨a¹⁵⟩   =   {e, a¹⁵, a³⁰ = a⁶, a²¹, a³⁶ = a¹², a²⁷ = a³, a¹⁸, a³³ = a⁹ }   =   ⟨a³⟩,

  where 3 = gcd(15, 24).

  2a,b. The generators are those ⟨a^r⟩ with gcd(24, r) = 1, namely r = 1, 5, 7, 11, 13, 17, 19, 23. These 8 generators are consistent with φ(24) = φ(2³3) = (2−1)2³⁻¹ (3−1) = 8.

  2c. We check that T₅ preserves multiplication:

  T₅(a^ℓa^m) = T₅(a^ℓ+m) = a^5(ℓ+m) = a^5ℓ a^5m = T₅(a^ℓ) T₅(a^m).

  2d. The automorphism T₅(a^ℓ) = a^5ℓ is pictured below, writing only the exponent ℓ for a^ℓ: For example, T₅(a⁶) = a⁵⁽⁶⁾ = a³⁰ = a⁶.

  2e. The inverse mapping T₅⁻¹ is given by reversing the arrows in the diagram. But since they are all bi-directional arrows, we get the same diagram, so T₅⁻¹ = T₅. We can see this since:

  T₅(T₅(a^ℓ)) = T₅(a^5ℓ) = a^25ℓ = (a²⁴)^ℓ a^ℓ = a^ℓ,

  so T₅∘T₅ = I, the identity.
• 9/29 Ch 3.1 Groups of permutations.   Notes   ⊞ HW  
  Reading: Terras Ch 3.1 pp. 81-89
  HW

  1. Recall the dihedral group G = D₄ = {I, R, R², R³, A, B, C,D}, the geometric symmetries of the square with corners 1,2,3,4. (See Soln 9/8.)
     
     1. Write each symmetry in compact cycle notation, omitting 1-cycles.
     2. Determine the order of each group element g (the smallest n > 0 with gⁿ = e). Verify that this is the least common multiple of the lengths of the cycles in the corresponding permutation.
  2. Do the same as above for the group G = Tet⁺, the 12 rotation symmetries of the tetrahedron from Notes 9/18.
     

  ⊞ Soln  

  1a.

  I	R	R2	R3	A	B	C	D
  id	(1234)	(13)(24)	(4321)	(14)(23)	(24)	(12)(34)	(13)

  1b. The order of each symmetry is clear geometrically:

  |I| = 1 = lcm(1,1,1,1);   |R| = |R³| = 4 = lcm(4);   |R²| = 2 = lcm(2,2);   |A| = |C| = lcm(2,2);   |B| = |D| = lcm(2,1,1).

  2a. See the 9/18 Soln

  2b. The non-identity elements of Tet⁺ are: R_i^±1 = ⅓ rotations of order 3; and A, B, C = ½ rotations of order 2.
  These again agree with the lcm of the cycle lengths.

  ---

• 10/2 Ch 3.1 Alternating permutations   Notes   ⊞ HW  
  Reading: Terras Ch 3.1 pp. 81-89
  HW

  1. Alternating group A_n. Recall that A_n is the subgroup of all permutations in S_n which are even: they are a product of an even number of transpositions. (A transposition is a 2-cycle (ij) switching just the elements i,j and leaving all other elements fixed.)
     1. For each element of S₃, write it in cycle notation, and as a product of transpositions. Determine which are the even elements A₃.
     2. Write each element of S₃ as a 3×3 permutation matrix: that is, for p : {1,2,3} → {1,2,3}, write the matrix of the linear mapping L_p defined by L_p(e_i) = e_p(i), where e₁ = (1,0,0), e₂ = (0,1,0), e₃ = (0,0,1). Thus, the columns of the permutation matrix are [ e_p(1) | e_p(2) | e_p(3) ].
     3. Find the determinant of each permutation matrix above, and verify that even permutations have determinant 1, odd have −1.
  2. Even and odd permutations
     1. Explain why the even permutations in S_n form a subgroup (called A_n). Hint: An even permutation can be written as the product of an even number of transpositions.
     2. (Terras Ex. 3.1.13 p. 87.) Consider the set of odd permutations in S_n, together with the identity: do these form a subgroup? Hint: What must you check to see if a subset is a subgroup?
  ⊞ Soln  

  1a. The elements of S₃ are: id (zero transpositions, even); transpositions (12), (13), (23), all odd; and (123) = (12)(23), (132) = (13)(32), both even. Thus A₃ = {id, (123), (132)}.
  1b,c. The permutation (123) has matrix [ e_p(1) | e_p(2) | e_p(3) ] = [ e₂ | e₃ | e₁ ] = [

  0	0	1
  1	0	0
  0	1	0

  ]. This can easily be computed to have determinant 1. Similarly for the other permutations.

  2a. A_n forms a group, since if σ, τ ∈ A_n, so that they are each products of an even number of permutations, then σtau; is a product of an even + even = even number, so σtau; ∈ A_n. Also, σ⁻¹ is a product of the same even number of transpositons in the opposite order (since (gh)⁻¹ = h⁻¹g⁻¹), so σ⁻¹ ∈ A_n. Since A_n is closed under multiplication and inverses, it is a subgroup.

  2b. The odd permutations are the products of an odd number of permutations, but they are not closed under multiplication, since odd + odd = even.

• 10/4 Ch 3.2 Isomorphisms & Cayley's Theorem   Notes   ⊞ HW  
  Reading: Terras Ch 3.2 pp. 89-93
  HW

  1. Recall that Cayley's Theorem gives a representation of any abstract group G of order n as permutations of itself, so that G ≅ G' ⊂ S_n. We associate each g ∈ G to the permutation σ_g ∈ S_n defined by σ_g(h) = gh; that is, σ_g moves h to gh, the product in G.
     1. Recall the dihedral group G = D₃ = {e, r, r², a, b = ar, c = ar²} with ra = ar². Write the permutation σ_g ∈ S₆ associated to each element, in cycle notation. (Write the elements to be permuted as group letters, not numbers.)
        Example: g = r multiplies the group elements as:
        re = r,   rr = r²,   rr² = e,   ra = c,   rb = a,   rc = b,
        
        σ_R  =  (

        e	r	r2	a	b	c
        r	r2	e	c	a	b

        )  =  (e r r²) (a c b).
        Hint: The one-line notation for each σ_g is the g-row of the multiplication table for D₃.
     2. In this representation of G in S₆, determine the sign (even or odd) of each permutation. Do these match the signs in the original permutation representation in S₃ as permutations of the three triangle vertices 1,2,3?
  ⊞ Soln  

  1a. The two-line notation for each permutation σ_g is given by the row of g in the multiplication table of G = D₃. Writing these in cycle notation:

  id,    r = (e r r²) (a c b),    r² = (e r² r) (a b c),
  a = (e  a) (r  b) (r²  c),    b = (e  b) (r  c) (r²  b) ,    c = (e  c) (r  a) (r²  b).

  (The identity has an empty cycle notation, since it has only 1-cycles.)

  1b. In the representation D₃ ⊂ S₆, the elements e, a, b, c are odd, while r, r² are even (since every 3-cycle is even). In fact, these are the same as the signs in our previous representation from the corners of a triangle, D₃ ≅ S₃ .

• ⊞ Hand-In HW 2 due Wed 10/11.
  Consider the 12-element tetrahedral rotation group:

  G  =  Tet⁺  =  { I, R₁, R₁⁻¹, R₂, R₂⁻¹, R₃, R₃⁻¹, R₄, R₄⁻¹, A, B, C }.

  We previously represented these as 3×3 matrices, or as permutations in S₄ corresponding to motions of the vertices 1,2,3,4: in fact, this gives all 12 = ½(4!) permutations in A₄. This group is generated by the right-handed ⅓ rotations R₁, R₂.
  The proof of Cayley's Theorem specifies how each group element can permute all 12 group elements, which is a different permutation representation in S₁₂: we take the permutation σ_g : G → G defined by σ_g(h) = gh.

  1. Write the permutations σ_g ∈ S₁₂ for the generator rotations g = R₁, R₂.
     Hint: To find the product gh ∈ Tet⁺, use cycle notation in the S₄ representation, then identify the product permutation in S₄ as one of the 12 letter elements.
  2. In this representation G ≅ G' = {σ_g} ⊂ S₁₂, are the permutations σ_g ∈ S₁₂ all even, as they were for the representation G ≅ A₄ ⊂ S₄? Do they give the entire group A₁₂?
  Tet⁺ Icosahedron
• 10/6 Ch 3.3 Cosets, Lagrange Thm   ⊞ Text   Notes
  Reading: Terras Ch 3.3, pp. 93-98. Cosets

  • Cosets. For a subgroup H ⊂ G and g ∈ G, define the left coset gH = {gh for h ∈ H}; and right coset Hg = {hg for h ∈ H}.
  • Lemma: For any subgroup H ⊂ G, the group splits into a disjoint union of cosets: G  =  g₁H ∪ ··· ∪ g_k−1H, where   g_iH ∩ g_jH = {} for i ≠ j.
  • Here g₁, . . . , g_k are representatives of their cosets, but not unique, though we usually take g₁ = e. In fact, hH = H for any h ∈ H, so if we take another gh ∈ Hg as the representative, we get the same coset gH = ghH.
  • Lagrange's Theorem: For a subgroup H ⊂ G with G finite, the order of the subgroup evenly divides the order of the group:  |H| is a divisor of |G|.
    Proof: Since every coset has equal size, |gH| = |H|, and the group G is split into k disjoint subsets g_iH of size |H|, we have:
    |G|  =  |g₁H| + ··· + |g_kH|  =  k|H|.
    That is, |H| evenly divides |G|.
  • The number of distinct cosets is k = ^|G|⁄_|H|, since the above proof shows that |G| = k|H|.
  ⊞ HW  
  1. Recall the symmetries of the square
     G = D₄ = {e, r, r², r³, a, b = ar, c = ar², d = ar³},
     with the relations r⁴ = a² = e and ra = ar⁻¹. In Quiz 10, we discussed its subgroups: the cyclic ones including the center Z(G) = {e, r²}, and two non-cyclic subgroups {e, r², a, c} and {e, r², b, d}.
     1. Check that all these subgroups do indeed satisfy Lagrange's Theorem.
     2. For the subgroup H = ⟨a,r²⟩, write the elements of each distinct coset gH.
     3. Same for H = ⟨a⟩.
  2. Could a coset gH ever be a subgroup itself, except for gH = H?
  3. Recall the Cayley graph of G = D₄ = ⟨r, a⟩. The vertices are the elements g ∈ G, and the effect of multiplying on the right by each generator is shown by the blue r-arrows g ^r→ g' = gr and the red bidirectional a-arrows g ^a↔ g' = ga (which represent two opposite arrows).
     
     1. For the cyclic subgroup H = ⟨r⟩, compute the two distinct cosets g₁H = H and g₂H, writing out the elements of each. On a copy of the picture, group each coset by a circle around its elements.
     2. Do the same for the other generator subgroup H = ⟨a⟩.
     3. Try this also for H = ⟨b⟩, where b = ar. Since this was not a generator of the graph, the cosets will look more messy.
  ⊞ Soln  
  1a. The subgroups

  H = {e}, {e, r²}, {e, a}, {e, b}, {e, c}, {e, d},
  {e, a, c, r²}, {e, b, d, r²}, {e, r, r², r³}, G

  all have order |H| = 1, 2, 4, or 8, which are all divisors of |G| = 8. This is the content of Lagrange's Theorem.

  1b. The cosets of H = {e, a, c, r²} are H and rH = {r, ra = d, rc = b, r³}. Together G = H ∪ rH, the union of two disjoint subsets each of size |H| = 4. This guarantees that |G| = 2 |H|.

  2. Since the subgroup H contains e, and different cosets never intersect, no other coset gH can contain e, so it cannot be a subgroup.

  3a. The two cosets of H = ⟨r⟩ are H = {e, r, r², r³} itself and aH = {a, ar, ar², ar³} = {a, b, c, d}. Note that the second coset could be represented by any of its elements: for example aH = bH since bH = {b, br, br², br³} = {b, c, d, a}.

  In the Cayley graph, the cosets are the cycles formed by the blue r-arrows:

  

  3b. For the subgroup H = ⟨a⟩ = {e,a}, the number of distinct cosets is ^|G|⁄_|H| = ⁸⁄₂ = 4, namely:

  H = {e,a},   rH = {r, ra} = {r, d},   r²H = {r², r²a} = {r², c},

  r³H = {r³, r³a} = {r³, b}.

  In the Cayley graph, these are just the pairs of elements at the two ends of each red a-arrow (which represent 2-cycles of red arrows).

  3c. The cosets of H = ⟨b⟩ are H = {e,b}, rH = {r, a}, r²H = {r², d}, r³H = {r³, c}.

  ---

• 10/9−13 Ch 3.4 Normal subgroup, quotient group   ⊞ Text   Notes  
  Reading: Terras Ch 3.4, pp. 98-101.

  • Conjugation by g ∈ G
    • Conjugate of h is ghg⁻¹
    • h₁ is conjugate to h₂ in G means there is some g ∈ G with h₁ = gh₂g⁻¹
    • G splits into disjoint classes of elements conjugate to each other, G = K(x₁) ∪ K(x₂) ∪···, where the conjugacy class of x ∈ G is:
      K(x)  =  {gxg⁻¹ for g ∈ G}.
      Conjugacy classes can have different sizes; for example the identity e is conjugate only to itself: K(e) = {e}.
  • Normal subgroup K ⊂ G definition
    • Left cosets equal right cosets:  gK = Kg for all g ∈ G
    • Same as:  K is equal to its conjugate subgroups
      K  =  gKg⁻¹  =  {gkg⁻¹ for k ∈ K}  for all  g ∈ G.

    • Same as:  K = K(x₁) ∪ ··· ∪ K(x_m), the subgroup is a union of conjugacy classes.
  • Quotient group G/K = {gK for g ∈ G} for normal K ⊂ G
    • Elements are cosets gK = Kg denoted [g] for short
    • Define the operation:
      g₁K·g₂K  =  {g₁k₁g₂k₂ for all k₁, k₂ ∈ K}  =  g₁g₂K.
      The product only produces a single coset since g₁Kg₂K = g₁g₂KK = g₁g₂K, since KK = {k₁k₂ for all k₁, k₂ ∈ K} = K.
    • This defines a group with identiy K = eK, inverse (gK)⁻¹ = g⁻¹K.
  • Example: G = D₃ = {e, r, r², a, ar, ar²} with r³ = e , a² = e , ra = ar²
    • Conjugacy classes split G into the identity, rotations, and reflections:
      G  =  {e} ∪ {r, r² = ara⁻¹} ∪ {a, ar = rar⁻¹, ar² = r²ar⁻²}

    • H = ⟨a⟩ = {e,a} gives left and right cosets:
      G  =  H ∪ rH ∪ r²H  =  {e,a} ∪ {r, ra = ar²} ∪ {r², r²a = ar}
           =  H ∪ Hr ∪ Hr²  =  {e,a} ∪ {r, ar} ∪ {r², ar²}
      Since the left and right cosets are not the same, H is not normal.
      We cannot define a unique multiplication on G/H = {H, rH, r²H} using g₁H · g₂H = g₁g₂H.
      For example, we get two different results if we try to multiply rH = ar²H = {r, ar²}:
      rH · rH = r·rH = r²H     ^?=^?     ar²H · rH = ar²·rH = aH = H.

    • K = ⟨r⟩ = {e,r,r²} is normal with cosets:
      G  =  K ∪ aK  =  [e] ∪ [a]  =  {e, r, r²} ∪ {a, ar, ar²}

    • Quotient group:  G/K = D₃/⟨r⟩ = {K, aK} = {[e], [a]} with [a]·[a] = [e], so G/K ≅ C₂.
  • Equivalence modulo K inside group G
    • Define equivalence g₁ ≡ g₂ mod K to mean g₁K = g₂K
    • Same as:  g₁ = g₂k for some k ∈ K
    • Same as:  g₁g₂⁻¹ ∈ K
  • Example: Modular addition in integers G = (Z , + )
    • Normal subgroup K = ⟨n⟩ = { . . . , −n, 0, n, 2n, . . . }
    • Cosets i+K = [i] = { . . . , i−n, i, i+n, i+2n, . . . }. We use additive group notation i+K instead of gK.
    • G/K  =  Z/⟨n⟩  =  Z_n  =  {⟨n⟩, 1+⟨n⟩, 2+⟨n⟩, . . . , n−1+⟨n⟩}  =  {[0], [1], [2], . . . , [n−1]}
    • i ≡ j mod n is equivalent to:
      [i]  =  [j]   ⇔   { . . . , i−n, i, i+n, i+2n, . . . } = { . . . , j−n, j, j+n, j+2n, . . . }
      
         ⇔    i = j + kn;    ⇔    i − j ∈ ⟨n⟩.

    • Addition operation: [i] + [j] = [i+j]
  ⊞ HW  
  Consider the dihedral group of order 8:

  G  =  D₄  =  {e, r, r², r³, a, b = ar, c = ar², d = ar³},

  where r⁴ = a² = e and ra = ar⁻¹. This is the symmetry group of a square in the plane:

  

  Recall the subgroups H ⊂ G:

  

  1. Split G into conjugacy classes K(x) = {gxg⁻¹ for g ∈ G}. That is, for some x, compute all its conjugates gxg⁻¹, do the same for another element y not in K(x), etc. For example, K(e) = {e} since geg⁻¹ = e for all g.
  2. Show that K(x) = {x} if and only if x ∈ Z(G), that is, x is a central element which commutes with all others. What is the center Z(D₄)?
  3. Find which subgroups K ⊂ G are normal: i.e. which satisfy gKg⁻¹ = K for all g. These are the subgroups which are unions of entire conjugacy classes K = K(e) ∪ K(x) ∪ K(y) ···, whereas non-normal subgroups contain only parts of some conjugacy classes.
  ⊞ Soln  

  1. The conjugacy classes of G = D₄ are:

  K(e) = {e} (identity),     K(r²) = {r²} (½ rotation),     K(r) = {r, r³} (¼ rotations),

  K(a) = {a,c} (reflections across sides),     K(b) = {b,d} (reflections across diagonals).

  Note that K(x) = K(x') for any x' ∈ K(x); that is, we can choose any element of a class as its representative.

  2. Claim: x ∈ Z(G) if and only if K(x) = {x}.

  Proof: First, assume x ∈ Z(G), so that gx = xg for all g. Then the conjugate is (gx)g⁻¹ = (xg)g⁻¹ = x, and the conjugacy class is K(x) = {gxg⁻¹ for all g} = {x}.

  Conversely, assume K(x) = {gxg⁻¹ for all g} = {x}. This means gxg⁻¹ = x, so (gxg⁻¹)g = xg, i.e. gx = xg for all g. Thus x ∈ Z(G).

  In our case, we have Z(D₄) = {e, r²}, since r²a = ar⁻² = ar², and all other non-identity elements clearly fail to commute with some reflection a, b, c, or d. QED

  3. The normal subgroups are marked with N:

  

  Each normal subgroup is a union of conjugacy classes: for example, {e, r², a, ar²} = K(e) ∪ K(r²) ∪ K(a). Note that every subgroup of order ^|G|⁄₂ = 4 is normal.

  ---

• 10/16 & 18 Midterm Review   ⊞ HW  
  1. For each of the following familiar groups G, give:
     1. Definition of G as symmetries of some object;
     2. List of elements g ∈ G, or a format for describing them;
     3. A method for computing products in G;
     4. Subgroups H ⊂ G, and which are normal K ⊂ G;
     5. Type of each quotient group G/K.
     6. Cayley graph X(G,S);
     The groups are:
     1. Cyclic group C_n
     2. Modular addition (Z_n, + )
     3. Modular multiplication (Z_n^×, × )
        Extra Credit: Find all subgroups: reference.
     4. Dihedral group D_n
        Extra Credit: Find all subgroups and quotient groups.
     5. Symmetric group S_n
     6. Alternating group A_n
     7. Tetrahedron rotation group Tet⁺
        Extra Credit: Use Mathematica to draw various polyhedron solids X with Sym(X) = Tet or Tet⁺, and relate their edge skeletons to Cayley graphs.
     8. General linear matrix group GL_n(R)
  2. Theory: definitions and theorems. To write a proof, start by writing the definitions of the terms involved. Try to transform the statement which is assumed (the setup) into the statement which is to be shown (the conclusion). The final draft should be a clear chain of deductions from the setup to the conclusion (not working from both ends).
     1. Give the definition and axioms of an abstract group, and explain why any symmetry group satisfies these axioms.
     2. Prove that in any group, any element has only one inverse. That is, if ab = e and ac = e, then b = c. Also, if ab = e and ca = e, then b = c.
     3. Show that if z ∈ Z(G), the center of G, then z⁻¹ ∈ Z(G). (This is one part of showing that Z(G) is a subgroup.)
     4. State Cayley's Theorem that every group G can be represented as a permutation group on its own elements, and define the permutation σ_g : G → G associated to g ∈ G.
     5. Show that if a subgroup H ⊂ G has |H| = ½|G|, then H is a normal subgroup.
     6. State Lagrange's Theorem about the size of any subgroup compared to the size of the whole group.
     7. Show that for any group element g ∈ G, the conjugation mapping T_g : G → G defined by T_g(x) = gxg⁻¹ is an isomorphism from G to itself (a symmetry of the group structure of G).
  ⊞ Soln  

  1a. C_n is the rotation symmetries of a regular n-gon (no reflections), or all geometric symmetries of an n-gon decorated with counterclockwise arrows. Its elements are C_n = {e, r, r², . . . , rⁿ⁻¹} with the relation rⁿ = e, so that rⁱr^j = r^{i+j mod n}.

  The subgroups are K = ⟨r^k⟩ for k a divisor of n. Since G is commutative, all subgroups are normal, and G/K = C_n / ⟨r^k⟩ ≅ C_n/k. The Cayley graph for the single generator r is a circle of n vertices with counterclockwise r-arrows.

  1b. (Z_n, + ) is isomorphic to C_n, so all structural features are the same, only the notation is different. The elements are Z_n = {[0], [1], . . . , [n−1]} where [k] means (k mod n), with the relation [n] = [0]. The subgroup H = ⟨ [k] ⟩ for k a divisor of n has quotient (Z_n/k , + ).

  1c. (Z_n^×, · ) = {ℓ with gcd(ℓ, n) = 1} under multiplication. These are the algebraic symmetries of the group (Z_n, + ): that is, each ℓ ∈ Z_n^× corresponds to an isomorphism

  T_ℓ : Z_n → Z_n ,   T_ℓ(i) = ℓi,

  preserving the + operation structure: T_ℓ(i+j) = T_ℓ(i) + T_ℓ(j). Composition of symmetries corresponds to multiplication in Z_n^×, so that T_ℓ(T_m(i)) = T_ℓ·m(i).

  1d. D_n is the geometric symmetries of a regular n-gon. D_n = {e, r, r², . . . , rⁿ⁻¹, a, ar, ar², . . . , arⁿ⁻¹} with relations rⁿ = a² = e and ra = ar⁻¹ = arⁿ⁻¹ , so that

  (a^prⁱ)·(a^qr^j) = a^{(p+q mod 2)} r^{((−1)q i + j mod n)}.

  One can also multiply in D_n by realizing elements as linear mappings on the plane, and multiplying their 2 × 2 matrices; or by realizing elements as permutations of the n corners, and composing permutations as in #1e below.

  The Cayley graph of D_n with generators S = {r, a} consists of a circle of n vertices with counterclockwise r-arrows, another circle with clockwise r-arrows, and bidirectional a-arrows connecting the n pairs of vertices in the two circles.

  1e. S_n is the symmetries of any unstructured set of n distinct objects, usually the numbers {1, 2, . . . , n}. A group element is a permutation, a one-to-one and onto mapping σ : {1, 2, . . . , n} → {1, 2, . . . , n}, denoted in 2-line notation with σ(i) written underneath i; or in cycle notation with σ(i) written next to i, except when i closes a cycle beginning with σ(i). The order (number of elements) is |S_n| = n! = n(n−1)··(2)(1). The multiplication σ·τ is computed by composing permutations: (σ·τ)(i) = (σ(τ(i)), so that each output of τ becomes an input of σ. The inverse σ⁻¹ can be computed by switching the rows in 2-line notation, or by reversing the cycles in cycle notation.

  S_n has many, many subgroups. In fact, Cayley's Theorem says that any finite group G can be represented by an isomorphic subgroup of permutations in some S_n: G ≅ G' ⊂ S_n. These subgroups are almost never normal; in fact, the only normal subgroup of S_n for n ≥ 5 is the alternating group A_n below. The Cayley graph of S_n for n ≥ 5 is too complicated to be useful. However, S₂ ≅ C₂, S₃ ≅ D₃, and S₄ ≅ Tet, the geometric symmetries of a tetrahedron, which has a nice Cayley graph below.

  1f. A_n is the subgroup of even permutations of S_n, namely those permutations σ which can be written as a product of an even number of transpositions τ = (ab), not necessarily disjoint transpositions. For example, any k-cycle can be written: as a product of k−1 transpositions:

  κ = (abcd···yz) = (ab)(bc)(cd)···(yz),

  so an even-length cycle is odd, and an odd-length cycle is even. Further, any permutation can be written as a product of disjoint cycles, so it is easy to see if the total number of transpositions is even or odd. The order is |A_n| = ½ n!.

  A_n again has many subgroups. Typically, if a geometric symmetry group G = Sym(X) is represented by permutations of n corners, G ≅ G' ⊂ S_n, then its subgroup of even permutations, H' = G' ∩ A_n, represents the subgroup G⁺ of rotations only.

  1g. Tet is the geometric symmetries (rotations and reflections) of a regular tetrahedron (pyramid with triangular base).

  

  Its elements can be represented as linear mappings of space (3 × 3 matrices), or most easily as permutations of the corners labeled {1,2,3,4}. In fact, this gives all 4! = 24 permutations in S₄, so that Tet ≅ S₄, similar to D₃ ≅ S₃.

  Tet⁺ is the subgroup of rotation symmetries only, represented by even permutations: Tet⁺ ≅ A₄. It has 12 elements generated by R₁ = (243), R₂ = (134), where R_i is the right-handed ⅓ rotation around the corner i.

  Tet⁺ = {I, R₁, R₁⁻¹, R₂, R₂⁻¹, R₃, R₃⁻¹, R₄, R₄⁻¹, A₁₂, A₁₃, A₁₄},

  where A_ij is ½ rotation around an axis through the midpoint of the edge ij. (In the HW, we had A = A₁₂, B = A₁₃, C = A₁₄.)

  The Cayley graph of Tet with respect to the transposition generators (12), (23), (34) is drawn below, as the 24 corners of the permutahedron solid X obtained by rotating and reflecting a fundamental domain X_o with one corner by the 24 permutations (in one-line notation), so that X = ⋃_σ∈S4 σ(X_o).

  

  The Cayley graph of Tet⁺ is drawn below in the plane, and also as the skeleton of a cuboctahedron solid, whose corners are the 12 rotations of the point (½,1,1) in the picture above. The extra generator B = (13)(24) cuts the quadrilateral faces into triangles, giving the skeleton of an irregular icosahedron.

  1h. GL_n(R) is the symmetries of the n-dimensional vector space Rⁿ, and its elements are linear mappings L, which preserve vector addition and scalar multiplication:

  L : Rⁿ → Rⁿ,   L(av + bw) = a L(v) + b L(w).

  To compute, we write L as an n × n matrix [L] with columns equal to L(e₁), . . . , L(e_n), where e_i is the axis vector with 1 in coorinate i, zeroes elsewhere. We compute products by matrix multiplication.

  2a. See HW 9/1 Text.

  2b. Proposition: Let a,b,c be elements of a group G. If ab = ac = e, then b = c. If ab = ca = e, then b = c.

  Proof: Suppose ab = ac = e. By the definition of a group, there is an element d = a⁻¹ with da = e, so b = (da)b = d(ab) = d(ac) = (da)c = c; that is, b = c.

  Now suppose ab = ca = e. Then b = eb = cab = ce = c; that is, b = c.

  2c. Proposition: If z ∈ Z(G), then z⁻¹ ∈ Z(G).

  Proof: z ∈ Z(G), the center of G, means that gz = zg for all g ∈ G. Then for any g ∈ G:

  z⁻¹g = z⁻¹(gz)z⁻¹ = z⁻¹(zg)z⁻¹ = gz⁻¹.

  That is gz⁻¹ = z⁻¹g for all g ∈ G, which means z⁻¹ ∈ Z(G).

  2d. See HW 9/15.

  2e. Proposition: If H ⊂ G is a subgroup with |H| = ½ |G|, then H is a normal subgroup.

  First proof. The subgroup H is normal means that gHg⁻¹ = H for any g ∈ G, where gHg⁻¹ = {ghg⁻¹ for all h ∈ H}. Thus, we must show that ghg⁻¹ ∈ H for any g ∈ G and h ∈ H. Clearly for g ∈ H, we must have ghg⁻¹ ∈ H since H is closed under multiplication and inverses.

  Now suppose g ∉ H, so that the coset gH is disjoint from eH = H. Since |H| = |gH| = ½ |G|, we have G = H ∪ gH. Which one of these contains ghg⁻¹? If we had ghg⁻¹ ∈ gH, so that ghg⁻¹ = gh' for h' ∈ H, then multiplying both sides by g⁻¹ would give hg⁻¹ = h', and g = (h')⁻¹h ∈ H. But we chose g ∉ H. The contradiction shows we cannot have ghg⁻¹ ∈ gH, so ghg⁻¹ must be in the other coset, ghg⁻¹ ∈ H. This shows H is normal.

  Second proof. An equivalent definition of a normal subgroup H is that its left and right cosets are equal: gH = Hg for all g ∈ G. For g ∈ H, we have gH = Hg = H. For g ∉ H, the cosets gH and Hg must both be disjoint from H, so gH and Hg lie inside G−H = {g ∈ G with g ∉ H}. But gH, Hg, and G−H all have the same size |H| = ½|G| elements, so they are all the same set, and gH = Hg. Therefore H is is normal.

  2f. See HW 10/6.

  2g. Claim: For any group element g ∈ G, the conjugation mapping T : G → G is defined as T(x) = gxg⁻¹. Then T_g is a group isomorphism.

  Proof. An isomorphism means a one-to-one and onto mapping which preserves multiplication.

  To check that T_g is one-to-one, suppose that T_g(x) = T_g(y). Then

  x = g⁻¹(gxg⁻¹)g = g⁻¹(gyg⁻¹)g = y,

  i.e. x = y, so that two different inputs cannot be mapped to the same output.

  To check that T_g is onto, take any y ∈ G, and note that for x = g⁻¹yg,

  T_g(x) = g(g⁻¹yg)g⁻¹ = y.

  Thus, there is x ∈ G with T_g(x) = y, and T_g(x) is onto.

  To check that T_g(x) preserves multiplication, note that:

  T_g(xy) = gxyg⁻¹ = gx(g⁻¹g)yg⁻¹ = (gxg⁻¹)(gyg⁻¹) = T_g(x)T_g(y).

  Therefore T_g is an isomorphism.

• 10/20 Midterm Exam   Solutions

  ---

• 10/21-24 Fall Break
• 10/25 Ch 3.5 Homomorphisms   ⊞ Text  Notes 
  • Homomorphism: A mapping between groups T : G → G' which satisfies the structure equation:
    T(a·b)  =  T(a)·T(b)   for all  a,b ∈ G.
    Thus, each multiplication a·b in G corresponds to a mulitplication T(a)·T(b) in G'.
    A homomorphism need not be one-to-one or onto, but an isomorphism is a homomorphism which is one-to-one and onto (bijective, invertible).
  • Kernel of T: The elements of G which are sent to the identity e' ∈ G':
    Ker(T) = {k ∈ G with T(k) = e'}.
    Image of T: The elements g' ∈ G' which are outputs of the homomorphism
    Im(T) = {g' = T(g) for g ∈ G}.

  • Projection homomorphism: The most common type of homomorphism (other than isomorphisms) is the natural mapping from a group G to a quotient group G/K:
    P : G → G/K   with   P(g) = [g] = gK ∈ G/K.
    
    The kernel contains those k with P(k) = [k] = [e], which means k ∈ K: that is, Ker(P) = K.
    The mapping P is clearly onto: each class is the class [g] of some element g ∈ G; so Im(P) = G/K.
  • Homomorphism Theorem: Let T : G → G' be any homomorphism of groups. Then:
    1. K = Ker(T) is a normal subgroup of G.
    2. Im(T) is a subgroup of G'.
    3. The quotient of G by the kernel of T is isomorphic to the image of T:
       G/Ker(T)  ≅  Im(T).
       The isomorphism is T : G/Ker(T) → Im(T) defined by T(gK) = T(g).
  • In the diagram, the homomorphism T takes each element gk ∈ gK, where K = Ker(T) to:
    T(gk) = T(g)T(k) = T(g)e' = T(g) = g',
    whereas the quotient isomorphism T takes the whole coset gK, a single element of G/K, to g' = T(g).
  • Example: Let G = (Z, + ) and G' = C_n = {e, r, r², . . . , r^r−1) with rⁿ = e. Define T : G → G' by T(i) = rⁱ. This mapping is onto Im(T) = G', and the elements in the kernel, i ∈ K = Ker(T) are those i ∈ Z with:
    e = T(i) = rⁱ   ⇔   i = kn.
    That is, Ker(T) = ⟨n⟩ = {0, ±n, ±2n, . . . }. The Isomorphism Theorem says:
    G/Ker(t)  =  Z/⟨n⟩  ≅  C_n .
    In fact Z/⟨n⟩ is just the definition of the modular addition group (Z_n , + ), and T : (Z_n , + ) → C_n is the isomorphism we have seen several times before.
  ⊞ HW 
  1. Homomorphisms to G' = (R^×, · ), where R^× = {x ∈ R, x ≠ 0}.
     For each mapping T : G → R^× below, check that it is a homomorphism, and determine the image Im(T), the kernel K = Ker(T), and the type of the quotient group G/K.
     1. T : (Z + ) → R^× defined as T(i) = (−1)ⁱ.
     2. The sign mapping T = sgn on permutations, sgn : S_n → R^×.
     3. The determinant mapping T = det on 2×2 invertible matrices, det : GL₂(R) → R^×.
        Hint: It is a homomorphism because of a well-known formula for the determinant of a product matrix. Look it up if needed.
  2. Recall our standard group G  =  D₄  =  {e, r, r², r³, a, b = ar, c = ar², d = ar³}, where r⁴ = a² = e and ra = ar⁻¹. This is the symmetry group of the square:
     1. Our usual representation of G is a homomorphism P : G → S₄ taking each g ∈ G to the corresponding permutation P(g) of the marked vertices 1,2,3,4. For example, a = side-to-side reflection of the square, switching vertices 1 & 2 and switching 3 & 4, so T(a) = (12)(34).
        Problem: Determine Im(P), K = Ker(P), and G/K.
     2. Consider a different permutation representation Q : G → S₄ taking each g ∈ G to the corresponding permutation Q(g) of the marked lines A,B,C,D. Here A is the line of reflection a, which takes A to itself, C to itself (flipped over), and switches the two diagonals B & D:

        a  =  (

        A	B	C	D
        A	D	C	B

        )  =  (BD).

        
        Problem: Determine Im(Q), K = Ker(Q), and G/K.
        Note: In this case, the kernel K is not trivial, so the image is not isomorphic to the original G: that is, the permutation Q(g) of A,B,C,D does not uniquely determine the group element g ∈ G.
  ⊞ Soln  

  1a. This is a homomorphism because

  T(i+j) = (−1)^i+j = (−1)ⁱ(−1)^j = T(i)·T(j).

  
  Note that on the left side the group operation is i+j, on the right side it is a·b. Im(T) = {±1}, K = Ker(T) = ⟨2⟩ = {even integers}, and Z/⟨2⟩ = Z₂ = {[0], [1]}, where [i] = i + K, i.e. [0] = {even integers}, [1] = {odd integers}.

  1b. This is a homomorphism because even and odd numbers add together in the same way as +1 and −1 multiply together, as you can prove by examining each case of even/odd plus even/odd.
  Im(sgn) = {±1}, K = Ker(T) = A_n even permutations, and G/K = S_n/A_n ≅ {±1} ≅ C₂.

  1c. This is a homomorphism because det(AB) = det(A)det(B). Im(det) = R^×, meaning det is onto. Ker(det) = SL₂(R) = {A ∈ GL₂(R) with det(A) = 1}, the special linear group of determinant-one matrices: these denote linear mappings of the plane which move any shape X to a distorted shape A(X) having the same area. G/K ≅ R^×.

  2a. Im(P) = {8 permutations in HW 9/8}, K = Ker(P) = {e}, G/K = G, so T is an isomorphism between G and Im(T).

  2b. Im(Q) = {Q(e) = I, Q(a) = (BD), Q(b) = (AC), Q(r) = (AC)(BD)}
  K = Ker(Q) = {e, r²} = ⟨r²⟩, a normal subgroup: in fact, K = Z(G) the center of G.
  G/K = D₄/⟨r²⟩ = {K, aK, bK, rK} ≅ K₄ symmetries of the rectangle.

• 10/27 Ch 3.6 Direct product groups.   Notes  

  ---

• 10/30 Classify |G| = 8   Notes   ⊞ HW  
  Classify all abstract groups of order 8 (i.e. |G| = 8 elements).

  1. For g ∈ G, what do we mean by a cyclic subgroup ⟨g⟩, and its order |g|?
  2. Let N = max{|g|  for  g ∈ G}, the largest order of a cyclic subgroup inside G. Explain why N > 1.
  3. What major theorem guarantees that |g| = 1, 2, 4, or 8 for every g ∈ G, so that N = 2, 4, or 8?
  4. Show if N = 8, then G ≅ C₈ .
  5. Show if N = 2, then G must be abelian, and in fact G ≅ C₂ × C₂ × C₂ .
     Hints: Examine the equation abab = (ab)² = e. Then find independent elements a,b,c ∈ G, and show that G = {e, a, b, c, ab, ac, bc, abc}.
  6. Lemma: Any subgroup H ⊂ G with |H| = ½|G| must be a normal subgroup.
  7. If N = 4, take an element r with |r| = 4, and an element a ∉ ⟨r⟩.
     1. Show that we have two cosets:
        G  =  ⟨r⟩ ∪ a⟨r⟩  =  {e, r, r², r³, a, ar, ar², ar³};
        and that ⟨r⟩ is a normal subgroup.
     2. Show that a² ∈ ⟨r⟩, and in fact a² = e or r².
     3. Show that ra ∈ a⟨r⟩ and in fact ra = ar or ar³.
        Hint: If ra = ar², what does that mean about r²a = r(ra)?
     4. Suppose ra = ar, and either a² = e or a² = r². Show that G ≅ C₄ × C₂ .
     5. Suppose ra = ar³ and a² = e. Show that G ≅ D₄.
  8. Quaternion group. Our last case in the above analysis is a group:
     G  =  {e, r, r², r³, a, ar, ar², ar³}   satisfying   ra = ar³,   a² = r²,   r⁴ = e.
     1. Work out the multiplication table of G implied by the above relations.
     2. The quaternion group is:
        Q₈ = {1, −1, i, −i, j, −j, k, −k},
        where −1 is a central element with −g = (−1)g = g(−1) for g = i, j, k, and:
        ij = k = −ji,   jk = i = −kj,   ki = j = −ik.
        Work out the multiplication table implied by these relations.
     3. Define an isomorphism T : Q₈ → G, which will tranform one multiplication table to the other. To show this works, you should check that the elements T(−1), T(i), T(j), T(k) ∈ G satisfy the relations for Q₈; and conversely the elements T⁻¹(a), T⁻¹(r) ∈ Q₈ satisfy the relations for G.
  ⊞ Soln  

  1. The cyclic subgroup of g contains all powers gⁱ including negative powers and g⁰ = e, so that ⟨g⟩ = {e, g, g², . . . , gⁿ⁻¹}, where the order n is the smallest positive number with gⁿ = e:

  n  =  |g|  =  #⟨g⟩  =  min{k > 0  with  g^k = e}.

  For infinite G, we could get an infinite cyclic group ⟨g⟩ with |g| = ∞, meaning g^k ≠ e for any k > 0.

  2. We have |g| = 1 exactly when g = g¹ = e. Any g ≠ e has |g| > 1, and G has 7 such elements, so the maximum |g| is N > 1.

  3. Lagrange's Theorem says that for any subgroup H ⊂ G, the number of elements |H| is a divisor of |G|. This is because G is split into distinct cosets gH, each with |H| elements; the number of cosets is denoted  [G : H]  =  ^|G|⁄_|H| .

  Now, a cyclic subgroup H = ⟨g⟩ has |H| = |g| elements, so the maximum order N = |g| is a divisor of |G| = 8, namely 1,2,4,8, but we know N > 1.

  4. Assume N = 8, which means there is some g with |g| = 8. Then G contains ⟨g⟩ = {e, g, g², . . . , g⁷} ≅ C₈, but since G only has 8 elements, we have G = ⟨g⟩ ≅ C₈.

  5. In any group, if g² = e for all g ∈ G, or equivalently g = g⁻¹, then G is commutative. This is because, for any g₁, g₂ ∈ G, we have g₁g₂ = (g₁g₂)⁻¹ = g₂⁻¹g₁⁻¹ = g₂g₁ .

  For our G, assume N = 2, which means g² = e for all g ∈ G. Take any a ∈ G with a ≠ e, and any b ≠ a,e. Since a² = b² = e and ba = ab, we have a subgroup ⟨a,b⟩ = {e, a, b, ab} with two cosets:  G = ⟨a,b⟩ ∪ c⟨a,b⟩ for any c ∉ ⟨a,b⟩. Then G = {e, a, b, ab, c, ac, bc, abc}, which is clearly isomorphic to:

  C₂ × C₂ × C₂  =  {(e,e,e), (t,e,e), (e,t,e), (t,t,e), (e,e,t), (t,e,t), (e,t,t), (t,t,t)},

  where t² = e ∈ C₂.

  Specifically, we have the isomorphism T : C₂×C₂×C₂ → G with T(tⁱ, t^j, t^k) = aⁱb^jc^k. This clearly respects multiplication. To check it is one-to-one, it is enough to show Ker(T) = {(e,e,e)}: this holds since T(tⁱ, t^j, t^k) = aⁱb^jc^k = e implies c^k = a⁻ⁱ b^−j ∈ ⟨a,b⟩; but we chose c¹ = c ∉ ⟨a,b⟩, so c^k = c⁰ = e. Similarly b^j = e and aⁱ = e, so (tⁱ, t^j, t^k) = (e, e, e). Since T is one-to-one, the images of its 8 elements must fill all of G, i.e. G is onto.

  6. Lemma: If H ⊂ G is a subgroup with |H| = ½|G|, then H is a normal subgroup.
  Proof: G has half its elements inside H, and half outside H, forming the complement G−H. For any g ∉ H, the left coset gH ⊂ G−H, with |gH| = |H| = ½|G| elements, must fill the entire complement G−H, and the same is true of the right coset Hg. Thus gH = G−H = Hg, and H is normal.

  7a. For r ∈ G with |r| = 4, the number of cosets of H = ⟨r⟩ = {e, r, r², r³} is [G : H]  =  ^|G|⁄_|H|  =  ⁸⁄₄  =  2.

  H is a subgroup with |H| = ½|G|, so H is normal by the previous problem. Choosing any a ∉ H = ⟨r⟩, we have

  G = H ∪ aH = {e, r, r², r³, a, ar, ar², ar³}.

  7b. We have the normal subgroup H = ⟨r⟩ with the quotient group G/H = {H, aH} ≅ C₂, so a²H = (aH)² = H. That is, that a²H = H, which means a² ∈ H = {e, r, r², r³}.

  If we had a² = r, this would mean a⁸ = r⁴ = e and |a| = 8, contradicting N = 4. (We can easily check aⁱ ≠ e for i = 1,2,3,4,5,6,7.) Thus a² = r is impossible. Similarly, a² = r³ = r⁻¹, with |r⁻¹| = 4, is also impossible. The remaining possiblilities are a² = e and a² = r².

  7c. Since ⟨r⟩ is normal by part (a), we have ⟨r⟩a = a⟨r⟩, so that ra ∈ {a, ar, ar², ar³}. Clearly ra ≠ a.

  If we had ra = ar², then rra = rar² = ar²r² = a, but then canceling a would give r² = e, which is untrue since |r| = 4. Thus ra = ar² is impossible. The remaining possiblities are ra = ar or ar³

  7d. Suppose ar = ra, so that G is commutative. Define C₄ × C₂ with elements (sⁱ, t^j) with i mod 4 and j mod 2.

  If we have a² = e, then we get an isomorphism T : C₄ × C₂ → G defined by T(sⁱ, t^j) = rⁱa^j.

  If we have a² = r², then |a| = |r| = 4. We have an isomorphism T : C₄ × C₂ → G defined by T(sⁱ, t^j) = rⁱ(ar)^j. That is, r corresponds to T⁻¹(r) = (s,e), and a corresponds to T⁻¹(a) = (s,t). Both groups are commutative, and r⁴ = e corresponds to (s,e)⁴ = (e,e). Finally, a² = r² corresponds to (s,t)² = (s,e)². These show that the multiplication tables correspond.

  In either case, G ≅ C₄ × C₂ .

  7e. Suppose ra = ar³ and a² = r⁴ = e. Then G = {e, r, r², r³, a, ar, ar², ar³} is our usual presentation of D₄, which means they have the same multiplication table:  G ≅ D₄.

  8a,b. See Wikipedia.

  8c. Suppose ra = ar³ and a² = r², along with r⁴ = a² = e. The quaternion group is Q₈ = {±1, ±i, ±j, ±k} with i² = j² = k² = −1, which is a central element with −g = (−1)g = g(−1) for g = i,j,k, and ij = k = −ji, jk = i = −kj, ki = j = −ik. Then we can define an isomorphism T : Q₈ → G by T(i) = r, T(j) = a, T(k) = ar³ = ar⁻¹, T(−1) = r². This respects multiplication because T(i), T(j), T(k), T(−1) in G obey all the defining relations among i, j, k, −1 in Q. For example, note that ra = ar⁻¹ implies r⁻¹a = ar, so that:

  T(k)²  =  (ar⁻¹)²  =  ar⁻¹ar⁻¹  =  a²rr⁻¹  =  a²  =  r²  =  T(−1)  =  T(k²).

  Also note that −1 commutes with all elements of Q, and similarly T(−1) = r² commutes with all elements of G, since r²a = rar³ = ar⁶ = ar². In a general group, we say an element c ∈ G is central if it commutes with all other elements, that is cg = gc for all g ∈ G. The set of all central elements is always a normal subgroup, denoted Z(G). Under an isomorphism, a central element always goes to a central element; here Z(Q) = {1, −1}, and the unknown 8-element group G has Z(G) = {e, r²}.

• 11/1 Cycle diagrams & Cayley graphs   ⊞ HW  
  1. The cycle diagram of a group G is a graph (network) whose vertices are the elements of G, and whose edges are unions of cycles corresponding to maximal cyclic subgroups ⟨g⟩ (let k = |g|):
     e−−g−−g²− ··· −g^k−1−−e
     (Edges of different cyclic subgroups may have different colors, but this is often omitted.)
     For example, the group K₄ = {e, a, b, ab} with a² = b² = e and ab = ba has diagram:
     
     Draw the cycle diagrams of the groups D₄ and Q₈. How do these show that these groups are not isomorphic?
  2. Recall the Cayley graph X(G,S) of a group G with generating set S. The vertices are again the elements of G, and for each generator s ∈ S, there are directed edges (arrows) of the form:
     g

     s

     →

     gs.
     The edge is labeled with s or with a color associated to s. Each vertex g ∈ G has one arrow of each color arriving and one leaving.
     1. Draw the Cayley graph of G = D₄ with generators r,a satisfying the relations r⁴ = a² = e and ra = ar³. Make the drawing so that it outlines a familiar 3-dimensional solid X ⊂ R³.
     2. Give a representation of D₄ as the rotation symmetries of this solid, and write 3×3 matrices for these rotations (at least for the generators r,a).
     3. Draw the Cayley graph of G = Q₈ with generators r,a satisfying the relations r⁴ = e, a² = r², and ra = ar³.
        This is not the outline of a 3-dimensional solid, and in fact Q₈ does not have any 3-dimensional relations. Next time, we will give a 4-dimensional representation.
  3. Extra Credit: Recall the 12-element tetrahedron rotation group Tet⁺ generated by R₁ = (243), R₂ = (243), and/or B = (13)(24). This Mathematica file draws pictures of solids whose corners are rotations of a given point v under Tet⁺. Try experimenting with different v to get different shapes: for example v = (1,1,1) generates the original tetrahedron, but v = (1,2,2) generates a cuboctahedron, and v = (1,2,3) generates an irregular icosahedron. By measuring the distance between appropriate points, cut the faces out of paper and construct these shapes.
     Show that the edge graph of the cuboctahedron is the Cayley graph of Tet⁺ with generators R₁, R₂. Label your physical or computer-drawn polyhedron with the appropriate group elements and the edges with the appropriate generators (colors). Do all this also for the icosahedron. Are there any other polyhedra that would work the same way?
  ⊞ Soln  

  1. The cycle graphs of the groups of order |G| ≤ 8 are:

  

  2a. Analogous to the Cayley diagram of D₃: a square prism with the 4-cycles of r-arrows in opposite directions around the two square ends, connected by double red a-arrows.

  

  2b. There is a ¼ rotation around the long axis of the square prism, and four ½-rotations around the vertical, horizontal, and diagonal axes through the middle square cross-section.

  These are given in coordinates as follows. Let the orgin be at the center of the block, the x & y axes through the middle square cross-section, and the z-axis along the length of the block. Then the 3×3 matrices of the 8 symmetries are the same as the 2×2 matrices of the corresponding symmetries of the square (in the HW on Rectangle Symmetries), with an extra ±1 diagonal entry in the z-column, making the determinant equal to 1.

  2c. The Cayley graph encodes the multiplication table of G = Q₈. Draw two 4-cycles of r-edges around ⟨r⟩ and its coset a⟨r⟩. Then compute the appropriate 4-cycles of a-edges g → ga. Remember each vertex will have one incoming and one out-going a-arrow.

  

  ---

• 11/3 & 6 Quaternion algebra ℍ & group Q₈   ⊞ Text  
  • Reading: Wikipedia
  • Complex numbers C are the set of expressions a + bi for a,b, ∈ R, multiplied according to the usual rules of algebra along with i² = −1, so that i = √(−1). The reciprocal is:
    ¹⁄_(a+bi)  =  ^(a−bi)⁄_(a²+b²)  =  ^a⁄_(a²+b²) − ^b⁄_(a²+b²) i .

  • The complex number a + bi ∈ C can be identified with the vector v = (a,b) in the plane R².
  • If |u| = 1, we can write u = cos(θ) + sin(θ)i, and the complex multiplication mapping
    M_u : C → C,     M_u(v) = uv
    is a linear mapping of the plane. In fact, it is counter-clockwise rotation by angle θ.
  • Quaternions H are the set of expressions a + bi + cj + dk for a,b,c,d ∈ R. They are multiplied according to the usual distributive rule along with:
    i² = j² = k² = −1,     ij = k = −ji,    jk = i = −kj,    ki = j = −ik;
    also the scalar a commutes with i, j, k. This multiplication is non-commutative. The reciprocal is:
    (a+bi+cj+dk)⁻¹  =  ¹⁄_(a+bi+cj+dk)  =  ^{(a−bi−cj−dk)}⁄_{(a²+b²+c²+d²)} .

  • The quaternion a + xi + yj + zk has scalar part a, and vector part v = xi + yj + zk which can be identified with (x,y,z) in R³.
  • For a unit vector u = bi + cj + dk ∈ R³ with |u| = 1, and an angle θ, let q = cos(½θ) + sin(½θ) u. Then the group conjugation mapping
    M_q : R³ → R³,     M_q(v) = qvq⁻¹
    is a linear mapping of space. In fact, it is right-handed rotation by angle θ around the axis u.
  • The 4-dimensional hyperoctahedron Oct₄ is an analog of the 3-dimensional octahedron, a convex polytope defined as:
    Oct₄  =  { (x₀, x₁, x₂, x₃) ∈ R⁴ with |x₀| + |x₁| + |x₂| + |x₃| ≤ 1 }.
    It can also be defined by its corners, the 8 signed coordinate vectors ±(1,0,0,0), . . . , ±(0,0,0,1); identifying R⁴ with H, these corners are the elements of the 8-element quaternion group Q₈ = {±1, ±i, ±j, ±k} ⊂ H. The outer edges between corners can be pictured by their projection into three dimensions:
    
    This consists of an outer tetrahedron (three-sided pyramid), an upside-down inner tetrahedron, and another tetrahedron connecting each corner of the outer tetrahedron with the nearest triangle face of the inner one.
  ⊞ HW  
  1. From multivariable calculus, recall the dot product u·v and the cross product u×v of two vectors u,v ∈ R³.
     Identifying a vector v = (x,y,z) with the quaternion xi + yj + zk, and denoting quaternion product from the notes as u∗v, check that:
     u∗v   =   −u·v + u×v.

  2. Let u = ¹⁄_√3(i+j+k) be the unit diagonal vector between the three coordinate axes, θ = ^2π⁄₃ a ⅓ circle angle, and q = cos(½θ) + sin(½θ)u.
     1. Compute the 3×3 matrix of the linear mapping:
        M_q : R³ → R³,     M_q(v) = qvq⁻¹.
        The columns are the output vectors M_q(i), M_q(j), M_q(k).
     2. Imagine the effect of M_q on the coordinate axis vectors i, j, k, and interpret M_q as a motion of space. This should agree with the description of M_q in the notes.
  3. The Cayley graph of Q₈ with respect to generators {i, j, k} is:
     
     This is the same abstract graph as the edge-skeleton of Oct₄ above.
     Problem: Label the vertices of the Oct₄ edge-skeleton with the elements of Q₈, and give colors and directions to the edges, to make the edge-skeleton identical to the Q₈ Cayley graph.
  4. The symmetries of the Cayley graph of Q₈ are isomorphic to the group itself. For a group element g ∈ Q₈, the symmetry L_g is a permutation of the vertices which also permutes the edges of each color, defined by left multiplication:
     L_g : G → G,   L_g(h) = gh.
     Since the group can be considered as axis vectors, Q₈ ⊂ H ≅ R⁴, this left multiplication symmetry is a linear mapping of H ≅ R⁴:
     L_g : R⁴ → R⁴,   L_g(v) = gv.
     Problem: Write the 4×4 matrix of each symmetry L_i, L_j, L_k . Note also that L₁ = I and L_(−g) = −L_g .
     Hint: The columns of the matrix of L_g are the outputs L_g(1), L_g(i), L_g(j), L_g(k).
  5. Extra Credit: Define the generalized quaternion group Q_4n ⊂ H to be generated by the elements:
     r = cos(^π⁄_n) + i sin(^π⁄_n)     and     a = j.
     This is also known as the dicyclic group.
     1. Give a presentation of Q_4n similar to that of the dihedral group D_2n with 4n elements. Discuss the similarities and differences between the corresponding dicyclic and dihedral groups.
     2. Describe the 4-dimensional polytope whose corners are the elements of Q_4n. For example, describe its edge-graph, and relate it to a Cayley graph of the group. Describe its 2- and 3-dimensional faces. Or define the polytope by inequalities on the coordinates (x₀, . . . , x₃) as for the hyperoctahedron above.
  ⊞ Soln  
  1. Computing out the quaternion product gives the usual formulas for dot and cross product:

  (x₁i + y₁j + z₁k) ∗ (x₂i + y₂j + z₂k)  =  −(x₁x₂ + y₁y₂ + z₁z₂) + (y₁z₂−y₂z₁)i − (x₁z₂−x₂z₁)j + (x₁y₂−x₂y₁)k .

  2. M_q turns out to be ⅓ rotation matrix around the diagonal axis u: it permutes the x,y,z axes in a 3-cycle:

  M_q(i) = j,   M_q(j) = k,   M_q(k) = i.

  We obtained this rotation in a previous homework.

  3. One way to label the vertices:

  

  The arrow directions and colors are induced by the multiplcation in Q₈.

  4. The matrices are given here: they are the 4×4 matrices with coefficients a,b,c,d.

• 11/8 Subgroups: necessary vs sufficient conditions   ⊞ HW  
  1. For two statements A and B, the implication A ⇒ B means any of these logically equivalent versions:
     • If A, then B
     • A is sufficient for B
     • A being true forces B to be true
     • B is necessary for A
     • B must be true for A to be true
     • If not B, then not A
     • If B is not true, then A cannot be true.
     Problem: Using everyday reasoning, examine the implication A ⇒ B and the converse B ⇒ A for the following statements. Verify that all the versions of a given implication are logically equivalent: they all mean the same thing.
     For a species of animal:
     1. The animal is a bird.
     2. The animal has wings.
     Hint: Having wings is necessary, but not sufficient, for an animal to be a bird.
  2. Consider the following statements for a group G of order |G| = n and a subgroup H ⊂ G:
     1. The subgroup H has order |H| = k.
     2. The number k divides n.
     Lagrange's Theorem says A ⇒ B. Restate the theorem in each logical version above. (Try to make the phrasing natural.)
  3. The converse of Lagrange's Theorem is not true for every group: that is, not all divisors k of |G| = n have a subgroup with order |H| = k.
     The smallest counterexample is the 12-element tetrahedron rotation group Tet⁺, isomorphic to the alternating group A₄ permuting the four tetrahedron vertices:
     G = Tet⁺ = { I, R₁^±1, R₂^±1, R₃^±1, R₄^±1, A, B, C }.
     Find all the subgroups of G, and verify that not every k dividing n = 12 has a subgroup with |H| = k.
  4. Again take G = Tet⁺.
     1. Determine the distinct conjugacy classes:
        K(x) = {gxg⁻¹ for g ∈ G}.
        Hint: Each conjugacy class contains elements of the "same kind": the right-handed ⅓ rotations R_i, the left-handed ⅓ rotations R_i⁻¹, the ½ rotations A,B,C.
     2. Determine which of the subgroups are normal: that is, which ones are unions of entire conjugacy classes, and thus satisfy gKg⁻¹ = K for all g ∈ G.
  ⊞ Soln  

  1. For A ⇒ B, the following mean the same:

  • If an animal is a bird, then it has wings.
  • Being a bird is sufficient to have wings.
  • Being a bird forces (requires) having wings.
  • Having wings is necessary to being a bird.
  • If an animal does not have wings, it is not a bird.
  • If an animal does not have wings, it cannot be a bird.

  Note that if scientists discover a wingless bird, the above statements will be false, but they will still mean the same thing.

  For B ⇒ A, the following mean the same:

  • If an animal has wings, then it is a bird.
  • Having wings is sufficient to be a bird.
  • Having wings forces an animal to be a bird.
  • Being a bird is necessary for having wings.
  • If an animal is not a bird, it does not have wings.
  • If an animal is not a bird, it cannot have wings.

  Of course, these are all equally false, since bats have wings.

  2. Versions of Lagrange's Theorem. For any group G of order |G| = n with a subgroup H ⊂ G:

  • If |H| = k, then k divides n.
  • |H| = k is sufficient for k dividing n.
  • |H| = k forces k to be a divisor of n.
  • Having k a divisor of n is necessary for |H| = k.
  • The number k must divide n for |H| to equal k.
  • If k does not divide n, then |H| ≠ k.
  • If k is not a divisor of n, then |H| cannot equal k.

  3. To find all the subgroups of G = Tet⁺, as always we have the trivial subgroup {I} and the whole group G. Then we have the cyclic subgroups

  {I, R_i, R_i² = R_i⁻¹}, {I, A}, {I, B}, {I, C}.

  We also have the K₄ subgroup {I, A, B, C}, since AB = C.

  There can be no other subgroups, because none of the above can be enlarged without generating the entire group. Any two rotations generate G, since this is clearly true for R₁, R₂, and any other rotations are conjugate to these. Same for R₁ along with any of A = R₁R₂⁻¹, B = R₁R₂R₁, or C = R₁⁻¹R₂, and similarly for any conjugate R_i.

  Thus, there is no subgroup with |H| = 6, a divisor of |G| = 12.

  4a. If an element of Tet⁺ ≅ A₄ is represented by a permutation P of vertices {1,2,3,4}, then:

  PR_iP⁻¹ = R_P(i) ,

  since P⁻¹ moves vertex P(i) to vertex i, then R_i rotates around i, then P moves i back to P(i), and the overall motion is a rotation around P(i). Similarly for the conugacy of R_i⁻¹. Also, for A = (13)(24):

  PAP⁻¹ = P·(13)(24)·P⁻¹ = (P(1), P(3)) (P(2), P(4)),

  so A, B, C form a conjugacy class.

  4b. Besides the trivial subgroup and the whole group, clearly the only subgroup K that can be formed from joining up conjugacy classes is {I,A,B,C}. All other unions of conjugacy classes generate the whole group.

  ---

• ⊞ Hand-In HW 3 due Mon 11/13.
  Write a complete proof that any group with six elements must be isomorphic to a cyclic or dihedral group:

  If |G| = 6, then G ≅ C₆ or D₃.

  • Do each step of the proof analogously to our proof for |G| = 8. Each case will reach a different conclusion from the other proof, sometimes an impossible conclusion which rules out that case.
  • Don't copy verbatim. Study the reference, then close it and write the argument as you understand it. Better yet, use your own alternative ideas.
  • Write in enough detail that it would be understandable to a classmate. But include nothing extra, only what is necessary to deduce the conclusion.
  • You may quote and apply any theorems we have covered, no need to re-prove them.
• 11/10 & 13 Ch 3.7 Cauchy theorem: Subgroup H with |H| = p prime   ⊞ Text   Notes  
  • ⊞ Method of complete induction
    • Recall the method of complete induction. If P(n) is a proposition depending on a variable n, then we can prove the family of propositions P(n) for all n as follows:
      • First directly prove the smallest case P(1).
      • Next, assume that all the cases P(1), P(2), . . . , P(n) have already been proved, up to an unspecified n. Using this assumption, deduce the next case P(n+1).
      • These steps show that the proposition is true for higher and higher values of n, and in fact for all n.
    • Example: Every whole number can be factored into primes.
      • Informally, this is because if n is itself a prime, then this is certainly true. On the other hand, if n is not a prime, then it can be factored into smaller numbers, which in turn can be factored further, and so on until all the factors are themselves unfactorizable, i.e. all factors are primes.
        Induction gives a rigorous way to express the "and so on" part of the argument.
      • Formally, define the statement P(n) = "The whole number n can be factored into primes."
      • Check the smallest case: P(1) is true: 1 = 1 is a factorization into zero primes.
      • Suppose we know 1, 2, . . . , n can all be factored into primes: i.e. assume P(1), . . . , P(n). If n+1 is prime, then P(n+1) is certainly true. On the other hand, if n+1 is not prime, it factors as n+1 = ab for smaller numbers a,b < n, so we know P(a) and P(b) are true: that a and b can be factored into primes; now multiplying these two factorizations gives a prime factorization of n+1 = ab.
      • These two steps show that P(n) is true for all n = 1, 2, 3, . . .
    • Problem: If G is any group with g² = e for all elements g ∈ G, then G is isomorphic to a product of groups C₂ = {e, a} with a² = e: that is, there are commuting elements a₁, . . . , a_k ∈ G such that there is an isomorphism:
      T : G  →  C₂^×k  =  C₂ × ··· × C₂ ,
      T(a₁^e₁ ··· a_k^e_k) = (a^e₁, . . . , a^e_k)   for all e_i = 0 or 1.

  • Centralizers and conjugacy classes
    • Centralizer of an element x ∈ G is the subgroup:
      Z(x)  =  {z ∈ G with zx = xz}.

    • Conjugating x by z ∈ Z(x) has no effect: zxz⁻¹ = x. The distinct conjugates gxg⁻¹ in the conjugacy class K(x) correspond to the distinct cosets gZ(x) ∈ G/Z(x):
      |K(x)|  =  ^|G|⁄_|Z(x)| .

    • The center of G is Z(G) = {z ∈ G with zx = xz for all x ∈ G}, so Z(G) is the intersection of all Z(x) for x ∈ G.
  • Cauchy Theorem: A group whose order is divisible by a prime p has a subgroup of order p.
    If the group G has |G| = n and p is a prime with p ∣ n, then some subgroup H ⊂ G has |H| = p.
  • Note: We previously showed that any group of prime order is cyclic, so H = ⟨h⟩ for some h ≠ e with h^p = e.
  • Proof by induction on n divisible by a fixed prime p. Take P(n) to be the theorem for a specific n, applying to all groups with |G| = n.
  • Base case P(p): The smallest case with p ∣ n is n = p. In this case and G = H ≅ C_p , and P(p) holds.
  • Chain case P(n) for n > p with p ∣ n. We assume P(m) is all true for all m < n, applying to all groups smaller than |G| = n, and we proceed to prove P(n).
  • Case 1: G is commutative (abelian). Since |G| = n > p is divisible by p, it cannot be prime. Therefore G has some non-trivial subgroup G' ⊂ G with
    1 < |G'| = n' < |G| = n.
    • Case 1a. If p ∣ n', we can apply P(n') to find h' ∈ G' with |h'| = p. But h' is also an element of G, so P(n) holds.
    • Case 1b. If p ∤ n', then p does divide ⁿ⁄_n' = |G/G'|, so P(ⁿ⁄_n') applies to the quotient group G/G'. That is, there is h'G' ∈ G/G' with order p:
      (h')^p G' = (h'G')^p = eG' = G'   ⇔   (h')^p = g' ∈ G'.
      Let h = (h')^n'. Since p does not divide n':
      hG' = (h')^n' H = (h'G')^n' ≠ eG'   ⇔   h ∉ G'.
      Hence h ≠ e. Also |g'| divides n' = |G'|, so:
      h^p = (h')^pn' = (g')^n' = e.
      Thus h ∈ G has |h| = p, and P(n) holds.
  • Case 2: G is non-commutative.
    • Case 2a. If p divides the centralizer m = |Z(x)| for some x ∈ G. Since G is non-commuative, it contains some g with gx ≠ xg, so m < n = |G|, and P(m) applies to Z(x). That is, there is h ∈ Z(x) of order p, and this is also an element of G, and P(n) holds.
    • Case 2b. If p does not divide |Z(x)| for any x ∈ G. Now, G is a disjoint union of conjugacy classes K(x). Each central element z ∈ Z(G) has K(z) = {z}, and we can take representives x_i ∉ Z(G) for all other conugacy classes K(x₁), K(x₂), . . . , with x_i ∉ Z(G), have size |K(x_i)| = ^|G|⁄_|Z(xi)| . Thus:
      |G|   =   |Z(G)|  +  ∑_i ^|G|⁄_|Z(xi)| .
      Now p does not divide |Z(x_i)|, so p does divide ^|G|⁄_|Z(xi)|, as well as n = |G|. Therefore it also divides the remaining term m = |Z(G)|. Thus P(m) applies to Z(G), which contains an element h of order p, and this is also an elment of G. Thus P(n) holds.
    • In every case, if we assume P(m) for m < n, the induction proceeds to show P(n) holds. Thus P(n) is true unconditionally for all n.
  ⊞ HW  
  Prove the following:

  1. If g ∈ G with |G| = n, then gⁿ = e.
  2. For any x ∈ G, the centralizer Z(x) is a subgroup. (See notes above.)
  3. The conjugacy class K(x) = {x} if and only if x ∈ Z(G).
  4. g₁xg₁⁻¹ = g₂xg₂⁻¹ if and only if g₁Z(x) = g₂Z(x) ∈ G/Z(x), i.e. g₁g₂⁻¹ ∈ Z(x).
     This is why |K(x)| = |G/Z(x)|.
  ⊞ Soln  
  1. Proposition: If g ∈ G with |G| = n, then gⁿ = e.
  Proof: The cyclic subgroup H = ⟨g⟩ = {e, g, g², . . . , g^m−1} with g^m = e has order |g| = m. By Lagrange's Theorem, |H| = m is a factor of |G| = n = mk for some k. Thus:

  gⁿ = g^mk = (g^m)^k = e^k = e.

  2. Proposition: For any x ∈ G, the centralizer Z(x) is a subgroup.
  Proof: By definition, Z(x) = {z ∈ G with zx = xz}. For this to be a subgroup, it must be closed under multiplication and inverses. First, if z, z' ∈ Z(x), then zx = xz and z'x = xz', so zz'x = zxz' = xzz', and zz' ∈ Z(x). Thus Z(x) is closed under multiplication. Second,

  xz⁻¹ = z⁻¹(zx)z⁻¹ = z⁻¹(xz)z⁻¹ = z⁻¹x,

  so z⁻¹ ∈ Z(x), and Z(x) is closed under inverses.

  3. Proposition: K(x) = {x} if and only if x ∈ Z(G).
  Proof: By definition, K(x) = {gxg⁻¹ for all g ∈ G} and Z(G) = {x ∈ G with xg = gx for all g ∈ G}.
  The following are equivalent:

  • K(x) = {gxg⁻¹ for all g ∈ G} = {x}
  • gxg⁻¹ = x for all g ∈ G
  • gx = xg for all g ∈ G
  • x ∈ Z(G).

  4. Proposition: g₁xg₁⁻¹ = g₂xg₂⁻¹ if and only if g₁Z(x) = g₂Z(x) ∈ G/Z(x)
  Proof: The following are equivalent:

  • g₁xg₁⁻¹ = g₂xg₂⁻¹
  • g₂⁻¹(g₁xg₁⁻¹)g₁ = g₂⁻¹(g₂xg₂⁻¹)g₁
  • g₂⁻¹g₁x = xg₂⁻¹g₁
  • g₂⁻¹g₁ ∈ Z(x)
  • g₂⁻¹g₁Z(x) = Z(x)
  • g₁Z(x) = g₂Z(x)
• 11/15 Ch 1.5 Euclidean algorithm. Ch 4.1 Cryptography.   Text   Notes   ⊞ HW  
  Reading: Terras Ch 1.5 pp. 22-23, Ch 4.1, pp. 124-125. Wikipedia: Euclidean Algorithm. Bezout's Identity.

  1. Consider Z₁₀, integers modulo 10 with the operation of modular multiplication.
     1. For each element a ∈ Z₁₀ find if possible a multiplicative inverse s = a⁻¹ ∈ Z₁₀, meaning as ≡ 1 mod 10. Otherwise show this is impossible.
        Example: For a = 3, we have (3)(7) = 21 = 1 mod 10. For a = 2, if we had 2s ≡ 1 mod 10, this would mean 2s + 10t = 1 for s,t ∈ Z, with the left side even and the right side odd. This is impossible.
     2. Give a general characterization of which a ∈ Z₁₀ have inverses and which do not. How could you tell without trying all possibilities?
     3. Let (Z₁₀)^× be the set of all a ∈ Z₁₀ which have an inverse. Write the mutliplication table of this group, and show it is isomorphic to the cyclic group C₄.
     4. Check that |(Z₁₀)^×| = φ(10) = (2−1)(5−1), where φ(n) means Euler's phi-function (see also previous HW).
  2. Consider Z₁₀₀ under multiplication.
     1. Use the Euclidean Algorithm to find the inverse of 17 ∈ Z₁₀₀.
        Method: Apply the Euclidean algorithm to a = 100, b = 17 to end with:
        r_n−2 = q_nr_n−1 + r_n,         r_n−1 = q_n+1r_n
        and d = r_n = gcd(a,b) = 1. Write remainders in terms of previous remainders, starting with d = r_n = −r_n−1q_n + r_n−2, to get:
        d = r_is_i + r_i−1t_i   for decreasing i = n−1, n−2, . . . ,
        eventually reaching d = as + bt, i.e. 1 = 17s + 100t. Then 17s = 1 (mod 100) and s = 17⁻¹ (mod 100).
     2. List all the elements with gcd(a, 100) = 1. The number of such elements defines the Euler phi function φ(100).
     3. Check that φ(100) = φ(2²5²) = 2²⁻¹(2−1)5²⁻¹(5−1).
  ⊞ Soln  

  1a,b. Inverses in Z₁₀: 1•1 = 3•7 = 9•9 = 1. All other a ∈ Z₁₀ have a common divisor d with 10, which makes an inverse impossible. For example a = 5: if we could write 5b ≡ 1 mod 10, this would mean 5b + 10k = 1 with b,k ∈ Z (Bezout's equation); but this would mean 5(b+2k) = 1, meaning 5 is a divisor of 1. The contradiction means there could not have been any such b.

  1c,d. The multiplicative group G =(Z₁₀)^×:

  ×	1	3	7	9
  1	1	3	7	9
  3	3	9	1	7
  7	7	1	9	3
  9	9	7	3	1

  It is isomorphic to the cyclic group C₄ = {e, c, c², c³} with c⁴ =1, because G = ⟨3⟩ = {1, 3, 3² = 9, 3³ = 7} with 3⁴ = 81 = 1.
  The group (Z₁₀)^× for 10 = (2)(5) does indeed have (2−1)(5−1) = 4 elements.

  2a. We perform division-with-remainder repeatedly, starting with 100÷17:

  100 = 5•17 + 15     17 = 1•15 + 2     15 = 7•2 + 1.

  Reversing this, we write Bezout's formula 1 = sa + bt with successive pairs (a,b) = (15,2), (17,15),(100, 17):

  1 = 15 − 7•2 = 15 − 7•(17 − 1•15) = −7•17 + 8•15
  = −7•17 + 8•(100 − 5•17) = 8•100 − 47•17.

  Thus −47•17 = 1 mod 100, and 17⁻¹ = −47 = 53. Indeed, 53•17 = 901 ≡ 1 mod 100.

  2b,c. The numbers relatively prime to n = 100 = 2²5² are:

  (Z₁₀₀)^×  =  {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39, 41, 43, 47, 49, 51,
                          51, 53, 57, 59, 61, 63, 67, 69, 71, 73, 77, 79, 81, 83, 87, 89, 91, 93, 97, 99}.

  There are indeed 2•(2−1)•5•(5−1) = 40 of these.
• 11/17 Ch 4.1 RSA Cryptography.   ⊞ Text   Notes 1 2 3  
  • Reading: Terras Ch 4.1 pp. 124-128, Ch 3.6 p. 110.
  • Crypto-system
    • Goal: Send a message m through public channels in a coded form x which cannot be read by eavesdroppers, but which can be decoded back to m by the intended recipient.
    • Classical crypto-systems rely on a codebook shared privately beforehand between the sender and recipient. But on the internet, millions of senders and recipients need to exchange private messages with no previous private communication.
    • Public-key crypto-systems generate a pair of keys (a, b) for each possible recipient.
      • The public key a is announced to everyone, and is used by any sender to encode messages to that specific recipient: the sender encodes m to
        x = m ↓ a,
        combining m with a using a public scrambling operation ↓.
      • The private key b is known only to the recipient, who can use it to recover the original message
        m = x ↑ b,
        decoding x by combining it with b via a public retrieval operation ↑. That is, ↓a and ↑b are inverse operations.
    • This relies on knowing a "trap-door operation" ↓a which practically cannot be reversed without being given the retrieval key ↑b, even though everyone knows a and both operations ↓ and ↑.
  • Modular multiplication crypto-system: a baby version of public-key crytography.
    • Represent a message by an integer m ∈ Z_n for some large n.
    • Let (a, b) be inverses mod n:   b = a⁻¹ ∈ (Z_n)^×, the multiplicative group.
    • Encode using the public keys a, n and multiplication:   x = m ↓ a = m · a mod n.
      Decode using the private key b:   m = x ↑ b = x · b.
      This works because the two keys are inverses with ab = 1 mod n, so that:

      x · b  =  m · a · b  =  m · 1  =  m  mod  n

    • This code can be broken using some math. Knowing the public information a and the multiplication mod n, we can use the Euclidean Algorithm to efficiently solve the equation as + nt = 1, giving the reciprocal s = b = a⁻¹ mod n to decode the scrambled message x.
  • RSA Crypto-system
    • Consider a product of two distinct primes n = pq, with
      (Z_n)^×  =  {k ∈ Z_n with gcd(k,n) = 1}.
      The number of elements is:
      φ(n)  =  |(Z_n)^×|  =  (p−1)(q−1).
      More generally, for any n with prime factorization n = p₁^d₁p₂^d₂···, we have φ(n) = (p₁−1)p₁^d₁−1(p₂−1)p₂^d₂−1 ···.
    • For any group G, we have g^|G| = e for any g ∈ G, since |g| divides |G| by Lagrange.
      Since φ(n)  =  |(Z_n)^×|, we have for any m ∈ (Z_n)^×:
      m^φ(n) = 1 ∈ (Z_n)^×.

    • For coding, we compute in two multiplicative groups:
      • Messages (original and coded) are m, x ∈ (Z_n)^×, modulo n.
      • Exponents (taking powers of messages) are α, β ∈ (Z_φ(n))^×, modulo φ(n).
    • The public key is some α ∈ (Z_φ(n))^×.
      The private key is the inverse β  =  α⁻¹ ∈ (Z_φ(n))^×.
    • Encode by raising to the α power:   x = m ↓ α = m^α mod n.
      Decode by raising to the β power:   m = x ↑ β = x^β mod n.
      This works because αβ = 1 + k φ(n) and m^φ(n) = 1, so:

      x^b  =  m^αβ  =  m¹m^{k φ(n)}  =  m¹(m^φ(n))^k  =  m.

    • This code has proven to be secure, because even knowing n = pq (but not p or q), it is not practical to find φ(n) = (p−1)(q−1), due to the difficulty of factoring large integers. (This difficulty has been verified by the failure of many attempts, but has not been proven.)
  • RSA Example
    • Take n = pq = 5·11, so φ(n) = (p−1)(q−1) = 4·10 = 40.
    • Messages are in the multiplicative group modulo n = 55 having φ(n) = 40 elements:

      m, x  ∈  (Zn)×  =  (Z55)×  =

      {1, 2, 3, 4, 6, 7, 8, 9, 12, 13, 14, 16, 17, 18, 19,   21, 23, 24, 26, 27, 28, 29, 31, 32, 34, 36, 37, 38, 39, 41, 42, 43, 46, 47, 48, 49, 51, 52, 53, 54}.

      Since this group has 40 elements, we have m⁴⁰ = 1 mod 55 for all m ∈ (Z₅₅)^×.
    • Exponents are in the multiplicative group modulo φ(n) = 40:
      α, β  ∈  (Z_φ(n))^× = (Z₄₀)^× = {1, 3, 7, 9, 11, 13, 17, 19, 21, 23, 27, 29, 31, 33, 37, 39}.

    • The keys are inverse exponents α, β ∈ (Z₄₀)^×. Choose α = 3, β = α⁻¹ = 27 mod 40, so that
      αβ = 3·27 = 81 = 1 mod 40.

    • Encode message m = 2:
      x = m^α = 2³ = 8 mod 55.

    • Decode message x = 8. Since β = 27 = 2⁴ + 2³ + 2 + 1, we compute mod 55:
      8² = 64 = 9 mod 55,     9² = 81 = 26 mod 55     26² = 16 mod 55
      
      m = x^β = 8²⁷ = (((8²)²)²)² ((8²)²)² 8² 8 = ((9²)²)² (9²)² 9·8
      = (26²)² 26² 17 = 16² 16·17 = 2 mod 55.
      That is, we recover m = 2 mod 55.
    • This works because
      αβ = 3·27 = 81 = 1 + 2·40,
      
      x^β  =  m^αβ  =  m¹(m⁴⁰)²  =  m  mod  55.

  ⊞ HW   HW Soln (see #3,4)   Q25 Soln
  1. For each of the following modular multiplication groups, either find a generator showing the group is cyclic, or show that it is not cyclic by examining the orders of elements.
     a. (Z₁₁)^×     b. (Z₁₅)^×
  2. Consider the following small version of the RSA encoding algorithm.
     • A message m consists of a single letter represented by a number according to A = 2, B = 3, . . . , Z = 27, to be securely transmitted only to a specific recipient.
     • The message is encoded into the number x = m^a mod n, where a = 11 and n = 1147.
     • The coded message is decoded by computing m = x^b mod n, where 11b ≡ 1 mod φ(n).
     • Here the public key, known to all, is (a,n) = (11, 1147); this is all anyone needs to encode a message m. The private key, known only to the decoder, is b = a⁻¹ mod φ(n); this is easy to compute once you know the factorization of n, and hence φ(n).
     Problems
     1. Factor n = 1147 by hand (or a simple calculator), showing your work. The point is to realize how difficult factorization is even for relatively small numbers.
     2. Compute φ(n) from the factorization in (a). It is significant because φ(n) = |(Z_n)^×| = #{k ∈ Z_n with gcd(k,n) = 1}.
     3. Find b with ab ≡ 1 mod φ(n), where a = 11, using the Extended Euclidean Algorithm.
     4. Verify by computation that (m^a)^b = m mod n for one or two message numbers m ∈ (Z_n)^×.
        Hint: For arithmetic shortcuts, see Terras p. 125-6. For example, from the binary expression 11 = 2³ + 2 + 1, you can compute m¹¹ = ((m²)²)² m² m, which uses fewer operations than multiplying 11 times.

  ---

• 11/20 Ch 6.2 Chinese Remainder Thm.   ⊞ Text   Notes 2 3  
  • Reading: Terras Ch 6.2 p. 193.
  • Chinese Remainder Theorem: If gcd(m,n) = 1, then there is an isomorphism C_m× C_n ≅ C_mn
    • Proof: Let
      • C_m = ⟨a⟩ with a^m = e,
      • C_n = ⟨b⟩ with bⁿ = e,
      • C_mn = ⟨c⟩ with c^mn = e,
      Define:
      T(aⁱ, b^j)  =  c^{(ni + mj)}.
      T is well-defined, regardless of chosen representatives of the exponents; we have (a^i+km, b^j+ℓn) = (aⁱ, b^j), and both give the same value of T:
      T(a^i+km, b^j+ℓn)  =  c^{n(i+km) + m(j+ℓn)}  =  c^ni+mj c^nm(k+ℓ)  =  c^ni+mj  =  T(aⁱ, b^j).

    • T is clearly a homomorphism (respects multiplication): T((aⁱ, b^j)·(a^i', b^j')) = T(aⁱ, b^j) · T(a^i', b^j').
    • T is also one-to-one and onto. Use the Extended Euclidean Algorithm to find a solution to Bezout's Formula ms + nt = 1. Then:
      T(a^tk, b^sk)  =  c^{ntk + msk}  =  c^{(nt + ms)k}  =  c^k.
      Thus T is onto, with inverse T⁻¹(c^k) = (a^tk, b^sk). In fact, (a^t, b^s) is a cyclic generator of the whole group C_m× C_n.
      Therefore T is also one-to-one, since the groups on the two sides have the same size.
  ⊞ HW   Soln (see #1,2)
  1. Proposition: For any element g of a group G of order |G| = n, we have gⁿ = e. Prove this using Lagrange's Theorem.
  2. The Chinese Remainder Theorem guarantees the group isomorphism C₃×C₁₁ ≅ C₃₃. Verify this using the folling steps:
     1. Solve Bezout's Formula 3s + 11t = 1 by the Extended Euclidean Algorithm.
     2. Use the result of (a) to produce an explicit isomorphism T : C₃×C₁₁ → C₃₃, as well as the inverse T⁻¹. (Define these by algebraic formulas.)
     3. Find the single cyclic generator of the whole group C₃×C₁₁, and write a table of its powers, verifying that they cover all 33 elements of C₃×C₁₁. Hint: Write C₃ = ⟨a⟩, C₁₁ = ⟨b⟩, C₃₃ = ⟨c⟩, and recall that (a,e) corresponds to some cⁱ with (cⁱ)³ = e, and (e,b) corresponds to c^j with (c^j)¹¹ = e.
  3. Extra Credit: Prove or disprove: If gcd(m,n) = 1, then (Z_m)^× × (Z_n)^× ≅ (Z_mn)^×.
• 11/23-26 Thanksgiving Break

  ---

• 11/27 Ch 5.1-5.3 Rings and fields.   ⊞ Text   Notes 1 2 3  
  Reading: Terras Ch 5, pp. 157-173.

  • A ring (R,+, · ) is a set with addition and multiplication operations satisfying the minimum properties for much of our familiar algebra
    • Properties: Addition (R,+) forms an abelian group: associative, commutative, with identity denoted 0 and negatives −a. Subtraction a − b means a + (−b).
      Multiplication is associative but not necessarily commutative, with identity denoted 1 (with 1 ≠ 0), but not every a ∈ R need have a reciprocal a⁻¹.
    • There is a multiplicative group of invertible elements (R^×, · ), where R^× = {a ∈ R such that a⁻¹ ∈ R}. This always contains 1, but possibly no other elements.
    • A field F is a ring with commutative multiplication where every non-zero element has a reciprocal, F^× = F−{0}. Division a/b means ab⁻¹ = b⁻¹a.
      Fields have enough properties for almost all elementary algebra to be valid, e.g. the Quadratic Formula.
    • Zero-divisors are non-zero elements of R whose product is zero: a,b ≠ 0 with ab = 0. A zero-divisor can never have an inverse.
  • Examples of rings
    • Integers Z, a commutative ring with Z^× = {±1} and no zero divisors
    • Fields of ordinary numbers: rationals Q, reals R, complex numbers C
    • Modular arithmetic Z_n, a commutative ring with Z_n^× = {k with gcd(k,n) = 1}, and all non-invertible elements are zero-divisors. This is a field whenever n = p, a prime number.
    • Matrix ring M_n(F), n×n matrices with entries in a field F, a non-commutative ring; all non-invertible matrices are zero-divisors
    • Ring of polynomials with coefficients in a field:
      F[x]  =  {f(x) = a₀ + a₁x + ··· + a_nxⁿ  for a_j ∈ F and n ≥ 0},
      a commutative ring with no zero-divisors and with F[x]^× = {constant polyonmials f(x) = a₀}
  • Ring proofs. The basic algebraic formulas below do not need to be required in the definition of a ring: they follow necessarily from the most basic properties which are in the definiton.
    1. Lemma: −(−a) = a for all a ∈ R.
       Proof: By definition, −(−a) + (−a) = 0. Adding a to both sides gives −(−a) + (−a) + a = a, i.e. −(−a) + 0 = a and −(−a) = a.
    2. Lemma: 0a = a0 = 0 for all a ∈ R.
       Proof: By distributivity, 0a + 0a = (0+0)a = 0a. Adding −0a to both sides gives 0a + 0a − 0a = 0a − 0a, i.e. 0a = 0. Similarly for a0 = 0.
    3. Lemma: (−a)b = a(−b) = −(ab) and for all a,b ∈ R.
       Proof: By distributivity and lemma (ii), (−a)b + ab = (−a + a)b = 0b = 0. Adding −(ab) to both sides gives (−a)b + ab + −(ab) = −(ab), i.e. (−a)b = (−a)b + 0 = −(ab). Similarly for a(−b) = −(ab).
    4. Lemma: (−a)(−b) = ab for all a,b ∈ R.
       Proof: Applying lemma (iii) twice, (−a)(−b) = −(a(−b)) = −(−(ab)), which equals ab by lemma (i).
  ⊞ HW  
  1. For each of the following rings R, say whether it is commutative (in multiplication), whether it has zero-divisors, and whether it is a field.
     1. R = Z₁₂
     2. R = Z₁₃
     3. R = M₂(R), the 2×2 matrices under the usual addition and multiplication.
  2. Consider R = {a+b√2 for a,b ∈ Q}, the set of real numbers equal to a fraction plus a fraction times the square root of 2. Show that R is a ring, checking each property in the definition of a ring.
  3. Zero-divisors.
     1. Show that a zero-divisor of a ring can never have an inverse.
     2. Is the converse true? That is: if an element does not have an inverse, then it is a zero-divisor.
  4. Ring properties. Let (R,+, · ) be a commutative ring (commutative multiplication), without zero-divisors (ab = 0 only for a = 0 or b = 0), and with 1+1 ≠ 0 in R (the characteristic is not 2). Give short proofs of the following.
     1. If a² = b² for a,b ∈ R, then a = b or a = −b.
     2. Consider a general quadratic equation ax² + bx + c = 0 with a,b,c ∈ R, a ≠ 0. This has a solution x ∈ R if and only if there is d ∈ R with d² = b² − 4ac, and in this case the two solutions are ^{(−b ± d)}⁄_2a .
        Hint: Use the standard complete-the-square argument, noting at each step why it is valid for R.
     3. Show that the above formulas do not work for R = M₂(R), the ring of 2×2 real matrices. In fact, show that there are infinitely many matrices X with X² = I. Hint: Diagonalize X = PDP⁻¹.
  ⊞ Soln  
  1a. R = Z₁₂ is commutative. An element k ≠ 0 is a zero-divisor when it has a common factor with 12: i.e. k = 2,3,4,6,8,9,10; the other elements are invertible: (Z₁₂)^× = {1,5,7,11}. Since not every non-zero element is invertible, R is not a field

  1b. R = Z₁₃ is commutative. An element k ≠ 0 is a zero-divisor when it has a common factor with 13, but since 13 is prime there is no such k. In fact Z₁₃ is a field, with every non-zero element invertible. Indeed, for any k ≠ 0, use the Euclidean algorithm to solve ks + 13t = 1 for integers s,t; then ks = 1 ∈ R.

  1c. R = M₂(R) does not have commutative multiplication, so it is not a commutative ring. Also, any singular matrix X with det(X) = 0 is a zero-divisor, for example, XY = 0 for X = [

  1	0
  0	0

  ], Y = [

  0	0
  0	1

  ].

  2. R = {a+b√2 for a,b ∈ Q} is a field. First, (R, + ) is a commutative group: it is closed under addition, and since the addition is the same as that of real numbers, it is associative and commutative. R contains 0 = 0 + 0√2, and −(a+b√2) = (−a)+(−b)√2 ∈ R, so R contains negatives.

  Second, R is closed under multiplication:

  (a+b√2)(c+d√2)  =  ac + ad√2 + bc√2 + bd(√2)²  =  (ac+2bd) + (ad+bc)√2  ∈  R.

  Since multiplication is the same as that of real numbers, it is associative and commutative, and has no zero-divisors. Finally, 1 = 1 + 0√2 ∈ R, and R contains the inverse of any a+b√2 ≠ 0:

  ¹⁄_(a+b√2)  =  ¹⁄_(a+b√2) · ^(a−b√2)⁄_(a−b√2)  =  ^(a−b√2)⁄_(a²−2b²)  =  ^a⁄_(a²−2b²) − ^b⁄_(a²−2b²) √2  ∈  R

  Note that the denominator is never zero unless a = b = 0, since √2 is irrational, i.e. √2 ≠ ^a⁄_b , so a²−2b² ≠ 0. Therefore R is a field.

  3a. Proposition: If R is a ring and a ∈ R is a zero-divisor, then a is not invertible.

  First Proof: By definition, the zero-divisor a has ab = 0 for some b ≠ 0. Then we have (ca)b = c(ab) = c(0) = 0 ≠ b. Since (ca)b ≠ b, by definition ca ≠ 1 for any c ∈ R, so a has no inverse.

  Second Proof: If an element a were both a zero-divisor and invertible, we would have some b, c ≠ 0 with ab = 0 and ac = ca = 1. Then we would have 0 = c0 = cab = 1b = b, so b = 0 which contradicts our assumptions. Therefore a could not be both a zero-divisor and invertible; and if a is a zero-divisor, it is not invertible.

  3b. It is not true in general that a non-invertible element is a zero-divisor. A counter-example is the ring R = Z, which contains no zero-divisors since ab ≠ 0 for any integers a,b ≠ 0. However, the only invertible elements are ±1, since otherwise ¹⁄_a ≠ Z.

  4. See here #1.

• 11/29 Extension fields: intro   ⊞ HW  
  1. The polynomial equation x³ + x − 1 has a unique real number solution x = α ≈ 0.682, as you can see from the graph. There is no nice expression for the irrational number α, but we can compute with it using its defining property:
     α³ + α − 1  =  0;     equivalently:     α³  =  1 − α.
     Define the extension field
     F  =  Q(α)  =  {a + bα + cα²  for  a,b,c ∈ Q}.
     1. Show that F is closed under addition, subtraction, and multiplication. (We will consider division later.)
     2. Write α⁹ in the standard form a+bα+cα². Hint: α⁹ = (α³)³.
  2. Now consider the field Z₂ = {0,1 mod 2}, so that 2 = 0 and −1 = 1. Let α be a solution of x² + x + 1 = 0: that is, α has the defining property:
     α² + α + 1  =  0;     equivalently:     α²  =  1 + α.
     Note that signs are irrelevant here, since −α = (−1)α = α. Define the 4-element extension field
     F  =  Z₂(α)  =  {a + bα  for  a,b ∈ Z₂} = {0, 1, α, 1+α}.
     1. Write the 4×4 addition table for F.
     2. Write the 4×4 multiplication table for F. That is, reduce each product to standard form a + bα.
     3. Use the table to check that every non-zero element of F is invertible, so that F is indeed a field.
     4. Is the additive group (F, + ) isomorphic to cyclic group (Z₄, + ) ≅ C₄?
        Is the multiplicative group (F^×, · ) isomorphic to (Z₄^×, · )?
        Putting these together, are F and Z₄ isomorphic as rings? That is, is there a one-to-one correspondence of the 4 elements which turns both the addition and multiplication tables of F into those of Z₄?
     5. Check that every quadratic equation ax² + bx + c = 0 has a solution x = γ ∈ F, not just the original equation x² + x + 1 = 0. Does the Quadratic Formula give these solutions?
  3. Let β be a solution of x³ + x + 1 = 0 over the base field Z₂: that is, β has the defining property:
     β³ + β + 1  =  0;     equivalently:     β³  =  1 + β.
     Define the extension field
     K  =  Z₂(β)  =  {a + bβ + cβ²  for  a,b,c ∈ Z₂}.
     1. List all the elements of K. How could you predict that there are 2³ = 8 elements without listing?
     2. Show that the multiplicative group (K^×, · ) is isomorphic to the cyclic group C₇. In fact, show that β is a generator, so that every non-zero element of K is a power βⁱ.
     3. Check that every monic cubic equation x³ + ax² + bx + c = 0 has a solution in x = γ ∈ K, not just the original equation x³ + x + 1 = 0.
  ⊞ Soln  

  1b. Corrected. α⁹ = (α³)³  =  (1−α)³  =  1 − 3α + 3α² − α³  =  1 − 3α + 3α² − (1 − α)  =  −2α + 3α².

  2a,b,c. See Wikipedia.

  2d. The additive group (F, + ) is isomorphic to the Klein 4-group C₂ × C₂, not to C₄. The multiplicative group F^× = F−{0} has 3 elements, whereas Z₄^× = {1, 3} has only 2 elments; they cannot be isomorphic. Consequently, the ring F (a field) cannot be isomorphic to the ring Z₄ (having zero-divisors).

  2e. The Quadratic Formula makes no sense over the base ring Z₂, since it divides by 2 = 0. However, we can solve each equation by guess-and-check, since there are only 4 elements altogether. In fact:

  x² + x + 1 = (x − α)(x − (α+1)),     x² + 1 = (x − 1)²,     x² + x = x(x − 1),

  and of course every linear equation (a = 0) has an immediate solution.

  3a,b. See Wikipedia.

  3c. The monic cubic polynomials are x³, x(x + 1)², x(x² + x + 1), (x + 1)³, which clearly have solutions x = 0 or 1, and two irreducible polynomials (unfactorable in Z₂[x]) x³ + x + 1 and x³ + x² + 1, which each have three solutions in F, accounting for the 2 + 3 + 3 = 8 total elements.

• 12/1 Extension fields: division   ⊞ Notes  
  • Algebraic number fields
    • An algebraic number α is a real or complex number which is a root of an equation with rational coefficients: that is, f(α) = 0 for some polynomial:
      f(x)  =  a₀ + a₁x + ··· + a₁xⁿ  ∈  Q[x],   where   a₀, . . . , a_n ∈ Q.
      (Here Q[x] is the ring of all polynomials with coefficients in Q.) For example, α = √2 is a root of x² − 2 = 0, and i = √(−1) is a root of x² + 1 = 0. The roots of a generic higher-degree polynomial like x⁵ − x + 1 are algebraic, but cannot be written in terms of radicals.
    • We compute with any algebraic number α using abstract algebra as we do with simple algebraic numbers like √2 using high school algebra. For this, we define Q[α]  =  {g(α) for g(x) ∈ Q[x]}, the polynomials in α. This is clearly a commutative ring, and we will show it is a field containing reciprocals.
    • We assume f(α) = 0 for f(x) an irreducible polynomial (i.e. no non-trivial factorizations in Q[x]).
    • In fact, this ring is a field, with every expression g(α) having a reciprocal h(α) with  g(α)h(α) = 1, i.e.  g(x)h(x) ≡ 1 mod f(x), i.e.
      g(x)h(x) = 1 + q(x)f(x)   for some   q(x) ∈ Q[x] .
      We can find the correct h(x) and q(x) using the Extended Euclidean Algorithm.
  • Example: f(x) = x³ + x − 1 = 0 has a unique real root x = α ≈ 0.682 .
    • Long division of polynomials gives any polynomial as g(x) = q(x)f(x) + r(x)  where  r(x) = a + bx + cx², so we can write any g(α) ∈ Q[α] in standard form:
      g(α)  =  q(α)f(α) + r(α)  =  0 + a + bα + cα².
      For example: x⁴  =  x f(x) + x − x², so α⁴  =  α − α².
    • We find the reciprocal ¹⁄_(1+α) in standard form. Long division gives: x³ + x − 1   =   (x²−x+2)(1+x) − 3. Dividing by 3 and rearranging, we get:
      (1+x) ⅓(x²−x+2) − (x³+x+1)   =   1
      Substituting x = α, the second term vanishes, and we get (1+α) ⅓(α²−α+2) = 1, so the reciprocal is:
      ¹⁄_(1+α)   =   ⅓α² − ⅓α + ⅔.
      In general, we would have to go through the longer Extended Euclidean Algorithm.
  ⊞ HW  
  1. Polynomial rings. Consider the polynomials
     f(x) = x⁴ + x³ + 2x² + x + 1  ,  g(x) = x⁴ − x³ + 2x² − x + 1  ∈  Q[x].
     1. Find the gcd of these polynomials using the Euclidean Algorithm.
     2. Give the complete factorization of f(x) and g(x) in Q[x], i.e. into polynomials with rational coefficients, and also in C[x], allowing factors with complex coefficients.
        Hint: A polynomial with no factors in Q[x] will still have a complex root x = γ, which produces a linear factor (x−γ) ∈ C[x].
  2. Consider the field Q[α], where α is the unique real root of the polynomial
     f(x) = x³ + 3x − 1.
     Compute the following numbers in the standard form a + bα + cα²   for a,b,c ∈ Q.
     1. Use Division with Remainder to compute α¹⁰.
     2. Use the Extended Euclidean Algorithm to find the reciprocal ¹⁄_(α²+1).
  3. Fields of characteristic 3. Let Z₃ = {0,1,2} = {0, ±1} with 3 = 0 ∈ Z₃.
     1. Determine all irreducible polyomials of the form x² + bx + c ∈ Z₃[x].
     2. Construct the field F₉ = Z₃[α], where α satisfies α² + α − 1 = 0. In particular, give complete addition and multiplication tables for the 9 elements of the form a + bα for a,b ∈ Z₃.
        
     3. Verify that F₉ is a field: what properties are needed?
  Soln (see #2,3,4)

  ---

• 12/4 Extension fields: quotient rings ⊞ Notes  
  • To construct extension fields in a rigorous way, we adapt the construction of modular arithmetic (Z_n , + , · ).
    • If we focus only on the addition operation, this can be thought of as a quotient group G/N: the quotient of the infinite cyclic group of integers G = (Z , + ) by the cyclic subgroup N = (n) = {kn for k ∈ Z}:
      Z_n  =  G / N  =  Z / (n)  =  {a + (n) for a ∈ Z},

      cosets [a] = a + (n) = {a + kn for k ∈ Z}.

      Each element [0], [1], . . . , [n−1] ∈ Z_n is a coset, the shift of (n) by some element a ∈ Z. We have:
      a ≡ a' mod n   ⇔   a' = a + kn   ⇔   [a] = [a'].
      For example, n is "crushed" to 0 in Z_n: that is, [n] = [0] because [n] = n + (n) and [0] = (n) are the same set, the multiples of n.
    • In the quotient group, addition is by [a] + [b] = [a+b], and we can make it a ring by defining multiplication by [a]·[b] = [ab]. The ring properties for (Z/(n) , + , · ) are then inherited from (Z , + , · ).
      We have to check this is well-defined: if we take equivalent representatitives [a] = [a'] and [b] = [b'], the sum and product do not change:
      a' + b'  =  (a+kn) + (b+ℓn)  =  a + b + (k+ℓ)n,
      
      a'b'  =  (a+kn)(b+ℓn)  =  ab + aℓn + bkn + kℓn²  =  ab + (aℓ+bk+kℓn)n.
      That is, [a+b] = [a'+b'] and [ab] = [a'b'].
  • Extension field F(α) as a quotient ring
    • Suppose a base field F does not contain a solution x = α to a particular polynomial equation
      f(x)  =  a₀ + a₁x + ··· + a_nxⁿ  =  0.
      We can construct an extension field that does contain a solution. Start with the polynomial ring:
      R  =  F[x]  =  {g(x) = b₀ + b₁x + ··· + b_nxⁿ  for  b_i ∈ F and n ≥ 0}.
      Now take the quotient by the subgroup (called an ideal) I = (f(x)) = {g(x)f(x) for g(x) ∈ F[x]}, the multiples of the particular polynomial f(x).
    • The quotient is:
      R/I  =  F[x] / (f(x))  =  {cosets [a(x)] for a(x) ∈ F[x]},
      The elements are cosets:
      [a(x)]  =  a(x) + (f(x))  =  {a(x) + g(x)f(x) for g(x) ∈ F[x]}.
      All multiples of f(x) are crushed to zero, and elements are modulo f(x):
      a(x) ≡ a'(x) mod f(x)   ⇔   a'(x) = a(x) + g(x)f(x)   ⇔   [a(x)] = [a'(x)].

    • Operations: [a] + [b] = [a+b] and [a]·[b] = [ab].
    • If f(x) is irreducible, with no factors (except constants) in F[x], then every [a(x)] ≠ [0] has an inverse [a(x)]⁻¹ = [s(x)] which can be computed using the Euclidean Algorithm, finding s(x), t(x) with:
      a(x)s(x) + f(x)t(x) = 1.

    • Define:
      α  =  [x]  =  {x + g(x)f(x) for g(x) ∈ F[x]}.
      Now comes the miracle: substitute α into the polynomial f(x):
      f(α)  =  f([x])  =  a₀ + a₁[x] + ··· + a_n[x]ⁿ
       =  [a₀+a₁x+···+a_nxⁿ]  =  [f(x)]  =  [0].
      That is, α = [x] satisfies the equation f(α) = 0 in the field F[x]/(f(x)).
    • Since F[x]/(f(x)) is generated by α = [x], we denote it as F[α] or F(α).
• 12/6 Finite fields: uniqueness   ⊞ Notes  
  Reading: Terras Ch 7.5-7.6 pp. 233-243.
  Theorem: For q = pⁿ with p prime (called the charcteristic), there is exactly one field F_q with q elements, up to isomorphism. There are no other finite fields.
  Example: F₈ with q = 8 = 2³. We give two different constructions of F₈, and show they are isomorphic.

  • Base field Z₂ = {0, 1} with 2 = 0 and −1 = 1.
  • There are two irreducible (unfactorable) polynomials of degree 3 in Z₂[x]:
    f(x) = x³ + x + 1,           g(x) = x³ + x² + 1,
    with roots f(α) = 0 and g(β) = 0, so that:
    α³ = α + 1,           β³ = β² + 1.
    
    Two 8-element extension fields:
    Z₂(α)  =  {aα²+bα+c for a,b,c ∈ Z₂},           Z₂(β)  =  {aβ²+bβ+c for a,b,c ∈ Z₂}.
    Why are these isomorphic?
  • The degree 3 polynomial f(x) should have three roots α₁ = α and α₂, α₃, so that
    f(x)  =  (x−α₁)(x−α₂)(x−α₃).
    In fact, these can all be found in Z₂(α) using symmetry!
    • An algebraic symmetry or automorphism of a field F is a one-to-one mapping Φ : F → F which respects (distributes over) addition and multiplication: for all γ₁, γ₂ ∈ F,
      Φ(γ₁+γ₂)  =  Φ(γ₁) + Φ(γ₂),           Φ(γ₁γ₂)  =  Φ(γ₁)·Φ(γ₂).
      In our case, there is the very simple Frobenius automorphism:
      Φ(γ)  =  γ^p  =  γ².
      This respects addition and multiplication because:
      (γ₁+γ₂)²  =  γ₁² + 2γ₁γ₂ + γ₂²  =  γ₁² + γ₂²,           (γ₁γ₂)²  =  γ₁² γ₂².
      For any field F, its symmetry group of automorphisms is called the Galois group G = Gal(F).
      In our example, Gal(F₈) = {I, Φ, Φ²} with Φ³ = I; that is, G ≅ C₃.
    • Claim: If α ∈ F is a root of f(x) = 0, and Φ is an automorphism of F, then Φ(α) ∈ F is also a root of f(x) = 0.
      Proof: Suppose f(α) = α³ + α + 1 = 0. Then:
      f(Φ(α))  =  Φ(α)³ + Φ(α) + 1  =  Φ(α³) + Φ(α) + Φ(1)  =  Φ(α³+α+1)  =  Φ(f(α))  =  Φ(0)  =  0.

    • Thus the three roots of f(x) are:
      α₁ = α,       α₂ = Φ(α) = α²,       α₃ = Φ(Φ(α)) = α⁴ = α² + α.
      Now, the Linear Factor Theorem says that a root f(γ) = 0 implies that (x−γ) is a factor of f(x). Hence we get the factorization:
      f(x)  =  (x−α₁) (x−α₂) (x−α₃).

  • Surprise! The Z₂(α) field contains a solution of g(x) = 0, namely β = α+1. (Check g(α+1) = 0 by computation.)
    • The other two roots of g(x) are also in Z₂(α):
      β₁ = β = α + 1,       β₂ = Φ(β) = β² = α² + 1,       β₃ = Φ(Φ(β)) = β⁴ = α² + α + 1.

    • Thus, we have an isomorphism T : Z₂(β) → Z₂(α) given by T(β) = α+1 and:
      T(aβ² + bβ + c)  =  a(α+1)² + b(α+1) + c.

    • That is, these two possible fields of 8 elements are the same up to isomorphism, as claimed by the Theorem.
  • The isomorphism Z₂(α) ≅ Z₂(β) is no coincidence, but will work in general. How to know without computation that there must be a root β of g(x) = 0 inside the field constructed from a root α of f(x) = 0?
    • For a field F with q elements, consider its multiplicative group G = (F^×, · ) of q−1 non-zero elements F^× = F−{0}.
    • For any group element g ∈ G, recall that g^|G| = e, since the order of g must be a divisor of |G|.
      In our case, for any γ ∈ F^×, we have γ^q−1 = 1, meaning every γ ≠ 0 is a root of x^q−1 − 1 = 0. Multiplying by x, we find that every γ ∈ F is a root of the universal polynomial x^q − x = 0.
      By the Linear Factor Theorem, this means every (x−γ) is a factor of x^q − x , and we get the factorization:
      x^q − x  =  (x−γ₁) (x−γ₂) ··· (x−γ_q),
      where F = {γ₁, . . . , γ_q}.
    • In our case F = Z₂(α), the universal polynomial has q = 8 linear factors:
      x⁸ − x  =  x (x−1) (x−α) (x−α²) (x−(α²+α)) ··· (x−(α²+α+1)),
      These factors include (x−α₁)(x−α₂)(x−α₃) = f(x), so f(x) is a divisor of x⁸ − x.
      Repeating this for the other 8-element F = Z₂(β), we find that g(x) is also a divisor of the same universal polynomial x⁸ − x. Since both f(x) and g(x) are factors, we get:
      x⁸ − x  =  x(x−1) f(x) g(x)  =  x (x−1) (x³+x+1) (x³+x²+1)  =  (x−γ₁) (x−γ₂) ··· (x−γ₈).
      This shows that the elements of any 8-element field F = {γ₁, . . . , γ₈} include the roots of both f(x) and g(x).
    • Generalizing this to any q = pⁿ proves the first part of the Theorem.
  • Why are there no other fields?
    • First, every finite field F must contain a prime ring R = {0, 1, 1+1 = 2, . . . , k−1} ≅ Z_k. Since this is inside a field, it cannot have any zero-divisors, so we must have k = p prime, which gives our base field Z_p ⊂ F.
    • F is a vector space over Z_p of some dimension n, and its elements can be written with n coordinates in Z_p with respect to some basis. Thus |F| = q = pⁿ.
    • The multiplicative group (F^× , · ) is cyclic. Indeed, if the maximum order of an element of F^× were N < |F^×| = q−1, then the polynomial x^N − 1 would have more than N roots, which is impossible by the Linear Factor Theorem and Unique Factorization in Z_p[x]. Thus F^× has an element of order q−1, making it a cyclic group.
    • If a cyclic generator α of F^× were the root of a polynomial of degree d < n, we could reduce every element α^j ∈ F^× to a polynomial in α of degree d−1, so that |F| ≤ p^d < pⁿ = q, contradicting our assumption. Thus α can only satisfy an irreducible of degree n, and F = Z_p(α).
  ⊞ HW  
  Consider the field F = Z₃(α) with α² = 2, the field with q = 9 = 3² elements considered in HW 12/1.

  1. Find a generator δ of the multiplicative group F^× ≅ C_q−1 = C₈.
     Write each non-zero element aα+b as a power δ^j.
     Hint: The number of choices for the generator δ is φ(8) = 4, since the integers relatively prime to 8 are {1,3,5,7}.
  2. Explain why every element of F is a root of the universal polynomial x⁹ − x.
  3. Show that the Frobenius mapping Φ(γ) = γ³ is an isomorphism of F.
     Explain why Φ² = I, so that we have the Galois group Gal(F) = {I, Φ} ≅ C₂.
  4. Find all the irreducible polynomials x² + bx + c ∈ Z₃[x], and use them to factor the universal polynomial x⁹ − x.
  5. Split the 9 elements of F into singletons a ∈ Z₃ and pairs β, Φ(β) using the action of the Galois group Gal(F) = {I, Φ}.
  6. Write each monic quadratic polynomial irreducible as (x−β₁)(x−β₂), explicitly identifying its roots β₁ = β and β₂ = Φ(β). This shows that F contains the roots of all these polynomials, so any extension field Z₃(β) is isomorphic to our F = Z₃(α).
  ⊞ Soln  

  1. Clearly 1, 2, α, 2α are not generators. The remaining elements must be the 4 possible generators: δ = α+1, α+2, 2α+1, 2α+2. For example:

  δ = α+1,   δ² = 2α,   δ³ = 2α+1,   δ⁴ = 2,   δ⁵ = 2α+2,   δ⁶ = α,   δ⁷ = α+2,   δ⁸ = 1.

  2. For any γ = δ^j, we have

  γ⁸  =  δ^8j  =  1^j  =  1,     so     γ⁸ − 1 = 0

  Thus all γ ≠ 0 are roots of x⁸ − 1 = 0, and all γ are roots of  x⁹ − x = x(x⁸ − 1) = 0.

  3. The Frobenius mapping preserves addition and multiplication because:

  (γ₁+γ₂)³  =  γ₁³ + 3γ₁²γ₂ + 3γ₁γ₂² + γ₂³  =  γ₁³ + γ₂³,           (γ₁γ₂)³  =  γ₁³ γ₂³.

  Now the universal equation γ⁹ − γ = 0 implies Φ²(γ) = (γ³)³ = γ, meaning Φ² = I.

  4. A quadratic polynomial is reducible if and only if it has linear factors:

  x² + 2 = (x+1)(x+2),       x² + 2x + 1 = (x+1)²       x² + x + 1 = (x+2)².

  The irreducibles are the remaining x² + bx + c with c ≠ 0:

  x² + 1,       x² + x + 2,       x² + 2x + 2.

  5 & 6. We have α² = 2 and Φ(α) = α³ = 2α = −α. Since Φ is an isomorphism,

  Φ(aα + b)  =  aΦ(α) + b  =  −aα b = 2aα + b.

  That is, Φ gives the conjugate radical. The universal polynomial factors as:

  x9 − x	=	x (x−1) (x−2)	(x2+1)	(x2+x+2)	(x2+2x+2)
  	=	x (x−1) (x−2)	(x−α)(x−2α)	(x−(α+1))(x−(2α+1))	(x−(α+2))(x−(2α+2)).

  Here each quadratic is above its factorization (x−β)(x−Φ(β)).

• 12/8 Final Review. Last class.   ⊞ HW   See also Midterm Review.
  Key concepts (see daily HW above)

  • Symmetry groups G = Sym(X) written as matrices and permutations
  • Abstract group definition (closed op, assoc, id, inv), proofs of basic properties
  • Compute with generators and relations, Cayley graph
  • Standard groups C_n, D_n, S_n, A_n, (Z_n , + ), (Z_n^× , · ), GL_n(F) for F = R and Z_n, Quaternion Q₈
  • Isomorphism and homomorphism
  • Subgroups H, cyclic subgroups ⟨g⟩, cosets gH
  • Normal subgroup N, quotient group G/N, Cartesian product G × G'
  • Lagrange Theorem: |H| divides |G|; Cauchy Theorem: For prime p dividing |G|, there is H with |H| = p.
  • Euclidean algorithm, inverses in (Z_n^× , · ), Chinese Remainder Theorem, RSA Cryptography
  • Rings and fields, extension fields F(α), inverses with Euclidean algorithm
  • Finite fields F_q = Z_p(α), q = pⁿ, universal polynomial x^q − x, Frobenius automorphism Φ(γ) = γ^p

  Problems

  1. Group GL₂(Z₂)
     • Base field F = Z₂ = {0,1}.
       Characteristic p = 2, so 2 = 0 and −1 = 1 in F.
     • Plane over F: Vector space
       V  =  F²  =  {v = (x,y) for x,y ∈ F}  =  { (0,0), (1,0), (0,1), (1,1) }.
       

     • General linear group: vector space symmetries = invertible 2×2 matrices
       G  =  GL₂(F)  =  Sym(V)  =  {invertible linear A : F² → F²}
        =  { [A] = [

       a	c
       b	d

       ]  with a,b,c,d ∈ F, det[A] = ad−bc ≠ 0 }.

     Problems
     1. Write the 6 matrices in G. Hint: The columns must be two unequal, nonzero vectors.
     2. Guess which standard group of order 6 is isomorphic to G. (See HW 3.) What structural properties can help you decide?
     3. In fact, G ≅ S₃ ≅ D₃, the group of all permutations of 3 vertices, or the 3 corners of a triangle.
        Give an explicit isomorphism T : G → S₃, taking each matrix A ∈ G to a permutation T(A) = σ ∈ S₃.
        Hint: Label the 3 non-zero vectors in V as 1,2,3, and compute how the linear mapping A moves these three to each other: this is a permutation in S₃. Compute each A(x,y) by multiplying the matrix [A] times the column vector (x,y).
  2. Group proofs. A homomorphism of groups is a mapping T : G → G' which respects multiplication, T(g₁g₂) = T(g₁) T(g₂), but is not necessarily one-to-one or onto.
     1. Prove that T(e) = e' and T(g⁻¹) = T(g)⁻¹.
        Hint: What is the definition of the identity e and e', and of the inverses g⁻¹ and (g')⁻¹ = T(g)⁻¹.
     2. The image of T is the set of all outputs: Im(T) = {T(g) ∈ G' for g ∈ G}. Prove that Im(T) is always a subgroup of G'.
        Hint: Write general elements of Im(T) as g'₁ = T(g₁), g'₂ = T(g₂). What properties must be checked?
     3. The kernel of T is the set of elements in G which are crushed to the identity in G':
        Ker(T)  =  { g ∈ G s.t. T(g) = e' ∈ G' }.
        Prove that Ker(T) is a normal subgroup of G. What properties must be checked?
     4. Prove that T is one-to-one if and only if Ker(T) = {e}.
        Hint: One direction is easy: if T is one-to-one, then nothing but e can map to e'. For the converse, assume T(g₁) = T(g₂) = g', then deduce g₁ = g₂, so only one element can map to g'.
  3. Group SL₂(Z₃)
     • Base field F = Z₃ = {0,1,−1}.
       Characteristic p = 3, so 3 = 0 and 2 = −1 in F.
     • Special linear group: 2×2 matrices with determinant 1
       G  =  SL₂(F)  =  { [A] = [

       a	c
       b	d

       ]  with a,b,c,d ∈ F, det[A] = ad−bc = 1 }.

     Problems
     1. How to find the order |G|? First compute |GL₂(F)|, the number of invertible matrices: the first column can be any non-zero v ∈ F², the second can be any w ∈ F² not on the line Fv = {0, v, −v}.
        Now, the subgroup SL₂(F) splits GL₂(F) into two cosets (matrices with det(A) = 1 and det(A) = −1), so |SL₂(F)| = ½|GL₂(F)|.
     2. Which symmetric group S_n has the same order as G? (See Notes on Standard Gps.)
     3. In fact, G is not isomorphic to S₄. Show this by finding a difference between the subgroup structure of the two groups.
        Hint: What are the simplest and most common subgroups of any group? Try taking powers of some matrices.
  4. Homomorphism T : SL₂(Z₃) → S₄.
     • A line through the origin in F² is the set of multiples of a vector, L = Fv = {0,v,−v}:
       L₁ = F(1,0),   L₂ = F(0,1),   L₃ = F(1,1),   L₄ = F(1,−1).
       

     • There are 4 possible lines L₁, . . . , L₄, and a linear mapping A moves them to each other, giving a permutation T(A) of the 4 lines. This defines the mapping:
       T : SL₂(Z₃) → S₄ .

     • For example, the matrix A = [

       0	−1
       1	0

       ]  is the F² version of a ¼ rotation, though not all linear mappings of F² look like mappings of the usual plane R². By matrix multiplication, we get A(1,0) = (0,1), so A(L₁) = L₂ ; and A(0,1) = −(1,0), so A(L₂) = L₁ ; etc. In 2-line and cycle notation, the permutation is:
       T(A)  =  (

       1	2	3	4
       2	1	4	3

       )   =  (12)(34).

     • T is a homomorphism because composition of linear mappings corresponds to composition of permutations:
       T(A∘B)  =  T(A) ∘T(B).

     Problems
     1. Find the image Im(T). Hint: It is a familiar subgroup of S_n. Compute some T(A)'s and see if they are even or odd permutations.
     2. Find the kernel Ker(T). Is there any A ≠ I which takes every line to itself (perhaps flipping it over)? Remember we are limited to det(A) = 1.
     3. Verify that Ker(T) is a normal subgroup of SL₂(Z₃), without using the general proposition about kernels. In fact, Ker(T) is a very special kind of subgroup defined by commutativity properties.
     4. What familiar group is isomorphic to the quotient group SL₂(Z₃)/Ker(T)?
  ⊞ Soln  

  1a. For a matrix A ∈ GL₂(F) with F = Z₂, there are |F²| − 1 = 3 choices for the first column, times |F²| − |F| = 2 choices for the second column, giving |G| = 6. there are |F²| − 1 = 3 choices for the first column, times |F²| − |F| = 2 choices for the second column, giving |G| = 6.

  1b. We classified groups of order 6 in HW 3: G ≅ D₃ ≅ S₃ or G ≅ C₆. Matrix multiplication is not commutative, so G cannot be C₆, and we must have G ≅ S₃.

  1c. The explicit isomorphism is given below, labeling the non-zero points of F² as v₁ = (1,0), v₂ = (0,1). v₃ = (1,1).
  
  

  [  1   0  0 1 ]	(  1   2   3  1 2 3 )  =  I
  [  1   1  0 1 ]	(  1   2   3  1 3 2 )  =  (23)
  [  0   1  1 0 ]	(  1   2   3  2 1 3 )  =  (12)
  [  0   1  1 1 ]	(  1   2   3  2 3 1 )  =  (123)
  [  1   1  1 0 ]	(  1   2   3  3 1 2 )  =  (321)
  [  1   0  1 1 ]	(  1   2   3  3 2 1 )  =  (13)

  2a. Proposition: Any group homomorphism T : G → G' satisfies T(e) = e' and T(g⁻¹) = T(g)⁻¹ for all g ∈ G.
  Proof: By definition, the homomorphism satisfies T(g₁g₂) = T(g₁) T(g₂). Now,

  T(e)  =  T(e·e)  =  T(e) T(e).

  Multiplying both sides by T(e)⁻¹ gives:

  e'  =  T(e)⁻¹ T(e)  =  T(e)⁻¹ (T(e)T(e))  =  T(e).

  This shows e' = T(e). Furthermore, we have:

  e'  =  T(e)  =  T(gg⁻¹)  =  T(g) T(g⁻¹).

  Thus g' = T(g⁻¹) satisfies e' = T(g)g', which is the definition of the inverse element T(g)⁻¹. Hence g' = T(g⁻¹) = T(g)⁻¹.

  2b. Proposition: For a group homomorphism T : G → G', the image H' = Im(T) is a subgroup of G'.
  Proof: For H' to be a subgroup of G', it must be closed under multiplication and inverses. By definition, elements of H' = Im(T) are of the form T(g₁), T(g₂), and their product stays in H' because T preserves multiplication:

  T(g₁) T(g₂)  =  T(g₁g₂)  =  T(g)   for   g = g₁g₂ ∈ G.

  Also the inverse stays in H' because of the Proposition in part (a):

  T(g₁)⁻¹  =  T(g₁⁻¹)  =  T(g)   for   g = g₁⁻¹ ∈ G.

  2c. Proposition: For a group homomorphism T : G → G', the kernel N = Ker(T) is a normal subgroup of G.
  Proof: To check N is a subgroup, we show it is closed under multiplication and inverses. By definition, elements g₁, g₂ ∈ N = Ker(T) satisfy T(g₁) = T(g₂) = e', and their product g₁g₂ stays in N because:

  T(g₁ g₂)  =  T(g₁) T(g₂)  =  e'e'   e'.

  Also the inverse stays in N because of the Proposition in part (a):

  T(g₁⁻¹)  =  T(g₁)⁻¹  =  (e')⁻¹   e'.

  Finally, to show the subgroup N is normal, we must show that for n ∈ N with T(n) = e', and g ∈ G, the conjugate gng⁻¹ stays in N:

  T(gng⁻¹)  =  T(g) T(n) T(g)⁻¹  =  T(g) e' T(g)⁻¹  =  T(g)T(g)⁻¹  =  e'.

  Thus gng⁻¹ ∈ N = Ker(T), and gNg⁻¹ = N, so N is normal.

  2d. Proposition: A group homomorphism T : G → G' is one-to-one if and only if Ker(T) = {e}.
  Proof: If T is one-to-one, this means T(g₁) = T(g₂) only when g₁ = g₂. Thus g ∈ Ker(T) only when T(g) = e' = T(e), hence only when g = e. That is, Ker(T) contains only e.

  For the other direction, assume Ker(T) = {e}, and take T(g₁) = T(g₂): we must show that g₁ = g₂. Indeed, we have:

  e'  =  T(g₁) T(g₂)⁻¹  =  T(g₁g₂⁻¹).

  That is, g₁g₂⁻¹ ∈ Ker(T) = {e}, so g₁g₂⁻¹ = e and g₁ = g₂. Thus T is one-to-one.

  3a. As before, for a matrix A ∈ GL₂(F) with F = Z₃, there are |F²| − 1 = 8 choices for the first column, times |F²| − |F| = 6 choices for the second column, giving |GL₂(F)| = 48 and |G| = |SL₂(F)| = ½|GL₂(F)| = 24.

  3b. A permutation σ ∈ S_n has n choices for σ(1), times n−1 choices for σ(2), etc., so |S_n| = n(n−1)···(2)(1) = n!. Here |G| = 24 = 4!, so G has the same number of elements as S₄.

  3c. Any group element g generates a cyclic subgroup ⟨g⟩ = {e, g, g², . . . , g^k−1} with g^k = e, and the size of this subgroup is the order |g| = k. Isomorphic groups must have corresponding isomorphic cyclic subgroups.

  Now, the permutations in σ ∈ S₄ can have order |σ| = 2 for σ of type (12) or (12)(34); or |σ| = 3 for type (123); or |σ| = 4 for type (1234). Thus the maximum order of any element (the maximum size of a cyclic subgroup) is N = 4.

  However, our G has the matrix A = [

  0	−1
  1	1

  ] with order |A| = 6: matrix multiplication shows that A, A², . . . , A⁵ ≠ I, but A⁶ = I. The maximum order in G is N = 6, and G cannot be isomorphic to S₄.

  4a. Recall that an even permutation σ ∈ S_n means σ can be written as a product of an even number of transpositions (ij); an odd-length cycle is an even permutation, like (123) = (12)(23). Otherwise, the permutation is odd, and an even-length cycle is an odd permutation, such as (1234) = (12)(23)(34). The even permutations form the alternating group A_n of order ^n!⁄₂.

  The homomorphism T : SL₂(Z₃) → S₄ takes any linear mapping to an even permutation, and in fact covers all ^4!⁄₂ = 12 of them: Im(T) = A₄ .

  4b. Consider A ∈ Ker(T), which means a linear mapping A : F² → F², with F = Z₃, with A(L) = L for every line L = Fv, meaning A(v) = ±v. Thus the colmumns of the matrix [A] are given by A(1,0) = ±(1,0) and A(0,1) = ±(0,1) which gives 4 matrices; but only A = ±I have det(A) = 1. Thus Ker(T) = {±I}.

  4c. The matrices ±I commute with any other matrix: AI = IA = A and A(−I) = (−I)A = −A. In fact, these are the only matrices in G that commute with all A, and Ker(T) = {±I} is the center:

  Z(G) = {z ∈ G with zg = gz for all g ∈ G}.

  The center is always a normal subgroup, since gZ(G) = Z(G)g for all g.

  4d. The Homomorphism Theorem implies that the quotient of G by the kernel of T is isomorphic to the image of T:

  G/Ker(T) ≅ Im(T) ≅ A₄.
• 12/10 Rate this course closes Sun

  ---

• 12/13 HW 3 corrections & Extra Credit problems due  
• 12/15  Final Exam Fri Dec 15, 2023 at 7:45-9:45am in usual classroom Wells A-228

  ---

  Extra Material
• X/X Ch 4.2 Complex numbers, spectrum of benzene   Text   Notes 11/4 11/6   ⊞ HW 7  HW 7 Soln
  Reading: Terras Ch 4.2, pp. 129, 132-134.
  (h)

  1. The conjugate of a complex number z = a+bi is  z̅ = a−bi.
     1. Show that conjugation respects complex addition and multiplication:  z+w = z + w  and  zw = z w.
     2. Show that z z̅ = |z|² = a²+b², the square length of the vector (a,b), and thus ¹⁄_z = ^z̅⁄_|z|² .
     3. Determine the formula for conjugating a complex number in polar coordinates, z = r e^iθ.
     4. Considering the complex numbers C as a real plane R², consider conjugation as a linear mapping R² → R². Write the 2×2 matrix of this mapping, and describe it geometrically.
  2. Complex roots
     1. Explicitly find the three complex cube roots of −1.
     2. Give a formula for the square root of a complex number z = a+bi. That is, write ±√a+bi = c+di, where c,d are real-number algebraic expressions in terms of a,b, without using trig or exponential functions. Hint: Start with the polar expression for square root, and convert it into an expression in a,b by means of trig identities.
     3. Extra Credit: The idea of even and odd functions are types of symmetry of a real function f(x) related to the two square roots of 1, namely ±1. Generalize this to new types of symmetry of a complex function f(z) related to the complex cube roots or n^th roots of unity.
  3. Recall from the text notes that the dual of a group G is the set Ĝ of all characters, homomorphism functions χ : G → C^× from G to the multiplicative group of nonzero complex numbers. Characters are multiplied in the usual way for functions: (χ·χ')(g) = χ(g) χ'(g).
     In this problem, consider G = C₂ × C₃ = ⟨a⟩ × ⟨b⟩ with a² = e and b³ = e. We know that an abelian G is isomorphic to its dual Ĝ, so |Ĝ| = 6.
     1. Give the 6 characters χ in Ĝ, in each case writing a formula for χ(a^j, b^k).
     2. We know by the Chinese Remainder Theorem that C₂ × C₃ ≅ C₆. Find one of the characters χ from (a) which is an isomorphism from G to the cyclic group ⟨ζ⟩ for ζ = e^iπ/3, the group of sixth roots of unity in C^×. Find the element in G with χ(a^j, b^k) = ζ, and verify that (a^j, b^k) generates all of G.
  4. Consider three balls labeled j = 0,1,2, attached in a triangular arrangement by three springs, similar to the benzene model in the notes. (This might be a model for ozone O₃.) Again let F_j(t) be the displacement functions for each ball, governed by a Hooke's Law depending on relative displacements. Imitate the notes to determine the following.
     1. The dynamic equations for F_j(t)
     2. The harmonic frequencies √λ
     3. Explicit formulas for the harmonic vibrations F_j(t) = f_j g(t).
  5. Extra Credit: Let G be the 12-element tetrahedron rotation group from HW 5. The group G is not abelian, but it still has non-trivial characters χ : G → C^×. Explicitly define such a character, giving each value χ(g). Hint: For the normal subgroup K = {I,A,B,C} from HW 5 #6, compose its quotient homomorphism mapping G → G/K ≅ C₃, with a character function C₃ → C^×.
• X/X Ch 5.1-5.6 Rings and fields. Ch 6.3 F[x] and Z.   ⊞ Text   Notes 11/9 11 13 16 18 20 23 25  
  Reading: Terras Ch 5, pp. 157-188; Ch 6.3, pp. 198-202.

  • A ring (R,+, · ) is a set with addition and multiplication operations satisfying the minimum properties for most of our familiar algebra
    • Properties: Addition (R,+) forms an abelian group: associative, commutative, with identity denoted 0 and negatives −a. Subtraction a − b means a + (−b).
      Multiplication is associative but not necessarily commutative, with identity denoted 1, but not every a ∈ R need have a reciprocal a⁻¹.
    • There is a multiplicative group of invertible elements (R^×, · ), where R^× = {a ∈ R such that a⁻¹ ∈ R}. This always contains 1, but possibly no other elements.
    • A field F is a ring with commutative multiplication where every non-zero element has a reciprocal, F^× = F−{0}. Division a/b means ab⁻¹ = b⁻¹a.
    • Zero-divisors are non-zero elements of R whose product is zero: a,b ≠ 0 with ab = 0.
  • Examples of rings
    • Integers Z, a commutative ring with Z^× = {±1} and no zero divisors
    • Fields of ordinary numbers: rationals Q, reals R, complex numbers C
    • Modular arithmetic Z_n, a commutative ring with Z_n^× = {k with gcd(k,n) = 1}, and all non-invertible elements are zero-divisors. This is a field whenever n = p, a prime number.
    • Matrix ring M_n(F), n×n matrices with entries in a field F, a non-commutative ring; all non-invertible matrices are zero-divisors
    • Ring of polynomials with coefficients in a field:
      F[x]  =  {f(x) = a₀ + a₁x + ··· + a_nxⁿ  for a_j ∈ F and n ≥ 0},
      a commutative ring with no zero-divisors and with F[x]^× = {constant polyonmials f(x) = a₀}
  • Ring proofs. These basic algebraic formulas do not need to be required as properties of a ring: they follow necessarily from the previous properties.
    1. Lemma: −(−a) = a for all a ∈ R.
       Proof: By definition, −(−a) + (−a) = 0. Adding a to both sides gives −(−a) + (−a) + a = a, i.e. −(−a) + 0 = a and −(−a) = a.
    2. Lemma: 0a = a0 = 0 for all a ∈ R.
       Proof: By distributivity, 0a + 0a = (0+0)a = 0a. Adding −0a to both sides gives 0a + 0a − 0a = 0a − 0a, i.e. 0a = 0. Similarly for a0 = 0.
    3. Lemma: (−a)b = a(−b) = −(ab) and for all a,b ∈ R.
       Proof: By distributivity and lemma (ii), (−a)b + ab = (−a + a)b = 0b = 0. Adding −(ab) to both sides gives (−a)b + ab + −(ab) = −(ab), i.e. (−a)b (−a)b = (−a)b + 0 = −(ab). Similarly for a(−b) = −(ab).
    4. Lemma: (−a)(−b) = ab for all a,b ∈ R.
       Proof: Applying lemma (iii) twice, (−a)(−b) = −(a(−b)) = −(−(ab)), which equals ab by lemma (i).
  • Ideals and quotient rings
    • To construct new rings and fields in a systematic way, we adapt the construction of quotient groups:
      coset decomposition G = g₁N ∪ ··· ∪ g_kN       and       quotient group G/N  =  {g₁N, . . . , g_kN},
      in which each coset gN = Ng is a single element of the quotient group, and all the elements of N are "crushed" into the identity element eN = N. We multiply by g₁N·g₂N = (g₁g₂)N.
    • Similarly, we can take R/I, the quotient of the ring R by the ideal I ⊂ R, which is a special kind of subring. The ideal is generated by certain elements of R which are to be "set to zero" in the quotient, which allows us to construct an extension field by setting a polynomial equation to zero.
    • An ideal I ⊂ R, where R is a commutative ring, means a proper subset (I ≠ R) with two properties:
      • Closed under addition: if i,j ∈ I then i + j ∈ I
      • Contains all multiples of its elements: if r ∈ R and i ∈ I then ri ∈ I.
      Note: (I, + , · ) is almost a ring itself, except that 1 ∉ I.
      Proof: If 1 ∈ I, then r = r·1 ∈ I for all r ∈ R, so that I = R, which is excluded from being an ideal.
    • The most common kind of ideal is all multiples of a single element i ∈ R, namely I = (i) = {ri for r ∈ R}.
    • Cosets of I, also called congruence classes, are the sets
      [r]  =  r + I  =  {r + i for i ∈ I}.
      We consider two elements equivalent modulo the ideal, r ≡ r' mod I, when [r] = [r'] or equivalently r − r' ∈ I. The ring splits into disjoint congruence classes: R = [r₁] ∪ [r₂] ∪ ···.
    • The quotient ring R/I means the set of all classes [r], with the natural operations [r] + [r'] = [r+r'] and [r][r'] = [rr']. This has the effect of crushing all elements j ∈ J to become zero: [i] = i + I = I = [0].
    • Example: This generalizes modular arithmetic, the case R = Z and I = (n) = {multiples of n}. The quotient R/I = Z/(n) = Z_n consists of the congruence classes [0], [1], . . . , [n−1], the subsets [r] = r + (n) = {r + kn for k ∈ Z} = {numbers congruent to r mod n}. Note that:
      [n]  =  n + (n)  =  {n + kn for k ∈ Z}  =  {kn for k ∈ Z}  =  [0],
      so that n is crushed to zero in Z/(n). Two classes are equal, [r] = [r'], whenever r − r' ∈ (n), i.e. n divides r − r'.
  • Algebraic number fields
    • An algebraic number α is a real or complex number which is a root of an equation with rational coefficients: that is, f(α) = 0 for some polynomial: f(x) ∈ Q[x]. For example, α = √2 is a root of x² − 2 = 0, and i = √(−1) is a root of x² + 1 = 0. The roots of a generic higher-degree polynomial like x⁵ − x + 1 are algebraic, but cannot be written in terms of radicals.
    • We compute with general algebraic numbers using abstract algebra as we do with simple algebraic numbers like √2 using high school algebra. For this, we define Q[α]  =  {g(α) for g(x) ∈ Q[x]}, the polynomials in α. This is clearly a commutative ring, and we will show it is a field containing reciprocals.
    • Assuming f(α) = 0 for f(x) an irreducible polynomial (i.e. no non-trivial factorizations), we can model the ring generated by α as:
      Q[α]  ≅  ^Q[x]⁄_(f(x)) ,
      the quotient R/J of the polynomial ring R = Q[x] by the ideal J = (f(x)) = {q(x)f(x) for q(x) ∈ Q[x]}. The elements are cosets [a(x)] with [f(x)] = [0]. Writing the class of a constant [c] as just c, we get f([x]) = [f(x)] = 0, and the class [x] is a solution of the original polynomial!
    • In fact, this ring is a field, with every class [g(x)] having a reciprocal [h(x)] with  [g(x)][h(x)] = [1], i.e.  g(x)h(x) ≡ 1 mod f(x), i.e.  g(x)h(x) = 1 + q(x)f(x)  for some polnomial q(x). We can find the correct h(x) and q(x) using the Extended Euclidean Algorithm. Finally, the isomorphism shows g(α)h(α) = 1 ∈ Q[α].
  • Example: f(x) = x³ + x − 1 = 0 has a unique real root x = α ≈ 0.682 .
    • Long division of polynomials gives any polynomial as g(x) = q(x)f(x) + r(x)  where  r(x) = a + bx + cx², so we can write any g(α) ∈ Q[α] in standard form:
      g(α)  =  q(α)f(α) + r(α)  =  0 + a + bα + cα².
      For example: x⁴  =  x f(x) + x − x², so α⁴  =  α − α².
    • We find the reciprocal ¹⁄_(1+α) in standard form. Long division gives: x³ + x − 1   =   (x²−x+2)(1+x) − 3. Dividing by 3 and rearranging, we get:
      (1+x) ⅓(x²−x+2) − (x³+x+1)   =   1
      Substituting x = α, the second term vanishes, and we get (1+α) ⅓(α²−α+2) = 1, so the reciprocal is:
      ¹⁄_(1+α)   =   ⅓α² − ⅓α + ⅔.
      In general, we would have to go through the longer Extended Euclidean Algorithm.
  ⊞ HW 8  HW 8 Soln
  Reading: Terras Ch 5, pp. 157-188; Ch 6.3 F[x] and Z, p
  (h)

  1. Ring properties. Let (R,+, · ) be a commutative ring (commutative multiplication), without zero-divisors (ab = 0 only for a = 0 or b = 0), and with 1+1 ≠ 0 in R (the characteristic is not 2). Give short proofs of the following.
     1. If a² = b² for a,b ∈ R, then a = b or a = −b.
     2. Consider a general quadratic equation ax² + bx + c = 0 with a,b,c ∈ R, a ≠ 0. This has a solution x ∈ R if and only if there is d ∈ R with d² = b² − 4ac, and in this case the two solutions are ^{(−b ± d)}⁄_2a .
        Hint: Use the standard complete-the-square argument, noting at each step why it is valid for R.
     3. Show that the above formulas do not work for R = M₂(R), the ring of 2×2 real matrices. In fact, show that there are infinitely many matrices X with X² = I. Hint: Diagonalize X = PDP⁻¹.
  2. Polynomial rings. Consider the polynomials
     f(x) = x⁴ + x³ + 2x² + x + 1  ,  g(x) = x⁴ − x³ + 2x² − x + 1 ∈ C[x].
     1. Find the gcd of these polynomials using the Euclidean Algorithm.
     2. Give the complete factorization of these polynomials into irreducibles in C[x]. Hint: A complex root produces a linear factor.
  3. Consider the field Q[α], where α is the unique real root of the polynomial
     f(x) = x³ + 3x − 1.
     Compute the following numbers in the standard form a + bα + cα²   for a,b,c ∈ Q.
     1. Use Division with Remainder to compute α¹⁰.
     2. Use the Extended Euclidean Algorithm to find the reciprocal ¹⁄_(α²+1).
  4. Fields of characteristic 3. Let Z₃ = {0,1,2} = {0, ±1} with 3 = 0 ∈ Z₃.
     1. Determine all irreducible polyomials of the form x² + bx + c ∈ Z₃[x].
     2. Construct the field F₉ = Z₃[x]/(x²+x−1) = Z₃[α], where α satisfies α² + α − 1 = 0. In particular, give complete addition and multiplication tables for the 9 elements of the form a + bα for a,b ∈ Z₃.
        Hint: Use the same algebraic construction as for Q[α] ≅ ^Q[x]⁄_(f(x)) . For complex algebraic numbers we know there is a root α ∈ C, but here we do not know of any extension field of Z₃ in which x²+x−1 has a root; rather we construct such a field.
     3. Verify that F₉ is a field: what properties are needed?
• X/X Ch 6.1 Ring homomorphisms   ⊞ Text   Notes 11/30 12/2
  Reading: Terras Ch 6.1, pp. 189-193.

  • Homomorphism Theorem: Given a ring homomorphism T : R → S, meaning T(r+r') = T(r) + T(r') and T(rr') = T(r) T(r'), we have:
    1. The image Im(T) = T(R) = {T(r) for r ∈ R}, the set of elements output by T, is a subring of S.
    2. The kernel Ker(T) = {k ∈ R with T(k) = 0}, the elements crushed to zero by T, is an ideal of R.
    3. The image is isomorphic to the quotient of the input ring modulo the kernel: T(R) ≅ ^R⁄_Ker(T).
  • Example: Projection homomorphism of a quotient, T : R → R/J, T(r) = [r] ∈ R/J. The Theorem says that any homomorphism is like a projection, in that its image (output set) is isomorphic to a quotient ring.
  • Example: Algebraic number field. For α ∈ C the root of an irreducible polyonmial f(x) ∈ Q[x], define T : Q[x] → Q[α], T(g(x)) = g(α). This is clearly an onto homomorphism, with Ker(T) = {g(x) s.t. g(α) = 0} = (f(x)). The Theorem implies:
    Q[α] = Im(T) ≅ Q[x]/Ker(T) = Q[x]/(f(x)).

  • Characteristic of a ring. Any ring R has a natural homomorphism T : Z → R, T(±n) = ±(1 + ··· + 1) with n terms. The Theorem says R has a subring T(Z) ≅ Z/Ker(T) = Z/(n) for some n, which is called the characteristic of the ring. If the characteristic is n = 0, this means R contains a copy of Z/(0) = Z. If R = F is a field, the characteristic must be either n = 0, so F contains Z and the rational numbers Q; or a prime number n = p, so F contains the finite field Z/(p) = Z_p.
• X/X Galois Theory   ⊞ Text   Notes 12/4 7 9 11  
  • For a field extension F ⊂ K, define [K : F], the degree of K over F, to mean the dimension of K as a vector space over F: the number of basis elements needed to span all of K as linear combinations with coefficients in F. For an intermediate extension F ⊂ L ⊂ K, the degrees multiply:
    [K:F]  =  [K:L]·[L:F],
    since one can multiply a basis of K over L by a basis of L over F to get a basis of K over F.
  • Fundamental Theorem of Galois Theory: Let K = F[α₁, . . . , α_n] be a splitting field, meaning we adjoin to F the n distinct roots α_i of a degree n polyomial f(x) ∈ F[x]. Define the Galois group as the symmetries of K fixing F:
    G = Gal(K/F) = {ring isomorphisms σ : K → K with σ(a) = a for a ∈ F}.
    1. The order of the Galois group is the degree of the field extension: |G| = [K : F]. Any symmetry permutes the roots α₁, . . . , α_n among each other, making G ⊂ S_n; and for any two roots α = α_i and β = α_j, there is an isomorphism σ ∈ G with σ(α) = β.
    2. There is a one-to-one correspondence between subgroups H ⊂ G and intermediate fields F ⊂ L ⊂ K, where L is the fixed set of H:
       L = K^H = {γ ∈ K s.t. σ(γ) = γ for all σ ∈ H}.
       The degree of the extension over the base field is equal to the index of the subgroup relative to the entire Galois group:
       [L:F]  =  ^|G|⁄_|H| .

    3. Normal subgroups N ⊂ G correspond to intermediate fields L which are splitting fields:
       F  ⊂  L  =  F[β₁, . . . , β_m],
       where β_j are the m roots of a degree m polyonomial g(x) ∈ F[x]. The Galois group of the fixed field over the base field is isomorphic to the quotient group: Gal(L/K) ≅ G/N.
  • Example: Let K = Q[α,ζ], where α = ³√2, the real cube root of 2 with minimal polynomial x³ − 2, and ζ = ⁻¹⁄₂ + ^i√3⁄₂, a complex cube root of unity with ζ³ = 1 and minimal polynomial x² + x + 1 = 0, since x³ − 1 = (x − 1)(x² + x + 1).
    • K = Q[α₁, α₂, α₃] is the splitting field of the polyomial:
      f(x)  =  x³ − 2  =  (x−α₁)(x−α₂)(x−α₃),
      whose roots are the three complex cube roots of 2, namely α₁ = α , α₂ = ζα , α₃ = ζ²α.
    • The Galois group G = Gal(K/F) contains one obvious symmetry: the complex conjugation σ(a+bi) = a−bi, so that σ(ζ) = ⁻¹⁄₂ − ^i√3⁄₂ = ζ². Thus
      σ(α) = α,   σ(ζα) = ζ²α,   σ(ζ²α) = ζα.
      Considering this in S₃ as a permutation of the 3 roots, σ = (23) in cycle notation.
    • There is another Galois symmetry ρ which comes from the fact that each x = α_i satisfies the same basic relation x³ − 2 = 0. In fact, we can take ρ(α₁) = α₂ and ρ(α₂) = α₃, i.e ρ(α) = ζα, ρ(ζα) = ζ²α. Since ρ is a field isomorphism, this implies
      ρ(ζ) = ρ(^ζα⁄_α) = ^ζ2α⁄_ζα = ζ,       ρ(α₃) = ρ(ζ²α) = ρ(ζ)²ρ(α) = ζ²ζα = α = α₁ .
      Thus, as a permutation ρ is the 3-cycle ρ = (123).
    • By multiplying σ and ρ, we can produce every permutation in S₃, and there can be no other symmetries, so we conclude G ≅ S₃.
    • A general way to find elements fixed under a group H, δ ∈ L = K^H, is to sum the symmetric images of an arbitrary element under the group action. That is, choose any γ ∈ K and take δ = ∑_h∈H h(γ). Applying any h' ∈ H to this will permute the terms, but give the same overall sum, so h'(δ) = δ. This is analogous to the symmetrization construction X_H = ∪_h∈H h(X_e) in Text 10/9.
      Example: For H = ⟨σρ⟩ = {e, σρ}, we can take γ = α and sum its two symmetric images:
      δ  =  e(α) + σρ(α)  =  α + ζ²α  =  −ζα  ∈  L = K^H,
      since 1 + ζ² = −ζ. This δ is invariant under H, and in fact, L = Q[δ] = Q[ζα] = Q[ζα], since by the Theorem [L : Q] = ^|G|⁄_|H| = 3, and [Q[ζα] : Q] = 3 also.
  ⊞ HW 9  
  (h)

  1. Let T : R → S be a homomorphism of rings. Prove the following, starting from the definitions given in the statement of the Homomorphism Theorem (11/30-12/2).
     1. The kernel K = Ker(T) = {k ∈ R s.t. T(k) = 0} is an ideal of R: that is, k+k', kr ∈ K for any k,k' ∈ K, r ∈ R. (This is the second part of the Theorem.)
     2. The mapping M : R/K → T(R), M([r]) = T(r), is well-defined: that is, if [r] = [r'] ∈ R/K, then T(r) = T(r'). (This the isomorphism in the third part of the Theorem.)
     3. T is one-to-one if and only if Ker(T) = {0}.
  2. Work out the Fundamental Theorem of Galois Theory for the case of F = Q ⊂ K = Q[α, i], where α = ⁴√2 is the real fourth root of 2, and i = √(−1), the imaginary unit. We can consider this a vector space with coefficients in Q. The intermediate field Q[α] has basis 1, α, α², α³, and adjoining i gives the 8 basis vectors:
     {1, α, α², α³, i, iα, iα², iα³}
     This means the dimension of K is [K:Q] = 8.
     Note: You may assume the Fundamental Theorem of Galois Theory to justify your computations.
     1. K is the splitting field of a polynomial of degree 4. Find this polynomial and its four complex roots α₁, . . . , α₄.
     2. Consider the complex conjugation mapping σ on K. Write σ as a permutation of the 4 roots, and also as the 8 × 8 matrix of a linear mapping with respect to the basis above. Hint: We discussed complex conjugation in HW 7.
     3. You may assume there is another Galois symmetry with ρ(α₁) = α₂ and ρ(α₂) = α₃. Write this symmetry also as a permutation and as an 8 × 8 matrix. Hint: We did some examples of symmetries as permutations and matrices in HW 9/9 & 9/11 and Hand-In HW 3 & 4.
     4. By repeatedly multiplying the generators σ, ρ as permutations, find the full Galois group G ⊂ S₄. How do you know there cannot be any more symmetries than the ones you listed? Hint: Use part (i) of the Fundamental Theorem above.
     5. Recall and define all the groups of order 8 we have considered in the group theory part of the course (including the Midterm). Which of these is isomorphic to the Galois group?
     6. Write all the subgroups of G in an inclusion diagram, but flipped so ⟨e⟩ is on top and G is on the bottom. Hint: We did something similar in Text 10/9. In this case, you should find a total of 10 subgroups.
     7. For each subgroup H ⊂ G, write the corresponding fixed field L = K^H, in a corresponding inclusion diagram.
        Hints:
        • For the cyclic subgroup H = ⟨σ⟩ = {e, σ}, the fixed field is the set of elements of K which are their own complex conjugate, We know σ(α) = α, so Q[α] ⊂ L = K^H. Also, we know that its dimension is [L:Q] = ^|G|⁄_|H| = ⁸⁄₂ = 4. Since [Q[α]:Q] = 4, there can be no other elements of L, and L = Q[α].
        • A general way to find elements fixed under a group H, δ ∈ L = K^H, is to sum the symmetric images of an arbitrary element under the group action. That is, choose any γ ∈ K and take δ = ∑_h∈H h(γ). Applying any h' ∈ H to this will permute the terms, but give the same overall sum, so h'(δ) = δ. This is analogous to the symmetrization construction X_H = ∪_h∈H h(X_e) in Text 10/9.
     8. Identify the normal subgroups of G, and for each fixed field, write it as a splitting field, adjoining all roots of a polynomial in Q[x]. Hint: We discussed normal subgroups in Text 10/2-5.
  3. Extra Credit: Consider the finite field K = Z₃[x]/(x²+x−1) from HW 8 over the base field F = Z₃.
     1. Show that the Frobenius mapping φ(γ) = γ³ is a field isomorphism, and hence an element of G = Gal(K/F).
     2. Show that K is a splitting field of x²+x−1 by finding the other root in K.
     3. Find all the elements of G. Why can't there be any other symmetries?
     4. Are there any subgroups or intermediate fields?
     5. Show that if K is a field with |K| = q elements, then γ^q−1 = 1 for all γ ∈ K^×.
     6. Apply the above to show every γ ∈ K is a root of x⁹ − x. Show that x⁹ − x is the product of all irreducible polyomials of degrees 1 or 2 in Z₃[x]. Split each irreducible as the product of linear factors in K[x].

  ---