Max limit on min magnitude of integer solution to underdetermined system of equations Given a system of equations on the form $\bar{a}_i\cdot\bar{x}=0\ \forall\ i\in\{1,\dots,d-1\}$, where $\bar{x}\in\mathbb{Z}^d\setminus\bar{0}$ must hold and $\bar{a}_i\in\{-L,-L+1,\dots,L-1,L\}^d\ \forall\ i\in\{1,\dots,d-1\}$ are known, linearly independent vectors, can we say anything about the non-trivial (non-zero) solution with the smallest magnitude? Can we limit it using big $O$ notation somehow?
 A: Non-trivial solutions may not exist. Let $A$ be the $(d-1)\times d$ matrix whose $i$-th row is $\tilde{a}_i$ for each $i$. By assumption, the rank of $A$ is $d-1$. Therefore $\ker(A)$ is one-dimensional. More specifically, by relabelling the columns of $A$ if necessary, we may write
$$
A\tilde{x}=\pmatrix{B&v}\pmatrix{y\\ c}
$$
where $B$ is invertible and $c$ is a scalar. The equation $A\tilde{x}$ thus becomes $By+cv=0$, or $y=cB^{-1}v$. The scalar $c$ cannot be zero, or else $y$ and $\tilde{x}$ become zero.
Although the entries of $B$ are bounded, when $B$ is close to singular, the entries of $B^{-1}$ can become very large. Hence the entries of $\tilde{x}$ can be very large too. E.g. consider
$$
B=\pmatrix{1&-1\\ &\ddots&\ddots\\ &&\ddots&-1\\ &&&1},
\quad v=\pmatrix{1\\ \vdots\\ \vdots\\ 1},
\quad y=c\pmatrix{1&1&\cdots&1\\ &\ddots&\ddots&\vdots\\ &&\ddots&1\\ &&&1}\pmatrix{1\\ \vdots\\ \vdots\\ 1}
=c\pmatrix{d-1\\ d-2\\ \vdots\\ 1}.
$$
As $c$ is a non-zero integer, $\|y\|_\infty$ (or $\|\tilde{x}\|_\infty$) is at least $d-1$. In particular, when $d>L+1$, there is not any feasible solution.
In general, if $v=0$, obviously the least-norm non-trivial solution is given by $\tilde{x}=(0,\ldots,0,1)^T$. If $v\ne0$, we may write $B^{-1}v=\frac1qw$ where $q$ is an integer and $w$ is an integer vector such that $w_1,w_2,\ldots,w_{d-1},q$ are relatively prime. Then the least-norm non-trivial integer solution is given by $c=\pm q$ or by $\tilde{x}=\pm\pmatrix{w\\ q}$. It is feasible if $\max\{|w_1|,|w_2|,\ldots,|w_{d-1}|,|q|\}\le L$.
