close

Wolfram Function Repository

Instant-use add-on functions for the Wolfram Language

Function Repository Resource:

 BitStringNullSpace

Source Notebook

A memory efficient form of computing the null space of a matrix modulo 2

Contributed by: Daniel Lichtblau

ResourceFunction["BitStringNullSpace"][{n1,n2,…},ncols]

treats the integers ni as vectors of zeros and ones, each having ncols bits, and returns integers representing a set of generators of the null space modulo 2.

Details and Options

The resulting integers represent bit strings that correspond to the null vectors form one would obtain using NullSpace with the option setting Modulus→2 on the bit vectors that correspond to the input.
The number of columns must be made explicit since there might be leading zeros in all rows.
ResourceFunction["BitStringNullSpace"] is intended for dense linear algebra. Sparse methods might be better suited for linear algebra modulo 2 when most matrix entries are zeros.

Examples

Basic Examples (2) 

Find the modulo-2 null space of a simple matrix:

In[1]:=
ResourceFunction["BitStringNullSpace"][{1, 2, 3}, 3]
Out[1]=
Image

Create a random matrix of bit vectors:

In[2]:=
SeedRandom[1111]; nrows = 7; ncols = 9; mat = RandomInteger[{0, 1}, {nrows, ncols}]; bitvecs = Map[FromDigits[#, 2] &, mat]
Out[6]=
Image

Find the 0‐1 null vectors mod 2, represented as integers:

In[7]:=
nullvecs = ResourceFunction["BitStringNullSpace"][bitvecs, ncols]
Out[7]=
Image

Scope (2) 

Create a large array of bit strings to use as a matrix:

In[8]:=
SeedRandom[1111]; bignrows = 1777; bigncols = 1789; bigbitvecs = Table[FromDigits[RandomInteger[{0, 1}, bigncols], 2], bignrows];

BitStringNullSpace is especially useful when working with matrices that might otherwise require excessive memory:

In[9]:=
Timing[bigbitnulls = ResourceFunction["BitStringNullSpace"][bigbitvecs, bigncols];]
Out[9]=
Image

Properties and Relations (2) 

Here is the matrix from which the bit vectors were created:

In[10]:=
mat
Out[10]=
Image

We see that the prior result agrees with NullSpace:

In[11]:=
nulls = NullSpace[mat, Modulus -> 2]
Out[11]=
Image
In[12]:=
Map[FromDigits[#, 2] &, nulls]
Out[12]=
Image
In[13]:=
% == nullvecs
Out[13]=
Image

Similarly, create a matrix of explicit 0‐1 vectors corresponding to the large integers:

In[14]:=
bigmat = Map[IntegerDigits[#, 2, bigncols] &, bigbitvecs];

NullSpace is substantially slower as compared to BitStringNullSpace:

In[15]:=
Timing[bigbitnulls2 = NullSpace[bigmat, Modulus -> 2];]
Out[15]=
Image

Check that the results agree:

In[16]:=
Map[FromDigits[#, 2] &, bigbitnulls2] === bigbitnulls
Out[16]=
Image

Version History

  • 2.0.0 – 10 July 2019
  • 1.0.0 – 03 April 2019

Related Resources

License Information