Let be a graph. A divisor on is an element of the free group generated by the vertices , .

We say that divisors and are *linearly equivalent* and write if is a principal divisor, i.e., if for some function . Note that if and are linearly equivalent, they must have the same degree, since the degree of every principal divisor is 0. Divisors of degree 0 are linearly equivalent if and only if they determine the same element of the Jacobian. If is a divisor of degree 0, we denote by the element of the Jacobian determined by . A divisor is said to be *effective* if for all vertices . We write to mean that is effective. The *linear system* associated to a divisor is the set

i.e., is the set of all effective divisors linearly equivalent to . Note that if , then . We note also that if , then must be empty.

Sage can be used to compute the linear system of any divisor on a graph.

def linear_system(D, Gamma): """ Returns linear system attached to the divisor D. EXAMPLES: sage: Gamma2 = graphs.CubeGraph(2) sage: Gamma1 = Gamma2.subgraph(vertices = ['00', '01'], edges = [('00', '01')]) sage: f = [['00', '01', '10', '11'], ['00', '01', '00', '01']] sage: is_harmonic_graph_morphism(Gamma1, Gamma2, f) True sage: PhiV = matrix_of_graph_morphism_vertices(Gamma1, Gamma2, f); PhiV [1 0 1 0] [0 1 0 1] sage: D = vector([1,0,0,1]) sage: PhiV*D (1, 1) sage: linear_system(PhiV*D, Gamma1) [(2, 0), (1, 1), (0, 2)] sage: linear_system(D, Gamma2) [(0, 2, 0, 0), (0, 0, 2, 0), (1, 0, 0, 1)] sage: [PhiV*x for x in linear_system(D, Gamma2)] [(0, 2), (2, 0), (1, 1)] """ Q = Gamma.laplacian_matrix() CS = Q.column_space() N = len(D.list()) d = sum(D.list()) #print d lin_sys = [] if d < 0: return lin_sys if (d == 0) and (D in CS): lin_sys = [CS(0)] return lin_sys elif (d == 0): return lin_sys S = IntegerModRing(d+1)^N V = QQ^N for v in S: v = V(v) #print D-v,v,D if D-v in CS: lin_sys.append(v) return lin_sys