1

I would like to check if there is an easy way to implement a check of linear (in)dependence of vectors but using modular arithmetic mod 2.

For example, suppose you have the following 3 vectors:

  1. v1 = (1,1,0);
  2. v2 = (0,1,1);
  3. v3 = (1,0,1).

If we use scipy.linalg's null_space such that:

M = [[1,0,1],
     [1,1,0],
     [0,1,1]]
null_space(M)

we get as a result that the 3 vectors are linearly independent, which is obviously true.

However, what I want to check is linear (in)dependence considering modular arithmetic mod 2. In that case, it is easy to check that v3 = v1 + v2 (i.e., the three vectors are linearly dependent).

Is there any way to determine this in Python?

Thank you in advance.

UPDATE (02/01/2022): Is there an alternative to doing this with sympy as suggested in one of the answers below? While this solution works for small instances I have noticed (in growing the matrix size) that the code sometimes gets stuck for over 30hours without being able to move on. This is very dependent on the example, which I find fascinating. That is, for a given size while some examples are worked through reasonably quickly (~2hours) others get stuck and the code still hasn't found a solution after 30hours which is less than desirable.! So, is there really no way of doing this with numpy or something like that?

fcrp
  • 29
  • 3
  • Maybe this answer has some clues: https://stackoverflow.com/questions/31190182/sympy-solving-matrices-in-a-finite-field – cadolphs Nov 29 '21 at 16:22

2 Answers2

3

Here is a solution using sympy, adapted from the answer linked by @Lagerbaer.

When finding the nullspace using sympy, you can pass in an argument iszerofunc, which specifies what you consider to be zeros in your matrix. In the case of the field of integers mod 2, our zero function is lambda x: x % 2 == 0.

You can verify that running the following code outputs a non-zero nullspace.

import sympy
M = sympy.Matrix([[1,0,1],
     [1,1,0],
     [0,1,1]])
print(M.nullspace(iszerofunc=lambda x: x % 2 == 0))
Scriniary
  • 100
  • 3
1

Here is one relatively quick and simple implementation of matrix reduction to find a rank mod 2. To clarify, vectors $r_1, ..., r_k$ are linearly independent if and only if the matrix with rows $r_1, ..., r_k$ has rank k.

Matrix representation. I like to represent Z_2-matrices as dictionaries of the form { row index : set of column indices containing 1 }. This is not too important, but it is convenient to work with, and it can speed things up considerably if you have sparse matrices.

The reduction algorithm. We reduce rows one by one from top to bottom. For each row we try to push the left-most 1 as much to the right as possible by adding previous rows. To this extent, we look at the left-most 1, i.e., the index min(row), and check whether some other_row above has the same value min(row) == min(other_row). If it does, we add the other_row to row. We repeat until we cannot reduce row any more. Instead of searching through the rows every time, we store the information in pivot_inverse, a dictionary of the form {min(row) : row}. At the end, we have a reduced matrix with each non-zero row having a unique pivot -- the rank of the matrix is the number of pivots, equivalently the number of non-zero rows.

def list_to_sparse(M):
    '''Convert list of lists to row sparse matrix representation.'''
    return {row_index : set(index for index,value in enumerate(row) if value)
            for row_index, row in enumerate(M)}

def rank_Z2(M):
    '''Given a Z_2 matrix in row sparse representation, reduce it and return rank.'''
    pivot_inverse = {} # remembers which row has a pivot in a given column
    for row_index in sorted(M): # we reduce rows one by one from top to bottom
        pi = pivot_inverse.get(min(M[row_index], default=-1), -1)
        while M[row_index] and pi!=-1:
            M[row_index]^= M[pi] # add rows mod 2
            pi = pivot_inverse.get(min(M[row_index], default=-1), -1)
        if M[row_index]:
            pivot_inverse[min(M[row_index])] = row_index
        else: # we throw zero rows away
            M.pop(row_index)
    
    return len(pivot_inverse) # rank(M) is the number of pivots

Example. For the example from the question, we get the following:

M = [[1,0,1],
     [1,1,0],
     [0,1,1]]
M_sparse = list_to_sparse(M)
# now M_sparse = {0: {0, 2}, 1: {0, 1}, 2: {1, 2}}

rank_Z2(M_sparse)
# output: 2
# now M_sparse = {0: {0, 2}, 1: {1, 2}}

Performance. I am sure things can be sped up if we use better data types for the job, but the run time is decent. On my laptop a random 1000x1000 (very much not sparse) matrix is reduced in ~10 seconds.

import time
import random

rndM = [[random.randint(0,1) for i in range(1000)] for j in range(1000)]
rndM_sparse = list_to_sparse(rndM)
start_time = time.perf_counter()
rank = rank_Z2(rndM_sparse)
print(f"rank: {rank}")
print(f"time: {time.perf_counter() - start_time : .2f} seconds")

# output:
#     rank: 999
#     time:  9.82 seconds

We can make rndM sparser for example like this

rndM = [[1 - bool(random.randint(0,p)) for i in range(1000)] for j in range(1000)]

For p=100 we have around 10000 ones and we get the rank in around 3 seconds, for p=200 we have around 5000 ones and it takes less than a second .

The code also performs better when the rank is low, so for example non-sparse matrix with the same overall size but shaped 100x10000 gets reduced in about 1.5 seconds.

OnDraganov
  • 199
  • 7