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
$\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$.

| cite | improve this answer | |
$\endgroup$
  • $\begingroup$ Thanks! How about a upper bound of form $c(n)\max\{\|y\|,1\}$? $\endgroup$ – user58955 Sep 13 '16 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 '16 at 6:58

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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