MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer
Are you using something along the lines of "the elementary divisors of an upper-triangular matrix are the elementary divisors of its diagonal part"? Why is that true? – darij grinberg Jun 6 '13 at 20:24
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

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.