# Question about the elementary divisors of a special matrix

I have the following question:

Is there a closed formula for the elementary divisors of the Matrix $M=\lbrace (m_{ij})\rbrace_{i=1,...,n,\ j=1,...,k}$, where $m_{ij}$ is the greatest common divisor of $i$ and $j$?

I know that det$(M)=\varphi(1)\cdot ... \cdot \varphi(n)$, if $M$ is a$\$ $n\times n$ square matrix.

Here, $\varphi$ is Euler's totient function.

But how to compute the elementary divisors?

Thank you very much.

-

First consider the square case $n = k$. Let $A$ be the $n \times n$ matrix whose $(i,j)$ entry is $\phi(j)$ if $j | i$ and $0$ otherwise. Let $B$ be the matrix whose $(i,j)$ entry is $1$ if $i | j$ and $0$ otherwise. Now $M = AB$ follows from $$\sum_{k | \gcd(i,j)} \phi(k) = \gcd(i,j).$$ (More generally, you can replace $\gcd(i,j)$ by any natural number $m$ in the above identity.) Ok, now note that $A$ is lower triangular and $B$ is upper triangular. And in fact $B$ is in $GL_n(\mathbb{Z})$. So the elementary divisors of $AB$ are the same as $A$, which can be read off from the diagonal elements which are $\phi(1), \dots, \phi(n)$. (They're not the same as the the diagonal elements: you have to factor and rearrange so that $d_1 | d_2 | \dots | d_n$.)
For the more general situation, where you have a $k$ by $n$ matrix, assume $k \leq n$. Then define $A$ to be a $k \times k$ matrix and $B$ to be a $k \times n$ matrix, in similar fashion. The first $k \times k$ minor of $B$ is invertible over $\mathbb{Z}$, so you get the same elementary divisors as in the diagonal case, I believe.
Ah, I see. $A$ itself is the product of a unipotent triangular matrix (namely, the matrix defined just as $A$ but with entries $1$ instead of $\phi(j)$) with the diagonal matrix $\mathrm{diag}\left(\phi(1),\phi(2),...,\phi(n)\right)$. That's a bit more subtle than just reading off the elementary divisors from the diagonal, though. – darij grinberg Jun 6 '13 at 20:28
In the situation above, I'm thinking of $AB$ acting on $\mathbb{Z}^n$ (column vectors), and we want to understand the cokernel of this matrix. By itself, $B$ has cokernel zero, so we just have to understand the cokernel of $A$. – Abhinav Kumar Jun 7 '13 at 1:51