I am looking for references for dealing with modular linear algebra. Specifically, let $A$ be an $m \times n$ matrix with entries in $\mathbb{Z}_k$, where $k \in \mathbb{N}$, $k>1$, can generally be non-prime. Given a system of linear equations
$$ A x = b \mod k, $$
how can I methodically determine
- Whether the system has a solution.
- The dimension of $\text{Col}(A)$, the $\mathbb{Z}_k-$span of the columns of $A$. I understand that if $k$ is not prime then $\text{Col}(A)$ is only a module, and not a vector space. We can still talk about its dimension, correct?
- How to compute a minimal set of vectors $u_1, \dots, u_r$ such that $$\text{Col}(A) \oplus \text{Span}_{\mathbb{Z}_k}\{u_1,\dots, u_r \} = \mathbb{Z}_k^m $$
These questions are easy to deal with when $k$ is prime, since then we just do linear algebra. But when $k$ is not prime, funny things happen since we are not talking about vector spaces anymore, but about modules over rings. For example, matrices may not be reducible to row-echelon form.
Ideally, I would like to understand better how much of the linear algebra I am familiar with goes through. For example, do we still get a rank-nullity theorem in this case?
Best Answer
Linear algebra is not so simple over rings which are not fields. For instance, dimension is no longer a sufficient concept to grasp questions like yours about the column space of a matrix. Since this could be any module, one instead needs to specify which one, using a classification of $\mathbb{Z}_k$-modules as the $k$-torsion abelian groups. Dimension is only well defined for the free modules. In particular, it doesn't make sense to ask for a rank-nullity theorem.
If we try to define dimension as you did in the comments, then the $1\times 1$ matrix $2$ over $\mathbb{Z}/4$ violates the rank-nullity theorem.
Since the classification of finitely generated abelian groups is simple, the above isn't that severe a complication. But you'll be in more trouble on finding a complement to the column space, as you ask in your last question. Again, in the "matrix" $2$ over $\mathbb{Z}/4$, the column space is $2\mathbb{Z}/4$, which is not a direct summand of $\mathbb{Z}/4$. In general, submodules over a ring need not have complements.
As for solving equations, as suggested in the comments one can lift the coefficients to $\mathbb{Z}$, compute the Smith normal form up there, and then reduce modulo $k$. One can also use the Chinese Remainder Theorem to work over fields if $k$ happens to be a product of distinct primes-just solve your problem separately modulo each prime factor.