Tests for GF(2) linear algebra

The linear module defines functions that test for linearity of functions defined on GF(2) vector spaces.

AUTHORS:

  • Paul Leopardi (2023-01-16): initial version

boolean_cayley_graphs.linear.is_linear(dim, perm, certificate=False)[source]

Check if a permutation on range(2**dim) is linear on GF(2)**dim.

INPUT:

  • dim – the dimension of the GF(2) linear space.

  • perm – a function from range(2**dim) to iself, usually a permutation.

  • certificate – bool (default False). If true, return the GF(2) matrix

    that corresponds to the permutation.

OUTPUT:

If certificate is false, a bool value. If certificate is true, a tuple consisting of either (False, None) or (True, M), where M is a GF(2) matrix that corresponds to the permutation.

EXAMPLES:

sage: from boolean_cayley_graphs.linear import is_linear
sage: dim = 2
sage: perm1 = lambda x: x*3 % 4
sage: is_linear(dim, perm1)
True
sage: is_linear(dim, perm1, certificate=True)
(
      [1 0]
True, [1 1]
)
sage: perm2 = lambda x: (x+1) % 4
sage: is_linear(dim, perm2)
False
sage: is_linear(dim, perm2, certificate=True)
(False, None)