# Principal ideal ring, does there exist an invertible matrix such that certain matrix is upper triangular?

I asked here on Math Stack Exchange the following question.

Let $$R$$ be a principal ideal ring. If $$A$$ is any $$p \times q$$ matrix over $$R$$, then does there exist an invertible matrix $$U$$ in $$\text{M}_p(R)$$ such that the $$p \times q$$ matrix $$UA$$ is upper triangular?

Of course you can try row reduction: you should probably go look at Smith normal form. Of course that is written for principal ideal domains, but I don't remember the domain part being the important condition to execute row operations. I think you just need GCDs. (I should check, maybe there is something tricky.)

Part of the algorithm is the process of performing row operations to put the matrix in upper triangular form.

The process continues with aim invertible matrix on the right to get the matrix into a diagonal form.

My question is, can anybody here beef up what he wrote here into a more complete (but hopefully concise) proof? I still don't really see why what he suggests works.

• All you want (and more) can be gleaned from the answers to this question. Sep 30 '16 at 13:36
• Then why did you accept it???? Sep 30 '16 at 21:34

The answer to your initial question is yes, and Igor Rivin's comment is right and good. The result follows from the fact that a commutative PIR (Principal Ideal Ring) with identity is a Hermite ring in the sense of I. Kaplansky.

Indeed, a Hermite ring possesses a trigonal reduction as required, cf. [1, Theorem 3.5]. The fact that a commutative PIR with identity is a Hermite ring is given by [1, Theorem 12.3 and the subsequent remark] and can also be deduced from Hungerford's theorem [Theorem 1, 3] for instance (quotients and direct products of a Hermite rings are still Hermite). A PIR is actually an elementary divisor ring in the sense of I. Kaplansky (still a consequence of [Theorem 1, 3]), which is even stronger as it enjoys diagonal reduction. This is stated without proof in [Notes on Chapter I, 4].

Regarding rschwieb's answer, this approach fails already for a PID (Principal Ideal Domain) if you restrict to elementary row reduction. Indeed, you cannot row-reduce every $$2$$-by-$$1$$ matrices with coefficients in $$R = \mathbf{Z}[\frac{1 + \sqrt{-19}}{2}]$$ to a trigonal form $$\begin{pmatrix}* \\ 0 \end{pmatrix}$$, since otherwise $$R$$ would be a $$GE$$-ring in the sense of P. M. Cohn and it isn't [2, Introduction and Theorem 6.1]. Still, the approach is successful for a Euclidean ring $$R$$, as we have $$SL_n(R) = E_n(R)$$ in this case. Here $$E_n(R)$$ denotes the group generated by the elementary matrices, i.e., those matrices which induce the elementary row reduction moves preserving the determinant.

Thus row reduction, i.e., multiplication on the left by elementary matrices, is not sufficient to reduce a matrix to a trigonal form in a PID. However, reduction to a trigonal form is always achievable in PIDs if you allow multiplication by any invertible matrix on the left, which is your original problem. This is a subpart of the Smith Normal Form Theorem, the result rightly referred to by rschwieb and Igor Rivin. It is presented in some classical text books, e.g., "Abstract Algebra" of D. S. Dummit and R. M. Foote, which also handles Dedekind domains. Other readers may point you to sources of a more algorithmic nature; the Euclidean case is advisable as it is algorithmic by nature and far less technical than the PID case. I found the wiki page on the Smith normal Form pretty good algorithm-wise. It goes into the detail of not-so-trivial induction arguments based on the number of prime divisors of coefficients, something that is missing in the outline of rschwieb. (You'll see there that the matrix $$L_0 \in SL_2(R)$$ used in step II is not necessarily an elementary matrix).

The most general class of rings with reduction to a trigonal form is, by definition, the class of Hermite rings in the sense of Kaplansky. For a modern treatment see [4], where the author refers to K-Hermite rings. As stated above, this class includes PIRs. In my humble opinion, the issue with zero divisors was not a minor one.

[1] "Elementary divisors and modules", I. Kaplansky, 1949
[2] "On the structure of the $$GL_2$$ of a ring", P. M. Cohn, 1966.
[3] "On the structure of principal ideal rings", T. W. Hungerford, 1968.
[4] "Serre's problem on projective modules", T. Y. Lam, 2006.

• According to Brown's book "Matrices over commutative rings", it's not necessary to use Hungerford's theorem, but only Zariski-Samuel's structure theorem for commutative PIRs. On the other hand, do you know any other references abouth Hermite/elementary divisor rings?
– Xam
Aug 3 '17 at 17:54
• @Xam The book "Diagonal reduction of matrices over rings" (2012) by Bogdan Zabavsky contains a section dedicated to Elementary Divisor Rings. Aug 9 '17 at 15:20
• @Xam You are more than right, it is sufficient and I didn't realize at the time you wrote your comment that the Zariski-Samuel's structure theorem was actually used by I. Kaplansky to prove "PIR implies EDR". At this time, long before 1975, the aforementioned structure theorem was attributed to Krull. It was re-proved by Kaplansky in his 1949's paper.. Jun 8 '20 at 19:35

An elementary matrix is a $p\times p$ matrix of the form $$E^a_{i,j} = I + a e_{i,j},$$ where $I$ is the identity matrix, $a$ is any element in your ring, $i\neq j$, and $e_{i,j}$ is the standard matrix unit. It is easy to see that $E^a_{i,j}$ is always invertible and that its inverse is $E^{-a}_{i,j}$. The other crucial property of this matrix is that, for every $p\times q$ matrix $A$, the product $E^a_{i,j}A$ coincides with the matrix you get by multiplying the $j^{th}$ row of $A$ by $a$, and adding it to the $i^{th}$ row. This is therefore one of the elementary operations used to perform row reduction.

The other important operation used in row reduction, namely exchange of rows, is also easily seen to be obtained by left multiplying $A$ by a suitable invertible matrix. Thus, if you can transform $A$ into an upper triangular matrix using a finite number of elementary operations, you may also left multiply $A$ by the same number of invertible matrices, obtaining an upper triangular matrix, say $$U_1U_2\ldots U_nA=T,$$ from where your conclusion follows easily.

• You didn't mention any special property for the ring of matrix coefficients. Let us think about the trigonal reduction of a $1$-by-$2$ matrix in a principal ideal domain (PID, stronger than PIR). Fairly easy. But assume now you have zero divisors. What is your next move? Sep 30 '16 at 22:26
• "multiplying" is a bit misleading -- the $j$-th row itself doesn't get changed. Oct 1 '16 at 1:26
• My answer was intended to clarify the relationship between row reduction and left multipliction by a unitary matrix, which, as I understand, has not been made clear by MSE user rschwieb in his answer. @Luc is however correct in pointing out that one need special proprties of the ring in order to be able to row reduce any matrix into upper triangular form. AFAIK the best result in this direction is for rings satisfying Euclidean division.
– Ruy
Oct 1 '16 at 21:19
• @darij, you are right, the $j$-th row is not changed in the process. I may have been a bit unclear in my description, but what I really meant is that you get the same thing as when applying an elementary operation to $A$.
– Ruy
Oct 1 '16 at 21:24
• @Ruy: Now I understand your intention, thanks. But elementary row reduction as you describe it is not enough, even for a PID. For a Euclidean ring, we agree. (I updated my answer about these points). Oct 1 '16 at 23:19