Re: Re: Complete solution to a modular System of equations ( Correction)

• To: mathgroup at smc.vnet.net
• Subject: [mg60560] Re: [mg60513] Re: Complete solution to a modular System of equations ( Correction)
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Tue, 20 Sep 2005 05:19:25 -0400 (EDT)
• References: <200509160750.DAA00817@smc.vnet.net><dgh4fn\$ng4\$1@smc.vnet.net> <200509190845.EAA23469@smc.vnet.net>
• Sender: owner-wri-mathgroup at wolfram.com

```This got a bit confused as to who wrote what, and some was in email not
sent to MathGroup, so I'll annotate. --DL

mumat wrote:
MUMAT:
> Sorry Guess the 2^100 solutions ( binary vectors of length 200) using
> MAGMA
>
> http://magma.maths.usyd.edu.au/magma/htmlhelp/text598.htm
>

DL:
> This is not very clear so let me point out a few things.
>
> (1) You are not going to list 2^100 elements of anything.
>

MUMAT:
>>The Magma! listed all 2^100!!! i had tried that for the binary finite field F_2= Z_2=GF(2).
>

DL:
> (2) You mention 2^(n-k) solutions. Is k meant to be the matrix rank?
>

MUMAT:
>Yes, k is the rank of matrix in Z_2.
>

DL:
> (3) You mention Z_p^n. This is the ring of integers modulo p^n. Did you
> instead have in mind the Galois field of p^n elements? I assume not.
> Did
> you mean (Z_p)^n, the vector space of dimension n with elements in Z_p?
>

MUMAT:
>>Yes, I meant the vector space (Z_p)^n. Sorry, I had to parenthesize Z_p!
>

DL:
> Assuming that last is what you have in mind, just find a null space
> basis with NullSpace, then take all possible combinations.
>

MUMAT:
>>As you see i have computed all possible combinations... but's it's too slow.
>
>
> thanks much for your comments, Daniel.

A Google search with key phrase "atoms in universe" will quickly
indicate that one does not explicitly list 2^100 elements of anything.

As for an efficient way to list solutions of more modest length, one
might do as below.

allNullVectors[mat_, mod_Integer /; mod>1] := Module[
{nulls, len},
nulls = NullSpace[mat, Modulus->mod];
len = Length[nulls];
nulls, mod], {j,mod^len}]
]

Example:
mat = {{0, 0, 0, 1, 1, 0, 0}, {1, 1, 1, 1, 1, 1, 0},
{0, 0, 0, 0, 0, 1, 0}, {1, 0, 0, 1, 0, 0, 1}};

In[58]:= InputForm[allNullVectors[mat,2]]
Out[58]//InputForm=
{{0, 0, 0, 0, 0, 0, 0}, {0, 1, 1, 0, 0, 0, 0}, {1, 1, 0, 1, 1, 0, 0},
{1, 0, 1, 1, 1, 0, 0}, {1, 1, 0, 0, 0, 0, 1}, {1, 0, 1, 0, 0, 0, 1},
{0, 0, 0, 1, 1, 0, 1}, {0, 1, 1, 1, 1, 0, 1}}

Here is a 10 x 15 example, with timing.

In[59]:= InputForm[mat = Table[Random[Integer], {10}, {15}]]
Out[59]//InputForm=
{{1, 0, 1, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1},
{0, 1, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0},
{1, 1, 1, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 0, 0},
{0, 0, 0, 0, 1, 0, 0, 1, 1, 1, 0, 1, 0, 0, 0},
{1, 0, 1, 0, 1, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0},
{1, 0, 0, 1, 1, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0},
{0, 0, 1, 0, 1, 1, 0, 1, 0, 0, 0, 0, 0, 1, 1},
{0, 1, 1, 1, 1, 1, 1, 0, 1, 0, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 0, 0, 1, 1, 1, 0, 1, 0, 1, 1, 0},
{0, 1, 0, 1, 0, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0}}

In[60]:= InputForm[Timing[allNullVectors[mat,2]]]
Out[60]//InputForm=
{0.0010000000000006254*Second, {{0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0,
0}, {0, 1, 0, 0, 0, 1, 1, 1, 1, 0, 0, 0, 0, 0, 0},
{1, 0, 0, 1, 1, 1, 0, 0, 0, 1, 1, 0, 0, 0, 0},
{1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 1, 0, 0, 0, 0},
{1, 0, 1, 0, 0, 1, 1, 0, 0, 1, 0, 1, 1, 0, 0},
{1, 1, 1, 0, 0, 0, 0, 1, 1, 1, 0, 1, 1, 0, 0},
{0, 0, 1, 1, 1, 0, 1, 0, 0, 0, 1, 1, 1, 0, 0},
{0, 1, 1, 1, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0},
{1, 1, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0},
{1, 0, 1, 1, 0, 1, 1, 1, 1, 0, 0, 0, 0, 1, 0},
{0, 1, 1, 0, 1, 1, 0, 0, 0, 1, 1, 0, 0, 1, 0},
{0, 0, 1, 0, 1, 0, 1, 1, 1, 1, 1, 0, 0, 1, 0},
{0, 1, 0, 1, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 0},
{0, 0, 0, 1, 0, 0, 0, 1, 1, 1, 0, 1, 1, 1, 0},
{1, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 1, 1, 1, 0},
{1, 0, 0, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 1, 0},
{1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 0, 1, 0, 0, 1},
{1, 1, 1, 1, 0, 0, 0, 0, 1, 0, 0, 1, 0, 0, 1},
{0, 0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 1, 0, 0, 1},
{0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1, 1, 0, 0, 1},
{0, 0, 0, 1, 0, 0, 0, 1, 0, 1, 0, 0, 1, 0, 1},
{0, 1, 0, 1, 0, 1, 1, 0, 1, 1, 0, 0, 1, 0, 1},
{1, 0, 0, 0, 1, 1, 0, 1, 0, 0, 1, 0, 1, 0, 1},
{1, 1, 0, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1, 0, 1},
{0, 1, 0, 0, 0, 1, 1, 1, 0, 0, 0, 1, 0, 1, 1},
{0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, 1, 0, 1, 1},
{1, 1, 0, 1, 1, 0, 1, 1, 0, 1, 1, 1, 0, 1, 1},
{1, 0, 0, 1, 1, 1, 0, 0, 1, 1, 1, 1, 0, 1, 1},
{1, 1, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 1, 1, 1},
{1, 0, 1, 0, 0, 1, 1, 0, 1, 1, 0, 0, 1, 1, 1},
{0, 1, 1, 1, 1, 1, 0, 1, 0, 0, 1, 0, 1, 1, 1},
{0, 0, 1, 1, 1, 0, 1, 0, 1, 0, 1, 0, 1, 1, 1}}}

Daniel Lichtblau
Wolfram Research

```

• Prev by Date: Re: A Su Doku solver
• Next by Date: Re: NonlinearFit-Logistic Function-CalcCenter 3
• Previous by thread: Re: Complete solution to a modular System of equations ( Correction)
• Next by thread: Re: Complete solution to a modular System of equations