1
$\begingroup$

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 ?

$\endgroup$
2
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.