How can I find an isomorphism between two representations?

Question

Suppose I have two representations (over $\mathbb{C}$) of a finite group $G$, $\rho : G \to GL(V)$ and $\tau : G \to GL(W)$. If I am given that these representations are isomorphic, i.e. there exists a linear map $A : V \to W$ such that for all $g \in G$, $\tau(g)A = A\rho(g)$, how can I find $A$?

The approach I have in mind is to compute $\tau(g)$ and $\rho(g)$ for all $g \in G$, then find the matrix that exhibits the simultaneous similarity of these. But this is just kind of rephrasing the problem.

One way of finding a solution would be to make each entry of $A$ a variable, then write out the linear equations given by $\tau(g)A = A\rho(g)$ for all $g \in G$. Then the solution space will have some invertible matrices in it, these are the ones I want. But I have no idea how to program this on a computer.

Another rephrasing of that idea is finding simultaneous fixed points of the linear maps given by:

$$A \mapsto \tau(g)A\rho(g^{-1}) $$

for each $g \in G$

This is going to be a very large matrix. And if I "unwrap" the matrix $A$ into vectors, the matrix of this linear map will be huge: if the representations have degree $n$, I'll end up with a matrix of size $n^2 \times n^2$ for which I have to find the eigenspace for value $1$.

Surely there is a smarter way of solving the problem than this?

I am using the GAP algebra system, so answers relating to this would be the most helpful, but any help is appreciated.

Some more information: usually I am dealing with the case where $G$ is a fairly large (tens of thousands of elements) permutation group, but I know the generators of $G$ and there are usually only a handful.

Answer 1

looking naively at the matter, the matrix $A$ has $n^2$ entries, which are initially unknown. and you have a set of $\#(G)$ linear equations in the $A_{ij}$:

$$ A_{ij} = \sum_{i} \sum_{j}\tau(g)_{ik}A_{kl}\rho(g^{-1})_{lj} $$

Answer 2

Here is another way that doesn't involve trying random matrices. For simplicity, assume $\rho$ and $\tau$ are irreducible and have degree $n$. Fix bases $B_V$ and $B_W$ for $V$ and $W$. For $g\in G$, let $\tau(g)$ have matrix form $(r_{ij})$ with respect to $B_W$.

We define maps $p_{ij}$ for $1\leq i,j \leq n$ from $V$ to itself as follows $$p_{ij} = \frac{n}{|G|}\sum_{g\in G}r_{ji}(g^{-1})\rho(g).$$ Note that $r_{ji}(g^{-1})$ is the $ji$-entry of the matrix representation of $g^{-1}$.

Then

1. $p_{ii}$ is a projection onto its image. Denote $V_i = \operatorname{im} p_{ii}$. Then $V = \bigoplus_{i=1}^n V_i$.

2. $p_{ij}$ is zero on $V_k$ for $k \neq j$ and is a vector space isomorphism from $V_j \to V_i$.

3. Let $x_1 \in V_1$ be a nonzero vector and let $x_i = p_{i1}(x_1) \in V_i$. Then $X = \{x_1,\dots,x_n\}$ is a basis for $V$ such that $$\rho(g)(x_i) = \sum_{j=1}^n r_{ij}(g)x_j.$$ In other words, the matrix representation of $\rho(g)$ with respect to the basis $X$ is exactly $(r_{ij}(g))$.

At this point, a representation isomorphism from $V \to W$ with respect to bases $X$ and $B_W$ is given by the identity matrix. To use $B_V$ as a basis for $V$, simply perform a change of basis from $B_V$ to $X$ first.

Proof: take Proposition 8 in section 2.7 of Linear Representations of Finite Groups by Serre and consider the special case when $V$ is already irreducible.

But this method almost always requires more computation than trying random matrices, because you need to compute $p_{i1}$ for $1\leq i \leq n$. That's $n$ maps each summing over $G$. So in practice I will probably go with what Daniel suggested.