The Unapologetic Mathematician

Mathematics for the interested outsider

General Linear Groups are Lie Groups

One of the most important examples of a Lie group we’ve already seen: the general linear group GL(V) of a finite dimensional vector space V. Of course for the vector space \mathbb{R}^n this is the same as — or at least isomorphic to — the group GL_n(\mathbb{R}) of all invertible n\times n real matrices, so that’s a Lie group we can really get our hands on. And if V has dimension n, then V\cong\mathbb{R}^n, and thus GL(V)\cong GL_n(\mathbb{R}).

So, how do we know that it’s a Lie group? Well, obviously it’s a group, but what about the topology? The matrix group GL_n(\mathbb{R}) sits inside the algebra M_n(\mathbb{R}) of all n\times n matrices, which is an n^2-dimensional vector space. Even better, it’s an open subset, which we can see by considering the (continuous) map \mathrm{det}:M_n(\mathbb{R})\to\mathbb{R}. Since GL_n(\mathbb{R}) is the preimage of \mathbb{R}\setminus\{0\} — which is an open subset of \mathbb{R} — GL_n(\mathbb{R}) is an open subset of M_n(\mathbb{R}).

So we can conclude that GL_n(\mathbb{R}) is an open submanifold of M_n, which comes equipped with the standard differentiable structure on \mathbb{R}^{n^2}. Matrix multiplication is clearly smooth, since we can write each component of a product matrix AB as a (quadratic) polynomial in the entries of A and B. As for inversion, Cramer’s rule expresses the entries of the inverse matrix A^{-1} as the quotient of a (degree n-1) polynomial in the entries of A and the determinant of A. So long as A is invertible these are two nonzero smooth functions, and thus their quotient is smooth at A.

June 9, 2011 Posted by | Algebra, Differential Topology, Group theory, Topology | 3 Comments

The Dominance Lemma

We will have use of the following technical result about the dominance order:

Let t^\lambda and s^\mu be Young tableaux of shape \lambda and \mu, respectively. If for each row, all the entries on that row of s^\mu are in different columns of t^\lambda, then \lambda\trianglerighteq\mu. Essentially, the idea is that since all the entries on a row in s fit into different columns of t, the shape of t must be wide enough to handle that row. Not only that, but it’s wide enough to handle all of the rows of that width at once.

More explicitly, we can rearrange the columns of t so that all the entries in the first i rows of s fit into the first i rows of t. This is actually an application of the pigeonhole principle: if we have a column in t that contains i+1 elements from the first i rows of s, then look at which row each one came from. Since i+1>i, we must have two entries in the column coming from the same row, which we assumed doesn’t happen.

Yes, this does change the tableau t, but our conclusion is about the shape of t, which remains the same.

So now we can figure \lambda_1+\dots+\lambda_i as the number of entries in the first i rows of t^\lambda. Since these contain all the entries from the first i rows of s^\mu, it must be greater than or equal to that number. But that number is just as clearly \mu_1+\dots+\mu_i. Since this holds for all i, we conclude that \lambda dominates \mu.

December 20, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 1 Comment

Young Tableaux

We want to come up with some nice sets for our symmetric group to act on. Our first step in this direction is to define a “Young tableau”.

If \lambda\vdash n is a partition of n, we define a Young tableau of shape \lambda to be an array of numbers. We start with the Ferrers diagram of the partition \lambda, and we replace the dots with the numbers 1 to n in any order. Clearly, there are n! Young tableaux of shape \lambda if \lambda\vdash n.

For example, if \lambda=(2,1), the Ferrers diagram is

\displaystyle\begin{array}{cc}\bullet&\bullet\\\bullet&\end{array}

We see that (2,1)\vdash3, and so there are 3!=6 Young tableaux of shape (2,1). They are

\displaystyle\begin{aligned}\begin{array}{cc}1&2\\3&\end{array}&,&\begin{array}{cc}1&3\\2&\end{array}&,&\begin{array}{cc}2&1\\3&\end{array}\\\begin{array}{cc}2&3\\1&\end{array}&,&\begin{array}{cc}3&1\\2&\end{array}&,&\begin{array}{cc}3&2\\1&\end{array}\end{aligned}

We write t_{i,j} for the entry in the (i,j) place. For example, the last tableau above has t_{1,1}=3, t_{1,2}=2, and t_{2,1}=1.

We also call a Young tableau t of shape \lambda a “\lambda-tableau”, and we write \mathrm{sh}(t)=\lambda. We can write a generic \lambda-tableau as t^\lambda.

December 9, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 13 Comments

Partitions and Ferrers Diagrams

We’ve discussed partitions before, but they’re about to become very significant. Let \lambda=(\lambda_1,\dots,\lambda_k) be a sequence of positive integers with \lambda_1\geq\dots\geq\lambda_k. We write

\displaystyle\lvert\lambda\rvert=\sum\limits_{i=1}^k\lambda_i

If \lvert\lambda\rvert=n we say \lambda is a partition of n, and we write \lambda\vdash n. A partition, then, is a way of breaking a positive integer n into a bunch of smaller positive integers, and sorting them in (the unique) decreasing order.

We visualize partitions with Ferrers diagrams. The best way to explain this is with an example: if \lambda=(3,3,2,1), the Ferrers diagram of \lambda is

\displaystyle\begin{array}{ccc}\bullet&\bullet&\bullet\\\bullet&\bullet&\bullet\\\bullet&\bullet&\\\bullet&&\end{array}

The diagram consists of left-justified rows, one for each part in the partition \lambda, and arranged from top to bottom in decreasing order. We can also draw the Ferrers diagram as boxes

\displaystyle\begin{array}{|c|c|c|}\cline{1-3}\hphantom{X}&\hphantom{X}&\\\cline{1-3}&&X\\\cline{1-3}&&\\\cline{1-2}&&\\\cline{1-1}\end{array}

The dangling vertical lines aren’t supposed to be there, but I’m having a hell of a time getting WordPress’ \LaTeX processor to recognize an \hfill command so I can place \vline elements at the edges of columns. This should work but.. well, see for yourself:

\displaystyle\begin{array}{ccc}\cline{1-3}\vline\hfill\hphantom{X}\hfill\vline&\hphantom{X}\hfill\vline&\hfill\vline\\\cline{1-3}\vline\hfill\hfill\vline&\hfill\vline&X\hfill\vline\\\cline{1-3}\vline\hfill\hfill\vline&\hfill\vline&\\\cline{1-2}\vline\hfill\hfill\vline&&\\\cline{1-1}\end{array}

So, if anyone knows how to make this look like the above diagram, but without the dangling vertical lines, I’d appreciate the help.

Anyway, in both of those ugly, ugly Ferrers diagrams, the X is placed in the (2,3) position; we see this by counting down two boxes and across three boxes. We will have plenty of call to identify which positions in a Ferrers diagram are which in the future.

December 8, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 10 Comments

The Road Forward

We’ve been talking a lot about the general theory of finite group representations. But our goal is to talk about symmetric groups in particular. Now, we’ve seen that the character table of a finite group is square, meaning there are as many irreducible representations of a group G as there are conjugacy classes K\subseteq G. But we’ve also noted that there’s no reason to believe that these have any sort of natural correspondence.

But for the symmetric group S_n, there’s something we can say. We know that conjugacy classes in symmetric groups correspond to cycle types. Cycles correspond to integer partitions of n. And from a partition we will build a representation.

For a first step, let n=\lambda_1+\lambda_2+\dots+\lambda_k be a partition, with \lambda_1\geq\lambda_2\geq\dots\geq\lambda_k. We can use this to come up with a subgroup S_\lambda\subseteq S_n. Given a set X we will write S_X for the group of permutations of that set. For example S_{\{1,\dots,\lambda_1\}} permutes the first \lambda_1 positive integers, and S_{\{\lambda_1+1,\dots,\lambda_2\}} permutes the next \lambda_2 of them. We can put a bunch of these groups together to build

\displaystyle S_\lambda=S_{\{1,\dots,\lambda_1\}}\times S_{\{\lambda_1+1,\dots,\lambda_2\}}\times\dots\times S_{\{\lambda_{k-1}+1,\dots,\lambda_k\}}

Elements of S_\lambda permute the same set as S_n, and so S_\lambda\subseteq S_n, but only in certain discrete chunks. Numbers in each block can be shuffled arbitrarily among each other, but the different blocks are never mixed. Really, all that matters is that the chunks have sizes \lambda_1 through \lambda_k, but choosing them like this is a nicely concrete way to do it.

So, now we can define the S_n-module M^\lambda=1\!\!\uparrow_{S_\lambda}^{S_n} by inducing the trivial representation from the subgroup S_\lambda to all of S_n. Now, the M^\lambda are not all irreducible, but we will see how to identify a particular irreducible submodule S^\lambda\subseteq M^\lambda of each one, and the S^\lambda will all be distinct. Since they correspond to partitions \lambda, there are exactly as many of them as there are conjugacy classes in S_n, and so they must be all the irreducible S_n-modules, up to isomorphism.

December 7, 2010 Posted by | Algebra, Group theory, Representation Theory, Representations of Symmetric Groups | 1 Comment

Inducing the Trivial Representation

We really should see an example of inducing a representation. One example we’ll find extremely useful is when we start with the trivial representation.

So, let G be a group and H be a subgroup. Since this will be coming up a bunch, let’s just start writing 1 for the trivial representation that sends each element of H to the 1\times1 matrix \begin{pmatrix}1\end{pmatrix}. We want to consider the induced representation 1\!\!\uparrow_H^G.

Well, we have a matrix representation, so we look at the induced matrix representation. We have to pick a transversal \{t_i\} for the subgroup H in G. Then we have the induced matrix in block form:

\displaystyle1\!\!\uparrow_H^G(g)=\begin{pmatrix}1(t_1^{-1}gt_1)&1(t_1^{-1}gt_2)&\cdots&1(t_1^{-1}gt_n)\\1(t_2^{-1}gt_1)&1(t_2^{-1}gt_2)&\cdots&1(t_2^{-1}gt_n)\\\vdots&\vdots&\ddots&\vdots\\1(t_n^{-1}gt_1)&1(t_n^{-1}gt_2)&\cdots&1(t_n^{-1}gt_n)\end{pmatrix}

In this case, each “block” is just a number, and it’s either 1 or 0, depending on whether t_i^{-1}gt_j is in H or not. But if t_i^{-1}gt_j\in H, then t_i^{-1}gt_jH=H, and latex g(t_jH)=(t_iH)$. That is, this is exactly the coset representation of G corresponding to H. And so all of these coset representations arise as induced representations.

December 6, 2010 Posted by | Algebra, Group theory, Representation Theory | 1 Comment

Dual Frobenius Reciprocity

Our proof of Frobenius reciprocity shows that induction is a left-adjoint to restriction. In fact, we could use this to define induction in the first place; show that restriction functor must have a left adjoint and let that be induction. The downside is that we wouldn’t get an explicit construction for free like we have.

One interesting thing about this approach, though, is that we can also show that restriction must have a right adjoint, which we might call “coinduction”. But it turns out that induction and coinduction are naturally isomorphic! That is, we can show that

\displaystyle\hom_H(W\!\!\downarrow^G_H,V)\cong\hom_G(W,V\!\!\uparrow_H^G)

Indeed, we can use the duality on hom spaces and apply it to yesterday’s Frobenius adjunction:

\displaystyle\begin{aligned}\hom_H(W\!\!\downarrow^G_H,V)&\cong\hom_H(V,W\!\!\downarrow^G_H)^*\\&\cong\hom_G(V\!\!\uparrow_H^G,W)^*\\&\cong\hom_G(W,V\!\!\uparrow_H^G)\end{aligned}

Sometimes when two functors are both left and right adjoints of each other, we say that they are a “Frobenius pair”.

Now let’s take this relation and apply our “decategorifying” correspondence that passes from representations down to characters. If the representation V has character \chi and W has character \psi, then hom-spaces become inner products, and (natural) isomorphisms become equalities. We find:

\displaystyle\langle\psi\!\!\downarrow^G_H,\chi\rangle_H=\langle\psi,\chi\!\!\uparrow_H^G\rangle_G

which is our “fake” Frobenius reciprocity relation.

December 3, 2010 Posted by | Algebra, Group theory, Representation Theory | 2 Comments

(Real) Frobenius Reciprocity

Now we come to the real version of Frobenius reciprocity. It takes the form of an adjunction between the functors of induction and restriction:

\displaystyle\hom_H(V,W\!\!\downarrow^G_H)\cong\hom_G(V\!\!\uparrow_H^G,W)

where V is an H-module and W is a G-module.

This is one of those items that everybody (for suitable values of “everybody”) knows to be true, but that nobody seems to have written down. I’ve been beating my head against it for days and finally figured out a way to make it work. Looking back, I’m not entirely certain I’ve ever actually proven it before.

So let’s start on the left with a linear map f:V\to W that intertwines the action of each subgroup element h\in H\subseteq G. We want to extend this to a linear map from V\!\!\uparrow_H^G to W that intertwines the actions of all the elements of G.

Okay, so we’ve defined V\!\!\uparrow_H^G=\mathbb{C}[G]\otimes_HV. But if we choose a transversal \{t_i\} for H — like we did when we set up the induced matrices — then we can break down \mathbb{C}[G] as the direct sum of a bunch of copies of \mathbb{C}[H]:

\displaystyle\mathbb{C}[G]=\bigoplus\limits_{i=1}^nt_i\mathbb{C}[H]

So then when we take the tensor product we find

\displaystyle\mathbb{C}[G]\otimes_HV=\left(\bigoplus\limits_{i=1}^nt_i\mathbb{C}[H]\right)\otimes_HV\cong\bigoplus\limits_{i=1}^nt_iV

So we need to define a map from each of these summands t_iV to W. But a vector in t_iV looks like t_iv for some v\in V. And thus a G-intertwinor \hat{f} extending f must be defined by \hat{f}(t_iv)=t_i\hat{f}(v)=t_if(v).

So, is this really a G-intertwinor? After all, we’ve really only used the fact that it commutes with the actions of the transversal elements t_i. Any element of the induced representation can be written uniquely as

\displaystyle v=\sum\limits_{i=1}^nt_iv_i

for some collection of v_i\in V. We need to check that \hat{f}(gv)=g\hat{f}(v).

Now, we know that left-multiplication by g permutes the cosets of H. That is, gt_i=t_{\sigma(i)}h_i for some h_i\in H. Thus we calculate

\displaystyle gv=\sum\limits_{i=1}^ngt_iv_i=\sum\limits_{i=1}^nt_{\sigma(i)}h_iv_i

and so, since \hat{f} commutes with h and with each transversal element

\displaystyle\begin{aligned}\hat{f}(gv)&=\sum\limits_{i=1}^n\hat{f}(t_{\sigma(i)}h_iv_i)\\&=\sum\limits_{i=1}^nt_{\sigma(i)}h_i\hat{f}(v_i)\\&=\sum\limits_{i=1}^ngt_i\hat{f}(v_i)\\&=g\hat{f}\left(\sum\limits_{i=1}^nt_iv_i\right)\\&=g\hat{f}(v)\end{aligned}

Okay, so we’ve got a map f\mapsto\hat{f} that takes H-module morphisms in \hom_H(V,W\!\!\downarrow^G_H) to G-module homomorphisms in \hom_G(V\!\!\uparrow_H^G,W). But is it an isomorphism? Well we can get go from \hat{f} back to f by just looking at what \hat{f} does on the component

\displaystyle V=1V\subseteq\bigoplus\limits_{i=1}^nt_iV

If we only consider the actions elements h\in H, they send this component back into itself, and by definition they commute with \hat{f}. That is, the restriction of \hat{f} to this component is an H-intertwinor, and in fact it’s the same as the f we started with.

December 3, 2010 Posted by | Algebra, Group theory, Representation Theory | 2 Comments

Induction and Restriction are Additive Functors

Before we can prove the full version of Frobenius reciprocity, we need to see that induction and restriction are actually additive functors.

First of all, functoriality of restriction is easy. Any intertwinor f:V\to W between G-modules is immediately an intertwinor between the restrictions V\!\!\downarrow^G_H and W\!\!\downarrow^G_H. Indeed, all it has to do is commute with the action of each h\in H\subseteq G on the exact same spaces.

Functoriality of induction is similarly easy. If we have an intertwinor f:V\to W between H-modules, we need to come up with one between \mathbb{C}[G]\otimes_HV and \mathbb{C}[G]\otimes_HW. But the tensor product is a functor on each variable, so it’s straightforward to come up with 1_{\mathbb{C}[G]}\otimes f. The catch is that since we’re taking the tensor product over H in the middle, we have to worry about this map being well-defined. The tensor s\otimes v\in\mathbb{C}[G]\otimes V is equivalent to sh^{-1}\otimes hv. The first gets sent to s\otimes f(v), while the second gets sent to sh^{-1}\otimes f(hv)=sh^{-1}\otimes hf(v). But these are equivalent in \mathbb{C}[G]\otimes_HW, so the map is well-defined.

Next: additivity of restriction. If V and W are G-modules, then so is V\oplus W. The restriction (V\oplus W)\!\!\downarrow^G_H is just the restriction of this direct sum to H, which is clearly the direct sum of the restrictions V\!\!\downarrow^G_H\oplus W\!\!\downarrow^G_H.

Finally we must check that induction is additive. Here, the induced matrices will come in handy. If X and Y are matrix representations of H, then the direct sum is the matrix representation

\displaystyle\left[X\oplus Y\right](h)=\left(\begin{array}{cc}X(h)&0\\{0}&Y(h)\end{array}\right)

And then the induced matrix looks like:

\displaystyle \left[X\oplus Y\right]\!\!\uparrow_H^G(g)=\left(\begin{array}{ccccccc}X(t_1^{-1}gt_1)&0&X(t_1^{-1}gt_2)&0&\cdots&X(t_1^{-1}gt_n)&0\\{0}&Y(t_1^{-1}gt_1)&0&Y(t_1^{-1}gt_2)&\cdots&0&Y(t_1^{-1}gt_n)\\X(t_2^{-1}gt_1)&0&X(t_2^{-1}gt_2)&0&\cdots&X(t_2^{-1}gt_n)&0\\{0}&Y(t_2^{-1}gt_1)&0&Y(t_2^{-1}gt_2)&\cdots&0&Y(t_2^{-1}gt_n)\\\vdots&\vdots&\vdots&\vdots&\ddots&\vdots&\vdots\\X(t_n^{-1}gt_1)&0&X(t_n^{-1}gt_2)&0&\cdots&X(t_n^{-1}gt_n)&0\\{0}&Y(t_n^{-1}gt_1)&0&Y(t_n^{-1}gt_2)&\cdots&0&Y(t_n^{-1}gt_n)\end{array}\right)

Now, it’s not hard to see that we can rearrange the basis to make the matrix look like this:

\displaystyle\left(\begin{array}{cc}\begin{array}{cccc}X(t_1^{-1}gt_1)&X(t_1^{-1}gt_2)&\cdots&X(t_1^{-1}gt_n)\\X(t_2^{-1}gt_1)&X(t_2^{-1}gt_2)&\cdots&X(t_2^{-1}gt_n)\\\vdots&\vdots&\ddots&\vdots\\X(t_n^{-1}gt_1)&X(t_n^{-1}gt_2)&\cdots&X(t_n^{-1}gt_n)\end{array}&0\\{0}&\begin{array}{cccc}Y(t_1^{-1}gt_1)&Y(t_1^{-1}gt_2)&\cdots&Y(t_1^{-1}gt_n)\\Y(t_2^{-1}gt_1)&Y(t_2^{-1}gt_2)&\cdots&Y(t_2^{-1}gt_n)\\\vdots&\vdots&\ddots&\vdots\\Y(t_n^{-1}gt_1)&Y(t_n^{-1}gt_2)&\cdots&Y(t_n^{-1}gt_n)\end{array}\end{array}\right)

There’s no complicated mixing up of basis elements amongst each other; just rearranging their order is enough. And this is just the direct sum X\!\!\uparrow_H^G\oplus Y\!\!\uparrow_H^G.

December 1, 2010 Posted by | Algebra, Group theory, Representation Theory | 1 Comment

(Fake) Frobenius Reciprocity

Today, we can prove the Frobenius’ reciprocity formula, which relates induced characters to restricted ones.

Now, naïvely we might hope that induction and restriction would be inverse processes. But this is clearly impossible, since if we start with a G-module V with dimension d, it restricts to an H-module V\!\!\downarrow^G_H which also has dimension d. Then we can induce it to a G-module V\!\!\downarrow^G_H\uparrow_H^G with dimension d\tfrac{\lvert G\rvert}{\lvert H\rvert}. This can’t be the original representation unless H=G, which is a pretty trivial example indeed.

So, instead we have the following “reciprocity” relation. If \chi is a character of the group G and \psi is a character of the subgroup H, we find that

\displaystyle\langle\chi\!\!\downarrow^G_H,\psi\rangle_H=\langle\chi,\psi\!\!\uparrow_H^G\rangle_G

Where the left inner product is that of class functions on H, while the right is that of class functions on G. We calculate the inner products using our formula

\displaystyle\begin{aligned}\langle\chi,\psi\!\!\uparrow_H^G\rangle_G&=\frac{1}{\lvert G\rvert}\sum\limits_{g\in G}\chi(g^{-1})\psi\!\!\uparrow_H^G(g)\\&=\frac{1}{\lvert G\rvert}\frac{1}{\lvert H\rvert}\sum\limits_{g\in G}\sum\limits_{x\in G}\chi(g^{-1})\psi(x^{-1}gx)\\&=\frac{1}{\lvert G\rvert}\frac{1}{\lvert H\rvert}\sum\limits_{x\in G}\sum\limits_{y\in G}\chi(xy^{-1}x^{-1})\psi(y)\\&=\frac{1}{\lvert G\rvert}\frac{1}{\lvert H\rvert}\sum\limits_{x\in G}\sum\limits_{y\in G}\chi(y^{-1})\psi(y)\\&=\frac{1}{\lvert H\rvert}\sum\limits_{y\in G}\chi(y^{-1})\psi(y)\\&=\frac{1}{\lvert H\rvert}\sum\limits_{y\in H}\chi(y^{-1})\psi(y)\\&=\frac{1}{\lvert H\rvert}\sum\limits_{y\in H}\chi\!\!\downarrow^G_H(y^{-1})\psi(y)\\&=\langle\chi\!\!\downarrow^G_H,\psi\rangle_H\end{aligned}

where we have also used the fact that \chi is a class function on G, and that \psi is defined to be zero away from H.

As a special case, let \chi^{(i)} and \chi^{(j)} be irreducible characters of G and H respectively, so the inner products are multiplicities. For example,

\displaystyle\langle\chi^{(i)},\chi^{(j)}\!\!\uparrow_H^G\rangle_G=m_1

is the multiplicity of \chi^{(i)} in the representation obtained by inducing \chi^{(j)} to a representation of G. On the other hand,

\displaystyle\langle\chi^{(i)}\!\!\downarrow^G_H,\chi^{(j)}\rangle_H=\overline{\langle\chi^{(j)},\chi^{(i)}\!\!\downarrow^G_H\rangle_H}=\overline{m_2}=m_2

is the multiplicity of \chi^{(j)} in the representation obtained by restricting \chi^{(i)} down to H. The Frobenius reciprocity theorem asserts that these multiplicities are identical.

Now, why did I call this post “fake” Frobenius reciprocity? Well, this formula gets a lot of press. But really it’s a pale shadow of the real Frobenius reciprocity theorem. This one is a simple equation that holds at the level of characters, while the real one is a natural isomorphism that holds at the level of representations themselves.

November 30, 2010 Posted by | Algebra, Group theory, Representation Theory | 3 Comments

« Previous Entries