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 {k} are all of the form {k^{\oplus n}},
  • 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: {R = \mathbb Z}.

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

Definition 1

If {R} is a UFD, then {p \in R} is a prime element if {(p)} is a prime ideal and {p \neq 0}. For UFD’s this is equivalent to the following property: if {p = xy} then either {x} or {y} is a unit.

So for example in {\mathbb Z} the set of prime elements is {\{\pm2, \pm3, \pm5, \dots\}}. Now, since {R} is a UFD, every element {r} factors into a product of prime elements

\displaystyle  r = u p_1^{e_1} p_2^{e_2} \dots p_m^{e_m}

Definition 2

We say {r} divides {s} if {s = r'r} for some {r' \in R}. This is written {r \mid s}.

Example 3 (Divisibility in {\mathbb Z})

The number {0} is divisible by every element of {\mathbb Z}. All other divisibility as expected.

Ques 4

Show that {r \mid s} if and only if the exponent of each prime in {r} is less than or equal to the corresponding exponent in {s}.

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

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

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

Proof: The fact that {R} is Noetherian is obvious. For {R} to be a UFD we essentially repeat the proof for {\mathbb Z}, using the fact that {(a,b)} is principal in order to extract {\gcd(a,b)}. \Box

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

Theorem 6 (Chinese remainder theorem for rings)

Let {m} and {n} be relatively prime elements, meaning {(m) + (n) = (1)}. Then

\displaystyle  R / (mn) \cong R/m \times R/n.

Proof: This is the same as the proof of the usual Chinese remainder theorem. First, since {(m,n)=(1)} we have {am+bn=1} for some {a} and {b}. Then we have a map

\displaystyle  R/m \times R/n \rightarrow R/(mn) \quad\text{by}\quad (r,s) \mapsto r \cdot bn + s \cdot am.

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

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

Definition 7

An {R}-module {M} 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 {M_1 \subsetneq M_2 \subsetneq \dots}.
  • All submodules of {M} (including {M} itself) are finitely generated.

This generalizes the notion of a Noetherian ring: a Noetherian ring {R} is one for which {R} is Noetherian as an {R}-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 {R} be a PID and let {M} be any finitely generated {R}-module. Then

\displaystyle  M \cong \bigoplus_{i=1}^m R/s_i

for some {s_i} satisfying {s_1 \mid s_2 \mid \dots \mid s_m}.

Corollary 10 (Structure theorem, primary form)

Let {R} be a PID and let {M} be any finitely generated {R}-module. Then

\displaystyle  M \cong R^{\oplus r} \oplus R/(q_1) \oplus R/(q_2) \oplus \dots \oplus R/(q_m)

where {q_i = p_i^{e_i}} for some prime element {p_i} and integer {e_i \ge 1}.

Proof: Factor each {s_i} into prime factors (since {R} is a UFD), then use the Chinese remainder theorem. \Box

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 {R}-modules

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

Suppose {M} is finitely generated by {d} elements. Then there is a surjective map of {R}-modules

\displaystyle  R^{\oplus d} \twoheadrightarrow M

whose image on the basis of {R^{\oplus d}} are the generators of {M}. Let {K} denote the kernel.

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

Lemma 12 (Direct sum of Noetherian modules is Noetherian)

Let {M} and {N} be two Noetherian {R}-modules. Then the direct sum {M \oplus N} is also a Noetherian {R}-module.

Proof: It suffices to show that if {L \subseteq M \oplus N}, then {L} is finitely generated. It’s unfortunately not true that {L = P \oplus Q} (take {M = N = \mathbb Z} {L = \{(n,n) \mid n \in \mathbb Z\}}) so we will have to be more careful.

Consider the submodules

\displaystyle  \begin{aligned} A &= \left\{ x \in M \mid (x,0) \in L \right\} \subseteq M \\ B &= \left\{ y \in N \mid \exists x \in M : (x,y) \in L \right\} \subseteq N. \end{aligned}

(Note the asymmetry for {A} and {B}: the proof doesn’t work otherwise.) Then {A} is finitely generated by {a_1}, \dots, {a_k}, and {B} is finitely generated by {b_1}, \dots, {b_\ell}. Let {x_i = (a_i, 0)} and let {y_i = (\ast, b_i)} be elements of {L} (where the {\ast}‘s are arbitrary things we don’t care about). Then {x_i} and {y_i} together generate {L}. \Box

Ques 13

Deduce that for {R} a PID, {R^{\oplus d}} is Noetherian.

Hence {K \subseteq R^{\oplus d}} is finitely generated as claimed. So we can find another surjective map {R^{\oplus f} \twoheadrightarrow K}. Consequently, we have a composition

\displaystyle  R^{\oplus f} \twoheadrightarrow K \hookrightarrow R^{\oplus d} \twoheadrightarrow M.

Observe that {M} is the cokernel of the composition {T : R^{\oplus f} \rightarrow R^{\oplus d}}, i.e. we have that

\displaystyle  M \cong R^{\oplus d} / \text{im }(T).

So it suffices to understand the map {T} well.

4. Smith normal form

The idea is now that we have reduced our problem to studying linear maps {T : R^{\oplus m} \rightarrow R^{\oplus n}}, which can be thought of as a generic matrix

\displaystyle  T = \begin{pmatrix} a_{11} & \dots & a_{1m} \\ \vdots & \ddots & \vdots \\ a_{n1} & \dots & a_{nm} \end{pmatrix}

for the standard basis {e_1}, \dots, {e_m} of {R^{\oplus m}} and {f_1}, \dots, {f_n} of {N}.

Of course, as you might expect it ought to be possible to change the given basis of {T} such that {T} has a nicer matrix form. We already saw this in Jordan form, where we had a map {T : V \rightarrow V} and changed the basis so that {T} 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 {3} times the first column to the second column, this is equivalent to replacing the basis

    \displaystyle  (e_1, e_2, e_3, \dots, e_m) \mapsto (e_1, e_2+3e_1, e_3, \dots, e_m).

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

    \displaystyle  (f_1, f_2, f_3, \dots, f_n) \mapsto (f_1-3f_2, f_2, f_3, \dots, f_n).

More generally, If {A} is an invertible {n \times n} matrix we can replace {T} with {AT}. This corresponds to replacing

\displaystyle  (f_1, \dots, f_n) \mapsto (A(f_1), \dots, A(f_n))

(the “invertible” condition just guarantees the latter is a basis). Of course similarly we can replace {X} with {XB} where {B} is an invertible {m \times m} matrix; this corresponds to

\displaystyle  (e_1, \dots, e_m) \mapsto (B^{-1}(e_1), \dots, B^{-1}(e_m))

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

Theorem 14 (Smith normal form)

Let {R} be a PID. Let {M = R^{\oplus m}} and {N = R^{\oplus n}} be free {R}-modules and let {T : M \rightarrow N} be a linear map. Set {k = \min(m,n)}.

Then we can select a pair of new bases for {M} and {N} such that {T} has only diagonal entries {s_1}, {s_2}, \dots, {s_k} and {s_1 \mid s_2 \mid \dots \mid s_k}.

So if {m > n}, the matrix should take the form

\displaystyle  \begin{pmatrix} s_1 & 0 & 0 & 0 & \dots & 0 \\ 0 & s_2 & 0 & 0 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots & \dots & \vdots \\ 0 & 0 & 0 & s_n & \dots & 0 \end{pmatrix}.

and similarly when {m \le n}.

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 {T : V \rightarrow V}; note that the source and target space are the same, and we are considering one basis for the space {V}.
  • In Smith form the maps {T : M \rightarrow N} are between different modules, and we pick two sets of bases (one for {M} and one for {N}).

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 {\mathbb Z}:

\displaystyle  \begin{pmatrix} 18 & 38 & 48 \\ 14 & 30 & 38 \end{pmatrix}.

The GCD of all the entries is {2}, 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:

\displaystyle  \begin{pmatrix} 18 & 38 & 48 \\ 14 & 30 & 38 \end{pmatrix} \mapsto \begin{pmatrix} 4 & 8 & 10 \\ 14 & 30 & 38 \end{pmatrix} \mapsto \begin{pmatrix} 4 & 8 & 10 \\ 2 & 6 & 2 \end{pmatrix}.

Now that the GCD of {2} 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 {2} was the GCD all along, we isolate {2} completely:

\displaystyle  \begin{pmatrix} 4 & 8 & 10 \\ 2 & 6 & 2 \end{pmatrix} \mapsto \begin{pmatrix} 2 & 6 & 2 \\ 4 & 8 & 10 \end{pmatrix} \mapsto \begin{pmatrix} 2 & 6 & 2 \\ 0 & -4 & 6 \\ \end{pmatrix} \mapsto \begin{pmatrix} 2 & 0 & 0 \\ 0 & -4 & 6 \end{pmatrix}.

This reduces the problem to a {1 \times 2} matrix. So we just apply the Euclidean algorithm again there:

\displaystyle  \begin{pmatrix} 2 & 0 & 0 \\ 0 & -4 & 6 \end{pmatrix} \mapsto \begin{pmatrix} 2 & 0 & 0 \\ 0 & -4 & 2 \end{pmatrix} \mapsto \begin{pmatrix} 2 & 0 & 0 \\ 0 & 0 & 2 \end{pmatrix} \mapsto \begin{pmatrix} 2 & 0 & 0 \\ 0 & 2 & 0 \end{pmatrix}.

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

\displaystyle  T = \begin{pmatrix} a_{11} & \dots & a_{1m} \\ \vdots & \ddots & \vdots \\ a_{n1} & \dots & a_{nm} \end{pmatrix}

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 {\gcd(x,y)} to be any generator of the principal ideal {(x,y)}.

Claim 18 (“Euclidean algorithm”)

If {a} and {b} are entries in the same row or column, we can change bases to replace {a} with {\gcd(a,b)} and {b} with something else.

Proof: We do just the case of columns. By hypothesis, {\gcd(a,b) = xa+yb} for some {x,y \in R}. We must have {(x,y) = (1)} now (we’re in a UFD). So there are {u} and {v} such that {xu + yv = 1}. Then

\displaystyle  \begin{pmatrix} x & y \\ -v & u \end{pmatrix} \begin{pmatrix} a \\ b \end{pmatrix} = \begin{pmatrix} \gcd(a,b) \\ \text{something} \end{pmatrix}

and the first matrix is invertible (check this!), as desired. \Box
Let {s_1 = (a_{ij})_{i,j}} be the GCD of all entries. Now by repeatedly applying this algorithm, we can cause {s} 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

\displaystyle  \begin{pmatrix} s_1 & 0 & 0 & \dots & 0 \\ 0 & a_{22}' & a_{23}' & \dots & a_{2n}' \\ 0 & a_{32}' & a_{33}' & \dots & a_{3n}' \\ \vdots&\vdots&\vdots&\ddots&\vdots \\ 0 & a_{m2}' & a_{m3}' & \dots & a_{mn}' \\ \end{pmatrix}.

Now we repeat the same procedure with this lower-right {(m-1) \times (n-1)} matrix, and so on. This gives the Smith normal form. \Box

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

\displaystyle  M \cong R^{\oplus d} / \text{im } T

and applying the theorem to {T} 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 {V} over a field {k} has a finite spanning set of vectors. Then for some {n}, {V \cong k^{\oplus n}}.

Proof: In the structure theorem, {k / (s_i) \in \{0,k\}}. \Box

Corollary 20 (Frobenius normal form)

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

\displaystyle  \begin{pmatrix} 0 & 0 & 0 & \dots & 0 & \ast \\ 1 & 0 & 0 & \dots & 0 & \ast \\ 0 & 1 & 0 & \dots & 0 & \ast \\ \vdots&\vdots&\vdots&\ddots&\vdots&\vdots \\ 0 & 0 & 0 & \dots & 1 & \ast \\ \end{pmatrix}.

Proof: View {V} as a {k[x]}-module with action {x \cdot v = T(v)}. By theorem {V \cong \bigoplus_i k[x] / (s_i)} for some polynomials {s_i}, where {s_1 \mid s_2 \mid s_3 \mid \dots}. Write each block in the form described. \Box

Corollary 21 (Jordan normal form)

Let {T : V \rightarrow V} where {V} is a finite-dimensional vector space over an arbitrary field {k} which is algebraically closed. Prove that {T} can be written in Jordan form.

Proof: We now use the structure theorem in its primary form. Since {k[x]} is algebraically closed each {p_i} is a linear factor, so every summand looks like {k[x] / (x-a)^m} for some {m}. \Box

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 {L}-series for non-abelian extensions. But for them to agree with the {L}-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 {K} be a number field. Then all abelian extensions {L/K} can be understood using solely information intrinsic to {K}: namely, the ray class groups (generalizing ideal class groups).

1. Infinite primes

Let {K} be a number field of degree {n}. We know what a prime ideal of {\mathcal O_K} is, but we now allow for the so-called infinite primes, which I’ll describe using embeddings. We know there are {n} embeddings {\sigma : K \rightarrow \mathbb C}, which consist of

  • {r} real embeddings where {\mathop{\mathrm{im}}\sigma \subseteq \mathbb R}, and
  • {s} pairs of conjugate complex embeddings.

Hence {r+2s = n}. The first class of embeddings form the real infinite primes, while the complex infinite primes are the second type. We say {K} is totally real (resp totally complex) if all its infinite primes are real (resp complex).

Example 1 (Examples of infinite primes)

  • {\mathbb Q} has a single real infinite prime. We often write it as {\infty}.
  • {\mathbb Q(\sqrt{-5})} has a single complex infinite prime, and no real infinite primes. Hence totally complex.
  • {\mathbb Q(\sqrt{5})} 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

\displaystyle \mathfrak m = \prod_{\mathfrak p} \mathfrak p^{\nu(\mathfrak p)}

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

  • {\nu(\mathfrak p) = 0} for any infinite prime {\mathfrak p}, and
  • {\nu(\mathfrak p) \le 1} for any real prime {\mathfrak p}.

Obviously, every {\mathfrak m} can be written as {\mathfrak m = \mathfrak m_0\mathfrak m_\infty} by separating the finite from the (real) infinite primes.

We say {a \equiv b \pmod{\mathfrak m}} if

  • If {\mathfrak p} is a finite prime, then {a \equiv b \pmod{\mathfrak p^{\nu(\mathfrak p)}}} means exactly what you think it should mean: {a-b \in \mathfrak p^{\nu(\mathfrak p)}}.
  • If {\mathfrak p} is a real infinite prime {\sigma : K \rightarrow \mathbb R}, then {a \equiv b \pmod{\mathfrak p}} means that {\sigma(a/b) > 0}.

Of course, {a \equiv b \pmod{\mathfrak m}} means {a \equiv b} modulo each prime power in {\mathfrak m}. With this, we can define a generalization of the class group:

Definition 2

Let {\mathfrak m} be a modulus of a number field {K}.

  • Let {I_K(\mathfrak m)} to be the set of all fractional ideals of {K} which are relatively prime to {\mathfrak m}, which is an abelian group.
  • Let {P_K(\mathfrak m)} be the subgroup of {I_K(\mathfrak m)} generated by

    \displaystyle \left\{ \alpha \mathcal O_K \mid \alpha \in K^\times \text{ and } \alpha \equiv 1 \pmod{\mathfrak m} \right\}.

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

Finally define the ray class group of {\mathfrak m} to be {C_K(\mathfrak m) = I_K(\mathfrak m) / P_K(\mathfrak m)}.

This group is known to always be finite. Note the usual class group is {C_K(1)}.

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

Definition 3

A congruence subgroup of {\mathfrak m} is a subgroup {H} with

\displaystyle P_K(\mathfrak m) \subseteq H \subseteq I_K(\mathfrak m).

Thus {C_K(\mathfrak m)} is a group which contains a lattice of various quotients {I_K(\mathfrak m) / H}, where {H} is a congruence subgroup.

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

Example 4 (Ray class groups in {\mathbb Q})

Consider {K = \mathbb Q} with infinite prime {\infty}. Then

  • If we take {\mathfrak m = 1} then {I_\mathbb Q(1)} is all fractional ideals, and {P_\mathbb Q(1)} is all principal fractional ideals. Their quotient is the usual class group of {\mathbb Q}, which is trivial.


  • Now take {\mathfrak m = 8}. Thus {I_\mathbb Q(8) \cong \left\{ \frac ab\mathbb Z \mid a/b \equiv 1,3,5,7 \pmod 8 \right\}}. Moreover

    \displaystyle P_\mathbb Q(8) \cong \left\{ \frac ab\mathbb Z \mid a/b \equiv 1 \pmod 8 \right\}.

    You might at first glance think that the quotient is thus {(\mathbb Z/8\mathbb Z)^\times}. But the issue is that we are dealing with ideals: specifically, we have

    \displaystyle 7\mathbb Z = -7\mathbb Z \in P_\mathbb Q(8)

    because {-7 \equiv 1 \pmod 8}. So actually, we get

    \displaystyle C_\mathbb Q(8) \cong \left\{ 1,3,5,7 \text{ mod } 8 \right\} / \left\{ 1,7 \text{ mod } 8 \right\} \cong (\mathbb Z/4\mathbb Z)^\times.


  • Now take {\mathfrak m = \infty}. As before {I_\mathbb Q(\infty) = \mathbb Q^\times}. Now, by definition we have

    \displaystyle P_\mathbb Q(\infty) = \left\{ \frac ab \mathbb Z \mid a/b > 0 \right\}.

    At first glance you might think this was {\mathbb Q_{>0}}, but the same behavior with ideals shows in fact {P_\mathbb Q(\infty) = \mathbb Q^\times}. So in this case, {P_\mathbb Q(\infty)} still has all principal fractional ideals. Therefore, {C_\mathbb Q(\infty)} is still trivial.


  • Finally, let {\mathfrak m = 8\infty}. As before {I_\mathbb Q(8\infty) \cong \left\{ \frac ab\mathbb Z \mid a/b \equiv 1,3,5,7 \pmod 8 \right\}}. Now in this case:

    \displaystyle P_\mathbb Q(8\infty) \cong \left\{ \frac ab\mathbb Z \mid a/b \equiv 1 \pmod 8 \text{ and } a/b > 0 \right\}.

    This time, we really do have {-7\mathbb Z \notin P_\mathbb Q(8\infty)}: we have {7 \not\equiv 1 \pmod 8} and also {-8 < 0}. So neither of the generators of {7\mathbb Z} are in {P_\mathbb Q(8\infty)}. Thus we finally obtain

    \displaystyle C_\mathbb Q(8\infty) \cong \left\{ 1,3,5,7 \text{ mod } 8 \right\} / \left\{ 1 \text{ mod } 8 \right\} \cong (\mathbb Z/8\mathbb Z)^\times

    with the bijection {C_\mathbb Q(8\infty) \rightarrow (\mathbb Z/8\mathbb Z)^\times} given by {a\mathbb Z \mapsto |a| \pmod 8}.

    Generalizing these examples, we see that

    \displaystyle \begin{aligned} C_\mathbb Q(m) &= (\mathbb Z/m\mathbb Z)^\times / \{\pm1\} \\ C_\mathbb Q(m\infty) &= (\mathbb Z/m\mathbb Z)^\times. \end{aligned}


3. Infinite primes in extensions

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

Now take a Galois extension {L/K} of degree {m}. We already know prime ideals {\mathfrak p} of {K} break into a produt of prime ideals {\mathfrak P} of {K} in {L} in a nice way, so we want to do the same thing with infinite primes. This is straightforward: each of the {n} infinite primes {\sigma : K \rightarrow \mathbb C} lifts to {m} infinite primes {\tau : L \rightarrow \mathbb C}, by which I mean the diagram

ramify-inf-primecommutes. Hence like before, each infinite prime {\sigma} of {K} has {m} infinite primes {\tau} of {L} which lie above it.

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

Example 5 (Ramification of {\infty})

Let {\infty} be the real infinite prime of {\mathbb Q}.

  • {\infty} is ramified in {\mathbb Q(\sqrt{-5})/\mathbb Q}.
  • {\infty} is unramified in {\mathbb Q(\sqrt{5})/\mathbb Q}.

Note also that if {K} is totally complex then any extension {L/K} is unramified.

4. Frobenius element and Artin symbol

Recall the following key result:

Theorem 6 (Frobenius element)

Let {L/K} be a Galois extension. If {\mathfrak p} is a prime unramified in {K}, and {\mathfrak P} a prime above it in {L}. Then there is a unique element of {\mathop{\mathrm{Gal}}(L/K)}, denoted {\mathrm{Frob}_\mathfrak P}, obeying

\displaystyle \mathrm{Frob}_\mathfrak P(\alpha) \equiv \alpha^{N\mathfrak p} \pmod{\mathfrak P} \qquad \forall \alpha \in \mathcal O_L.

Example 7 (Example of Frobenius elements)

Let {L = \mathbb Q(i)}, {K = \mathbb Q}. We have {\mathop{\mathrm{Gal}}(L/K) \cong \mathbb Z/2\mathbb Z}.

If {p} is an odd prime with {\mathfrak P} above it, then {\mathrm{Frob}_\mathfrak P} is the unique element such that

\displaystyle (a+bi)^p \equiv \mathrm{Frob}_\mathfrak P(a+bi) \pmod{\mathfrak P}

in {\mathbb Z[i]}. In particular,

\displaystyle \mathrm{Frob}_\mathfrak P(i) = i^p = \begin{cases} i & p \equiv 1 \pmod 4 \\ -i & p \equiv 3 \pmod 4. \end{cases}

From this we see that {\mathrm{Frob}_\mathfrak P} is the identity when {p \equiv 1 \pmod 4} and {\mathrm{Frob}_\mathfrak P} is complex conjugation when {p \equiv 3 \pmod 4}.

Example 8 (Cyclotomic Frobenius element)

Generalizing previous example, let {L = \mathbb Q(\zeta)} and {K = \mathbb Q}, with {\zeta} an {m}th root of unity. It’s well-known that {L/K} is unramified outside {\infty} and prime factors of {m}. Moreover, the Galois group {\mathop{\mathrm{Gal}}(L/K)} is {(\mathbb Z/m\mathbb Z)^\times}: the Galois group consists of elements of the form

\displaystyle \sigma_n : \zeta \mapsto \zeta^n

and {\mathop{\mathrm{Gal}}(L/K) = \left\{ \sigma_n \mid n \in (\mathbb Z/m\mathbb Z)^\times \right\}}.

Then it follows just like before that if {p \nmid n} is prime and {\mathfrak P} is above {p}

\displaystyle \mathrm{Frob}_\mathfrak P(x) = \sigma_p.

An important property of the Frobenius element is its order is related to the decomposition of {\mathfrak p} in the higher field {L} in the nicest way possible:

Lemma 9 (Order of the Frobenius element)

The Frobenius element {\mathrm{Frob}_\mathfrak P \in \mathop{\mathrm{Gal}}(L/K)} of an extension {L/K} has order equal to the inertial degree of {\mathfrak P}, that is,

\displaystyle \mathop{\mathrm{ord}} \mathrm{Frob}_\mathfrak P = f(\mathfrak P \mid \mathfrak p).

In particular, {\mathrm{Frob}_\mathfrak P = \mathrm{id}} if and only if {\mathfrak p} splits completely in {L/K}.

Proof: We want to understand the order of the map {T : x \mapsto x^{N\mathfrak p}} on the field {\mathcal O_K / \mathfrak P}. But the latter is isomorphic to the splitting field of {X^{N\mathfrak P} - X} in {\mathbb F_p}, by Galois theory of finite fields. Hence the order is {\log_{N\mathfrak p} (N\mathfrak P) = f(\mathfrak P \mid \mathfrak p)}. \Box

Exercise 10

Deduce from this that the rational primes which split completely in {\mathbb Q(\zeta)} are exactly those with {p \equiv 1 \pmod m}. Here {\zeta} is an {m}th root of unity.

The Galois group acts transitively among the set of {\mathfrak P} above a given {\mathfrak p}, so that we have

\displaystyle \mathrm{Frob}_{\sigma(\mathfrak P)} = \sigma \circ (\mathrm{Frob}_{\mathfrak p}) \circ \sigma^{-1}.

Thus {\mathrm{Frob}_\mathfrak P} is determined by its underlying {\mathfrak p} up to conjugation.

In class field theory, we are interested in abelian extensions, (which just means that {\mathop{\mathrm{Gal}}(L/K)} is Galois) in which case the theory becomes extra nice: the conjugacy classes have size one.

Definition 11

Assume {L/K} is an abelian extension. Then for a given unramified prime {\mathfrak p} in {K}, the element {\mathrm{Frob}_\mathfrak P} doesn’t depend on the choice of {\mathfrak P}. We denote the resulting {\mathrm{Frob}_\mathfrak P} by the Artin symbol.

\displaystyle \left( \frac{L/K}{\mathfrak p} \right).

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 {(2/p) \equiv 2^{\frac{p-1}{2}}} where {p > 2} is prime. Consider the element

\displaystyle \left( \frac{\mathbb Q(\sqrt 2)/\mathbb Q}{p\mathbb Z} \right) \in \mathop{\mathrm{Gal}}(\mathbb Q(\sqrt 2) / \mathbb Q).

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

\displaystyle \left( \frac{\mathbb Q(\sqrt 2)/\mathbb Q}{p\mathbb Z} \right) \left( \sqrt 2 \right) \equiv \left( \sqrt 2 \right)^{p} \equiv 2^{\frac{p-1}{2}} \cdot \sqrt 2 \equiv \left( \frac 2p \right) \sqrt 2 \pmod{\mathfrak P}

where {\left( \frac 2p \right)} is the usual Legendre symbol, and {\mathfrak P} is above {p} in {\mathbb Q(\sqrt 2)}. 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 {\theta} is primary in {K = \mathbb Q(\sqrt{-3}) = \mathbb Q(\omega)} (thus {\mathcal O_K = \mathbb Z[\omega]} is Eisenstein integers). Then for example

\displaystyle \left( \frac{K(\sqrt[3]{2})/K}{\theta \mathcal O_K} \right) \left( \sqrt[3]{2} \right) \equiv \left( \sqrt[3]{2} \right)^{N(\theta)} \equiv 2^{\frac{N\theta-1}{3}} \cdot \sqrt 2 \equiv \left( \frac{2}{\theta} \right)_3 \sqrt[3]{2}. \pmod{\mathfrak P}

where {\mathfrak P} is above {p} in {K(\sqrt[3]{2})}.

5. Artin reciprocity

Now, we further capitalize on the fact that {\mathop{\mathrm{Gal}}(L/K)} is abelian. For brevity, in what follows let {\mathop{\mathrm{Ram}}(L/K)} denote the primes of {K} (either finite or infinite) which ramify in {L}.

Definition 14

Let {L/K} be an abelian extension and let {\mathfrak m} be divisible by every prime in {\mathop{\mathrm{Ram}}(L/K)}. Then since {L/K} is abelian we can extend the Artin symbol multiplicatively to a map

\displaystyle \left( \frac{L/K}{\bullet} \right) : I_K(\mathfrak m) \twoheadrightarrow \mathop{\mathrm{Gal}}(L/K).

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 {H_{L/K}(\mathfrak m) \subseteq I_K(\mathfrak m)}. Thus we have

\displaystyle \mathop{\mathrm{Gal}}(L/K) \cong I_K(\mathfrak m) / H(\mathfrak m).

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

Theorem 15 (Artin reciprocity)

Let {L/K} be an abelian extension. Then there is a modulus {\mathfrak f = \mathfrak f(L/K)}, divisible by exactly the primes of {\mathop{\mathrm{Ram}}(L/K)}, with the following property: if {\mathfrak m} is divisible by all primes of {\mathop{\mathrm{Ram}}(L/K)}

\displaystyle P_K(\mathfrak m) \subseteq H_{L/K}(\mathfrak m) \subseteq I_K(\mathfrak m) \quad\text{if and only if}\quad \mathfrak f \mid \mathfrak m

We call {\mathfrak f} the conductor of {L/K}.

So the conductor {\mathfrak f} plays a similar role to the discriminant (divisible by exactly the primes which ramify), and when {\mathfrak m} is divisible by the conductor, {H(L/K, \mathfrak m)} is a congruence subgroup.

Note that for example, if we pick {L} such that {H(L/K, \mathfrak m) \cong P_K(\mathfrak m)} then Artin reciprocity means that there is an isomorphism

\displaystyle \mathop{\mathrm{Gal}}(L/K) \cong I_K(\mathfrak m) / P_K(\mathfrak m) \cong C_K(\mathfrak m).

More generally, we see that {\mathop{\mathrm{Gal}}(L/K)} is always a subgroup some subgroup {C_K(\mathfrak f)}.

Example 16 (Cyclotomic field)

Let {\zeta} be a primitive {m}th root of unity. We show in this example that

\displaystyle H_{\mathbb Q(\zeta) / \mathbb Q} (m\infty) = P_\mathbb Q(m\infty) = \left\{ \frac ab \mathbb Z \mid a/b \equiv 1 \pmod m \right\}.

This is the generic example of achieving the lower bound in Artin reciprocity. It also implies that {\mathfrak f(\mathbb Q(\zeta)/\mathbb Q) \mid m\infty}.

It’s well-known {\mathbb Q(\zeta)/\mathbb Q} is unramified outside finite primes dividing {m}, so that the Artin symbol is defined on {I_K(\mathfrak m)}. Now the Artin map is given by

cyclo-mapSo we see that the kernel of this map is trivial, i.e.\ it is given by the identity of the Galois group, corresponding to 1 \pmod{m} Then {H = H_{L/K}(\mathfrak m)} for a unique abelian extension {L/K}.

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

Lemma 17 (Inclusion-reversing congruence subgroups)

Fix a modulus {\mathfrak m}. Let {L/K} and {M/K} be abelian extensions and suppose {\mathfrak m} is divisible by the conductors of {L/K} and {M/K}. Then

\displaystyle L \subseteq M \quad\text{if and only if}\quad H_{M/K}(\mathfrak m) \subseteq H_{L/K}(\mathfrak m)

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

inclusion-diagramcommutes, 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. \Box
Note that we can always take {\mathfrak m} 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 {L} be an abelian extension of {\mathbb Q}. Then {L} is contained in a cyclic extension {\mathbb Q(\zeta)} where {\zeta} is an {m}th root of unity (for some {m}).

Proof: Suppose {\mathfrak f(L/\mathbb Q) \mid m\infty} for some {m}. Then by the example from earlier we have the chain

\displaystyle P_{\mathbb Q}(m\infty) = H(\mathbb Q(\zeta)/\mathbb Q, m\infty) \subseteq H(L/\mathbb Q, m) \subseteq I_\mathbb Q(m\infty).

So by inclusion reversal we’re done. \Box

Corollary 19 (Hilbert class field)

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

  • {E/K} is the maximal such extension by inclusion.
  • {\mathop{\mathrm{Gal}}(E/K)} is isomorphic to the class group of {E}.
  • A prime {\mathfrak p} of {K} splits completely in {E} if and only if it is principal.

We call {E} the Hilbert class field of {K}.

Proof: Apply the Takagi existence theorem with {\mathfrak m = 1} to obtain an unramified extension {E/K} such that {H(E/K, 1) = P_K(1)}. We claim this works:

  • To see it is maximal by inclusion, note that any other extension {M/K} with this property has conductor {1} (no primes divide the conductor), and then we have {P_K(1) = H(E/K, 1) \subseteq H(M/K, 1) \subseteq I_K(1)}, so inclusion reversal gives {M \subseteq E}.
  • We have {\mathop{\mathrm{Gal}}(L/K) \cong I_K(1) / P_K(1) = C_K(1)} the class group.
  • The isomorphism in the previous part is given by the Artin symbol. So {\mathfrak p} splits completely if and only if {\left( \frac{L/K}{\mathfrak p} \right) = \mathrm{id}} if and only if {\mathfrak p} is principal (trivial in {C_K(1)}).

This completes the proof. \Box

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 {k} and let {G} be a finite group. In this post we will show that one can reconstruct the group {G} from the monoidal category of {k[G]}-modules (i.e. its {G}-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 {k}-algebra is a {k}-vector space {A} equipped with a map {m : A \otimes A \rightarrow A} and {i : k \hookrightarrow A} (unit), satisfying some certain axioms.

Then a {k}-coalgebra is a map

\displaystyle \Delta : A \rightarrow A \otimes A \qquad \varepsilon : A \rightarrow k

called comultiplication and counit respectively, which satisfy the dual axioms. See \url{}.

Now a Hopf algebra {A} is a bialgebra {A} over {k} plus a so-called antipode {S : A \rightarrow A}. We require that the diagram



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

\displaystyle G = \left\{ x \in A \mid \Delta(x) = x \otimes x \right\}.

Exercise 1

Show that {G} is a group with multiplication {m} and inversion {S}.

Now the example

Example 2 (Group algebra is Hopf algebra)

The group algebra {k[G]} is a Hopf algebra with

  • {m}, {i} as expected.
  • {\varepsilon} the counit is the trivial representation.
  • {\Delta} comes form {g \mapsto g \otimes g} extended linearly.
  • {S} takes {g \mapsto g^{-1}} extended linearly.


Theorem 3

The group-like elements are precisely the basis elements {1_k \cdot g \in k[g]}.


Proof: Assume {V = \sum_{g \in G} a_g g} is grouplike. Then by assumption we should have

\displaystyle \sum_{g \in G} a_g (g \otimes g) = \Delta(v) = \sum_{g \in G} \sum_{h \in G} a_ga_h (g \otimes h).

Comparing each coefficient, we get that

\displaystyle a_ga_h = \begin{cases} a_g & g = h \\ 0 & \text{otherwise}. \end{cases}

This can only occur if some {a_g} is {1} and the remaining coefficients are all zero. \Box


2. Monoidal functors

Recall that monoidal category (or tensor category) is a category {\mathscr C} equipped with a functor {\otimes : \mathscr C \times \mathscr C \rightarrow \mathscr C} which has an identity {I} and satisfies some certain coherence conditions. For example, for any {A,B,C \in \mathscr C} we should have a natural isomorphism

\displaystyle A \otimes (B \otimes C) \xrightarrow{a_{A,B,C}} (A \otimes B) \otimes C.

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

Now take two monoidal categories {(\mathscr C, \otimes_\mathscr C)} and {(\mathscr D, \otimes_\mathscr D)}. Then a monoidal functor {F : \mathscr C \rightarrow \mathscr D} is a functor for which we additionally need to select an isomorphism

\displaystyle F(A \otimes B) \xrightarrow{t_{A,B}} F(A) \otimes F(B).

We then require that the diagram


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

We also have a notion of a natural transformation of two functors {t : F \rightarrow G}; this is just making the squares


commute. Now, suppose {F : \mathscr C \rightarrow \mathscr C} is a monoidal functor. Then an automorphism of {F} is a natural transformation {t : F \rightarrow F} which is invertible, i.e. a natural isomorphism.

3. Application to {k[G]}

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

Let {U} be the forgetful functor

\displaystyle U : \mathsf{Mod}_{k[G]} \rightarrow \mathsf{Vect}_k.

It’s easy to see this is in fact an monoidal functor. Now let {\text{Aut }^{\otimes}(U)} be the set of monoidal automorphisms of {U}.

The key claim is the following:

Theorem 4 ({G} is isomorphic to {\text{Aut }^\otimes(U)})

Consider the map

\displaystyle i : G \rightarrow \text{Aut }^\otimes(U) \quad\text{by}\quad g \mapsto T^g.

Here, the natural transformation {T^g} is defined by the components

\displaystyle T^g_{(V,\phi)} : (V, \phi) \rightarrow U(V, \phi) = V \quad\text{by}\quad v \mapsto \phi(g) v.

Then {i} is an isomorphism of groups.

In particular, using only {\otimes} structure this exhibits an isomorphism {G \cong \text{Aut }^\otimes(U)}. Consequently this solves the problem proposed at the beginning of the lecture.

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

To see it’s injective, we show {1_G \neq g \in G} gives {T^g} isn’t the identity automorphism. i.e. we need to find some representation for which {g} acts nontrivially on {V}. 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 {T \in \text{Aut }^\otimes(U)} is completely determined by {T_{k[G]}(1_{k[G]}) \in k[G]}.


Proof: Let {(V, \phi)} be a representation of {G}. Then for all {v \in V}, we have a unique morphism of representations

\displaystyle f_v : k[G] \rightarrow (V, \phi) \quad\text{by}\quad 1_{k[G]} \mapsto v.

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


Next, we claim

Lemma 6

{T_{k[G]}(1_{k[G]})} is a grouplike element of {k[G]}.


Proof: Draw the diagram

rep-tan-5and note that it implies

\displaystyle \Delta(T_{k[G]}(1_{k[G]})) = T_{k[G]}(1_{k[G]}) \otimes T_{k[G]}(1_{k[G]}).

This implies surjectivity, by our earlier observation that grouplike elements in {k[G]} are exactly the elements of {G}. \Box


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 {m \times n} 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

\displaystyle \left( \begin{array}{cccc} 1 & 0 & \dots & 0 \\ 0 & 1 & \dots & 0 \\ \vdots & \vdots & \ddots & \vdots \\ 0 & 0 & \dots & 1 \\ \end{array} \right)

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 {\det(AB) = \det A \det B}, 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 {T_1} and {T_2} are similar if

\displaystyle T_2 = ST_1S^{-1}

for some invertible matrix {S}. You’re told that the trace of a matrix {\text{Tr } T} 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

\displaystyle p_T = \det (XI - T).

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: {p_T(T)} 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 {T_2 = ST_1S^{-1}}? Only if you know that the matrices are linear maps does this make sense: {T_2} is just {T_1} 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 {\rho_\alpha} is equal to the number of conjugacy classes of {G}.
  2. We have { \left\lvert G \right\rvert = \sum_\alpha \left( \dim \rho_\alpha \right)^2 }.

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

In what follows {k} is an algebraically closed field, {G} is a finite group, and the characteristic of {k} does not divide {\left\lvert G \right\rvert}. 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.

\displaystyle  	\begin{array}{|l|lll|} 		\hline 		\text{Representation} & \text{Group} & \text{Space} & \text{Action} \\ \hline 		\rho & V & G & G \rightarrow g \cdot_\rho V \\ 		\text{Fun}(X) & G & \text{Fun}(X) & (g \cdot f)(x) = f(g^{-1} \cdot x) \\ 		\text{triv}_G & G & k & g \cdot a = a \\ 		\rho_1 \oplus \rho_2 & G & V_1 \oplus V_2 & g \cdot (v_1 + v_2) = (g \cdot_{\rho_1} v_1) + (g \cdot_{\rho_2} v_2) \\ 		\rho_1 \boxtimes \rho_2 & G_1 \times G_2 & V_1 \otimes V_2 & (g_1, g_2) \cdot (v_1 \otimes v_2) \\ 		&&& = (g_1 \cdot_{\rho_1} v_1) \otimes (g_2 \cdot_{\rho_2} v_2) \\ 		\text{Res}^G_H(\rho) & H & V & h \cdot v = h \cdot_\rho v\\ 		\rho_1 \otimes \rho_2 & G & V_1 \otimes V_2 & g \cdot (v_1 \otimes v_2) = (g \cdot_{\rho_1} v_1) \otimes (g \cdot_{\rho_2} v_2) \\ 		\text{Reg}(G) & G \times G & \text{Fun}(G) & (g_1, g_2) \cdot f(g) = f(g_2 g g_1^{-1}) \\ 		\rho^\vee & V^\vee & G & (g \cdot \xi)(v) = \xi(g^{-1} \cdot_\rho v) \\ 		\hline 	\end{array}

1. The Regular Representation

Recall that {\mathrm{Fun}(G)} is the vector space of functions from {G} to {k}, with addition being defined canonically. It has a basis of functions {\delta_g} for each {g \in G}, where

\displaystyle  	\delta_g(x) 	= 	\begin{cases} 		1 & x = g \\ 		0 & \text{otherwise} 	\end{cases}

for every {x \in G}. (Throughout this post, I’ll be trying to use {x} to denote inputs to a function from {G} to {k}.)

Definition Let {G} be a finite group. Then the finite regular representation, {\mathrm{Reg}(G)} is a representation on {G \times G} defined on the vector space {\mathrm{Fun}(G)}, with the following action for each {f \in \mathrm{Fun}(G)} and {(g_1, g_2) \in G \times G}:

\displaystyle  ( g_1, g_2 ) \cdot f(x) \overset{\text{def}}{=} f(g_2 x g_1^{-1}).

Note that this is a representation of the product {G \times G}, not {G}! (As an aside, you can also define this representation for infinite groups {G} by replacing {\mathrm{Fun}(G)} with {\mathrm{Fun}_c(G)}, the functions which are nonzero at only finitely many {g \in G}.)

In any case, we now can make {\mathrm{Reg}(G)} into a representation of {G} by this restriction, giving {\mathrm{Res}_G^{G \times G} \left( \mathrm{Reg}(G) \right)}, which I will abbreviate as just {\mathrm{Reg}^\ast(G)} through out this post (this is not a standard notation). The action for this is

\displaystyle  	(g \cdot_{\mathrm{Reg}^\ast(G)} f)(x) 	\overset{\text{def}}{=} 	\left( (g, g) \cdot_{\mathrm{Reg}(G)} f \right)(x) 	= f\left( g^{-1} x g \right).

Exercise Consider the invariant subspace of {\mathrm{Reg}^\ast(G)}, which is

\displaystyle  \left( \mathrm{Reg}^\ast(G) \right)^G 		= 		\left\{ f : G \rightarrow V \mid f(g^{-1} x g) = f(x) \; \forall x,g \in G \right\}.

Prove that the dimension of this space is equal to the number of conjugacy classes of {G}. (Look at the {\delta_g} basis.)

Recall that in general, the invariant subspace {\rho^G} is defined as

\displaystyle  \rho^G \overset{\text{def}}{=} \left\{ v \in V \mid g \cdot_\rho v = v \; \forall g \in G \right\}.

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 {V}, we define the \textbf} by

\displaystyle  V^\vee \overset{\text{def}}{=} \mathrm{Hom}(V,k)

i.e. it is the set of maps from {V} to {k}. If {V} is finite-dimensional, we can think of this as follows: if {V} consists of the column vectors of length {m}, then {V^\vee} is the row vectors of length {m}, which can be multiplied onto elements of {V}. (This analogy breaks down for {V} infinite dimensional.) Recall that if {V} is finite-dimensional then there is a canonical isomorphism {V \simeq (V^\vee)^\vee} by the map {v \mapsto \mathrm{ev}_v}, where {\mathrm{ev}_v : V^\vee \rightarrow k} sends {\xi \mapsto \xi(v)}.

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

Definition Let {\rho = (V, \cdot_\rho)} be a {G}-representation. Then we define the dual representation {\rho^\vee} by

\displaystyle  \rho^\vee = \left( V^\vee, \cdot_{\rho^\vee} \right) 		\quad\text{where}\quad 		\left( g \cdot_{\rho^\vee} \xi \right)(v) 		= \xi \left( g^{-1} \cdot_\rho v \right).

Lemma 1 If {\rho} is finite-dimensional then {(\rho^\vee)^\vee \simeq \rho} by the same isomorphism.

Proof: We want to check that the isomorphism {V = (V^\vee)^\vee} by {v \mapsto \mathrm{ev}_v} respects the action of {G}. That’s equivalent to checking

\displaystyle  \mathrm{ev}_{g \cdot_\rho v} = g \cdot_{(\rho^\vee)^\vee} \mathrm{ev}_v.


\displaystyle  		\mathrm{ev}_{g \cdot v}(\xi) 		= \xi(g \cdot_\rho v)


\displaystyle  		\left( g \cdot_{(\rho^\vee)^\vee} \mathrm{ev}_v \right)(\xi) 		= 		\mathrm{ev}_v(g^{-1} \cdot_{\rho^\vee} \xi) 		= \left( g^{-1} \cdot_{\rho^\vee} \xi \right)(v) 		= \xi(g \cdot_\rho v).

So the functions are indeed equal. \Box

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

Lemma 2 For any finite-dimensional {\rho_1}, {\rho_2} we have {\mathrm{Hom}_G(\rho_1, \rho_2) \simeq \mathrm{Hom}_G(\rho_1 \otimes \rho_2^\vee, \text{triv}_G)}.

Proof: Let {\rho_1 = (V_1, \cdot_{\rho_1})} and {\rho_2 = (V_2, \cdot_{\rho_2})}. We already know that we have an isomorphism of vector homomorphisms

\displaystyle  		\mathrm{Hom}_{\textbf{Vect}}(V_1, V_2) 		\simeq \mathrm{Hom}_{\textbf{Vect}} (V_1 \otimes V_2^\vee, k)

by sending each {T \in \mathrm{Hom}_{\textbf{Vect}}(V_1, V_2)} to the map {T' \in \mathrm{Hom}_{\textbf{Vect}} (V_1 \otimes V_2^\vee, k)} which has {T'(v \otimes \xi) = \xi(T(v))}. So the point is to check that {T} respects the {G}-action if and only if {T'} does. This is just a computation. \Box

You can deduce as a corollary the following.

Exercise Use the lemma to show {\mathrm{Hom}_G(\rho, \text{triv}_G) \simeq \mathrm{Hom}_G(\text{triv}_G, \rho^\vee)}.

Finally, we want to talk about when {\rho^\vee} being irreducible. The main result is the following.

Lemma 3 Consider a representation {\rho}, not necessarily finite-dimensional. If {\rho^\vee} is irreducible then so is {\rho}.

When {\rho} is finite dimensional we have {(\rho^\vee)^\vee \simeq \rho}, and so it is true for finite-dimensional irreducible {\rho} that {\rho^\vee} is also irreducible. Interestingly, this result fails for infinite-dimensional spaces as this math.SE thread shows.

Proof: Let {\rho = (V, \cdot_\rho)}. Let {W} be a {\rho}-invariant subspace of {V}. Then consider

\displaystyle  W^\perp = \left\{ \xi \in V^\vee : \xi(w) = 0 \right\}.

This is a {\rho^\vee}-invariant subspace of {V^\vee}, so since {\rho^\vee} is irreducible, either {W^\perp = V^\vee} or {W^\perp = \{0\}}. You can check that these imply {W=0} and {W=V}, respectively. \Box

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 {\mathrm{Reg}(G)}.

Theorem 4 We have an isomorphism

\displaystyle  		\mathrm{Reg}(G) \simeq 		\bigoplus_{\alpha} \rho_\alpha \boxtimes \rho_\alpha^\vee.

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

Lemma 5 Let {\pi} be a representation of {G \times G}. Then there is an isomorphism

\displaystyle  \mathrm{Hom}_{G \times G}(\pi, \mathrm{Reg}(G)) 		\simeq \mathrm{Hom}_G(\mathrm{Res}^{G \times G}_G(\pi), \text{triv}_G).

Proof: Let {\pi = (V, \cdot_\pi)}. Given a map {T : V \rightarrow \mathrm{Fun}(G)} which respects the {G \times G} action, we send it to the map {\xi_T : V \rightarrow k} with {\xi_T(v) = T(v)(1)}. Conversely, given a map {\xi : V \rightarrow k} which respects the {G} action, we send it to the map {T_\xi : V \rightarrow \mathrm{Fun}(G)} so that {T_\xi(v)(x) = \xi\left( (x,x^{-1}) \cdot v \right)}.

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 {\xi_T(v)} respects the {G} action given that {T} respects the {G \times G} action. We want to prove

\displaystyle  \xi_T\left( (g,g) \cdot_\pi v \right) 	= g \cdot_\text{triv} \xi_T(v) = \xi_T(v).

Using the definition of {\xi_T}

\displaystyle  		\begin{aligned} 		\xi_T\left( (g,g) \cdot_\pi (v) \right) 		&= T\left( (g,g) \cdot_\pi v \right)(1) \\ 		&= \left( (g,g) \cdot_{\mathrm{Fun}(G)} T(v) \right)(1) \\ 		&= T(v)\left( g 1 g^{-1} \right) = T(v)(1) = \xi_T(v). 		\end{aligned}

The remaining computations are left to a very diligent reader. \Box

Now let’s prove the main theorem!

Proof: We have that {\mathrm{Reg}(G)} is the sum of finite-dimensional irreducibles {\rho_\alpha \boxtimes \rho_\beta}, meaning

\displaystyle  		\mathrm{Reg}(G) = 		\bigoplus_{\alpha, \beta} 		\left( \rho_\alpha \boxtimes \rho_\beta \right) 		\otimes 		\mathrm{Hom}_{G \times G}\left( \rho_\alpha \boxtimes \rho_\beta, \mathrm{Reg}(G) \right).

But using our lemmas, we have that

\displaystyle  		\mathrm{Hom}_{G \times G}\left( \rho_\alpha \boxtimes \rho_\beta, \mathrm{Reg}(G) \right) 		\simeq 		\mathrm{Hom}_G(\rho_\alpha \otimes \rho_\beta, \text{triv}_G) 		\simeq \mathrm{Hom}_G(\rho_\alpha, \rho_\beta^\vee).

We know that {\rho_\beta^\vee} is also irreducible, since {\rho_\beta} is (and we’re in a finite-dimensional situation). So

\displaystyle  		\mathrm{Hom}_G\left( \rho_\alpha, \rho_\beta^\vee \right) 		\simeq 		\begin{cases} 			k & \rho_\beta^\vee = \rho_\alpha \\ 			\{0\} & \text{otherwise}. 		\end{cases}

Thus we deduce

\displaystyle  \mathrm{Reg}(G) 		\simeq \bigoplus_{\alpha} 		\left( \rho_\alpha \boxtimes \rho_\alpha^\vee \right) 		\otimes k 		\simeq \bigoplus_{\alpha} 		\left( \rho_\alpha \boxtimes \rho_\alpha^\vee \right)

and we’re done. \Box

4. Corollaries

Recall that {\mathrm{Fun}(G)}, the space underlying {\mathrm{Reg}(G)}, has a basis with size {\left\lvert G \right\rvert}. Hence by comparing the dimensions of the isomorphsims, we obtain the following corollary.

Theorem 6 We have {\left\lvert G \right\rvert = \sum_\alpha \left( \dim \rho_\alpha \right)^2}.

Moreover, by restriction to {G} we can obtain the corollary

\displaystyle  	\mathrm{Reg}^\ast(G) 	\simeq \bigoplus_\alpha \mathrm{Res}_{G}^{G \times G} \left( \rho_\alpha \otimes \rho_\alpha^\vee \right) 	= \bigoplus_\alpha \rho_\alpha \otimes \rho_\alpha^\vee.

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

\displaystyle  \left( \rho_\alpha \otimes \rho_\alpha^\vee \right)^G \simeq k.

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

\displaystyle  \left( \rho_\alpha \otimes \rho_\alpha^\vee \right)^G \simeq 	\mathrm{Hom}_G(\text{triv}_G, \rho_\alpha \otimes \rho_\alpha^\vee).

Then we can write

\displaystyle  \begin{aligned} 	\mathrm{Hom}_G(\text{triv}_G, \rho_\alpha \otimes \rho_\alpha^\vee) 	&\simeq 	\mathrm{Hom}_G\left(\text{triv}_G, \left( \rho_\alpha^\vee \otimes \rho_\alpha \right)^\vee \right) \\ 	&\simeq \mathrm{Hom}_G\left(\rho_\alpha^\vee \otimes \rho_\alpha, \text{triv}_G \right) \\ 	&\simeq \mathrm{Hom}_G\left(\rho_\alpha \otimes \rho_\alpha^\vee, \text{triv}_G \right) \\ 	&\simeq \mathrm{Hom}_G\left(\rho_\alpha, \rho_\alpha \right) \\ 	&\simeq k \end{aligned}

by the lemma, where we have also used Schur’s Lemma at the last step. So that means the dimension of the invariant space {(\mathrm{Reg}^\ast (G))^G} is just the number of irreducibles.

But we already showed that the invariant space of {(\mathrm{Reg}^\ast (G))^G} has dimension equal to the conjugacy classes of {G}. Thus we conclude the second result.

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


Time permitting I might talk about the irreducibles of {S_n} 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 {2015 = 5 \cdot 13 \cdot 31}.

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

In what follows {k} is an algebraically closed field, {G} is a finite group, and the characteristic of {k} does not divide {\left\lvert G \right\rvert}.

1. Products of Representations

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

Definition Let {G_1} and {G_2} be groups. Given a {G_1} representation {\rho_1 = (V_1, \cdot_{\rho_1})} and a {G_2} representation {\rho_2 = (V_2, \cdot_{\rho_2})}, we define

\displaystyle  \rho_1 \boxtimes \rho_2 \overset{\text{def}}{=} 	\left( V_1 \otimes V_2, \cdot \right)

as a representation of {G_1 \times G_2} on {V_1 \otimes V_2}. The action is given by

\displaystyle  (g_1, g_2) \cdot (v_1 \otimes v_2) 	= \left( g_1 \cdot_{\rho_1} v_1 \right) \otimes (g_2 \cdot_{\rho_2} v_2).

In the special case {G_1 = G_2 = G}, we can also restrict {\rho_1 \boxtimes \rho_2} to a representation of {G}. Note that we can interpret {G} itself as a subgroup of {G \times G} by just looking along the diagonal: there’s an obvious isomorphism

\displaystyle  G \sim \left\{ (g,g) \mid g \in G \right\}.

So, let me set up the general definition.

Definition Let {\mathcal G} be a group, and let {\mathcal H} be a subgroup of {\mathcal G}. Then for any representation {\rho = (V, \cdot_\rho)} of {\mathcal G}, we let

\displaystyle  \mathrm{Res}^{\mathcal G}_{\mathcal H} (\rho)

denote the representation of {\mathcal H} on {V} 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 {\rho_1 \otimes \rho_2} out of {\rho_1 \boxtimes \rho_2}.

Definition Let {\rho_1 = (V_1, \cdot_{\rho_1})} and {\rho_2 = (V_2, \cdot_{\rho_2})} be representations of {G}. Then we define

\displaystyle  \rho_1 \otimes \rho_2 		\overset{\text{def}}{=} 		\mathrm{Res}^{G \times G}_G \left( \rho_1 \boxtimes \rho_2 \right)

meaning {\rho_1 \otimes \rho_2} has vector space {V_1 \otimes V_2} and action {g \cdot (v_1 \otimes v_2) = (g \cdot_{\rho_1} v_1) \otimes (g \cdot_{\rho_2} v_2)}.

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

Lemma 1 Given representations {\rho}, {\rho_1}, {\rho_2} we have

\displaystyle  		\rho \otimes \left( \rho_1 \oplus \rho_2 \right) 		\simeq 		\left( \rho \otimes \rho_1 \right) \oplus \left( \rho \otimes \rho_2 \right).

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

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

\displaystyle  	\begin{array}{|l|lll|} 		\hline 		\text{Representation} & \text{Group} & \text{Space} & \text{Action} \\ \hline 		\rho & V & G & g \cdot_\rho v \\ 		\text{Fun}(X) & G & \text{Fun}(X) & (g \cdot f)(x) = f(g^{-1} \cdot x) \\ 		\text{triv}_G & G & k & g \cdot a = a \\ 		\rho_1 \oplus \rho_2 & G & V_1 \oplus V_2 & g \cdot (v_1 + v_2) = (g \cdot_{\rho_1} v_1) + (g \cdot_{\rho_2} v_2) \\ 		\rho_1 \boxtimes \rho_2 & G_1 \times G_2 & V_1 \otimes V_2 & (g_1, g_2) \cdot (v_1 \otimes v_2) \\ 		&&& = (g_1 \cdot_{\rho_1} v_1) \otimes (g_2 \cdot_{\rho_2} v_2) \\ 		\text{Res}^G_H(\rho) & H & V & h \cdot v = h \cdot_\rho v\\ 		\rho_1 \otimes \rho_2 & G & V_1 \otimes V_2 & g \cdot (v_1 \otimes v_2) = (g \cdot_{\rho_1} v_1) \otimes (g \cdot_{\rho_2} v_2) \\ 		\hline 	\end{array}

2. Revisiting Schur and Maschke

Defining a tensor product of representations gives us another way to express {\rho^{\oplus n}}, as follows. By an abuse of notation, given a vector space {k^m} we can define an associated {G}-representation {k^m = (k^m, \cdot_{k^m})} on it by the trivial action, i.e. {g \cdot_{k^m} v = v} for {v \in k^m}. A special case of this is using {k} to represent {\text{triv}_G}. With this abuse of notation, we have the following lemma.

Lemma 2 Let {M} be an {m}-dimensional vector space over {k}. Then {\rho^{\oplus m} \simeq \rho \otimes M}.

Proof: It reduces to checking that {\rho \otimes k \overset{\text{def}}{=} \rho \otimes \text{triv}_G} is isomorphic to {\rho}, which is evident. We can then proceed by induction: {\rho \otimes (k \oplus k^{t-1}) 	\simeq (\rho \otimes k) \oplus (\rho \otimes k^{t-1})}. \Box

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

\displaystyle  \rho \simeq \bigoplus_\alpha \rho_\alpha^{\oplus n_\alpha} \quad\text{where}\quad n_\alpha = \dim \mathrm{Hom}_G(\rho, \rho_\alpha)

we now have instead

\displaystyle  	\bigoplus_\alpha \rho_\alpha \otimes \mathrm{Hom}_G(\rho, \rho_\alpha) 	\simeq \rho.

Now we’re going to explicitly write down the isomorphism between these maps. It suffices to write down the isomorphism {\rho_\alpha \otimes \mathrm{Hom}_G(\rho, \rho_\alpha) \rightarrow \rho_\alpha^{\oplus n_\alpha}}, and then take the sum over each of the {\alpha}‘s. But

\displaystyle  \mathrm{Hom}_G(\rho, \rho_\alpha) \simeq \mathrm{Hom}_G(\rho_\alpha^{\oplus n_\alpha}, \rho_\alpha) \simeq \mathrm{Hom}_G(\rho_\alpha, \rho_\alpha)^{\oplus n_\alpha}.

So to write the isomorphism {\rho_\alpha \otimes \mathrm{Hom}_G(\rho_\alpha, \rho_\alpha)^{\oplus n_\alpha} \rightarrow \rho_\alpha^{\oplus n_\alpha}}, we just have to write down the isomorphism {\rho_\alpha \otimes \mathrm{Hom}_G(\rho_\alpha, \rho_\alpha) \rightarrow \rho_\alpha},

Schur’s Lemma tells us that {\mathrm{Hom}_G(\rho_\alpha, \rho_\alpha) \simeq k}; i.e. every {\xi \in \mathrm{Hom}_G(\rho_\alpha, \rho_\alpha)} just corresponds to multiplying {v} by some constant. So this case is easy: the map

\displaystyle  v \otimes \xi \mapsto \xi(v)

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 {\rho}, the homomorphism of {G} representations

\displaystyle  	\bigoplus_\alpha \rho_\alpha \otimes \mathrm{Hom}_G(\rho, \rho_\alpha) 	\rightarrow \rho

given by sending every simple tensor via

\displaystyle  v \otimes \xi \mapsto \xi(v)

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 {G_1 \times G_2} 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 {G_1} and {G_2} be finite groups. Then a finite-dimensional representation {\rho} of {G_1 \times G_2} is irreducible if and only if it is of the form

\displaystyle  \rho_1 \boxtimes \rho_2

where {\rho_1} and {\rho_2} are irreducible representations of {G_1} and {G_2}, respectively.

Proof: First, suppose {\rho = (V, \cdot_\rho)} is an irreducible representation of {G_1 \times G_2}. Set

\displaystyle  \rho^1 \overset{\text{def}}{=} \mathrm{Res}^{G_1 \times G_2}_{G_1} (\rho).

Then by Maschke’s Theorem, we may write {\rho^1} as a direct sum of the irreducibles

\displaystyle  	\bigoplus_\alpha \rho_\alpha^1 \otimes \mathrm{Hom}_{G_1} (\rho_\alpha^1, \rho^1) \simeq \rho^1

with the map {v \otimes \xi \mapsto \xi(v)} being the isomorphism. Now we can put a {G_2} representation structure on {\mathrm{Hom}_{G_1} (\rho_\alpha^1, \rho^1)} by

\displaystyle  	(g_2 \cdot f)(g) 	= g_2 \cdot_{\rho} (f(g)).

It is easy to check that this is indeed a {G_2} representation. Thus it makes sense to talk about the {G_1 \times G_2} representation

\displaystyle  	\bigoplus_\alpha \rho_\alpha^1 \boxtimes \mathrm{Hom}_{G_1} (\rho_\alpha^1, \rho^1).

We claim that the isomorphism for {\rho^1} as a {G_1} representation now lifts to an isomorphism of {G_1 \times G_2} representations. That is, we claim that

\displaystyle  	\bigoplus_\alpha \rho_\alpha^1 \boxtimes \mathrm{Hom}_{G_1} (\rho_\alpha^1, \rho^1) \simeq \rho

by the same isomorphism as for {\rho^1}. To see this, we only have to check that the isomorphism {v \otimes \xi \mapsto \xi(v)} commutes with the action of {g_2 \in G_2}. But this is obvious, since {g_2 \cdot (v \otimes \xi) = v \otimes (g_2 \cdot \xi) \mapsto (g_2 \cdot \xi)(v)}.

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

Now for the other direction: take {\rho_1} and {\rho_2} irreducible. Suppose {\rho_1 \boxtimes \rho_2} has a nontrivial subrepresentation of the form {\rho_1' \boxtimes \rho_2'}. Viewing as {G_1} representation, we find that {\rho_1'} is a nontrivial subrepresentation of {\rho_1}, and similarly for {\rho_2}. But {\rho_1} is irreducible, hence {\rho_1' \simeq \rho_1}. Similarly {\rho_2' \simeq \rho_2}. So in fact {\rho_1' \boxtimes \rho_2' \simeq \rho_1 \boxtimes \rho_2}. Hence we conclude {\rho_1 \boxtimes \rho_2} is irreducible. \Box

4. Conclusion

In particular, this means that any representation {\rho} of {G \times G} decomposes as

\displaystyle  \rho \simeq \bigoplus_{\alpha, \beta} \rho_\alpha \boxtimes \rho_\beta

and we even have

\displaystyle  \mathrm{Res}_{G}^{G\times G} \rho \simeq \bigoplus_{\alpha, \beta} \rho_\alpha \otimes \rho_\beta.

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 {G} now, and consider all isomorphism classes of finite-dimensional representations of {G}. We’ll denote this set by {\mathrm{Irrep}(G)}. Maschke’s Theorem tells us that any finite-dimensional representation {\rho} can be decomposed as

\displaystyle  	\bigoplus_{\rho_\alpha \in \mathrm{Irrep}(G)} \rho_{\alpha}^{\oplus n_\alpha}

where {n_\alpha} is some nonnegative integer. This begs the question: what is {n_\alpha}? Is it even uniquely determined by {\rho}?

To answer this I first need to compute {\mathrm{Hom}_G(\rho, \pi)} for any two distinct irreducible representations {\rho} and {\pi}. One case is easy.

Lemma 1 Let {\rho} and {\pi} be non-isomorphic irreducible representations (not necessarily finite dimensional). Then there are no nontrivial homomorphisms {\phi : \rho \rightarrow \pi}. In other words, {\mathrm{Hom}_G(\rho, \pi) = \{0\}}.

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 {G}-representations between them which is also a bijection of the underlying vector spaces.

Proof: Let {\phi : \rho_1 \rightarrow \rho_2} be a nonzero homomorphism. We can actually prove the following stronger results.

  • If {\rho_2} is irreducible then {\phi} is surjective.
  • If {\rho_1} is irreducible then {\phi} is injective.

Exercise Prove the above two results. (Hint: show that {\text{Im } \phi} and {\ker \phi} give rise to subrepresentations.)

Combining these two results gives the lemma because {\phi} is now a bijection, and hence an isomorphism. \Box

2. Schur’s Lemma

Thus we only have to consider the case {\rho \simeq \pi}. 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 {k} is algebraically closed. Let {\rho} be a finite dimensional irreducible representation. Then {\mathrm{Hom}_{G} (\rho, \rho)} consists precisely of maps of the form {v \mapsto \lambda v}, where {\lambda \in k}; the only possible maps are multiplication by a scalar. In other words,

\displaystyle  \mathrm{Hom}_{G} (\rho, \rho) \simeq k

and {\dim \mathrm{Hom}_G(\rho, \rho) = 1}.

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

Example Let {k = {\mathbb R}}, let {V = {\mathbb R}^2}, and let {G = {\mathbb Z}_3} act on {V} by rotating every {\vec x \in {\mathbb R}^2} by {120^{\circ}} around the origin, giving a representation {\rho}. Then {\rho} 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 {\rho} as a map in {{\mathbb C}} which is multiplication by {e^{\frac{2\pi i}{3}}}. Then for any other complex number {\xi}, the map “multiplication by {\xi}” commutes with the map “multiplication by {e^{\frac{2\pi i}{3}}}”. So in fact

\displaystyle  \mathrm{Hom}_G(\rho, \rho) \simeq {\mathbb C}

which has dimension {2}. \Box

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

Proof: Clearly any map {v \mapsto \lambda v} respects the {G}-action.

Now consider any {T \in \mathrm{Hom}_G(\rho, \rho)}. Set {\rho = (V, \cdot_\rho)}. Here’s the key: because {k} is algebraically closed, and we’re over a finite dimensional vector space {V}, the map {T} has an eigenvalue {\lambda}. Hence by definition {V} has a subspace {V_\lambda} over which {T} is just multiplication by {\lambda}.

But then {V_\lambda} is a {G}-invariant subspace of {V}! Since {\rho} is irreducible, this can only happen if {V = V_\lambda}. That means {T} is multiplication by {\lambda} for the entire space {V}, as desired. \Box

3. Computing dimensions of homomorphisms

Since we can now compute the dimension of the {\mathrm{Hom}_G} of any two irreducible representations, we can compute the dimension of the {\mathrm{Hom}_G} for any composition of irreducibles, as follows.

Corollary 3 We have

\displaystyle  		\dim \mathrm{Hom}_G 		\left( \bigoplus_\alpha \rho_\alpha^{\oplus n_\alpha}, 		\bigoplus_\beta \rho_\beta^{\oplus m_\beta} \right) 		= \sum_{\alpha} n_\alpha m_\alpha

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

Proof: The {\mathrm{Hom}} just decomposes over each of the components as

\displaystyle  		\begin{aligned} 		\mathrm{Hom}_G 		\left( \bigoplus_\alpha \rho_\alpha^{\oplus n_\alpha}, 		\bigoplus_\beta \rho_\beta^{\oplus m_\beta} \right) 		&\simeq 		\bigoplus_{\alpha, \beta} 		\mathrm{Hom}_G(\rho_\alpha^{\oplus n_\alpha}, \rho_\beta^{\oplus m_\beta}) \\ 		&\simeq 		\bigoplus_{\alpha, \beta} 		\mathrm{Hom}_G(\rho_\alpha, \rho_\beta)^{\oplus n_\alpha m_\alpha}. 		\end{aligned}

Here we’re using the fact that {\mathrm{Hom}_G(\rho_1 \oplus \rho_2, \rho) = \mathrm{Hom}_G(\rho_1, \rho) \oplus \mathrm{Hom}_G(\rho_2, \rho)} (obvious) and its analog. The claim follows from our lemmas now. \Box

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

Corollary 4 Suppose {\rho = \bigoplus_\alpha \rho_\alpha^{n_\alpha}} as above. Then for any particular {\beta},

\displaystyle  n_\beta = \dim \mathrm{Hom}_G(\rho, \rho_\beta).

Proof: We have

\displaystyle  \dim \mathrm{Hom}_G(\rho, \rho_\beta) = n_\beta \mathrm{Hom}_G(\rho_\beta, \rho_\beta) = n_\beta

as desired. \Box

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

\displaystyle  n_\beta = \frac{\dim \mathrm{Hom}_G(\rho, \rho_\beta)}{\dim \mathrm{Hom}_G(\rho_\beta, \rho_\beta)}.

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 {G}.

  • Maschke’s Theorem: If {G} is finite and {\text{char } k} does not divide {\left\lvert G \right\rvert}, then any finite dimensional representation is a direct sum of irreducibles. This decomposition is unique up to isomorphism.
  • Schur’s Lemma: If {k} is algebraically closed, then {\mathrm{Hom}_G(\rho, \rho) \simeq k} for any irreducible {\rho}, 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 {\rho_\alpha} is equal to the number of conjugacy classes of {G}.
  2. We have { \left\lvert G \right\rvert = \sum_\alpha \left( \dim \rho_\alpha \right)^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 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 {k} (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 {G} be a group.

Definition A representation of {G} consists of a pair {\rho = (V, \cdot_\rho)} where {V} is a vector space over {k} and {\cdot_\rho} is a (left) group action of {G} on {V} which is linear in {V}. If {V} is finite-dimensional then the dimension of {\rho} is just the dimension of {V}.

Explicitly the conditions on {\cdot_\rho} are that

\displaystyle \begin{aligned} 1 \cdot_\rho v &= v \\ g_1 \cdot_\rho (g_2 \cdot_\rho v) &= (g_1g_2) \cdot_\rho v \\ g_1 \cdot_\rho (v_1 + v_2) &= g \cdot_\rho v_1 + g \cdot_\rho v_2 \\ g_1 \cdot_\rho (cv) &= c(g \cdot_\rho v). \end{aligned}

Note that another equivalent phrasing is that {\rho} is a homomorphism from {G} to the general linear group {\text{GL}(V)}; however, we will not use this phrasing.

By abuse of notation, we occasionally refer to {\rho} by just its underlying vector space {V} in the case that {\cdot_\rho} is clear from context. We may also abbreviate {g \cdot_\rho v} as just {g \cdot v}.

A simple example of a nontrivial representation is the following.

Example If {V = k^{n}} and {G = S_n}, then an example of an action is {\rho = (V, \cdot_\rho)} is simply

\displaystyle \sigma \cdot_\rho \left<x_1, \dots, x_n\right> = \left<x_{\sigma(1)}, \dots, x_{\sigma(n)}\right>

meaning we permute the basis elements of {V}. We denote this representation by {\mathrm{refl}_n}.

Let us give another useful example.

Definition Let {X} be a set acted on by {G}. We define the vector space

\displaystyle \mathrm{Fun}(X) \overset{\text{def}}{=} \left\{ \text{maps } X \rightarrow k \right\}

with the standard addition of functions.

Example We define a representation on {\mathrm{Fun}(X)} by the following action: every {f \in \mathrm{Fun}(X)} gets sent to a {g \cdot f \in \mathrm{Fun}(X)} by

\displaystyle (g \cdot_{\mathrm{Fun}(X)} f)(x) = f\left( g^{-1} \cdot_X x \right).

By abuse of notation we will let {\mathrm{Fun}(X)} 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 {G} be a group. We define the trivial representation {\text{triv}_G}, or just {\text{triv}}, as the representation {\text{triv}_G = (k, \cdot_\text{triv})}, where

\displaystyle g \cdot_\text{triv} a = a

for every {a \in k}. In other words, {G} acts trivially on {k}.

2. Homomorphisms of Representations

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

Definition Let {\rho_1 = (V_1, \cdot_{\rho_1})} and {\rho_2 = (V_2, \cdot_{\rho_2})} be representations of the same group {G}. A homomorphism of {G}-representations is a linear map {T : V_1 \rightarrow V_2} which respects the {G}-action: for any {g \in G} and {v \in V},

\displaystyle g \cdot_{\rho_2} T(v) = T\left( g \cdot_{\rho_1} v \right).

The set of all these homomorphisms is written {\mathrm{Hom}_G(\rho_1, \rho_2)}, which is itself a vector space over {k}.

(Digression: For those of you that know category theory, you might realize by now that representations correspond to functors from a category {\mathcal G} (corresponding to the group {G}) into {\textbf{Vect}_k} 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 {\rho = \left( V, \cdot_\rho \right)}. We define the {G}-invariant space {\rho^G \subseteq V} to be

\displaystyle \rho^G \overset{\text{def}}{=} \left\{ v \in V \mid g \cdot_\rho v = v \; \forall g \in G \right\}.

Then there is a natural bijection of vector spaces {\mathrm{Hom}_G(\text{triv}_G, \rho) \simeq \rho^G}.

Proof: Let {\rho = (V, \cdot_\rho)}. The set {\mathrm{Hom}_G(\text{triv}_G, \rho)} consists of maps {T : k \rightarrow V} with

\displaystyle g \cdot_\rho T(a) = T(g \cdot_{\text{triv}} a) = T(a)

for every {a \in k}. Since {T : k \rightarrow V} is linear, it is uniquely defined by {T(1)} (since {T(a) = a T(1)} in general). So {g \cdot_\rho T(1) = T(1)}, i.e. {T(1) \in \rho^G}, is necessary and sufficient. Thus the bijection is just {T \mapsto T(1)}. \Box

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 {\rho = (V, \cdot_\rho)}.

Definition Suppose we have a subspace {W \subseteq V} which is {\rho}-invariant, meaning that {g \cdot_\rho w \in W} for every {w \in W} and {g \in G}. Then we can construct a representation of {G} on {W} by restricting the action to {W}:

\displaystyle \rho' = \left( W, \cdot_\rho|_W \right).

In that case the resulting {\rho} is called a subrepresentation of {V}.

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

Example Consider the representation {\mathrm{refl} = (k^n, \cdot)} of {S_n} on {k^n} defined in the first section. For all {n \ge 2}, {\mathrm{refl}} is not irreducible.

Proof: Consider the subspace {W \subset k^n} given by

\displaystyle W = \left\{ (x_1, x_2, \dots, x_n) \mid x_1 + \dots + x_n = 0. \right\}

then {W} is invariant under {\mathrm{refl}}, so we have a subrepresentation of {\mathrm{refl}}, which we’ll denote {\mathrm{refl}_0}. \Box

This motivates the ideas of irreducibles.

Definition A representation {\rho} 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 {\rho_1 = (W_1, \cdot_{\rho_1})} and {\rho_2 = (W_2, \cdot_{\rho_2})} be representations and suppose we have {V = W_1 \oplus W_2}. Then we define the representation {\rho = \rho_1 \oplus \rho_2} by {\rho = (V, \cdot_\rho)} where

\displaystyle g \cdot_\rho (w_1 + w_2) = (g \cdot_{\rho_1} w_1) + (g \cdot_{\rho_2} w_2).

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 {G = S_2}, let {k = \mathbb F_2} be the finite field of order {2} (aka {{\mathbb Z}/2{\mathbb Z}}), and consider {\mathrm{refl} = (k^2, \cdot)}, which is not irreducible. However, we claim that we cannot write {\mathrm{refl} = \rho_1 \oplus \rho_2} for any nontrivial {\rho_1} and {\rho_2}.

Proof: This is a good concrete exercise.

Assume not, and let {V_1} and {V_2} be the underlying vector spaces of {\rho_1} and {\rho_2}. By nontriviality, {\dim V_1 = \dim V_2 = 1}, and in particular we have that as sets, {\left\lvert V_1 \right\rvert = \left\lvert V_2 \right\rvert = 2}. Take the only nonzero elements {(a,b) \in V_1} and {(c,d) \in V_2}. Since {V_1} is invariant under {\mathrm{refl}}, {(b,a) \in V_1}, so {(a,b) = (b,a) \implies (a,b) = (1,1) \in V_1}. Similarly, {(1,1) \in V_2}, which is impossible. \Box

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 {k} with any field which does not have characteristic {2}. Then {\rho} does decompose.

Proof: Consider the following two subspaces of {V = k^2}:

\displaystyle \begin{aligned} W_1 &= \left\{ \left<a, a\right> \mid a \in k \right\} \\ W_2 &= \left\{ \left<a, -a\right> \mid a \in k \right\}. \end{aligned}

It’s easy to see that both {W_1} and {W_2} are both invariant under {\rho}. Moreover, if {\text{char } k \neq 2} then we in fact have

\displaystyle V = W_1 \oplus W_2

because {\left<x,y\right> = \frac{1}{2} \left<x+y, x+y\right> + \frac{1}{2} \left<x-y, y-x\right>} for any {x,y \in k}. So if we let {\rho_1 = (W_1, \cdot_{\rho_1})} be the subrepresentation corresponding to {W_1}, and define {\rho_2} on {W_2} similarly, then we have {\rho = \rho_1 \oplus \rho_2}. \Box

Thus the only thing in the way of the counterexample was the fact that {\text{char } k = 2}. And it turns out in general this is the only obstacle, a result called Maschke’s Theorem.

Theorem 2 (Maschke’s Theorem) Suppose that {G} is a finite group, and {\text{char } k} does not divide {\left\lvert G \right\rvert}. 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 {m} decomposes as the product of primes. We use by strong induction on {m}; if {m} is prime we are done, and if {m} is composite there is a nontrivial divisor {d \mid m}, so we apply the inductive hypothesis to {d} and {m/d} 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

\displaystyle \frac{1}{\left\lvert G \right\rvert} \sum_{g \in G} g \cdot v

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

Proof: We proceed by induction on the dimension of the representation {\rho}. Let {\rho = (V, \cdot_\rho)} be a representation and assume its not irreducible, so it has a nontrivial subspace {W} which is {\rho}-invariant. It suffices to prove that there exists a subspace {W' \subset V} such that {W'} is also {\rho}-invariant and {V = W \oplus W'}, because then we can apply the inductive hypothesis to the subrepresentations induced by {W} and {W'}.

Let {\pi : V \rightarrow W} be any projection of {V} onto {W}. We consider the averaging map {T : V \rightarrow V} by

\displaystyle T(v) = \frac{1}{\left\lvert G \right\rvert} \sum_{g \in G} g^{-1} \cdot_\rho \pi(g \cdot_\rho v).

We’ll use the following properties of the map.

Exercise Show that the map {T} has the following three properties.

  • For any {w \in W}, {T(w) = w}.
  • For any {v \in V}, {T(w) \in W}.
  • {T \in \mathrm{Hom}_G(\rho, \rho)}.

As with any projection map {T}, we must have {V = \ker T \oplus \text{Im } T}. But {\text{Im } T = W}. Moreover, because the map {T} is {G}-invariant, it follows that {\ker T} is {\rho}-invariant. Hence taking {W' = \ker T} completes the proof. \Box

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 {\rho} can be decomposed as

\displaystyle \bigoplus_{\rho_\alpha \in \mathrm{Irrep}(G)} \rho_{\alpha}^{\oplus n_\alpha}

where {n_\alpha} is some nonnegative integer, and {\mathrm{Irrep}(G)} 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” {n_\alpha}. In the next post I’ll show how to compute the exponents {n_\alpha} (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.