# 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
Yes that would take a long time. :) If you thought of Solve, you should have tried it! Another tip: Don't use Print to accumulate you results. Table will accumulate them; then DeleteCases[table, Null, Infinity], gets rid of the Nulls; then perhaps Flatten. Better yet, learn about Reap/Sow. – Michael E2 Jul 28 '13 at 22:03
(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[35]:= LatticeReduce[ Join[NullSpace[A], 7*IdentityMatrix[Length[A[[1]]]]]] Out[35]= {{-2, 2, -1}, {1, -1, -3}, {4, 3, 2}} – Daniel Lichtblau Jul 29 '13 at 14:14

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[7]

{{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[6])

{Sqrt[51], Sqrt[22], Sqrt[11], 2 Sqrt[22], Sqrt[57], 2 Sqrt[11]}


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[1], C[2], 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[2];
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.

-