Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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|improve this question
add comment

Your Answer

 
discard

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

Browse other questions tagged or ask your own question.