7
$\begingroup$

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.

Improve this question
$\endgroup$
7
  • 1
    $\begingroup$ 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. $\endgroup$
    – Ryan Budney
    Nov 2, 2010 at 16:55
  • 4
    $\begingroup$ 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 $\endgroup$
    – Yemon Choi
    Nov 2, 2010 at 17:25
  • 6
    $\begingroup$ Casting a vote against closing $\endgroup$
    – Yemon Choi
    Nov 2, 2010 at 17:25
  • 1
    $\begingroup$ @Yemon, that confuses me. I'm not sure reference requests for solutions to homeworkish-type problems are appropriate, either. $\endgroup$
    – Ryan Budney
    Nov 2, 2010 at 17:49
  • 2
    $\begingroup$ This MO entry mathoverflow.net/questions/31275/… is directly related to your question. You can find there a direct link to a paper of Kaplansky concerning which rings $R$ have the property that all matrices over $R$ are equivalent to ones in Smith normal form, and/or equivalent to diagonal matrices. By Theorem 5.1 of that paper, it is enough to verify this for matrices of maximal dimension 2. $\endgroup$
    – Sidney Raffer
    Nov 3, 2010 at 6:31

1 Answer 1

Reset to default
4
$\begingroup$

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.

Improve this answer
$\endgroup$
5
  • 2
    $\begingroup$ 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$. $\endgroup$
    – Homology
    Nov 3, 2010 at 16:09
  • $\begingroup$ @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. $\endgroup$
    – Sidney Raffer
    Nov 3, 2010 at 16:30
  • 2
    $\begingroup$ @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. $\endgroup$
    – Alex
    Nov 3, 2010 at 17:35
  • 2
    $\begingroup$ 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})$. $\endgroup$
    – Homology
    Nov 3, 2010 at 20:09
  • $\begingroup$ Ugh. Of course! $\endgroup$
    – Sidney Raffer
    Nov 3, 2010 at 21:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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