Say you have some matrix $C\in\mathbb{Z}_k^{n\times m}$, where $k$ is composite, and say the rank of $C$ is $r$. Moreover, say that you have some prior knowledge that $C$ can be written as $C = AB$, where $A\in\mathbb{Z}_k^{n\times r}, B\in\mathbb{Z}_k^{r\times m}$, and $B$ is known to you. How might you go about finding $A$?
If these were matricies over a finite field, the answer would be quite simple:
- Take the rank decomposition of $C = A' B'$.
- Find the hermite normal form $H'$ of $B'$, and the transformation $U'$ such that $U'B' = H'$
- Repeat with $B$ to find $H, U$ such that $UB = H$
- The uniqueness of the hermite normal form should imply that $H = H'$, so $$C = A' B' = A' U'^{-1}UB$$ The answer is therefore $A = A' {U'}^{-1}U$.
I'm curious what can be done for matricies over $\mathbb{Z}_k$. The above algorithm fails in Sage at least as HNF computations are not implemented over this space (although I don't know if this is a fundamental limitation).