# Finding shortest non-zero vector $x$ satisfying $Ax=0 \pmod q$

Let $n$, $m$, and $q$ be positive integers (with $m > n$), and $A$ be a matrix over $\mathbb{Z}_q^{n \times m}$. Using Mathematica, I want to find the shortest non-zero vectors $x \in \mathbb{Z}_q^m$ such that:

$$Ax=0 \pmod q$$

Note: By "shortest," I mean the vector with the smallest Euclidean norm. I'm not sure if this vector is unique. If it's not, I want a list of vectors with smallest Euclidean norm.

Example:

Let: $n=2, m=3, q=7, A = \left(\begin{matrix} 2 & 1 & 6\\ 1 & 3 & 1 \end{matrix} \right)$. Then, the following vectors are solutions to

{1,1,3} $\quad$ Norm = $\sqrt{11}$

{3,3,2} $\quad$ Norm = $\sqrt{22}$

{2,2,6} $\quad$ Norm = $\sqrt{44}$

{5,5,1} $\quad$ Norm = $\sqrt{51}$

{4,4,5} $\quad$ Norm = $\sqrt{57}$

{6,6,4} $\quad$ Norm = $\sqrt{88}$

Therefore, the vector {1,1,3} is the shortest solution.

PS: I used an exhaustive search to find the above solutions. My approach takes a long time for even small choices of $n$ and $m$, say $n=2, m=8$. Please offer an approach which can at least find solutions for such small parameters.

Edit: As Michael suggested in a comment, I demonstrate the "exhaustive search" code I used. I'm not proud of it at all, as I just wrote the code to find an example for this question.

A = RandomInteger[6, {2, 3}];
x = {a, b, c};
Table[
If[Mod[A.x, 7] == {0, 0}, Print[{x, x // Norm}]],
{a, 0, 6}, {b, 0, 6}, {c, 0, 6}]

• You might show the code you tried -- perhaps it can be made efficient. Users are much more likely to try out your problem if they can cut and paste a starting point. – Michael E2 Jul 28 '13 at 20:24
• @MichaelE2: Thanks for the suggestion. I added the code snippet. It does not use Mathematica's built-in functions like Solve or FindMin. It's nothing more than an exhaustive search, and that's why it takes a long time to find a solution for even relatively small parameters. – M.S. Dousti Jul 28 '13 at 21:05
• (1) You are working in a ring that really does not have a notion of length. Why is a rock-bottom smallest in Euclidean norm result needed? – Daniel Lichtblau Jul 29 '13 at 14:12
• (2) One can get small results using lattice reduction. This unfortunately does not force values to be nonnegative. All the same, a usable vector might appear. In a run of your example I have mat = {{2, 3, 2}, {2, 6, 1}}. Then it turns out that {4,3,2} is the null vector of interest (though see (1) above-- I do not know why it is of interest). It appeas in the following lattice reduction. In:= LatticeReduce[ Join[NullSpace[A], 7*IdentityMatrix[Length[A[]]]]] Out= {{-2, 2, -1}, {1, -1, -3}, {4, 3, 2}} – Daniel Lichtblau Jul 29 '13 at 14:14
• You are wrong, but close. LatticeReduce is guaranteed to find a vector that is "short" (in Euclidean norm) in a particular sense. But it is not guaranteed to be shortest. In practice, it tends to be close. – Daniel Lichtblau Jul 30 '13 at 20:12

One way to approach this is to use the Null space of the matrix a, which is a basis for all elements x such that a.x=0. For the OPs problem, this can be done by first finding the null space:

a = {{2, 1, 6}, {1, 3, 1}};
n = First[NullSpace[a, Modulus -> 7]]

{5, 5, 1}


Now, observe that a.x=0 is true exactly when a.(c*x)=0, so it is possible to list all the answers (mod 7) to this problem by

Mod[# n, 7] & /@ Range

{{5, 5, 1}, {3, 3, 2}, {1, 1, 3}, {6, 6, 4}, {4, 4, 5}, {2, 2, 6}}


To find the one with smallest norm, apply the norm to each element,

Norm /@ (Mod[# n, 7] & /@ Range)

{Sqrt, Sqrt, Sqrt, 2 Sqrt, Sqrt, 2 Sqrt}


which gives the same answer as the OP found by search.

More generally, the NullSpace of a is a collection of $m-n$ vectors, and it will be necessary to search over all linear combinations of these $m-n$ vectors (mod $q$) for the one with the smallest norm. While this may still be large, it is certainly smaller than search over $m$ dimensions as in the brute force approach.

Using Solve helps a bit. If vars is the list of variables, then

Solve[A.vars == ConstantArray[0, n], vars, Modulus -> q]


finds all solutions in terms of parameters C, C, etc. depending on the dimension of the solution space.

Another bottleneck is computing the values of the general solution at all possible combinations of values for the parameters C[i] modulo q. The possible combinations can be computed with

Tuples[Range[0, q - 1], n]


where n is the number of parameters C[i]. The result is certainly reasonably fast for the small values of m, n, q mentioned in the question.

Finally Nearest will return the shortest nonzero vector (the zero vector having been deleted).

findSols[q_, A_] :=
Module[{m, n, vars, x, sol, vals, params, vecs},
{n, m} = Dimensions@A;
vars = Array[x, m];
sol = vars /. First @ Solve[A.vars == ConstantArray[0, n], vars, Modulus -> q];
(* Print@sol; *) (*optional output*)
params = Union@Cases[sol, _C, Infinity];
(* Print@params; *) (*optional output*)
vals = Transpose @ Tuples[Range[0, q - 1], Length@params];
vecs = DeleteCases[
Mod[#, q] &@ Transpose[sol /. MapThread[Rule, {params, vals}]],
ConstantArray[0, m]];
Nearest[vecs, ConstantArray[0, m]]
]


Example in OP:

A = {{2, 1, 6}, {1, 3, 1}};
findSols[7, A] // Timing
(* {0.000675, {{1, 1, 3}}} *)


Additional example with $m=8$. (Over 117000 solutions, still less than a second.)

SeedRandom;
A = RandomInteger[6, {2, 8}]

findSols[7, A] // Timing
(* {{5, 6, 1, 6, 2, 2, 6, 5}, {2, 1, 5, 5, 0, 0, 6, 4}} *)
(* {0.289682, {{0, 1, 0, 0, 1, 0, 1, 0}, {0, 1, 0, 0, 0, 1, 1, 0}}} *)


Note that for q = 17 there will be over 24,000,000 solutions -- I killed the kernel when it went past 20GB.