Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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];
   Table[Mod[PadLeft[IntegerDigits[j-1,mod],len].
     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

• References:
  • Complete solution to a modular System of equations
    • From: "mumat" <csarami@gmail.com>
  • Re: Complete solution to a modular System of equations ( Correction)
    • From: "mumat" <csarami@gmail.com>