You are currently browsing the tag archive for the ‘groups’ tag.
Diagram chasing is a method of mathematical proof used especially in homological algebra. Homological algebra studies, in particular, the homology of chain complexes in abelian categories – therefore the name. From a modern perspective, homological algebra is the study of algebraic objects, (such as groups, rings or Lie algebras, or sheaves of such objects), by ‘resolving them’, replacing them by more stable objects whose homotopy category is the derived category of an abelian category. Given a commutative diagram, a proof by diagram chasing involves the formal use of the properties of the diagram, such as injective or surjective maps, or exact sequences. A syllogism is constructed, for which the graphical display of the diagram is just a visual aid. It follows that one ends up "chasing" elements around the diagram, until the desired element or result is constructed or verified. Examples of proofs by diagram chasing include those typically given for the Snake Lemma, Four Lemma, Five Lemma, Nine Lemma, and Zig-Zag Lemma.
Formally, an exact sequence is a sequence of maps
between a sequence of spaces which satisfies
where denotes the image and
the group kernel. That is,
iff
for some
. It follows that
The notion of exact sequence makes sense when the spaces are groups, modules, chain complexes, or sheaves. The notation for the maps may be suppressed and the sequence written on a single line as
- A short exact sequence:
beginning and ending with zero, meaning the zero module
.
- A long exact sequence:
Special information is conveyed when one of the spaces is the zero module. For instance, the sequence
is exact iff the map is injective. Similarly,
is exact iff the map is surjective.
In homological algebra, given a short exact sequence of
-modules, there is a canonical long exact sequence
where the are certain "connecting homomorphisms" (or "snake maps"). This can be deduced from the Snake Lemma. For the proof the latter, one can engage in "diagram chasing". One can see, in the movie It’s My Turn (1980) a proof given for the Snake Lemma using diagram chasing. To define
: given
, lift
" to
, push it into
by
, then check that the image has a preimage in
. Then verify that the result is well-defined, et cetera.
in which the rows are exact, there is a canonical map , induced by
such that the sequence
is exact.
with exact rows. We wish to prove that the sequence
is exact.
First we claim that if any square
is commutative, then there are well-defined morphisms and
. For example, if
, then the square
must commute, and so the image of in the top row must be in
. The proof of the claim for cokernels is similar. Thus we have two sequences,
each of which inherits being a complex from the original diagram.
Suppose is sent to
. By exactness,
has a preimage
. Because the diagram
is commutative and the bottom morphism is injective, and so
. So the sequence
is exact. The proof of the claim for the cokernel sequence is similar.
So now all we need to do is find a connecting morphism such that the resulting sequence is exact at both of those points.
Suppose . Then
has at least one preimage in
. So let
and
be preimages of
. Thus
and so by exactness has a preimage
. By commutativity of the diagram,
has a preimage
, which is unique by injectivity of the morphism
. But we know that the square
is commutative. We wish to define by
. Observe that
and so the choice of preimage of does not affect which cokernel element we ultimately select. So now we have our connecting morphism. By applying this definition we see that
is a complex.
Suppose is sent to
by the connecting morphism. Thus we have a diagram
which is commutative. Let be the image of
under the morphism
. Exactness of the diagram implies that
is a preimage of
. But
. So the kernel-cokernel sequence is exact at
. The proof that it is exact at
is similar.
These notes are a wonderful introduction to group theory! Though only 39 pages in length, it covers a fair amount of the subject in a very clear fashion by relating the theory to the study of the Rubik’s Cube.
A Rubik’s Cube is a cube in which the 26 subcubes on the outside are internally hinged in such a way that rotation (by a quarter turn in either direction or a half turn) is possible in any plane of cubes. Each of the six sides is painted a distinct color, and the goal of the puzzle is to return the cube to a state in which each side has a single color after it has been randomized by repeated rotations. The puzzle was invented in the 1970s by the Hungarian Ernő Rubik and sold millions of copies worldwide over the next decade.
The number of possible positions of the Rubik’s cube is
(Turner and Gold 1985, Schönert). Hoey showed using the Pólya-Burnside lemma that there are positions up to conjugacy by whole-cube symmetries.
The group of operations on the Rubik’s cube is known as Rubik’s group, and the Cayley graph of that group is called Rubik’s graph. The minimum number of turns required to solve the cube from an arbitrary starting position is equal to the graph diameter of Rubik’s graph, and is sometimes known as God’s number. While algorithms exist for solving a cube from an arbitrary initial position, they are not necessarily optimal (i.e., requiring a minimum number of turns) and computation of God’s number is very difficult. It had been known since 1995 that a lower bound on the number of moves for the solution (in the worst case) was 20, it was not known until demonstrated by Rokicki et al. (2010) that no configuration requires more than 20 moves, thus establishing that God’s number is 20.
A Note to the Reader
These notes are based on a 2-week course that I taught for high school students at the Texas State Honors Summer Math Camp. All of the students in my class had taken elementary number theory at the camp, so I have assumed in these notes that readers are familiar with the integers mod n as well as the units mod n.
Because one goal of this class was a complete understanding of the Rubik’s cube, I have tried to use notation that makes discussing the Rubik’s cube as easy as possible. For example, I have chosen to use right group actions rather than left group actions.
Introduction
The goal of these notes is to give an introduction to the subject of group theory, which is a branch of the mathematical area called algebra (or sometimes abstract algebra). You probably think of algebra as addition, multiplication, solving quadratic equations, and so on. Abstract algebra deals with all of this but, as the name suggests, in a much more abstract way! Rather than looking at a specific operation (like addition) on a specific set (like the set of real numbers, or the set of integers), abstract algebra is algebra done without really specifying what the operation or set is. This may be the first math you’ve encountered in which objects other than numbers are really studied!
A secondary goal of this class is to solve the Rubik’s cube. We will both develop methods for solving the
Rubik’s cube and prove (using group theory!) that our methods always enable us to solve the cube.
References
Douglas Hofstadter wrote an excellent introduction to the Rubik’s cube in the March 1981 issue of Scientific American. There are several books about the Rubik’s cube; my favorite is Inside Rubik’s Cube and Beyond by Christoph Bandelow. David Singmaster, who developed much of the usual notation for the Rubik’s cube, also has a book called Notes on Rubik’s ’Magic Cube,’ which I have not seen.
For an introduction to group theory, I recommend Abstract Algebra by I. N. Herstein. This is a wonderful book with wonderful exercises (and if you are new to group theory, you should do lots of the exercises). If you have some familiarity with group theory and want a good reference book, I recommend Abstract Algebra by David S. Dummit and Richard M. Foote.
Topics covered are:
- Functions
- Groups
- The Rubik’s Cube and Subgroups
- Cube Notation
- Making the Rubik’ Cube into a Group
- Subgroups
- Simplifying Group Notation
- Generators
- The Symmetric Group
- Disjoint Cycle Decomposition
- Rubik’s Cube
- Group Homomorphisms
- The Sign Homomorphisms
- The Alternating Group
- Group Actions
- Valid Configurations of the Rubik’s Cube
Proofs from THE BOOK by Martin Aigner and Günter Ziegler begins by giving six proofs of the infinity of primes. We will go over the second proof. Before we go over this proof, lets cover some background.
— 1. Algebraic Structures —
One of the themes of modern algebra is to compare algebraic structures. An algebraic structure refers to a nonempty set equipped with a binary operation or several binary operations (usually two). Also, we shall refer to a nonempty set equipped with two binary operations satisfying certain properties as a number system. First, we shall define algebraic structures called group, ring and field. A group consists of nonempty set with one binary operation satisfying several conditions. It is the simplest of the three.
i. The binary operation is associative, i.e.,
for all
.
ii. There is a -identity
, i.e.,
for all
.
iii. For each , there is a
-inverse
, i.e.,
, where
is the
-identity.
Further more, a group is said to be commutative (or abelian), if the binary operation
is commutative.