New algebra handouts on my website

For olympiad students: I have now published some new algebra handouts. They are:

• Introduction to Functional Equations, which cover the basic techniques and theory for FE’s typically appearing on olympiads like USA(J)MO.
• Monsters, an advanced handout which covers functional equations that have pathological solutions. It covers in detail the solutions to Cauchy functional equation.
• Summation, which is a compilation of various types of olympiad-style sums like generating functions and multiplicative number theory.

I have also uploaded:

• English, notes on proof-writing that I used at the 2016 MOP (Mathematical Olympiad Summer Program).

You can download all these (and other handouts) from my MIT website. Enjoy!

The Structure Theorem over PID’s

In this post I’ll describe the structure theorem over PID’s which generalizes the following results:

• Finite dimensional vector fields over are all of the form ,
• The classification theorem for finitely generated abelian groups,
• The Frobenius normal form of a matrix,
• The Jordan decomposition of a matrix.

1. Some ring theory prerequisites

Prototypical example for this section: .

Before I can state the main theorem, I need to define a few terms for UFD’s, which behave much like : Our intuition from the case basically carries over verbatim. We don’t even need to deal with prime ideals and can factor elements instead.

Definition 1

If is a UFD, then is a prime element if is a prime ideal and . For UFD’s this is equivalent to the following property: if then either or is a unit.

So for example in the set of prime elements is . Now, since is a UFD, every element factors into a product of prime elements

Definition 2

We say divides if for some . This is written .

Example 3 (Divisibility in )

The number is divisible by every element of . All other divisibility as expected.

Ques 4

Show that if and only if the exponent of each prime in is less than or equal to the corresponding exponent in .

Now, the case of interest is the even stronger case when is a PID:

Proposition 5 (PID’s are Noetherian UFD’s)

If is a PID, then it is Noetherian and also a UFD.

Proof: The fact that is Noetherian is obvious. For to be a UFD we essentially repeat the proof for , using the fact that is principal in order to extract .

In this case, we have a Chinese remainder theorem for elements.

Theorem 6 (Chinese remainder theorem for rings)

Let and be relatively prime elements, meaning . Then

Proof: This is the same as the proof of the usual Chinese remainder theorem. First, since we have for some and . Then we have a map

One can check that this map is well-defined and an isomorphism of rings. (Diligent readers invited to do so.)

Finally, we need to introduce the concept of a Noetherian -module.

Definition 7

An -module is Noetherian if it satisfies one of the two equivalent conditions:

• Its submodules obey the ascending chain condition: there is no infinite sequence of modules .
• All submodules of (including itself) are finitely generated.

This generalizes the notion of a Noetherian ring: a Noetherian ring is one for which is Noetherian as an -module.

Ques 8

Check these two conditions are equivalent. (Copy the proof for rings.)

2. The structure theorem

Our structure theorem takes two forms:

Theorem 9 (Structure theorem, invariant form)

Let be a PID and let be any finitely generated -module. Then

for some satisfying .

Corollary 10 (Structure theorem, primary form)

Let be a PID and let be any finitely generated -module. Then

where for some prime element and integer .

Proof: Factor each into prime factors (since is a UFD), then use the Chinese remainder theorem.

Remark 11

In both theorems the decomposition is unique up to permutations of the summands; good to know, but I won’t prove this.

3. Reduction to maps of free -modules

The proof of the structure theorem proceeds in two main steps. First, we reduce the problem to a linear algebra problem involving free -modules . Once that’s done, we just have to play with matrices; this is done in the next section.

Suppose is finitely generated by elements. Then there is a surjective map of -modules

whose image on the basis of are the generators of . Let denote the kernel.

We claim that is finitely generated as well. To this end we prove that

Lemma 12 (Direct sum of Noetherian modules is Noetherian)

Let and be two Noetherian -modules. Then the direct sum is also a Noetherian -module.

Proof: It suffices to show that if , then is finitely generated. It’s unfortunately not true that (take ) so we will have to be more careful.

Consider the submodules

(Note the asymmetry for and : the proof doesn’t work otherwise.) Then is finitely generated by , \dots, , and is finitely generated by , \dots, . Let and let be elements of (where the ‘s are arbitrary things we don’t care about). Then and together generate .

Ques 13

Deduce that for a PID, is Noetherian.

Hence is finitely generated as claimed. So we can find another surjective map . Consequently, we have a composition

Observe that is the cokernel of the composition , i.e. we have that

So it suffices to understand the map well.

4. Smith normal form

The idea is now that we have reduced our problem to studying linear maps , which can be thought of as a generic matrix

for the standard basis , \dots, of and , \dots, of .

Of course, as you might expect it ought to be possible to change the given basis of such that has a nicer matrix form. We already saw this in Jordan form, where we had a map and changed the basis so that was “almost diagonal”. This time, we have two sets of bases we can change, so we would hope to get a diagonal basis, or even better.

Before proceeding let’s think about how we might edit the matrix: what operations are permitted? Here are some examples:

• Swapping rows and columns, which just corresponds to re-ordering the basis.
• Adding a multiple of a column to another column. For example, if we add times the first column to the second column, this is equivalent to replacing the basis

  

• Adding a multiple of a row to another row. One can see that adding times the first row to the second row is equivalent to replacing the basis

  

More generally, If is an invertible matrix we can replace with . This corresponds to replacing

(the “invertible” condition just guarantees the latter is a basis). Of course similarly we can replace with where is an invertible matrix; this corresponds to

Armed with this knowledge, we can now approach the following result.

Theorem 14 (Smith normal form)

Let be a PID. Let and be free -modules and let be a linear map. Set .

Then we can select a pair of new bases for and such that has only diagonal entries , , \dots, and .

So if , the matrix should take the form

and similarly when .

Ques 15

Show that Smith normal form implies the structure theorem.

Remark 16

Note that this is not a generalization of Jordan form.

• In Jordan form we consider maps ; note that the source and target space are the same, and we are considering one basis for the space .
• In Smith form the maps are between different modules, and we pick two sets of bases (one for and one for ).

Example 17 (Example of Smith normal form)

To give a flavor of the idea of the proof, let’s work through a concrete example with the following matrix with entries from :

The GCD of all the entries is , and so motivated by this, we perform the Euclidean algorithm on the left column: subtract the second row from the first row, then three times the first row from the second:

Now that the GCD of is present, we move it to the upper-left by switching the two rows, and then kill off all the entries in the same row/column; since was the GCD all along, we isolate completely:

This reduces the problem to a matrix. So we just apply the Euclidean algorithm again there:

Now all we have to do is generalize this proof to work with any PID. It’s intuitively clear how to do this: the PID condition more or less lets you perform a Euclidean algorithm.

Proof: Begin with a generic matrix

We want to show, by a series of operations (gradually changing the given basis) that we can rearrange the matrix into Smith normal form.

Define to be any generator of the principal ideal .

Claim 18 (“Euclidean algorithm”)

If and are entries in the same row or column, we can change bases to replace with and with something else.

Proof: We do just the case of columns. By hypothesis, for some . We must have now (we’re in a UFD). So there are and such that . Then

and the first matrix is invertible (check this!), as desired.
Let be the GCD of all entries. Now by repeatedly applying this algorithm, we can cause to appear in the upper left hand corner. Then, we use it to kill off all the entries in the first row and the first column, thus arriving at a matrix

Now we repeat the same procedure with this lower-right matrix, and so on. This gives the Smith normal form.

With the Smith normal form, we have in the original situation that

and applying the theorem to completes the proof of the structure theorem.

5. Applications

Now, we can apply our structure theorem! I’ll just sketch proofs of these and let the reader fill in details.

Corollary 19 (Finite-dimensional vector spaces are all isomorphic)

A vector space over a field has a finite spanning set of vectors. Then for some , .

Proof: In the structure theorem, .

Corollary 20 (Frobenius normal form)

Let where is a finite-dimensional vector space over an arbitrary field (not necessarily algebraically closed). Then one can write as a block-diagonal matrix whose blocks are all of the form

Proof: View as a -module with action . By theorem for some polynomials , where . Write each block in the form described.

Corollary 21 (Jordan normal form)

Let where is a finite-dimensional vector space over an arbitrary field which is algebraically closed. Prove that can be written in Jordan form.

Proof: We now use the structure theorem in its primary form. Since is algebraically closed each is a linear factor, so every summand looks like for some .

This is a draft of Chapter 15 of the Napkin.

Artin Reciprocity

I will tell you a story about the Reciprocity Law. After my thesis, I had the idea to define -series for non-abelian extensions. But for them to agree with the -series for abelian extensions, a certain isomorphism had to be true. I could show it implied all the standard reciprocity laws. So I called it the General Reciprocity Law and tried to prove it but couldn’t, even after many tries. Then I showed it to the other number theorists, but they all laughed at it, and I remember Hasse in particular telling me it couldn’t possibly be true.

Still, I kept at it, but nothing I tried worked. Not a week went by — for three years! — that I did not try to prove the Reciprocity Law. It was discouraging, and meanwhile I turned to other things. Then one afternoon I had nothing special to do, so I said, `Well, I try to prove the Reciprocity Law again.’ So I went out and sat down in the garden. You see, from the very beginning I had the idea to use the cyclotomic fields, but they never worked, and now I suddenly saw that all this time I had been using them in the wrong way — and in half an hour I had it.

— Emil Artin

Algebraic number theory assumed (e.g. the ANT chapters of Napkin). In this post, I’m going to state some big theorems of global class field theory and use them to deduce the Kronecker-Weber plus Hilbert class fields. For experts: this is global class field theory, without ideles.

Here’s the executive summary: let be a number field. Then all abelian extensions can be understood using solely information intrinsic to : namely, the ray class groups (generalizing ideal class groups).

1. Infinite primes

Let be a number field of degree . We know what a prime ideal of is, but we now allow for the so-called infinite primes, which I’ll describe using embeddings. We know there are embeddings , which consist of

• real embeddings where , and
• pairs of conjugate complex embeddings.

Hence . The first class of embeddings form the real infinite primes, while the complex infinite primes are the second type. We say is totally real (resp totally complex) if all its infinite primes are real (resp complex).

Example 1 (Examples of infinite primes)

• has a single real infinite prime. We often write it as .
• has a single complex infinite prime, and no real infinite primes. Hence totally complex.
• has two real infinite primes, and no complex infinite primes. Hence totally real.

The motivation from this actually comes from the theory of valuations. Every prime corresponds exactly to a valuation; the infinite primes correspond to the Archimedean valuations while the finite primes correspond to the non-Archimedean valuations.

2. Modular arithmetic with infinite primes

A modulus is a formal product

where the product runs over all primes, finite and infinite. (Here is a nonnegative integer, of which only finitely many are nonzero.) We also require that

• for any infinite prime , and
• for any real prime .

Obviously, every can be written as by separating the finite from the (real) infinite primes.

We say if

• If is a finite prime, then means exactly what you think it should mean: .
• If is a real infinite prime , then means that .

Of course, means modulo each prime power in . With this, we can define a generalization of the class group:

Definition 2

Let be a modulus of a number field .

• Let to be the set of all fractional ideals of which are relatively prime to , which is an abelian group.
• Let be the subgroup of generated by

  

  This is sometimes called a “ray” of principal ideals.

Finally define the ray class group of to be .

This group is known to always be finite. Note the usual class group is .

One last definition that we’ll use right after Artin reciprocity:

Definition 3

A congruence subgroup of is a subgroup with

Thus is a group which contains a lattice of various quotients , where is a congruence subgroup.

This definition takes a while to get used to, so here are examples.

Example 4 (Ray class groups in )

Consider with infinite prime . Then

• If we take then is all fractional ideals, and is all principal fractional ideals. Their quotient is the usual class group of , which is trivial.

 

• Now take . Thus . Moreover

  

  You might at first glance think that the quotient is thus . But the issue is that we are dealing with ideals: specifically, we have

  

  because . So actually, we get

  

   

• Now take . As before . Now, by definition we have

  

  At first glance you might think this was , but the same behavior with ideals shows in fact . So in this case, still has all principal fractional ideals. Therefore, is still trivial.

   

• Finally, let . As before . Now in this case:

  

  This time, we really do have : we have and also . So neither of the generators of are in . Thus we finally obtain

  

  with the bijection given by .

  Generalizing these examples, we see that

  

 

3. Infinite primes in extensions

I want to emphasize that everything above is intrinsic to a particular number field . After this point we are going to consider extensions but it is important to keep in mind the distinction that the concept of modulus and ray class group are objects defined solely from rather than the above .

Now take a Galois extension of degree . We already know prime ideals of break into a produt of prime ideals of in in a nice way, so we want to do the same thing with infinite primes. This is straightforward: each of the infinite primes lifts to infinite primes , by which I mean the diagram

commutes. Hence like before, each infinite prime of has infinite primes of which lie above it.

For a real prime of , any of the resulting above it are complex, we say that the prime ramifies in the extension . Otherwise it is unramified in . An infinite prime of is always unramified in . In this way, we can talk about an unramified Galois extension : it is one where all primes (finite or infinite) are unramified.

Example 5 (Ramification of )

Let be the real infinite prime of .

• is ramified in .
• is unramified in .

Note also that if is totally complex then any extension is unramified.

4. Frobenius element and Artin symbol

Recall the following key result:

Theorem 6 (Frobenius element)

Let be a Galois extension. If is a prime unramified in , and a prime above it in . Then there is a unique element of , denoted , obeying

Example 7 (Example of Frobenius elements)

Let , . We have .

If is an odd prime with above it, then is the unique element such that

in . In particular,

From this we see that is the identity when and is complex conjugation when .

Example 8 (Cyclotomic Frobenius element)

Generalizing previous example, let and , with an th root of unity. It’s well-known that is unramified outside and prime factors of . Moreover, the Galois group is : the Galois group consists of elements of the form

and .

Then it follows just like before that if is prime and is above

An important property of the Frobenius element is its order is related to the decomposition of in the higher field in the nicest way possible:

Lemma 9 (Order of the Frobenius element)

The Frobenius element of an extension has order equal to the inertial degree of , that is,

In particular, if and only if splits completely in .

Proof: We want to understand the order of the map on the field . But the latter is isomorphic to the splitting field of in , by Galois theory of finite fields. Hence the order is .

Exercise 10

Deduce from this that the rational primes which split completely in are exactly those with . Here is an th root of unity.

The Galois group acts transitively among the set of above a given , so that we have

Thus is determined by its underlying up to conjugation.

In class field theory, we are interested in abelian extensions, (which just means that is Galois) in which case the theory becomes extra nice: the conjugacy classes have size one.

Definition 11

Assume is an abelian extension. Then for a given unramified prime in , the element doesn’t depend on the choice of . We denote the resulting by the Artin symbol.

The definition of the Artin symbol is written deliberately to look like the Legendre symbol. To see why:

Example 12 (Legendre symbol subsumed by Artin symbol)

Suppose we want to understand where is prime. Consider the element

It is uniquely determined by where it sends . But in fact we have

where is the usual Legendre symbol, and is above in . Thus the Artin symbol generalizes the quadratic Legendre symbol.

Example 13 (Cubic Legendre symbol subsumed by Artin symbol)

Similarly, it also generalizes the cubic Legendre symbol. To see this, assume is primary in (thus is Eisenstein integers). Then for example

where is above in .

5. Artin reciprocity

Now, we further capitalize on the fact that is abelian. For brevity, in what follows let denote the primes of (either finite or infinite) which ramify in .

Definition 14

Let be an abelian extension and let be divisible by every prime in . Then since is abelian we can extend the Artin symbol multiplicatively to a map

This is called the Artin map, and it is surjective (for example by Chebotarev Density).

Since the map above is surjective, we denote its kernel by . Thus we have

We can now present the long-awaited Artin reciprocity theorem.

Theorem 15 (Artin reciprocity)

Let be an abelian extension. Then there is a modulus , divisible by exactly the primes of , with the following property: if is divisible by all primes of

We call the conductor of .

So the conductor plays a similar role to the discriminant (divisible by exactly the primes which ramify), and when is divisible by the conductor, is a congruence subgroup.

Note that for example, if we pick such that then Artin reciprocity means that there is an isomorphism

More generally, we see that is always a subgroup some subgroup .

Example 16 (Cyclotomic field)

Let be a primitive th root of unity. We show in this example that

This is the generic example of achieving the lower bound in Artin reciprocity. It also implies that .

It’s well-known is unramified outside finite primes dividing , so that the Artin symbol is defined on . Now the Artin map is given by

So we see that the kernel of this map is trivial, i.e.\ it is given by the identity of the Galois group, corresponding to Then for a unique abelian extension .

Finally, such subgroups reverse inclusion in the best way possible:

Lemma 17 (Inclusion-reversing congruence subgroups)

Fix a modulus . Let and be abelian extensions and suppose is divisible by the conductors of and . Then

Here by we mean that is isomorphic to some subfield of . Proof: Let us first prove the equivalence with fixed. In one direction, assume ; one can check from the definitions that the diagram

commutes, because it suffices to verify this for prime powers, which is just saying that Frobenius elements behave well with respect to restriction. Then the inclusion of kernels follows directly. The reverse direction is essentially the Takagi existence theorem.
Note that we can always take to be the product of conductors here.

6. Consequences

With all this theory we can deduce the following two results.

Corollary 18 (Kronecker-Weber theorem)

Let be an abelian extension of . Then is contained in a cyclic extension where is an th root of unity (for some ).

Proof: Suppose for some . Then by the example from earlier we have the chain

So by inclusion reversal we’re done.

Corollary 19 (Hilbert class field)

Let be any number field. Then there exists a unique abelian extension which is unramified at all primes (finite or infinite) and such that

• is the maximal such extension by inclusion.
• is isomorphic to the class group of .
• A prime of splits completely in if and only if it is principal.

We call the Hilbert class field of .

Proof: Apply the Takagi existence theorem with to obtain an unramified extension such that . We claim this works:

• To see it is maximal by inclusion, note that any other extension with this property has conductor (no primes divide the conductor), and then we have , so inclusion reversal gives .
• We have the class group.
• The isomorphism in the previous part is given by the Artin symbol. So splits completely if and only if if and only if is principal (trivial in ).

This completes the proof.

One can also derive quadratic and cubic reciprocity from Artin reciprocity; see this link for QR and this link for CR.

Tannakian Reconstruction

These notes are from the February 23, 2016 lecture of 18.757, Representations of Lie Algebras, taught by Laura Rider.

Fix a field and let be a finite group. In this post we will show that one can reconstruct the group from the monoidal category of -modules (i.e. its -representations).

1. Hopf algebras

We won’t do anything with Hopf algebras per se, but it will be convenient to have the language.

Recall that an associative -algebra is a -vector space equipped with a map and (unit), satisfying some certain axioms.

Then a -coalgebra is a map

called comultiplication and counit respectively, which satisfy the dual axioms. See \url{https://en.wikipedia.org/wiki/Coalgebra}.

Now a Hopf algebra is a bialgebra over plus a so-called antipode . We require that the diagram

commutes.

Given a Hopf algebra group-like element in is an element of

Exercise 1

Show that is a group with multiplication and inversion .

Now the example

Example 2 (Group algebra is Hopf algebra)

The group algebra is a Hopf algebra with

• , as expected.
• the counit is the trivial representation.
• comes form extended linearly.
• takes extended linearly.

 

Theorem 3

The group-like elements are precisely the basis elements .

 

Proof: Assume is grouplike. Then by assumption we should have

Comparing each coefficient, we get that

This can only occur if some is and the remaining coefficients are all zero.

 

2. Monoidal functors

Recall that monoidal category (or tensor category) is a category equipped with a functor which has an identity and satisfies some certain coherence conditions. For example, for any we should have a natural isomorphism

The generic example is of course suggested by the notation: vector spaces over , abelian groups, or more generally modules/algebras over a ring .

Now take two monoidal categories and . Then a monoidal functor is a functor for which we additionally need to select an isomorphism

We then require that the diagram

commutes, plus some additional compatibility conditions with the identities of the ‘s (see Wikipedia for the list).

We also have a notion of a natural transformation of two functors ; this is just making the squares

commute. Now, suppose is a monoidal functor. Then an automorphism of is a natural transformation which is invertible, i.e. a natural isomorphism.

3. Application to

With this language, we now reach the main point of the post. Consider the category of modules endowed with the monoidal (which is just the tensor over , with the usual group representation). We want to reconstruct from this category.

Let be the forgetful functor

It’s easy to see this is in fact an monoidal functor. Now let be the set of monoidal automorphisms of .

The key claim is the following:

Theorem 4 ( is isomorphic to )

Consider the map

Here, the natural transformation is defined by the components

Then is an isomorphism of groups.

In particular, using only structure this exhibits an isomorphism . Consequently this solves the problem proposed at the beginning of the lecture.

Proof: It’s easy to see is a group homomorphism.

To see it’s injective, we show gives isn’t the identity automorphism. i.e. we need to find some representation for which acts nontrivially on . Now just take the regular representation, which is faithful!

The hard part is showing that it’s surjective. For this we want to reduce it to the regular representation.

Lemma 5

Any is completely determined by .

 

Proof: Let be a representation of . Then for all , we have a unique morphism of representations

If we apply the forgetful functor to this, we have a diagram

Next, we claim

Lemma 6

is a grouplike element of .

 

Proof: Draw the diagram

and note that it implies

This implies surjectivity, by our earlier observation that grouplike elements in are exactly the elements of .

 

Rant: Matrices Are Not Arrays of Numbers

The following is an excerpt from a current work of mine. I thought I’d share it here, as some people have told me they enjoyed it.

As I’ll stress repeatedly, a matrix represents a linear map between two vector spaces. Writing it in the form of an matrix is merely a very convenient way to see the map concretely. But it obfuscates the fact that this map is, well, a map, not an array of numbers.

If you took high school precalculus, you’ll see everything done in terms of matrices. To any typical high school student, a matrix is an array of numbers. No one is sure what exactly these numbers represent, but they’re told how to magically multiply these arrays to get more arrays. They’re told that the matrix

is an “identity matrix”, because when you multiply by another matrix it doesn’t change. Then they’re told that the determinant is some magical combination of these numbers formed by this weird multiplication rule. No one knows what this determinant does, other than the fact that , and something about areas and row operations and Cramer’s rule.

Then you go into linear algebra in college, and you do more magic with these arrays of numbers. You’re told that two matrices and are similar if

for some invertible matrix . You’re told that the trace of a matrix is the sum of the diagonal entries. Somehow this doesn’t change if you look at a similar matrix, but you’re not sure why. Then you define the characteristic polynomial as

Somehow this also doesn’t change if you take a similar matrix, but now you really don’t know why. And then you have the Cayley-Hamilton Theorem in all its black magic: is the zero map. Out of curiosity you Google the proof, and you find some ad-hoc procedure which still leaves you with no idea why it’s true.

This is terrible. Who gives a — about ? Only if you know that the matrices are linear maps does this make sense: is just rewritten with a different choice of basis.

In my eyes, this mess is evil. Linear algebra is the study of linear maps, but it is taught as the study of arrays of numbers, and no one knows what these numbers mean. And for a good reason: the numbers are meaningless. They are a highly convenient way of encoding the matrix, but they are not the main objects of study, any more than the dates of events are the main objects of study in history.

When I took Math 55a as a freshman at Harvard, I got the exact opposite treatment: we did all of linear algebra without writing down a single matrix. During all this time I was quite confused. What’s wrong with a basis? I didn’t appreciate until later that this approach was the morally correct way to treat the subject: it made it clear what was happening.

Throughout this project, I’ve tried to strike a balance between these two approaches, using matrices to illustrate the maps and to simplify proofs, but writing theorems and definitions in their morally correct form. I hope that this has both the advantage of giving the “right” definitions while being concrete enough to be digested. But I would just like to say for the record that, if I had to pick between the high school approach and the 55a approach, I would pick 55a in a heartbeat.

Representation Theory, Part 4: The Finite Regular Representation

Good luck to everyone taking the January TST for the IMO 2015 tomorrow!

Now that we have products of irreducibles under our belt, I’ll talk about the finite regular representation and use it to derive the following two results about irreducibles.

1. The number of (isomorphsim classes) of irreducibles is equal to the number of conjugacy classes of .
2. We have .

These will actually follow as corollaries from the complete decomposition of the finite regular representation.

In what follows is an algebraically closed field, is a finite group, and the characteristic of does not divide . As a reminder, here are the representations we’ve already seen in the order we met them, plus two new ones we’ll introduce properly below.

1. The Regular Representation

Recall that is the vector space of functions from to , with addition being defined canonically. It has a basis of functions for each , where

for every . (Throughout this post, I’ll be trying to use to denote inputs to a function from to .)

Definition Let be a finite group. Then the finite regular representation, is a representation on defined on the vector space , with the following action for each and :

Note that this is a representation of the product , not ! (As an aside, you can also define this representation for infinite groups by replacing with , the functions which are nonzero at only finitely many .)

In any case, we now can make into a representation of by this restriction, giving , which I will abbreviate as just through out this post (this is not a standard notation). The action for this is

Exercise Consider the invariant subspace of , which is

Prove that the dimension of this space is equal to the number of conjugacy classes of . (Look at the basis.)

Recall that in general, the invariant subspace is defined as

2. Dual Representations

Before I can state the main theorem of this post, I need to define the dual representation.

Recall that given a vector space , we define the \textbf} by

i.e. it is the set of maps from to . If is finite-dimensional, we can think of this as follows: if consists of the column vectors of length , then is the row vectors of length , which can be multiplied onto elements of . (This analogy breaks down for infinite dimensional.) Recall that if is finite-dimensional then there is a canonical isomorphism by the map , where sends .

Now we can define the dual representation in a similar way.

Definition Let be a -representation. Then we define the dual representation by

Lemma 1 If is finite-dimensional then by the same isomorphism.

Proof: We want to check that the isomorphism by respects the action of . That’s equivalent to checking

But

and

So the functions are indeed equal.

Along with that lemma, we also have the following property.

Lemma 2 For any finite-dimensional , we have .

Proof: Let and . We already know that we have an isomorphism of vector homomorphisms

by sending each to the map which has . So the point is to check that respects the -action if and only if does. This is just a computation.

You can deduce as a corollary the following.

Exercise Use the lemma to show .

Finally, we want to talk about when being irreducible. The main result is the following.

Lemma 3 Consider a representation , not necessarily finite-dimensional. If is irreducible then so is .

When is finite dimensional we have , and so it is true for finite-dimensional irreducible that is also irreducible. Interestingly, this result fails for infinite-dimensional spaces as this math.SE thread shows.

Proof: Let . Let be a -invariant subspace of . Then consider

This is a -invariant subspace of , so since is irreducible, either or . You can check that these imply and , respectively.

3. Main Result

Now that we know about the product of representations and dual modules, we can state the main result of this post: the complete decomposition of .

Theorem 4 We have an isomorphism

Before we can begin the proof of the theorem we need one more lemma.

Lemma 5 Let be a representation of . Then there is an isomorphism

Proof: Let . Given a map which respects the action, we send it to the map with . Conversely, given a map which respects the action, we send it to the map so that .

Some very boring calculations show that the two maps are mutually inverse and respect the action. We’ll just do one of them here: let us show that respects the action given that respects the action. We want to prove

Using the definition of

The remaining computations are left to a very diligent reader.

Now let’s prove the main theorem!

Proof: We have that is the sum of finite-dimensional irreducibles , meaning

But using our lemmas, we have that

We know that is also irreducible, since is (and we’re in a finite-dimensional situation). So

Thus we deduce

and we’re done.

4. Corollaries

Recall that , the space underlying , has a basis with size . Hence by comparing the dimensions of the isomorphsims, we obtain the following corollary.

Theorem 6 We have .

Moreover, by restriction to we can obtain the corollary

Now let us look at the -invariant spaces in this decomposition. We claim that

Indeed, {Proposition 1} in {Part 1} tells us that we have a bijection of vector spaces

Then we can write

by the lemma, where we have also used Schur’s Lemma at the last step. So that means the dimension of the invariant space is just the number of irreducibles.

But we already showed that the invariant space of has dimension equal to the conjugacy classes of . Thus we conclude the second result.

Theorem 7 The number of conjugacy classes of equals the number of irreducible representations of .

Hooray!

Time permitting I might talk about the irreducibles of in subsequent posts. No promises here though.

Thanks to Dennis Gaitsgory, who taught me this in his course Math 55a. My notes for Math 55a can be found at my website.

Represenation Theory, Part 3: Products of Representations

Happy New Year to all! A quick reminder that .

This post will set the stage by examining products of two representations. In particular, I’ll characterize all the irreducibles of in terms of those for and . This will set the stage for our discussion of the finite regular representation in Part 4.

In what follows is an algebraically closed field, is a finite group, and the characteristic of does not divide .

1. Products of Representations

First, I need to tell you how to take the product of two representations.

Definition Let and be groups. Given a representation and a representation , we define

as a representation of on . The action is given by

In the special case , we can also restrict to a representation of . Note that we can interpret itself as a subgroup of by just looking along the diagonal: there’s an obvious isomorphism

So, let me set up the general definition.

Definition Let be a group, and let be a subgroup of . Then for any representation of , we let

denote the representation of on by the same action.

This notation might look intimidating, but it’s not really saying anything, and I include the notation just to be pedantic. All we’re doing is taking a representation and restricting which elements of the group are acting on it.

We now apply this to get out of .

Definition Let and be representations of . Then we define

meaning has vector space and action .

This tensor product obeys some nice properties, for example the following.

Lemma 1 Given representations , , we have

Proof: There’s an obvious isomorphism between the underlying vector spaces, and that isomorphism respects the action of .

To summarize all the above, here is a table of the representations we’ve seen, in the order we met them.

2. Revisiting Schur and Maschke

Defining a tensor product of representations gives us another way to express , as follows. By an abuse of notation, given a vector space we can define an associated -representation on it by the trivial action, i.e. for . A special case of this is using to represent . With this abuse of notation, we have the following lemma.

Lemma 2 Let be an -dimensional vector space over . Then .

Proof: It reduces to checking that is isomorphic to , which is evident. We can then proceed by induction: .

So, we can actually rewrite Maschke’s and Schur’s Theorem as one. Instead of

we now have instead

Now we’re going to explicitly write down the isomorphism between these maps. It suffices to write down the isomorphism , and then take the sum over each of the ‘s. But

So to write the isomorphism , we just have to write down the isomorphism ,

Schur’s Lemma tells us that ; i.e. every just corresponds to multiplying by some constant. So this case is easy: the map

works nicely. And since all we’ve done is break over a bunch of direct sums, the isomorphism propagates all the way up, resulting in the following theorem.

Theorem 3 (Maschke and Schur) For any finite-dimensional , the homomorphism of representations

given by sending every simple tensor via

is an isomorphism.

Note that it’s much easier to write the map from left to right than vice-versa, even though the inverse map does exist (since it’s an isomorphism). (Tip: as a general rule of thumb, always map out of the direct sum.)

3. Characterizing the irreducibles

Now we are in a position to state the main theorem for this post, which shows that the irreducibles we defined above are very well behaved.

Theorem 4 Let and be finite groups. Then a finite-dimensional representation of is irreducible if and only if it is of the form

where and are irreducible representations of and , respectively.

Proof: First, suppose is an irreducible representation of . Set

Then by Maschke’s Theorem, we may write as a direct sum of the irreducibles

with the map being the isomorphism. Now we can put a representation structure on by

It is easy to check that this is indeed a representation. Thus it makes sense to talk about the representation

We claim that the isomorphism for as a representation now lifts to an isomorphism of representations. That is, we claim that

by the same isomorphism as for . To see this, we only have to check that the isomorphism commutes with the action of . But this is obvious, since .

Thus the isomorphism holds. But is irreducible, so there can only be one nontrivial summand. Thus we derive the required decomposition of .

Now for the other direction: take and irreducible. Suppose has a nontrivial subrepresentation of the form . Viewing as representation, we find that is a nontrivial subrepresentation of , and similarly for . But is irreducible, hence . Similarly . So in fact . Hence we conclude is irreducible.

4. Conclusion

In particular, this means that any representation of decomposes as

and we even have

In the next post I’ll invoke this on the so-called finite regular representation to get the elegant results I promised at the end of Part 2.

Thanks to Dennis Gaitsgory, who taught me this in his course Math 55a. My notes for Math 55a can be found at my website.

Representation Theory, Part 2: Schur’s Lemma

Merry Christmas!

In the previous post I introduced the idea of an irreducible representation and showed that except in fields of low characteristic, these representations decompose completely. In this post I’ll present Schur’s Lemma at talk about what Schur and Maschke tell us about homomorphisms of representations.

1. Motivation

Fix a group now, and consider all isomorphism classes of finite-dimensional representations of . We’ll denote this set by . Maschke’s Theorem tells us that any finite-dimensional representation can be decomposed as

where is some nonnegative integer. This begs the question: what is ? Is it even uniquely determined by ?

To answer this I first need to compute for any two distinct irreducible representations and . One case is easy.

Lemma 1 Let and be non-isomorphic irreducible representations (not necessarily finite dimensional). Then there are no nontrivial homomorphisms . In other words, .

I haven’t actually told you what it means for representations to be isomorphic, but you can guess — it just means that there’s a homomorphism of -representations between them which is also a bijection of the underlying vector spaces.

Proof: Let be a nonzero homomorphism. We can actually prove the following stronger results.

• If is irreducible then is surjective.
• If is irreducible then is injective.

Exercise Prove the above two results. (Hint: show that and give rise to subrepresentations.)

Combining these two results gives the lemma because is now a bijection, and hence an isomorphism.

2. Schur’s Lemma

Thus we only have to consider the case . The result which relates these is called Schur’s Lemma, but is important enough that we refer to it as a theorem.

Theorem 2 (Schur’s Lemma) Assume is algebraically closed. Let be a finite dimensional irreducible representation. Then consists precisely of maps of the form , where ; the only possible maps are multiplication by a scalar. In other words,

and .

This is NOT in general true without the algebraically closed condition, as the following example shows.

Example Let , let , and let act on by rotating every by around the origin, giving a representation . Then is a counterexample to Schur’s Lemma.

Proof: This representation is clearly irreducible because the only point that it fixes is the origin, so there are no nontrivial subrepresentations.

We can regard now as a map in which is multiplication by . Then for any other complex number , the map “multiplication by ” commutes with the map “multiplication by ”. So in fact

which has dimension .

Now we can give the proof of Schur’s Lemma.

Proof: Clearly any map respects the -action.

Now consider any . Set . Here’s the key: because is algebraically closed, and we’re over a finite dimensional vector space , the map has an eigenvalue . Hence by definition has a subspace over which is just multiplication by .

But then is a -invariant subspace of ! Since is irreducible, this can only happen if . That means is multiplication by for the entire space , as desired.

3. Computing dimensions of homomorphisms

Since we can now compute the dimension of the of any two irreducible representations, we can compute the dimension of the for any composition of irreducibles, as follows.

Corollary 3 We have

where the direct sums run over the isomorphism classes of irreducibles.

Proof: The just decomposes over each of the components as

Here we’re using the fact that (obvious) and its analog. The claim follows from our lemmas now.

As a special case of this, we can quickly derive the following.

Corollary 4 Suppose as above. Then for any particular ,

Proof: We have

as desired.

This settles the “unique decomposition” in the affirmative. Hurrah!

It might be worth noting that we didn’t actually need Schur’s Lemma if we were solely interested in uniqueness, since without it we would have obtained

However, the denominator in that expression is rather unsatisfying, don’t you think?

4. Conclusion

In summary, we have shown the following main results for finite dimensional representations of a group .

• Maschke’s Theorem: If is finite and does not divide , then any finite dimensional representation is a direct sum of irreducibles. This decomposition is unique up to isomorphism.
• Schur’s Lemma: If is algebraically closed, then for any irreducible , while there are no nontrivial homomorphisms between non-isomorphic irreducibles.

In the next post I’ll talk about products of irreducibles, and use them in the fourth post to prove two very elegant results about the irreducibles, as follows.

1. The number of (isomorphsim classes) of irreducibles is equal to the number of conjugacy classes of .
2. We have .

Thanks to Dennis Gaitsgory, who taught me this in his course Math 55a. My notes for Math 55a can be found at my website.

Representation Theory, Part 1: Irreducibles and Maschke’s Theorem

Good luck to everyone taking the December TST tomorrow!

The goal of this post is to give the reader a taste of representation theory, a la Math 55a. In theory, this post should be accessible to anyone with a knowledge of group actions and abstract vector spaces.

Fix a ground field (for all vector spaces). In this post I will introduce the concept of representations and irreducible representations. Using these basic definitions I will establish Maschke’s Theorem, which tells us that irreducibles and indecomposables are the same thing.

1. Definition and Examples

Let be a group.

Definition A representation of consists of a pair where is a vector space over and is a (left) group action of on which is linear in . If is finite-dimensional then the dimension of is just the dimension of .

Explicitly the conditions on are that

Note that another equivalent phrasing is that is a homomorphism from to the general linear group ; however, we will not use this phrasing.

By abuse of notation, we occasionally refer to by just its underlying vector space in the case that is clear from context. We may also abbreviate as just .

A simple example of a nontrivial representation is the following.

Example If and , then an example of an action is is simply

meaning we permute the basis elements of . We denote this representation by .

Let us give another useful example.

Definition Let be a set acted on by . We define the vector space

with the standard addition of functions.

Example We define a representation on by the following action: every gets sent to a by

By abuse of notation we will let refer both to the vector space and the corresponding representation.

Now that we have two nontrivial examples, we also give a trivial example.

Definition Let be a group. We define the trivial representation , or just , as the representation , where

for every . In other words, acts trivially on .

2. Homomorphisms of Representations

First, as a good budding algebraist (not really) I should define how these representations talk to each other.

Definition Let and be representations of the same group . A homomorphism of -representations is a linear map which respects the -action: for any and ,

The set of all these homomorphisms is written , which is itself a vector space over .

(Digression: For those of you that know category theory, you might realize by now that representations correspond to functors from a category (corresponding to the group ) into and that homomorphisms of representations are just natural transformations.)

To see an example of this definition in action, we give the following as an exercise.

Proposition 1 Let . We define the -invariant space to be

Then there is a natural bijection of vector spaces .

Proof: Let . The set consists of maps with

for every . Since is linear, it is uniquely defined by (since in general). So , i.e. , is necessary and sufficient. Thus the bijection is just .

This proposition will come up again at the end of Part 4.

3. Subrepresentations, Irreducibles, and Maschke’s Theorem

Now suppose I’ve got a representation .

Definition Suppose we have a subspace which is -invariant, meaning that for every and . Then we can construct a representation of on by restricting the action to :

In that case the resulting is called a subrepresentation of .

Every has an obvious subrepresentation, namely itself, as well as a stupid subrepresenation on the zero-dimensional vector space . But it’s the case that some representations have interesting subrepresentations.

Example Consider the representation of on defined in the first section. For all , is not irreducible.

Proof: Consider the subspace given by

then is invariant under , so we have a subrepresentation of , which we’ll denote .

This motivates the ideas of irreducibles.

Definition A representation is irreducible if it has no nontrivial subrepresentations.

Of course the first thing we ask is whether any representation decomposes as a product of irreducible representations. But what does it mean to compose two representations, anyways? It’s just the “natural” definition with the direct sum.

Definition Let and be representations and suppose we have . Then we define the representation by where

Just like every integer decomposes into prime factors, we hope that every representation decomposes into irreducibles. But this is too much to hope for.

Example Let , let be the finite field of order (aka ), and consider , which is not irreducible. However, we claim that we cannot write for any nontrivial and .

Proof: This is a good concrete exercise.

Assume not, and let and be the underlying vector spaces of and . By nontriviality, , and in particular we have that as sets, . Take the only nonzero elements and . Since is invariant under , , so . Similarly, , which is impossible.

So we hoped for perhaps too much. However, with seemingly trivial modifications we can make the above example work.

Example In the same example as above, suppose we replace with any field which does not have characteristic . Then does decompose.

Proof: Consider the following two subspaces of :

It’s easy to see that both and are both invariant under . Moreover, if then we in fact have

because for any . So if we let be the subrepresentation corresponding to , and define on similarly, then we have .

Thus the only thing in the way of the counterexample was the fact that . And it turns out in general this is the only obstacle, a result called Maschke’s Theorem.

Theorem 2 (Maschke’s Theorem) Suppose that is a finite group, and does not divide . Then every finite-dimensional representation decomposes as a direct sum of irreducibles.

Before proceeding to the proof, I’ll draw an analogy between the proof that every positive integer decomposes as the product of primes. We use by strong induction on ; if is prime we are done, and if is composite there is a nontrivial divisor , so we apply the inductive hypothesis to and and combine these factorizations. We want to mimic the proof above in our proof of Maschke’s Theorem, but we have a new obstacle: we have to show that somehow, we can “divide”.

So why is it that we can divide in certain situations? The idea is that we want to be able to look at an “average” of the form

because this average has the nice property of being -invariant. We’ll use this to obtain our proof of Maschke’s Theorem.

Proof: We proceed by induction on the dimension of the representation . Let be a representation and assume its not irreducible, so it has a nontrivial subspace which is -invariant. It suffices to prove that there exists a subspace such that is also -invariant and , because then we can apply the inductive hypothesis to the subrepresentations induced by and .

Let be any projection of onto . We consider the averaging map by

We’ll use the following properties of the map.

Exercise Show that the map has the following three properties.

• For any , .
• For any , .
• .

As with any projection map , we must have . But . Moreover, because the map is -invariant, it follows that is -invariant. Hence taking completes the proof.

This completes our proof of Maschke’s Theorem, telling us how all irreducibles decompose. Said another way, Maschke’s Theorem tells us that any finite-dimensional representation can be decomposed as

where is some nonnegative integer, and is the set of all (isomorphism classes of) irreducibles representations.

You may wonder whether the decomposition is unique, and if so what we can say about the “exponents” . In the next post I’ll show how to compute the exponents (which in particular gives uniqueness).

Thanks to Dennis Gaitsgory, who taught me this in his course Math 55a. Thanks also to the MOPpers at PUMaC 2014 who let me run this by them during a sleepover; several improvements were made to the original draft as a result. My notes for Math 55a can be found at my website. Thanks also to N for pointing out an error in my proof of Maschke’s Theorem.