Tag Archive

You are currently browsing the tag archive for the ‘groups’ tag.

The Snake Lemma

February 10, 2012 in Mathematics Posts | Tags: abelian category, categories, chain complexes, cokernel, commutative diagram, complex, connecting morphism, diagram chasing, exact sequences, exactness, five lemma, four lemma, groups, homological algebra, homomorphism, homotopy, image, it's my turn, kernel, modules, morphisms, movie, nine lemma, sheaves, snake lemma, zig-zag lemma | Leave a comment

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.

Definition 1 An exact sequence is a sequence, either finite or infinite, of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

Definition 2 A short exact sequence is a finite sequence of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

Definition 3 A long exact sequence is an infinite sequence of objects and morphisms between them such that the image of one morphism equals the kernel of the next.

Formally, an exact sequence is a sequence of maps

$\displaystyle \alpha_{i}:A_{i}\rightarrow A_{i+1}$

between a sequence of spaces ${A_{i},}$ which satisfies

$\displaystyle im(\alpha_{i})=\ker(\alpha_{i+1}),$

where ${im}$ denotes the image and ${\ker}$ the group kernel. That is, ${a\in A_{i},\alpha_{i}(a)=0}$ iff ${a=\alpha_{i-1}(b)}$ for some ${b\in A_{i-1}}$ . It follows that ${\alpha_{i+1}\circ\alpha_{i}=0.}$ 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

$\displaystyle \cdots\rightarrow A_{i-1}\rightarrow A_{i}\rightarrow A_{i+1}\rightarrow\cdots.$

A short exact sequence:
$\displaystyle 0\rightarrow A\rightarrow B\rightarrow C\rightarrow0.$

beginning and ending with zero, meaning the zero module ${\{0\}}$ .
A long exact sequence:
$\displaystyle \cdots\rightarrow A\rightarrow B\rightarrow C\rightarrow\cdots.$

Special information is conveyed when one of the spaces is the zero module. For instance, the sequence

$\displaystyle 0\rightarrow A\rightarrow B$

is exact iff the map is injective. Similarly,

$\displaystyle A\rightarrow B\rightarrow0$

is exact iff the map is surjective.

In homological algebra, given a short exact sequence ${0\rightarrow M'\rightarrow M\rightarrow M''\rightarrow0}$ of ${G}$ -modules, there is a canonical long exact sequence

$\displaystyle 0\rightarrow H^{0}(G,M')\rightarrow\cdots\rightarrow H^{i}(G,M'')\stackrel{\delta_{i}}{\rightarrow}H^{i+1}(G,M')\rightarrow \\ H^{i+1}(G,M)\rightarrow H^{i+1}(G,M'')\cdots,$

where the ${\delta_{i}}$ 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 ${\delta}$ : given ${x''\in\ker(\gamma)\subseteq C}$ , lift ${x}$ " to ${B}$ , push it into ${B'}$ by ${\beta}$ , then check that the image has a preimage in ${A'}$ . Then verify that the result is well-defined, et cetera.

Lemma 1 (Snake Lemma) Given the commuting diagram

in which the rows are exact, there is a canonical map ${\delta:\ker(\gamma)\rightarrow coker(\alpha)}$ , induced by ${\delta x''=f'^{-1}\circ\beta\circ g^{-1}x''}$ such that the sequence

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma)\stackrel{\delta}{\rightarrow} coker(\alpha)\rightarrow coker(\beta)\rightarrow \\ coker(\gamma)\rightarrow0$

is exact.

Proof: Suppose we are given a commutative diagram

with exact rows. We wish to prove that the sequence

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma)\rightarrow coker(\alpha)\rightarrow coker(\beta)\rightarrow \\ coker(\gamma)\rightarrow0$

is exact.

First we claim that if any square

is commutative, then there are well-defined morphisms ${\ker(\varphi)\rightarrow\ker(\psi)}$ and ${ coker(\varphi)\rightarrow coker(\psi)}$ . For example, if ${x\in\ker(\varphi)}$ , then the square

must commute, and so the image of ${x}$ in the top row must be in ${\ker(\psi)}$ . The proof of the claim for cokernels is similar. Thus we have two sequences,

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma){\ and\ } coker(\alpha)\rightarrow coker(\beta)\rightarrow \\ coker(\gamma)\rightarrow0,$

each of which inherits being a complex from the original diagram.

Suppose ${x\in\ker(\beta)}$ is sent to ${0\in\ker(\gamma)}$ . By exactness, ${x}$ has a preimage ${x'\in A}$ . Because the diagram

is commutative and the bottom morphism is injective, ${y'=0}$ and so ${x'\in\ker(\alpha)}$ . So the sequence

$\displaystyle 0\rightarrow\ker(\alpha)\rightarrow\ker(\beta)\rightarrow\ker(\gamma)$

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 ${\ker(\gamma)\rightarrow coker(\alpha)}$ such that the resulting sequence is exact at both of those points.

Suppose ${x''\in\ker(\gamma)}$ . Then ${x''}$ has at least one preimage in ${B}$ . So let ${x}$ and ${\widehat{x}}$ be preimages of ${x''}$ . Thus ${\widehat{x}-x\mapsto0}$ and so by exactness has a preimage ${x'\in A}$ . By commutativity of the diagram, ${\beta(x)}$ has a preimage ${y'}$ , which is unique by injectivity of the morphism ${A'\rightarrow B'}$ . But we know that the square

is commutative. We wish to define ${\ker(\gamma)\rightarrow coker(\alpha)}$ by ${x''\mapsto y'+im(\alpha)}$ . Observe that

$\displaystyle y'+\alpha(x')\mapsto\beta(x)+\beta(\widehat{x}-x)=\beta(\widehat{x}),$

and so the choice of preimage of ${x''}$ does not affect which cokernel element we ultimately select. So now we have our connecting morphism. By applying this definition we see that

$\displaystyle \ker(\beta)\rightarrow\ker(\gamma)\rightarrow coker(\alpha)\rightarrow coker(\beta)$

is a complex.

Suppose ${x''\in\ker(\gamma)}$ is sent to ${0}$ by the connecting morphism. Thus we have a diagram

which is commutative. Let ${\widehat{x}}$ be the image of ${x'}$ under the morphism ${A\rightarrow B}$ . Exactness of the diagram implies that ${x-\widehat{x}}$ is a preimage of ${x''}$ . But ${\beta(x-\widehat{x})=0}$ . So the kernel-cokernel sequence is exact at ${\ker(\gamma)}$ . The proof that it is exact at ${coker(\alpha)}$ is similar.

$\Box$

Group Theory and the Rubik’s Cube by Janet Chen

January 12, 2012 in Mathematics Posts | Tags: abstract algebra, alternating group, burnside, cayley graph, christoph bandelow, configurations, conjugacy, david s. dummit, david singmaster, disjoint cycle decomposition, douglas hofstadter, elementary number theory, ernő rubik, functions, generators, god’s number, graph diameter, group actions, group homomorphisms, group theory, groups, high school students, homomorphism, hungarian, i. n. herstein, janet chen, modular arithmetic, number theory, pólya, pólya-burnside lemma, puzzle, richard m. foote, rubik’s cube, rubik’s graph, rubik’s group, sign homomorphisms, subgroups, symmetric group, symmetries, texas state honors summer math camp, tomas rokicki | 1 comment

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 $3\times3\times3$ 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

$\frac{8!\cdot12!\cdot3^{8}\cdot2^{12}}{2\cdot3\cdot2}=43252003274489856000$

(Turner and Gold 1985, Schönert). Hoey showed using the Pólya-Burnside lemma that there are $901083404981813616$ 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

Read the article here.

Visit Janet Chen’s website here.

Finite Groups

December 20, 2011 in Mathematics Posts | Tags: abelian groups, abelian rings, congruence classes, coset, cyclic group, cyclic subgroup, division ring, equivalence class, equivalence relation, euler, euler totient, fermat, fermat's little theorem, fields, finite field, finite groups, group of units in the integers mod n, groups, infinity of primes, integral domain, lagrange, lagrange’s resolution, modular arithmetic, prime numbers, rings, subfield, subgroups, zero-divisors | Leave a comment

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.

Definition 1 Let ${G}$ be a nonempty set and ${*:G\times G\rightarrow G}$ be a binary operation on ${G.}$ Then the set ${G}$ together with the binary operation ${*}$ , denoted ${(G,*)}$ , is a group, if the following three conditions are satisfied:

i. The binary operation ${*}$ is associative, i.e., ${(a*b)*c=a*(b*c)}$ for all ${a,b,c\in G}$ .