Linalg Encoding

from sympy import Matrix
import numpy as np

# produce the original, "used" tape
tape = np.random.randint(2, size=(8, ))
zeros, ones = np.bincount(tape)

# produce new data to encode, for convenience make it exactly the same
# length as the number of free bits in our tape
data = np.random.randint(2, size=(zeros, ))

# produce the random matrix A
matrix = np.random.randint(2, size=(zeros, 8))

# select columns in A corresponding to zero/free bits in the tape
matrix_prime = matrix[:, tape == 0]

# create augmented matrix from A' and X'
aug_matrix = Matrix(np.hstack((matrix_prime, data.reshape((zeros, 1)))))

# put it in reduced row echelon form
rref, cols = aug_matrix.rref()

# solve for X', reduce mod 2
x_prime = (1 - np.array(rref)[:, -1]) % 2

# ensure nonzero
assert np.any(x_prime)

# insert X' into the tape at zero/free bits, producing X
x = tape.copy()
x[tape == 0] = x_prime

# multiply the matrix with 1-X, reduce mod 2
result = matrix.dot(1 - x) % 2

# ensure X is not all 1s
assert not np.all(x)

print(tape)
print(data)
print(result)