Intersection of the null space of a matrix with integer vectors

74 Views Asked by At

I have an $m\times n$ rational matrix $A$ which is full rank and has linearly independent columns. With $m>n$ I would like to find all integer values of $x$ for which

$$A\vec x=0$$

If $A$ was an integer matrix this could be calculated by using the Smith normal form to solve linear Diophantine equations. However, since $A$ has rational elements the solutions to $\vec x$ can also be rational. I would like to find a general form of the allowed values of $\vec x$ which are integers.

I would expect to be able to find some form like

$$\vec x=S\vec k$$

where $\vec k$ is a $n$-vector consisting of any choice of integers. My first guess is that

$$S=A^+(I-AA^+)$$

where $A^+$ is the Moore-Penrose inverse such that $A^+A=I$ and $(I-AA^+)$ is a projection onto the null space of $A$.

This would mean $$A\vec x=AA^+(I-AA^+)\vec k=(AA^+-AA^+AA^+)\vec k=(AA^+-AA^+)\vec k=0$$

But this would also mean

$$\vec x=S\vec k=(A^+-A^+AA^+)\vec k =(A^+-A^+)\vec k=0$$

Does this problem have a solution in general or for specific cases of $A$?