# 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 ?

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'$.