Existence of integer solution of a linear system of equations

128 Views Asked by At

Let $\phi: \mathbb R^d \to \mathbb R^n$ be an injective linear transformation given by an $n \times d$ integer matrix. Suppose that the rows of the matrix are primitive lattice points, i.e., in each row the g.c.d. of all non zero entries is $1$. Let $v \in \phi(\mathbb R^d)$ be an integer vector. Can I find an $u \in \mathbb Z^d$ such that $\phi(u)=v$?

I think the injectiveness is not needed here.

2

There are 2 best solutions below

0
On BEST ANSWER

Let your matrix be $A=\pmatrix{2&3\cr4&5\cr}$, let $v=\pmatrix{1\cr0\cr}$, then the only solution to $Ax=v$ is $x=\pmatrix{-5/2\cr2\cr}$

1
On

In general, no.

The linear system may or may not have a solution in $\Bbb Q^d$. If not, there is of course also no solution in $\Bbb Z^d$. If there is a rational solution, it is unique (by injectivity) and may or may not be integer.