Let 
Let F be a field, let 
in the notation of Biggs [B]. If we identify 
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.
, ![{\mathbb{Z}}[V]](https://s0.wp.com/latex.php?latex=%7B%5Cmathbb%7BZ%7D%7D%5BV%5D&bg=ffffff&fg=323232&s=0&c=20201002)
.
and 
are linearly equivalent and write 
if 
is a principal divisor, i.e., if 
for some function 
. Note that if ![[D]](https://s0.wp.com/latex.php?latex=%5BD%5D&bg=ffffff&fg=323232&s=0&c=20201002)
the element of the Jacobian determined by 
for all vertices 
. We write 
to mean that 
is the set of all effective divisors linearly equivalent to 
, then 
. We note also that if 
, then 
between graphs 
and 
can be uniquely defined by specifying where the vertices of 
go. If 
and 
then this is a list of length 
consisting of elements taken from the 
vertices in 
.
and let 
denote the “cube graph” (actually the unit square) in 
.
by
to be a subgraph of 
is called harmonic if for all vertices 
, the quantity
in 
.
according to any proposed reference matrix of the general type described in Section 7, whatever the finite field in which the operations are effected. Such machines would enable us to dispense entirely with tables of any sort, and checks could be determined with great speed. But before checking machines could be seriously planned, the following problem — which is one, incidentally, of considerable interest from the standpoint of pure number theory — would require solution:
with 
-element sequence 
, a reference matrix 
is the greatest possible. Corresponding to any 
being elements of any given finite algebraic field 
with 
— determinants of first order (
) being single elements of the matrix.
, 
is an 
element operand
-element check based upon the matrix 
is:
, 
.
, 
be a 
, \dots, $f_{s}$, $s\leq n$. Let 
. If, in the transmittal of the sequence 
-in-
chance of escaping disclosure, according as $v$ is, or is not, less than 
. In this statement, 
. The presence of error is evidently certain to be disclosed.
. There is no loss of generality of we assume [This assumption implies 
. – wdj] the $v$ errors are 
, 
, affecting 
. The errors cannot escape disclosure. For, to do so, they would have to satisfy the system of homogeneous linear equations:
contains no vanishing determinant of any order, and which, therefore admits no solution other than 
(
).
errors fall among the 
and 
errors fall among the 
. Without loss in generality, we may assume that the errors are 
, affecting 
, and 
, 
, affecting 
, 
.
. Writing 
, where 
denotes a non-negative integer which may or may not be zero, we have 
. Hence 
of the 
denote a set of 
. But the matrix of coefficients in this system contains no vanishing determinant, so that the only solution would be 
).
. Then 
, where $h$ denotes a positive integer. Assuming that the presence of error is to escape detection, we see, therefore, that the 
) a system of 
equations involving only the errors 
, (
) a system of 
equations involving all 
— as polynomial functions of the 
errors are determined as rational functions of the remaining 
errors determine the other $t$ errors.
of elements of any given finite algebraic field. Operations in the field 
. Suppose that we wish, in a certain message, to transmit the numerical sequence 
) is obtained by the simple tabulation which follows. We use Table 4, noting that in each of the nine rows, the one-hundred columns are shown in four sections, there being twenty-five columns in each section.
, and a one-column tabulation would have sufficed. If a two-element check had been desired, we should have taken 
and a two-column tabulation would have sufficed. Etc.
elements, the procedure, to determine check of Type A, is obvious. A 
, with 
, is as stated:
. The manner of its evaluation, by means of Table 4, is clear.
.
– that is, upon
. The tabulation is as follows:
. The tabulation is as follows:
, on the sequence 
of 
, is given by
, will be called a check of “type 
th row shows the products of all non-zero elements of 
($i=1,2,\dots, 9$), where the 
Yet Another Mathblog 
You must be logged in to post a comment.