Automorphisms of a matrix in Smith normal form?

2011-09-11T04:17:48Z

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:

$S_{ij}M$ interchanges rows $i$ and $j$ of $M$;
$N_iM$ multiplies row $i$ of $M$ by $-1$;
$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:

$(P,Q)=(S_{ij},S_{ij})$ for any $1\le i\lt j\le n$ such that $d_i=d_j$,
$(P,Q)=(N_i,N_i)$ for any $1\le i\le n$,
$(P,Q)=(L_{ij}(1),L_{ij}(-d_j/d_i))$ for any $1\le i\lt j\le n$,
$(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 http://mathoverflow.net/questions/2757/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:

Is the above understanding of $n=2$ correct? If so, what is the smallest set of generators one can write down?
Do 1–4 generate the automorphism group for $n>3$? If so, how and where is this proved?

Answer by Amritanshu Prasad for Automorphisms of a matrix in Smith normal form?

2011-09-11T11:32:29Z

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

Scaling any row/column by a $p$-free integer
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$.
Interchanging rows or columns with the same invariant factors.

Automorphisms of a matrix in Smith normal form? - MathOverflow

Automorphisms of a matrix in Smith normal form?

Answer by Amritanshu Prasad for Automorphisms of a matrix in Smith normal form?