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
    I would be extraordinarily surprised if you gained anything from represting elements of $\mathbb Z/p^k$ as matrices...2012-03-30
  • 0
    @MarianoSuárez-Alvarez it is a **faulty** embedded platform where the math routines for modular reductions are *very very* slow (and have bugs). It's an engineering environment, and I have to make the code work at moderate cost (fixing the routines is not an option).2012-03-30
  • 2
    Even for $k=1$ you need a pretty large value of $n$ for the coefficients of the matrices in the representation be integral. So in practice you will need to do arithmetic with *exact* rational numbers or, worse, algebraic numbers. If modular arithmetic is buggy, that is going to be in all likelihood worse. For complicated groups a faithful linear representation does solve some issues, but for a cyclic group any such improvement would be reallu, really surprising!2012-03-30
  • 1
    If the built-in routines are slow and/or buggy, just implement them yourself. The best algorithms known are available (you can probably even copy the code from OSS projects like libgmp...)2012-03-30
  • 1
    I have an issue with the fact that you would like to model $+$ _and_ $\times$ mod $p^k$ simultaneously as matrices. Usually one talks about linear representations of a Group, which only has one operation. When you have $+$ _and_ $\times$ you're usually talking about a Ring2012-03-30
  • 0
    @you would that be a problem?2012-03-30
  • 2
    @Lori Jiang Well, one problem is that $GL(n,\mathbb{C})$ isn't closed under matrix addition: if $A\in GL(n,\mathbb{C})$ then so is $-A$, but $A-A=0\not\in GL(n,\mathbb{C})$.2012-03-30
  • 1
    Although, it might not be a problem in this case, since multiplication in $\mathbb{Z}/p^k$ can be derived from addition ($[m]\times[n]=\Sigma_{i=1}^n [m]$). So if you used the representation given in Alex Becker's answer, which maps addition in $\mathbb{Z}/p^k$ to matrix multiplication in $GL(n,\mathbb{C})$, then it will induce a new "multiplication" on $GL(n,\mathbb{C})$.2012-03-30
  • 2
    Clearly you can't use matrix addition to model the addition in $\mathbb Z/p^k \mathbb Z$: the latter has the identity $x+\ldots+x=0$ where there are $p^k$ terms, but that has no nonzero solutions in matrices over $\mathbb C$.2012-03-30
  • 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