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

Ax=0 \pmod qAx=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)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\quad Norm = \sqrt{11}\sqrt{11}

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

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

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

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

{6,6,4} \quad\quad Norm = \sqrt{88}\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 nn and mm, say n=2, m=8n=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

=================

2 Answers

2

=================

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-nm-n vectors, and it will be necessary to search over all linear combinations of these m-nm-n vectors (mod qq) for the one with the smallest norm. While this may still be large, it is certainly smaller than search over mm 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=8m=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.