Integer vector decomposition on a degenerate integer vectors basis Let's say I have a vector of integer numbers, and I would like to get a decomposition of that vector using a set of "basis" vectors (which are also integers), these vectors are arbitrary, i.e. they could and most definitely are linearly dependent. In matrix notation:
$M{\times}b=v$ where $v$ is a given $m{\times}1$ integers vector, $b$ is a $n{\times}1$ vector, $M$ is a given $m{\times}n$ integers matrix.
Is there any simple criteria to test if the system has integer solutions for the coefficients b and express these solutions ?
 A: In fact, the question is about free finitely generated abelian
groups. There are two solutions.
1) A criterion for existence of integer solution of the system of
equations $M\times x=b$ in a closed form. However it is difficult
to apply it for large matrices and it does not give the general
solution if the equation.
Let $D_k(M)$ denote the greatest common divisor of the
determinants of all $k\times k$ square submatrices of the matrix
$M$ (or zero if there is no such submatrices for given $k$). Then
the system of equations $M\times x=b$ has an integer solution if
and only if $D_k(M)=D_k(\bar M)$ for all $k\geq 1$, where $\bar
=(M|b)$ is the extended matrix of the system.
2) An algorithm ready for computer realization giving all integer
solutions of the system $M\times x=b$ (in particular the empty set
of solutions).
The key step is the reduction of an integer  matrix to a diagonal
one by means of a series of transformations  of the following
three types:
$T_1$. Addition to some row (column) of another row (column)
multiplied by any integer.
$T_2$. Interchanging two rows (columns).
$T_3$. Multiplication of a row (column) by$(-1)$.
The process goes as follows.
Step 1. If the matrix $A$ is zero or empty then stop.
Step 2. Choose a non zero element $d$ in $A$ with the least
absolute value and move it using $T_2$ to the upper left corner.
Step 3. Using $T_1$ substitute all elements in the first row and
the first column except the upper left element with their
remainders modulo $d$.
Step 4. If all elements in the first row and the first column
except the upper left element are zero then go to Step 1 for the
submatrix of $A$ formed by all rows and columns except the first
ones. Else go to Step 2.
The process ends since each repetition of Steps 2 and 3 decreases
the absolute value of the element in the upper left corner, and
each repetition of Step 4 decreases the size of the matrix.
To apply this reduction to solution of the system $M\times x=b$,
where $M$ has $m$ rows and $n$ columns let us first form a matrix
$\widehat M=\begin{pmatrix}M&b\\E&0\end{pmatrix}$, where $E$ is
the identity matrix of size $n\times n$, then using Step 1- Step 4
we reduce the submatrix $M$ of the matrix $\widehat M$ to diagonal
form $M'$ with nonzero integers $d_1,\ldots,d_k$ in the diagonal
cells. Since the transformations are applied to full rows and
columns of the matrix $\widehat M$ a new matrix $\widehat
M'=\begin{pmatrix}M'&b'\\Q&0\end{pmatrix}$ will be calculated. The
general solution of the equation $M'\times x'=b'$ is evident: if
$d_i$does not divide $b'_i$ for some $i$ or the $i$-th diagonal
cell contains 0 while $b'_i\neq 0$ then the set of solutions is
empty, otherwise $x_1',\ldots x'_k$ are given by $x_i'=b_i'/d_i$
and $x_i'$ are arbitrary integers for all $i=k+1,\ldots,n$ if
$k<n$. To obtain the general solution of the initial system it is
sufficient to set $x=Q\times x'$.
