Group Theory
and
Rubik's Cube

Fall 2015
course
navigation

Buzzwords, Notations, Definitions, and Theorems

A collection of various technical geeky words and their (fairly) precise definitions that many mathemeticians have at the tip of their tongue, but you and I may want to have a place to look up.

1-to-1 A map from {x}->{y} in which every x is sent to a different y, i.e. x not equal y implies f(x) not equal f(y). This does not imply that the map must completely cover {y}. (See "onto", "bijection".)
Abelian A group G is called abelian if a*b=b*a for all a,b in G. (See "boring.")
Automorphism An automorphism is an ismomorphic map of a group G onto itself. The set of isomorphisms of a given group G is also a group, called Aut(G).
Bijection A bijection is a map which is both 1-to-1 and onto.

Such maps take each element of {x} to a unique {y}, and each {y} is the result of a unique {x}; therefore, bijections are invertible maps and sometimes written {x} <-> {y} .

boring A group G is called "boring" if it isn't particularly related to any interesting puzzles, physics, or profound cool group stuff. At least in Jim's opinion. (see "Abelian".)
Campanology The art and science of "change ringing", ringing N church (or hand) bells in many of their possible N permutations in a systematic way.

Folks who did this understood quite a bit about permutations long before the mathematics of "group theory" existed; therefore, you could say it was the precursor of all this stuff.

Conjugate Two group elements a and b are conjugate to each other if there exists an element c such that a = c b c-1 . The set of all {x} conjugate to a given element y is called y's "conjugacy class." It turns out that these conjugacy classes partition each group into disjoint subsets; each group element belongs to a single conjugacy class.
Cayley's Theorem
(All groups are permutations.)
Every group G is is isomorphic to a subgroup of SG, the group of permutations of the elements of G.

If G is finite and has order n, then G is isomorphic to a subgroup of Sn.

Countable A set X is countable iff there exists a 1-to-1 map from the positive integers to X, {1,2,3,...} <-> {X}.
Commute Two group elements a,b are said to commute if a*b=b*a. (See "Abelian.")
Commutator The commutator [a,b] of two elements is a*b*a-1*b-1.
Commutator Subgroup The set of all {x} such that x = [a,b] for some a,b in a group G is called that group's commutator subgroup. The order of this subgroup is a measure of how abelian-like G is.
Coset Given a group G with a subgroup H={h1,h2,...}, the "left coset" of H corresponding to an element x of G is defined as the set { x h1 , x h2 , x h3, ... }.

"x is in the same coset as y" defines an equivalence relation between x and y, and thus partitions G into order(H) disjoint sets. Showing that each of these cosets has the same number of elements leads to a proof of Lagrange's Theorem.

cubelet One of the smaller solid cubes which together make up the Rubik's Cube puzzle. Each of the corners, edges, and faces in the 3x3x3 Rubik's Cube is a "cubelet."
Cyclic The cyclic groups ( Cn ) are those isomorphic to the integers {0,1,2,3,...,(n-1)} under addition mod n.
Determinant The determinant of an NxN square matrix is the scalar value of the N-dimensional "volume" spanned by the column vectors of the matrix. In particular, if the determinant is zero then the matrix has no inverse, is is not particularly interesting.

For a 2x2 matrix (a,b; c,d) the determinant is a*d-b*c. For larger matrices the formulas get trickier; check any linear algebra or calculus text.

Examples Some specific named groups discussed in class and (brief) definitions:
  • Cn : cyclic group of n elements; order = n
  • Sn : permuntations of n objects; order = n!
  • An : even permunations of n objects; order = (n!)/2
  • Dn : rotations and flips of plane n-gon; order = 2n
  • Euclidian group : isometries (distances stay same) of plane; uncountable
  • Symmetries of regular solids: cube (order 24), tetrahedron, etc.
  • Rubik's Cube: order = 12! 212 8! 38 / 12 = 43252003274489856000. (This is for face centers held fixed in space and in any orientation, not counting positions reached by dissesembling cube.)
  • Matrix groups
    • GLn(R) : "general linear group": n x n invertable matrices with real entries
    • On : n x n orthogonal real matrices (subgroup of GLn)
    • SOn : n x n orthogonal, determinant=1 (special) matrices (subgroup of On)
    • Un : n x n unitary (complex analogue to orthogonal) matrices (subroup of GLn(C))
    • SUn : n x n unitary, determinant=1 matrices
Equivalence relation An equivalence relation on a set S is a set of pairs of elements (s1,s2) with the following properties:
  1. a~a for all a in S,
  2. a~b imples b~a,
  3. if a~b and b~c , then a~c .
Any such relation breaks S into equivalence classes (sets of elements equivalent to each other), and these classes partition S into disjoin subsets. Typically we write s1~s2 using one of the various "=" symbols.
Function A function F(x)=y is a map between two sets, {x}->{y}. (See Map.)
Generators The generators of a group G are elements in a subset H of G = {h1,h2,h3...} such that any element of G may be reached by a some sequence x1*x2*x3*x4*... where all the x's are members of H.

The set H is not usually unique. (Any subset of elements {a,b,c,...} of G similarly generates a group which must be a subgroup of G.)

The order of the smallest possible such set H may be though of as a characterstic "dimension" of the group, analogous to the 1,2,3 dimensions of a point, line, plane in Euclidean space, i.e. as the number of independent "directions" which extend outwards from the origin (identify).

Group A set G = {a, b, c,...} and a binary operation * with the following properties:
(i) closure: For any a, b in G, a * b = is in the set.
(ii) associativity: For all a, b, c in G, (a * b )* c = a * ( b * c ) .
(iii) identify: There exists an element I such that I * a = a for every a in G.
(iv) inverse: For every element a there exists an a-1 such that a * a-1 = I.
Homomophism A homomorphism from G into H is a map f which perserves the group operation, i.e. for all g1, g2 in G, f(g1 g2) = f(g1) f(g2).

See kernel.

Isomorphic Two groups G and H are isomorphic if and only if there exists a 1-to-1 map between them which preserves the group multiplication table. In other words, if g1 and g2 are members of G, and h1=f(g1), h2=f(g2) are the corresponding members of H under the 1-to-1 map f, then f(g1*g2)=f(g1)*f(g2).

Intuitively, isomorphic groups are essentially the same for all practical purposes.

Kernel The kernel of a homomorphism G->H is the set of elements of G which are mapped to the identify of H.

The kernel is always a normal subgroup of G, and its cosets form a quotient group G/(kernel) which is isomophic to H.

See quotient group.

Lagrange's Theorem The order of a subgroup H of a group G divides the order of G.
(See "coset" for an outline of a proof.)
Map A relation between two sets X={a,b,c,...} and Y={A,B,C,...} that given any element in X specifies an element of Y. Often written as X->Y. The relation may be given explictly or (more often) by some kind of rule. Every element of X _must_ be mapped to something in Y. The converse is not necessarily true; there may be "untouched" elements in Y. X and Y may be the same. (See Function, 1-to-1). Example: X={1,2,3}, Y={1,2,3,4}, x->1 for any x in X. (As a function f, f(1)=1, f(2)=1, f(3)=1.)
Matrices There are several ways to define these depending on how picky you want to get. Technically, matrices are linear maps in an N-dimensional vector space, which can be written as a table of numbers in a given basis for the vector space. Practically speaking, the matrix is usually just thought of as that NxN table of numbers. For example, the 3x3 "identity" matrix looks like this:
1 0 0
0 1 0
0 0 1

Matrices are worthy of a whole course unto themselves - it's called "linear algebra" - in which you learn about their inverses, determinants, eigenvalues, eigenvectors, diagonalization, and a whole lot of other multi-syllabic words that we won't get into here. But the easy parts are so common and so useful in group theory that we may make some use of them. Also see determinant.

Normal A subgroup J of a group G is "normal" if any of these three equivalent conditions are met:
  • J is made up of whole conjugacy classes, or
  • g J g-1 = J for all g in G, or
  • the left and right cosets of J are the same, xJ=Jx for all x in G.
See homomorphism, simple, kernel
Onto A map f:{x}->{y} such that for each element y there exists an x such that f(x)=y; i.e. the map touches every part of {y}. (See "1-to-1", "bijection".)
Orbit Given an element x of a group G, the orbit of x is the set of all elements of G which are generated by x, i.e. {x, x2, x3, ... }.

For any element x, the orbit of x is a subgroup of G isorphic to CN, the cyclic group of N elements, where xN=I.

Order Generally speaking, "how many." More specifically, the order of a group (or subgroup) is how many elements there are in that group (or subgroup). By the order of an element of a group we usually mean how many elements there are in its orbit, i.e. the order of an element x is the smallest positive integer N such that xN=I. This is also called the period of that element.
Period The period of a group element is another term for its order.
Normal A subgroup J of a group G is "normal" if any of these three equivalent conditions are met:
  • J is made up of whole conjugacy classes, or
  • g J g-1 = J for all g in G, or
  • the left and right cosets of J are the same, xJ=Jx for all x in G.
See homomorphism, simple, kernel
Quotient group Given a group G and a normal subgroup J, the set of cosets of J form a group G/J of order ord(G)/ord(J) whose group operation is given by
(xJ)(yJ)=(xyJ)
where each () represents one of the cosets. This is also called "G mod J".
Representation A representation of a group G is a set of matrices M which are homomorphic to the group. In other words, there must exists a map f:G->M such that f(g1 g2) = f(g1) * f(g2) where "*" here refers to the usual matrix multiplication.

Representations of groups is a whole branch of group theory unto itself.

Rubik's Cube A group-theory permutation puzzle made up of a 3-dimensional array of smaller "cubies" ( N3 of them, where N=2,3,4,...) with colored faces. But you already knew that...
Scalar A single real or complex numeric value. (See "Vector", "Matrix".)
Semi-direct product If a group G has a normal subgroup N, and thus can be factored as G/N = M, then we also say that G is the "semi-direct" product of N and M, G = N x| M.
Simple A simple group is one which has only two normal subgroups: the identity element and the entire group. Simple groups cannot be factored, and so are analogous to prime numbers.

(hard) Question: what is the smallest non-abelian simple group?
Answer: A5. (This fact is directly related to one of the major math results of the last century, namely that you can solve the general 4th order polynomial, but not the general 5th order one.)

Set A collection of elements {a, b, c, d, ... } of any kind. May be empty. Size may be zero (null set, {}), finite (example: {1,2,3}) or infinite (example: {integers}).
Subgroup A subset of a group which is also a group.
Vector Technically, a member of a linear vector space with certain kinds of addition properties which can be written as a column of numbers given a specific basis for the vector space. Practically speaking, we usually just imagine the vector as a column (or row) of numbers, A = (1,0,0). (See "Scalar", "Matrix")
http://cs.marlboro.edu/ courses/ fall2015/rubik/ wiki/ definitions
last modified Saturday August 8 2015 11:34 am EDT