Evaluate

Basic Examples

Find the modulo 2 null space of a simple matrix:
[◼]
BitStringNullSpace
[{1,2,3},3]
In[]:=
{4}
Out[]=
Create a random matrix of bit vectors:
SeedRandom[1111];​​nrows=7;​​ncols=9;​​mat=RandomInteger[{0,1},{nrows,ncols}];​​bitvecs=Map[FromDigits[#,2]&,mat]
In[]:=
{39,425,395,375,251,102,115}
Out[]=
Find the 0-1 null vectors mod 2, represented as integers:
nullvecs=
[◼]
BitStringNullSpace
[bitvecs,ncols]
In[]:=
{325,136}
Out[]=

Scope

Create a large array of bit strings to use as a matrix:
SeedRandom[1111];​​bignrows=1777;​​bigncols=1789;​​bigbitvecs=Table[FromDigits[RandomInteger[{0,1},bigncols],2],bignrows];
In[]:=
BitStringNullSpace
is especially useful when working with matrices that might otherwise require excessive memory:
Timingbigbitnulls=
[◼]
BitStringNullSpace
[bigbitvecs,bigncols];
In[]:=
{4.548,Null}
Out[]=

Properties and Relations

Here is the matrix from which the bit vectors were created:
mat
In[]:=
{{0,0,0,1,0,0,1,1,1},{1,1,0,1,0,1,0,0,1},{1,1,0,0,0,1,0,1,1},{1,0,1,1,1,0,1,1,1},{0,1,1,1,1,1,0,1,1},{0,0,1,1,0,0,1,1,0},{0,0,1,1,1,0,0,1,1}}
Out[]=
We see that the prior result agrees with
NullSpace
:
nulls=NullSpace[mat,Modulus2]
In[]:=
{{1,0,1,0,0,0,1,0,1},{0,1,0,0,0,1,0,0,0}}
Out[]=
Map[FromDigits[#,2]&,nulls]
In[]:=
{325,136}
Out[]=
%nullvecs
In[]:=
True
Out[]=
Similarly, create a matrix of explicit 0-1 vectors corresponding to the large integers:
bigmat=Map[IntegerDigits[#,2,bigncols]&,bigbitvecs];
In[]:=
NullSpace
is substantially slower as compared to
BitStringNullSpace
:
Timing[bigbitnulls2=NullSpace[bigmat,Modulus2];]
In[]:=
{23.492,Null}
Out[]=
Check that the results agree:
Map[FromDigits[#,2]&,bigbitnulls2]===bigbitnulls
In[]:=
True
Out[]=