Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Added: Amritanshu Prasad's answer makes it clear that I am really asking for a description of the group of integer unimodular matrices $P$ such that $D^{-1}PD$ is also integer. These matrices are characterized by the property that the elements below the diagonal satisfy certain divisibility properties, namely that for $j\lt i$, the element $p_{ij}$ is divisible by $d_i/d_j$. (The latter is integer by assumption on $D$.) My question was whether there is a simple set of generators for this group.

Amritanshu Prasad's answer provides a nice set of generators when the elements of each row, rather than being integers, are taken modulo a certain number. I will have to think about whether this helps with the problem that motivated the question originally. Meanwhile, I am still interested in finding out what is known about this question in the integer case.

Original post: Let $M$ be a nonsingular integer $n\times n$ matrix with invariant factors $d_1,\ldots,d_n$ satisfying $d_j\mid d_{j+1}$ for $1\le j\lt n$ and $d_j\gt0$ for $1\le j\le n$. Let $D=\mathrm{diag}(d_1,\ldots,d_n)$ be the Smith normal form of $M$. There is a pair of integer unimodular matrices $(P_1,Q_1)$ such that $P_1MQ_1=D$, but $(P_1,Q_1)$ is not uniquely determined. I am trying to understand this nonuniqueness.

Suppose that $P_1MQ_1=P_2MQ_2=D$. Define $P$ and $Q$ to be the integer unimodular matrices that satisfy $P_2=PP_1$ and $Q_2=Q_1Q$. Then $PDQ=D$. We call such a pair $(P,Q)$ an automorphism of $D$, and are interested in characterizing the group consisting of all automorphisms of $D$.

Define the elementary matrices $S_{ij}$, $N_i$, $L_{ij}(a)$ as follows:

  1. $S_{ij}M$ interchanges rows $i$ and $j$ of $M$;
  2. $N_iM$ multiplies row $i$ of $M$ by $-1$;
  3. $L_{ij}(a)M$ adds $a$ times row $j$ of $M$ to row $i$ of $M$, where $a$ is a nonzero integer.

With these definitions, some elementary pairs that satisfy $PDQ=D$ are:

  1. $(P,Q)=(S_{ij},S_{ij})$ for any $1\le i\lt j\le n$ such that $d_i=d_j$,
  2. $(P,Q)=(N_i,N_i)$ for any $1\le i\le n$,
  3. $(P,Q)=(L_{ij}(1),L_{ij}(-d_j/d_i))$ for any $1\le i\lt j\le n$,
  4. $(P,Q)=(L_{ij}(-d_i/d_j),L_{ij}(1))$ for any $1\le j\lt i\le n$.

My question is: Do these four types of pair generate the entire automorphism group?

I initially thought that this would be a straightforward question to answer, and that the answer would be 'yes', but now I am fairly sure it is not so simple. For example, consider the smallest nontrivial form, $D=\begin{bmatrix}1 & 0\\ 0 & r\end{bmatrix}$ with $r>1$. Writing $P=\begin{bmatrix}a & b\\ c & d\end{bmatrix}$ with $\lvert ad-bc\rvert=1$, the relation $Q=D^{-1}P^{-1}D$ implies that $Q=(ad-bc)^{-1}\begin{bmatrix}d & -br\\ -c/r & a\end{bmatrix}$, which is integer when $r\mid c$. Hence the most general pair is $(P,Q)=\left(\begin{bmatrix}a & b\\ rc' & d\end{bmatrix},(ad-rbc')^{-1}\begin{bmatrix}d & -rb\\ -c' & a\end{bmatrix}\right)$ with $\lvert ad-rbc'\rvert=1$. For the subgroup satisfying $ad-rbc'=1$, we therefore require that $P$ be an element of the congruence subgroup $\Gamma_0(r)$ and that $Q=\rho(Q)$ where $\rho:\Gamma_0(r)\rightarrow\Gamma^0(r)$ is the map $\begin{bmatrix}a & b\\c & d\end{bmatrix}\mapsto\begin{bmatrix}d & -rb\\-c/r & a\end{bmatrix}$. We obtain the full automorphism group by including, in addition to the generators $(\gamma,\rho(\gamma))$ where $\gamma$ is a generator of $\Gamma_0(r)$, the generators $(N_1,N_1)$ and $(N_2,N_2)$.

The problem with this is that the set of generators 1–4 appears not to be adequate for the case $r=5$, for example. Andy Putman's question Generators for congruence subgroups of SL_2 seems relevant in this regard, although it is concerned with generators of $\Gamma(r)$ rather than $\Gamma_0(r)$. The Grosswald and Frasch references in Ignat Soroko's answer to that question provide a set of generators that freely generates $\Gamma(p)$ for $p$ an odd prime; this set contains many generators in addition to 1–4, and the number of generators grows as $p^3$.

It would therefore appear that, if the picture for $\Gamma_0(r)$ is similar to that of $\Gamma(r)$, and if Frasch's requirement of free generation is not the origin of all this complication, then the answer to my question is no, at least in the case where $n=2$ and $r$ is a prime greater than 3. On the other hand, a remark in Andy Putman's question suggests to me that the situation may be considerably simpler for $n>2$, and that there's a chance that the generators 1–4 suffice. I am not, however, sure that congruence subgroups are the relevant concept for $n>2$. Also, for $n=2$, I wonder whether adding the single extra generator $L_{12}(1)$ to Frasch/Grosswald's set would generate all $P$?

This leads to the following additional questions:

  1. Is the above understanding of $n=2$ correct? If so, what is the smallest set of generators one can write down?
  2. Do 1–4 generate the automorphism group for $n>3$? If so, how and where is this proved?
share|improve this question
Do you know what the automorphisms look like for (e.g. when n=2) the case of rational r and rational P and Q? Gerhard "Ask Me About System Design" Paseman, 2011.09.10 –  Gerhard Paseman Sep 11 '11 at 5:02
I believe that questions like this are considerably more straightforward to answer over a field. We can let $P$ be any element of $\mathrm{GL}_n(\mathbf{Q})$; then $Q$, also in $\mathrm{GL}_n(\mathbf{Q})$, is determined by $Q=D^{-1}P^{-1}D$. –  Will Orrick Sep 12 '11 at 14:15
add comment

1 Answer

If you have $P$, I think you can recover $Q$ as $(D^{-1}PD)^{-1}$. Therefore, you are looking for invertible integer matrices $P$ such that $D^{-1}PD$ is also invertible (i.e., $P\in GL_n(\mathbf Z)\cap D GL_n(\mathbf Z) D^{-1}$).

Going modulo the subgroup group consisting of $I+T$, where $T$ is an endomorphism of $\mathbf Z^n$ such that $T(\mathbf Z^n)\subset D\mathbf Z^n$, you get the automorphism group of the finite abelian group $A=\mathbf Z/d_1\mathbf Z\times\dotsb\mathbf\times Z/d_n\mathbf Z$. This group is a product of the automorphism groups of the primary components of $A$.

A $p$-primary component of $A$ is of the form $\mathbf Z/p^{\lambda_1}\mathbf Z\times\dotsb\times\mathbf Z/p^{\lambda_n}\mathbf Z$. This group is generated by the Birkhoff moves (see Subgroups of Finite Abelian Groups by Garrett Birkhoff in Proceedings of the London Math. Society, 1935):

  1. Scaling any row/column by a $p$-free integer
  2. Adding $\alpha$ times the $i$th row (column) to the $j$th row (column) so long as $p^{\max\{0,\lambda_i-\lambda_j\}}$ divides $\alpha$.
  3. Interchanging rows or columns with the same invariant factors.
share|improve this answer
Which group is meant by "This is acually" Aut(A) ? If $D=\lambda \cdot I$ then $GL_n(\mathbb{Z}) \cap DGL_n(\mathbb{Z})D^{-1} = GL_n(\mathbb{Z})$ surely isn't Aut(A). –  Ralph Sep 11 '11 at 12:09
One has a map from the group we seek to the automorphism group of $A$ with as kernel the group consisting of the maps that can be written as identity plus a homomorphism from ${\mathbb Z}^n $ to $D{\mathbb Z}^n $. –  Wilberd van der Kallen Sep 11 '11 at 13:29
You are absolutely right. –  Amritanshu Prasad Sep 11 '11 at 23:20
@Amritanshu Prasad : Thank you (and thanks to the other commenters) for your answer. While I continue to think about what you have said, I will ask what I'm sure is a naive question. A $p$-free integer is always a unit in $\mathbf{Z}/p^λ\mathbf{Z}$, but not in $\mathbf{Z}$. Therefore it would seem that move 1 is not generally invertible in the context of the original question. I confess that I have not yet fully understood certain aspects of your answer, so perhaps this is taken care of somehow? –  Will Orrick Sep 12 '11 at 21:22
The moves work with matrices where the $i$th row is taken modulo $p^{\lambda_i}$. So, you only need to invert modulo some power of $p$.The Birkhoff moves are not moves on the matrices per se (so maybe my answer does not answer you question), but rather on matrices where the entries are taken modulo some congruences. –  Amritanshu Prasad Sep 16 '11 at 10:10
add comment

Your Answer


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.