615.sagews

import networkx.generators.atlas
atlas_graphs = [Graph(i) for i in networkx.generators.atlas.graph_atlas_g()]

def minimum_rank(F, g):
    """
    Returns the minimum rank of the graph g over the field F.  This is done by exhaustively iterating 
    through all possible matrices in S(F,G).
    
    EXAMPLES:
        
        sage: min_rank, mat = minimum_rank(FiniteField(3), graphs.PathGraph(4))
        sage: min_rank
        3
        sage: mat
        [1 1 0 0]
        [1 1 1 0]
        [0 1 0 1]
        [0 0 1 0]
    """
    A=g.adjacency_matrix().change_ring(F)
    n=g.order()
    nonzero_elements = [e for e in F if e != 0]
    all_possible_nonzero_entries = CartesianProduct(*[nonzero_elements]*g.size())
    nonzero_positions = set(g.edges(labels=False))
    diagonals = VectorSpace(F, n) # The vector space of n-dimensional vectors over F

    minimum_rank = n

    for nonzero_entries in all_possible_nonzero_entries:
        #print "testing nonzero entries: ", nonzero_entries
        
        # Set the nonzero positions
        for position, entry in zip(nonzero_positions, nonzero_entries):
            A[position] = entry
            # and the symmetric entry
            A[position[1], position[0]] = entry
    
        # Iterate through all the diagonals
        for diagonal in diagonals:
            for index, diagonal_entry in enumerate(diagonal):
                A[index, index] = diagonal_entry

            new_rank = A.rank()
            if new_rank < minimum_rank:
                minimum_rank = new_rank
                minimum_rank_matrix = A.copy()
                print "min rank example: rank ", minimum_rank
                print minimum_rank_matrix
                print sage_input(minimum_rank_matrix)
                print

    return minimum_rank, minimum_rank_matrix

g=atlas_graphs[1124]
show(g)

The minimum rank function calculation below takes a long time because it is iterating through almost 36 million matrices.  To see this, off-diagonal nonzero entries can be one of two values, and diagonal entries can be one of three values, so we have:

2^g.size()*3^g.order()

35831808

However, we can interrupt the calculation after just a few seconds since we know that the minimum rank is at least 3 from zero forcing, and we quickly find a matrix with rank 3 over the finite field of size 3.

minimum_rank(FiniteField(3), g)

min rank example: rank 6 [0 1 1 1 1 0 0] [1 0 1 1 1 0 0] [1 1 0 1 1 0 0] [1 1 1 0 1 1 0] [1 1 1 1 0 1 1] [0 0 0 1 1 0 1] [0 0 0 0 1 1 0] matrix(GF(3), [[0, 1, 1, 1, 1, 0, 0], [1, 0, 1, 1, 1, 0, 0], [1, 1, 0, 1, 1, 0, 0], [1, 1, 1, 0, 1, 1, 0], [1, 1, 1, 1, 0, 1, 1], [0, 0, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 1, 0]]) min rank example: rank 5 [1 1 1 1 1 0 0] [1 1 1 1 1 0 0] [1 1 1 1 1 0 0] [1 1 1 0 1 1 0] [1 1 1 1 0 1 1] [0 0 0 1 1 0 1] [0 0 0 0 1 1 0] matrix(GF(3), [[1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 0, 1, 1, 0], [1, 1, 1, 1, 0, 1, 1], [0, 0, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 1, 0]]) min rank example: rank 4 [1 1 1 1 1 0 0] [1 1 1 1 1 0 0] [1 1 1 1 1 0 0] [1 1 1 2 1 1 0] [1 1 1 1 1 1 1] [0 0 0 1 1 0 1] [0 0 0 0 1 1 0] matrix(GF(3), [[1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 2, 1, 1, 0], [1, 1, 1, 1, 1, 1, 1], [0, 0, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 1, 0]]) min rank example: rank 3 [1 1 1 1 1 0 0] [1 1 1 1 1 0 0] [1 1 1 1 1 0 0] [1 1 1 0 1 1 0] [1 1 1 1 2 1 1] [0 0 0 1 1 0 1] [0 0 0 0 1 1 1] matrix(GF(3), [[1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 1, 1, 0, 0], [1, 1, 1, 0, 1, 1, 0], [1, 1, 1, 1, 2, 1, 1], [0, 0, 0, 1, 1, 0, 1], [0, 0, 0, 0, 1, 1, 1]])

g.clique_number()

5