Linear Spaces of a Graph

How to contact me.
This material comes from some notes for a University of Waterloo course taught by Herb Shank (c. 1975). I have an export of a maple worksheet, showing these operators: http://www.math.fau.edu/Locke/courses/GraphTheory/LinSpGen.htm.
Back to the Graph Theory Index.
Let G be a finite, connected, directed graph. If the vertex set of G is V={v1,v2,...,vm } and the edge set of G is E={e1,e2,...,en }, then it is useful to consider an oriented edge to be an ordered pair of vertices (say tip first, then tail). So: ei=(vs,vr ) would indicate that edge ei is directed from vr to vs.

If F is a field, and S is a finite set, let <S>F denote the set of all linear combinations of elements of S with coefficients in F. If addition and scalar multiplication are "coordinatewise", then <S>F is a vector space over F having S as one of its bases. Where unambiguous, the subscript F may be omitted. Despite this notational convention, <E>F is important enough to have a special name, CF(G). When it is convenient and no misinterpretation is possible, we will write C for CF(G). CF(G) is the vector space of all linear combinations of edges of G, with coefficients in F. Similarly, DF(G)=<V>F.

Define a linear transformation ð:CF(G) -> <V>F by ð:ei=vs-vr, for ei=(vs,vr ), and extending ð to all of CF(G) by linearity. The space ZF(G) of cycles is the kernel of ð. That is, z is an element of ZF(G) iff ðz=0. As a special case, note that any loop e is in ZF(G), since ðe=0. Note also: there are two definitions of cycle found in graph theory texts and literature. The other definition corresponds to the non-zero elements of ZF(G) with minimal support and with coefficients of ±1 on this support. On this page, these are called polygons.

Another description of ð is in terms of the vertex-edge incidence matrix of G. For G as above, this will be an m by n matrix M=(mi,j ). If ei=(vs,vr ), then ms,i=+1, mr,i=-1 and mk,i=0 if k is neither s nor r. This incidence matrix is the matrix representing ð with respect to the basis E of CF(G) and the basis V of <V>F.

We could have used incidence matrices to define graphs. A directed, loopless graph may be interpreted to be an m by n matrix M, with entries in {-1,0,+1}, such that every column has exactly one entry which is +1 and exactly one entry which is -1. The rows of M are the vertices of the graph, and the columns of M are the edges of the graph. We would say that M is connected if the rank of M is m-1. (The rank does not depend on F.) The reader who is familiar with the usual definition of graph should verify that this definition of connected is equivalent to the usual definition and that this definition of rank is equivalent to the usual definition.
Example 1. Suppose that the vertices of G are {v1,v2,v3,v4 } and that the edges of G are e1=(v1,v4 ), e2=(v1,v2 ), e3=(v2,v3 ), e4=(v4,v3 ) and e5=(v4,v2 ). Then, M(G) is 
                 +1   +1    0    0    0 
                  0   -1   +1    0   -1 
                  0    0   -1   -1    0 
                 -1    0    0   +1   +1
Now CF(G) consists of all a1e1+a2e2+a3e3+a4e4+a5e5, with ai in F and <V>F consists of all b1v1+b2v2+b3v3+b4v4, with bi in F.

ð(3e1-7e2+e5 ) = 3ðe1 -7ðe2 +ðe5 = 3 (v1-v4 )-7(v1-v2 )+(v4-v2 ) = -4v1+6v2-2v4; therefore, 3e1-7e2+e5 is a cycle only if char(F)=2. (And then, of course, 3e1-7e2+e5=e1+e2+e5.)

However, ð(7e1-7e2-4e3+4e4+3e5 )=0, so that this member CF(G) is a cycle (i.e., belongs to ZF(G)) no matter what F is. To be continued.
Exercise. Let G be a finite, loopless, directed graph and let M be the incidence matrix of G. Show that the rows of M are not linearly independent.
Exercise. Let G be a finite, loopless, directed graph and let M be the incidence matrix of G. Let W be any square submatrix of M. Show that det(W) is in {-1,0,+1}.
By the support of a vector of C we mean the set of edges of G having non-zero coefficient in the vector. It is obvious that a polygon supports a cycle whose non-zero coeffiecients are all ±1. In the above example, the polygon having edges {e1,e2,e5 } supports the cycles e1-e2+e5 and -e1+e2-e5. Note that a coefficient of -1 has the geometric connotation of taking an edge in the opposite direction to the one given (by the orientation).

A tree or spanning tree or maximal tree T is a maximal set of edges of G such that <T>F intersect ZF = {0}. Althought this definition involves F, whether or not a set of edges is a tree does not depend on the choice of F, and a tree by this definition is the usual object. The reader might prove this by induction.
Exercise. List all of the spanning trees for the graph given in Example 1. (There are 8 of them.)

Exercise. Let e be an edge of G in the complement T' of T. By definition, <T> intersect ZF(G) = {0}.

(a) Using the definition of T, show that the dimension of <T union {e}> intersect ZF(G) is at least one.

(b) Suppose that x,y are nonzero elements of <T union {e}> intersect ZF(G). Show that the coefficients of e in x and y cannot be 0.

(c) Suppose that x,y are nonzero elements of <T union {e}> intersect ZF(G). Show that x is a multiple of y, thereby proving that <T union {e}> intersect ZF(G) has dimension 1.
If e1,...,ek are edges of G in the complement T' of T, <T union {ei }> intersect ZF(G) is 1-dimensional; denote by ATei the unique member of this space for which the coefficient of ei is +1. T union {ei } contains a unique polygon which supports ATei, and the non-zero coefficients of ATei are all ±1. Accordingly, ATei does not depend on the choice of F. If e is an element of T, we consider ATe to be 0.

For convenience, T union {ei } will usually be written T union ei .
Example 1 continued. Let T={e1,e3,e4 }. Then ATe2=-e1+e2+e3-e4 and ATe5=e3-e4+e5.
Exercise. Using the graph of Example 1, list ATei, for each edge ei and each tree T.
Exercise. Using the graph of Example 1, calculate the sum of ATei, for each edge ei, where the sum is taken over all trees of the graph.
Theorem 1. The set of all ATei, where ei is not an element of T, is a basis for ZF. Furthermore, if z is an element of ZF and z=a1e1+...+an-m+1en-m+1+bn-men-m+...bnen, where e1,...,en-m+1 are not in T and en-m,...,en are in T, then z=a1ATe1+...+an-m+1ATen-m+1.

Proof. That the nonzero ATei are linearly independent is clear. That they span ZF comes from z-a1ATe1+...+an-m+1ATen-m+1 is in ZF; expressed as a linear combination of edges, the coefficient of each ei which is not is T is ai-ai=0. Hence, z-a1ATe1+...+an-m+1ATen-m+1 is in <T> and thus z-a1ATe1+...+an-m+1ATen-m+1 is in <T> intersect ZF = {0}.

Comment. Suppose that G is a connected graph embedded in the plane (no crossing edges). Let φ denote the number of faces of G, ν the number of vertices, and ε the number of edges. Then, any φ-1 faces of G comprise a basis for the cycle space of G. The basis described by Theorem 1 has ε-ν+1 elements. Hence, ε-ν+1 = φ-1. This is more commonly written ν-ε+φ = 2, and known as Euler's theorem. (If you don't like cycle spaces, prove it by induction.) Euler stated the result in 1750, and Cauchy gave a graph theoretic proof in 1813. Lhuilier 1811, gave the following generalizations. If a connected graph H is embedded on an orientable surface of genus g (g handles or g holes), with every face contractible to a disc, then ν(H)-ε(H)+φ(H) = 2-2g. Similarly, if a connected graph H is embedded on a non-orientable surface with c crosscaps, with every face contractible to a disc, then ν(H)-ε(H)+φ(H) = 2-c. Some readers might like to examine the book, Proofs and Refutations, by Imre Lakatos.

If u=a1e1+...+anen is in C and v=b1e1+...+bnen is in C, the inner product (u,v) is a1b1+...+anbn. It is induced by bi-linearity and (ei,ej )=1, if i=j, and (ei,ej )=0, if i is not equal to j.

For the field of complex numbers there is an alternate way to define inner product. In terms of u and v above, one could define (u,v)=a1b1*+...+anbn*, where b* represents the complex conjugate of b.

However, we will ignore this form in what follows.
Define the space BF of cocycles by:

b is in BF iff (b,z)=0, for all z in ZF.

In other notation, one might write BF=(ZF )* . (As of the year 2003, HTML has a "perp" symbol -- but it doesn't appear propoerly in every browser, so I've used a *.) What are called cycles here are called circuits by some authors. Cocyles are sometimes called bonds. The letters Z and B presumably come from the German names. Dènes König called these Zyklenformen and Büschelformen.
Exercise. Let e be an edge of T.

(a) Show that for any non-zero element x of <T'>, there is an edge ei in T' such that (ATei,x) is not 0.

(b) Suppose that x,y are nonzero elements of <T' union {e}> intersect BF(G). Show that the coefficients of e in x and y cannot be 0.

(c) Suppose that x,y are nonzero elements of <T' union {e}> intersect BF(G). Show that x is a multiple of y, thereby proving that <T'> intersect BF(G) has dimension 1.
If T is a tree, and e is an edge in T, <{e} union T'> intersect BF(G) is 1-dimensional: consider a member of B whose support is in {e} union T', say, b=ae + a1e1+...+am-n+1em-n+1, where the e1,...,em-n+1 are edges not in the tree. For each edge ej not in T, 

0 = (b,ATej ) 
  = (ae + a1e1+...+am-n+1em-n+1,ATej ) 
  = (ae,ATej ) + (a1e1,ATej ) +...+(am-n+1em-n+1,ATej,ATej ) 
  = a(e,ATej ) + a1(e1,ATej ) +...+am-n+1(em-n+1,ATej,ATej ) 
  = a(e,ATej ) + aj.
Therefore, aj = - a(e,ATej ).

Define BTe to be the unique cocyle having a=1. That is BTe=e-(e,ATe1 )e1 - ... - (e,ATem-n+1 )em-n+1.

BTe is easy to obtain from G. Deleting e from T partitions V into two cells, X and Y, each of which remains connected by T-e. Without loss of generality, the tip of e belongs to X. The support of BTe consists of all edges having one end in X and the other end in Y. Those edges having tips in X have coefficient +1, those having tail in X have coefficient -1. Referring again to Example 1, suppose that T={e1,e3,e5 }. Deleting e5 from T partitions V into {v1,v4 } and {v2,v3 }, and e5 is directed from {v2,v3 } to {v1,v4 }. The edges of T' joining these sets are e2 and e4, and they are each directed from {v2,v3 } to {v1,v4 }. Thus, BTe5=e2+e4+e5. Similarly, BTe1=e1+e2 and BTe3=e3+e4. If e is not in T, we consider BTe to be 0.
Exercise. For the graph of Example 1, list BTei, for each edge ei and each tree T. Then list BT1ei + ... + BTkei, for each edge ei, where the sum is over all trees of the graph.
Another description of the space BF is as the image of <V>F under the linear transformation þ:<V>F   -->   <C>F whose matrix representation with respect to the bases V and E is the transpose of M(G). In the graph of Example 1, þv1 = e1+e2, þv2 = -e2+e3-e5, þv3 = -e3-e4 and þv4 = -e1+e4+e5.
The proof of the following theorem is similar to the proof of Theorem 1.

Theorem 2. If T is a tree and e1,...,ek are its edges, then BTe1,...,BTek is a basis for B.
Exercise. State and prove a representation theorem which expresses each cocycle as a linear combination of elements of the basis described in Theorem 2. Prove that the elements described in Theorem 2 do comprise a basis for the cocycle space.
Summarizing, a tree T of G determines, in a standard way, a basis for the space ZF of cycles and a basis for the space BF of cocycles. Because all of the coefficients for each member of these bases are 0 or ±1, they "make sense" for every field F. While ZF and BF depend on F, they have the same sets of standard bases as long as 0, 1 and -1 are interpreted as belonging to F.

If F is the integers modulo 2, each member S=ei1+...+eip of CF corresponds in a natural way with a set of edges, via {ei1,...,eip } corresponds to ei1+...+eip, and addition of vectors amounts to taking the symmetric difference of sets. Symmetric difference of the sets S1 and S2 is (S1 union S2 ) - (S1 intersect S2 ). The inner product of vectors is the parity of the cardinality of the sets corresponding to the vectors. Accordingly, using cycle to mean the set corresponding to a vector of Z, we say: a cycle is a symmetric difference of poylgons; and a set of edges is a cocyle iff it has even cardinality intersection with every cycle.
Exercise. For the graph of Example 1, list all elements of Z2(G) and all elements of B2(G). Then list all elements of Z2(G) intersect B2(G).
In K4-e, the 4-gon is both a cycle and a cocyle; in K3, only the empty set is a cycle and a cocyle. If G is obtained from the wheel with 4 spokes by removing a rim edge, then Z2(G) intersect B2(G)={0}.

When G and F are such that ZF(G) intersect BF(G)={0}, we say that ZF(G) and BF(G) are disjoint. Then CF(G) is the direct sum of ZF(G) and BF(G), and every member of CF(G) can be written uniquely as the direct sum of a cycle and a cocyle. If c=z+b, with z in ZF(G) and b in BF(G), we say that z is the cycle part of c and b is the cocyle part of c. We also say that z is the projection of c onto its cycle part and that b is the projection of c onto its cocyle part.

To obtain expressions for these projections, it is convenient to re-use "AT" and "BT" as names for linear transformations. If T is tree of G, define AT : C -> C and BT : C -> C by:

AT(e)=ATe if e is not in T,
AT(e)=0 if e is in T,
BT(e)=0 if e is not in T, and
BT(e)=BTe if e is in T.

Recall that if f : C -> C is a linear transformation there is a unique f* : C -> C that is linear with (fc1,c2 )=(c2,f*c2 ). The transformation f* is called the adjoint of f. If we treat f as a matrix and c1, c2 as vectors:

(fc1,c2 ) = (fc1 )tc2 = (c1tf t)c2 = c1t(f tc2 ) = (c1,f tc2 ),

where f t is the usual transpose of f. If F is the complex numbers, we might have used conjugate transpose instead of transpose, except we have decided to use the same inner product form for all fields. We have established the existence of a linear transformation of the required type. To establish uniqueness, simply note: that if (fc1,c2 )=(c1,gc2 )=(c1,hc2 ), then (c1,(g-h)c2 )=0. Since this is to be true for every c1 and c2, g-h must send every c2 to 0. Thus g-h=0 and g=h.

We now proceed to prove a fact about a certain linear transfomation that is defined in terms of spanning trees.

Let R : C -> C be linear with Rei=riei, and define wT to be the product of the factors ri, where ei is not in T. Finally, define H : C -> C by: H = wT1AT1+...+wTkATk, where the sum is over all spanning trees, Ti. We will show that RH is self-adjoint, and then use this information to investigate a certain problem that has its origins in electrical network theory and to investigate under what circumstances the spaces Z and B are disjoint.
Exercise. For the graph of Example 1, display the matrices representing H, R and RH, with respect to the usual bases.
The proof that RH is self-adjoint follows a sequence of easy lemmas.

Lemma 1. Suppose that T is a spanning tree with ei not in T, ej in T, and (ATei,ej ) not 0. Then T1=(T-e_j) union {ei } is a spanning tree and (RwTATei,ej ) = (RwT1AT1ej,ei ).

Proof. To see that T1 is a spanning tree, note that the only polygon in T union {ei } contains ej. The equation (ATei,ej ) = (AT1ej,ei ) just says that ei and ej have the same orientation or opposite orientation in this polygon; if we multiply both sides of this equation by rjwT=riwT1, we have

rjwT(ATei,ej ) = riwT1(AT1ej,ei ),
(wTATei,rj*ej ) = (wT1AT1ej,riei ),
(wTATei,R*ej ) = (wT1AT1ej,R*ei ),
(RwTATei,ej ) = (RwT1AT1ej,ei ).

Here, we have used r* mainly to assist with the book-keeping. We might point out, however, that the proof given would also hold if F is the complex numbers (or a subfield thereof) and inner product is of the conjugate-transpose variety. For this latter case, we set r* to be the complex conjugate of r, but if F is finite, or a subfield of the reals, r*=r.
Lemma 2. (R sumTwTATei,ej ) = (R sumT1wT1AT1ej,ei ), where the sum extends over all trees T satisfying the conditions of Lemma 1, and T1 = (T-ej ) union {ei } as in Lemma 1.
Theorem 3ß. RH = (RH)*.

Proof. We show that (RHei,ej ) = (RHej,ei ). For i=j, there is no problem. For i different from j, note that unless T is one of the trees counted in Lemma 2, its contribution in the sum is 0.


ßNote: The proof of Theorem 3 assumes that (u,v) = (v,u), which fails in the case that F is the field of complex numbers using (u,v) = u1v1*+...+umvm*, where * denotes complex conjugate. The proof with (u,v) = u1v1+...+umvm, and F complex is valid -- but then adjoint means transpose and not conjugate transpose.
The discussion continues in: Resistive Networks and When are Z and B disjoint?
Back to the Graph Theory Index.
Department of Mathematical Sciences
Florida Atlantic University
777 Glades Road
Boca Raton, Florida 33431-0991
USA

Office: Room 286, Science & Engineering
Phone: (561) 297-3350
Fax: (561) 297-2436
URL: http://www.math.fau.edu/locke/linearsp.htm

Last modified November 3, 2000, by S.C. Locke.