1
$\begingroup$

Consider the lattice $\mathbb{Z}^n$ and a real matrix $A\in \mathbb{R}^{m\times n}$ ($m<n$) with orthonormal rows. Let $y\in A\mathbb{Z}^n\setminus\{0\}$ and consider the equation $Ax=y$. Is there a (good) upper bound on the smallest norm of such $x$ in terms of norms of $y$? I am hoping an upper bound of $n^c\|y\|$ for some $c > 1$ but $c^n\|y\|$ would be bad.

$\endgroup$

1 Answer 1

1
$\begingroup$

When $m \geq 1$, there is no universal bound of the form $c(n)|| y||$ for the smallest norm of such an $x$. To see this, let $X$ be the $\frac{1}{2}m(2n-1-m)$-dimensional manifold of real $m \times n$ matrices $A$ with orthonormal rows. Let $Z$ be the subset of matrices which have a rational entry in the first column, or which have a row with entries linearly dependent over $\mathbb{Q}$. Since $Z$ lies in a countable union of hypersurfaces of $X$, it has dense complement in $X$. In particular, there is a sequence $(A_k)_k \subset X \setminus Z$ such that $y_k = A_k e_1 \rightarrow 0$. But for each $k$, the vector $e_1$ is the unique $x \in \mathbb{Z}^n$ such that $A_k x = y_k$.

$\endgroup$
2
  • $\begingroup$ Thanks! How about a upper bound of form $c(n)\max\{\|y\|,1\}$? $\endgroup$
    – user58955
    Sep 13, 2016 at 15:05
  • $\begingroup$ Neither. Just replace $y_k$ by $\lfloor || y_k||^{-1} \rfloor y_k$ and $e_1$ by $\lfloor || y_k||^{-1} \rfloor e_1$ in my answer. $\endgroup$
    – js21
    Sep 14, 2016 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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