ARS MATHEMATICA CONTEMPORANEA Also available at http://amc-journal.eu ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.) ARS MATHEMATICA CONTEMPORANEA 9 (2015) 125-144 Matrices and their Kirchhoff graphs Joseph D. Fehribach * Mathematical Sciences, Worcester Polytechnic Institute, Worcester, MA 01609-2247, USA Received 11 October 2012, accepted 21 July 2014, published online 28 September 2014 The fundamental relationship between matrices over the rational numbers and a newly defined type of graph, a Kirchhoff graph, is established. For a given matrix, a Kirchhoff graph represents the orthogonal complementarity of the null and row spaces of that matrix. A number of basic results are proven, and then a relatively complicated Kirchhoff graph is constructed for a matrix that is the transpose of the stoichiometric matrix for a reaction network for the production of sodium hydroxide from salt. A Kirchhoff graph for a reaction network is a circuit diagram for that reaction network. Finally it is conjectured that there is at least one Kirchhoff graph for any matrix with rational elements, and a process for constructing an incidence matrix for a Kirchhoff graph from a given matrix is discussed. Keywords: Kirchhoff graphs, fundamental theorem of linear algebra, reaction networks. Math. Subj. Class.: 05C20, 05C50, 05C90 1 Introduction To understand the relationship between matrices and a newly-defined type of graph, a Kirchhoff or fundamental graph, consider the simple directed graph in Figure 1 and the incidence matrix for this digraph: In this matrix element aj = 1 if the j-th edge Sj exits the ¿-th vertex vaj = — 1 if Sj enters vand aj =0 if Sj is not incident to vThis use of 1 and —1 is the opposite of what many authors use in graph theory, but it matches the forward direction for steps *The support of the National Science Foundation under grant DMS-0707692 is gratefully acknowledged. Website: http://www.wpi.edu/\textasciitildebach E-mail address: bach@math.wpi.edu (Joseph D. Fehribach) Abstract 1 0 1 1 1 0 011 (1.1) ©® This work is licensed under http://creativecommons.org/licenses/by/3.0/ 126 Ars Math. Contemp. 9 (2015) 115-124 in chemical reaction networks and hence is preferred here. The edges of the graph in Figure 1 and indeed of all the graphs considered here are vectors (have specified length and direction). Notice that the rows of this incidence matrix are linearly dependent, and that the vector [1,1, -1]T is in its null space. But this null-space vector also represents the cycle1 in this digraph since (1)S1 + (1)S2 + (-1)s3 = 0 is the cycle. Also the cuts for each vertex2 of this graph are (as always) represented by the rows of the incidence matrix. So the graph in Figure 1 is a representation of the orthogonality of the null and row spaces of this incidence matrix, and this orthogonality is essentially v 2 v v s 3 3 Figure 1: A simple example to illustrate the concept of Kirchhoff graph. the classic result that the cycle space and the cut space of a (standard) graph are orthogonal complements (cf. e.g. Diestel(1997) [5, p. 22] or Bollobas(1998) [1, p. 53]). The relationship between the graph in Figure 1 and its incidence matrix easily extends to multi-digraphs where the edges are again vectors. As a simple example of this extension, consider the multi-digraph in Figure 2 and its incidence matrix3: to 0 1 2 0 1 to 1 0 -2 1 0 0 -1 -1 = 0 -1 -1 0 1-1 0 0 0 0 0 0 1-1 0 0 0 Here "1 - 1" means that the same vector enters and exits a given vertex. Again the graph in Figure 2 represents the orthogonality of the row and null spaces of this incidence matrix since the cycle is (1)si + (2)S2 + (-2)s3 = 0 and the vertex cuts "lie" in this row space. What is really interesting is that the relationship can be extended even further: For any matrix with rational elements, it would seem possible to construct a multi-digraph whose 1For the current discussion, a cycle in a graph is a closed walk, i.e. an alternating sequence of vertices and edges incident to adjacent vertices {v i, si, v2, ...vn, sn, v1} beginning and ending with the same vertex, with no assumption that any vertices or edges are distinct. 2A vertex cut in a graph is the set of edges incident to the vertex (the minimum set of edges that would need to be removed to isolate the vertex from the rest of the graph). 3 The term incidence matrix as used here is a generalization of the standard definition. Here each column corresponds to an edge vector, even though that vector may appear multiple times in the graph J. D. Fehribach: Matrices and their Kirchhoff graphs 127 Figure 2: A multi-digraph that is a somewhat more complicated Kirchhoff graph. The double hash marks crossing s1 indicate that two copies of this edge vector connect the first two vertices. cycle space corresponds to the null space of the matrix and whose cut space lies in the row space of the matrix. Indeed the concept of a Kirchhoff graph is a sort of inverse of the relationship between the cycle space and the cut space for the standard graph in that one starts with an arbitrary matrix and then attempts to construct the graph. Thus each Kirchhoff graph for a matrix is a graph-theoretic representation of the fundamental theorem of linear algebra which states that the null space and the row space of any matrix are orthogonal complements.4 Because of the relationship between Kirchhoff graphs for a given matrix and the fundamental spaces for that matrix, a Kirchhoff graph can also be termed a fundamental graph. Also from the simple examples above, one sees that the exact length and orientation of the edge vectors are not important. The key issue, rather, is the multiplicities of any given vector in a cycle and the multiplicities of that vector between given vertices. The graph in Figure 1 is a Kirchhoff graph for any matrix with the same row space and null space as the matrix in (1.1), and the graph in Figure 2 is a Kirchhoff graph for any matrix with the same row space and null space as the matrix in (1.2). The concept of a Kirchhoff graph comes out of chemical reaction network theory. As the name implies, when based on a reaction network, a Kirchhoff graph satisfies both the Kirchhoff current law and the Kirchhoff potential law, and is therefore a circuit diagram for that reaction network. Their role in this context was discussed by Fehribach(2009) [9], and also by Fishtik, Datta et al. [11, 12, 13, 10, 14, 25] and in some of their references. In the latter works, Kirchhoff graphs are referred to as reaction route graphs. The concept of a Kirchhoff graph thus connects the fundamental theorem of linear algebra with the fundamental conservation principle in the Kirchhoff laws. There is also the important and distinct concept of a Kirchhoff or Laplacian matrix and the well-known Kirchhoff theorem which relates the eigenvalues of the Kirchhoff matrix for a graph to the number of spanning trees of that graph. A variety of other graphs have been used to discuss reaction networks. For a general review, particularly of early uses, see Fehribach(2007) [8]. An important recent sequence of work on graphs and reaction networks began with the work of Horn(1973) [15, 16], followed by that of Perelson & Oster(1974) [22], Clarke(1980) [3], Schlosser & Fein-berg(1994) [23], and the work of Craciun & Feinberg(2006) [4]. The graphs studied in 4Not all authors/texts use this terminology, but it has become more widely used in recent years; cf. Strang(2003) [24]. 128 Ars Math. Contemp. 9 (2015) 115-124 these articles are termed species-complex-linkage (SCL) graphs and species-complex (SC) graphs, and are useful in studying reaction kinetics and the stability of equilibria, but they are not connected to the fundamental spaces of any matrix, nor do they give a representation of the fundamental theorem of linear algebra. Also in general the above articles specifically discuss graphs; see their references for other related articles that discuss the reaction networks themselves. Throughout this work, we consider matrices with rational elements, but then consider basis vectors for the null and row spaces with integer elements. This is possible since for any matrix over the rationals, one can multiply each element by the least common multiple of all the denominators to obtain a matrix with integral elements, but the same null and row space as the original rational matrix. Also it is important to realize that the correspondences between the null and row spaces on the one hand and the cycle and cut spaces on the other are not equivalences. The null and row spaces are vector spaces over the rationals, while the cycle and cut spaces are modules over the integers (it is easy to interpret integral multiples of a cycle, but not fractional multiples). For a Kirchhoff graph G of a matrix A, there are natural embeddings of the cycle space of G into the null space of A, and of the cut space of G into the row space of A. The next section contains the formal definition of a Kirchhoff graph and several basic results; these make rigorous the ideas introduced in the examples above. Since the impetus for the concept of Kirchhoff graph comes from the theory of chemical reaction networks, Section 3 presents the development of a Kirchhoff graph for such a network. The final two sections discuss the construction of Kirchhoff graphs, as well as open problems and future work. 2 Kirchhoff Graphs—Definition and Basic Results Consider an m x n matrix over the rationals: A G Mm,n(Q). The main question to be considered here is "Which graph or graphs best represent this matrix in terms of its fundamental spaces and the fundamental theorem of linear algebra?" That is, which graph(s) best reflect the duality that Row(A) and Null(A) are orthogonal complements: Row(A) ± Null(A), RowT(A) © Null(A) = Qn where the superscript T indicates the transpose of all vectors in the space. The proposed answer to this question is the Kirchhoff graph: Definition 2.1. For a given matrix A G Mm,n(Q), a geometric cyclic multi-digraph G is a Kirchhoff graph for A if and only if the following two conditions are satisfied: 1. For uj G Z, u = [u^u2, ...,un]T G Null(A) if and only if there is a cycle in G where, for each j, 1 < j < n, the jth directed edge appears with multiplicity |uj |. The sign of uj gives the relative direction that the jth edge is crossed. 2. For a given vertex of G, if the jth edge exits with multiplicity vj G Z, then v = [v1, v2,..., vn] G Row(A). When vj is negative, the edge enters the vertex (exits in the negative sense). J. D. Fehribach: Matrices and their Kirchhoff graphs 129 Remark 2.2. 1. While in general A e Mm,n(Q), there is no loss of generality in assuming that A e Mm,n(Z) since one can multiply A by the least common multiple of all the denominators of the elements of A without affecting the null and row spaces. Similarly one can take the elements of the basis vectors for the null space or row space to be integers. 2. According to this definition, two matrices with the same null and row spaces have the same Kirchhoff graph(s). 3. For the present discussion, a digraph G is cyclic if and only if Sj is an edge vector of G implies Sj is an edge vector of some cycle C c G. The trivial graph with one vertex and no edges is then vacuously cyclic. 4. These graphs are "geometric" in that edges are vectors. Two edges with the same length and direction are the same vector and are therefore identified. For discussions of the more-general topic of geometric graphs, see Pach, et al. [19, 20, 21]. 5. The second condition in Definition 2.1 assures that all of the vertex cuts lie in the row space of the matrix, but not all dimensions of the row space necessarily need to be represented explicitly as vertex cuts. As is discussed below, if A is nonsingular, the simplest Kirchhoff graph is a single vertex with no edges. 6. Making the outward direction positive matches the tradition in analysis and is what is needed for discussing reaction networks; unfortunately it is the opposite what is generally used in graph theory. 7. In the extreme cases where either Null(A) = {0} or Row(A) = {0}, the Kirchhoff graph can be defined as a single vertex with no edges. When Null(A) = {0}, this graph results from the only allowed cycle being a null cycle where all edge vectors appear an even number of times and cancel as one moves around the cycle; the simplest null cycle is a single vertex. When Row(A) = {0}, then the second condition in the definition requires that all edges vectors begin and end at the same vertex and therefore have length zero. 8. As will be discussed in Section 3 below, if the matrix A is the transpose of the stoichiometric matrix for a reaction network, the first condition in Definition 2.1 is a form of the Kirchhoff potential (or voltage) law, while the second condition is a form of the Kirchhoff current law. The rest of this section is devoted to some basic properties and results associated with Kirchhoff graphs. 2.1 Some Basic Results Proposition 2.3. Suppose that A e Mm,n(Q) and Null(A) = Span{[ai, a2,..., an]T}, aj e Z, with at least one aj = 0. Then dim(Null(A)) = 1 and dim(Row(A)) = n — 1, and a Kirchhoff graph for A can be given as a single cycle with |a11 + |a2| + ... + |an| vertices. Proof. Suppose first that Null(A) = Span{[a1, a2,..., an]T} with aj = 0 Vj. Then Row(A) = Span{[—a2, a1,0,..., 0], [0, —a3,a2,..., 0],..., [0,..., —an,an-1]}, and these n — 1 vectors give n — 1 cut (vertex balance) conditions for vertices where differing edge 130 Ars Math. Contemp. 9 (2015) 115-124 vectors meet. The final condition is a linear combination these row-space basis vectors: [-an, 0,0,..., aij. Unless |aj | = 1 Vj, there are also null vertices where the same edges enter and exit. If aj = 0 for some j, then the unit vector with 1 as the j-th element and all other elements being 0 lies in Row(A). The edge Sj does not appear in the graph, and the vertex balance conditions are formed as before leaving out this unit vector. (Recall that the definition of a Kirchhoff graph does not require that all the basis vectors for the row space be represented in a graph.) □ Example 2.4. A simple example is helpful in understanding the above proposition: Suppose that Null (A) = Span{[0,1, -3, 2]T}. Then Row(A) = Span{[1,0,0,0], [0, 3,1,0], [0,0, 2, 3]} and [0, -2,0,1] is the additional vector from Row(A) needed for the vertex where the s4 edges join s2. Figure 3 shows a one-cycle Kirchhoff graph for this example. Figure 3: A simple cycle to illustrate Proposition 2.3. The hash marks give the multiplicity of each edge indicating how the cut space of the graph corresponds to Row(A). Remark 2.5. If fewer than three of the elements aj are nonzero, then the Kirchhoff graph is degenerate, as when the null space or row space is trivial. When only one aj is nonzero, there is one vertex and an edge of length zero (the edge must begin and end at the same vertex); when two aj are nonzero, there are two vertices and two overlapping edges, as in the degenerate case shown in Figure 5 below. The previous proposition suggests that matrices can have multiple Kirchhoff graphs since the edges can appear in any order in the cycle. For example, one could split the two s4 vectors so that the order moving around the cycle is s2, s4, -3s3, and finally the second s4. In fact, a given matrix may have two or more Kirchhoff graphs which differ even more than just the order that edges appear in a cycle. Proposition 2.6. A given matrix A G Mm,n(Q) may have multiple, distinct Kirchhoff graphs, i.e., a matrix does not necessarily have a unique Kirchhoff graph. Proof. Consider the matrix " 10 11 A 1101 (2.1) J. D. Fehribach: Matrices and their Kirchhoff graphs 131 Here Row(A) is just the span of the two rows of A, while Null(A) = Span • 1 ■ 0 " 1 1 -1 1 0 -1 (2.2) At least5 two Kirchhoff graphs exist for this matrix (and any other matrix with the same row and null spaces), as seen in Figure 4. □ Figure 4: Two Kirchhoff graphs for A in (2.1). Again the hash marks in Graph 2 indicate that two copies of that edge are needed in that position. Now suppose that dim(Row(A)) = 1 and thus dim(Null(A)) = n - 1. This is again a degenerate case, and a Kirchhoff graph in this case again depends on what one is willing to accept as a cycle. For our purposes here, we again allow for a degenerate cycle where the edge vectors double back on themselves. Proposition 2.7. Suppose that A e Mm,n(Q) and that dim(Row(A)) = 1. Then dim(Null(A)) = n — 1, and a Kirchhoff graph for A can be given as a degenerate one-dimensional set of cycles whose edge vectors lie on top of each other. Proof. Suppose first that Row(A) = Span{[ai, a2,..., an]} with aj = 0. Then Null(A) = Span{[—a2, ai, 0,..., 0]T, [0, —a3, a2,..., 0]T,..., [0, 0,..., —an, an-1]T}, and these n — 1 vectors represent n — 1 degenerate cycles. Each of the vertices in the middle of the cycle is a null vertex—a vertex where exactly the same edges enter and exit. On the other hand, the edges entering/leaving the two end vertices satisfies the row space condition, i.e., at each end |aj | copies of Sj enter or exit and the sign of aj determines which end the edge Sj enters and which end it exits. If aj = 0, then Sj = 0 since this is the only edge vector that ends where it begins. □ Example 2.8. Reversing the situation in the previous example, suppose that Row(A) = Span{[0,1, —3,2]}. Then Null (A) = Span{[1,0,0,0]T, [0, 3,1,0]T, [0,0,2, 3]T}. The first vector in the span ([1,0,0,0]T) implies that s1 = 0. Figure 5 shows a degenerate Kirchhoff graph for this example. 5Clearly the union of any two Kirchhoff graphs is also a Kirchhoff graph, but the author believes that these are the only two minimal or prime Kirchhoff graphs for this matrix. 132 Ars Math. Contemp. 9 (2015) 115-124 S4 •—//-» //-» //- S3 -VA--VA-• s 2 v v L R Figure 5: A degenerate Kirchhoff graph to illustrate Proposition 2.7. The three sets of vectors must be overlaid to form the Kirchhoff graph so that all edge vector sets begin or end at the two end vertices vL and v R. The middle vertices are null vertices where copies of an edge both begin and end. Another basic case that should be considered is the one mentioned in the Introduction: Proposition 2.9. Suppose that A e Mm,n (Q) is row equivalent to the incidence matrix for a standard cyclic digraph (having at most one edge vector between any two vertices, and no edge vector appearing multiple times in the digraph). Then this digraph is a Kirchhoff graph for A. Remark 2.10. A matrix is the incidence matrix for a standard cyclic digraph if and only if (1) all elements are 0 or ±1, (2) each column has exactly one 1 and one -1, (3) no two columns have their nonzero elements in the same rows, and (4) each row has at least two nonzero elements. Proof. In this case the standard result that the cycle space and the cut space of a graph are orthogonal complements yields the desired result, since Null( A) and Row( A) are preserved under row operations (cf. e.g. Diestel [5, p. 22] or Bollobas [1, p. 53]). □ One might think that every geometric cyclic multi-digraph is the Kirchhoff graph for some matrix; this is not the case, as the following counterexample shows. Consider the Figure 6: Three similar geometric cyclic multi-digraphs: the leftmost is not the Kirchhoff graph of any matrix; the center and rightmost are Kirchhoff graphs. Note that the Kirchhoff graph in the center is not minimal; it is simply the union of two triangular Kirchhoff graphs, each triangular graph having one copy of each edge vector. leftmost geometric cyclic multi-digraph in Figure 6. If this graph is a Kirchhoff graph for J. D. Fehribach: Matrices and their Kirchhoff graphs 133 some matrix A, then [1,1, — 1]T must be in Null(A) and [1,1,1] must be in Row(A) which of course is impossible since these vectors are not orthogonal. So the cycle space and the cut space for this graph are not orthogonal. There are two possible Kirchhoff graphs similar to this non-Kirchhoff graph, and they are shown in the center and on the right in Figure 6. Finally the following proposition is an immediate consequence of the definition of Kirchhoff graph: Proposition 2.11. If G is a Kirchhoff graph for a matrix A, and if B is the same as A except that columns ji and j2 are interchanged, then a Kirchhoff graph for B is obtained by interchanging the labeling of edge vectors Sj1 and Sj2 in G. 3 Kirchhoff Graphs and Reaction Networks Let us now consider connections between Kirchhoff graphs and chemical reaction networks. As was mentioned in the Introduction, the study of such reaction networks led to the definition of a Kirchhoff graph. The reaction network discussed below describes the production of sodium hydroxide from a brine (salt) solution through electrolysis. There are a number of processes to accomplish this production (Castner-Kellner, diaphragm, membrane), and a number of variations of these processes [2, 17]. The steps presented here do not all necessarily occur in all processes, but considering all the steps together allows one to compare various processes. The reaction steps for the network to be studied here are as follows: si 52 53 54 55 56 57 58 NaCl 2Cl- 2Na+ + 2e- + 2H2O H+ + Cl-Na+ + OH- 2H+ + 2e-H2O 2H2O + 2e- Na+ + Cl-Cl2 + 2e-2NaOH + H2 HCl NaOH H2 H+ + OH- H2 + 2OH- (3.1) For this network, the charged species are viewed as intermediate, while the uncharged species are viewed as terminal. The net concentrations of the intermediate species are constant as the reaction steps proceed, while the terminal species are being produced or consumed by the reaction network. Based on these steps (3.1) and this definition of intermediate and terminal species, the achievable overall reactions for this reaction network are determined using basic linear algebra [9]. In this case the two achievable overall reactions are bi : 2NaCl + 2H2O ^ Cl2 + H2 + 2NaOH b2 : NaCl + H2O ^ HCl + NaOH ( ) Combining these two overall reactions (3.2) with the reaction steps (3.1) above, one obtains the entire reaction network. 134 Ars Math. Contemp. 9 (2015) 115-124 Now consider the stoichiometric matrix for this network: 0 1 0 1 0 -1 0 0 0 0 0 2 -2 0 0 0 0 0 1 0 0 0 -2 0 0 -2 0 0 -2 0 1 0 2 0 -1 0 0 -1 0 0 0 0 1 0 at = 0 0 -1 -1 0 0 0 0 0 0 1 -2 0 0 0 -2 0 0 0 1 0 0 0 0 1 0 1 0 -1 0 0 0 0 -2 0 2 0 0 0 -2 0 1 0 0 0 0 0 0 0 -2 -2 1 1 0 2 0 0 0 0 0 -1 -1 0 0 1 1 (3.3) In a stoichiometric matrix, the entries are the stoichiometric coefficients for each chemical equation with positive entries for products and negative entries for reactants (species that are consumed in a reaction step). The rows of AT correspond to the eight steps plus the two overall reactions; the columns correspond to the eleven chemical species, namely, in order, e-, Cl-, OH-, Na+, H+, NaCl, H2O, Cl2, H2, HCl and NaOH. To construct a Kirchhoff graph for this reaction network, we must compute both Null(A) and Row(A) where A is the transpose of the stoichiometric matrix in (3.3); one finds that Null(A) = Spanjui, u2, u3, u4} where u 1 := 0 0 2 1 0 0 1 0 -1 0 1 0 0 0 0 1 2 0 0 1 0 , u2 := 1 , U3 := 0 , u4 := 0 0 2 0 1 1 -1 0 0 0 0 -1 0 0 0 0 -1 (3.4) and that Row(A) = Span{v1, v2, v3, v4, v5, ve} where v1 : = [ 1 0 -2 0 -1 000 0 0 v2 : = [ 0 0 0 0 1 0 -1 -2 0 0 v3 : = [ 0 0 0 1 0 2 -1 0 0 0 v4 : = [ 1 0 0 0 0 000 2 1 v5 = [ 0 1 0 0 0 000 1 0 ve = [ 0 0 0 1 0 000 0 1 (3.5) Null space vectors u3 and u4 give the combinations of reaction steps that yield the two overall reactions; vectors u1 and u2 give two linearly independent null cycles among these steps—combinations of steps that exactly cancel. The six vectors in (3.5) give six linearly independent reaction-rate balance conditions which guarantee the rates for all ten steps in the reaction network balance so that all of the species concentrations change only through the overall reactions (see the specific example for rNaci below). By inspection, the columns and rows in (3.4) and (3.5) form a basis for Null (A) and Row(A), respectively. J. D. Fehribach: Matrices and their Kirchhoff graphs 135 Figure 7: Kirchhoff graph for NaCl-NaOH network. Hash marks again indicate the multiplicity of edge vectors between vertices. One Kirchhoff graph for this network is shown in Figure 7. This Kirchhoff graph is in fact the two dimensional projection of vectors which actually lie in an eleven dimensional phase space for the eleven chemical species in this reaction network. All of the nodes of Figure 7 lie in Row(A), while the cycles of Figure 7 correspond to vectors that span Null(A); these are of course the two defining properties that make the graph in Figure 7 a Kirchhoff graph for this reaction network, (3.1) and (3.2). Indeed one can confirm that the graph in Figure 7 is Kirchhoff by observing that the cut or incidence vectors of edges for each vertex are linear combinations of the vectors in (3.5), while the cycles in this graph are linear combinations of the vectors in (3.4). To see how the Kirchhoff graph in Figure 7 satisfies the Kirchhoff laws and is thus a circuit diagram for the NaCl-NaOH reaction network, the concepts of electrochemical potential and component potential must be introduced. An electrochemical potential can be defined for each species X in a reaction network, and as potentials, they can be combined linearly. The linear combinations of electrochemical potentials that are based on the stoichiometry of each reaction step Sj and each overall reaction bk are the component potentials for the reaction network. Up to an arbitrary reference potential, these component potentials are the potentials for the vertices of the Kirchhoff graph. So for example, if the potential of vertex v2 in Figure 7 is set to a reference potential (pv = pref), then the electrochemical potential for the vertex v3 at the opposite end of s2 is given by the stoichiometry of the second reaction step: Mv = Mref + — MCl2 — 2Me- 136 Ars Math. Contemp. 9 (2015) 115-124 The signs in the linear combination are determined by the direction of the reaction step. The difference in potential between two vertices connected by a reaction step vector is the affinity of that reaction step and is a property of that reaction step. Similarly a component potential can be determined for each vertex, and because of the stoichiometry, the net change in potential around any cycle in this Kirchhoff graph must be zero. This is of course the Kirchhoff potential law. For a more thorough discussion of electrochemical potentials and component potentials in the context of reaction networks, cf. e.g. Newman(2004) [18] andFehribach [7, 6]. To see that the Kirchhoff graph also satisfies the Kirchhoff current law, consider the reaction steps that are incident on vertex v i. Because the total amounts of each species must be conserved when the overall reactions are taken into account, the reaction rates for each reaction step (rSj and ru ) are not independent, but rather must satisfy a set of j bk rate-balance conditions: the rate of production/consumption of species X must be zero (rX = 0). So for example, the balance for vi represents the rate (or current) balance for the consumption of NaCl. Since NaCl occurs in reactions si, bi and b2, the stoichiometry again yields the needed rate balance condition: rNaCl = rSi + 2rbi + rb2 = 0 This is the Kirchhoff current law at vertex vi and corresponds precisely to v4 in (3.5). Similar rate balance conditions for other species or linear combinations of species hold for each vertex in the Kirchhoff graph. Thus both Kirchhoff laws are satisfied by this Kirchhoff graph, and the result is a fundamental connection between the fundamental theorem of linear algebra for the transpose of the stoichiometric matrix for a reaction network and the conservation principles of the Kirchhoff laws. Since the Kirchhoff laws are satisfied, a chemical engineer can use a Kirchhoff graph as a circuit diagram for a chemical reaction network in the same way an electrical engineer can use a traditional circuit diagram for an electrical network. 4 Existence and Construction of Kirchhoff Graphs As the NaCl-NaOH network makes clear, it is relatively easy to verify that a given geometric cyclic multi-digraph is a Kirchhoff graph for a given reaction network or a given matrix. One needs only to check that the two conditions in the definition for a Kirchhoff graph are satisfied. The two real issues are those of existence and construction of Kirchhoff graph(s) for a given reaction network or matrix. The question of existence is open, but the author offers the following conjecture: Conjecture 4.1. Every matrix over Q has a Kirchhoff graph. Proving this conjecture seems to be a difficult and interesting issue. While no proof is given here, a process for constructing Kirchhoff graphs offers one possible approach for a constructive proof—showing that the process always converges to a Kirchhoff graph would establish existence. The following two subsections demonstrate this process for two of the matrices above; the first is relatively simple, the second, somewhat more complicated. The final subsection below gives a general summary of the process. J. D. Fehribach: Matrices and their Kirchhoff graphs 137 4.1 Construction of First Kirchhoff Graph in Figure 4 One method to systematically construct a Kirchhoff graph for A in (2.1) is to "weave" the bases vectors of the null space through the row space to form the incidence matrix for a graph. To begin, consider two rows of A and the first basis vector for Null(A) in (2.2). Since the first elements in these rows are 1 and -1, these rows can correspond to the first two vertices in the graph with edge s1 connecting them. Now since the second element of the first row is a zero, one should consider the negative of the second row as a new third row of the developing incidence matrix; this new row corresponds to a new third vertex, with s2 now connecting the second and third vertices. But there would seem to be a problem in that the zero in the third position of the third row does not seem to allow an edge to connect the first and third vertices or to complete the first cycle. This problem can be overcome, however, by adding the negative of the first row to the original choice for the third row; this allows the 1 in the third position of the first row and the -1 in the third position of the new third row to correspond to —s3, completing the cycle corresponding to the first basis vector for Null(A). The partial three-vertex incidence matrix constructed so far is Here bold face numbers correspond to the vertices of this first cycle; the non-bold entries in the fourth column correspond to "loose ends" that must be "tied up" as the incidence matrix is developed. Only when all of the loose ends are dealt with in some way can one hope to have the incidence matrix for a complete Kirchhoff graph. Now to tie up at least some of the loose ends and incorporate the next basis vector from Null(A), additional rows from Row(A) corresponding to new vertices must be appended to the developing incidence matrix. Since this next null space basis vector corresponds to the cycle s2 + s3 — s4, it would seem to make sense to start with the s2 edge represented in the second column of the partial incidence matrix (4.1). Moving across this edge in the forward direction, one needs a forward copy of s3; this can be created by adding the negative of the third row in (4.1) to that third row (thus the vertex corresponding to the new third row becomes a null vertex), then appending as a fourth row the negative of the first row. The resulting (still) partial incidence matrix is now The cycle corresponding to the second basis vector from Null(A) is now shown in bold in (4.2), while the entries corresponding to the remaining two edges of the first basis vector are now in italics, and the remaining loose ends are in standard typeface. The partial incidence matrix in (4.2) still has three loose ends and thus is still incomplete. But these loose ends themselves now lie in Row(A) and thus can be tied up by appending one more row which is the negative of the current second row. To make the final incidence matrix symmetric, this final new row should be the fourth, and the previous 1 0 1 1 11 0 1 0 -1 -1 -2 (4.1) 1 0 1 1 1 1 0 1 0 1 — 11 — 1 0 1 0 1 1 (4.2) 138 Ars Math. Contemp. 9 (2015) 115-124 fourth row should become the fifth. The now complete incidence matrix is 1 0 1 1 1 1 0 1 0 1-1 1-1 0 1 -1 0 -1 1 0 1 1 Again the typeface indicates which column-element pairs represent vertices which are connected by an edge. All of the vertices satisfy the second Kirchhoff graph condition because all of the rows of (4.3) are in Row(A), and it is easy to check that all of the cycles represented in (4.3) are in Null( A). Keeping in mind that an edge vector that appears multiple times in the graph must always have a fixed length and direction, one can use (4.3) to draw the left Kirchhoff graph in Figure 4, or an equivalent version of this graph. Of course there were many free choices in the above construction where one could have added new vertices and/or edges in alternate ways. One set of alternate choices would lead to the other graph in Figure 4. Still other choices could lead to a diverging construction of a larger and larger graph which never satisfies both of the Kirchhoff conditions at all of its vertices and for all of its cycles. A full algorithm for a construction would need a measure of how close/far the process is from converging to determine whether to proceed with an ongoing construction, or to go back to some earlier point in the construction and make a different choice for rows to add or cycles to weave. 4.2 Construction of Kirchhoff Graph in Figure 7 Now we turn our attention to the construction of a Kirchhoff graph for a somewhat larger matrix—A defined by (3.3). To begin, consider vectors u1 and u2 from Null(A) in (3.4) and vectors v\, v2 and v3 from Row(A) in (3.5). These cycles/cuts do not involve either of the overall reactions b1 or b2 and therefore constitute an important subgraph to the Kirchhoff graph we seek. Because the third element of u1 is -1, let us start with row vector vi, and take this as the first row of a partial incidence matrix. Since this is in fact the only row space vector with a nonzero third entry, the only choice for the second row of the incidence matrix is the negative of the first row, and the -2 and 2 in the third column of these first two rows of a partial incidence matrix represent s3 from u1. The next row in the incidence must be connected to the second row by either s5 or s8 (the other two edge vectors in u1). Since the only nonzero entries in the second incidence matrix row are in the first and fifth columns, one should hope to use s5 to connect the second and third rows of the incidence matrix. This third row cannot be a multiple of the first or second since then s3 and s5 would need to be multiples of each other. So the only possible choice among the given row space vectors that s5 can connect to is the negative of row vector v2 in (3.5). To complete this first cycle and represent the rest of the entries v1, the fourth row on the incidence matrix can be the negative of the third. Two copies of s8 then connect the 2 and - 2 in the eight columns of the third and fourth rows of the incidence matrix, and finally an s5 then connects the 1 and -1 in the fifth column of the fourth and first rows, thus completing the cycle and weaving v1, through several row vectors from (3.5). This weave is shown in (4.4) where the bold face numbers correspond to vertices that are in the first cycle. In (4.4), note that each row corresponds to a vertex, and each column corresponds to an edge vector. Since there are two s5 edge vectors in this cycle, the entries corresponding J. D. Fehribach: Matrices and their Kirchhoff graphs 139 to each vector are realigned to the left or right to indicate which vertices are connected: 1 0 —2 0 — 1 0 0 0 0 0 1 0 2 0 1 0 0 0 0 0 0 0 0 0 — 1 0 1 2 0 0 0 0 0 0 1 0 1 2 0 0 (4.4) Again, the convention is that edge vectors go from positive entries to negative ones, and these entries must always have the same absolute value. Also the non-bold elements of (4.4) represent edge vectors that are currently open (not connected) and must be connected in the eventual full incidence matrix. Now we must try to incorporate the second cycle (i.e., the second vector from (3.4)) into the partial incidence matrix. Although there is no guarantee, one can hope that the s8 edge vector from the first cycle is common to this second cycle and therefore start with it. Because the (3,7) element of (4.4) is 1, it makes sense to try to have s7 leave v3. This edge cannot go to v4 since it would then connect the same vertices as s8. Since one also needs s6 in this cycle, it makes sense to add v3 to the partial incidence matrix, and thereby to add a new vertex to the graph. Adding -v3 as the sixth row of the partial incidence matrix, one connects these rows and their vertices using edge vectors s6 and s7 to complete the second cycle. The rows of the partial incidence matrix for the first six vertices are now given in (4.5); the first cycle is now in italics, while the new cycle is in bold: 1 0 — 2 0 — 1 0 0 0 0 0 1 0 2 0 1 0 0 0 0 0 0 0 0 0 — 1 0 1 2 0 0 0 0 0 0 1 0 —1 —2 0 0 0 0 0 1 0 2 —1 0 0 0 0 0 0 1 0 2 1 0 0 0 Next one must include u3 and u4, the latter two null space vectors from (3.4), and do this in such a way so as to tie up the non-boldface, non-italicized entries in (4.5). Considering u3, one must have two copies of the si edge vector and one s3 in this cycle. The first two vertices (the first two rows of (4.5)) are already connected by two copies of s3 and have loose ends for si in the proper direction, so this would seem a natural place to tie in the third cycle. To complete this cycle, one must add a vertex corresponding to v4 and add an s1 edge vector to connect this seventh row of the partial incidence matrix to its second row. Continuing this cycle, one must add an eighth row to the partial incidence matrix which is two times v5, and two copies of b1 to connect the vertices that correspond to these seventh and eighth rows. Finally two copies of s2 are needed to complete the cycle, but upon checking each of the rows in (3.5), one finds that none have the correct requirements for a final vertex. This means that linear combinations of the rows in (3.5) must be considered. Taking into account all of the requirements for this final vertex, one finds that the correct linear combination is v4 — 2v5. This linear combination then becomes the ninth row of the partial incidence matrix, and the corresponding vertex is connected to v1 by one copy of s1, and to v8 by two copies of s2, all with the proper orientation to complete the third 140 Ars Math. Contemp. 9 (2015) 115-124 cycle. The partial incidence matrix for the first nine vertices is thus 1 0 -2 0 -1 0 0 0 0 0 -1 0 2 0 1 0 0 0 0 0 0 0 0 0 -1 0 1 2 0 0 0 0 0 0 1 0 -1 -2 0 0 0 0 0 1 0 2 -1 0 0 0 0 0 0 -1 0 -2 1 0 0 0 1 0 0 0 0 0 0 0 2 1 0 -2 0 0 0 0 0 0 -2 0 1 2 0 0 0 0 0 0 0 1 (4.6) Again the new cycle in (4.6) is in bold, while the two previous cycles are now in italics. In this case, the final cycle corresponding to u4 is easy to include, but it must occur twice. The partial incidence matrix (4.6) has only four loose connections (nonzero entries that are neither in italics or bold), and happily these can be connected pairwise by copies of s4 and b2 through the addition of two new vertices, one corresponding to v6, and the other corresponding to its negative. The full incidence matrix is then 1 0 -2 0 -1 0 0 0 0 0 -1 0 2 0 1 0 0 0 0 0 0 0 0 0 -1 0 1 2 0 0 0 0 0 0 1 0 -1 -2 0 0 0 0 0 1 0 2 -1 0 0 0 0 0 0 -1 0 -2 1 0 0 0 1 0 0 0 0 0 0 0 2 1 0 -2 0 0 0 0 0 0 -2 0 -1 2 0 0 0 0 0 0 0 -1 0 0 0 -1 0 0 0 0 0 -1 0 0 0 1 0 0 0 0 0 1 (4.7) For simplicity, no entries in (4.7) are in bold or italics, but entries corresponding to different copies of the same edge are still shifted to the right or left side of their column. Remark 4.2. Again when the edge vectors that satisfy the definition of Kirchhoff graph are actually drawn, (Definition 2.1), their exact length and direction are not important. One needs only to ensure that a given edge vector sj has the same length and orientation each time it appears in the graph, and to avoid any degeneracies (accidentally placing two distinct vertices in the same position). Because a Kirchhoff graph is actually a two dimensional projection of a much higher dimensional geometric structure, the incidence matrix is sufficient to produce some projection of this structure. For example, if the Kirchhoff graph comes from a reaction network with N species, then the vector structure lies in the stoichiometric space QN. Dividing the process into two parts as was done above, first constructing the part of the graph that does not involve the overall reactions (or some other group of reaction steps), then adding on these remaining steps (edges) as the row and null space vectors require, J. D. Fehribach: Matrices and their Kirchhoff graphs 141 is often a very effective way of constructing a full Kirchhoff graph. Of course the above construction is not guaranteed to produce a Kirchhoff graph, and in particular there are points in the process where one might choose the wrong row and not be able to neatly complete a given cycle. One would then have to go back and consider different rows or linear combinations of rows from (3.5) to form possible rows in a partial incidence matrix. Fortunately this laborious process should be computerizable, so that a computer can sort through the possible weaves to produce a Kirchhoff graph, assuming that one actually exists. 4.3 Summary of Kirchhoff Graph Construction While the construction process used above contains too many free choices to be called an algorithm, it does have a certain structure which it is useful to summarize. Given a matrix A over Q, the process can be summarized in the following general steps: Step 1: Construct bases with integral elements for both Null(A) and Row(A). Even for moderately large matrices, this construction can be accomplished effectively with any of a number of software packages/applications. Step 2: Refine the bases found in Step 1 to find ones that satisfy minimal total absolute sum norms: If [xi} is an integral basis for one of these two spaces, with xi = (xij) and xij e Z, refine this basis until J2ij Ixij I minimal. Step 3: Starting with the minimal basis for Row(A), begin to construct a first attempt at an incidence matrix for the first vector in Null(A). The construction may require linear combinations of the row vectors. This first attempt should have column pairs which represent each edge in the cycle corresponding to this first vector in Null(A), but the order of the edges may or may not match what is eventually needed, and there will in general be "loose ends," entries in the matrix which represent one end of an edge for which there is not yet an entry for the other end. As in the earlier examples, it may also be necessary to introduce one or more null vertices (a rows of zeros) to form an incidence matrix consistent with this first null space vector. Step 4: Next, attempt to include the next vector from Null(A) in the growing incidence matrix, using as many of the loose ends as possible, but also adding new rows from Row(A) as needed. Note that each additional row in the incidence matrix corresponds to an additional vertex in the developing Kirchhoff graph. Step 5: If all vectors from Null(A) have been included and all loose ends have been ellim-inated, then the construction of the incidence matrix and the Kirchhoff graph are complete. If there remain vectors from Null(A) to be included, but the number of loose ends is in some sense declining, return to Step 4 to add another null space vector. If the number of loose ends is in some increasing, then return to Step 3 and/or Step 4 to change the order in which the edges appear in one or more cycles, or change the row vectors that determine which edges are incident to each vertex. 5 Conclusion A Kirchhoff graph for a rational matrix is a graph-theoretic representation of the fundamental theorem of linear algebra for that matrix. When the matrix is based on a reaction network, a Kirchhoff graph is a circuit diagram for that reaction network, and it represents the connection between the Kirchhoff laws and the fundamental theorem of linear algebra. 142 Ars Math. Contemp. 9 (2015) 115-124 Figure 8: An example of a relatively simple matrix with a fairly intricate Kirchhoff graph. Edge vector s42 is the vector sum of s2 and s4 which always occur in sequence. The multiplicity of an edge vector between given vertices is given by hash marks which should be read as Roman numerals. To reduce crowding, not all edge vectors are labeled. Certainly the most interesting open question unresolved in this work is the actual existence of a Kirchhoff graph for any given matrix. While it is not obvious that the conjecture is true, it is clear that there is no guarantee that a Kirchhoff graph for a relatively simple matrix will itself be in any sense simple. Consider the matrix 1 -1 1 0 0 A = 0 1 0 1 0 -4 0 0 1 1 Then Null (A) = Span {[0, 1, 1,-1, 1]T, [ 1, 0,-1, 0, 4]T} (5.2) and Row(A) is the span of the three rows of A. Therefore a Kirchhoff graph for this matrix must have two linearly independent cycles, and all of its vertices must lie in the row space, but this really does not indicate how intricate a Kirchhoff graph for A is. The author believes that the Kirchhoff graph given in Figure 8 is the simplest one corresponding to A in (5.1). It is difficult to image that anyone could guess how complicated a Kirchhoff graph for A needs to be just looking at A, Null(A) and Row(A). Other matrices that would appear similar to A have much simpler Kirchhoff graphs, but there are also other relatively simple matrices (or relatively simple reaction networks) where to the author's knowledge no Kirchhoff graph has yet been constructed and any possible Kirchhoff graph must be large and intricate. For example, consider the matrix A- 1003 1829 -17 0 0 59 1411 1003 (5.3) The rows of A in (5.3) clearly form a basis for Row(A), and no linear combination of these two rows will lead to a simpler set of vertex conditions for any possible Kirchhoff graph. J. D. Fehribach: Matrices and their Kirchhoff graphs 143 One also finds that Null(A) = Span 31 " 1 -17 0 0 59 1 -83 (5.4) so any possible Kirchhoff graph for this matrix must be a complicated weave of large cycles based on these null space vectors. Again considering linear combinations of these null space vectors would not simplify the graph. The rows of (5.3) and the vectors of (5.4) satisfy the minimal total absolute sum norm condition discussed in Step 2 above. If the matrix in (5.3) is the stoichiometric matrix of some reaction network, even if one succeeds in constructing a Kirchhoff graph, it would seem to be of little use since it would be far too complicated. But since stoichiometric coefficients are typically 0, ±1 or occasionally ±2, elements like those in (5.3) are not realistic as stoichiometric coefficients. From an applications point of view, the key point is that when the Kirchhoff graph for a reaction network is relatively simple, it can be used to study the reaction network in the same way that a circuit diagram is used to study an electrical network. One can construct equivalent circuits, study how temperature, pH or other changes which reaction pathway is dominant, or compute the rate of an overall reaction from the rates of the individual steps, to name a few. In terms of future work, the process for constructing Kirchhoff graphs needs to be computerized. This will make it possible to find Kirchhoff graphs for matrices and reaction networks where construction by hand is too time consuming to be practical. Finally it seems worth noting that there is a certain aesthetic beauty in the intricacy of the more-complicated Kirchhoff graphs such as the one in Figure 8. 6 Acknowledgments The author wishes to thank Manasi Vartek for originally bringing to his attention the NaCl-NaOH reaction network, and also wishes to thank Ravi Datta and Ilie Fishtik for introducing him to the concept of reaction route graphs, and Pete Christopher, Willy Hereman, Bill Martin, Brigitte Servatius, Gil Strang and Lubos Thoma for many illuminating discussions on graph theory and linear algebra. Finally, the author wishes to thank the referees for numerous helpful suggestions and corrections. References [1] B. Bollobas, Modern Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, New York, NY, 1998. [2] T. Bommaraju, P. Orosz and E. Sokol, Brine electrolysis, Electrochemistry Encyclopedia: http://electrochem.cwru.edu/encycl, September 2007. [3] B. L. Clarke, Stability of complex reaction networks, in: I. Prigogine and S. A. Rice (eds.), Advances in Chemical Physics, Wiley, Chichester, volume 43, 1980, 1-215. [4] G. Craciun and M. Feinberg, Multiple equilibria in complex chemical reaction networks: II. the species-reaction graph, SIAM J. Appl. Math. 66 (2006), 1321-1338. [5] R. Diestel, Graph Theory, Graduate Texts in Mathematics, Springer-Verlag, New York, NY, 1997. 144 Ars Math. Contemp. 9 (2015) 115-124 [6] J. D. Fehribach, J. A. Prins-Jansen, K. Hemmes, J. H. W. de Wit and F. W. Call, On modelling molten carbonate fuel-cell cathodes by electrochemical potentials, J. Appl. Electrochem. 30 (2000), 1015-1021. [7] J. D. Fehribach, Diffusion-reaction-conduction processes in porous electrodes: the electrolyte wedge problem, European J. Appl. Math. 12 (2001), 77-96. [8] J. D. Fehribach, The use of graphs in the study of electrochemical reaction networks, in: C. Vayenas, R. E. White and M. E. Gamboa-Aldeco (eds.), Modern Aspects of Electrochemistry, Springer-Verlag, New York, NY, volume 41, chapter 3, 2007, 197-219. [9] J. D. Fehribach, Vector-space methods and Kirchhoff graphs for reaction networks, SIAM J. Appl. Math. 70 (2009), 543-562. [10] I. Fishtik and R. Datta, A thermodynamic approach to the systematic elucidation of unique reaction routes in catalytic reactions, Chem. Eng. Sci. 55 (2000), 4029-4043. [11] I. Fishtik, C. A. Callaghan and R. Datta, Reaction route graphs. I. theory and algorithm, J. Phys. Chem. B 108 (2004), 5671-5682. [12] I. Fishtik, C. A. Callaghan and R. Datta, Reaction route graphs. II. examples of enzyme and surface catalyzed single overall reactions, J. Phys. Chem. B 108 (2004), 5683-5697. [13] I. Fishtik, C. A. Callaghan, J. D. Fehribach and R. Datta, A reaction route graph analysis of the electrochemical hydrogen oxidation and evolution reactions, J. Electroanal. Chem. 576 (2005), 57-63. [14] I. Fishtik and R. Datta, A reaction route network for hydrogen combustion, Physica A 373 (2007), 777-784. [15] F. Horn, On a connexion between stability and graphs in chemical kinetics. I. Stability and the reaction diagram, Proc. R. Soc. Lond. A. 334 (1973), 299-312. [16] F. Horn, On a connexion between stability and graphs in chemical kinetics. II. Stability and the complex graph, Proc. R. Soc. Lond. A. 334 (1973), 313-330. [17] C. Mantell, Electrochemical Engineering, Chemical Engineering Series, McGraw-Hill, New York, NY, 4th edition, 1960, chpt 11: Electrolysis of alkali halides and sulfates. [18] J. Newman and K. Thomas-Alyea, Electrochemical Systems, Prentice Hall, Englewood Cliffs, NJ, 3rd edition, 2004. [19] J. Pach, Geometric graph theory, in: Surveys in Combinatorics, London Math. Soc. Lecture Note Series, Cambridge Univ. Press, Cambridge, UK, 1999, 167-200. [20] J. Pach, Geometric graph theory, in: J. Goodman and J.O'Rourke (eds.), Handbook of Discrete and Computational Geometry, 2nd edition, CRC, New York, NY, 2004, 219-238,. [21] J. Pach (ed.), Towards a Theory of Geometric Graphs, Contemporary Mathematics, AMS, Providence, RI, 2004. [22] A. Perelson and G. Oster, Chemical reaction dynamics, Part II: reaction networks, Arch. Rat. Mech. 57 (1974), 31-98. [23] P. Schlosser and M. Feinberg, A theory of multiple steady states in isothermal homogeneous CFSTRs with many reactions, Chem. Eng. Sci. 49 (1994), 1749-1767. [24] G. Strang, Introduction to Linear Algebra, Wellesley-Cambridge Press, Wellesley, MA, 3rd edition, 2005. [25] S. A. Vilekar, I. Fishtik and R. Datta, The steady-state kinetics of parallel reaction networks, Chem. Eng. Sci. 65 (2010), 2921-2933.