monic_span

ssip.monic_span_checker.monic_span(M: ~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy.uint8]], N: ~numpy.ndarray[~typing.Any, ~numpy.dtype[~numpy.uint8]]) -> (<class 'dict'>, <class 'dict'>)

Checks that there is a monic span with a logical operator subcomplex at the apex, with each morphism mapping basis elements to basis elements, and returns the relevant data required to construct that span (there may be multiple, in which case it returns the first it finds). We approach this by checking that two boolean matrices M and N are equivalent up to permutation of rows/columns, i.e. PMQ = N for some permutation matrices P, Q. This is the same as finding a hypergraph isomorphism, if it exists, which can be reduced in poly-time (but at the cost of increased space) to finding a graph isomorphism for bipartite graphs, as described in p1 of “Colored Hypergraph Isomorphism is Fixed Parameter Tractable”. We use NetworkX and the VF2 algorithm to find the graph isomorphisms. Despite formidable worst-case complexity, this routine is fast in practice.

Parameters:

• M – The first F_2 matrix.

• N – The second F_2 matrix.

Returns:

The hypergraph isomorphism, which is a bijective map on columns and corresponding bijective map on rows.