2
$\begingroup$

Engineer here.

I'm confused about representation theory of finite groups. For some program I am writing, I have to work with arithmetic modulo $p^k,$ where $p$ is a prime, and $k \ge 2.$ That is, numbers from $\mathbb{Z}/p^k\mathbb{Z} = \{ 0, 1, \ldots, p^k - 1\}.$ If I understand it correctly, linear representation theory allows me to map my computations from scalars into the domain of matrices through a homomorphism: $h : \mathbb{Z}/p^k\mathbb{Z} \to {\rm GL}(n, \mathbb{C})$

Quote from the wikipedia article:

Thus to specify a representation, we just assign a square matrix to each element of the group, in such a way that the matrices behave in the same way as the group elements when multiplied together.

which is great since modular reduction computations are slow/hard in my target platform, but linear algebra is easy/fast. So I really want to replace my scalaraarithmetic operations $\{+, -, \times\} \bmod {p^k}$ with matrix operations $\{+, -, \times\}.$

My questions:

  1. Is linear representation what I need?

  2. Given $p, k,$ how can I choose $n$?

  3. How can I construct the mapping $h$ and its inverse $h^{-1}$?

References are welcome as answers. But I'm really interested in the computational solutions that work (even if it fails few times.)

  • 0
    Wouldn't it be easier to reprogram modular arithmetics yourself? You just need to program$a$function $a \mod b$ that gives the remainder of $a$ divided by $b$, and the rest would follow.2012-03-31

1 Answers 1

4

Warning: Compared to computations in $\mathbb Z/p^k \mathbb Z$, computations in $\mathrm{GL}(p^k,\mathbb C)$ under multiplication (which is what is done when you take group representations) are really, really slow on any platform I have ever heard of. Computations in the first run in linear time, while in the second there are no known algorithms that work in even quadratic time.

That being said, we can generate a subgroup of $\mathrm{GL}(p^k,\mathbb C)$ isomorphic to $\mathbb Z/p^k \mathbb Z$ with the $p^k\times p^k$ matrix $X=\begin{pmatrix} 0 & 0& \cdots & 0& 1\\ 1 & 0 & \cdots & 0 & 0\\ 0 & 1 & \cdots & 0 & 0\\ \vdots & & \ddots& \vdots & \vdots\\ 0 & 0 & \cdots & 1& 0\end{pmatrix}$ which is just the identity matrix $I$ with all but the last row shifted down one, and the last row placed at the top. The isomorphism is then simply $h(n)=X^n$, as $I=X^0=X^{p^k}$.

Edit: Note that we are really representing $\mathbb Z/p^k \mathbb Z$ as a subgroup of $S_{p^k}$, namely that generated by the cycle $(12\cdots p^k)$, and then representing $S_{p^k}$ as a subgroup of $\mathrm{GL}(p^k,\mathbb C)$ via the map $\sigma\mapsto \begin{pmatrix}e_{\sigma(1)}\\ \vdots\\ e_{\sigma(p^k)}\end{pmatrix}$ where $e_n$ denotes the $n$th row of the identity matrix.

  • 0
    Chrome crashed five times as I wrote this... this is new.2012-03-30