Monthly Archives: July 2015

Signed incidence matrices in Sagemath

Posted on by

Let \Gamma be a graph with an edge orientation. This means that we are given \Gamma = (V,E), where V is the set of vertices and E a set of ordered pairs of distinct vertices representing the edges, and, for each edge an “orientation”. Simply put, an orientation on $\latex \Gamma$ is a list e_0 of length |E| consisting of \pm 1‘s. If an edge e=(v,w) is associated to a -1 then we think of the edge as going from w to v; otherwise, it goes from v to w.

Let F be a field, let n = |V| and let m=|E|. The incidence matrix may be regarded as a mapping B from the vector space of function on V to the vector space of functions on E:

B: C^0(\Gamma, F)\to C^1(\Gamma, F),

in the notation of Biggs [B]. If we identify C^0(\Gamma, F) with the vector space of column vectors F^n and C^1(\Gamma, F) with the vector space of column vectors F^m then B may be regarded as an m\times n matrix.

At one point Sagemath’s incidence matrix did not respect the given ordering of the vertices and edges, nor did it allow for orientations. (I’m not sure if that still is true.) I wrote the following the following to implement a function to return a signed incidence matrix

def incidence_matrix(Gamma, eo):
    """
    This computes the incidence matrix (whose rows are indexed by edges
    and whose columns are indexed by vertices) of a graph Gamma with 
    edge-orientation vector eo. The ordering of the edges and of the vertices is the same 
    as Sage's vertices and edges methods.

    INPUT:
        Gamma - graph
        eo - a vector of 1's and -1's whose length is the number of edges in Gamma
             (ie, the size of Gamma, M)

    EXAMPLES:
        sage: Gamma = graphs.PaleyGraph(9)
        sage: E = Gamma.edges()
        sage: V = Gamma.vertices()
        sage: eo = [1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1]
        sage: incidence_matrix(Gamma, eo)
        [ 1 -1  1  1  0  0  0  0  0  0  0  0  0  0  0  0  0  0]
        [-1  0  0  0 -1 -1  1  0  0  0  0  0  0  0  0  0  0  0]
        [ 0  1  0  0  1  0  0 -1  1  0  0  0  0  0  0  0  0  0]
        [ 0  0  0  0  0  0  0  1  0  1 -1 -1  0  0  0  0  0  0]
        [ 0  0 -1  0  0  0  0  0  0 -1  0  0  1 -1  0  0  0  0]
        [ 0  0  0  0  0  1  0  0  0  0  1  0 -1  0  1  0  0  0]
        [ 0  0  0  0  0  0 -1  0  0  0  0  0  0  0 -1  1 -1  0]
        [ 0  0  0  0  0  0  0  0 -1  0  0  1  0  0  0 -1  0 -1]
        [ 0  0  0 -1  0  0  0  0  0  0  0  0  0  1  0  0  1  1]
        sage: B = incidence_matrix(Gamma, eo) 
        sage: B*B.transpose() == Gamma.laplacian_matrix()
        True

    """
    E = Gamma.edges()
    V = Gamma.vertices()
    IG = [[incidence_value(Gamma, v, e, eo) for v in V] for e in E]
    #print IG
    return matrix(QQ, IG).transpose()

This uses the function below

def incidence_value(Gamma, v, e, eo):
    """
    This computes the incidence value of a vertex and edge of 
    a graph Gamma with edge-orientation vector eo. 

    INPUT:
        Gamma - graph
        v  - vertex of Gamma
        e  - edge of Gamma  
        eo - a vector of 1's and -1's whose length is the number of edges in Gamma
 
    EXAMPLES:
        sage: Gamma = graphs.PaleyGraph(9)
        sage: E = Gamma.edges()
        sage: V = Gamma.vertices()
        sage: eo = [1]*len(E)
        sage: incidence_value(Gamma, V[2], E[3], eo)
        0
        sage: incidence_value(Gamma, V[8], E[3], eo)
        -1

    """
    E = Gamma.edges()
    if v in e:
        if v == e[0]:
            k = E.index(e)
            return eo[k]
        elif v == e[1]:
            k = E.index(e)
            return -eo[k]
        else:
            return 0
    return 0

For example, consider the Paley graph on 9 vertices:

graph-sage-paley9

The orientation [1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1, 1, -1, 1, 1, -1, -1] attached to the edges [(0, 1),
(0, 2), (0, a + 1), (0, 2*a + 2), (1, 2), (1, a + 2), (1, 2*a), (2, a), (2, 2*a + 1), (a, a + 1), (a, a + 2), (a, 2*a + 1), (a + 1, a + 2), (a + 1, 2*a + 2), (a + 2, 2*a), (2*a, 2*a + 1), (2*a, 2*a + 2), (2*a + 1, 2*a + 2)] gives rise to the incidence matrix

\left(\begin{array}{rrrrrrrrrrrrrrrrrr} 1 & -1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & -1 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & -1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & -1 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & -1 & 0 & -1 \\ 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \end{array}\right)

References:
[B] Norman Biggs, “Algebraic potential theory on graphs”, BLMS, 1997.

I think Caroline Melles for help debugging the code above.