Finding minimal generating sets of submodules of $\mathbb{Z}_d^k$ Let $M$ be a submodule of $\mathbb{Z}_d^k$. A minimal generating set $G$ of $M$ is a subset $G \subseteq M$, such that $G$ generates $M$, and $|G| \leq |G'|$, for any other generating set $G'$ of $M$. I want to know the following:

*

*Is there an efficient algorithm for computing a minimal generating set of $M$. Suppose that we are given $M$ in terms of a generating set, i.e. we are given a set $S = \{s_1,s_2,\dots,s_{\ell}\} \subseteq \mathbb{Z}_d^k$ such that $M$ is generated by $S$. If not, is it known what is the complexity class of the problem?

The naive way to do this will be to generate all possible subsets of $M$ and see if they generate $M$, and pick the one with the smallest size.
 A: I think I can answer this question based on the comments of @JyrkiLahtonen above.
We start by putting the elements of $S$ into the columns of a matrix $A \in \mathbb{Z}_d^{k \times \ell}$. Then $M$ is the submodule generated by the columns of $A$, i.e. $M = \{Ax : x \in \mathbb{Z}_d^{\ell}\}$. The minimal number of generators of $M$ is given by the number of non-zero elements of the diagonal matrix of the Smith Normal Form (SNF) of $A$.
Recall the SNF: if $R$ is a principal ideal ring, then for any matrix $B \in R^{m \times n}$, there exist invertible matrices $P \in R^{m \times m}$ and $Q \in R^{n \times n}$, such that $AQ = PD$, where $D \in R^{m \times n}$ is a diagonal matrix. Moreover the diagonal elements of $D$ satisfy a "chain of divisibilities" condition, which I won't mention, as I don't need it in this argument, but can be found here. The diagonal elements of $D$ are also determined uniquely up to multiplication by units (invertible elements) of $R$. The SNF is unique modulo these conditions on $D$. $\mathbb{Z}_d$ is a principal ideal ring, so the SNF applies for matrices over $\mathbb{Z}_d$.
One important property that easily follows from the properties of SNF mentioned above is the following: let $t$ be the number of non-zero columns of $A$. Then the number of non-zero entries of $D$ is at most $\min \{t,m,n\}$.
Also I think the following is true, though I can't seem to find an easy reference for this (may be someone knows a citable source): if the columns of two square matrices $X, Y \in \mathbb{Z}_d^{k \times k}$ generate the same submodule, then $X = Y P$ for some invertible matrix $P$. This fact has now been answered in this MathOverflow answer.
Now we return to the proof. We compute the SNF of $A$. So we get $AQ=PD$, and let us denote $PD = \begin{bmatrix} P_1 & 0 \end{bmatrix}$, where the number of columns of $P_1$ equal the number of non-zero entries of $D$ (and by invertibility of $P$ and uniqueness of SNF, the columns of $P_1$ are all non-zero). So we get that $M$ is generated by the columns of $P_1$. We need to show that this is also a minimal generating set of $M$.
Suppose there is a matrix $T \in \mathbb{Z}_d^{k \times q}$, where $q$ is less than the number of columns of $P_1$, and whose columns also generate $M$. Complete $P_1$ and $T$ to square matrices of shape $k \times k$ by adding zero columns, and call them $\overline{P_1}$ and $\overline{T}$. Then there exists an invertible matrix $U$ such that $\overline{P_1} = \overline{T}U$. If $\overline{P_1}$ has a SNF given by $\overline{P_1} = E \overline{D} F$ for invertible matrices $E,F$, then $\overline{T}$ has a SNF given by $\overline{T} = E \overline{D} (FU^{-1})$.
Now number of non-zero elements of $\overline{D}$ is less than $q$, and also equal to number of columns of $P_1$, which is a contradiction.
