Ask Your Question

Revision history [back]

One way is to define a generator that goes through symmetric zero-one matrices and yields those that are invertible.

There could be several variations, depending whether we want to consider the matrices as defined (and invertible) over $\mathbb{Z}$, $\mathbb{Q}$, or $\mathbb{Z}/2\mathbb{Z}$, and whether the inverses should also be zero-one matrices.

Here is a version which gives all symmetric zero-one invertible matrices over $\mathbb{Q}$, of size d by d.

def symmetric_invertible_zero_one_matrices(d, mutable=True):
    r"""
    Return a generator of symmetric invertible zero-one d by d matrices.

    EXAMPLES::

        sage: list(symmetric_invertible_zero_one_matrices(0))
        [[]]
        sage: list(symmetric_invertible_zero_one_matrices(1))
        [[1]]
        sage: list(symmetric_invertible_zero_one_matrices(2))
        [
        [0 1]  [1 1]  [1 0]  [0 1]
        [1 0], [1 0], [0 1], [1 1]
        ]
        sage: {d: sum(1 for m in symmetric_invertible_zero_one_matrices(d))
        ....:  for d in range(6)}
        {0: 1, 1: 1, 2: 4, 3: 32, 4: 528, 5: 18596}
    """
    M = MatrixSpace(QQ, d)
    n = d * (d + 1) // 2
    z = [0] * n
    for a in srange(2^n):
        c = z[:]
        b = a.bits()
        c[:len(b)] = b
        f = lambda i, j: (c[d*i - i*(i+1) // 2 + j])
        g = lambda i, j: f(i, j) if i <= j else f(j, i)
        m = M(g)
        if m.is_invertible():
            if not mutable:
                m.set_immutable()
            yield m

To make a set of them, use mutable=False.

sage: S = set(symmetric_invertible_zero_one_matrices(5, mutable=False))
sage: len(S)
18596