Linear Algebra for Representations

These notes are being transcribed, condensed, and illustrated. They may lag or omit details, please refer to the handwritten notes for the full lecture.

This note reviews the linear algebra concepts we will need for group representations. The key ideas are: vector spaces provide the "stage" on which groups act, orthogonality and projectors let us decompose that stage into meaningful pieces, and the Kronecker product lets us solve for similarity transforms — one of the most important algorithms in this course.

1) Vector Spaces

In this course we work with real \mathbb{R}^n and complex \mathbb{C}^n vector spaces (though we'll use real ones when we can for convenience).

A vector space over a field \mathbb{F} (= \mathbb{R} or \mathbb{C}) is a set V equipped with vector addition and scalar multiplication satisfying eight axioms:

1. Associativity of addition: \vec{u} + (\vec{v} + \vec{w}) = (\vec{u} + \vec{v}) + \vec{w}
2. Commutativity of addition: \vec{u} + \vec{v} = \vec{v} + \vec{u}
3. Additive identity: \vec{v} + \vec{0} = \vec{v}
4. Additive inverse: \vec{v} + (-\vec{v}) = \vec{0}
5. Scalar multiplication: a(b\vec{v}) = (ab)\vec{v}
6. Identity scalar: 1\vec{v} = \vec{v}
7. Distributivity over vector addition: a(\vec{u} + \vec{v}) = a\vec{u} + a\vec{v}
8. Distributivity over field addition: (a + b)\vec{v} = a\vec{v} + b\vec{v}

1.1) Why Vector Spaces + Groups?

The set of invertible n \times n matrices acting on a vector space V naturally forms a group under matrix multiplication:

1. Closure: For A, B \in V \times V (matrices that act on V), AB = C \in V \times V.
2. Associativity: A(BC) = (AB)C.
3. Identity: E = \mathbb{I}_n (np.eye(n)).
4. Inverse: Here's the catch — we need invertible matrices!

This gives us the general linear group GL(n, \mathbb{C}) (or GL(n, \mathbb{R})) — the group of all invertible n \times n matrices over the complex (or real) numbers. All the matrix groups we'll study (O(n), SO(n), SU(n), permutation groups, etc.) are subgroups of GL(n).

2) Inner Products and the Trivial Metric

While the topic of how groups act on Riemannian manifolds (smooth manifolds with smooth metrics \langle \cdot, \cdot \rangle_p : T_pM \times T_pM \to \mathbb{R}) is rich and relevant for geometric deep learning, we will study groups and group representations that admit a trivial metric — or at least focus on cases where we can use a trivial metric locally.

This means the inner product of two vectors is simply:

where \dagger denotes the conjugate transpose. This also means that when we use index notation, we can be a bit "sloppy" and only use down indices, i.e. \sum_i u_i v_i rather than the more proper \sum_i u^i v_i.

3) Subspaces and Spanning Sets

A subspace is a vector space contained within another vector space. For example, the vectors that lie in the xy-plane define a subspace of 3D space (xyz).

A spanning set of vectors S = \{s_1, \ldots, s_n\} spans a vector space W if every w \in W can be written as a linear combination of vectors in S. Note, we have said nothing about the vectors s_i being orthogonal — i.e. s_i \cdot s_j = 0 for i \neq j.

Example: The vectors \hat{x} and \hat{y} span the subspace of the xy-plane, as do 0.5\hat{x} + 0.5\hat{y} and -0.5\hat{x} + 0.5\hat{y}.

4) Orthogonality

Orthogonality is a crucial concept in linear algebra and representation theory.

Two (nontrivial) vectors are orthogonal if their inner product is zero:

We can expand this idea to subspaces (subsets of vector spaces): for U, W \subseteq V,

5) Projectors

If we have two vectors u and v and we want to ask how "similar" they are, we can compute the inner product \langle u, v \rangle = \|u\| \|v\| \cos\theta.

If we want to ask how much of u points in the direction of v, we take \langle u, \hat{v} \rangle = \|u\| \cos\theta.

If we want to recover the part of u that is pointing along the direction of \hat{v}, we compute \langle u, \hat{v} \rangle \hat{v}.

Alternatively, we can construct the projection matrix of \hat{v}:

5.1) Projectors for Subspaces

If we want to project into a multidimensional subspace, we can find a spanning set of orthogonal vectors (we'll see how to do this systematically with Gram-Schmidt), construct each vector's projector matrix, and then add them up. Again, this will be useful when we discuss eigenspaces.

5.2) Projector Invariance Under Rotation Within the Subspace

The projector matrix is invariant under any rotation within the subspace R_{\text{sub}}. This will be important when we talk about eigenspaces!

Suppose a projector P_n represents an n-dimensional subspace of an m-dimensional space. We can apply a rotation U to bring P into a standard form:

Now if we apply a rotation only on the subspace, R_{\text{sub}} = \begin{pmatrix} \mathbb{I}_{m-n} & 0 \\ 0 & R_n \end{pmatrix}:

Intuition: Imagine you have a plane in 3D. We can always rotate the plane to align to the xy-plane. Then any rotation within that plane doesn't change which plane it is.

6) Orthogonal Complement

For W \subseteq V, the orthogonal complement W^\perp is the set of all vectors orthogonal to every vector in W:

If you took a spanning set of vectors of W and constructed a matrix A = \begin{pmatrix} w_1 \\ \vdots \\ w_r \end{pmatrix} (with r \leq n), then w' \in W^\perp would be in the nullspace of A, i.e. Aw' = 0 for all w' \in W^\perp.

Another way to find W^\perp is with projectors: compute the projector P_W of W (using Gram-Schmidt), then the projector onto the orthogonal complement is \mathbb{I} - P_W.

7) Gram-Schmidt Algorithm

Given a spanning set of vectors in a space W, we can construct an orthonormal basis using the Gram-Schmidt algorithm. This basis is not unique — it can be rotated by any rotation of the subspace, and it is highly dependent on e.g. the order of its inputs.

We recommend implementing Gram-Schmidt using projectors, as it makes the code much cleaner.

The essential idea, using a spanning set of vectors:

8) Special Types of Matrices

There are several types of matrices that have special properties, characterized by how they are related under transposition (flipping along the diagonal), complex conjugation, and their determinant. Note, the determinant tells us how volume scales under the transformation.

Orthogonal matrices are what we think of as rotations (and reflections, when \det = -1). The "special" variants (SO(n), SU(n)) enforce \det = 1, which excludes reflections and leaves only pure rotations. Unitary matrices are the complex generalization of orthogonal matrices.

9) Four Fundamental Subspaces

For an m \times n matrix A, there are four fundamental subspaces:

where r is the rank of A. The nullspace can be found by solving A^\dagger A x = 0 (finding the eigenspace of eigenvalue 0). Why does this work? If A^\dagger A x = 0, then x^\dagger A^\dagger A x = 0, which means \|Ax\|^2 = 0, so Ax = 0 — the vector is in the nullspace of A as well.

Note that for any matrix A, the product A^\dagger A is always Hermitian: (A^\dagger A)^\dagger = A^\dagger (A^\dagger)^\dagger = A^\dagger A. (For real matrices, A^T A is always symmetric.) Since Hermitian matrices have real eigenvalues and are always diagonalizable, A^\dagger A is always well-behaved — even when A itself is not. This fact will be important when we discuss the SVD and computing nullspaces.

10) Singular Value Decomposition (SVD)

For an m \times n matrix M (over reals or complex), the singular value decomposition factorizes the matrix as:

where U, V are unitary (or orthogonal if real) with U^\dagger U = \mathbb{I}_m and V^\dagger V = \mathbb{I}_n, and \Sigma is a diagonal matrix of singular values \sigma_i \geq 0.

This means any matrix can be written as a linear combination of outer products:

11) Eigenvalue / Eigenvector Decomposition

For diagonalizable (square) matrices:

where Q is unitary/orthogonal and \Lambda is diagonal. The columns of Q, q_i, are eigenvectors with eigenvalues \lambda_i: A q_i = \lambda_i q_i.

What does this really mean? A is a linear combination of the projectors of the eigenvectors, weighted by the eigenvalues:

i.e. "there's \lambda_i amount of the subspace v_i \otimes v_i^* in A."

Example: A = \begin{pmatrix} 1 & 0 & 0 \\ 0 & 2 & 0 \\ 0 & 0 & 2 \end{pmatrix} has \lambda = 1, 2, 2.

The second term is the projector onto the 2D eigenspace of eigenvalue 2.

11.1) Degenerate Eigenvalues

How about degenerate eigenvalues? In this case, eigenvectors are not unique (beyond sign ambiguity). You can take the eigenvectors with the same eigenvalue and rotate them within the spanned subspace, and the decomposition means the same thing.

Example: The 3 \times 3 identity matrix \mathbb{I}_3 has eigenvalue 1 with multiplicity 3. Any set of three mutually orthogonal vectors is a valid set of eigenvectors — \{e_x, e_y, e_z\}, or any rotation of them. The eigendecomposition is always \mathbb{I}_3 = 1 \cdot P where P is the projector onto the full 3D space, regardless of which basis you pick.

Note: most (if not all) linear algebra packages will return only one choice of eigenvectors, even though many exist. The reason usually stems from various conventions used to make the computation efficient.

11.2) Normal vs. Nonnormal Matrices

A matrix A is normal if it commutes with its conjugate transpose: A A^\dagger = A^\dagger A. Normal matrices include all unitary, Hermitian, and symmetric matrices. The key property: normal matrices are always diagonalizable with orthogonal eigenvectors.

Nonnormal matrices don't have this nice property. Even if they're full-rank (invertible), they may not be diagonalizable!

Example: \begin{pmatrix} 1 & 1 \\ 0 & 1 \end{pmatrix} or \begin{pmatrix} 2 & 1 \\ 0 & 2 \end{pmatrix}

These can be decomposed into a scaling part plus a nilpotent part (N^2 = 0):

Geometric intuition: The nilpotent part represents a shear transformation. While rotations and scalings preserve the "shape" of objects (circles stay circles), shears distort them (circles become ellipses). The nilpotent matrix \begin{pmatrix} 0 & 1 \\ 0 & 0 \end{pmatrix} shears along the x-axis — it moves points horizontally by an amount proportional to their y-coordinate.

11.3) Relationship with SVD

The SVD and eigendecomposition are closely related:

The non-zero eigenvalues of M^\dagger M and M M^\dagger are the squared non-zero singular values. The nullspace is the same: \sqrt{0} = 0.

12) Similarity Transforms: Motivation

One of the most important problems we'll encounter in this course is finding similarity transforms between matrices. Two matrices S and R are similar if there exists a matrix Q such that:

This equation appears everywhere in representation theory: when we want to show two representations are equivalent, when we want to change basis, or when we want to block-diagonalize a representation into irreducible pieces.

The challenge: Given S and R, how do we solve for Q? This isn't a standard linear system Ax = b — the unknown Q appears on both sides of the equation, multiplied by different matrices.

Even more challenging: for group representations, we often need to find a single Q that simultaneously satisfies S_g Q = Q R_g for all group elements g. That is, S and R are "stacks" of matrices (one for each group element), and we need one Q that works for all of them at once.

The solution: We'll use the Kronecker product to convert this problem into a standard nullspace computation. The key insight is that we can "flatten" the matrix Q into a vector and rewrite SQ - QR = 0 as P \cdot \text{vec}(Q) = 0 for some larger matrix P. For multiple equations, we simply stack the constraints.

13) Kronecker Product and Kronecker Sum

The Kronecker product and sum are the tools that make this conversion possible.

13.1) Kronecker Product (Tensor Product)

For A \in \mathbb{R}^{m \times n} and B \in \mathbb{R}^{p \times q}:

In index notation: (A \overset{kr}{\otimes} B)_{ik,j\ell} = A_{ij} B_{k\ell}, where ik and j\ell are flattened into single indices.

Note: A \overset{kr}{\otimes} B \neq B \overset{kr}{\otimes} A in general! This is easy to compute with np.einsum and a reshape (or alternatively with the build in np.kron function).

13.2) Kronecker Sum

For A (n \times n) and B (m \times m):

In index notation: (A \overset{kr}{\oplus} B)_{ik,j\ell} = A_{ij} \delta_{k\ell} + \delta_{ij} B_{k\ell}

13.3) Visualizing the Kronecker Product

How do we visualize a 4-index tensor like (A \overset{kr}{\otimes} B)_{ik,j\ell}? Since 4D shapes are hard to picture, we use matrices within matrices — "matrix-ception" if you will. For indices i, j, k, \ell: the outer indices (i, j) select which block you're in (the "entry" of the outer matrix), and the inner indices (k, \ell) select the entry within that block (the submatrix).

The interactive visualization below shows how the Kronecker product creates this block matrix structure, and highlights the special cases when one of the matrices is the identity.

14) Similarity Transforms: The Algorithm

Now we have the tools to solve the similarity transform problem we posed earlier: given S (m \times m) and R (n \times n), find Q (m \times n) such that SQ = QR.

The solution space can be an entire vector space of answers! Here's how to find it using Kronecker products.

14.1) Step 1: Set Up the Equation

14.2) Step 2: Convert to PQ = 0 Form Using Kronecker Products

We can rewrite this with indices. The (i,k) component of SQ - QR = 0 is:

Key insight: Once we write things in index notation, S_{ij}, Q_{jk}, and R_{\ell k} are just numbers (scalars), not matrices. Scalars commute, so we can freely rearrange them — unlike matrix multiplication where SQ \neq QS in general. This freedom is what lets us collect terms and factor out Q_{j\ell}.

To write this as a single matrix acting on \text{vec}(Q), we introduce delta functions to express both terms as sums over (j, \ell):

Recognizing the Kronecker product structure (with flattened indices (ik, j\ell)), and noting R_{\ell k} = (R^T)_{k\ell}:

14.3) Step 3: Find the Nullspace

The solutions Q are the nullspace of (S \overset{kr}{\otimes} \mathbb{I}_n) - (\mathbb{I}_m \overset{kr}{\otimes} R^T).

The symm4ml library implements this algorithm as linalg.infer_change_of_basis. Try it in the companion notebook:

# Find Q such that S @ Q = Q @ R for all group elements
Q = linalg.infer_change_of_basis(S, R)
# Returns a basis for the space of solutions
# If no solutions exist, Q has length 0

14.4) Solving for Multiple Pairs of S and R

When we have multiple pairs of matrices S_i and R_i that should all be related by the same Q (i.e. S_i Q = Q R_i for all i), we stack the equations:

and find the nullspace of the stacked matrix. More equations means more constraints, which narrows down the space of solutions.

14.5) Visualizing the Index Manipulation

The interactive visualization below walks through how the index manipulation transforms the matrix equation SQ = QR into a nullspace problem. The key insight is how the Kronecker delta functions restructure the 4-index tensor.

Related exercises: Linear Algebra Exercises