Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

Let $\vec v\in\mathbb Q^n$. Is there an efficient algorithm to compute the smallest (in the $\ell_\infty$ norm) nonzero vector $\vec w\in\mathbb Z^n$ such that $\vec v\cdot \vec w=0$? Equivalently, if we let $A$ be a matrix with columns consisting of a basis for the nullspace of $\vec v^T$, can we find the smallest element of $\mathbb Z^n$ in the image of $A$?

I would also be interested in approximation algorithms, which perhaps do not give the smallest such vector but the vector $\vec w'$ they give satisfies $\|\vec w'\|_\infty/\|\vec w\|_\infty < C$ for some $C$ which does not depend of $\vec v$ (but may depend on $n$). For example an algorithm which minimizes the $\ell_2$ norm would suffice.

share|cite|improve this question

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

Browse other questions tagged or ask your own question.