# Signed incidence matrices in Sagemath

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:

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.