3
$\begingroup$

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.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
5
$\begingroup$

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.

Improve this answer
$\endgroup$
3
  • $\begingroup$ 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? $\endgroup$
    – darij grinberg
    Commented Jun 6, 2013 at 20:24
  • $\begingroup$ 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. $\endgroup$
    – darij grinberg
    Commented Jun 6, 2013 at 20:28
  • $\begingroup$ 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$. $\endgroup$
    – Abhinav Kumar
    Commented Jun 7, 2013 at 1:51

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .