Automorphisms of a matrix in Smith normal form? - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-26T04:19:45Z http://mathoverflow.net/feeds/question/75127 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/75127/automorphisms-of-a-matrix-in-smith-normal-form Automorphisms of a matrix in Smith normal form? Will Orrick 2011-09-11T04:17:48Z 2011-09-30T19:45:11Z <p><strong>Added:</strong> 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.</p> <p>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.</p> <p><strong>Original post:</strong> 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. </p> <p>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 <em>automorphism</em> of $D$, and are interested in characterizing the group consisting of all automorphisms of $D$.</p> <p>Define the elementary matrices $S_{ij}$, $N_i$, $L_{ij}(a)$ as follows:</p> <ol> <li>$S_{ij}M$ interchanges rows $i$ and $j$ of $M$;</li> <li>$N_iM$ multiplies row $i$ of $M$ by $-1$;</li> <li>$L_{ij}(a)M$ adds $a$ times row $j$ of $M$ to row $i$ of $M$, where $a$ is a nonzero integer.</li> </ol> <p>With these definitions, some elementary pairs that satisfy $PDQ=D$ are:</p> <ol> <li>$(P,Q)=(S_{ij},S_{ij})$ for any $1\le i\lt j\le n$ such that $d_i=d_j$,</li> <li>$(P,Q)=(N_i,N_i)$ for any $1\le i\le n$,</li> <li>$(P,Q)=(L_{ij}(1),L_{ij}(-d_j/d_i))$ for any $1\le i\lt j\le n$,</li> <li>$(P,Q)=(L_{ij}(-d_i/d_j),L_{ij}(1))$ for any $1\le j\lt i\le n$.</li> </ol> <p><strong>My question is:</strong> Do these four types of pair generate the entire automorphism group? </p> <p>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, <code>$D=\begin{bmatrix}1 &amp; 0\\ 0 &amp; r\end{bmatrix}$</code> with $r>1$. Writing <code>$P=\begin{bmatrix}a &amp; b\\ c &amp; d\end{bmatrix}$</code> with $\lvert ad-bc\rvert=1$, the relation $Q=D^{-1}P^{-1}D$ implies that <code>$Q=(ad-bc)^{-1}\begin{bmatrix}d &amp; -br\\ -c/r &amp; a\end{bmatrix}$</code>, which is integer when $r\mid c$. Hence the most general pair is <code>$(P,Q)=\left(\begin{bmatrix}a &amp; b\\ rc' &amp; d\end{bmatrix},(ad-rbc')^{-1}\begin{bmatrix}d &amp; -rb\\ -c' &amp; a\end{bmatrix}\right)$</code> 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 <code>$\begin{bmatrix}a &amp; b\\c &amp; d\end{bmatrix}\mapsto\begin{bmatrix}d &amp; -rb\\-c/r &amp; a\end{bmatrix}$</code>. 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)$.</p> <p>The problem with this is that the set of generators 1&ndash;4 appears not to be adequate for the case $r=5$, for example. Andy Putman's question <a href="http://mathoverflow.net/questions/2757/generators-for-congruence-subgroups-of-sl-2" rel="nofollow">http://mathoverflow.net/questions/2757/generators-for-congruence-subgroups-of-sl-2</a> 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&ndash;4, and the number of generators grows as $p^3$.</p> <p>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&ndash;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$?</p> <p>This leads to the following <strong>additional questions:</strong></p> <ol> <li>Is the above understanding of $n=2$ correct? If so, what is the smallest set of generators one can write down?</li> <li>Do 1&ndash;4 generate the automorphism group for $n>3$? If so, how and where is this proved?</li> </ol> http://mathoverflow.net/questions/75127/automorphisms-of-a-matrix-in-smith-normal-form/75138#75138 Answer by Amritanshu Prasad for Automorphisms of a matrix in Smith normal form? Amritanshu Prasad 2011-09-11T11:32:29Z 2011-09-12T06:21:57Z <p>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}$).</p> <p>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$.</p> <p>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 <em>Birkhoff moves</em> (see <em>Subgroups of Finite Abelian Groups</em> by Garrett Birkhoff in Proceedings of the London Math. Society, 1935):</p> <ol> <li>Scaling any row/column by a $p$-free integer</li> <li>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$.</li> <li>Interchanging rows or columns with the same invariant factors.</li> </ol>