Problem Set 6: Sum Decompositions

Work out the matrix representation $[g]_\B$ for each $g \in S_3$. What do you notice about the form of these matrices?

1. Let $U, V$ be vector spaces. Suppose that $\B_U := \{u_1, \ldots, u_m\}$ is a basis for $U$ and $\B_V := \{v_1,\ldots, v_n\}$ is a basis for $V$. Prove that \[ \B_{U\oplus V} := \{u_1 \oplus 0, \ldots, u_m \oplus 0, 0 \oplus v_1, \ldots, 0 \oplus v_n\} \] is a basis for $U \oplus V$.

   Solution

   Let $x \oplus y \in U \oplus V$. Since $\B_U$ and $\B_V$ are bases, we may write $x = \sum_i a_i u_i$ and $y = \sum_j b_j v_j$ for some scalars $a_i, b_j \in \CC$. Since the vector space operations in $U \oplus V$ are defined componentwise, \[ x \oplus y = \Big(\sum_i a_i u_i\Big) \oplus \Big(\sum_j b_j v_j\Big) = \sum_i a_i (u_i \oplus 0) + \sum_j b_j (0 \oplus v_j), \] so $\B_{U \oplus V}$ spans $U \oplus V$. For linear independence, suppose $\sum_i a_i (u_i \oplus 0) + \sum_j b_j (0 \oplus v_j) = 0 \oplus 0$. The left side equals $(\sum_i a_i u_i) \oplus (\sum_j b_j v_j)$, so comparing components gives $\sum_i a_i u_i = 0$ in $U$ and $\sum_j b_j v_j = 0$ in $V$. Since $\B_U$ and $\B_V$ are linearly independent, all of the $a_i$ and $b_j$ are zero. Hence $\B_{U \oplus V}$ is a basis, and in particular $\dim(U \oplus V) = \dim U + \dim V$.

2. Now suppose that $U$ and $V$ are both $G$-representations. Given $g \in G$, let $[g]_U$ and $[g]_V$ denote the matrix representations for $g$ acting on $U$ and $V$ with respect to the bases $\B_U$ and $\B_V$, respectively. Similarly, let $[g]_{U\oplus V}$ denote the matrix representation of $g$ with respect to $\B_{U \oplus V}$. Prove that \[ [g]_{U \oplus V} = \begin{bmatrix} {[g]_U} & 0\\ 0 & [g]_V \end{bmatrix}, \] where the $0$ here represent rectangular matrices of zeros. Matrices in this form are called block diagonal matrices.

   Solution

   Write $[g]_U = (a_{ij})$ and $[g]_V = (b_{ij})$. By definition of the matrix of a linear map with respect to a basis, this means \[ g u_j = \sum_{i=1}^m a_{ij} u_i \qquad\text{and}\qquad g v_j = \sum_{i=1}^n b_{ij} v_i. \] The $j$th column of $[g]_{U \oplus V}$ records the coordinates of $g$ applied to the $j$th vector of $\B_{U \oplus V}$. For $1 \leq j \leq m$, \[ g(u_j \oplus 0) = gu_j \oplus g0 = \Big(\sum_{i=1}^m a_{ij} u_i\Big) \oplus 0 = \sum_{i=1}^m a_{ij} (u_i \oplus 0), \] so the $j$th column of $[g]_{U \oplus V}$ is $(a_{1j}, \ldots, a_{mj}, 0, \ldots, 0)$: the $j$th column of $[g]_U$ followed by $n$ zeros. Similarly, for $1 \leq j \leq n$, \[ g(0 \oplus v_j) = 0 \oplus gv_j = \sum_{i=1}^n b_{ij} (0 \oplus v_i), \] so the $(m + j)$th column of $[g]_{U \oplus V}$ is $(0, \ldots, 0, b_{1j}, \ldots, b_{nj})$: $m$ zeros followed by the $j$th column of $[g]_V$. Assembling these columns gives exactly the block diagonal matrix \[ [g]_{U \oplus V} = \begin{bmatrix} {[g]_U} & 0 \\ 0 & [g]_V \end{bmatrix}. \]

Suppose that $U, V \subseteq W$ are subspaces such that $U + V = W$ and $U \cap V = \zero$. Prove that $W \cong U \oplus V$. These conditions are called the internal direct sum criteria.

Let $X$ and $Y$ be $G$-sets. Recall that $X + Y$ is the disjoint union of $X$ and $Y$. Prove that $\CC(X + Y) \cong \CC X \oplus \CC Y$. Hint: Without loss of generality you may assume that $X, Y \subseteq X + Y$. This will allow you to use the internal direct sum criteria.

Prove that every nonzero finite dimensional representation $V$ is isomorphic to a finite direct sum of irreducible representations.

Let $C_\infty = \langle g \rangle$ be the infinite cyclic group. An $n$-dimensional representation of $C_\infty$ is equivalent to the choice of an invertible $n\times n$ matrix. For example, consider the 2-dimensional representation $W = \CC^2$ of $C_\infty$ given by \[ g \longmapsto \mat 1 1 0 1 . \] Prove that $U = \Span(e_1)$ is a $C_\infty$-invariant subspace and that $U$ has no complementary invariant subspace.

Let's review/get to know inner products. Suppose $V$ is an inner product space.

1. Prove that $\langle v, v\rangle \in \RR$ for all $v \in V$ (hence that the third axiom defining the inner product makes sense).

   Solution

   Taking $w = v$ in the first axiom gives $\langle v, v\rangle = \overline{\langle v, v\rangle}$. A complex number equal to its own conjugate is real, so $\langle v, v\rangle \in \RR$ and the inequality $\langle v, v\rangle > 0$ in the third axiom makes sense.

2. Prove that $\langle v, c_1w_1 + c_2w_2\rangle = \overline{c_1}\langle v,w_1\rangle + \overline{c_2}\langle v,w_2\rangle$ for all $v,w_1, w_2 \in V$ and all $c_1, c_2 \in \CC$.

   Solution

   Using the first axiom, then linearity in the first slot, then the fact that complex conjugation respects sums and products,

   \[\begin{aligned} \langle v, c_1 w_1 + c_2 w_2\rangle &= \overline{\langle c_1 w_1 + c_2 w_2, v\rangle} = \overline{c_1 \langle w_1, v\rangle + c_2\langle w_2, v\rangle}\\ &= \overline{c_1}\,\overline{\langle w_1, v\rangle} + \overline{c_2}\,\overline{\langle w_2, v\rangle} = \overline{c_1}\langle v, w_1\rangle + \overline{c_2}\langle v, w_2\rangle, \end{aligned}\]

   where the last step uses the first axiom once more. So an inner product is linear in the first slot and conjugate-linear in the second.

3. Prove that $\langle 0,w\rangle = \langle v, 0\rangle = 0$ for all $v, w \in V$.

   Solution

   Since the zero vector satisfies $0 = 0 \cdot 0$ (the scalar $0$ times the vector $0$), linearity in the first slot gives \[ \langle 0, w\rangle = \langle 0 \cdot 0, w\rangle = 0 \cdot \langle 0, w\rangle = 0. \] Then $\langle v, 0\rangle = \overline{\langle 0, v\rangle} = \overline{0} = 0$.

1. Let $V$ be a finite dimensional inner product space and let $U \subseteq V$ be a subspace. Prove that \[ U^\perp := \{ v\in V : \langle u,v\rangle = 0 \text{ for all }u \in U\} \] is a subspace of $V$ and that $V \cong U \oplus U^\perp$. Hint: Choose a basis $u_1,\ldots, u_k$ of $U$ and consider the linear transformation $T: V \to \CC^k$ defined by \[ T(v) := (\langle v,u_1\rangle, \ldots, \langle v, u_k\rangle). \] We call $U^\perp$ the orthogonal complement of $U$.

   Solution

   Let $n := \dim V$ and $k := \dim U$.

   $U^\perp$ is a subspace. By Problem 6.7(3), $\langle u, 0\rangle = 0$ for all $u \in U$, so $0 \in U^\perp$. If $v, v' \in U^\perp$ and $c, c' \in \CC$, then for every $u \in U$ conjugate-linearity in the second slot (Problem 6.7(2)) gives \[ \langle u, cv + c'v'\rangle = \overline{c}\langle u, v\rangle + \overline{c'}\langle u, v'\rangle = 0, \] so $cv + c'v' \in U^\perp$.

   $U \cap U^\perp = \zero$. If $u \in U \cap U^\perp$, then $\langle u, u\rangle = 0$, which by the third axiom forces $u = 0$.

   $U + U^\perp = V$. Choose a basis $u_1, \ldots, u_k$ of $U$ and define $T : V \to \CC^k$ by \[ T(v) := \big(\langle v, u_1\rangle, \ldots, \langle v, u_k\rangle\big). \] Each coordinate is linear in $v$ by the second axiom, so $T$ is linear. A vector $v$ lies in $\ker T$ exactly when $\langle v, u_i\rangle = 0$ for all $i$. Since every $u \in U$ is a linear combination of the $u_i$, this is equivalent to $\langle v, u\rangle = 0$ for all $u \in U$, which after conjugating is the condition $v \in U^\perp$. Thus $\ker T = U^\perp$, and rank–nullity gives $\dim U^\perp = n - \operatorname{rank} T \geq n - k$. Applying Problem 6.3 to the subspaces $U$ and $U^\perp$ of $U + U^\perp$ gives $U + U^\perp \cong U \oplus U^\perp$, so by Problem 6.2 \[ \dim(U + U^\perp) = \dim U + \dim U^\perp \geq k + (n - k) = n = \dim V. \] Hence $U + U^\perp = V$ (and in fact $\dim U^\perp = n - k$).

   The internal direct sum criteria now give $V \cong U \oplus U^\perp$.

2. Now suppose that $V$ is a $G$-representation and that $U \subseteq V$ is an invariant subspace. Furthermore, let's suppose that $V$ has an inner product $\langle \,\cdot\, , \,\cdot\, \rangle$ which is $G$-invariant: \[ \langle gv, gw\rangle = \langle v, w\rangle \] for all $g\in G$ and $v, w\in V$. Prove that $U^\perp$ is also $G$-invariant and that $V \cong U \oplus U^\perp$ as $G$-representations.

   Solution

   Let $v \in U^\perp$ and $g \in G$. For any $u \in U$, invariance of the inner product applied with the group element $g^{-1}$ gives \[ \langle u, gv\rangle = \langle g^{-1}u, g^{-1}gv\rangle = \langle g^{-1}u, v\rangle = 0, \] since $g^{-1}u \in U$ by invariance of $U$ and $v \in U^\perp$. Hence $gv \in U^\perp$, so $U^\perp$ is $G$-invariant. By part (1), $U$ and $U^\perp$ satisfy the internal direct sum criteria, and both are subrepresentations, so by Problem 6.3 (and the remark following it) the map $u \oplus v \mapsto u + v$ is an isomorphism of $G$-representations $U \oplus U^\perp \cong V$.

3. Prove that the $C_\infty$-representation $W$ constructed in Problem 6.6 does not have any $C_\infty$-invariant inner product.

   Solution

   Suppose for contradiction that $W$ had a $C_\infty$-invariant inner product. The subspace $U = \Span(e_1)$ is $C_\infty$-invariant by Problem 6.6, so by part (2) its orthogonal complement $U^\perp$ is a $C_\infty$-invariant subspace with $U + U^\perp = W$ and $U \cap U^\perp = \zero$. That is, $U^\perp$ is a complementary invariant subspace of $U$, which Problem 6.6 shows does not exist.

Prove that $\langle \,\cdot\, , \,\cdot\, \rangle_G$ is a $G$-invariant inner product on $V$.

1. Construct an explicit inner product $\langle \,\cdot\, , \,\cdot\,\rangle$ on $\CC^n$ for all $n \geq 1$.

   Solution

   For $v = (a_1, \ldots, a_n)$ and $w = (b_1, \ldots, b_n)$ in $\CC^n$ define \[ \langle v, w\rangle := \sum_{i=1}^n a_i \overline{b_i}. \] This is the standard inner product on $\CC^n$; when all coordinates are real it is the usual dot product. We check the axioms.

   Conjugate symmetry. $\overline{\langle w, v\rangle} = \overline{\sum_i b_i \overline{a_i}} = \sum_i \overline{b_i}\, a_i = \langle v, w\rangle$.

   Linearity in the first slot. If $v' = (a_1', \ldots, a_n')$ and $c, c' \in \CC$, then $\langle cv + c'v', w\rangle = \sum_i (ca_i + c'a_i')\overline{b_i} = c\langle v, w\rangle + c'\langle v', w\rangle$.

   Positivity. $\langle v, v\rangle = \sum_i a_i\overline{a_i} = \sum_i |a_i|^2$ is a sum of nonnegative reals, and it is zero only if every $|a_i| = 0$, that is, only if $v = 0$.

2. Let $V$ be an $n$-dimensional complex vector space and suppose that $\varphi : V \to \CC^n$ is an isomorphism. Prove that the function \[ \langle v,w\rangle_\vp := \langle \vp(v),\vp(w)\rangle \] defines an inner product on $V$.

   Solution

   Here $\langle\,\cdot\,,\,\cdot\,\rangle$ denotes the standard inner product on $\CC^n$ from part (1). Conjugate symmetry and linearity in the first slot are inherited from $\CC^n$ because $\vp$ is linear: \[ \langle v, w\rangle_\vp = \langle \vp(v), \vp(w)\rangle = \overline{\langle \vp(w), \vp(v)\rangle} = \overline{\langle w, v\rangle_\vp} \] and

   \[\begin{aligned} \langle c_1v_1 + c_2v_2, w\rangle_\vp &= \langle c_1\vp(v_1) + c_2\vp(v_2), \vp(w)\rangle\\ &= c_1\langle \vp(v_1), \vp(w)\rangle + c_2\langle\vp(v_2), \vp(w)\rangle = c_1\langle v_1, w\rangle_\vp + c_2\langle v_2, w\rangle_\vp. \end{aligned}\]

   For positivity, if $v \neq 0$ then $\vp(v) \neq 0$ since $\vp$ is injective, so $\langle v, v\rangle_\vp = \langle \vp(v), \vp(v)\rangle > 0$. (Only the injectivity of $\vp$ was used; surjectivity is not needed.) Since every $n$-dimensional vector space admits an isomorphism $\vp : V \to \CC^n$, obtained by choosing a basis, every finite dimensional vector space has an inner product.

3. If $G$ is a finite group and $V$ is a nonzero finite dimensional $G$-representation, prove that $V$ is irreducible if and only if the only $G$-invariant subspaces of $V$ are $\zero$ and $V$ itself.

   Solution

   Suppose first that $V$ has an invariant subspace $U$ with $U \neq \zero$ and $U \neq V$. By parts (1) and (2), $V$ has an inner product, and by Problem 6.9 averaging it over $G$ produces a $G$-invariant inner product on $V$. By Problem 6.8(2), $V \cong U \oplus U^\perp$ as $G$-representations. Here $\dim U > 0$ since $U \neq \zero$, and $\dim U^\perp = \dim V - \dim U > 0$ since $U \neq V$. Thus $V$ is not irreducible.

   Conversely, suppose $V$ is not irreducible, so there is an isomorphism of $G$-representations $\psi : U \oplus U' \to V$ with $U$ and $U'$ of positive dimension. Let $U_0 := \psi(U \oplus 0) \subseteq V$ be the image of the subspace $U \oplus 0 := \{u \oplus 0 : u \in U\}$. Since $\psi$ is linear, $U_0$ is a subspace, and it is $G$-invariant because $\psi$ commutes with $G$: for $u \in U$, \[ g\psi(u \oplus 0) = \psi(g(u \oplus 0)) = \psi(gu \oplus 0) \in U_0. \] Since $\psi$ is injective, $\dim U_0 = \dim U > 0$, so $U_0 \neq \zero$; and $\dim U_0 = \dim V - \dim U' < \dim V$, so $U_0 \neq V$. Thus $V$ has an invariant subspace other than $\zero$ and $V$.

   Combining the two directions, $V$ is irreducible if and only if its only invariant subspaces are $\zero$ and $V$. Note that the second direction did not use that $G$ is finite; finiteness (through the averaging trick) is needed only for the first.

Let $V$ and $W$ be $G$-representations and let $\vp : V \to W$ be a $G$-linear map.

1. Prove that $\ker\vp$ is a $G$-invariant subspace of $V$ and that $\im\vp$ is a $G$-invariant subspace of $W$.

   Solution

   Both are subspaces by linear algebra, so we only need to check invariance. If $v \in \ker\vp$ and $g \in G$, then $\vp(gv) = g\vp(v) = g0 = 0$, so $gv \in \ker\vp$. If $w \in \im\vp$, say $w = \vp(v)$, then $gw = g\vp(v) = \vp(gv) \in \im\vp$.

2. Now suppose $V$ and $W$ are both irreducible. Prove that $\vp$ is either the zero map or an isomorphism of $G$-representations. This result is known as Schur's lemma.

   Solution

   By part (1), $\ker\vp$ is an invariant subspace of the irreducible representation $V$, so $\ker\vp = V$ or $\ker\vp = \zero$. In the first case $\vp = 0$. In the second case $\vp$ is injective, so $\im\vp \cong V$ is nonzero because $V \neq \zero$. By part (1), $\im\vp$ is a nonzero invariant subspace of the irreducible representation $W$, hence $\im\vp = W$ and $\vp$ is surjective. Thus $\vp$ is a bijective $G$-linear map, which is to say an isomorphism of $G$-representations.

3. Suppose $V$ is irreducible and $\vp : V \to V$ is $G$-linear. Prove that $\vp = \lambda 1_V$ for some $\lambda \in \CC$, where $1_V$ is the identity map. Conclude that if $V$ and $W$ are irreducible, then $\dim \Hom_G(V, W)$ is $1$ if $V \cong W$ and $0$ otherwise. Hint: Since $\CC$ is algebraically closed, $\vp$ has an eigenvalue.

   Solution

   Since $V$ is a nonzero finite dimensional complex vector space, the characteristic polynomial of $\vp$ has a root $\lambda \in \CC$, so $\vp - \lambda 1_V$ has a nonzero kernel. The identity $1_V$ is $G$-linear, so $\vp - \lambda 1_V \in \Hom_G(V,V)$. By Schur's lemma, $\vp - \lambda 1_V$ is either zero or an isomorphism, and it is not injective, so $\vp - \lambda 1_V = 0$. Hence $\Hom_G(V, V) = \CC \cdot 1_V$ has dimension $1$.

   Now let $V$ and $W$ be irreducible. If $V \not\cong W$, then by Schur's lemma every element of $\Hom_G(V,W)$ is zero, so $\dim\Hom_G(V,W) = 0$. If $\psi : V \to W$ is an isomorphism of $G$-representations, then $\psi^{-1}$ is $G$-linear, so for any $\vp \in \Hom_G(V,W)$ the composite $\psi^{-1}\vp$ lies in $\Hom_G(V,V)$ and therefore equals $\lambda 1_V$ for some $\lambda$. Then $\vp = \lambda\psi$, so $\Hom_G(V,W) = \CC\psi$, which has dimension $1$ since $\psi \neq 0$.

Let $G$ be a finite abelian group, let $V$ be a $G$-representation, and let $h \in G$. Prove that the map $\rho_h : V \to V$ given by $\rho_h(v) := hv$ is $G$-linear. Conclude that every irreducible representation of $G$ is 1-dimensional.

1. Let $U, U', W$ be $G$-representations. Prove that there is an isomorphism of vector spaces \[ \Hom_G(W, U \oplus U') \cong \Hom_G(W, U) \oplus \Hom_G(W, U'). \] The same argument with the roles reversed shows that $\Hom_G(U \oplus U', W) \cong \Hom_G(U, W) \oplus \Hom_G(U', W)$.

   Solution

   Let $\pi : U \oplus U' \to U$ and $\pi' : U \oplus U' \to U'$ be the projections $\pi(u \oplus u') = u$ and $\pi'(u \oplus u') = u'$, and let $\iota : U \to U \oplus U'$ and $\iota' : U' \to U \oplus U'$ be the inclusions $\iota(u) = u \oplus 0$ and $\iota'(u') = 0 \oplus u'$. All four maps are $G$-linear because $G$ acts componentwise on $U \oplus U'$, and they satisfy $\iota\pi + \iota'\pi' = 1_{U \oplus U'}$.

   Define $\Phi : \Hom_G(W, U \oplus U') \to \Hom_G(W,U) \oplus \Hom_G(W,U')$ by $\Phi(\vp) := \pi\vp \oplus \pi'\vp$. Composites of $G$-linear maps are $G$-linear, so this makes sense, and $\Phi$ is linear since composition is linear in $\vp$. Define $\Psi$ in the other direction by $\Psi(\alpha \oplus \alpha') := \iota\alpha + \iota'\alpha'$, that is, $w \mapsto \alpha(w) \oplus \alpha'(w)$. Then $\Phi\Psi(\alpha \oplus \alpha') = \pi(\iota\alpha + \iota'\alpha') \oplus \pi'(\iota\alpha + \iota'\alpha') = \alpha \oplus \alpha'$ since $\pi\iota = 1_U$, $\pi\iota' = 0$, $\pi'\iota = 0$, and $\pi'\iota' = 1_{U'}$. Also $\Psi\Phi(\vp) = \iota\pi\vp + \iota'\pi'\vp = (\iota\pi + \iota'\pi')\vp = \vp$. Hence $\Phi$ is an isomorphism.

   For the reversed statement, send $\vp \in \Hom_G(U \oplus U', W)$ to $\vp\iota \oplus \vp\iota'$, with inverse $\beta \oplus \beta' \mapsto \beta\pi + \beta'\pi'$; the same identities show these are mutually inverse.

2. Suppose $V \cong W_1 \oplus \cdots \oplus W_\ell$ with each $W_i$ irreducible, and let $W$ be an irreducible representation. Prove that $\dim\Hom_G(W, V)$ and $\dim\Hom_G(V, W)$ both equal the number of indices $i$ with $W_i \cong W$. Conclude that if $V \cong W_1' \oplus \cdots \oplus W_m'$ is another decomposition into irreducibles, then $m = \ell$ and, after reordering, $W_i \cong W_i'$ for all $i$.

   Solution

   Let $\psi : V \to W_1 \oplus \cdots \oplus W_\ell$ be an isomorphism of $G$-representations. Composing with $\psi$ gives a linear map $\Hom_G(W, V) \to \Hom_G(W, W_1 \oplus \cdots \oplus W_\ell)$, $\vp \mapsto \psi\vp$, which is an isomorphism with inverse $\vp \mapsto \psi^{-1}\vp$. Applying part (1) repeatedly (by induction on $\ell$), \[ \Hom_G(W, W_1 \oplus \cdots \oplus W_\ell) \cong \Hom_G(W, W_1) \oplus \cdots \oplus \Hom_G(W, W_\ell), \] so $\dim\Hom_G(W, V) = \sum_{i=1}^\ell \dim\Hom_G(W, W_i)$ by Problem 6.2. By Problem 6.11(3), each term is $1$ if $W_i \cong W$ and $0$ otherwise, so the sum counts the indices $i$ with $W_i \cong W$. The computation of $\dim\Hom_G(V, W)$ is identical, using the reversed statement in part (1) and composing with $\psi^{-1}$ instead.

   For uniqueness, fix an irreducible $W$. The number of $i$ with $W_i \cong W$ and the number of $j$ with $W_j' \cong W$ are both equal to $\dim\Hom_G(W, V)$, a quantity which depends only on $V$ and $W$. So the two decompositions contain each isomorphism type of irrep the same number of times. Summing over the isomorphism types which occur gives $\ell = m$, and matching up the $W_i$ and $W_j'$ of each type gives the reordering.

Let $G$ be a finite group and let $V$ be a $G$-representation.

1. Prove that $V^G$ is a $G$-invariant subspace of $V$, that $P$ is $G$-linear, that $\im P \subseteq V^G$, and that $Pv = v$ for every $v \in V^G$. Conclude that $\im P = V^G$ and $P^2 = P$. That is, $P$ is a projection onto $V^G$.

   Solution

   Since each $g$ acts linearly, $g0 = 0$ and $g(cv + c'v') = cgv + c'gv' = cv + c'v'$ whenever $v, v' \in V^G$, so $V^G$ is a subspace. It is invariant since $gv = v \in V^G$ for $v \in V^G$.

   The map $P$ is linear because each $g$ is. For $h \in G$, \[ hPv = \frac{1}{|G|}\sum_{g \in G} hgv = \frac{1}{|G|}\sum_{g' \in G} g'v = Pv, \] reindexing by $g' = hg$ (left multiplication by $h$ is a bijection $G \to G$), so $Pv \in V^G$, which shows $\im P \subseteq V^G$. Similarly $P(hv) = \frac{1}{|G|}\sum_g ghv = Pv$, reindexing by $g' = gh$. Combining the two, $P(hv) = Pv = hPv$, so $P$ is $G$-linear. If $v \in V^G$, then every term $gv$ equals $v$, so $Pv = \frac{1}{|G|} \cdot |G| v = v$. Hence $V^G \subseteq \im P$, so $\im P = V^G$, and $P(Pv) = Pv$ because $Pv \in V^G$, so $P^2 = P$.

2. Prove that the map $\Hom_G(\triv, V) \to V^G$ given by $\vp \mapsto \vp(1)$ is an isomorphism of vector spaces. Conclude that $\dim V^G = m_\triv(V)$ is the multiplicity of the trivial representation in $V$.

   Solution

   If $\vp \in \Hom_G(\triv, V)$ then $g\vp(1) = \vp(g \cdot 1) = \vp(1)$ since $G$ acts trivially on $\triv$, so $\vp(1) \in V^G$ and the map is well defined. It is linear since $(c\vp + c'\psi)(1) = c\vp(1) + c'\psi(1)$. It is injective because a linear map $\vp : \CC \to V$ is determined by $\vp(1)$, namely $\vp(z) = z\vp(1)$. It is surjective: given $v \in V^G$, define $\vp(z) := zv$. This is linear, and it is $G$-linear since $\vp(gz) = \vp(z) = zv$ while $g\vp(z) = zgv = zv$. Thus $\Hom_G(\triv, V) \cong V^G$, and taking dimensions gives $m_\triv(V) = \dim V^G$.

3. Let $X$ be a finite $G$-set. For each orbit $O \subseteq X$ let $e_O := \sum_{x \in O} e_x \in \CC X$. Prove that the vectors $e_O$, one for each orbit, form a basis for $(\CC X)^G$. Hence $\dim (\CC X)^G$ is the number of orbits of $G$ on $X$.

   Solution

   For $g \in G$ we have $ge_O = \sum_{x \in O} e_{gx} = e_O$, since $x \mapsto gx$ is a bijection from $O$ to itself. So each $e_O$ lies in $(\CC X)^G$.

   The orbits are pairwise disjoint, so distinct $e_O$ involve disjoint sets of basis vectors $e_x$. If $\sum_O c_O e_O = 0$, then looking at the coefficient of $e_x$ for any $x \in O$ gives $c_O = 0$, so the $e_O$ are linearly independent.

   For spanning, let $v = \sum_{x \in X} c_x e_x \in (\CC X)^G$. For $g \in G$, \[ gv = \sum_{x \in X} c_x e_{gx} = \sum_{x \in X} c_{g^{-1}x} e_x, \] reindexing by $x \mapsto g^{-1}x$. Comparing coefficients in $gv = v$ gives $c_{g^{-1}x} = c_x$ for all $g \in G$ and $x \in X$, so the coefficients $c_x$ are constant on each orbit. Writing $c_O$ for the common value on $O$, we get $v = \sum_O c_O e_O$.

1. Let $P : V \to V$ be a linear map with $P^2 = P$. Prove that $V = \im P \oplus \ker P$, in the sense that $\im P$ and $\ker P$ satisfy the internal direct sum criteria, and deduce that $\trace(P) = \dim \im P$. Hint: $v = Pv + (v - Pv)$.

   Solution

   For any $v \in V$ we have $v = Pv + (v - Pv)$ with $Pv \in \im P$ and $P(v - Pv) = Pv - P^2v = 0$, so $v - Pv \in \ker P$. Hence $\im P + \ker P = V$. If $v \in \im P \cap \ker P$, write $v = Pu$; then $v = Pu = P^2u = Pv = 0$. So $\im P \cap \ker P = \zero$ and the internal direct sum criteria hold.

   By Problems 6.2 and 6.3, if $v_1, \ldots, v_r$ is a basis of $\im P$ and $v_{r+1}, \ldots, v_n$ is a basis of $\ker P$, then $v_1, \ldots, v_n$ is a basis of $V$. For $i \leq r$ write $v_i = Pu_i$; then $Pv_i = P^2u_i = Pu_i = v_i$, while $Pv_i = 0$ for $i > r$. So the matrix of $P$ in this basis is diagonal with $r$ ones followed by $n - r$ zeros, and $\trace(P) = r = \dim\im P$.

2. Let $X$ be a finite $G$-set and let $g \in G$. Write $X^g := \{x \in X : gx = x\}$ for the set of fixed points of $g$. Prove that the trace of $g$ acting on $\CC X$ equals $|X^g|$. Then prove Burnside's lemma: the number of orbits of $G$ on $X$ is \[ \frac{1}{|G|}\sum_{g \in G} |X^g|. \]

   Solution

   Compute the matrix of $g$ with respect to the basis $\{e_x : x \in X\}$ of $\CC X$. The column indexed by $x$ records $ge_x = e_{gx}$, so it has a single $1$ in the row indexed by $gx$ and zeros elsewhere. The diagonal entry in row and column $x$ is therefore $1$ if $gx = x$ and $0$ otherwise. Summing the diagonal entries gives $\trace(g) = |X^g|$.

   Now let $P$ be the averaging operator on $\CC X$. By linearity of the trace, \[ \trace(P) = \frac{1}{|G|}\sum_{g \in G}\trace(g) = \frac{1}{|G|}\sum_{g \in G}|X^g|. \] On the other hand $P^2 = P$ and $\im P = (\CC X)^G$ by Problem 6.14(1), so by part (1) and Problem 6.14(3), \[ \trace(P) = \dim (\CC X)^G = \text{the number of orbits of $G$ on $X$}. \] Equating the two expressions for $\trace(P)$ proves Burnside's lemma.

Let $G$ be a finite group.

1. Let $W$ be any $G$-representation. Prove that the map $\Hom_G(\CC G, W) \to W$ given by $\vp \mapsto \vp(e_\ve)$ is an isomorphism of vector spaces.

   Solution

   The map is linear since $(c\vp + c'\psi)(e_\ve) = c\vp(e_\ve) + c'\psi(e_\ve)$. It is injective: if $\vp$ is $G$-linear, then $\vp(e_h) = \vp(he_\ve) = h\vp(e_\ve)$ for every $h \in G$, so $\vp$ is determined on the basis $\{e_h\}$, and hence everywhere, by the single vector $\vp(e_\ve)$. It is surjective: given $w \in W$, define $\vp : \CC G \to W$ on the basis by $\vp(e_h) := hw$ and extend linearly, so $\vp(\sum_h c_h e_h) = \sum_h c_h hw$. Then $\vp$ is $G$-linear, since it suffices to check on basis vectors and $\vp(ge_h) = \vp(e_{gh}) = ghw = g\vp(e_h)$. Finally $\vp(e_\ve) = \ve w = w$.

2. Prove that every irreducible representation $W$ of $G$ occurs in $\CC G$ with multiplicity $m_W(\CC G) = \dim W$. Use this to show that $G$ has only finitely many irreducible representations up to isomorphism, and that \[ \sum_W (\dim W)^2 = |G|, \] where the sum runs over the irreducible representations of $G$ up to isomorphism.

   Solution

   By Problem 6.13(2), the multiplicity of $W$ in $\CC G$ may be computed as $\dim\Hom_G(\CC G, W)$, which equals $\dim W$ by part (1). In particular every irrep $W$ has $m_W(\CC G) = \dim W \geq 1$, so every irrep appears in a decomposition $\CC G \cong W_1 \oplus \cdots \oplus W_\ell$ into irreducibles. Thus every irrep of $G$ is isomorphic to one of the finitely many $W_i$, and there are only finitely many irreps up to isomorphism. Grouping the $W_i$ by isomorphism type and taking dimensions, \[ |G| = \dim \CC G = \sum_{i=1}^\ell \dim W_i = \sum_W m_W(\CC G)\dim W = \sum_W (\dim W)^2. \]

3. Let $G = S_3$. Let $\triv$ be the trivial representation, let $\CC_\sgn$ be the sign representation on $\CC$ given by $\sigma z := \sgn(\sigma)z$, and let $V_2$ be the plane from the beginning of this problem set, which we showed is irreducible. Prove that $\triv$, $\CC_\sgn$, and $V_2$ are pairwise non-isomorphic and that every irreducible representation of $S_3$ is isomorphic to one of them. Conclude that \[ \CC S_3 \cong \triv \oplus \CC_\sgn \oplus V_2 \oplus V_2, \] and find explicit vectors $u, u' \in \CC S_3$ such that $\Span(u) \cong \triv$ and $\Span(u') \cong \CC_\sgn$.

   Solution

   The representations $\triv$ and $\CC_\sgn$ are 1-dimensional and given by different homomorphisms $S_3 \to \CC^\times$ (they differ on $(12)$), so they are not isomorphic: a $G$-linear isomorphism $\vp : \triv \to \CC_\sgn$ is multiplication by some $c \neq 0$, and then $c = \vp((12) \cdot 1) = (12) \cdot \vp(1) = -c$, a contradiction. Neither is isomorphic to $V_2$, which has dimension $2$. All three are irreducible: 1-dimensional representations trivially so, and $V_2$ by the discussion following the definition of irreducibility. Now $(\dim \triv)^2 + (\dim \CC_\sgn)^2 + (\dim V_2)^2 = 1 + 1 + 4 = 6 = |S_3|$, so by part (2) any further irrep would make the sum of squares exceed $|S_3|$. Hence these are all the irreps of $S_3$. By part (2) their multiplicities in $\CC S_3$ are $1$, $1$, and $2$, which gives the stated decomposition.

   Let $u := \sum_{\sigma \in S_3} e_\sigma$ and $u' := \sum_{\sigma \in S_3} \sgn(\sigma) e_\sigma$. For $\tau \in S_3$, reindexing by $\sigma' = \tau\sigma$, \[ \tau u = \sum_{\sigma} e_{\tau\sigma} = u \qquad\text{and}\qquad \tau u' = \sum_{\sigma} \sgn(\sigma) e_{\tau\sigma} = \sum_{\sigma'} \sgn(\tau^{-1}\sigma') e_{\sigma'} = \sgn(\tau) u', \] using $\sgn(\tau^{-1}\sigma') = \sgn(\tau)\sgn(\sigma')$. So $\Span(u)$ is a copy of $\triv$ and $\Span(u')$ is a copy of $\CC_\sgn$. Note that $u$ spans $(\CC S_3)^{S_3}$ by Problem 6.14(3), since $S_3$ acting on itself has a single orbit. With respect to the standard inner product on $\CC S_3$ (which is $S_3$-invariant, since each $\tau$ permutes the orthonormal basis $\{e_\sigma\}$), the orthogonal complement of $\Span(u, u')$ is a 4-dimensional subrepresentation isomorphic to $V_2 \oplus V_2$.

1. Let $X$ and $Y$ be finite $G$-sets. A linear map $\vp : \CC X \to \CC Y$ is determined by the numbers $a_{y,x} \in \CC$ defined by $\vp(e_x) = \sum_{y \in Y} a_{y,x} e_y$. Prove that $\vp$ is $G$-linear if and only if $a_{gy,gx} = a_{y,x}$ for all $g \in G$, $x \in X$, $y \in Y$. Conclude that $\dim\Hom_G(\CC X, \CC Y)$ is the number of orbits of $G$ on $Y \times X$.

   Solution

   For $g \in G$ and $x \in X$ we have $\vp(ge_x) = \vp(e_{gx}) = \sum_y a_{y,gx}e_y$, while \[ g\vp(e_x) = \sum_y a_{y,x}e_{gy} = \sum_y a_{g^{-1}y,x}e_y. \] So $\vp$ is $G$-linear if and only if $a_{y,gx} = a_{g^{-1}y,x}$ for all $g, x, y$; replacing $y$ by $gy$, this says $a_{gy,gx} = a_{y,x}$. Thus $\vp \mapsto (a_{y,x})$ identifies $\Hom_G(\CC X, \CC Y)$ with the space of functions $Y \times X \to \CC$ that are constant on $G$-orbits, which has a basis given by the indicator functions of the orbits. (Equivalently, $\vp \mapsto \sum a_{y,x}e_{(y,x)}$ identifies $\Hom_G(\CC X, \CC Y)$ with $(\CC(Y \times X))^G$, and we may quote Problem 6.14(3).)

2. Let $V$ and $V'$ be $G$-representations. Prove that \[ \dim\Hom_G(V, V') = \sum_W m_W(V)\,m_W(V'), \] where the sum runs over the irreps of $G$ up to isomorphism. Deduce that $V$ is irreducible if and only if $\dim\Hom_G(V,V) = 1$.

   Solution

   Decompose $V \cong \bigoplus_i W_i$ and $V' \cong \bigoplus_j W_j'$ into irreducibles. Applying both halves of Problem 6.13(1) repeatedly, \[ \Hom_G(V, V') \cong \bigoplus_{i,j}\Hom_G(W_i, W_j'), \] and by Problem 6.11(3) the $(i,j)$ summand has dimension $1$ if $W_i \cong W_j'$ and $0$ otherwise. For each irrep $W$ there are $m_W(V)\,m_W(V')$ pairs $(i,j)$ with $W_i \cong W \cong W_j'$, giving the formula. Taking $V' = V$ gives $\dim\Hom_G(V,V) = \sum_W m_W(V)^2$, which equals $1$ exactly when a single irrep occurs, with multiplicity $1$.

3. Let $X$ be a $G$-set with $|X| \geq 2$. We say $G$ acts doubly transitively on $X$ if for any $x \neq y$ and $x' \neq y'$ in $X$ there is some $g \in G$ with $gx = x'$ and $gy = y'$.

   Prove that the following are equivalent:

   1. $G$ acts doubly transitively on $X$;
   2. $G$ has exactly two orbits on $X \times X$;
   3. $\CC X \cong \triv \oplus W$ where $W$ is irreducible and $W \not\cong \triv$.

   Show that in this case $W$ may be taken to be $\{\sum_x c_xe_x : \sum_x c_x = 0\}$.

   Solution

   The diagonal $\Delta = \{(x,x)\}$ and its complement are both unions of orbits, and both are nonempty since $|X| \geq 2$. Double transitivity says precisely that $X \times X \setminus \Delta$ is a single orbit; it also forces $G$ to be transitive (given $x \neq x'$, choose $y \neq x$ and $y' \neq x'$, and map $(x,y) \mapsto (x',y')$), so $\Delta$ is a single orbit as well. Conversely two orbits means $\Delta$ and its complement are each an orbit. So (a)$\iff$(b).

   By parts (1) and (2), the number of orbits on $X \times X$ is $\sum_W m_W(\CC X)^2$. If this is $2$, then exactly two irreps occur, each with multiplicity $1$. One of them is $\triv$, since $m_\triv(\CC X) = \dim(\CC X)^G$ is the number of orbits on $X$, which is at least $1$; this gives (c). Conversely, (c) gives $\sum_W m_W(\CC X)^2 = 1 + 1 = 2$. So (b)$\iff$(c).

   The standard inner product on $\CC X$ is $G$-invariant since $G$ permutes the orthonormal basis $\{e_x\}$. Since $G$ is transitive, $(\CC X)^G = \Span(e_X)$ with $e_X = \sum_x e_x$, and its orthogonal complement is the sum-zero subspace, which is a $G$-invariant complement to $\triv$, hence isomorphic to $W$ by Problem 6.13.

4. Applications.

   1. Prove that for $n \geq 2$ the standard representation $V_{n-1} := \{(c_1, \ldots, c_n) \in \CC^n : \sum_i c_i = 0\}$ of $S_n$ is irreducible. (For $n = 3$ this is the plane $V_2$ from the beginning of this problem set.)
   2. Prove that for $n \geq 4$, $V_{n-1}$ remains irreducible when regarded as a representation of the alternating group $A_n$. What goes wrong when $n = 3$?
   3. Let $p$ be a prime and let $G = \mathrm{Aff}(\FF_p)$ be the group of functions $\FF_p \to \FF_p$ of the form $x \mapsto ax + b$ with $a \in \FF_p^\times$ and $b \in \FF_p$, under composition. Determine all irreducible representations of $G$ up to isomorphism: prove that there are exactly $p$ of them, namely $p - 1$ of dimension $1$ and one of dimension $p - 1$. Hint: Look at the map $G \to \FF_p^\times$ sending $x \mapsto ax + b$ to $a$, and recall the remark following Problem 6.16. (When $p = 3$, check that $G \cong S_3$ and you recover Problem 6.16(3).)
   4. Let $n \geq 4$ and let $X$ be the set of $2$-element subsets of $[n]$, with the natural action of $S_n$. Prove that $\CC X \cong \triv \oplus V_{n-1} \oplus U$ where $U$ is an irreducible representation of $S_n$ of dimension $n(n-3)/2$, not isomorphic to $\triv$ or $V_{n-1}$. In particular, this produces a $2$-dimensional irrep of $S_4$ and a $5$-dimensional irrep of $S_5$. Hint: Use part (1) to compute $\dim\Hom_G(\CC X, \CC X)$ and $\dim\Hom_G(\CC[n], \CC X)$.
   Solution

   (a) $S_n$ acts doubly transitively on $[n]$: given $i \neq j$ and $k \neq \ell$, extend $i \mapsto k$, $j \mapsto \ell$ by any bijection $[n] \setminus \{i,j\} \to [n] \setminus \{k,\ell\}$ to get a permutation. Apply part (3).

   (b) Given $i \neq j$ and $k \neq \ell$, choose $\sigma \in S_n$ as in (a). If $\sigma$ is odd, since $n \geq 4$ there are two elements $r, s \notin \{k, \ell\}$, and $(r\,s)\sigma$ is even and still sends $i \mapsto k$, $j \mapsto \ell$. So $A_n$ is doubly transitive and part (3) applies. For $n = 3$, $A_3 \cong C_3$ is abelian, so by Problem 6.12 its irreps are $1$-dimensional and $V_2$ must split; indeed $A_3$ has three orbits on $[3] \times [3]$ (the diagonal, and the two cyclic orientations $\{(1,2),(2,3),(3,1)\}$ and $\{(2,1),(3,2),(1,3)\}$).

   (c) $|G| = p(p-1)$. $G$ acts doubly transitively on $\FF_p$: given $x \neq y$ and $x' \neq y'$, the equations $ax + b = x'$, $ay + b = y'$ have the solution $a = (x'-y')/(x-y) \neq 0$, $b = x' - ax$. By part (3), $\CC\FF_p \cong \triv \oplus W$ with $W$ irreducible of dimension $p - 1$. Next, $(x \mapsto ax+b) \circ (x \mapsto a'x + b') = (x \mapsto aa'x + (ab' + b))$, so $\pi : G \to \FF_p^\times$, $(x \mapsto ax+b) \mapsto a$, is a surjective homomorphism. Since $\FF_p^\times$ is abelian of order $p - 1$, it has $p - 1$ pairwise non-isomorphic irreps, each a homomorphism $\chi : \FF_p^\times \to \CC^\times$. The composites $\chi \circ \pi$ are $1$-dimensional representations of $G$, and they are pairwise non-isomorphic: an isomorphism between $1$-dimensional representations is multiplication by some $c \neq 0$, which forces $\chi \circ \pi = \chi' \circ \pi$ as functions, hence $\chi = \chi'$ since $\pi$ is surjective. Now $(p-1)\cdot 1^2 + (p-1)^2 = p(p-1) = |G|$, so by Problem 6.16(2) these are all the irreps of $G$. (When $p > 2$, $W$ is not among the $1$-dimensional ones by dimension; when $p = 2$, $G \cong C_2$ and $W$ is the sign representation, which is the one $1$-dimensional representation not of the form $\chi \circ \pi$.)

   (d) Orbits of $S_n$ on $X \times X$ are classified by $|A \cap B| \in \{2, 1, 0\}$, and all three occur since $n \geq 4$; so $\sum_W m_W(\CC X)^2 = 3$, and $\CC X$ is a sum of three pairwise non-isomorphic irreps, each with multiplicity $1$. One is $\triv$ since $S_n$ is transitive on $X$. Orbits of $S_n$ on $X \times [n]$ are classified by whether $i \in A$, so by parts (1) and (2), using $\CC[n] \cong \triv \oplus V_{n-1}$ from (a), \[ 2 = \dim\Hom_G(\CC[n], \CC X) = m_\triv(\CC X) + m_{V_{n-1}}(\CC X) = 1 + m_{V_{n-1}}(\CC X). \] So $V_{n-1}$ is the second irrep, and the third $U$ has dimension $\binom{n}{2} - 1 - (n-1) = n(n-3)/2$.