20
$\begingroup$

The elementary divisor theorem was originally proved by a calculation on integer matrices, using elementary (invertible) row and column operations to put the matrix into Smith normal form. That is the matrix is zero off the diagonal, and on the diagonal each entry divides the one below it.

This calculation immediately generalizes to matrices over any Euclidean ring.

The key point is that in a Euclidean ring the GCD of two elements can be found by a series of steps where, in each step, one of the arguments is not multiplied by any non-unit. Specifically you reduce an entry $B$ modulo an entry $A$ by adding some (generally non-unit) multiple of A to B to get a result with smaller Euclidean norm than $A$. But $B$ is not multiplied by anything in this step, and so certainly not multiplied by any non-unit.

This does not generalize directly to every PID. In a PID elements $A,B$ have a GCD which is a linear combination of them, But that linear combination may require non-unit multiples of each (even in the integers). And it is not obvious that in every PID the process can be broken into steps where one or the other argument enters the linear combination with no multiplier (or at worst some unit multiplier).

Is there either some way to do it that I have not seen, or a proof that in some PIDs it cannot be done? Can one calculate Smith normal forms over PIDs by elementary matrix operations?

The motivation for this question is to understand exactly what facts Emmy Noether faced when she gave her abstract algebra proof of the elementary divisor theorem for PIDs. Her proof was one striking confirmation that the Noetherian condition on rings is a powerfully useful idea.

The discussion by მამუკა ჯიბლაძე and Luc Guyot reveals the interesting point that, while the answer to my question is simply no for the case of the integers in $\mathbb{Q}(\sqrt{-19})$, you actually can get Smith normal forms for that case by essentially the same kind of arithmetic, if you also allow yourself to also add new columns to the matrix as new `work space.' But algebraic $K$-theory shows the answer remains negative for other cases even when you allow that. As to the history, it seems Noether could well have seen elementary matrix calculations as hopeless for the problem, but she could not have proved they cannot work. She is not known to have ever done things like concrete calculations on $\sqrt{-19}$.

$\endgroup$
  • 3
    $\begingroup$ The title is inappropriate. You should write invariant factors instead. Elementary divisors are factors $p^m$ of the invariant factors, where $p$ is irreducible. Even in a Euclidian domain, one cannot always compute them explicitly. For instance in a polynomial ring, one cannot factorize explicitly most polynomials of degree $\ge5$. $\endgroup$ – Denis Serre Jul 23 '17 at 7:02
  • $\begingroup$ @DenisSerre The title is changed. $\endgroup$ – Colin McLarty Jul 25 '17 at 4:43
12
$\begingroup$

The answer is no: it is not possible, in general, to reduce a matrix over a principal ideal domain (PID) to a diagonal (or trigonal) matrix by means of elementary row and column operations. (This topic has been discussed in this MO post).

The following example is a result proved by P. M. Cohn [1, Theorem 6.1 and subsequent discussion] in 1966 and doesn't rely on some $SK_1$ obstruction.

Let $R = \mathbb{Z} [\frac{1 + \sqrt{-19}}{2}]$ and let $\theta \in R$ be a root of $X^2 - X + 5$. Then $R$ is a PID (see, e.g., Hardy and Wright) and the $1$-by-$2$ matrix $( 3 - \theta,\, 2 + \theta)$ cannot be reduced to a trigonal form $(*, \, 0)$.

Edit. The following lines aim at comparing P. M. Cohn's example with those presented by მამუკა ჯიბლაძე in his answer.

Here is a first remark which applies to both examples of PIDs. Because the Bass stable rank of $R$ is at most $2$ (use Bass Cancellation Theorem), it easily follows that any $1$-by-$n$ matrix over $R$ with $n \ge 3$ can be reduced to a matrix of the form $(*, \, 0, \dots,\,0)$ using elementary transformations. This certainly contrasts with the above example of $1$-by-$2$ matrix.

This second remark only holds for P. M. Cohn's example. Let $E_n(R)$ denote the subgroup of $SL_n(R)$ generated the elementary matrices over $R$, i.e., those matrices which differ from the identity by a single off-diagonal entry. Then we observe that $SL_n(R)/E_n(R) \simeq SK_1(R)$ for every $n \ge 3$ by the classical stability theorems [2, Corollary 11.19] and $SK_1(R) = 1$ by the Bass-Milnor-Serre Theorem [2, Theorem 11.33]. For P. M. Cohn's matrix [1, Theorem 6.1], from which we borrowed the first row, this means that $\begin{pmatrix} 3 - \theta & 2 + \theta \\ - 3 - 2\theta & 5 - 2\theta \end{pmatrix} \in E_3(R) \setminus E_2(R)$.

Eventually, in the case of the D. Grayson's PID, i.e., $R = S^{-1} \mathbb{Z}[T]$, with $S$ the multiplicative subset generated by $T$ and the polynomials $T^m - 1$, one can find $A \in SL_2(R)$ such that $A \notin E_n(R)$ for every $n \ge 2$ (I am unable to provide an explicit matrix at the moment).


[1] "On the structure of the $GL_2$ of a ring", P. M. Cohn, 1966.
[2] B. Magurn, "An algebraic introduction to K-theory", 2002.

$\endgroup$
  • 1
    $\begingroup$ Wow. A ferociously concise proof, once you know this $R$ is a PID. $\endgroup$ – Colin McLarty Jul 23 '17 at 11:14
  • 1
    $\begingroup$ Sorry about retracting the acceptance but I think I had better let the community compare these answers for a while. $\endgroup$ – Colin McLarty Jul 23 '17 at 11:17
  • 1
    $\begingroup$ @ColinMcLarty No worry, I agree. I added some lines which should help compare the different examples. $\endgroup$ – Luc Guyot Jul 23 '17 at 13:11
  • 1
    $\begingroup$ I am confused now. Given $ax+by=1$ one seemingly does not have any obstacles to reduce $(a,b,0)$ to $(0,0,1)$ like this: $$\begin{aligned}(a,b,0)&\to(a,b,0+xa)\\ &\to(a,b,0+xa+yb)\\ =(a,b,1)&\to(a-a1,b,1)\\ =(0,b,1)&\to(0,b-b1,1)\\ =(0,0,1).\end{aligned}$$In other words, $(a,b,0)e_{13}(x)e_{23}(y)e_{31}(-a)e_{32}(-b)=(0,0,1)$. Where am I wrong?? $\endgroup$ – მამუკა ჯიბლაძე Jul 23 '17 at 17:26
  • 1
    $\begingroup$ @მამუკა ჯიბლაძე You are right, a part of my remark was vacuous. I just wanted to say that a $1$-by-$n$ matrix over any PID can be reduced to $(*,0,\dots,0)$ for $n > 2$. This is corrected now. $\endgroup$ – Luc Guyot Jul 23 '17 at 20:27
12
$\begingroup$

According to Wikipedia, examples of PIDs with nontrivial $SK_1$ have been first given by Ischebeck in "Hauptidealringe mit nichttrivialer $SK_1$-Gruppe" (Arch. Math. 35 (1980), 138–139) and by Grayson in "$SK_1$ of an interesting principal ideal domain" (JPAA 20 (1981), 157–163).

Closely related question: Why do we care whether a PID admits some crazy Euclidean norm?

$\endgroup$
  • 3
    $\begingroup$ Since StackExchange answers are archived, and are meant to help later readers as well as answer the OP, I will note that $SK_1$ is defined in algebraic $K$-theory and gives a colimit over all dimensions of the special linear groups on a given PID modulo the elementary matrix groups. So its nontriviality is precisely a negative answer to my title question. $\endgroup$ – Colin McLarty Jul 23 '17 at 10:14
  • 1
    $\begingroup$ @ColinMcLarty Nothing to be sorry about - that answer certainly describes a sharper result. I am also thinking on how do they compare. I believe the difference is whether one can still have elementary reductions if one is allowed to increase dimension - in that case stabilization to $SK_1$ may become relevant. $\endgroup$ – მამუკა ჯიბლაძე Jul 23 '17 at 11:27
  • 1
    $\begingroup$ @მამუკა ჯიბლაძე I edited my answer in order to add some elements of comparison. $\endgroup$ – Luc Guyot Jul 23 '17 at 13:06
  • 1
    $\begingroup$ @LucGuyot Thank you very much, I was trying to figure this out. I believe in the lower right corner of your matrix must be $5$ rather than $-5$, since $(3-\theta)(5-2\theta)-(2+\theta)(-3-2\theta)=21-4\theta+4\theta^2=21-4\theta+4(\theta-5)=1$ $\endgroup$ – მამუკა ჯიბლაძე Jul 23 '17 at 13:40

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.