from numbers import Number from sympy import Matrix, PermutationMatrix, det, eye, sqrt from sympy.combinatorics import Permutation from chapter_2 import trace
For me Character Theory was rather new when I accountered the appendix for the first time. I found it hard to learn it from this Appendix so I searched for alternative resources. I think Chapters 1 and 2 of (William Fulton and Joe Harris, 2004) constitutes a gentle introduction to the topic. I only skimmed over it, so I am not sure, but what I know is that this made the topic much clearer to me.
In this section I briefly summarize how I learned the very basics of this nice theory. I refer to the exercises when appropriate. It duplicates a lot of things from the (Nielsen, Michael A. and Chuang, Isaac L., 2011). But in my oppinion certain crucial things are missing in the book. To make it self contained I decided to repeat certain things.
Let \((G,\cdot,e)\) be a group. A matrix representation of \(G\) is a homomorphism of groups \(\rho:G\to M\) where \(M\) is a group of matrices over some complex vector space \(V\) (other ground fields are possible but we do not care here). Homomorphism just means
\[ \forall g,h: \rho(gh) = \rho(g)\rho(h) \; \text{ and } \; \rho(g\inv) = \rho(g)\inv \; \text{ and } \; \rho(e) = I . \]
A matrix representation is called irreducible if it has no non-trivial invariant subspaces \(W\); non-trivial meaning \(W\notin\{0,V\}\). Invariant means \(\rho(g)W\,\subseteq\,W\) for all \(g\).
A matrix representation is called indecomposable if \(\rho\) cannot be written as a direct sum \(\rho_1\oplus\rho_2\) over non-trivial subspaces \(V_1\oplus V_2=V\). It is clear that irreducible matrix groups are also indecomposable. The reverse direction also holds for finite groups (see (William Fulton and Joe Harris, 2004) Proposition 1.5). The proof is not very difficult once the fact that representations of finite groups are equivalent to unitary groups is established.
Let \(\rho\) be a finite-dimensional matrix representation over \(\CC\). The character of \(\rho\) is \(\chi_\rho:G\to\CC\) given by:
\[ \chi_\rho(g) = \trace{\rho(g)} . \]
The character is called irreducible if \(\rho\) is irreducible. The degree of the character is the dimension of the vector space.
Characters are a special case of the so called class functions, these are functions \(\alpha:G\to\CC\) such that
\[ \forall g,h: \; \alpha(h^{-1} g h) = \alpha(g) . \]
For characters this holds due to \(\trace{AB}=\trace{BA}\).
Basic properties of characters are proved in exercise A2.11. The proof shows that for a finite group \(\chi(g)\) is a sum of \(r\)th roots of unity where \(r\) is the order of \(g\).
Two representations are called equivalent if they are isomorphic and the isomorphism preserves the corresponding characters. A linear map \(S:V\to W\in\hom(V,W)\) is called G-linear if
\[ \forall g: \rho_W(g) \, S = S \, \rho_V(g) . \]
Let us denote by \(\hom(\rho^V,\rho^W)\), or \(\hom_G(V,W)\) (G-homomorphisms), the subset of those homomorphisms between \(V\) and \(W\) (\(\hom(V,W)\)) which are G-linear. This makes the class of representations of \(G\) into a category.
Clearly two representations are equivalent iff there exists a G-isomorphism between them.
Schur's Lemma will tell us that up to a scalar factor there is at most one non-zero G-homomorphisms between two irreducible finite dimensional representations, which is an isomorphism if it exists.
A matrix group is called unitary if every matrix is unitary. In exercise A2.12 it is shown that every representation of a finite group is equivalent to a unitary representation. The proof shows that the transformation is essentially a change of scalar product:
\[ \rho(g) \mapsto \sqrt{p} \rho(g) \sqrt{p}\inv , \]
where \(p\) is some suitably chosen positive definite matrix. The technique to obtain \(p\) via averaging is standard in Character Theory.
Assuming we have a representation on certain vector spaces \(V\), \(W\) we can construct new ones like in the following listing. Note that sometimes we write \(gv\) instead of \(\rho_V(g)v\) if we are not at risk of ambiguity. Just for this section we briefly allow a general ground field \(\KK\) instead of \(\CC\). I think this aids understanding the construction for dual spaces - in my opinion.
Tensor products \(V\otimes W\):
\[ g(v\otimes w) := gv \otimes gw . \]
Direct sums \(V\oplus W\):
\[ g(v\oplus w) := gv \oplus gw . \]
Homomorphism spaces \(\hom(V, W)\):
\[ g\phi = g \circ \phi \circ g\inv \]
Dual spaces \(V^*\):
\[ \rho_{V^*}(g) = \rho_V(g\inv)^\dagger . \]
The definition for dual spaces is natural since it is a consequence from the natural requirement to preserve the natural dual pairing:
\[ \langle gv^*, gv \rangle_{V^*,V} = \langle v^*, v \rangle_{V^*,V} . \]
The formula for homomorphisms is motivated by \(\hom(V,W)=V^*\otimes W\)
\begin{align*} \rho_{V^*\otimes W}(g) \langle v^*, \cdot \rangle w &= \langle \rho_{V^*}(g)v^*, \cdot \rangle \rho_W(g)w \\ &= \langle \rho_{V}(g\inv)^\dagger v^*, \cdot \rangle \rho_W(g)w \\ &= \langle v^*, \rho_V(g\inv)(\cdot) \rangle \rho_W(g)w \\ &= \rho_{\hom(V,W)}(g) \langle v^*, \cdot \rangle w . \end{align*}and is consistent with \(V^*=\hom(V,\KK)\).
\begin{align*} \rho_{\hom(V,\KK)}(g) \langle v^*, \cdot\rangle &= \rho_\KK(g) \langle v^*, \rho_V(g\inv)(\cdot)\rangle \\ &= \langle \rho_V(g\inv)^\dagger v^*, \cdot\rangle \\ &= \rho_{V^*}(g) \langle v^*, \cdot\rangle . \end{align*}Moreover the dual representation behaves well for unitary representations with the natural identification of the dual space with the Hilbert space itself: \(\rho^*=\rho\) in this case.
Let \(G\) be a group and \(\rho_V\), \(\rho_W\) two irreducible representations on non-trivial
complex vector spaces \(V\) and \(W\). Let \(S:V\to W\) be a G-linear map, the latter meaning:
\[ \forall g: \rho_W(g) \, S = S \, \rho_V(g) . \]
Then either
Moreover, if \(\rho_V=\rho_W\) and the vector spaces are finite-dimensional, necessarily \(S=\alpha I\) for some \(\alpha\in\CC\). If \(\rho_V\neq\rho_W\) are finite-dimensional and \(S_1\), \(S_2\) are two isomorphisms as above then each of them is a scalar multiple of the other one.
PROOF: Let \(N\subseteq V\) and \(R\subseteq W\) the kernel (null-space) and image (range) of \(S\). Clearly those are invariant under the respective representations of \(G\). By irreducibility we have:
This leads to four cases two of which are impossible (both zero-space or both full-space) since \(V\) and \(W\) are non-trivial. The other two cases are:
This shows the first part. Now consider the second part where (among other things) \(V=W\) is assumed. Since \(\CC\) is algebraically closed and the vector spaces are finite dimensional \(S\) must have an eigenvalue \(\alpha\). Clearly \(S-\alpha\) satisfies the G-linearity in place of \(S\) too. By the first part and since \(S-\alpha\) is no isomorphism we must have \(S=\alpha\).
The final part follows from the second part by considering the G-linear mappings composed of G-linear mappings from \(V\) to \(W\) and back from \(W\) to \(V\). QED.
Let \(V\) be a complex representation of a finite group \(G\). Then the vector space \(V\) decomposes into irreducible sub-representations
\[ V = V^{\oplus a_1}_1 \oplus \ldots \oplus V^{\oplus a_n}_n \]
with distinct (irreducible) \(V_i\). Moreover the \(V_i\) and the \(a_i\) are unique. If the representation is unitary the decomposition is orthogonal.
I could not find a proof of the complete statement which I could understand. So I give my own here.
PROOF: We may assume that the representation is unitary (see above).
If \(V\) is not already reducible there must be a non-trivial invariant subspace \(U\). Since the representation is unitary the orthogonal complement \(U^\perp\) is invariant too. Hence we have the decomposition
\[ V = U \oplus U^{\perp} . \]
The existence now follows by induction on the dimension of \(V\) and the fact that one-dimensional representations are always irreducible. This concludes the existence part of the proof.
For the uniqueness consider another decomposition
\[ V = W^{\oplus b_1}_1 \oplus \ldots \oplus W^{\oplus b_m}_m . \]
Note that the identity induces an isomorphism
\[ V^{\oplus a_1}_1 \oplus \ldots \oplus V^{\oplus a_n}_n \to W^{\oplus b_1}_1 \oplus \ldots \oplus W^{\oplus b_m}_m . \]
Let us denote by \(\hom_G(V,W)\) the G-linear maps between \(V\) and \(W\). Note that
\[ \hom_G(V, V) = \bigoplus_{i=1}^n \bigoplus_{j=1}^m \hom_G(V_i, W_j)^{\oplus a_i b_j} . \]
This holds also for \(\hom_G\) replaced by \(\hom\). In fact, this statement is analogous to the fact that linear maps between finite dimensional vector spaces can be represented by matrices.
Now suppose that for some \(i\) the \(V_i\) is not equivalent to any of the \(W_j\). Then this together with Schur's Lemma implies that \(V_i\) is mapped to \(0\) by the identity map - contradiction. By symmetry this implies that \(n=m\) and \(V_i=W_{\pi(i)}\) for some permutation \(\pi\). Without loss of generality \(\pi=\mathrm{id}\).
Again by Schur's lemma we thus have \(\hom(V_i,W_j)=0\) for \(i\neq j\) and hence:
\[ \hom_G(V, V) = \bigoplus_{i=1}^n \hom_G(V_i, W_i)^{\oplus a_i b_i} . \]
Hence the identity on \(V\) induces a G-isomorphism between \(V_i^{a_i}\) and \(W_i^{b_i}\). Since the dimensions of \(V_i\) and \(W_i\) are the same (by equivalence) this implies \(a_i=b_i\). QED.
Recall that the class functions are constant on all conjugacy classes
\[ \mathrm{Cl}(a) = \{g a g\inv; g\in G \} . \]
Hence for a finite group the space of class functions is a \(k\) dimensional vector space where \(k\) is the number of different conjugacy classes (the indicator functions of the single conjugacy classes form a basis).
Using the following scalar product, the vector space turns into a Hilbert Space:
\[ \langle \alpha, \beta \rangle = \frac{1}{\abs{G}} \sum_{g\in G} \alpha(g)^* \beta(g) . \]
It turns out that the irreducible characters are an orthonormal basis of this Hilbert Space. This should be shown in exercise A2.15. This exercise however bases the proof on a more difficult result so it does not really help to understand this nice result. For a direct proof have a look into (William Fulton and Joe Harris, 2004), Chapter 2.2. I recommend to read the proof, it is really nice. You can also try to find it on your own based on the following hints:
The map
\[ p = \frac{1}{\abs{G}} \sum_{g\in G} g \]
is a projection from \(V\) to \(V^G:=\{v\in V; \forall g: gv=v\}\).
Hence
\[ \dim V^G = \chi_V(p) = \frac{1}{\abs{G}} \sum_{g\in G} \chi_V(g) . \]
As a corollary of the above we see that the number of distinct irreducible characters is equal to the number of conjugacy classes.
With the notation of decomposition of representations we see that a general character decomposes like this into irreducible characters:
\[ \chi_V = \sum_{i=1}^n a_n \chi_{V_i} \]
In particular we deduce that a character is irreducible iff its norm is \(1\) (all other characters have a larger norm).
As special case consider the characters \(\chi_p(j)=\exp(2\pi\ii jp/N)\) of the Abelian group \(\ZZ_N\). The general theory shows that these functions are a basis of \(\CC^N\). This basis is orthogonal if we scale the scalar product on \(\CC^N\) by \(1/\sqrt{N}\) (as in the formula for general groups). Note that the orthonormality relation is equivalent to the well known
\[ \sum_{j=0}^{N-1} e^{2\pi\ii jp/N} = \begin{cases} N & \text{if } p=0 \\ 0 & \text{otherwise.} \end{cases} \]
Of course the latter can also be seen from the formula for geometric sums.
Let \(G\) be a finite group and \(\hat{G}\) its irreducible representations (one example for each isomorphy class). Then for \(\rho,\sigma\in\hat{G}\) (and for any choice of basis):
\[ \sum_{g\in G} \rho(g\inv)_{ij} \sigma(g)_{kl} = \frac{\abs{G}}{d_\rho} \delta_{il} \delta_{jk} \delta_{\rho \sigma} . \]
PROOF: Let \(X\) be a matrix with compatible dimensions for the following formula:
\[ P := \sum_{g\in G} \rho(g\inv) X \sigma(g) . \]
Observe that \(P\) is G-linear. Hence \(P\) is either zero or a multiple of the identity depending on whether \(\rho=\sigma\) holds. Let us set
\[ X_{ab} = \delta_{aj} \delta_{kb} . \]
In that case:
\[ P_{il} := \sum_{g\in G} \rho(g\inv)_{ij} \sigma(g)_{kl} . \]
CASE \(\rho\neq\sigma\): Then \(P=0\) and the formula follows.
CASE \(\rho=\sigma\): Then \(P=\lambda I\). By taking the trace we get the value of \(\lambda\)
\[ \lambda d_\rho = \sum_g \trace{X} = \abs{G} \cdot \delta_{jk} . \]
Hence the claim follows in this case too. QED.
In the following let \(N=\abs{G}\) and let the representations be unitary. Let \(V_\rho\) be the underlying Hilbert space of \(\rho\). Order the elements of \(\hat{G}\) in some way and order the numbers in the matrices like this:
\begin{bmatrix} 1 & 2 & \ldots & d_\rho \\ d_\rho + 1 & d_\rho + 2 & \ldots & 2d_\rho \\ \vdots & \vdots & \vdots & \vdots \\ (d_\rho-1)d_\rho + 1 & (d_\rho-1)d_\rho + 2 & \ldots & d_\rho^2 \end{bmatrix}The exact ordering is absolutely unimportant but it is necessary to have one. Let us define the Fourier transform as the representation which is a direct sum of all irreducible representations:
\[ \rho^F = \bigoplus_{\rho\in\hat{G}} \sqrt{\frac{d_\rho}{N}} \; \rho . \]
Notice that with the above ordering for fixed \(\rho\), \(i\), and \(j\) (\(N\) possible combinations) each \((\rho(g)_{ij})_{g\in G}\) can be identified with a vector in \(\CC^N\). The fundamental formula states that these vectors are an orthonormal basis of \(\CC^N\).
Let us also order the elements of \(G\) in some way. Then \(\rho^F\) can be identified with a matrix in \(\CC^{N\times N}\). By the previous paragraph it is a unitary matrix since its rows are orthonormal (taking the \(\rho\in\hat{G}\) as the row index).
But as a unitary matrix \(\rho^F\) has orthonormal columns too! So the fundamental formula has a companion which looks like this:
\[ \frac{1}{N} \sum_\rho d_\rho \sum_{ij} \rho(g)_{ij}^* \rho(h)_{ij} = \delta_{gh} \]
Keep in mind that this is only valid for unitary representations. Hence \(\{\rho^F(g)\}_{g\in G}\) is another orthonormal basis of \(\CC^N\).
For a unital ring \(R\) (we will only consider the rings \(\CC\) and \(\ZZ\)) the group ring \(R[G]\) can be defined as the set of all formal linear combinations of the form
\[ \sum_{g\in G} c_g \, g \text{ where } c_g \in R . \]
This set has naturally the structure of a free module. If you do not know what a free module is, that is not very important. Just remember that with free module we mean this "interpretation" (as formal linear combinations) of \(R[G]\). Actually the module is even a (complex) vector space in this case and \(G\) is a basis (the latter being essentially what free means). Further below we will give another interpretation as a ring.
In the section on the fundamental formula we have seen that \(\rho^F\) can be interpreted as a mapping \(G\to\CC^N\) and that \(\{\rho^F(g)\}_{g\in G}\) is an orthonormal basis of \(\CC^N\). Hence it makes sense to extend it by linearity to \(\CC[G]\) via:
\[ \rho^F\left( \sum_{g\in G} c_g \, g \right) := \sum_{g\in G} c_g \, \rho^F(g) . \]
This mapping is unitary by what we just said if we endow the vector space \(\CC[G]\) with its natural norm (making it into a Hilbert space):
\[ \norm{\sum_{g\in G} c_g \, g} = \sqrt{\sum_{g\in G} \abs{c_g}^2} . \]
Let us give another interpretation of \(R[G]\) - as the ring of functions \(f:G\to\CC\) which can be denoted as \(R^G\). Identifying \(f(g)=c_g\) the elements of \(R[G]\) have the form
\[ \sum_{g\in G} f(g) \, g . \]
Lets equip \(R^G\) with an addition operation \(+\) and a multiplication operation \(*\), making it into a ring \((R^G,+,*)\) which is consistent with the addition and multiplication in the free module interpretation. It turns out that the two relevant operation are "ordinary" addition
\[ (f+g)(x) := f(x) + g(x) , \]
and convolution
\[ (f*g)(x) := \sum_{u\in G} f(u) g(u\inv x) = \sum_{v\in G} f(x v\inv) g(v) . \]
For addition this should be obvious so let us just show it for the convolution:
\[ \left( \sum_{u\in G} f(u) \, u \right) \left( \sum_{v\in G} g(v) \, v \right) = \sum_x \sum_{uv=x} f(u)g(v) x = \sum_x \sum_{u} f(u)g(u\inv x) x . \]
In the section on the group ring \(\CC[G]\) we have seen that \(\rho^F\) naturally extends to \(\CC[G]\) and yields a representation as linear matrices. In fact, we have seen that we get all linear maps which respect the invariant subspaces defined by the decomposition into irreducible representations.
Let us now restrict \(\rho^F\) to \(\ZZ[G]\). That is, we only use integer coefficients in the formal linear combinations. What do we gain from this? We will show that the eigenvalues of the corresponding linear maps are algebraic integers. This will be useful in exercise A2.14.
The algebraic numbers are defined as all complex numbers which are a root of some polynomial with rational coefficients. Likewise algebraic integers are defined as all complex numbers which are a root of some polynomial with integer coefficients and whose leading coefficient is \(1\) (this is called a monic polynomial).
Clearly rational numbers are algebraic numbers. Similarly integers are algebraic integers. It is also not hard to see that a rational number which is an algebraic integer is already an integer (consider \(p/q\) with coprime \(p\), \(q\) and look what the highest monomial does to the denominator).
THEOREM: Algebraic integers are a ring and algebraic numbers are a field.
PROOF: We have to show that \(a+b\), \(ab\), and \(-a\) are algebraic integers/numbers if \(a\) and \(b\) are and that \(a\inv\) is an algebraic number too if \(a\) is a non-zero algebraic number. For the existence of the additive and multiplicative inverses this simply follows from considering \(p(-x)\) and \(x^np(x\inv)\) respectively if \(p\) is a polynomial of degree \(n\) with root \(a\).
Note that any polynomial is also the characteristic polynomial of a matrix (see companion matrix). Let \(A\) and \(B\) be matrices with integer or rational coefficients and eigenvalues \(a\) and \(b\) respectively. Let \(u\), \(v\) be the corresponding eigenvectors. Then \(A\otimes B\) and \(A\otimes I+I\otimes B\) have eigenvalues \(ab\) and \(a+b\) respectively. The corresponding eigenvectors are \(u\,\otimes\,v\) both times. QED.
THEOREM: Each element in \(\\Z[G]\) satisfies a monic polynomial with integer coefficients ("satisfies" means \(p(\alpha)=0\)). In particular the eigenvalues of the matrices in \(\rho^F(\ZZ[G])\) are algebraic integers.
PROOF: A proof can be found in Chapter VII Extensions of Rings §1 of (Lang, Serge, 2002) (The book seems to be very well structured I found the proof within seconds upon first opening it). I give essentially the same proof, but formulated a little bit differently. Lang's book goes the abstract way, I instead try to rely on things which I remember from my linear algebra course (which is basically the same but sounds a bit less technical).
Let \(\alpha,x\in\ZZ[G]\) be arbitrary. Let us write \(\sum_g x_g g\) (with \(x_g\in\ZZ\)). Note that \(\alpha\) naturally acts on \(\ZZ[G]\) by
\[ x \mapsto \alpha x , \]
where we use the fact that \(\ZZ[G]\) can be interpreted as a ring. Note that this is essentially the regular representation of \(\ZZ[G]\)). Let us define the matrix \(A\) with coefficients \(a_{gh}\in\ZZ\) by:
\[ \alpha g = \sum_{h\in G} a_{gh} h \text{ for } g\in G . \]
Because \(\CC[G]\) is a vector space the coefficients are indeed uniquely defined by this. Observe
\[ \alpha x = \sum_{g,h} x_g a_{gh} h . \]
Hence the action of \(\alpha\) on the module \(\ZZ[G]\) (or the vector space \(\CC[G]\)) can be described by the matrix \(A\) which acts by right matrix multiplication:
\[ (x_g)_{g\in G} \mapsto (x_g)_{g\in G} A . \]
Except for the unusual index space this is precisely the type of math we know from our linear algebra course (one could enumerate the elements of \(G\) to have natural numbers as usual). The characteristic polynomial \(p(\lambda)=\det(\lambda-A)\) is monic, of degree \(N\), and has only integer coefficients. By the Caley-Hamilton theorem \(A\) satisfies this polynomial (that is, \(p(A)=0\)).
The regular representation (which essentially maps \(\alpha\) to \(A\)) is faithful. Hence \(p(\alpha)=0\) too. QED.
The Fourier transformation is already defined here. But let us re-introduce it with slightly enhanced notation which is closer to what we know from the standard case. For \(f\in\CC^G\) let
\[ \hat{f} := \rho^F\left( \sum_{g\in G} f(g) \, g \right) := \sum_{g\in G} f(g) \, \rho^F(g) . \]
By the chapter on the fundamental formula we can identify \(\hat{f}\) with a vector \(\CC^N\), which is the set of functions from \(\{1,2,\ldots,N\}\) to \(\CC\). By the same chapter the mapping \(\FT:f\mapsto\hat{f}\) is unitary.
Let \(n(\rho,i,j)\in\{1,\ldots,N\}\) be index in the vector \(\hat{f}\) according to the ordering of the irreducible representation \(\rho\) and the matrix indices \(i,j\in{1,\ldots,d_\rho}\). Then:
\[ \hat{f}(n(\rho,i,j)) = \sqrt{\frac{d_\rho}{N}} \sum_{g\in G} f(g) \, \rho(g)_{ij} . \]
This shows that our definition is consistent with the one given in the book:
\[ \hat{f}(\rho) = \sqrt{\frac{d_\rho}{N}} \sum_{g\in G} f(g) \, \rho(g) . \]
Sometimes the square root above is convenient (for example if we want the Fourier transform to be unitary) but sometimes it is better to replace it by \(1\). Let \(\FT_1\) the variant where this is done.
Observe that we can identify \(\CC^N\) with \(\CC[Z_N]\) and this in turn as a ring (of functions defined on \(\{1,\ldots,N\}\)) with ordinary vector addition as addition and with component-wise multiplication as the multiplication operation. Observe
\[ \FT_1f(n) \FT_1g(n) = \FT_1(f*g)(n) . \]
In fact, this follows by the same reasoning which justified convolution as the "right" multiplication on \(\CC^G\) to be compatible with the free module \(\CC[G]\).
Hence the Fourier transform \(\FT_1\) is a ring isomorphism from \((\CC^G,+,*)\) to \((\CC^N,+,\cdot)\).
By a direct calculation (as in the book) we can see that
\[ f(g) = \frac{1}{\sqrt{N}} \sum_{\rho\in\hat{G}} \sqrt{d_\rho} \, \trace{\hat{f}(\rho)\rho(g\inv)} \]
yields \(\FT\inv\).
In the Abelian case the notational burden simplifies heavily. As always let \(G\) be a finite group, \(N=\abs{G}\). Note that the set \(\hat{G}\) of irreducible representations is the same as the set of irreducible characters since all irreducible representations of an Abelian group are one-dimensional (see exercise A2.23).
\[ \hat{f}(\chi) = \frac{1}{\sqrt{N}} \sum_{g\in G} f(g) \chi(g) \text{ where } \chi \in \hat{G} . \]
The inverse Fourier transform is
\[ f(g) = \frac{1}{\sqrt{N}} \sum_{\chi\in\hat{G}} \hat{f}(\chi) \chi(g\inv) \text{ where } g \in G . \]
Using Exercise A2.11(5) or more precisely the fact that \(\chi(g)\) is a root of unity (whose order divides \(N\)) we can show that \(\hat{G}\) can be identified with the Abelian group \(\hom(G,S^1)\) (group homomorphisms from \(G\) to the unit circle \(S^1\subseteq\CC\)). See also Pontryagin duality at wikipedia. That \(\hat{G}\) is a sub-group should be clear from what was already said. Equality can be shown from the (non-trivial) fact that finite Abelian groups are isomorphic to a direct sum of cyclic groups (for a proof see libretexts.org).
Cyclic groups in turn are (easily seen to be) isomorphic to \(\ZZ_n\) for which it is easy to see that \(\hom(\ZZ_n,S^1)\) has exactly \(n\) elements. In fact, it is easy to see that the values of a \(\chi\in\hom(G,S^1)\) must be \(n\)th roots of unity. From this and the functional equation
\[ \chi(a+b) = \chi(a)\chi(b) \in S^1 \subseteq \CC \]
we see that the \(n\) irreducible characters of \(\ZZ_n\) are the only possible elements of \(\hom(\ZZ_n,S^1)\):
\[ \chi_k(j) = e^{-2\pi kj/n} . \]
Compare this with exercise A2.23.
Let \(G=H\oplus K\) be a direct sum of two finite Abelian groups. It is not hard to see that products of the irreducible characters of \(H\) and \(K\) are the irreducible characters of \(G\):
\[ \chi_G^{ij}(h, k) = (\chi_H^i \otimes \chi_K^j)(h,k) = \chi_H^i(h) \chi_K^j(k) . \]
Let \(f:G\to\CC\) be a product:
\[ f(h,k) = f_1(h) f_2(k) . \]
By definition of the Fourier transform on Abelian groups we have:
\[ \FT_G f(\chi_G^{ij}) = \frac{1}{\sqrt{\abs{G}}} \sum_{h,k} f(h,k) \chi_H^i(h) \chi_K^j(k) . \]
Since \(f\) is a product, the sum factors into a sum over \(h\) and a sum over \(k\). Hence the Fourier transform commutes with tensor products in the following sense
\[ \FT_G (f_1 \otimes f_2) = (\FT_H f_1) \otimes (\FT_K f_2) . \]
Now, let \(f:G\to\CC\) be a function which is invariant with respect to \(K\), that is:
\[ f(h, k) = f(h, 0) . \]
This is clearly a special case of a product with second factor being just the constant function \(1\). By the orthonormality relation for irreducible characters we have
\[ \FT_K (k\mapsto 1)(\chi_K^j) = \sqrt{\abs{K}} . \]
Hence for \(K\)-invariant functions \(f\) we have
\[ \FT_Gf(\chi_G^{ij}) = \begin{cases} \sqrt{\frac{\abs{K}}{\abs{H}}} (\FT_H f(\cdot,0))(\chi_H^i) & \text{if } j=0 \\ 0 & \text{otherwise.} \end{cases} \]
Recall that abelian groups are direct sums of cyclic groups:
\[ G = \bigoplus_{i=1}^n \ZZ_{r_i} . \]
In fact, one can acutally choose the \(r_i\) to be prime powers (see libretexts.org). The decomposition is unique in the sense that the multi-set of the \(r_i\) is unique if we require them to be prime-powers. It is useful to know that \(\ZZ_n\oplus\ZZ_m\cong\ZZ_{nm}\) if \(n\) and \(m\) are coprime.
It is very important to note that some of the \(r_i\) can be equal. For example, there are two non-isomorphic abelian groups of order 4: \(\ZZ_4\) and \(\ZZ_2\oplus\ZZ_2\). Also note that the Fourier transform on \(\ZZ_4\) is the "standard" discrete Fourier transform while the Fourier transform on \(\ZZ_2\oplus\ZZ_2\) is the Hadamard transform \(H^{\otimes 2}\).
From a previous section we see that
\[ \FT_G = \bigotimes_{i=1}^n \FT_{\ZZ_{r_i}} . \]
That is, the Fourier transform on an abelian group is just a product of standard Fourier transforms. Equivalently one can say that the set of irreducible characters on \(G\) are given by:
\[ \chi_l(g) = \exp\left( 2\pi\ii \sum_{i=1}^n l_i g_i / r_i \right) \text{ for } l\in G . \]
Note that \(\chi_{l+h}(g)=\chi_l(g)\chi_h(g)\) and \(\chi_{-l}(g)=\chi_l(g)^\dagger\). In particular \(\hat{G} \cong G\). I.e. both groups are isomorphic. Also note that this isomorphism is not canonical. First of all the decomposition of \(G\) is not completely unique. Moreover there are at least two competing conventions whether to put a sign in front of \(2\pi\) in the formula for \(\chi_l(g)\) or not.
There is an interesting relation between Fourier transforms (or irreducible characters) and quotient groups (Notation: \(G/K\)).
Let \(K\) be a subgroup of a finite abelian group \(G\). The character dual of \(K\) is
\[ K^\perp = \{ g \in G | \forall k\in K: \; \chi_g(k) = 1 \} . \]
The character dual is isomorphic to the quotient group:
\[ K^\perp \cong G/K \]
This property is the reason I call it dual:
\[ (K^\perp)^\perp = K \]
We have
\[ \sum_{k\in K} \chi_l(k) = \begin{cases} \abs{K} & \text{if } l \in K^\perp \\ 0 & \text{otherwise.} \end{cases} \]
Let \(f\in\CC^G\) be a function which is constant on cosets of \(K\). Then
\[ \langle f, \chi_l \rangle = 0 \text{ if } l\notin K^\perp . \]
In other words (by the orthonormality property of irreducible characters), \(f\) can be represented as a linear combination of the characters corresponding to \(K^\perp\).
We show the isomorphism \(K^\perp\cong\widehat{(G/K)}\). This is sufficient since the characters of an abelian group are isomorphic to the group itself (\(g\mapsto\chi_g\) is the isomorphism).
The isomorphism \(K^\perp\cong\widehat{(G/K)}\) is given by
\[ h\mapsto(\chi_h^{G/K}:g+K\mapsto\chi_h(g)) \]
This mapping is well-defined precisely because \(h\in K^\perp\). To see that the \(\chi_h^{G/K}\) are indeed irreducible characters it suffices to note that they are group homomorphisms from \(G/K\) to \(S^1\) (c.f. Pontryagin duality). This shows \(K^\perp\subseteq\widehat{G/K}\).
The other direction can be seen from the fact that any \(\chi\in\widehat{G/K}\) give rise to a \(\tilde{\chi}\in\hat{G}\) satisfying \(\tilde{\chi}(k)=1\) for all \(K\). In fact, just set
\[ \tilde{\chi}(g) := \chi(g+K) \]
Clearly this is the reverse of the above mapping. QED.
We have to show that
\[ K = \{ g\in G| \forall h\in K^\perp: \; \chi_g(h) = 1 \} . \]
By the symmetry \(\chi_g(h)=\chi_h(g)\) the inclusion \(K\subseteq(K^\perp)^\perp\) is clear. But by the first part of the Theorem we must have equality due to cardinality reasons. QED.
Let \(1_K\in\CC^G\) be the function which maps any element of \(K\) to \(1\) and any other element to \(0\). Up to the factor \(\abs{K}\) the LHS of what is to prove in part is just the scalar product \(\langle1_K,\chi_l\rangle\).
The fact that \(\langle1_K,\chi_l\rangle=1\) if \(l\in K^\perp\) should be clear.
Now consider the subspace \(S\subseteq\CC^G\) of functions which are constant on cosets of \(K\). Observe that \(f,1_K\in S\). Clearly \(S\cong\CC^{G/K}\) by an isomorphism consistent (in a sense) with the one from the proof of part 1. Hence, \(\{\chi_h|h\in\,K^\perp\}\), which is isomorphic to \(\widetilde{G/K}\) by part 1, is an orthormal basis which precisely spans \(S\). Hence, again by orthonormality of all characters of \(G\) the other ones must have zero scalar product with any element of \(S\) (in particular with \(1_K\)). QED.
The theorem is important for the hidden subgroup problem. The goal of the problem is to find a generating set for some subgroup \(K\) (related to some function \(f\)) of \(G\). The quantum part of the algorithm solving the problem does not directly yield a generating set for \(K\). Instead a generating set \(l^{(1)},\ldots,l^{(J)}\) for \(K^\perp\) as in the theorem is produced (with high probability).
How do we find a generating set for
\[ K = \{ k\in G| \; \forall i: \, \chi_{l^{(i)}}(k) = 1 \} \]
? First let us define \(r=\mathrm{lcd}(r_1,\ldots,r_n)\), \(s_i=r/r_i\) and note that \(K\) is characterized by the system of equations with integer coefficients
\[ \sum_{i=1}^n s_i l_i^{(j)} k_i = 0 \mod r \text{ for } j \in \{1,\ldots,J\} . \]
Defining the matrix \(A=(s_il_i^{(j)})\in\ZZ^{J\times n}\) this can be written as
\[ Ak = 0 \mod r . \]
Let us note one subtle thing here. We silently interpreted \(k_i,l_i\) as elements of \(\ZZ_r\) although they are elements of \(\ZZ_{r_i}\) (and \(r=\prod_ir_i\)). But this is not a problem since \(s_i=r/r_i\) ensures that this does not change the set of solutions.
By the Smith normal form there are invertible matrices \(S\in\ZZ^{J\,\times\,J}\) and \(T\in\ZZ^{n\,\times\,n}\) such that \(D=SAT\) is a diagonal (\(J\,\times\,n\)) matrix. The multi-set of numbers on the diagonal is unique. Without loss of generality we may assume that \(d_i=D_{ii}\) for \(i=1,\ldots,n_0\) are the only non-zero entries. It is easy to find the solutions of
\[ Dk' = 0 \mod r . \]
In fact, if \(n_0=n\), a generating set is just the \(n_0\) values \(k'^{(i)}\) with \(k'^{(i)}_j=\delta_{ij}r/d_i\). If \(n_0 < n\) we have to add some \(k'^{(i)}_j=\delta_{ij}\) for \(i>n_0\). Let \(k^{(i)}=Tk'^{(i)}\) and interpret each \(j\)th entry modulo \(r_j\). This yields a (not necessarily minimal) generating set for \(K\).
Prove the following properties of characters on a finite (and complex) matrix group:
This should be clear since the identity matrix has exactly \(n\) ones on the diagonal.
Recall that the trace is just the sum of all eigenvalues, counted with multiplicity (exactly \(n\) numbers). Let \(\lambda\) be one of the eigenvalues and consider a corresponding eigenvector \(v\). Then
\[ g^a \ket{v} = \lambda^a \ket{v} . \]
Each element of a finite group has finite order. Hence there is an integer \(r\) such that \(g^r=e\) and thus
holds for any eigenvalue. In particular \(|\lambda|=1\). Hence, by the triangle inequality we get the claim. QED.
This follows from the special form of the eigenvalues, together with the fact that the triangle inequality is strict iff all summands are colinear.
We have to show \(\chi(h^{-1}gh)=\chi(g)\). This follows from the cyclicity property of the trace:
\[ \trace{ab} = \sum_{ij} a_{ij} b_{ji} = \sum_{ji} b_{ji} a_{ij} = \trace{ba} . \]
QED.
Since we work on vector spaces of complex numbers, the characteristic polynomial can be factored into linear polynomials:
\[ \prod_{i=1}^n (\lambda_i - g) . \]
This assumes that the eigenvalues (including multiplicities) are \(\lambda_i\). Multiplying this by \(g^{-n}\) shows that the eigenvalues of \(g^{-1}\) are \(\lambda_i^{-1}\) (including multiplicities). From the special form of the eigenvalues we get \(\lambda_i^{-1}=\lambda_i^*\) which implies the claim. QED.
Again by the special form of the eigenvalues the character is just a sum of roots of unity. The latter are algebraic. According to wikipedia algebraic numbers form a field (in fact, they are the algebraic closure of the rational numbers). Hence sums of algebraic numbers are algebraic too. QED.
A unitary matrix group is comprised solely of unitary matrices. Show that every finite matrix group is equivalent to a unitary matrix group. If a representation of a group consists entirely of unitary matrices, we may refer to it as being a unitary representation.
An example of a non-unitary matrix group is generated by
\[ g = \begin{bmatrix} 1 & a \\ 0 & -1 \end{bmatrix} . \]
Clearly \(\langle g \rangle = \{I, g\}\), since \(g^2=I\). Moreover \(g\) is not unitary for any \(a\neq0\). On the other hand \(g\) is diagonalizable (its eigenvalues are \(\pm1\)). Note that the claim of the exercise implies diagonalizability for any representation of a finite group! In fact, equivalence to a unitary group means that there is a G-isomorphism \(h\) such that \(hgh\inv\) is unitary and hence diagonalizable. But if \(hgh\inv\) is diagonalizable the same is true for \(g\).
On the other hand for \(a\neq0\) the following is a generator for a faithful representation of \(\ZZ\) which is not diagonalizable (up to a factor the matrix is already in Jordan normal form):
\[ g = \begin{bmatrix} 1 & a \\ 0 & 1 \end{bmatrix} . \]
Thus a conjugation \(g\mapsto hgh\inv\) won't make this into a unitary group. Hence this representation is not equivalent to a unitary representation.
Let us define the positive semi-definite operator (identifying group elements with their matrix representation)
\[ p = \sum_{h\in G} h^\dagger h . \]
This operator is invertible since \(\bra{u}p\ket{u} > 0\) for any non-zero vector \(u\). By the functional calculus for hermitian matrices we can uniquely define a positive semi-definite operator \(\sqrt{p}\) whose square is \(p\) (if \(p\) is already diagonal just take the square roots of each entry and else apply the spectral theorem first to make it diagonal). The matrix \(\sqrt{p}\) is invertible too.
Now define the mapping \(\phi\) as the conjugation with \(\sqrt{p}\):
\[ \phi: g \mapsto \sqrt{p} g \sqrt{p}^{-1}. \]
It is easy to see that this is an isomorphism of \(G\) to some other matrix group \(G'\). Moreover this matrix group is unitary since every \(g\in G\) acts as a permutation on \(G\) which implies:
\[ \phi(g)^\dagger \phi(g) = \sqrt{p}^{-1} g^\dagger p g \sqrt{p}^{-1} = \sqrt{p}^{-1} \sum_{h\in G} (hg)^\dagger hg \sqrt{p}^{-1} = \sqrt{p}^{-1} p \sqrt{p}^{-1} = I . \]
Since conjugation preserves the trace (exercise A2.11) we are done. QED.
Show that every irreducible Abelian matrix group is one dimensional.
Let \(s\) by an arbitrary element of the group. Since the group is abelian we have:
\[ g s = s g \]
for any element \(g\). By Schur's Lemma we have \(\rho(s)=\alpha_s I\) for some complex number \(\alpha_s\). Since \(s\) was arbitrary we have that any element is of this form. A group of multiples of the identity can clearly only be irreducible if it is one dimensional. QED.
Prove that if \(\rho\) is an irreducible representation of \(G\), then \(|G|/d_\rho\) is an integer.
Let \(\mathcal{C}\) be the set of all (different) conjugacy classes of \(G\). Let \(C\in\mathcal{C}\). Consider
\[ p = \sum_{g\in C} \rho(g) . \]
We will only consider the representation \(\rho\) so let us omit it and write briefly:
\[ p = \sum_{g\in C} g . \]
Note that this map is G-linear, since \(C\) is a conjugacy class (which implies \(C=hCh\inv\)):
\[ ph = \sum_{g\in C} gh = \sum_{g\in C} (hgh\inv)h = hp . \]
By Schur's Lemma there is a \(\lambda_C\in\CC\) such that \(p=\lambda_C I\). Taking the trace we get
\[ \lambda_C = \frac{\abs{C}}{d_\rho}\chi(C) . \]
Here \(\chi\) is the character of \(\rho\) and \(\chi(C)\) is the (only) value \(\chi\) assumes on \(C\) (recall that characters are constant on conjugacy classes, see exercise A2.11(4)).
Now comes the crucial part. Observe that \(p\in\ZZ[G]\). Each element of \(\ZZ[G]\) satisfies a monic polynomial with integer coefficients (monic means that the leading coefficient is \(1\)). Hence \(\lambda_C\) (which satisfies the same polynomial) is an algebraic integer.
Consider
\[ \sum_{C\in\mathcal{C}} \lambda_C \chi(C)^* = \sum_{C\in\mathcal{C}} \frac{\abs{C}}{d_\rho} \abs{\chi(C)}^2 = \frac{N}{d_\rho} \in \QQ \]
The first equality follows from the formula for \(\lambda_C\). The second one from the orthonormality of irreducible characters. The left-hand side is an algebraic integer since \(\lambda_C\) is an algebraic integer (as we have just seen), \(\chi(C)^*\) too (as a root of unity), and algebraic integers are a ring.
Hence \(N/d_\rho\) is an algebraic integer. Clearly it is a rational too. But the only rationals which are algebraic integers are the integers themselves. QED.
Using the Fundamental Theorem, prove that irreducible characters are orthogonal, that is:
\[ \sum_{i=1}^r r_i (\chi_i^p)^* \chi_i^q = \abs{G} \delta_{pq} \quad \text{and} \quad \sum_{p=1}^r (\chi_i^p)^* \chi_j^p = \frac{\abs{G}}{r_i} \delta_{ij} , \]
where \(p\), \(q\), and \(\delta_{pq}\) have the same meaning as in the theorem, and \(\chi_i^p\) is the value the character of the \(p\)th irreducible representation takes on the \(i\)th conjugacy class of \(G\), and \(r_i\) is the size of the \(i\)th conjugacy class.
Consider the first equality. We have
\[ \sum_{i=1}^r r_i (\chi_i^p)^* \chi_i^q = \sum_{g\in G} \chi^p(g)^* \chi^q(g) . \]
Moreover \(\chi^p(g)^*=\chi^p(g\inv)\) by exercise A2.11(5). Hence
\[ \sum_{i=1}^r r_i (\chi_i^p)^* \chi_i^q = \sum_g \sum_{ij} \rho^p(g)\inv_{ii} \rho^q(g)_{jj} . \]
By the fundamental theorem this is zero (as desired) if \(p\neq q\). So let us assume \(p=q\) in the following:
\[ \sum_{i=1}^r r_i (\chi_i^p)^* \chi_i^p = \sum_{ij} \sum_g \rho^p(g)\inv_{ii} \rho^p(g)_{jj} = \sum_{ij} \abs{G} d_{\rho^p}\inv \delta_{ij} = \abs{G} . \]
This proves the first formula. The second formula actually follows automatically from the first one as we will see now. Consider the square matrix \(U\in\CC^{r\times r}\) given by:
\[ U_{ip} = \chi_i^p \cdot \sqrt{\frac{r_i}{\abs{G}}} . \]
Observe that the two statemtents from the exercise are equivalent to the assertion that \(U\) has orthonormal columns or rows respectively (with respect to the standard scalar product on \(\CC^r\)). It is well known that either of these is equivalent to \(U\) being unitary. Hence if one of them holds (as we just proved) the other one holds too. QED.
\(S_3\) is the group of permutations of three elements. Suppose we order these as mapping
123 to: 123; 231; 312; 213; 132, and 321, respectively. Show that
there exist two one-dimensional irreducible representations of \(S_3\), one of which is
trivial, and the other of which is 1, 1, 1, -1, −1, −1, corresponding in order
to the six permutations given earlier. Also show that there exists a two-dimensional
irreducible representation, with the matrices
\[ \left[\begin{matrix}1 & 0\\0 & 1\end{matrix}\right], \; \left[\begin{matrix}- \frac{1}{2} & - \frac{\sqrt{3}}{2}\\\frac{\sqrt{3}}{2} & - \frac{1}{2}\end{matrix}\right], \; \left[\begin{matrix}- \frac{1}{2} & \frac{\sqrt{3}}{2}\\- \frac{\sqrt{3}}{2} & - \frac{1}{2}\end{matrix}\right], \; \left[\begin{matrix}-1 & 0\\0 & 1\end{matrix}\right], \; \left[\begin{matrix}\frac{1}{2} & - \frac{\sqrt{3}}{2}\\- \frac{\sqrt{3}}{2} & - \frac{1}{2}\end{matrix}\right], \; \left[\begin{matrix}\frac{1}{2} & \frac{\sqrt{3}}{2}\\\frac{\sqrt{3}}{2} & - \frac{1}{2}\end{matrix}\right] \]
Verify that the representations are orthogonal.
It is convenient to work with sympy. First let us define the group \(S_3\) and its
representation \(\rho_{\mathrm{perm}}\) as permutation matrices.
group_s3 = [[0, 1, 2], [1, 2, 0], [2, 0, 1], [1, 0, 2], [0, 2, 1], [2, 1, 0]] group_s3 = [Permutation(g) for g in group_s3] s3_perm = [PermutationMatrix(g).as_explicit() for g in group_s3]
\[ \left[\begin{matrix}1 & 0 & 0\\0 & 1 & 0\\0 & 0 & 1\end{matrix}\right], \; \left[\begin{matrix}0 & 1 & 0\\0 & 0 & 1\\1 & 0 & 0\end{matrix}\right], \; \left[\begin{matrix}0 & 0 & 1\\1 & 0 & 0\\0 & 1 & 0\end{matrix}\right], \; \left[\begin{matrix}0 & 1 & 0\\1 & 0 & 0\\0 & 0 & 1\end{matrix}\right], \; \left[\begin{matrix}1 & 0 & 0\\0 & 0 & 1\\0 & 1 & 0\end{matrix}\right], \; \left[\begin{matrix}0 & 0 & 1\\0 & 1 & 0\\1 & 0 & 0\end{matrix}\right] \]
Observe that \(\rho_{\mathrm{perm}}\) is faithful. It is not irreducible: First of all, the character is given by:
[trace(g) for g in s3_perm]
[3, 0, 0, 1, 1, 1]
The norm of this (see Class Functions as a Hilbert Space) is bigger than \(1\) hence it is not irreducible since a character is irreducible iff its norm is \(1\). We can also see this directly by observing that \(V_{\mathrm{triv}}=\CC(1,1,1)\) is an invariant subspace.
The trivial representation exists for every group:
\[ \rho_{\mathrm{triv}}(g) = 1 \in \CC . \]
The non-trivial one-dimensional representation can be defined via:
\[ \rho_{\mathrm{sign}}(g) = \det(\rho_{\mathrm{perm}}(g)) \in \{-1, +1\} \subseteq \CC . \]
It acts as desired:
[det(g) for g in s3_perm]
[1, 1, 1, -1, -1, -1]
Let us briefly mention that this is related to the parity of permutations, and can alternatively calculated by counting the number of binary swaps \((x \; y)\) in the cycle representation (odd count means \(-1\), even count means \(+1\)).
Let \(V_{\mathrm{std}}=V_{\mathrm{triv}}^\perp\). By definition
\[ \CC^3=V_{\mathrm{triv}}\oplus V_{\mathrm{std}} . \]
We claim that \(\rho_{\mathrm{perm}}\) restricted to \(V_{\mathrm{std}}\) is the 2D representation \(\rho_{\mathrm{std}}\) presented in the exercise statement (for a certain choice of basis in \(V_{\mathrm{std}}\)). But first let us observe that this restriction is indeed irreducible. In fact (c.f. decomposition of characters):
\[ \chi_{\mathrm{std}} = \chi_{\mathrm{perm}} - \chi_{\mathrm{triv}} = (2, -1, -1, 0, 0, 0) . \]
The norm of this is \(1\). Hence we know that it must be irreducible although we haven't calculated the representation yet! Let us show that
s3_std = [ Matrix([[1, 0], [0, 1]]), Matrix([[-1, -sqrt(3)], [sqrt(3), -1]]) / 2, Matrix([[-1, sqrt(3)], [-sqrt(3), -1]]) / 2, Matrix([[-1, 0], [0, 1]]), Matrix([[1, -sqrt(3)], [-sqrt(3), -1]]) / 2, Matrix([[1, sqrt(3)], [sqrt(3), -1]]) / 2, ]
is indeed the second summand in \(\rho_{\mathrm{perm}}=\rho_{\mathrm{triv}}\oplus\rho_{\mathrm{std}}\). The following unitary matrix is the G-isomorphism which shows this:
U_std = Matrix([ [sqrt(3)/3, -sqrt(2)/2, sqrt(6)/6], [sqrt(3)/3, sqrt(2)/2, sqrt(6)/6], [sqrt(3)/3, 0, -sqrt(6)/3] ])
How did we find it? It is clear that we have to choose a spanning vector of the invariant subspace \(\CC(1,1,1)\) as the first column to obtain the trivial representation as the first summand. How to choose the other two columns is only important to obtain the particular matrices given in the exercise. The second column is easily seen to be a multiple of \((1,1,0)\) when looking at the fourth matrix. The last column is essentially fixed by the unitarity constraint.
A brief check that it does what we want:
assert U_std.H * U_std == eye(3) for i in range(6): G = U_std.H * s3_perm[i] * U_std G.col_del(0) G.row_del(0) assert G == s3_std[i] "PASSED"
PASSED
Orthogonality of the three irreducible representation already follows from the fact that they are irreducible, but can be easily check directly of course. QED.
Another way to see that the 2D matrices form a (faithful) representation is the following. First observe that the second and the fourth element generate the group:
a = group_s3[1] b = group_s3[3] assert a**3 == b**2 == group_s3[0] assert a**(-1) == group_s3[2] assert a**(-1) * b * a == group_s3[4] assert a * b * a**(-1) == group_s3[5] "PASSED"
PASSED
From an algebraic perspective this describes the group completely. Hence we just have to show that the analogous formulas hold for \(\rho_{\mathrm{std}}\) too:
A = s3_std[1] B = s3_std[3] assert A**3 == B**2 == s3_std[0] assert A**(-1) == s3_std[2] assert A**(-1) * B * A == s3_std[4] assert A * B * A**(-1) == s3_std[5] "PASSED"
PASSED
Prove that the regular representation is faithful.
This is more or less obvious. In fact, the regular representation \(\rho^R\) can be identified with the vector space \(R=\CC^{\oplus G}\) made up of the following formal sums:
\[ v = \sum_{h \in G} \lambda_h h , \]
where \(\lambda_h\in\CC\) and \(G\) is acts as a basis (so that the \(\lambda_h\) are unique). See also the entry for free module on wikipedia. With this definition \(\rho^R\) is given by
\[ \rho^R(g) v = \sum_{h \in G} \lambda_h (gh) . \]
Clearly this is a homomorphism of groups. It is also an isomorphism since \(\rho^R(g)=\rho^R(e)\) implies \(\rho^R(g)e=\rho^R(e)e\) which in turn implies \(ge=e\), hence \(g=e\). QED.
Show that the character of the regular representation is zero except on the representation of the identity element, for which \(\chi^R(I)=\abs{G}\).
We have
\[ \rho^R(g)_{ij} = \begin{cases} 1 & \text{if } g g_i=g_j \\ 0 & \text{else.} \end{cases} \]
\(g g_i=g_i\) is equivalent to \(g=e\). Hence \(\rho^R(g)\) has any non-zero entries on the diagonal iff \(g=e\). QED.
Use Theorem A2.5 to show that the regular representation contains \(d_{\rho^p}\) instances of each irreducible representation \(\rho^p\). Thus, if \(R\) denotes the regular representation, and \(\hat{G}\) denotes the set of all inequivalent irreducible representations, then
\[ \chi_i^R = \sum_{\rho \in \hat{G}} d_\rho \chi_i^\rho . \]
By Theorem A2.4 (the fundamental theorem) the irreducible representations are an orthonormal basis of the Hilbert Space of class functions (see here too). Hence
\[ \chi^R = \sum_{\rho\in\hat{G}} c_\rho \chi^\rho \]
for some \(c_\rho\in\CC\). Let us calclute the value of the coefficients:
\[ c_\rho = \langle \chi^\rho, \chi^R \rangle = \abs{G}\inv \chi^\rho(e)^* \chi^R(e) = d_\rho . \]
The second equality follows from exercise A2.18 and the third one from exercise A2.11(1). QED.
The character of the regular representation is zero except for the conjugacy class containing \(e\) (which is \(\{e\}\)), the identity element in \(G\) (see exercise A2.18). Show, therefore, that
\[ \sum_{\rho \in \hat{G}} d_\rho \chi^\rho(g) = \abs{G} \delta_{ge} . \]
We have
\[ \sum_{\rho \in \hat{G}} d_\rho \chi^\rho(g) = \chi^R(g) = \abs{G} \delta_{ge} . \]
The first equality follows from exercise A2.19. The second one from exercise A2.18. QED.
Show that \(\sum_{\rho\in\hat{G}}d_\rho^2=\abs{G}\).
We have
\[ \sum_{\rho\in\hat{G}} d_\rho^2 = \sum_{\rho\in\hat{G}} d_\rho \chi^\rho(e) = \chi^R(e) = \abs{G} . \]
The first equality follows from exercise A2.11(1), the second from A2.19 and the third again from A2.11(1). QED.
Substitute (A2.10) into (A2.9) and prove that \(\hat{f}(\rho)\) is obtained.
Let us fix an irreducible representation \(\rho\) and indices \(i,j\). Let \(n=n(\rho,i,j)\) where we use the same notation as in the coordinate formulation of the Fourier transform.
\begin{align*} &\sqrt{\frac{d_\rho}{N}} \sum_g f(g) \rho(g)_{ij} \\ &= \frac{1}{N} \sum_g \sum_\sigma \sqrt{d_\rho d_\sigma} \trace{\hat{f}(\sigma)\sigma(g\inv)} \rho(g)_{ij} \\ &= \frac{1}{N} \sum_g \sum_\sigma \sqrt{d_\rho d_\sigma} \sum_{kl} \hat{f}(\sigma)_{kl}\sigma(g\inv)_{lk} \rho(g)_{ij} \\ &= \frac{1}{N} \sum_{\sigma} \sum_{kl} \sqrt{d_\rho d_\sigma} \hat{f}(\sigma)_{kl} \sum_g \sigma(g\inv)_{lk} \rho(g)_{ij} \\ &= \sum_{\sigma} \sum_{kl} \sqrt{\frac{d_\sigma}{d_\rho}} \hat{f}(\sigma)_{kl} \delta_{lj} \delta_{ki} \delta_{\sigma \rho} \\ &= \hat{f}(\rho)_{ij} \\ &= \hat{f}(n) . \end{align*}In the fourth equality we used the fundamental formula.
Let us represent an Abelian group \(G\) by \(g\in[0,N-1]\), with addition as the group operation, and define \(\rho_h(g)=\exp[−2\pi\ii gh/N]\) as the \(h\) representation of \(g\). This representation is one-dimensional, so \(d_\rho=1\). Show that the Fourier transform relations for \(G\) are
\[ \hat{f}(h) = \frac{1}{\sqrt{N}} \sum_{g=0}^{N-1} f(g) e^{-2\pi\ii gh/N} \quad \text{and} \quad f(g) = \frac{1}{\sqrt{N}} \sum_{h=0}^{N-1} \hat{f}(h) e^{2\pi\ii gh/N} . \]
Let us first note that \(g\inv\) is to be translated to \(-g\) since the group operation is \(+\). That the \(\rho_g\) are representations is easy to verify. To see that they are irreducible first observe that \(\rho_g\) is equal to its character \(\chi_g\) and hence irreducibility follows from
\[ \norm{\chi_g}^2 = \frac{1}{N} \sum_h \chi_g(h)^* \chi_g(h) = \frac{1}{N} \sum_h 1 = 1 , \]
which characterizes irreducible characters. The rest is pluggin stuff into formulas. See also the section on the Fourier transform on Abelian groups.
Using the results of Exercise A2.16, construct the Fourier transform over \(S_3\) and express it as a 6×6 unitary matrix.
It is easy to write some code which does this:
def get_fourier_matrix(representations: list[list[Matrix | Number]]) -> Matrix: """Get a matrix representation of the Fourier transform F of a group G. Args: representations: All irreducible representations of G. Returns: The unitary N×N matrix for F with N = |G|. The concrete matrix for F depends on the ordering of the representations and the choice of basis for each individual representation. """ assert len(representations) > 0, "Need at least one representation" N = len(representations[0]) ftrafo = [] assert N > 0, "A group cannot have zero elements (c.f. first represenation)." for rep in representations: assert len(rep) == N, "Cardinality of all representations must be equal." if isinstance(rep[0], Number): rep = [Matrix([[r]]) for r in rep] dim = len(rep[0].col(0)) assert all([g.shape == (dim, dim) for g in rep]), \ f"Inconsistent dimension in {rep}" for i in range(dim**2): row = [sqrt(dim) * g[i] / sqrt(N) for g in rep] ftrafo.append(row) return Matrix(ftrafo)
Plug in the arguments for \(S_3\):
s3_triv = 6*[1] s3_sign = 3*[1] + 3*[-1] FT_s3 = get_fourier_matrix([s3_triv, s3_sign, s3_std])
The matrix looks like this:
\[ \left[\begin{matrix}\frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6}\\\frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6} & \frac{\sqrt{6}}{6} & - \frac{\sqrt{6}}{6} & - \frac{\sqrt{6}}{6} & - \frac{\sqrt{6}}{6}\\\frac{\sqrt{3}}{3} & - \frac{\sqrt{3}}{6} & - \frac{\sqrt{3}}{6} & - \frac{\sqrt{3}}{3} & \frac{\sqrt{3}}{6} & \frac{\sqrt{3}}{6}\\0 & - \frac{1}{2} & \frac{1}{2} & 0 & - \frac{1}{2} & \frac{1}{2}\\0 & \frac{1}{2} & - \frac{1}{2} & 0 & - \frac{1}{2} & \frac{1}{2}\\\frac{\sqrt{3}}{3} & - \frac{\sqrt{3}}{6} & - \frac{\sqrt{3}}{6} & \frac{\sqrt{3}}{3} & - \frac{\sqrt{3}}{6} & - \frac{\sqrt{3}}{6}\end{matrix}\right] \]
It is unitary:
assert FT_s3.H * FT_s3 == eye(6) "PASSED"
PASSED
Let us disect this a bit. The first row (index 0) corresponds to this equation:
\[ \hat{f}(\rho_{\mathrm{triv}}) = \frac{1}{\sqrt{6}} \sum_g f(g) = \frac{1}{\sqrt{6}} (1,1,1,1,1,1) \cdot f . \]
The second row (index 1) corresponds to (note that for one-dimensional representations the character is equal to the representation)
\[ \hat{f}(\rho_{\mathrm{triv}}) = \frac{1}{\sqrt{6}} \sum_g f(g) \chi_{\mathrm{sign}}(g) = \frac{1}{\sqrt{6}} (1,1,1,-1,-1,-1) \cdot f . \]
Row with index \(2 + i + 2j\) where \(i,j\in\{0,1\}\) is given by:
\[ \hat{f}(\rho_{\mathrm{std}})_{ij} = \sqrt{\frac{2}{6}} \sum_g f(g) \rho_{\mathrm{std}}(g)_{ij} . \]
In other words: each column in the last four rows contains a flattend version of each element in \(\rho_{\mathrm{std}}\). This finishes the demonstration.
Lang, Serge (2002). Algebra., New York, NY: Springer.
Nielsen, Michael A. and Chuang, Isaac L. (2011). Quantum Computation and Quantum Information: 10th Anniversary Edition, Cambridge University Press.
William Fulton and Joe Harris (2004). Representation theory, Springer.