# Kirchhoff graph

In the mathematical field of graph theory, a Kirchhoff graph is a vector graph (a graph whose edges are vectors or are assigned vectors) that satisfies a generalized version of Kirchhoff's laws (and is therefore named after Gustav Kirchhoff). If the edge vectors represent reaction steps for a reaction network, a Kirchhoff graph can be viewed as a circuit diagram for the reaction network..[1] For a finite set of vectors in some vector space, a Kirchhoff graph represents the dependencies of these vectors. In this regard, Kirchhoff graphs are related to matroids[2] They also represent the orthcomplementrarity of the row space and the null space of the matrix whose columns represent these vectors; the vertex cuts lie in the row space and the cycles of the graph span for the null space

### Definition

Given a finite set of <math display="inline">n[/itex] vectors <math display="inline">\{\mathbf{s}_1, \mathbf{s}_2, \ldots, \mathbf{s}_n\}[/itex] from some vector space, suppose that for <math display="inline"> 1<k<n [/itex], the first <math display="inline">k[/itex] are a basis for the span of the full set. Then it is possible to write each of the final <math display="inline">n-k[/itex] vectors as a linear combination of the first <math display="inline">k[/itex]: <math display="block">[\mathbf{s}_1, \mathbf{s}_2, \ldots, \mathbf{s}_k, \mathbf{s}_{k+1}, \mathbf{s}_n]\begin{bmatrix}

     C_0     \\
\vdots  \\
-I


\end{bmatrix} = \mathbf{0}[/itex] where <math display="inline">[\mathbf{s}_1, \mathbf{s}_2, \ldots, \mathbf{s}_n][/itex] is the vector whose entries are the <math display="inline">\mathbf{s}_i[/itex] vectors, <math display="inline">C_0[/itex] is the <math display="inline">k\times(n-k)[/itex] coefficient matrix, and the multiplication here is the row vector of vectors dotted with each of the columns of the matrix <math display="inline"> n\times(n-k) [/itex] whose upper block is <math display="inline">C_0[/itex] and whose lower block is the negative of the <math display="inline">(n-k)\times(n-k)[/itex] identity matrix.

Now, assuming that all of the entries of <math display="inline">C_0[/itex] are rational (the vectors <math display="inline">\mathbf{s}_i[/itex] form only rational combinations), let <math display="inline">q[/itex] be the least common multiple of the denominators of these entries. Define <math display="block"> R := \begin{bmatrix} qI\mid C \end{bmatrix}\qquad\text{ and }\qquad N := \begin{bmatrix}

      C     \\
\vdots  \\
-qI


\end{bmatrix}[/itex] where <math display="inline">C := qC_0[/itex] is row-equivalent to <math display="inline">C_0[/itex] but has integer entries. The rows of <math display="inline">R[/itex] form a basis for the row space of <math display="inline">R[/itex], while the columns of <math display="inline">N[/itex] form a basis for the null space of <math display="inline">R[/itex]. By the rank–nullity theorem for the row space and the null space of a matrix, these two bases can be combined and viewed as a basis for either <math display="inline">\mathbb{R}^n[/itex] or <math display="inline">\mathbb{Q}^n[/itex]. Also as with <math display="inline">\mathbf{s}_i[/itex] vector above, because of the orthogonality of the rows and columns, <math display="inline">RN = \mathbf{0}[/itex]. So regardless of which vector space the <math display="inline">\mathbf{s}_i[/itex] come from, the columns of <math display="inline">R[/itex] can be used as a canonical representation for the <math display="inline">\mathbf{s}_i[/itex].

A Kirchhoff graph for the set <math display="inline">\{\mathbf{s}_1, \mathbf{s}_2, \ldots, \mathbf{s}_n\}[/itex], the matrix <math display="inline">R[/itex] and/or any matrix row-equivalent to <math display="inline">R[/itex] is a vector graph (1) whose edges are the edge vectors <math display="inline">\mathbf{s}_i[/itex], (2) whose vertex cuts span the row space of <math display="inline">R[/itex] and (3) whose cycles span the null space of <math display="inline">R[/itex] .

Here is a simple example of a Kirchhoff graph: Suppose that <math display="block"> R = \left[ \begin{array}{rrrr} 1 & 0 & 1 & 2\\ 0 & 1 & 2 & 1 \end{array} \right] \qquad \text{ and }\qquad N = \left[ \begin{array}{rr}

1 &  2\\
2 &  1\\


-1 & 0\\

0 & -1


\end{array} \right][/itex] So here <math display="inline">q = 1[/itex]. Again the columns of <math display="inline">R[/itex] represent the vectors <math display="inline">\{\mathbf{s}_1, \mathbf{s}_2, \mathbf{s}_3, \mathbf{s}_4\}[/itex]. The four smallest Kirchhoff graphs in this case are:

Small symmetric Large symmetric Lower chiral Upper chiral

The numbers on the edge vectors give the numbers of copies of a given edge vector that lie in parallel between the same vertices. For the small symmetric graph, notice that the vertex cut for the lower left vertex is <math display="inline">[ 1, 1, 3, 3][/itex] which is the sum of the two rows of <math display="inline">R[/itex], and indeed all of the vertex cuts are some linear combination of the rows of <math display="inline">R[/itex] (a negative entry in a vertex cut corresponds to a vector entering that vertex). Similarly, the cycle vector <math display="inline">[ 1, -1, 1, -1]^\textsf{T}[/itex] is the difference of the two columns of <math display="inline">N[/itex] and represents (starting at the vertex on the lower left) the cycle <math display="inline">\mathbf{s}_1 + \mathbf{s}_3 - \mathbf{s}_4 - \mathbf{s}_2[/itex].

### Chirals

Given a Kirchhoff graph projected onto a plane (if its natural embedding is in a higher dimensional space), its chiral is obtained by rotating the entire graph by 180 degrees, then reversing (flipping) each individual vector. This chiral graph must also be a Kirchhoff graph

In the example above, the two Kirchhoff graphs on the left are symmetric in the sense that they are self chirals. The two Kirchhoff graphs on the right, on the other hand, are each the chiral of the other.

### Uniformity

One of the most important properties for many Kirchhoff graphs is uniformity---that each edge vector occurs in the graph the same number of times counting the edge multiplicities. For a uniform Kirchhoff graph, let <math display="inline">m[/itex] be the common edge multiplicity; in the example above, <math display="inline">m = 6[/itex] for each Kirchhoff graph.

The general uniformity result is that all vector 2-connected Kirchhoff graphs are uniform[3][4]

### Reaction network circuit diagram

For the hydrogen evolution reaction (HER) network, the overall reaction (that does not occur directly) and the three reaction steps that yield that overall reaction are as follows[1] <math display="block">\begin{array}{rrcl} \mathbf{b}~~:&2\text{H}_2\text{O} + 2\text{e}^- & \rightleftharpoons & \text{H}_2 + 2\text{OH}^- \\ \mathbf{s}_{\textsf{T}}:&2\text{H}\cdot\text{S} & \rightleftharpoons & 2\text{S} + \text{H}_2 \\ \mathbf{s}_{\textsf{V}}:&\text{S} + \text{H}_2\text{O} + \text{e}^- & \rightleftharpoons & \text{H}\cdot\text{S} + \text{OH}^- \\ \mathbf{s}_{\textsf{H}}:&\text{H}\cdot\text{S} + \text{H}_2\text{O} + \text{e}^- & \rightleftharpoons & \text{S} + \text{H}_2 + \text{OH}^- \end{array}[/itex] The stoichiometric matrix for this network is then <math display="block"> \left[ \begin{array}{rrrr}

1 &  1 &  0 &  1\\
2 &  0 &  1 &  1\\


-2 & 0 & -1 & -1\\ -2 & 0 & -1 & -1\\

0 &  2 & -1 &  1\\
0 & -2 &  1 & -1


\end{array} \right] [/itex] and this row-reduces to <math display="block"> R = \left[ \begin{array} {rrrr} 2 & 0 & 1 & 1 \\ 0 & 2 & 1 & -1 \end{array} \right] [/itex]

A Kirchhoff graph that can be used as a circuit diagram for the HER network is shown at right. This graph shows that the overall reaction can be achieved through any one of three reaction pathways: (1) $\mathbf{s}_{\textsf{V}} + \mathbf{s}_{\textsf{H}} = \mathbf{b}$ (2) $\mathbf{s}_{\textsf{V}} + \mathbf{s}_{\textsf{T}} + \mathbf{s}_{\textsf{V}} = \mathbf{b}$ and (3) $\mathbf{s}_{\textsf{H}} - \mathbf{s}_{\textsf{T}} + \mathbf{s}_{\textsf{H}} = \mathbf{b}$. These are the only pathways consistent with the stoichiometry. This also means that each cycle in this Kirchhoff graph correspond to a vector from the null space of the stoichiometric matrix—a version of the Kirchhoff potential law (since all species are conserved around a cycle, the electrochemical potential must also be conserved).

The Kirchhoff circuit law is reflected by the rate balances at each vertex (the sum of the rates at each node must be zero; what flows in flows out). In terms of the spaces, the requirement is that each vertex lies in the row space of the stoichiometric matrix and thus of <math display="inline">R[/itex]. For example, at the top and bottom vertex, $r_{\textsf{V}} - r_{\textsf{H}} = 2r_{\textsf{T}}$. So the difference between the rates for $\mathbf{s}_{\textsf{V}}$ and $\mathbf{s}_{\textsf{H}}$ is twice the rate for $\mathbf{s}_{\textsf{T}}$, and this balance makes this Kirchhoff graph a sort of Wheatstone bridge: the rate and direction of the flow across the middle on $\mathbf{s}_{\textsf{T}}$ determines whether the rate of $\mathbf{s}_{\textsf{V}}$ or $\mathbf{s}_{\textsf{H}}$ is largest.

All of the information in this Kirchhoff graph is also present in the stoichiometric matrix and in the electrochemical reaction steps, but it may be much easier to see in the Kirchhoff graph.

## References

1. Fehribach, Joseph D. (2009). "Vector-space methods and Kirchhoff graphs for reaction networks". SIAM J. Appl. Math. 70: 543–562. doi:10.1137/080722667. ISSN 0036-1399.
2. Reese, Tyler M.; Fehribach, Joseph D.; Paffenroth, Randy C.; Servatius, Brigitte (2018). "Matrices over finite fields and their Kirchhoff graphs". Linear Algebra and its Applications. 547: 128–147. doi:10.1016/j.laa.2018.02.020. ISSN 0024-3795.
3. Reese, Tyler M.; Fehribach, Joseph D.; Paffenroth, Randy C.; Servatius, Brigitte (2019). "Uniform Kirchhoff graphs". Linear Algebra and its Applications. 566: 1–16. doi:10.1016/j.laa.2018.12.018. ISSN 0024-3795.
4. Fehribach, Joseph D. (2019). "Kirchhoff graph uniformity". Congressus Numerantium. 233: 143–150.