Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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.)

share|improve this question
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! –  Mariano Suárez-Alvarez Mar 30 '12 at 21:15
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...) –  Mariano Suárez-Alvarez Mar 30 '12 at 21:18
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 Ring –  you Mar 30 '12 at 21:26
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})$. –  you Mar 30 '12 at 21:34
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$. –  Robert Israel Mar 30 '12 at 21:40

1 Answer 1

up vote 4 down vote accepted

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.

share|improve this answer
    
Chrome crashed five times as I wrote this... this is new. –  Alex Becker Mar 30 '12 at 21:28

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.