Let be a graph with an edge orientation. This means that we are given , 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 of length |E| consisting of ‘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 and let . 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:

,

in the notation of Biggs [B]. If we identify with the vector space of column vectors and with the vector space of column vectors then B may be regarded as an 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:

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

References:

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

I think Caroline Melles for help debugging the code above.

You must be logged in to post a comment.