# “Linear algebra” over Z/nZ - reference please!

Let A be a matrix with entries in Z/nZ. (n is not assumed to be prime.) Then the size of the row span is the size of the column span. All computations are mod n, so both these numbers are finite.

I believe you can prove this using Smith normal form: both the size of the row span and the size of the column span will be the same after passing to the Smith normal form (lift the matrix entries to Z to compute the Smith normal form). When A is in Smith normal form, these quantities can be easily computed.

I would like to find a reference for this fact, and would be grateful to anyone who could provide one.

-
Alex, your question is quite appropriate for the math.stackexchange website. It is very close to a what I might see as a homework problem in a linear algebra course (over rings). I've voted to close. –  Ryan Budney Nov 2 '10 at 16:55
To be fair, Ryan, Alex is asking for a reference not a solution. So while the question may be basic it is not a HW question per se, especially since Alex has actually described his idea for a solution –  Yemon Choi Nov 2 '10 at 17:25
Casting a vote against closing –  Yemon Choi Nov 2 '10 at 17:25
@Yemon, that confuses me. I'm not sure reference requests for solutions to homeworkish-type problems are appropriate, either. –  Ryan Budney Nov 2 '10 at 17:49
I agree with Yemon. I don't think that this question should be closed! –  Martin Brandenburg Nov 2 '10 at 21:16

Your idea of using Smith normal form leads directly to a solution: But you need to verify that for every matrix $M$ with entries in $\mathbb{Z}/n\mathbb{Z}$ there are invertible matrices $A$ and $B$ with entries in $\mathbb{Z}/n\mathbb{Z}$ such that $AMB$ is in Smith normal form. It is essential that $A$ and $B$ be invertible as matrices over $\mathbb{Z}/n\mathbb{Z}$, otherwise the row and column spaces of $AMB$ won't necessarily be the same size as those of $M$.

A ring with the property that every matrix is equivalent to one in Smith normal form is called an elementary divisor ring. In the book "Matrices over Commutative Rings" by William Brown (Marcel Dekker 1993) it is shown (Theorem 15.8 and 15.9) that every principal ideal ring is an elementary divisor ring. It is simple to check that the rings $\mathbb{Z}/n\mathbb{Z}$ are principal ideal rings. So there's the reference you asked for. If you can't find the book by Brown the article by Kaplansky mentioned in the comments has the same material in a more general setting.

-
In fact you don't need to prove anything over $\mathbb{Z}/n\mathbb{Z}$ here: lifting $M$ anyhow over $\mathbb{Z}$ and applying the Smith normal form, you can then reduce mod $n$. –  Homology Nov 3 '10 at 16:09
@Homology: But then one still has to check that the matrices $A$ and $B$ are invertible mod n. I suppose this can be done directly. –  SJR Nov 3 '10 at 16:30
@SJR This is easy, since the matrices A and B will be products of unipotent integer matrices (coming from row/column addition operations) and permutation matrices. Such matrices generate SL_m(Z), and also correspond to the steps in the algorithm for finding Smith Normal Form. Thank you for the reference. I think this is as close as I will get to an exact reference for the fact in question. –  Alex Nov 3 '10 at 17:35
It's even easier than that: if $f: R \rightarrow R'$ is a morphism of rings and $A \in \mathrm{GL}_n(R)$, then $f(A) \in \mathrm{GL}_n(R')$, with $f(A)^{-1}=f(A^{-1})$. –  Homology Nov 3 '10 at 20:09
Ugh. Of course! –  SJR Nov 3 '10 at 21:21