lacunary - Mathnotes

Groups

Definition

Definition: group \@{group}

A group is a set G together with a binary operation such that:

Closure: The set is closed under the binary operation. For all a,bG,abG.

Associativity: The binary operation is associative on the set. For all a,b,cG,(ab)c=a(bc).

Identity: The set contains an identity element, denoted e. For all aG,ae=a.

Inverses: All elements in the set have inverse elements in the set, denoted using a1. For all aG there exists a1G such that aa1=e.

This set/operation combination G is commonly denoted as the pair (G,).

Referenced by (16 direct, 386 transitive)

Transitive (depth 1):

Transitive (depth 2):

Transitive (depth 3):

Transitive (depth 4):

Transitive (depth 5):

Transitive (depth 6):

Transitive (depth 7):

Transitive (depth 8):

Transitive (depth 9):

Transitive (depth 10):

Transitive (depth 11):

Transitive (depth 12):

Examples

Example: Examples of Groups \@{example-2}

Some examples of groups:

  • The integers under addition: (Z,+). The identity element is 0.
  • The non-zero reals under multiplication: (R,). The identity element is 1.
  • n×n invertible matrices.

Loads more listed here.

A non-example is the naturals under addition - (N,+). The naturals are closed under addition, but there is no identity element since 0 isn't included, and thus no inverses either.

Abelian Groups

Definition: Abelian \@{abelian}

Abelian groups are groups whose operation is commutative. For a,bG,ab=ba.

Referenced by (5 direct, 373 transitive)

Transitive (depth 1):

Transitive (depth 2):

Transitive (depth 3):

Transitive (depth 4):

Transitive (depth 5):

Transitive (depth 6):

Transitive (depth 7):

Transitive (depth 8):

Transitive (depth 9):

Transitive (depth 10):

Transitive (depth 11):

Transitive (depth 12):

Example: Abelian and Non-Abelian Groups \@{abelian-examples}

The integers under addition are Abelian, because a+b=b+a, but invertible n×n matrices are not, because it's not necessary that AB=BA.

Finite Groups

The examples given so far are all infinite groups, but finite groups also exist.

Example: A Finite Group \@{z4-finite-group}

(Z4,+4) i.e. {0,1,2,3} together with addition mod 4 is a finite group.

Subgroups

Definition: subgroup \@{subgroup}

A subgroup H of a group G is a subset of G together with the same operation as G that still forms a group. The identity element of G must also be the identity element of H.

Example: Even Integers as a Subgroup \@{even-integers-subgroup}

The even integers under addition, (2Z,+), are a subgroup of the integers under addition.

Definition: normal \@{normal}

A subgroup H of a group G is normal if its left and right cosets coincide, that is, if gH=Hg, i.e. gHg1=H, for all gG.

Referenced by (3 direct, 3 transitive)

Direct references:

Cyclic Groups

Definition: cyclic group \@{cyclic-group}

A cyclic group is a group where there exists some gG such that every element in G can be generated from the group operation applied to g.

That is, G={gn|nZ} when we think of the operation as multiplication, or G={ng|nZ} when we think of the operation as addition.

Note: Generator Notation \@{note-10}

We use angle brackets to denote an element as a generator. For example, 1 is a generator of (Z,+), because every integer can be written as n1 for some nZ.

Definition: order \@{order}

The order of a finite group is the number of its elements. The order of group G is denoted as ord(G) or G. The order of an element a (also called period length or period) is the number of elements in the subgroup generated by a, and is denoted by ord(a) or a.

Cyclic Subgroups

Definition: cyclic subgroup \@{cyclic-subgroup}

Any subgroup of a cyclic group is also cyclic - a cyclic subgroup.

Theorem \@{cyclic-subgroup-generated-by-powers}

Let G=a be a cyclic group with n elements. Let bG and b=as. Then b generates a cyclic subgroup of G containing nd elements, where d=gcd(s,n). Two cyclic subgroups as and at are equal if and only if gcd(s,n)=gcd(t,n).

Proof \@{proof-of-cyclic-subgroup-generated-by-powers}

Suppose gG with ord(g)=n and let mN. Then, gm=ggcd(m,n).

So, g=gmgcd(m,n)=1.

Every element of a cyclic finite group will generate a cyclic subgroup. Some of these subgroups will be equivalent to others - we denote each subgroup gs, where s is the smallest natural number that generates the subgroup.

To find the subgroups of a cyclic group, we follow this algorithm, keeping track of which elements we've found the generated subgroup for.

  1. Some element g will generate the entire group. If the group's order is n, then any element of the form gs where s and n are relatively prime will also generate the entire group, so note that we've found the generated subgroup for all of those elements.
  1. Starting with the next gs not covered already, find the subgroup generated by it - all elements of G of the form (gs)k. Note the order of this subgroup and call it t. Any elements of G of the form rgs where r is relatively prime with t will generate the same subgroup. Note that we've found the generated subgroup for all of those elements.
  1. Repeat step 2 until we've found the subgroup generated by all elements.
Example: Subgroups of Z20 \@{example-16}

This sounds really abstract, so here's an example of finding all of the subgroups of (Z20,+20)

Cyclic Subgroups of <math alttext="Z_{20}" xmlns="http://www.w3.org/1998/Math/MathML"><msub><mi>Z</mi><mrow data-mjx-texclass="ORD"><mn>20</mn></mrow></msub></math>

The diagram in this image is called a subgroup diagram or subgroup lattice. It represents containment - so a node being higher on the diagram indicates that any nodes below it are subsets of it.

Permutations

Example: Permutation Matrix Notation \@{example-17}

If we rearrange the ordered set A={1,2,3,4,5} to another order, say {3,2,5,1,4}, then we get a permutation of A.

This rearrangement is a bijection from A to A that performs

1322354154

We can represent this permutation compactly using a matrix

(1234532514)

Here, the top row is the input and the bottom row is the output, column-wise.

Definition: permutation \@{permutation}

A permutation is a bijection ϕ:AA, that is, a bijection from a set onto itself.

Note \@{permutations-usually-finite}

Generally, we talk about permutations on finite sets, but this doesn't seem to be a hard and fast rule.

The set of all permutations on the set A is denoted by SA:

SA={ϕ:AA|ϕ is a bijection}

Definition: symmetric group \@{symmetric-group}

When A is the finite set {1,2,3,,n}, the group of all permutations of A is the symmetric group on n letters, and is denoted by Sn. It has n! elements.

Definition: permutation multiplication \@{permutation-multiplication}

Permutations can be "multiplied", which is just composition. So if we have two permutations on A, called σ and τ, στ means their multiplication, and we apply from right to left, so τ applies first and then σ. The result will also be a permutation in A.

Referenced by (2 direct)

Permutation multiplication of permutations of a set forms a group:

Theorem \@{permutations-form-group}

Let A be a nonempty set, and SA be the collection of all permutations of A. Then SA is a group under permutation multiplication.

Orbits

Definition: orbit containing a point \@{orbit-containing-a-point}

Let σ be a permutation of A, the orbit of σ containing aA is the set

{,σ2(a),σ1(a),a,σ(a),σ2(a),}={σn(a)|nZ}.

So, a,bA are in the same orbit of σ, written as ab, if and only if b=σn(a) for some nZ.

The relation "~" is an equivalence relation (reflexive, symmetric, transitive). This means A can be partitioned into orbits of σ.

Definition: orbit \@{orbit}

Let σ be a permutation of A. The equivalence classes in A determined by the equivalence relation "~" are the orbits of σ.

Referenced by (1 direct, 2 transitive)

Direct references:

Transitive (depth 1):

Example: Orbits of a Permutation in S8 \@{example-25}

Consider σ=(12345678 38674152) in S8. The orbit of σ

  • containing 1 is {1,3,6} because σ(1)=3, σ(3)=6, and σ(6)=1.
  • containing 2 is {2,8}.
  • containing 4 is {4,5,7}.

So the orbits of σ are {1,3,6},{2,8},{4,5,7}.

Cycles

Definition: cycle \@{cycle}

A permutation σSn is a cycle if it has at most one orbit containing more than one element. The length of a cycle is the number of elements in its largest orbit.

Referenced by (2 direct)
Definition: cyclic notation \@{cyclic-notation}

A cycle in Sn may be written as (a1,a2,,ak) - this is called cyclic notation. It represents the permutation that sends a1a2aka1.

Definition: disjoint (cycle) \@{disjoint-cycle}

Two or more cycles are disjoint if no element appears in more than one cycle.

Theorem \@{permutation-as-product-of-disjoint-cycles}

Every permutation σ of a finite set is a product of disjoint cycles.

Even and Odd Permutations

Definition: transposition \@{transposition}

A cycle of length 2 is a transposition.

Definition: even (permutation) \@{even-permutation}

A permutation of a finite set is even if it is the product of an even number of transpositions.

Definition: odd (permutation) \@{odd-permutation}

A permutation of a finite set is odd if it is the product of an odd number of transpositions.

Theorem \@{permutation-parity-is-well-defined}

A permutation in Sn can be written as either a product of an odd number of transpositions or a product of an even number of transpositions, but not both.

Definition: alternating group \@{alternating-group}

The subgroup of Sn consisting of all even permutations of n letters is the alternating group An on n letters. If n2, then this set forms a subgroup of Sn of order n!/2.

Cosets

Definition: coset \@{coset}

Let H be a subgroup of G. Given aG, the subset aH={ah|hH} of G is the left coset of H containing a, while the subset Ha={ha|hH} is the right coset of H containing a.

Referenced by (1 direct)
Example: Left Cosets of 3Z \@{example-36}

Left cosets of subgroup 3Z of Z:

0+3Z={,9,6,0,3,6,9,}1+3Z={,8,5,1,4,7,10,}2+3Z={,7,4,2,5,8,11,}

Proposition: Properties of Cosets \@{coset-properties}
  • If aHbH, then aH=bH. This means we can partition G into left cosets of H.
  • If G is Abelian, the left cosets and right cosets of H will be equal. So, in the example above, a+3Z=3Z+a.
  • The order of aH is the order of H, that is, aH=H. Thus, cosets of a subgroup are of equal size.
Definition: index \@{index}

The number of left cosets of a subgroup H in a group G is the index (G:H) of H in G.

Referenced by (1 direct)

Direct references:

From the example above, the index of 3Z in Z is 3 since there are 3 left cosets.

Layered Cosets

Here's a proof from a homework exercise I did.

Theorem \@{lagrange-theorem-for-indices}

Suppose H and K are subgroups of a group G such that KHG, and suppose that (H:K) and (G:H) are both finite. Then (G:K)=(G:H)(H:K) is finite.

Intuition \@{lagrange-theorem-for-indices-intuition}

The intuition here is that each coset of H can be partitioned into (H:K) cosets of K, and that G can be partitioned into (G:H) cosets of H, so G can be partitioned into (G:K)=(G:H)(H:K) cosets of K. Since both (G:H) and (H:K) are given as finite, their product is also finite.

Proof \@{proof-of-lagrange-theorem-for-indices}

In more detail, say G can be partitioned into n=(G:H) cosets of H, where n is a natural number. Let A be a set of coset representatives AG such that P=aiAaiH is a partition of G formed by the left cosets of H.

Then, P is

P={a1H,a2H,a3H,,anH},(a)

and each aiH is a disjoint coset of H in G.

Now, H can be partitioned into m=(H:K) cosets of K, where m is a natural number. Let B be a set of coset representatives BH such that Q=biBbiK is a partition of H formed by the left cosets of K.

Then, Q={b1K,b2K,b3K,,bmK}. Now, we can recover H by taking the union of the elements of Q, that is, H=qQq, so the elements of Q, after a round of flattening, are the same as those of H. If we replace H in (a) with Q, distribute each an group action over the elements of Q, and then take the union across each resulting set we end up with

R={a1b1K,a1b2K,a1b3K,,a1bmK,a2b1K,a2b2K,a2b3K,,a2bmK,a3b1K,a3b2K,a3b3K,,a3bmK,,anb1K,anb2K,anb3K,,anbmK},

which is G partitioned into the left cosets of K. Because we constructed each element in R by partitioning the elements of a partition of G into cosets of K (then taking their union), we know they are disjoint and cover all of G. There are nm=(G:H)(H:K)=(G:K) elements in R, and since n and m are finite, so is (G:K).

Homomorphisms

Definition: homomorphism (group) \@{homomorphism-group}

A homomorphism is a map ϕ:GG between groups (not necessarily a bijection), G, and G,, that satisfies the homomorphism property:

ϕ(ab)=ϕ(a)ϕ(b), a,bG.

Referenced by (2 direct, 1 transitive)

Homomorphisms have some nice properties.

Proposition: Properties of Group Homomorphisms \@{homomorphism-properties}

Suppose that ϕ:GG is a group homomorphism. Then the following properties hold.

  1. If e is the identity of G, then ϕ(e) is the identity e in G.
  1. If aG, then ϕ(a1)=ϕ(a)1.
  1. If H is a subgroup of G, then the image of H in G is a subgroup of G.
  1. If K is a subgroup of G, then the inverse image, ϕ1[K]={gG|ϕ(g)K} is a subgroup of G.
Definition: kernel \@{kernel}

The kernel of a homomorphism ϕ is the set of elements that ϕ sends to e, and it is denoted by ker(ϕ). It is a normal subgroup of G.

Referenced by (1 direct)
Theorem \@{homomorphism-injective-iff-trivial-kernel}

One useful fact you may recall from linear algebra that also applies with group homomorphisms is that ϕ is injective iff the kernel of ϕ is {e}.

Simple Groups

Definition: simple \@{simple}

A group G is simple if it has no proper nontrivial normal subgroups, that is, if |G|>1 and the only normal subgroups of G are {e} and G itself.

Every group G has two important normal subgroups, the center and the commutator subgroup.

Definition: center (group) \@{center-group}

The center of a group G is all the elements that commute with all elements of G:

Z(G)={zG|zg=gz for all gG}.

Referenced by (1 direct)

Direct references:

Definition: commutator \@{commutator}

The commutator subgroup of G is the group C generated by all elements of the set

{aba1b1|a,bG}.

Referenced by (1 direct)

Direct references: