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 – Lagerbaer Nov 29 '21 at 16:22

1 Answers1

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