Multiple Time Series Analysis

I am reading the book New Introduction to Multiple Time Series Analysis by L├╝tkepohl to refresh my memory of vector autoregressive models, error correction models, and state space models (supposedly all equivalent.) I will build in some computational aspect of these models into this post using python or julia. This post serves as my workbook while reading the book.

To Be Continued…

Representation Theory of Finite Group

I am reading the book Representation Theory of Finite Groups by Benjamin Steinberg due to my interest in probability theory on groups and other algebraic structure. This is related to my earlier post on random walk on n-gons which I found to be very interesting. This post will be my workspace for reading through this book and other related material, notably Group Representations in Probability and Statistics by Persi Diaconis.

Representation theory studies how a group act on vector spaces. Another way to think about it is that for any group G, what are the ways to embed or map it to the general linear group GL(V). We need to first review what a group action is. The action of a group G on a set X is a homomorphism \varphi:G\longrightarrow S_X, assigning each group member g \in G some permutation \sigma of the set X that is compatible with the structure of the group G. This is always possible because one can do this trivially (the trivial action) such that \varphi(g) = \sigma_1 for all g \in G, mapping every element of g to the identity permutation. If we take X = G, then it is also always possible because of Cayley’s Theorem, which states that every group is isomorphic to a group of permutation or a subgroup of the symmetric group S_{\lvert G \rvert}. The set X can have some additional structure, and if we take X to be a vector space over field \mathcal{F} and ensure the map \varphi respect the additional structure of the vector space as well, then the group action is called a group representation.

Definition (Representation)

A representation \varphi of group G is the homomorphism \varphi:G\longrightarrow GL(V) from G to the general linear group of the vector space V. The degree of \varphi is the dimension of V.

We write the linear map \varphi(g) as \varphi_g, and \varphi_g(v), sometimes written as \varphi_g v for the action of \varphi_g on v \in V. Below is an example of the representation on S_3.

Example (Representation of S_3)

Immediately from the definition we see the analogy of trivial action as a representation: the trivial representation \varphi:G\longrightarrow\mathbb{C} given by \varphi(g)=1 for all g \in G. We also see that the degree of the trivial representation is 1. It is interesting to see some other representations of a small group such as S_3 the group of all permutations on 3 elements. Aside from the trivial representation, we can compute two others: the alternating representation and the standard representation or the permutation representation.

Let \sigma \in S_3 be a permutation on 3 elements, the alternating representation is the function \varphi_\sigma v = \mathrm{sgn}(\sigma) v where \mathrm{sgn}(\sigma) = +1 if \sigma can be written as a product of an even number of transpositions, and -1 otherwise. More precisely, define the signum of \sigma by

    \begin{equation*} \mathrm{sgn}(\sigma)=\prod_{1\leq i < j \leq n}\frac{\sigma(i)-\sigma(j)}{i-j} \end{equation*}

then the map \sigma\longrightarrow\mathrm{sgn}(\sigma) is a group homomorphism of S_n to the subgroup \left\{1,-1\right\} of the multiplicative group \mathbf{R^*}=\mathbf{R}\setminus\{0\}. Thus the number of transpositions in a representation of \sigma is either even or odd. We can check that this is a representation. For g, h \in G we have

    \begin{align*} \varphi_{gh}v &= \mathrm{sgn}(gh) v \\               &= \left(\mathrm{sgn}(g)\mathrm{sgn}(h)\right) v \\               &= \left(\varphi_{g} \varphi_{h}\right) v \\               &= \varphi_{g} \left(\varphi_{h} v\right) \end{align*}

so \varphi_{gh} = \varphi_g \circ \varphi_h. This representation has degree 1.

The standard representation \varphi: S_3 \longrightarrow GL_3(\mathbb{C}) takes each permutation \sigma \in S_3 to a matrix in GL_3(\mathbb{C}) on standard basis such that rows of the matrix is permuted according to \sigma. In other words, \varphi_\sigma(e_i) = e_{\sigma(i)}. For example

    \begin{equation*} \varphi_{(1 2)} = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 1 & 0 & 0 \\ 0 & 0 & 1  \end{array} \right], \qquad \varphi_{(1 2 3)} = \left[ \begin{array}{rrr} 0 & 1 & 0 \\ 0 & 0 & 1 \\ 1 & 0 & 0  \end{array} \right] \end{equation*}

The standard representation has degree 3.

If we start with a representation \varphi: G \longrightarrow GL_n(\mathbb{C}) where B is a basis for \mathbb{C}^n, and if we have another isomorphism S:\mathbb{C}^n \longrightarrow \mathbb{C}^n with a basis B', then \varphi_g' = S \varphi_g S^{-1} is another representation. These two representation are intuitively the “same”. More generally, we have the definition of equivalence

Definition (Equivalence)

Two representations \varphi: G \longrightarrow GL(V) and \psi: G \longrightarrow GL(W) are said to be equivalent if there exists an isomorphism T:V \longrightarrow W such that \psi_g = T\varphi_gT^{-1} for all g \in G, or \psi_g T = T \varphi_g, or in picture, the following diagram commutes:

    \begin{equation*} \xymatrix{V\ar[r]^{\varphi_g}\ar[d]_{T} & V\ar[d]^{T}\\W\ar[r]^{\psi_g}& W} \end{equation*}

If \varphi is equivalent to \psi, we write \varphi \sim \phi.

An example of equivalent representations is given in Sternberg as follows:

Example (Equivalence)

Define \psi: \mathbb{Z}/n\mathbb{Z} \longrightarrow GL_2(\mathbb{C}) and \varphi: \mathbb{Z}/n\mathbb{Z} \longrightarrow GL_2(\mathbb{C}) by

    \begin{equation*} \psi_{[m]} = \left[  \begin{array}{cc} e^{\frac{2\pi mi}{n}} & 0 \\ 0 & e^{-\frac{2\pi mi}{n}} \end{array} \right], \quad \varphi_{[m]} = \left[ \begin{array}{lr} \cos\left(\frac{2\pi m}{n}\right) & -\sin\left(\frac{2\pi m}{n}\right) \\ \sin\left(\frac{2\pi m}{n}\right) & \cos\left(\frac{2\pi m}{n}\right) \end{array} \right] \end{equation*}

To show that \varphi \sim \psi, we need to find an an invertible matrix P such that \psi = P^{-1} \varphi P. This matrix P also represents a simple basis transformation in \mathbb{C}^2. Let us find the eigenvectors of the two operators. The eigenvectors for \varphi_{[m]} are [-i, i] and [1, 1], and for \psi_{[m]} is [1, 0] and [0, 1] the standard basis, while the eigenvalues for \varphi_{[m]} are \cos(2\pi m/n)+i\sin(2\pi m/n)) and \cos(2\pi m/n)-\sin(2\pi m/n)) and for \psi_{[m]} are \exp(2\pi i m/n) and \exp(-2\pi i m/n). By Euler’s formula, the two sets of eigenvalues are the same, so we can deduce that the change of basis matrix is the matrix with columns of eigenvectors of \varphi, namely,

    \begin{equation*} P=\left[ \begin{array}{cc} i &-i \\ 1 & 1 \end{array} \right] \end{equation*}

Indeed, P^{-1}\varphi_{[m]}P=\psi_{[m]} after some calculation.

The notion of equivalent representation are the same as matrix similarity, except that the former describes the equivalence between operators and the latter their matrix representation. Also note that in the example above there are two eigenspaces for \psi_{[m]}, namely E_1 = \mathbb{C}\mathbf{e}_1 and E_2 = \mathbb{C}\mathbf{e}_2. For v \in E_1, we have \psi_{[m]}(v) \in E_1 for all m \in \mathbb{Z}/n\mathbb{Z} as well. This motivates the definition of G-invariant subspace.

Definition (G-Invariant Subspace)

Let \varphi:G\longrightarrow GL(V) be a representation. A subspace W\le V is G-invariant if, for all g\in G and w \in W, one has \varphi_g w \in W.

We can use this definition to find the S_3-invariant subspace of the standard representation \varphi: S_3 \longrightarrow GL_3(\mathbb{C}). Note that the 1-dimensional space W spanned by \mathbf{e}_1 + \mathbf{e}_2 + \mathbf{e}_3 is a S_3-invariant subspace, since for any \sigma \in S_3,

(1)   \begin{align*} \varphi_{\sigma}(\mathbf{e}_1 + \mathbf{e}_2 + \mathbf{e}_3) &= \mathbf{e}_{\sigma(1)} + \mathbf{e}_{\sigma(2)} + \mathbf{e}_{\sigma(3)} \\ &= \mathbf{e}_1 + \mathbf{e}_2 + \mathbf{e}_3 \end{align*}

is again in the W. Also note that its compliment W^\perp = \left\{(x_1, x_2, x_3) : x_1 + x_2 + x_3 = 0\right\} is also S_3-invariant. Indeed, if \varphi: G \longrightarrow GL(V) is a representation and W < V is a G-invariant subspace, then restricting \varphi to W yields a subrepresentation \varphi\vert_W:G\longrightarrowGL(W) The following computation of restricting the standard representation to W^\perp follows that of Disconis.

Computation of the 2-Dimensional Representation of S_3

Let w_1 = \mathbf{e}_1 - \mathbf{e}_2 and w_2 = \mathbf{e}_2 - \mathbf{e}_3. Let v = a\mathbf{e}_1 + b\mathbf{e}_2 + c\mathbf{e}_3 \in W^\perp then v = a\mathbf{e}_1 + b\mathbf{e}_2 + (-a-b)\mathbf{e}_3 since the components of v add to 0. then v = a(\mathbf{e}_1 - \mathbf{e}_2) + (b+a)\mathbf{e}_2 + (-b-a)\mathbf{e}_3 yields v = a(\mathbf{e}_1 - \mathbf{e}_2) + (b+a)(\mathbf{e}_2 - \mathbf{e}_3) = aw_1 + (b+a)w_2. Therefore w_1 and w_2 are basis for W^\perp. Let’s consider the action \sigma on this basis.

    \begin{equation*} \begin{array}{cccc} \sigma & \varphi(\sigma)w_1 & \varphi(\sigma)w_2 & \varphi(\sigma) \\ \hline \mathrm{id} & w_1 & w_2 & \left[\begin{array}{p{0.5cm}p{0.5cm}} 1 & 0 \\ 0 & 1\end{array}\right] \\ (1 2) & -w_1 & w_1 + w_2 & \left[\begin{array}{p{0.5cm}p{0.5cm}}-1 & 1 \\ 0 & 1\end{array}\right] \\ (2 3) & w_1 + w_2 & -w_2 & \left[\begin{array}{p{0.5cm}p{0.5cm}}1 & 0 \\ 1 & -1\end{array}\right] \\ (1 3) & -w_2 & -w_1 & \left[\begin{array}{p{0.5cm}p{0.5cm}}0 & -1 \\ -1 & 0\end{array}\right] \\ (1 2 3) & w_2 & -(w_1+w_2) & \left[\begin{array}{p{0.5cm}p{0.5cm}}0 & -1 \\ 1 & -1\end{array}\right] \\ (1 3 2) & -(w_1 + w_2) & w_1 & \left[\begin{array}{p{0.5cm}p{0.5cm}}-1 & 1 \\ -1 & 0\end{array}\right] \\ \hline \end{array}  \end{equation*}

This gives the 2-dimensional representation of S_3

The 2-dimensional representation of S_3 is also irreducible, which means

Definition: Irreducible Representation

A non-zero representation \varphi:G\longrightarrow GL(V) of a group G is said to be irreducible if the only G-invariant subspaces of V are \{0\} and V.

To show that, assume a non-zero vector (x, y, z) \in W^\perp (say x \neq 0) and let W_1 be the span of this vector. If W_1 is a sub representation, then W_1 < W^\perp. Since (1, y', z') \in W_1, \varphi_{(1 2)}(1, y', z') = (y', 1, z') \in W_1 and so their difference (1-y', y'-1, 0) is also in W_1. If y' \neq 1, then \mathbf{e}_1 - \mathbf{e}_2 = w_1 \in W_1. Since \varphi_{(13)}(w_1) = -w_2, w_2 must be in W_1 as well, so W_1 = W^\perp. If y'=1 then (1, 1, -2) \in W_1. \varphi_{(23)}(1, 1, 2) = (1, 2, 1). Take the difference and we have (0, -1, 1) = w_2 \in W_1. Then \varphi_{(132)}w_2 = w_1 must also be in W_1, so again W_1 = W^\perp. This irreducible representation is 2-dimensional. We will see that the restriction of the permutation representation of S_n to W^\perp = \{x\in \mathbb{R}^n:\sum x_i = 0\} is an irreducible n-1-dimensional representation.

Since we can form direct sum of vector spaces, we can similarly define a direct sum of representations. We want to do this because we want to show that if V_1 and V_2 are two G-invariant subspaces and \varphi is a representation, then it makes sense to talk about a representation \varphi\vert_{V_1} \oplus \varphi\vert_{V_2} that maps from G to GL(V_1 \oplus V_2).

Definition: Direct Sum of Representations

Let \varphi^{(1)}:G\longrightarrow GL(V_1) and \varphi^{(2)}:G\longrightarrow GL(V_2) be two representations, then their external direct sum

    \begin{equation*} \varphi^{(1)}\oplus\varphi^{(2)}:G\longrightarrow GL(V_1 \oplus V_2) \end{equation*}

is defined by

    \begin{equation*} (\varphi^{(1)}\oplus\varphi^{(2)})_g(v_1, v_2) = \(\varphi^{(1)}_g(v_1), \varphi^{(2)}_g(v_2)) \end{equation*}

and has dimension \mathrm{dim}(V_1) + \mathrm{dim}(V_2).

If we restrict ourselves to matrices, then suppose \varphi^{(1)}:G\longrightarrow GL_m(\mathbb{C}) and \varphi^{(2)}:G\longrightarrow GL_n(\mathbb{C}). Then

    \begin{equation*} \varphi^{(1)} \oplus \varphi^{(2)}:G \longrightarrow GL_{m+n}(\mathbb{C}) \end{equation*}

has the block matrix form

    \begin{equation*}(\varphi^{(1)} \oplus \varphi^{(2)})_g =  \left[ \begin{array}{cc} \varphi^{(1)}_g & 0 \\ 0 & \varphi^{(2)}_g \end{array} \right] \end{equation*}

The representation \psi in the example about equivalence is a good demonstration of how to form direct product of representations. It should also be clear that if a representation can be written as a direct sum of subrepresentations, then it is not irreducible. Therefore. the representations in our equivalence example are not irreducible.

Related to the notion of irreducible representation are the decomposable and completely reducible representations.

To Be Continued…