Math 202C: Lecture 0

This post serves as the syllabus for Math 202C.

DATETOPICModality
March 30Graphs and operatorsIn-person lecture
April 1Cayley graphsIn-person lecture
April 3Level operators on Cayley graphsAsynchronous lecture post
April 6Jucys-Murphy elementsIn-person lecture
April 8Symmetric polynomialsIn-person lecture
April 10The JM algebraIn-person lecture
April 13
April 15
April 17
April 20
April 22
April 24
April 27
April 29
May 1
May 4
May 6
May 8
May 11
May 13
May 15
May 18
May 20
May 22
May 27
May 29
June 1
June 3
June 5
Schedule subject to change

Math 202C: Lecture 3

*** All problems in this lecture due April 12 at 23:59 ***

We return to the general setting of a finite, connected, simple graph G=\mathrm{Cay}(S,T), and as before \mathcal{C}(S) the Hilbert space with orthonormal basis |\pi\rangle, |\rho\rangle,|\sigma\rangle,\dots. In Lecture 1 we introduced the metrics level set linear operators L_0,L_1,L_2,\dots in \mathrm{End}\mathcal{C}(S) which act on vertices according to

L_r|\rho\rangle = \sum\limits_{\substack{\sigma \in S \\ \mathrm{d}(\rho,\sigma)=r}} |\sigma\rangle.

We argued the case that these operators are quite fundamental: L_0=I is the identity operator, L_1=K is the adjacency operator,

D = \sum\limits_{r=0}^\infty rL_r

is the distance operator,

\Omega_q=\sum\limits_{r=0}^\infty q^r L_r

is the exponential distance operator. However, the selfadjoint operators L_0,L_1,L_2,\dots and the subalgebra of \mathrm{End}\mathcal{C}(S) they generate are not easy to understand.

Problem 3.1. Show that \langle \sigma|L_sL_r|\rho\rangle is the cardinality of the intersection of the sphere of radius r centered at \rho with the sphere of radius s centered at \sigma.

So, the matrix elements of the commutator

[L_s,L_r]=L_sL_r - L_rL_s

are differences of intersection numbers,

\langle \sigma | [L_s,L_r] |\rho\rangle = |S_\rho(r) \cap S_\sigma(s)|-|S_\rho(s) \cap S_\rho(r)|,

and if it seems difficult to characterize graphs for which all such differences are zero, that’s because it is. There is one much-studied class of graphs which does have the property that metric level set operators L_0,L_1,L_2,\dots commute.

Problem 3.2. Show that if G is a distance regular graph, then [L_r,L_s]=0.

The following is the only restricted situation in which I personally know a simple combinatorial characterization of commutativity of the metric level set operators (it is likely that an actual graph theorist would know more).

Problem 3.3. Suppose G has diameter 2. Prove that the metric level set operators on G commute if and only if G is a regular graph. (Hint: the basic reason behind this is that in a graph of diameter 2, the metric does not contain any more information than the adjacency relation).

I am torturing you (us, really) with these combinatorial considerations because I want to further hammer home the point that Cayley graphs are much easier to understand than general graphs due to the underlying group structure, which is reflected in the behavior of linear operators acting on the vertices of the graph.

Suppose that S=\{\pi,\rho,\sigma,\dots\} is a finite group, so that \mathcal{C}(S) is the convolution algebra of this group. For any arbitrary subset A \subseteq S, we write

|A\rangle=\sum\limits_{\pi \in A}|\pi\rangle,

which is simply the indicator function of the set A. It is a very convenient abuse of notation to also simply write A for the image of |A\rangle in the right regular representation, i.e. we identity the set A \subseteq S with the operator A \in \mathrm{End}\mathcal{C}(S) defined by

A|\rho\rangle = |\rho\rangle|A\rangle=\sum\limits_{\pi \in A} |\rho\pi\rangle.

Recall from Math 202B that we have a tracial state

\langle \cdot \rangle \colon \mathcal{C}(S) \longrightarrow \mathbb{C}

on the convolution algebra of S defined by

\langle A \rangle := \langle \iota |A\rangle,

where \iota \in S is the group identity. In other words, \langle A \rangle is the coefficient of the vector |A\rangle in the group basis |\pi\rangle, which is the same thing as the value of the function A at the point \pi=\iota. Here is a second under-appreciated characterization of this important functional, which is often referred to as the canonical group trace.

Problem 3.4. Prove that all diagonal matrix elements \langle \pi | A |\pi\rangle of the image A \in \mathrm{End}\mathcal{C}(S) of |A\rangle\in \mathcal{C}(S) in the regular representation are equal to the same number, and that that number is \langle A \rangle. Hence conclude (as was already shown in Math 202B) that the \langle A \rangle =\frac{1}{|S|}\mathrm{Tr} A.

Now to Cayley graphs. We continue with a finite group S and select inside it a symmetric set of generators T, giving us the Cayley graph G = \mathrm{Cay}(S,T). As discussed above, we may also view T \in \mathrm{End}\mathcal{C}(S) as the adjacency operator on G.

Problem 3.5. Show that \langle T^r\rangle is the number of length r loops based at the identity element (or any other specified point) in S.

Now specialize to the case where S=\mathrm{Aut}\{1,\dots,n\} is the symmetric group and T is the full conjugacy class of transpositions. The metric level set operators L_0,L_1,L_2,\dots \in \mathrm{End}\mathcal{C}(S) commute for a very simple reason: they are the images of the vectors

|L_r \rangle = \sum\limits_{\substack{\pi \in S \\ |\pi|=r}} |\pi\rangle, \quad r=0,1,2,\dots,

and these vectors lie in the center of the convolution algebra \mathcal{C}(S). Indeed, the center of \mathcal{C}(S) is spanned by the conjugacy classes

|C_\alpha\rangle = \sum\limits_{\pi \in C_\alpha} |\pi\rangle, \quad \alpha \in \Lambda,

and

|L_r\rangle = \sum\limits_{\substack{\alpha \vdash n \\ \ell(\alpha)=n-r}} |C_\alpha\rangle

is simply the sum of all conjugacy classes corresponding to partitions of n with n-r parts.

The fact that the level set operators L_0,L_1,L_2,\dots on a graph G commute is equivalent to saying that they are simultaneously diagonalizable. However, in the group-theoretic setting this statement can be refined. Let us stick with the case where S=\mathrm{Aut}\{1,\dots,n\} is the symmetric group, noting that what follows is true for the Cayley graph G=\mathrm{Cay}(S,T) of any finite group S with generating set T \subseteq S such that |T\rangle is a central element in the convolution algebra \mathcal{C}(S). Let \Lambda be a set indexing the conjugacy classes in S, so for the symmetric group \Lambda is the set of partitions of n. Then \Lambda also indexes isomorphism classes of irreducible unitary representations of S, or equivalently irreducible linear representations of \mathcal{C}(S). For each \lambda \in \Lambda, choose a representative (V^\lambda,\Phi^\lambda) of the corresponding isomorphism class. By Schur’s Lemma, any central element |A\rangle \in \mathcal{C}(S) acts in each irrep (V^\lambda,\Phi^\lambda) as a scalar operator: we have

\Phi^\lambda|A\rangle = \widehat{A}(\lambda) I_{V^\lambda}, \quad \widehat{A}(\lambda) \in \mathbb{C}.

Let us apply this to the adjacency operator on the all-transpositions Cayley graph G=\mathrm{Cay}(S,T) of the symmetric group, which is the image of the central element

|T\rangle = \sum\limits_{\tau \in T} |\tau\rangle= \sum\limits_{1 \leq s<t \leq n} |s\ t\rangle.

The eigenvalues of the adjacency operator T \in \mathrm{End}\mathcal{C}(S) are the numbers

\widehat{T}(\lambda) = {n \choose 2} \frac{\chi^\lambda(\tau)}{\dim V^\lambda}, \quad \lambda \in \Lambda,

where \tau \in T is any transposition. Moreover, where the multiplicity of \widehat{T}(\lambda) is (\dim V^\lambda)^2 because the isotypic decomposition of the regular representation is

\mathcal{C}(S) = \bigoplus\limits_{\lambda \in \Lambda} (\dim V^\lambda)V^\lambda.

Thus, in a sense, we completely know the spectrum of the adjacency operator on the all-transpositions Cayley graph of the symmetric group. However, to actually compute these numbers explicitly, we need to know both the dimension

\dim V^\lambda = \chi^\lambda(\iota) = \mathrm{Tr}\varphi^\lambda(\iota)

of every irreducible unitary representation (V^\lambda,\varphi^\lambda) of S, as well as the character

\chi^\lambda(\tau) = \mathrm{Tr} \varphi^\lambda(\tau)

of a transposition in each representation.

This highlights the fact that we really only know the irreducible unitary representations (V^\lambda,\varphi^\lambda) of S=\mathrm{Aut}\{1,\dots,n\} abstractly. In particular, while we know that the irreducible representations of S are (up to isomorphism) in bijection with the conjugacy classes in S, we have not explicitly selected such a bijection and it is not at all clear how best to do so.

Nevertheless, there are a few things we can say concretely at this stage. First, as with every group, S has the trivial representation (V^\mathsf{triv},\varphi^\mathsf{triv}) in which V^\mathsf{triv} is a one-dimensional Hilbert space and \varphi^\mathsf{triv} sends every \sigma \in S to the identity operator on this space. For this representation, we have

\widehat{T}^\mathsf{triv}={n \choose 2} \frac{\chi^\mathsf{triv}(\tau)}{\dim V^\mathsf{triv}}= {n \choose 2},

and we have reproduced the fact that the degree of the regular graph G=\mathrm{Cay}(S,T) is an eigenvalue of its adjacency operator.

Second, the symmetric group S has a second one-dimensional representation (V^\mathsf{alt},\varphi^\mathsf{alt}) in which

\varphi^\mathsf{alt} = (-1)^{|\sigma|}I.

This gives the eigenvalue

\widehat{T}^\mathsf{alt}={n \choose 2} \frac{\chi^\mathsf{alt}(\tau)}{\dim V^\mathsf{alt}}=- {n \choose 2},

which could also be deduced from the fact that the spectrum of the adjacency operator on a bipartite graph is symmetric about zero.

We can compute a third eigenvalue of the adjacency operator on the all-transpositions Cayley graph which is not directly accessible without representation-theoretic methods. To do so, we start with the permutation representation (V^\mathsf{perm},\varphi^\mathsf{perm}), in which V is the Hilbert space with orthonormal basis |1\rangle,\dots,|n\rangle and \varphi^\mathrm{perm}(\sigma)|i\rangle=|\sigma(i)\rangle. The character of this representation is

\chi^\mathsf{perm}(\sigma) = \sum\limits_{i=1}^n \langle i | \varphi^\mathsf{perm}(\sigma) | i\rangle = \sum\limits_{i=1}^n \langle i|\sigma(i)\rangle=\mathsf{fix}(\sigma),

the number of fixed points of the permutation \sigma. However, the permutation representation is not irreducible, as it has a one-dimensional invariant subspace spanned by the vector

|w\rangle = |1\rangle + \dots + |n\rangle.

The orthogonal complement of this vector gives an (n-1)-dimensional representation (V^\mathsf{std},\varphi^\mathsf{std}) of S called the standard representation, whose character satisfies

\chi^\mathsf{std}+\chi^\mathsf{triv}=\chi^\mathsf{perm}

and is therefore given by

\chi^\mathsf{std}(\sigma)=\mathsf{fix}(\sigma)-1.

Problem 3.6. Prove that the standard representation of S=\mathrm{Aut}\{1,\dots,n\} is irreducible, and give a third eigenvalue of the adjacency operator on the all-transpositions Cayley graph G=\mathrm{Cay}(S,T).

Math 202C: Lecture 2

*** Problems in this lecture due April 10 at 23:59 ***

In this lecture, we remain in the setting of the symmetric group S=\mathrm{Aut}\{1,\dots,n\} but we will change the geometry on this group. More precisely, instead of identifying S with its Cayley graph as generated by the set of adjacent transpositions, we will identify the symmetric group with its Cayley graph as generated by the full conjugacy class of transpositions,

T = \{(s\ t) \in S \colon 1 \leq s < t \leq n\}.

Let \mathrm{d} denote the corresponding metric on S, so that \mathrm{d}(\rho,\sigma) is the minimal number r such that there exist transpositions \tau_1,\dots,\tau_r \in T with

\sigma = \rho\tau_1 \dots \tau_r.

As before, write |\pi|=\mathrm{d}(\iota,\pi) for the distance from the identity permutation \iota to a given permutation \pi.

Problem 2.1. Prove that |\pi|=n-\mathrm{cyc}(\pi), where \mathrm{cyc}(\pi) is the number of factors in the disjoint cycle decomposition of \pi.

Identifying S with \mathrm{Cay}(S,T), the symmetric group becomes a graded graph: it decomposes into a disjoint union

S = L_0 \sqcup L_1 \sqcup \dots \sqcup L_{n-1}

in which

L_r = \{\pi \in S \colon |\pi|=r\} = \{\pi \in S \colon \mathsf{cyc}(\pi)=n-r\}

is the sphere of radius r centered at \iota, and L_r is an independent set, meaning that no two of its points are adjacent vertices. Moreover, if \rho,\sigma \in S are adjacent vertices, then we have \rho \in L_r and \sigma \in L_s with |r-s|=1. The decomposition of a group into concentric spheres is a general thing that happens whenever one chooses a generating set; a special feature of this particular situation is that each sphere further decomposes into a disjoint union of conjugacy classes,

L_r = \bigsqcup\limits_{\substack{\alpha \vdash n \\ \ell(\alpha)=n-r}}C_\alpha.

Here, we are indexing the conjugacy classes of S by the set \Lambda of partitions of n. More precisely, the notation \alpha \vdash n means that \alpha is a decomposition of n into a sum of \ell(\alpha) positive integers, without regard to order of the terms. Every permutation \pi \in S gives a partition \mathsf{type}(\pi)\vdash n obtained from the lengths of the cycles in its disjoint cycle decomposition; conversely, for any partition \alpha \vdash n the corresponding fiber C_\alpha =\mathsf{type}^{-1}(\alpha) is a conjugacy class in S.

Let us now construct the analogue of Mallows measure corresponding to the all-transpositions geometry. This is called the Ewens measure on permutations: by definition, it is the Gibbs measure

\mathbb{P}(\sigma) = \frac{q^|\sigma|}{Z} = \frac{q^{n-\mathsf{cyc}(\sigma)}}{Z}

corresponding to a statistical mechanical system whose states \sigma are permutations of 1,\dots,n with the potential energy of \sigma being inversely proportional to its number of cycles. The partition function is

Z= \sum\limits_{\sigma \in S} q^{|\sigma|} = q^n\sum\limits_{\sigma \in S} q^{-\mathsf{cyc}(\sigma)},

or equivalently

Z=\sum\limits_{k=0}^n \begin{bmatrix} n \\ k \end{bmatrix} q^{-k},

where \begin{bmatrix} n \\ k \end{bmatrix} is the Stirling number of the first kind, which counts permutations in S=\mathrm{Aut}\{1,\dots,n\} whose disjoint cycle factorization has k components. This in turn gives

Z= (1+q)(1+2q) \dots (1+(n-1)q),

corresponding to the fact that Stirling Numbers of the first kind are the coefficients of the falling factorial polynomial.

Problem 2.2. Show that the expected number of cycles in a random permutation under Ewens measure is

1 + \sum\limits_{j=1}^{n-1} \frac{1}{1+jq}.

Deduce from this that the expected number of cycles in a uniformly random permutation of 1,\dots,n is the harmonic number

H_n=1+\frac{1}{2} + \dots + \frac{1}{n}.

The all-transpositions geometry on permutations has many features which make it easier to understand than the adjacent-transpositions geometry. Perhaps the most significant of these is that it is “Euclideanizable.” Right, that’s not a real word – here is what is meant more precisely.

Consider the full forward cycle \gamma=(1\ 2\ \dots\ n) in the symmetric group S. In the all-transpositions geometry, we have |\gamma|=n-1, and the number of geodesics \iota \to \gamma is \mathrm{Cay}_{n-1}, where

\mathrm{Cay}_n = (n+1)^{n-1}

is the nth Cayley number. Taking this formula for granted, we can calculate the number of geodesics from the identity to any permutation (hence the number of geodesics between any two permutations) as follows.

Problem 2.3. Let \pi be any permutation in the conjugacy class C_\alpha of S. Show that the number of geodesics \iota \to \pi is

{n \choose \alpha_1-1,\dots,\alpha_\ell-1} \prod\limits_{k=1}^\ell \mathrm{Cay}_{\alpha_k-1},

where \ell=\ell(\alpha).

To Euclideanize the all-transpositions geometry on the symmetric group, we give a rule which allows one to systematically select a distinguished geodesic between every pair of points. To do so, let us label the edges of \mathrm{Cay}(S,T) as follows: we mark each edge corresponding to the transposition (s\ t) with t, the larger of the two numbers swapped. Thus, emanating from every vertex of the graph we have one 2-edge, two 3-edges, three 4-edges, etc. Call a walk on the Cayley graph strictly monotone if the labels of the edges it traverses form a strictly increasing sequence. Thus, an r-step strictly monotone walk \rho \to \sigma corresponds to an equation of the form

\sigma=\rho(s_1\ t_1) \dots (s_r\ t_r), \quad 2\leq t_1 < \dots < t_r \leq n

in S.

Problem 2.4. Prove that for any \pi \in S, there exists a unique strictly monotone walk \iota \to \pi, and that the length of this walk is |\pi|. Conclude that there exists a unique strictly monotone walk between every pair of points in S, and that this walk is a geodesic.

This more or less marks the end of my efforts to get you thinking about the combinatorics of permutations; after this we will move on to the algebraic aspects of the symmetric group and its representations. The campaign for the elementary beauty and unexpected subtlety of permutations met with mixed success: there were interesting follow-up discussions with some students, whereas other pairs of eyes glazed over as the minds behind them fell into the “I already know this stuff” trap, which is one the of the more pernicious lies you can tell yourself.

Here is one final push. Our ever-curious Lani was recently asking about posets, and whether there is any active research being conducted on them these days. The answer is definitely “yes,” and though I don’t really work in the area I do have one burning question about posets which keeps me up at night. The question is about finding a partial order on permutations of a fixed genus.

From our Euclideanized perspective, genus is a metric invariant which measures “flatness” of triangles S as generated by the full conjugacy class of transpositions. More precisely, let \pi,\rho,\sigma be three distinct permutations in S=\mathrm{Aut}\{1,\dots,n\}. There are two oriented strictly monotone triangles formed by these three points, namely \rho \to \pi \to \sigma \to \rho and \sigma \to \pi \to \rho \to \sigma. It may happen \pi lies on a geodesic \rho \to \sigma, in which case both of these triangles are flat, and have perimeter

|\pi^{-1}\rho| + |\rho^{-1}\sigma| + |\sigma^{-1}\pi| = 2|\rho^{-1}\sigma|.

In general, the oriented triangle \rho \to \pi \to \sigma \to \rho is a cycle in a bipartite graph, so necessarily has even perimeter: we have

|\pi^{-1}\rho| + |\rho^{-1}\sigma| + |\sigma^{-1}\pi| = 2|\rho^{-1}\sigma| + 2g(\rho,\pi,\sigma)

for some nonnegative integer g(\rho,\pi,\sigma) which we call the genus of the triple (\rho,\pi,\sigma). At the other extreme from flatness, it may be that \pi,\rho,\sigma are pairwise antipodal points, i.e. the distance between each pair of them is the diameter of S, in which case the above equation becomes

3(n-1)=2(n-1)+2g(\rho,\pi,\sigma),

giving a maximal genus of

g(\pi,\rho,\sigma) = \lfloor \frac{n-1}{2} \rfloor.

Problem 2.5. Show that a triple of pairwise antipodal points in S exists if and only if n is odd.

Since

g(\rho,\pi,\sigma)=g(\iota,\rho^{-1}\pi,\rho^{-1}\sigma),

it is natural to view genus as a function g(\pi,\sigma):=g(\iota,\pi,\sigma) on pairs of permutations. Going even further, let us fix the second argument to be \sigma=\gamma, where \gamma=(1\ 2\ \dots\ n) is the full forward cycle, and define the genus of a permutation by g(\pi):=g(\pi,\gamma). Then, we obtain a corresponding decomposition of the symmetric group

S = \bigsqcup\limits_{k=0}^{\lfloor \frac{n-1}{2} \rfloor} S_g

in which S_g is the set of permutations of genus g. The set S_0 of “planar” permutations consists precisely of those \pi which lie on a geodesic \iota \to \gamma, and these permutations have a special feature: the disjoint cycle decomposition of any \pi \in S_0 is a noncrossing partition of \{1,\dots,n\}, and in fact this map from genus zero permutations into noncrossing permutations is bijective. There is also a very natural partial order on S_0 which can be described as follows: we have \pi \leq \sigma if and only if \pi and \sigma lie on a common geodesic \iota \to \gamma, and a particle emanating from \iota and traveling along this geodesic passes through \pi before passing through \sigma. This is a special case of the geodesic partial order which can be defined relative to any two vertices of a connected graph, and in this case it coincides exactly with the reverse refinement order on noncrossing partitions.

Now the question is: what is the higher genus analogue of this partial order? How can we define a poset structure by some uniform recipe which feels good for all values of g, subject to the condition that our recipe reverts to the above at g=0? This is an open question. The most natural thing that I can think of is the following: given two permutations \pi,\sigma \in S_g, we declare \pi \leq \sigma if and only if they lie on a common genus g triangle two of whose vertices are \iota and \gamma, and a particle emanating from \iota and traveling along the perimeter of this triangle encounters \pi before encountering \sigma. Whether or not this actually defines a partial order on S_g is not clear to me, but my fluid intelligence is declining from its peak while yours is cresting. So, if you want to discuss further please feel free to get in touch.

Math 202B: Revenge of the Centralizer

Yesterday during office hours I had the unsettling experience of being shown that something I assumed to be true is, in fact, subtly incorrect. That’s what happens when you take things for granite. My sloppy thinking was pointed out to me by Amelia and Eliza in the context of the following problem which appeared on the Math 202B Exam: prove that if \mathcal{B} is a maximal abelian subalgebra of an algebra \mathcal{A}, then the centralizer Z(\mathcal{B},\mathcal{A}) of \mathcal{B} in \mathcal{A} equals \mathcal{B}.

This was supposed to be easy. Since \mathcal{B} is abelian, it is certainly contained in its centralizer Z(\mathcal{B},\mathcal{A}). Now, if the containment is proper, then there exists an element C \in Z(\mathcal{B},\mathcal{A}) which does not lie in \mathcal{B}. Then,

\mathcal{C}=\mathrm{CAlg}(\mathcal{B} \sqcup \{C\}),

the commutative algebra generated by \mathcal{B} with C adjoined, is a commutative algebra properly containing \mathcal{B}, contradicting the fact that \mathcal{B} is a MASA.

The subtle issue here is that \mathcal{C} is by definition the intersection of all commutative subalgebras of \mathcal{A} containing the set \mathcal{B} \sqcup \{C\}, and this could conceivably be empty. To be concrete, imagine a single non-normal matrix C. There is no commutative subalgebra of the full matrix algebra containing C, since our definition of “algebra” requires *-closure, and by hypothesis C does not commute with its adjoint.

Luckily, our attempted solution can be salvaged: as Evan immediately recognized, if we can show that Z(\mathcal{B},\mathcal{A}) contains a *selfadjoint* element D not contained in \mathcal{B} this issue goes away. This is the case, since we can take D to be either the real or imaginary part of C — at least one of these does not lie in \mathcal{B}, since if they both did so would C.

Hopefully I’m now getting this right, and my apologies for being such a bad professor. Try reading some of my papers, I swear they’re really good.

In any case, we will have to incorporate this correction into our census of reality. In particular, if this problem were to appear on the qual, a proposed solution which did not address this issue would no longer pass muster. Live and learn.

Math 202C: Lecture 1

***Problems in this lecture due 23:59 on April 8***

Let G=(S,T) be a finite, connected, simple graph with vertex set S=\{\pi,\rho,\sigma,\dots\} and edge set T \subseteq {S \choose 2}. A basic (meaning fundamental, not necessarily easy) problem is to compute the number W^r(\rho,\sigma) of r-step walks from \rho to \sigma in G.

Problem 1.1. Let G be the complete graph on S=\{1,\dots,N\}, whose vertex set is T={S \choose 2}. Using nothing but your brain, find a formula for W^r(\rho,\sigma). If you find this problem intractable or, worse, uninteresting, consider a degree in law or medicine.

Math 202A provides an algebraic encoding of graphs. Let \mathcal{C}(S) be the Hilbert space with orthonormal basis |\rho\rangle,|\pi\rangle,|\sigma\rangle,\dots. Let \langle \rho|,\langle \pi|,\langle \sigma|,\dots be the dual basis of \mathrm{Hom}(\mathcal{C}(S),\mathbb{C}), so that

\langle \rho | \sigma \rangle = \langle \rho,\sigma \rangle = \delta_{\rho\sigma}.

Does using Dirac notation make this an applied math course? The question is vacuous since there is no such thing as non-applied math, but there are cultural differences between fields which are reflected in their iconography, and hopefully you can at least read a paper in quantum computing at the end of this sequence.

The adjacency operator K\in \mathrm{End}\mathcal{C}(S) acts on the vertex basis of \mathcal{C}(S) by creating a flat superposition of all vertices adjacent to a given input,

K|\rho\rangle = \sum\limits_{\substack{\sigma \in S \\ \{\rho,\sigma\} \in T}} |\sigma\rangle.

Equivalently, the matrix elements of K in the vertex basis are

\langle \sigma | K |\rho\rangle=\begin{cases} 1, \text{ if } \{\rho,\sigma\} \in T\\ 0, \text{ if } \{\rho,\sigma\} \not\in T\end{cases}.

Thus, the selfadjoint operator K \in \mathrm{End}\mathcal{C}(S) encodes the edge set T \subseteq {S\choose 2}.

For example, consider the complete graph G=(S,T) on the vertex set S=\{1,\dots,N\}. The computational basis in \mathcal{C}(S) consists of the vectors

|1\rangle, |2\rangle,\dots,|N\rangle,

upon which A acts according to

K| i\rangle = \sum\limits_{j \neq i} |j\rangle.

Problem 1.2. Show that W^r(\rho,\sigma) = \langle \rho| K^r|\sigma\rangle. In particular, show that the trace of K^r equals the total number of loops (i.e. closed walks) of length r in G.

The linear algebra approach to counting walks in graphs is to find a basis of \mathcal{C}(G) on which K acts diagonally.

Problem 1.3. Implement this approach for the complete graph and recover your barehands solution to Problem 1.1.

The mathematical subject which uses eigenvalues of linear operators to analyze graphs is called spectral graph theory. In particular, the spectrum of the adjacency operator K on a given graph G=(S,T) is called the adjacency spectrum of G. A couple of facts worth mentioning: if G is bipartite then the spectrum of K is symmetric about 0; if G is degree-regular then the largest eigenvalue of K is the degree of any vertex.

Instead of asking how many walks there are between two given vertices, we may ask how far apart they are. This information is encoded in the distance operator D \in \mathrm{End}\mathcal{C}(S), whose matrix elements in the vertex basis tabulate geodesic distance in G,

\langle \sigma | D | \rho\rangle = \mathrm{d}(\rho,\sigma).

Ron Graham made the striking discovery that the determinant of the distance operator on a tree depends only on the cardinality of its vertex set. Distance eigenvalues of graphs have been much studied ever since. I found some recent interesting work on distance operators via Johann Birnick’s website; Johann is the TA for this course.

One can in a sense interpolate between K and D. To do so, we consider operators L_0,L_1,L_2,\dots \in \mathcal{C}(S) corresponding to metric level sets in G=(S,T), meaning that

\langle \sigma | L_r |\rho \rangle = \begin{cases} 1, \text{ if }\mathrm{d}(\rho,\sigma)=r \\ 0, \text{ otherwise}\end{cases}.

Equivalently,

L_r|\rho\rangle = \sum\limits_{\substack{\sigma \in S \\ \mathrm{d}(\rho,\sigma)=r}} |\sigma\rangle

is the sum of all points on the sphere of radius r centered at \rho. We have that L_0=I is the identity operator, L_1 = K is the adjacency operator, and

D=\sum\limits_{r=0}^\infty rL_r.

This is in fact a finite sum, since L_r is the zero operator for all r exceeding the diameter of G.

One can also consider the exponential adjacency operator

\Psi_t= \sum\limits_{r=0}^\infty \frac{t^r}{r!} K^r =: e^{tK}

on G, whose matrix elements are exponential generating functions enumerating walks between vertices by length,

\langle \sigma | \Psi_t |\rho \rangle = \sum\limits_{r=0}^\infty \frac{t^r}{r!} W^r(\rho,\sigma).

For regular graphs this is essentially the heat kernel, which has been much studied. The exponential distance operator,

\Omega_q = \sum\limits_{r=0}^\infty q^r L_r,

is the element-wise exponential of the distance operator,

\langle \sigma | \Omega_q |\rho\rangle= q^{\mathrm{d}(\rho,\sigma)},

and unlike \Psi_t it is a relative newcomer in spectral graph theory.

Looking at the power series which define \Psi_t and \Omega_q, one sees that the level set operators L_0,L_1,L_2,\dots are to \Omega_q as powers K^0,K^1,K^2,\dots of the adjacency operator are to \Psi_t. While the first two elements of these sequences are the same, a big flaw in this symbolic analogy is that the subalgebra of \mathrm{End}\mathcal{C}(S) generated by the (finite) set of selfadjoint operators \{L_0,L_1,L_2,\dots\} is highly non-trivial, whereas the subalgebra of \mathrm{End}\mathcal{C}(S) generated by the single selfadjoint operator K simply consists of polynomials in this operator, which is but a small sector of \mathrm{Alg}(L_0,L_1,L_2,L_3,\dots). In particular, it is not at all clear what relations exist between L_r and L_s, or even whether they commute. We will have more to say about this later.

The exponential distance operator \Omega_q encodes the same information as the distance operator D in a manner which interfaces more readily with the formalism of statistical mechanics. More precisely, let us write q=e^{-\beta} so that

\langle \sigma | \Omega_q | \rho \rangle = e^{-\beta \mathrm{d}(\rho,\sigma)}.

Then, fixing a root vertex \rho, the \rhoth row of \Omega_q defines Gibbs measure (after Josiah, not Amelia) on the vertices of G according to

\mathbb{P}(\sigma) = \frac{1}{Z}e^{-\beta |\sigma|}.

Physically, this distribution corresponds to a thermodynamic ensemble whose states are the vertices of G, with \beta>0 the inverse temperature and the potential energy |\sigma| of a state \sigma being equal to its distance |\sigma|:=\mathrm{d}(\rho,\sigma) to the root vertex \rho in G. The partition function

Z= \sum\limits_\sigma q^{|\sigma|} = \sum\limits_{\sigma} e^{-\beta\mathrm{d}(\rho,\sigma)}

sums the energy over all states, ensuring that \mathbb{P} is a probability measure on S. Its logarithm \log Z is the free energy of our ensemble, and

q \frac{\partial}{\partial q} \log Z = \frac{1}{Z} \sum\limits_{\sigma} |\sigma|q^{|\sigma|}=\sum\limits_\sigma |\sigma| \mathbb{P}(\sigma)

is precisely the average distance to the root vertex \rho under the non-uniform distribution \mathbb{P}, which becomes the uniform distribution on states in the high-temperature limit \beta \to 0 limit, where q=e^{-\beta} \to 1.

Let us try this out on a toy example, the complete graph G=(S,T) on S=\{1,\dots,N\}. Take the root vertex to be 1, so that the potential energy of any other vertex \sigma \in \{1,\dots,N\} is

|\sigma| = \mathrm{d}(1,\sigma)=1.

Thus, under the corresponding Gibbs measure on states S=\{1,\dots,N\} we have

\mathbb{P}(1) = \frac{1}{Z}

and

\mathbb{P}(\sigma) = \frac{q}{Z}, \quad \sigma \neq 1,

where the partition function is

Z= q^0+q^1+ \dots + q^1 = 1+(N-1)q.

We thus have

q\frac{d}{dq} \log Z = \frac{(N-1)q}{1+(N-1)q},

and setting q=1 we recover the obvious fact that the average distance to 1 under the uniform measure on the complete graph is \frac{N-1}{N}. Indeed, for the uniform measure on the complete graph the random variable \sigma \mapsto |\sigma| has a Bernoulli distribution on \{0,1\} which assigns probability \frac{1}{N} to 0 and probability \frac{N-1}{N} to 1.

Linear operators on graphs fall under the broad umbrella of Math 202A, which treated linear maps between finite-dimensional Hilbert spaces. Math 202B gives us additional algebraic tools which apply to graphs whose vertices form a group; these are officially known as Cayley graphs.

Let S be a finite group and T \subset S a symmetric set of generators in G. Symmetric means that \tau \in T implies \tau^{-1} \in T, and saying that T generates S means that for any \sigma \in S there exists r \in \mathbb{N}_0 and \tau_1,\dots, \tau_r \in T such that \sigma=\tau_1\tau_2 \dots \tau_r. The Cayley graph \mathrm{Cay}(S,T) has vertex set S, with \{\rho,\sigma\} an edge if and only if \sigma = \rho\tau for some \tau \in T, which is then necessarily unique. The fact that T is symmetric means that this is a well-defined as an undirected graph without multiple edges, and the fact that T generates S means that the graph is connected. If T does not contain the identity element \iota then no vertex is adjacent to itself, and we henceforth assume this to be the case. We see that for Cayley graphs G=\mathrm{Cay}(S,T), the edge set can effectively be viewed as a subset of the vertex set, since the generating T \subseteq S determines the adjacency relation on vertices.

For a Cayley graph G=\mathrm{Cay}(S,T), the space \mathcal{C}(S) carries not just a scalar product but also a vector product, namely convolution: we have

|\pi\rangle|\sigma\rangle = |\pi \sigma\rangle, \quad \pi,\sigma \in S,

where \pi\sigma is the group product of \pi and \sigma. This gives us a new point of view on the adjacency operator K on G=\mathrm{Cay}(S,T). For any subset P \subseteq S, let

|P\rangle = \sum\limits_{\pi \in P} |\pi\rangle

be the corresponding element of \mathcal{C}(S). Thus in particular

\langle P|Q\rangle = |P \cap Q|.

Let us allow the following extremely useful abuse of notation: we will also identify P \subset S with its image in the (right) regular representation of \mathcal{C}(S). Thus,

P|\rho \rangle = |\rho\rangle |P\rangle = \sum\limits_{\pi \in P} |\rho\pi\rangle.

In particular, T is both our chosen generating set of S, and also its image in the regular representation is the adjacency operator on \mathrm{Cay}(S,T),

T|\rho\rangle = |\rho\rangle |T\rangle = \sum\limits_{\tau \in T} |\rho\tau\rangle.

More generally, let

L_r = \{ \pi \in S \colon |\pi|=r\} = \{\pi \in S \colon \mathrm{d}(\iota,\pi)=r\}

be the sphere of radius r centered at the identity element. This set becomes a vector in \mathcal{C}(S) via quantization,

|L_r\rangle = \sum\limits_{\pi \in L_r} |\pi\rangle,

and this vector becomes an operator in \mathrm{End}\mathcal{S} via the regular representation,

L_r|\rho\rangle = |\rho\rangle |L_r\rangle = \sum\limits_{|\pi|=r} |\rho\pi\rangle.

The matrix elements of the operator L_r are

\langle \sigma | L_r |\rho \rangle = \sum\limits_{|\pi|=r} \langle \sigma |\rho\pi\rangle,

and

\langle \sigma|\rho\pi\rangle\neq 0 \iff \sigma=\rho\pi \iff \rho^{-1}\sigma=\pi,

in which case

\mathrm{d}(\rho,\sigma)=|\rho^{-1}\sigma|=|\pi|=r.

Thus, the image of |L_r\rangle in the (right) regular representation is indeed the metric level set operator L_r.

To sum up, the adjacency eigenvalues of the Cayley graph \mathrm{Cay}(S,T) are the eigenvalues of |T\rangle \in \mathcal{C}(S) acting in the regular representation of \mathcal{C}(S). This means that the spectral graph theory of Cayley graphs is part of the representation theory of finite groups. If we are in the incredibly fortuitous situation where G is an abelian group, this comes down to using the discrete Fourier transform.

Problem 1.4. Let C be the cyclic group of order n with generator \gamma, and take the symmetric generating set D=\{\gamma,\gamma^{-1}\}. Then \mathrm{Cay}(C,D) is a cycle graph with n vertices. Find a formula for W^r(\rho,\sigma), the number of r-step walks between two given vertices of a cycle graph.

Concerning distance in Cayley graphs \mathrm{Cay}(S,T), we by definition have that \mathrm{d}(\rho,\sigma) is equal to the minimal value of r such that there exist \tau_1,\dots,\tau_r such that

\sigma = \rho\tau_1 \dots \tau_r.

Problem 1.5. Show that for any \pi,\rho,\sigma \in S we have \mathrm{d}(\pi\rho,\pi\sigma)=\mathrm{d}(\rho,\sigma), and explain why the same cannot in general be said for \mathrm{d}(\rho\pi,\sigma\pi). Show that \mathrm{d}(\rho,\sigma) = \mathrm{d}(\iota,\rho^{-1}\sigma) with \iota the group identity.

Now let us consider a nonabelian example: our group is S=\mathrm{Aut}\{1,\dots,n\}, the symmetric group consisting of all bijections \pi \colon \{1,\dots,n\} \to \{1,\dots,n\}, which are generally called permutations. We will take the group law to be \pi\sigma := \sigma \circ \pi, which is the convention used in most computer algebra systems, or so I am told. Take the generating set

T = \{(1\ 2),(2\ 3),\dots,(n-1\ n)\}

of adjacent transpositions.

Problem 1.6. Draw \mathrm{Cay}(S,T) for n=3.

Set |\pi|=\mathrm{d}(\iota,\pi) with \iota the identity permutation.

Now consider the metric Gibbs measure on the Cayley graph \mathrm{Cay}(S,T) of the symmetric group S=\mathrm{Aut}\{1,\dots,n\} corresponding to the generating set T=\{(1\ 2),(2\ 3),\dots,(n-1\ n)\} of adjacent transpositions. We take the root vertex to be \iota, the identity permutation in S. Thus,

\mathbb{P}(\sigma) = \frac{q^{|\sigma|}}{Z},

where |\sigma|=\mathrm{d}(\iota,\sigma) is the minimal number of adjacent transpositions whose produce is \sigma.

Problem 1.7. Show that |\sigma|=\mathsf{inv}(\sigma), where \mathrm{inv}(\sigma) is the cardinality of the set \{1 \leq i<j \leq n\ \colon\ \sigma(i)>\sigma(j)\} of inversions in the permutation \sigma. Hence compute the diameter of G=\mathrm{Cay}(S,T).

We conclude that the metric Gibbs measure on G=\mathrm{Cay}(S,T) is

\mathbb{P}(\sigma)=\frac{1}{Z}q^{\mathsf{inv}(\sigma)}.

This is a famous probability measure on permutations called the Mallows measure; it arises in theoretical computer science in the analysis of sorting algorithms. It is a remarkable fact that the partition function

Z=\sum\limits_{\sigma \in S} q^{|\mathsf{inv}(\sigma)|}.

It is a remarkable fact that this partition function can be evaluated exactly, i.e. this stat mech model is exactly solvable. For any positive integer k, the corresponding q-number is

[k]_q = 1+q+ \dots + q^{k-1},

so that in particular [k]_1=k reverts to an ordinary number at q=1. The q-factorial is accordingly defined as

[k]_q! = [1]_q[2]_q \dots [k]_q.

Here’s a pretty thing.

Theorem 1.1. The partition function for Mallows measure is Z=[n]_q!.

Now you can derive many things, including the following.

Problem 1.8. Find a formula for the expected number of inversions in a random permutation whose distribution is Mallows measure. Using your result, find a formula for the expected number of inversions in a uniformly random permutation.

Math 202B: Lecture 26

We begin by recalling our general algebraic perspective on the discrete Fourier transform (DFT). A Fourier basis of an algebra \mathcal{A} is a basis \{F^\lambda \colon \Lambda\} of pairwise orthogonal selfadjoint idempotents. If such a basis exists, then \mathcal{A} is necessarily commutative. Note also that since we have not mentioned a scalar product on the algebra \mathcal{A}, the orthogonality of the Fourier basis vectors can only refer to the fact that the vector product of two distinct Fourier basis vectors is the zero vector.

There is no guarantee that a given algebra \mathcal{A} admits a Fourier basis, but if it does then every element A \in \mathcal{A} can be expanded on the Fourier basis,

A = \sum\limits_{\lambda \in \Lambda} \widehat{A}(\lambda)F^\lambda,

and the coefficients in this expansion define a function \widehat{A} \in \mathcal{F}(\Lambda). One of our most basic but important theorems from early on in the course is that the map A \mapsto \widehat{A} is an algebra isomorphism \mathcal{A} \to \mathcal{F}(\Lambda). This algebra isomorphism is called the Fourier transform on \mathcal{A}.

The above construction cannot work for noncommutative algebras, in the sense that a noncommutative algebra cannot be isomorphic to a function algebra. We do however have an alternative path to pursue in this case. Instead of looking for a Fourier basis in \mathcal{A}, we look for a Frobenius scalar product on \mathcal{A}. When such a scalar product exists, then \mathcal{A} becomes a Hilbert space in a way which is compatible with its algebra structure. In this case, we have shown that \mathcal{A} is isomorphic not to an algebra of functions on a finite set, but rather to an algebra of operators on a finite-dimensional Hilbert space. More precisely, we have an algebra homomorphism \Phi \colon \mathcal{A} \to \mathrm{End} \mathcal{A} which sends each A \in \mathcal{A} to the corresponding left multiplication operator \Phi(A) \in \mathrm{End}\mathcal{A}. A good name for the homomorphism \Phi would be the Wedderburn transform; the pair (\mathcal{A},\Phi) together is the left-regular representation of \mathcal{A}. The Wedderburn transform is an injective algebra homomorphism, and it replaces the Fourier transform in the sense that it sets up an isomorphism between the abstract algebra \mathcal{A} and the subalgebra of \mathrm{End}\mathcal{A} consisting of left multiplication operators \Phi(A), A \in \mathcal{A}.

Although the above describes the Wedderburn transform as a replacement for the Fourier transform in the noncommutative setting, there is no reason that it cannot be applied in the commutative setting. Namely, the best case scenario is that we have a commutative algebra \mathcal{A} in which we have successfully identified a Fourier basis \{F^\lambda \colon \lambda \in \Lambda\}, and we also are able to identify a Frobenius scalar product on the commutative algebra \mathcal{A}. In this case, both the Fourier transform \mathcal{A} \to \mathcal{F}(\Lambda) and the Wedderburn transform \mathcal{A} \to \mathrm{End}\mathcal{A} are in play. They are moreover related in a very useful way: the Fourier basis \{F^\lambda \colon \lambda \in \Lambda\} is an eigenbasis for the Wedderburn transform \Phi(A) of every A \in \mathcal{A}, and the corresponding eigenvalues are given by the Fourier transform of A,

\Phi(A)F^\lambda = \widehat{A}(\lambda)F^\lambda, \quad \lambda \in \Lambda.

We have concretely implemented this compelling abstract picture in the case where \mathcal{A}=\mathcal{C}(G) is the convolution algebra of a finite abelian group, G. In order to construct a Fourier basis of \mathcal{C}(G), we started from the observation that the set \{\chi^\lambda \colon \lambda \in \Lambda\} of multiplicative characters of G, which is parameterized by an explicit set \Lambda corresponding to the decomposition of G as a product of cyclical groups, forms an orthogonal basis of \mathcal{C}(G). This allows us to define a Fourier basis in \mathcal{C}(G) consisting of the normalized multiplicative characters

F^\lambda = \frac{1}{|G|}\sum\limits_{g \in G} \chi^\lambda(g)E_g.

In order to see how the Fourier transform and the Wedderburn transform work together in the setting of convolution algebras of finite abelian groups, I asked you to work out the case where G is a cyclic group in detail, where the synchrony between the two transforms gives a method to diagonalize circulant matrices. I hope this was instructive, and it is definitely something worth reviewing more than once.

Now suppose G is a nonabelian group. Then, \mathcal{C}(G) is a noncommutative algebra which cannot be isomorphic to a function algebra. However, the center \mathcal{K}(G) of \mathcal{C}(G), which consists of functions on G which are constant on conjugacy classes of G, is a commutative algebra associated to G. In this lecture we will see that the Fourier transform can indeed be concretely implemented for the class algebra of any finite group, which generalizes our prior implementation for convolution algebras of abelian groups. To achieve this extension, we will rely on our extension of multiplicative characters of finite abelian groups to irreducible characters of arbitrary finite groups. I hope that at this point you are close to internalizing the fact that, for abelian groups, multiplicative characters and irreducible characters are the same thing.

Let \Lambda be a set parameterizing irreducible unitary representations of G (or equivalently irreducible linear representations of \mathcal{C}(G)) up to isomorphism. For each \lambda \in \Lambda, let (V^\lambda,\varphi^\lambda) be a representative of the corresponding isomorphism class, and let

\chi^\lambda(g) = \mathrm{Tr} \varphi^\lambda(g), \quad g \in G.

We know that the set \{\chi^\lambda \colon \lambda \in \Lambda\} forms an orthogonal basis of \mathcal{K}(G). Let \{C_\alpha \colon \alpha \in \Lambda\} be the set of conjugacy classes in G. For each \alpha \in \Lambda, let K_\alpha be the indicator function of C_\alpha. Then, the set \{K_\alpha \colon \alpha \in \Lambda\} is an orthogonal basis of \mathcal{K}(G),

\langle K_\alpha,K_\beta\rangle = \delta_{\alpha\beta}|C_\alpha|.

The connection coefficients of the class basis,

K_\alpha K_\beta = \sum\limits_{\gamma \in \Lambda} c_{\alpha\beta\gamma}K_\gamma,

count solutions to certain equations in the underlying group, G. Namely, c_{\alpha\beta\gamma} is the number of pairs (h,k) \in C_\alpha \times C_\beta such that g=hk, where g \in C_\gamma. Let \chi^\lambda_\alpha denote \chi^\lambda(g) for any g \in C_\alpha. In Lecture 25, we posed the following problem which expresses the connection coefficients of \mathcal{K}(G) in terms of the irreducible characters of G. You should reflect on what this says in the case where G is abelian.

Theorem 26.1. For any \alpha,\beta,\gamma \in \Lambda, we have

c_{\alpha\beta\gamma} = \frac{|C_\alpha| |C_\beta|}{|G|}\sum\limits_{\lambda \in \Lambda}\frac{\chi^\lambda_\alpha \chi^\lambda_\beta \overline{\chi^\lambda_\gamma}}{\dim V^\lambda}.

Using this result, we construct a Fourier basis of \mathcal{K}(G). Here is the basic claim: the central functions

F^\lambda = \frac{\dim V^\lambda}{|G|}\sum\limits_{\alpha \in \Lambda} \overline{\chi^\lambda_\alpha}K_\alpha, \quad \lambda \in \Lambda

form a Fourier basis of \mathcal{K}(G). Let us first check that these candidate functions are nonzero.

Problem 26.1. Compute the L^2-norm of F^\lambda, and show that \sum_{\lambda \in \Lambda} \|F^\lambda\|^2=1.

Now, on to the main event.

Theorem 26.1. The |\Lambda| nonzero functions

F^\lambda = \frac{\dim V^\lambda}{|G|}\sum\limits_{\alpha \in \Lambda} \overline{\chi^\lambda_\alpha}K_\alpha, \quad \lambda \in \Lambda

are pairwise orthogonal selfadjoint idempotents in \mathcal{K}(G).

Proof: We have

F^\lambda F^\mu = \frac{\dim V^\lambda}{|G|}\frac{\dim V^\mu}{|G|}\sum\limits_{\alpha \in \Lambda}\sum\limits_{\beta \in \Lambda} \overline{\chi^\lambda_\alpha} \overline{\chi^\mu_\beta} K_\alpha K_\beta=\frac{\dim V^\lambda}{|G|}\frac{\dim V^\mu}{|G|}\sum\limits_{\alpha \in \Lambda}\sum\limits_{\beta \in \Lambda} \sum\limits_{\gamma \in \Lambda}\overline{\chi^\lambda_\alpha} \overline{\chi^\mu_\beta} c_{\alpha\beta\gamma}K_\gamma.

By Theorem 26.1, the right hand side is

\frac{\dim V^\lambda}{|G|}\frac{\dim V^\mu}{|G|}\sum\limits_{\alpha \in \Lambda}\sum\limits_{\beta \in \Lambda} \sum\limits_{\gamma \in \Lambda}\overline{\chi^\lambda_\alpha} \overline{\chi^\mu_\beta} K_\gamma \frac{|C_\alpha||C_\beta|}{|G|}\sum\limits_{\nu \in \Lambda} \frac{\chi^\nu_\alpha\chi^\nu_\beta\overline{\chi^\nu_\gamma}}{\dim V^\nu}.

This quadruple sum over \Lambda can be reorganized as

\frac{\dim V^\lambda \dim V^\mu}{|G|^3}\sum\limits_{\nu \in \Lambda}\frac{1}{\dim V^\nu} \left(\sum\limits_{\alpha \in \Lambda} \overline{\chi^\lambda_\alpha}\chi^\nu_\alpha|C_\alpha| \right)\left(\sum\limits_{\beta \in \Lambda} \overline{\chi^\mu_\beta}\chi^\nu_\beta|C_\beta|\right)\sum\limits_{\gamma \in \Lambda}\overline{\chi^\nu_\gamma}K_\gamma.

Character orthogonality (original, not dual) collapses the sums over \alpha and \beta, leaving

\frac{\dim V^\lambda \dim V^\mu}{|G|}\sum\limits_{\nu \in \Lambda} \frac{1}{\dim V^\nu}\delta_{\lambda\nu}\delta_{\mu\nu}\sum\limits_{\gamma \in \Lambda}\overline{\chi^\nu_\gamma}K_\gamma =\delta_{\lambda\mu} \frac{\dim V^\lambda}{|G|}\sum\limits_{\gamma \in \Lambda}\overline{\chi^\lambda_\gamma}K_\gamma.

This completes the orthogonal idempotent part of the proof. It remains to check that the proposed Fourier basis consists of selfadjoint elements, and we leave this as an exercise. \square

Math 202B: Lecture 25

Let \Lambda be a set parameterizing irreducible unitary representations of G up to isomorphism, and for each \lambda \in \Lambda let (V^\lambda,\varphi^\lambda) be a representative of the corresponding isomorphism class. Equivalently, \Lambda parameterizes irreducible linear representations of the convolution algebra \mathcal{C}(G) up to isomorphism, and for each \lambda \in \Lambda we take the representative (V^\lambda,\Phi^\lambda) determined by

\Phi^\lambda(E_g) = \varphi^\lambda(g), \quad g \in G.

Thus, for any function

A = \sum\limits_{g \in G} A(g) E_g

in \mathcal{C}(G) we have

\Phi^\lambda(A) = \sum\limits_{g \in G} A(g)\phi^\lambda(g),

and

\chi^\lambda(A) = \mathrm{Tr}\ \Phi^\lambda(A) = \sum\limits_{g \in G} A(g) \mathrm{Tr}\, \varphi^\lambda(g) = \sum\limits_{g \in G} A(g) \chi^\lambda(g).

Recall that the class algebra \mathcal{K}(G) consists of those functions A \in \mathcal{C}(G) which are constant on the conjugacy classes of G, and that this is the center of \mathcal{C}(G). By Schur’s Lemma, if A \in \mathcal{K}(G) then the operator \Phi^\lambda(A) is a scalar multiple of the the identity operator,

\Phi^\lambda(A) = \omega^\lambda(A)I_{V^\lambda}.

This determines a map

\omega^\lambda \colon \mathcal{K}(G) \longrightarrow \mathbb{C}

called the central character of the irrep (V^\lambda,\Phi^\lambda).

Problem 25.1. Prove that, for any \lambda \in \Lambda, the central character \omega^\lambda \colon \mathcal{K}(G) \to \mathbb{C} is an algebra homomorphism, given in terms of the character of (V^\lambda,\Phi^\lambda) by

\omega^\lambda(A) = \frac{1}{\dim V^\lambda} \chi^\lambda(A), \quad A \in \mathcal{K}(G).

We are now ready to prove that the irreducible characters of G form an orthogonal basis of the class algebra \mathcal{K}(G). We

Theorem 25.2. The set \{\chi^\lambda \colon \lambda \in \Lambda\} spans \mathcal{K}(G).

Proof: Let W be the subspace of \mathcal{K}(G) spanned by \{\chi^\lambda \colon \lambda \in \Lambda\}. We will show that W^\perp consists solely of the zero function. That is, if A \in \mathcal{K}(G) is a central function orthogonal to every irreducible character,

\langle A, \chi^\lambda \rangle = \sum\limits_{g \in G} \overline{A(g)}\chi^\lambda(g) =0, \quad \lambda \in \Lambda,

then A is the zero function on G. Let

\overline{A}=\sum\limits_{g \in G} \overline{A(g)}E_g,

which is the conjugate of A viewed as an element of the function algebra \mathcal{F}(G) rather than the convolution algebra \mathcal{C}(G). Then,

\omega^\lambda(\overline{A})= \frac{1}{\dim V^\lambda} \mathrm{Tr} \Phi^\lambda(\overline{A}) = \frac{1}{\dim V^\lambda} \sum\limits_{g \in G} \overline{A(g)} \chi^\lambda(g) \frac{1}{\dim V^\lambda} \langle A,\chi^\lambda\rangle= 0, \quad \lambda \in \Lambda.

This says that the image of \overline{A} in every irreducible representation (V^\lambda,\Phi^\lambda) of \mathcal{C}(G) is the zero operator. Since every linear representation of \mathcal{C}(G) is a direct sum of irreducible linear representations, this means that \overline{A} is the zero operator in every linear representation of \mathcal{C}(G). This includes the regular representation, which is faithful. We conclude that \overline{A} and hence A is the zero function on G, as required. \square

We now know that the set \{\chi^\lambda \colon \lambda \in \Lambda\} of irreducible characters of G is an orthogonal basis of \mathcal{K}(G). In particular, |\Lambda|=\mathrm{dim}\mathcal{K}(G), which says the following.

Corollary 25.3. The number of isomorphism classes of irreducible unitary representations of G is equal to the number of conjugacy classes in G.

Let us consider character orthogonal more carefully. Explicitly, we have

\langle \chi^\lambda,\chi^\mu\rangle= \sum\limits_{g \in G} \overline{\chi^\lambda(g)}\chi^\mu(g) = \sum\limits_{g \in G}\chi^\lambda(g^{-1})\chi^\mu(g)=\delta_{\lambda\mu}|G|.

Now, let \{C_\alpha \colon \alpha \in \Lambda\} be an enumeration of the conjugacy classes in G, and let us write \chi^\lambda_\alpha for \chi^\lambda(g) with g \in C_\alpha. Then, character orthogonality takes the form

\langle \chi^\lambda,\chi^\mu\rangle= \sum\limits_{g \in G} \overline{\chi^\lambda(g)}\chi^\mu(g) = \sum\limits_{\alpha \in \Lambda} |C_\alpha|\overline{\chi^\lambda_\alpha} \chi^\mu_\alpha=\delta_{\lambda\mu}|G|.

Definition 25.4. The character table of G is the square matrix \mathbf{T} with rows and columns indexed by \Lambda and entries

\mathbf{T}_{\alpha\lambda} = \chi^\lambda_\alpha.

The modified character table of G is the square matrix \mathbf{M} with rows and columns indexed by \Lambda and entries

\mathbf{M}_{\alpha\lambda} = \sqrt{\frac{|C_\alpha|}{|G|}}\chi^\lambda_\alpha.

Character orthogonality says that the modified character table of G is a unitary matrix, i.e. that columns of \mathbf{M} are pairwise orthogonal unit vectors,

\sum\limits_{\alpha \in \Lambda} \overline{\mathbf{M}}_{\lambda\alpha} \mathbf{M}_{\mu\alpha}=\sum\limits_{\alpha \in \lambda} \sqrt{\frac{|C_\alpha|}{|G|}}\overline{\chi^\lambda_\alpha}\sqrt{\frac{|C_\alpha|}{|G|}}\chi^\mu_\alpha=\delta_{\lambda\mu}.

Since the rows of a unitary matrix are also pairwise orthogonal unit vectors, this gives us a second orthogonality relation, namely

\sum\limits_{\lambda \in \Lambda} \overline{\mathbf{M}}_{\lambda\alpha} \mathbf{M}_{\lambda\beta}=\sum\limits_{\lambda \in \lambda} \sqrt{\frac{|C_\alpha|}{|G|}}\overline{\chi^\lambda_\alpha}\sqrt{\frac{|C_\beta|}{|G|}}\chi^\lambda_\beta=\delta_{\alpha\beta}.

This is called dual character orthogonality.

Theorem 25.5. For any \alpha,\beta \in \Lambda, we have

\sum\limits_{\lambda \in \Lambda} \overline{\chi^\lambda_\alpha}\chi^\lambda_\beta=\delta_{\alpha\beta}\frac{|G|}{|C_\alpha|}.

As an application of Dual Character Orthogonality, we can obtain a formula for the connection coefficients of the class algebra \mathcal{K}(G) in terms of the irreducible characters of G. Recall that the class basis

K_\alpha=\sum\limits_{g \in C_\alpha} E_g, \quad \alpha \in \Lambda

of \mathcal{K}(G) has the property that its connection coefficients

K_\alpha K_\beta = \sum\limits_{\gamma \in \Lambda} c_{\alpha\beta\gamma}K_\gamma, \quad \alpha,\beta \in \Lambda

solve a factorization problem in the group G.

Problem 25.2. Prove that

c_{\alpha\beta\gamma} = \frac{|C_\alpha||C_\beta|}{|G|}\sum\limits_{\lambda \in \lambda} \frac{\chi^\lambda_\alpha \chi^\lambda_\beta \overline{\chi^\lambda_\gamma}}{\dim V^\lambda}.

Math 202B: Lecture 24

*** Problems in this lecture Due March 15 ***

*** Please complete a course evaluation ***

Let G be a finite group, and let \Lambda be a set parameterizing irreducible unitary representations of G up to isomorphism. We know that \Lambda is a finite set whose cardinality is bounded by the number of conjugacy classes in G. For each \lambda \in \Lambda, let (V^\lambda,\varphi^\lambda) be an irreducible unitary representation of G, and denote by

\chi^\lambda(g) = \mathrm{Tr}\ \varphi^\lambda(g), \quad g \in G,

the corresponding character. Then, \{\chi^\lambda \colon \lambda \in \Lambda\} form an orthogonal set of functions in the class algebra \mathcal{K}(G),

\langle \chi^\lambda,\chi^\mu\rangle= \delta_{\lambda\mu}|G|.

We do not yet know that \{\chi^\lambda \colon \lambda \in \Lambda\} spans \mathcal{K}(G), but we will get there soon.

Today we will discuss the representation-theoretic analogue of prime factorization. In fact, decomposing representations is easier than decomposing numbers because our set of irreducible objects \{V^\lambda \colon \lambda \in \Lambda\} is finite, and there is a formula for the multiplicity of a given irreducible in a given representation.

Let (V,\varphi) be any finite-dimensional unitary representation of G. Either this representation is irreducible, or not. If it is, then (V,\varphi) is isomorphic to (V^\lambda,\varphi^\lambda) for some \lambda \in \Lambda). If not, then it contains a proper subrepresentation, i.e. a nonzero subspace V_1<V which is G-stable.

Theorem 24.1 (Maschke’s Theorem). The orthogonal complement V_1^\perp is also G-stable.

Proof: For any v_0 \in V_1^\perp and v_1 \in V_1 we have

\langle \varphi^\lambda(g)v_0,v_1\rangle = \langle v_0,\varphi^\lambda(g^{-1})v_1\rangle = 0

for all g \in G. \square

We now have a decomposition V=V_1 \oplus V_2 of V into two proper subrepresentations. Repeat this process on each of the “factors” V_1 and V_2, and after finitely many steps you will produce a binary tree whose leaves are irreducible subrepresentations of V. Each of these leaves is necessarily isomorphic to one of the “primes” (V^\lambda,\varphi^\lambda). We thus have a “prime factorization”

V \simeq \bigoplus\limits_{\lambda \in \Lambda} \mathrm{mult}(V^\lambda,V)V^\lambda,

where \mathrm{mult}(V^\lambda,V) is the number of leaves in the tree isomorphic to V^\lambda. This is called the isotypic decomposition of V. It remains to verify that however we decompose (V,\varphi) into irreducibles, the end result will be the same.

Problem 24.1. State and prove a uniqueness theorem for “the” isotypic decomposition of a representation (hint: character orthogonality).

Theorem 24.2. We have

\mathrm{mult}(V^\lambda,V)=\frac{1}{|G|}\langle \chi^\lambda,\chi^V\rangle.

Proof: Taking traces on each side of the isotypic decomposition yields

\chi^V = \sum\limits_{\lambda \in \Lambda} \mathrm{mult}(V^\lambda,V)\chi^\lambda,

now use character orthogonality. \square

Problem 24.2. Prove that \mathrm{mult}(V^\lambda,V) = \dim\mathrm{Hom}_G(V^\lambda,V).

Now we are in position to prove that the character of a representation really does characterize it, up to isomorphism.

Theorem 24.3. Two unitary representation (V,\varphi) and (W,\psi) of G are isomorphic if and only if \chi^V=\chi^W.

Proof: It is clear that isomorphic representations have the same character. For the converse, the fact that \chi^V=\chi^W implies that \langle \chi^\lambda,\chi^V\rangle = \langle \chi^\lambda,\chi^W\rangle for all \lambda \in \Lambda, so that V and W have the same isotypic decomposition. \square

Theorem 24.4. A unitary representation (V,\varphi) of G is irreducible if and only if \langle \chi^V,\chi^V \rangle=|G|.

Proof: Let

\chi^V = \sum\limits_{\lambda \in \Lambda} \mathrm{mult}(V^\lambda,V)\chi^\lambda

denote the isotypic decomposition of G in character form. We then have

\langle \chi^V,\chi^V\rangle = |G|\sum\limits_{\lambda \in \Lambda} \mathrm{mult}(V^\lambda,V)^2,

and you can take it from here. \square

Problem 24.3. Compute the isotypic decomposition of the regular representation.

Math 202B: Lecture 23

*** Problems in this lecture due March 15 ***

*** Please complete a course evaluation ***

Let \mathbf{Rep}(G) be the category of finite-dimensional unitary representations (V,\varphi) of a finite group G.

Problem 23.1. One-dimensional unitary representations of G are the same thing as multiplicative characters of G. Explain this sentence carefully.

We also discussed a way to associate a scalar-valued function on G to every unitary representation (V,\varphi) of G. Namely, the character of (V,\varphi) is the function on G defined by

\chi^V(g)= \mathrm{Tr}\ \varphi(g), \quad g \in G.

After objects come morphisms. We have been working on our understanding of the hom-spaces in \mathbf{Rep}(G), which are vector spaces of linear transformations. Namely, for any two unitary representations (V,\varphi) and (W,\psi) of G, the corresponding set of morphisms \mathrm{Hom}_G(V,W) is the subspace of \mathrm{Hom}(V,W) consisting of those linear transformations which satisfy

T\circ \varphi(g) = \psi(g) \circ T, \quad g \in G.

Transformations T \in \mathrm{Hom}_G(V,W) are said to intertwine the actions \varphi and \psi. Equivalently, \mathrm{Hom}_G(V,W) is the space of G-equivariant linear maps from V to W. The first thing we did was prove a dimension formula, which we restate now for ease of reference.

Theorem 23.1. We have

\dim \mathrm{Hom}_G(V,W) = \frac{1}{|G|} \langle \chi^V,\chi^W \rangle.

This is at least reminiscent of our main result about multiplicative characters of a finite abelian group: they form an orthogonal basis of \mathcal{C}(G). So, we want to see some sort of orthogonality emerging for characters of unitary representations which, once again, are higher-dimensional generalizations of multiplicative characters. We saw that the more general version of character orthogonality we are trying to develop is related to the concept of irreducibility.

Problem 23.2. Prove that if G is abelian, all its irreducible representations are one-dimensional.

Last lecture, we proved the following.

Theorem 23.2 (Schur’s Lemma). If (V,\varphi) and (W,\psi) are irreducible unitary representations of G, then every nonzero map T \in \mathrm{Hom}_G(V,W) is an isomorphism.

As a consequence of Theorems 23.1 and 23.2 we have the following: if (V,\varphi) and (W,\psi) are irreducible and non-isomorphic, their characters are orthogonal: we have

\chi^V,\chi^W \rangle = |G| \dim \mathrm{Hom}_G(V,W) =0.

In particular, this generalizes character orthogonality as we know it for finite abelian groups. This leads to the following.

Conjecture 23.3. If (V,\varphi) is an irreducible unitary representation of G, then

\langle \chi^V,\chi^V\rangle = |G|.

The goal of this lecture is to prove Conjecture 23.3. First of all, because of Theorem 23.1, for any unitary representation (V,\varphi) of G we have

\langle \chi^V,\chi^V\rangle = |G|\dim \mathrm{Hom}_G(V,V).

So Conjecture 23.3 is equivalent to the following.

Conjecture 23.4. If (V,\varphi) is an irreducible unitary representation of G, then \mathrm{End}_G(V) = \mathrm{Hom}_G(V,V) is one-dimensional.

First of all, let us clarify that \mathrm{End}_G(V) is the space of all linear operators T \in \mathrm{End}(V) such that

T\rho(g)=\rho(g)T, \quad g \in G.

As we have seen, this is in fact a subalgebra of \mathrm{End}(V), and e know that \mathrm{End}_G(V) and every algebra has a unique one-dimensional subalgebra. So, Conjecture 23.4 is equivalent to the following.

Theorem 23.5. If (V,\varphi) is an irreducible unitary representation of G, then \mathrm{End}_G(V) = \mathbb{C}I.

Proof: Let T \in \mathrm{End}_G(V) and let \alpha be an eigenvalue of T. Then, T - \alpha I is again in the algebra \mathrm{End}_G(V), but at the same time \mathrm{Ker}(T-\alpha I) is a nontrivial G-stable subspace of V. Since (V,\varphi) is irreducible, \mathrm{Ker}(T-\alpha I)=V, which is the same as T=\alpha I. \square

The above argument relies on something we all take for granted. For any algebra \mathcal{A} and any element A \in \mathcal{A}, the spectrum of A is the set

\mathrm{Spec}(A) = \{\alpha \in \mathbb{C} \colon A-\alpha I \text{ not invertible}\}.

Theorem 23.6 (Fundamental Theorem of Algebra). Every T \in \mathrm{End}(V) has nonempty spectrum \mathrm{Spec}(T) \subset \mathbb{C}.

Problem 23.3. Assuming the above, prove that the spectrum of any element of any finite-dimensional von Neumann algebra is nonempty.

The following generalizes Theorem 23.6.

Theorem 23.7 (Burnside’s Theorem). The only subalgebra \mathcal{A} \leq \mathrm{End}(V) which admits no proper non-trivial stable subspace W \leq V is \mathcal{A}=\mathrm{End}(V).

Let (V,\varphi) be any unitary representation of G, and consider the corresponding linear representation of \mathcal{C}(G) defined by

\Phi(E_g) = \varphi(g), \quad g \in G.

Problem 23.4. Prove that (V,\varphi) is irreducible if and only if (V,\Phi) is irreducible.

Combining this problem with Burnside’s theorem, we have that if (V,\varphi) and hence (V,\Phi) is irreducible, then the image of \mathcal{C}(G) in \mathrm{End}(V) is \mathrm{End}(V). Consequently, \mathrm{End}_G(V) is the center of \mathrm{End}(V) and a second proof of Theorem 23.5 follows if we prove directly that the center of an endomorphism algebra is minimal.

Theorem 23.8. The center of \mathrm{End}(V) is \mathbb{C}I.

Proof: Let X \subset V be an orthonormal basis and let \{E_{yx} \colon x,y \in X\} be the corresponding elementary basis of \mathrm{End}(V). Suppose that A \in \mathrm{End}(V) commutes with all elementary operators. Then, for any p,q \in X we have

E_{pp}AE_{qq} = \sum\limits_{x,y \in X} \langle y,Ax\rangle E_{pp}E_{yx}E_{qq} = \sum\limits_{y \in X} \langle p,Ax\rangle E_{px}E_{qq} = \langle p,Aq \rangle E_{pq},

and likewise

E_{qq}AE_{pp} = \langle q,Ap \rangle E_{qp},

so that

p \neq q \implies \langle p,Aq\rangle = \langle q,Ap \rangle =0.

Furthermore, we have

E_{pq}AE_{qp} = \sum\limits_{x,y \in X} \langle y,Ax\rangle E_{pq}E_{yx}E_{qp} =\sum\limits_{x \in X} \langle q,Ax\rangle E_{px}E_{qp} = \langle q,Aq\rangle E_{pp},

and also

E_{pq}E_{qp}A = E_{pp}A = \sum\limits_{x,y \in X} \langle y,Ax \rangle E_{pp}E_{yx} = \sum\limits_{x \in X} \langle p,Ax\rangle E_{px} = \langle p,Ap\rangle E_{pp},

which forces \langle p,Ap\rangle = \langle q,Aq\rangle. \square

Math 202B: Lecture 22

Let \mathbf{Rep}(G) be the category of finite-dimensional unitary representations of a finite group G. As we discussed last week, \mathbf{Rep}(G) is both “bigger” and “smaller” than the category \mathbf{FHil} of finite-dimensional Hilbert spaces. What this means is that the same Hilbert space V may appear in \mathbf{Rep}(G) as two distinct representations (V,\varphi) and (V,\varphi'), but at the same time hom-spaces in \mathbf{Rep}(G) may be smaller because, unlike \mathrm{Hom}(V,W), linear maps in \mathrm{Hom}_G(V,W) must intertwine the actions \varphi and \psi of two unitary representations (V,\varphi) and (W,\psi). In fact, we have already made this “smaller” feature quantitative by deriving the dimension formula

\dim \mathrm{Hom}_G(V,W) = \frac{1}{|G|} \langle \chi^V,\chi^W\rangle.

In this lecture we will compare \mathrm{Hom}(V,W) and \mathrm{Hom}_G(V,W) structurally as opposed to numerically.

One of the simplest things we can say about a linear map T \in \mathrm{Hom}(V,W) is that its kernel and image are subspaces of V and W, respectively. It is therefore natural to hope that a G-equivariant linear map T \in \mathrm{Hom}_G(V,W) would have kernel and image that are “subrepresentations” of V and W, respectively. To make sense of this we first need to define subobjects in \mathbf{Rep}(G).

Definition 22.1. Let (V,\varphi) be a unitary representation of G, and let W be a vector subspace of V. We say that W is G-stable if \varphi(g)w \in W for all g \in G and w \in W.

Problem 22.1. Prove that if T \in \mathrm{Hom}_G(V,W) then \mathrm{Ker}(T) is a G-stable subspace of V and \mathrm{Im}(T) is a G-stable subspace of W.

The only reason that the above is not our definition of “subrepresentation” is that we require representations to be nonzero.

Definition 22.2. A subrepresentation of (V,\varphi) is a nonzero G-stable subspace W \leq V. In particular, (W,\varphi) is a unitary representation of G in its own right provided we restrict each \varphi(g) to W.

Now let us recall the main structure theorem we have for linear maps between finite-dimensional vector spaces, which was the main result of Math 202A.

Theorem (SVD): For any linear map T \in \mathrm{Hom}(V,W) between finite-dimensional Hilbert spaces, there exist distinct positive numbers \sigma_1> \dots > \sigma_r > 0 and nonzero pairwise orthogonal subspaces V_1,\dots,V_r and W_1,\dots,W_r of V and W such that

V = V_1 \oplus \dots \oplus V_r \oplus \mathrm{Ker}(T) \quad\text{and}\quad W=W_1 \oplus \dots \oplus W_r \oplus \mathrm{Im}(T)^\perp

and the restriction of T to V_i has the form T=\sigma_iU_i with U_i \in \mathrm{Hom}(V_i,W_i) an isometric isomorphism.

It is an under-appreciated fact that the SVD holds in \mathbf{Rep}(G) in a very natural way.

Theorem 22.3 (G-equivariant SVD). Let (V,\varphi) and (W,\psi) be unitary representations of G and let T \in \mathrm{Hom}_G(V,W) be a G-equivariant linear map. Then, the left singular spaces V_1,\dots,V_r of T are subrepresentations of V, the right singular spaces W_1,\dots,W_r are subrepresentations of W, and the restriction of T to V_i is an isomorphism in \mathrm{Hom}_G(V_i,W_i). Moreover, the map U_i = \sigma_iT_i|_{V_i} is an isometric isomorphism in \mathrm{Hom}(V_i,W_i).

In \mathbf{FHil}, a space V whose only subspace is V is necessarily one-dimensional. In \mathbf{Rep}(G), the situation is not as simple.

Definition 22.1. A unitary representation (V,\varphi) of G is said to be irreducible if the only subrepresentation it contains is (V,\varphi) itself.

Let \mathbf{Irr}(G) be the full subcategory of \mathbf{Rep}(G) whose objects are irreducible representations. The hom-spaces in this category are highly restricted.

Theorem 22.4 (Schur’s Lemma). If (V,\varphi) and (W,\psi) are irreducible unitary representations of G, then any nonzero map T \in \mathrm{Hom}_G(V,W) is an isomorphism.

Problem 22.2. Prove Schur’s Lemma (it follows directly from the $latex $G-equivariant SVD).$

Another way to state Schur’s Lemma is that if (V,\varphi) and (W,\psi) are irreducible representations which are not isomorphic, then

\mathrm{Hom}_G(V,W) = \{0_{\mathrm{Hom}(V,W)}\}.

Together with our dimension formula for \mathrm{Hom}_G(V,W), this yields the following.

Corollary 22.5. The characters of two non-isomorphic irreducible unitary representations (V,\varphi) and (W,\psi) are orthogonal: we have \langle \chi^V,\chi^W\rangle=0.

Problem 22.3. Prove that the character of any unitary representation (V,\varphi) of G is a class function on G. Prove that the characters of any two isomorphic representations are equal. Combining these facts, deduce an upper bound on the number of isomorphism classes of irreducible unitary representations of G.