This is a small Python library implementing an object Mat2 of matrices over F2, the two-element (boolean) field. Import it as:
from f2linalg import Mat2
Its constructor takes a list of lists of 0 and 1, representing a matrix.
# some 3x3 square matrices
m = Mat2(
[[1, 0, 1],
[0, 1, 1],
[1, 1, 1]])
k = Mat2(
[[1, 1, 1],
[1, 1, 1],
[1, 1, 1]])
# a 3x4 rectangular matrix
n = Mat2(
[[1, 0, 1, 1],
[0, 1, 1, 1],
[1, 1, 1, 0]])
# 3x1 matrices, i.e. column vectors
v = Mat2([[1], [0], [1]])
v1 = Mat2([[1], [1], [1]])
# a 1x3 matrix, i.e. a row vector
w = Mat2([[1, 1, 1]])
# a 2x2 identity matrix
id5 = Mat2.id(2)
# a 3x2 all-zero matrix
z32 = Mat2.zeros(3, 2)
print(m, k, n, v, v1, w, id5, z32, sep='\n\n')
[ 1 0 1 ] [ 0 1 1 ] [ 1 1 1 ] [ 1 1 1 ] [ 1 1 1 ] [ 1 1 1 ] [ 1 0 1 1 ] [ 0 1 1 1 ] [ 1 1 1 0 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 1 1 ] [ 1 0 ] [ 0 1 ] [ 0 0 ] [ 0 0 ] [ 0 0 ]
+ is overloaded to perform matrix/vector addition (modulo 2), and * to perform F2 matrix multiplication.
print(
v + v1,
m + m,
m * v,
m * k,
w * m * v,
m * (v + v1),
sep='\n\n')
[ 0 ] [ 1 ] [ 0 ] [ 0 0 0 ] [ 0 0 0 ] [ 0 0 0 ] [ 0 ] [ 1 ] [ 0 ] [ 0 0 0 ] [ 0 0 0 ] [ 1 1 1 ] [ 1 ] [ 0 ] [ 1 ] [ 1 ]
transpose() returns the transpose:
print(n, n.transpose(), sep='\n\n')
[ 1 0 1 1 ] [ 0 1 1 1 ] [ 1 1 1 0 ] [ 1 0 1 ] [ 0 1 1 ] [ 1 1 1 ] [ 1 1 0 ]
Almost all non-trivial functionality is implemented using the gauss method under the hood. This performs (in-place) reduction to row echelon form and reduced row echelon form (full_reduce=True).
n_ref = n.copy()
n_ref.gauss()
n_rref = n.copy()
n_rref.gauss(full_reduce=True)
print(n, n_ref, n_rref, sep='\n\n')
[ 1 0 1 1 ] [ 0 1 1 1 ] [ 1 1 1 0 ] [ 1 0 1 1 ] [ 0 1 1 1 ] [ 0 0 1 0 ] [ 1 0 0 1 ] [ 0 1 0 1 ] [ 0 0 1 0 ]
It takes an optional parameter x which is can be used to perform Gaussian elimination on an augmented matrix, e.g. to solve linear systems or invert a matrix.
For example, we can solve the linear system m * x = b as follows:
mg = m.copy()
b = Mat2([[1], [0], [1]])
print('system:')
for i in range(m.rows()):
print(' + '.join([f'{m[i,j]}*x{j}' for j in range(m.cols())]) + f' = {b[i,0]}')
mg.gauss(x=b, full_reduce=True) # this results in `b` getting transformed to the solution `x`
print('\nsolution:', *[f'x{i} = {b[i,0]}' for i in range(m.rows())], sep='\n')
system: 1*x0 + 0*x1 + 1*x2 = 1 0*x0 + 1*x1 + 1*x2 = 0 1*x0 + 1*x1 + 1*x2 = 1 solution: x0 = 1 x1 = 0 x2 = 0
...and invert a matrix as follows:
mg = m.copy()
mi = Mat2.id(3)
mg.gauss(x=mi, full_reduce=True)
print(
m,
mi,
m * mi,
mi * m,
sep='\n\n'
)
[ 1 0 1 ] [ 0 1 1 ] [ 1 1 1 ] [ 0 1 1 ] [ 1 0 1 ] [ 1 1 1 ] [ 1 0 0 ] [ 0 1 0 ] [ 0 0 1 ] [ 1 0 0 ] [ 0 1 0 ] [ 0 0 1 ]
You can also get these via convenience methods solve() and inverse(), which do not change m or b.
b = Mat2([[1], [0], [1]])
print(f'x =\n{m.solve(b)}', f'mi =\n{m.inverse()}', sep='\n\n')
x = [ 1 ] [ 0 ] [ 0 ] mi = [ 0 1 1 ] [ 1 0 1 ] [ 1 1 1 ]
You can get the rank of a matrix with rank. Any rank-R matrix of size MxN can always be factored as k = k0 * k1 where k0 is an MxR matrix and k1 is an RxM matrix, using the factor method.
k0, k1 = k.factor()
print(f'rank(k) = {k.rank()}', k0 * k1, k0, k1, sep='\n\n')
rank(k) = 1 [ 1 1 1 ] [ 1 1 1 ] [ 1 1 1 ] [ 1 ] [ 1 ] [ 1 ] [ 1 1 1 ]
The nullspace() method returns a spanning set for the nullspace (a.k.a. kernel) of the matrix. That is, it is a spanning set of solutions for the associated homogeneous system of equations.
k.nullspace()
[[ 1 ] [ 1 ] [ 0 ], [ 1 ] [ 0 ] [ 1 ]]
It returns an empty list if the matrix is invertible, meaning the only vector in the nullspace is 0:
m.nullspace()
[]