# Finding all integer solutions to linear map

Supose we have a known matrix $A:\mathbb{R}^3 \mapsto \mathbb{R}^N$ where $N>3$.

Is the a way to find all solutions $\mathbf{x}$ to

\begin{align} A\mathbf{x} = \mathbf{I} \end{align}

where $|\mathbf{x}| \leq 2,\mathbf{I} \in \mathbb{Z}^N$?

The problem here is that $\mathbf{I}$ is not known, i.e. the question really is: What vectors $\mathbf{x}$ with length $\leq 2$ hits the $\mathbb{Z}^N$ integer lattice under the map $A$?

• If $A$ is rank $3$ a starting point could be to use the fact that there is one or several left inverses (you can probably find an expression for each coefficient of the left-inverse matrix) to obtain $\mathbf{x} = A^{-1}_L \mathbf{I}$ and then search all $\mathbf{I}$ such that $\left|A^{-1}_L \mathbf{I}\right| \leq 2$. – M. P. Oct 10 '17 at 12:09
• This is true but as the problem relates to reality unfortunately A is most often rank 2 and N is often > 25, considering that the norm if a typical row of A is ~6 (re-writing the matrix equation into inner product of $\langle \mathbf{a}_{row}, \mathbf{x} \rangle$ and looking for max & minimum of this expression), this turns into $I_j \in [-6,6] \forall j$. Thus the number of computations required would be $13^{25}$ and is quite unfeasible. I might have a solution using plane intersection theory and the Moore-Penrose inverse but i will post it only once i have tested it. – Daniel Korpi Kastinen Oct 11 '17 at 12:48