{'fraction_non_alphanumeric': 0.06029808132783619, 'fraction_numerical': 0.013796115780838846, 'mean_word_length': 3.6568437763556085, 'pattern_counts': {'":': 0, '<': 2, '<?xml version=': 0, '>': 9, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 28, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Codes on graphs: Models for elementary algebraic topology and statistical physics

This paper is primarily a semi-tutorial introduction to elementary algebraic topology and its applications to Ising-type models of statistical physics, using graphical models of linear and group codes. It contains new material on systematic (n,k) group codes and their information sets; normal realizations of (co)homology spaces; dual and hybrid models; and connections with system-theoretic concepts such as observability, controllability and input/output realizations.


Introduction
Algebraic topology is a topic whose origins go back to Kirchhoff's circuit laws [3]; however, it is not very familiar to most engineers and scientists. A major purpose of this paper is to provide an introduction to elementary algebraic topology using graphical models that have arisen in coding theory-namely, normal realizations (NRs) [5] and normal factor graphs (NFGs) [13]-which turn out to be very well suited to this purpose.
This work was directly stimulated by that of Al-Bashabsheh and Vontobel [2], who as far as we know were the first to use NFGs to model algebraic topology spaces. They apply these models to computing partition functions of Ising-type models of statistical physics, which had been shown by Al-Bashabsheh and Mao [1] and Forney and Vontobel [9] to be nicely modeled by NFGs. Some differences in our approach are: • We use NRs rather than NFGs to model the principal spaces of elementary algebraic topology.
• We focus on the group case rather than the field case, using a "universal algebra" approach.
• In particular, algebraic topology spaces are regarded as "systematic (n, k) group codes." • We make connections to system-theoretic notions such as such as observability, controllability and input/output (I/O) realizations.
Another stimulus was the work of Molkaraie et al. [14,15,18], who have used dual NFGs for Monte Carlo evaluations of partition functions of Ising-type models. Our work lays an algebraic foundation for such evaluations, and systematically presents alternative approaches to carrying them out.
In Section 2, we develop the main results of elementary (one-dimensional) algebraic topology. We introduce a connection matrix M to describe the topology of a graph G = (V, E), which allows us to treat the group and vector space cases in a common "universal algebra" framework.
We introduce the concept of a systematic (n, k) group code over a group alphabet A, generalizing a linear (n, k) block code, and show that the principal spaces of elementary algebraic topology are systematic (n, k) group codes. We model all of these spaces by normal realizations. Using systemtheoretic concepts such as observability and controllability, we then reduce these realizations to minimal (observable and controllable) input/output (I/O) realizations.
We begin unconventionally with cohomology (coboundary operators, etc.), which we regard as more basic than homology (boundary operators, etc.), and then obtain dual results using an elementary adjoint homomorphism lemma, as well as normal realization duality. As is well known, we can exhibit "bases" of principal spaces that are based on cut sets and cycles of G in the primal and dual cases, respectively. Finally, we give simple dual normal realizations that we believe capture the essences of the zeroth and first (co)homology spaces of G.
In Section 3, following [1,2,9,18], we show how to model partition functions of an Ising-type (e.g., Ising or Potts) model by "edge-weighted normal factor graphs" based on normal realizations of algebraic-topology spaces as in Section 2. Some of the I/O realizations of Section 2 are simpler than the straightforward normal realizations that have been used previously, and may be more suitable for simulations. Our development holds for general finite abelian group spin alphabets A rather the usual cyclic group alphabets Z q .
Since the partition function of such a model is a constant, it is equal to its Fourier transform, which is represented by the dual NFG. As observed in [18], computations based on the dual NFG may be simpler, as in the case of a single-cycle graph, or may behave better at low temperatures. We generalize the well-known high-temperature expansion for Ising models (A = Z 2 ) to Potts models (A = Z q ) and to generalized Ising-type models whose spin alphabet A may be any finite abelian group.
In the presence of an external field, we show that a realization of the partition function using the dual NFG is generally more complicated (higher-dimensional) than using the primal NFG. To reduce this increased complexity, we suggest a novel hybrid model, with part in the primal domain, part in the dual domain, and a Fourier transform between them.
In Section 4, closely following [2], we give an introduction to two-dimensional algebraic topology, using planar graphs to illustrate two-dimensional complexes. We introduce dual graphs, and show (as in [2,18]) that there are in general four different ways to represent the partition function of an Ising-type model on a planar graph G, involving either G or its dual graphĜ, and either the original interaction weights or their Fourier transforms (in which temperature is dualized).
In an Appendix, we give a very simple proof of the normal factor graph duality theorem (NFGDT), including scale factors, and show how the scale factor must be modified when the NFG is based on a normal realization. Interestingly, this leads to an alternative proof of the controllability test of [8].

Introduction to elementary algebraic topology
The concepts of elementary (one-and two-dimensional) algebraic topology are often phrased in scary mathematical jargon, but they actually involve only some elementary graph theory and linear algebra, or, more fundamentally, the algebra of abelian groups.
This section is a tutorial introduction to these concepts, with the following unusual features: • We treat the field and group cases in a common setting; • We specify graph topology via a "connection matrix" M ; • We begin with cochains and coboundary operators rather than chains and boundary operators; consequently, our primal model is the dual of the usual primal model, and vice versa; • We give graphical models (normal realizations) of all important spaces; • We use system-theoretic properties such as observability, controllability and I/O realizations.

Elementary graph theory
A finite undirected graph G = (V, E) is specified by a finite vertex set V , a finite edge set E, and a specification of which two vertices are incident on each edge. In algebraic topology, each edge e ∈ E is given an orientation, perhaps arbitrary. We will call the two vertices that are incident on edge e its head vertex h(e) ∈ V and tail vertex t(e) ∈ V . This orientation is merely a technical device to resolve ambiguities; we still think of G as an undirected graph. (We assume that there are no self-loops; i.e., that h(e) = t(e). ) We then associate with each edge e ∈ E a {0, ±1}-valued row vector M e = (M ev , v ∈ V ) that has precisely two nonzero components, namely M eh(e) = +1 and M et(e) = −1. The |E| × |V | {0, ±1}-valued matrix M whose |E| rows are the vectors M e will be called the connection matrix of G. As we will see, it makes no difference whether we take M e or −M e as the eth row of M .
Thus each of the |E| rows of the connection matrix M has two nonzero values, namely ±1. The number of nonzero values in the vth column M v of M is the number of edges whose initial or final vertex is v, namely the degree d v of v. Example 1. Consider the directed graph G of Figure 1. G has |V | = 5 vertices and |E| = 6 edges. Its connection matrix is The key graphical parameters of a finite graph G = (V, E) are: • the number |V | of its vertices; • the number |E| of its edges; • the number β 0 (G) of its connected components, also called its zeroth Betti number ; • its "cyclomatic number" 1 β 1 (G) = |E| − |V | + β 0 (G), also called its first Betti number.
If G = (V, E) has β 0 (G) connected components G i = (V i , E i ), then V = i V i and E = i E i . If the vertices and edges are ordered to reflect this partition, then the connection matrix of G is M = diag{M 1 , M 2 , . . .}, where M i is the connection matrix of G i . The component graphs G i may then be analyzed independently. Therefore, without essential loss of generality, we will assume from now on that G is connected; i.e., β 0 (G) = 1 and β 1 (G) = |E| − |V | + 1.
The key property of β 1 (G) is that it is the number of edge deletions needed to reduce G to a spanning tree T of G. It is well known in elementary graph theory that if G = (V, E) is connected, then G contains a spanning tree T = (V, E T ), namely a cycle-free connected subgraph of G that comprises all |V | vertices of G and |E T | = |V | − 1 of its edges. The number of edge deletions required is thus |E| − |E T | = |E| − |V | + 1 = β 1 (G). It follows that β 1 (G) ≥ 0, with equality if and only if G is cycle-free. We will see that β 1 (G) measures the number of independent cycles in G.
For example, given the graph G of Example 1, we may obtain a spanning tree T ⊂ G by removing β 1 (G) = 2 edges; e.g., e 3 and e 5 . G contains three cycles, any two of which may be chosen as "independent;" the third cycle is then the "sum" of the other two. (These terms will be defined more satisfactorily later.)

Elements of algebraic topology
In algebraic topology [3], a finite graph G = (V, E) is called a 1-dimensional complex. Its vertices v ∈ V are called its 0-dimensional objects, and its edges e ∈ E are called its 1-dimensional objects. As we shall see, its connection matrix M is the matrix of a certain operator.
Let A be some abelian group alphabet. The reader will not be misled if he or she assumes that A is a field; however, we assert that all of our results hold if A is any abelian group with a well-defined dual groupÂ; e.g., any finite abelian group.
We consider the spaces C 0 = A V and C 1 = A E of all A-valued functions defined on V and E, respectively. In algebraic topology, the elements of C 0 and C 1 are called 0-cochains and 1-cochains, respectively. We will regard them as column vectors x ∈ A V and y ∈ A E indexed by V and E, respectively, which we will call vertex vectors x and edge vectors y, respectively.
In elementary algebraic topology, the coboundary operator d is defined as the homomorphism whose matrix is M ; i.e., d : 1 The term "cyclomatic number" was apparently coined by James Clerk Maxwell [10].
This definition makes sense because the "product" za is well-defined for all z ∈ Z, a ∈ A, for any abelian group A; i.e., we regard M as an integer matrix. If A contains a unit element 1-e.g., if A is a field or a ring with unity-then M may alternatively be thought of as an A-matrix.
Notice that if x has precisely one nonzero value x v = a, then the "coboundary vector" has precisely d v nonzero values y e = ±a, for the d v edge indices e such that edge e is incident on vertex v. Edge vectors y of the form M v a will be called elementary coboundary vectors.
The image of the coboundary operator d is called the coboundary space The kernel of the coboundary operator is called the zero-coboundary space Z 0 = ker d. We have immediately: is a connected graph, then its zero-coboundary space Z 0 = ker d is the repetition code C = = {(a, a, . . . , a) | a ∈ A} ⊆ C 0 over A.
Proof : The constraint M x = 0 implies that for every edge e ∈ E, M e x = 0. Since the row vector M e has precisely two nonzero values of opposite sign, this implies x h(e) = x t(e) for all e ∈ E; i.e., the vertex values at the two ends of edge e must be equal. Since G is connected, these edge constraints propagate throughout G, implying that all vertex values x v must be equal.
A graphical illustration of this proof will be given in Figure 3, below. Theorem 1 has the following corollary: is a connected graph, then its coboundary space B 1 = im d is isomorphic to A |V |−1 .
Proof : By the fundamental theorem of homomorphisms, we have Moreover, it is straightforward to show that (C 0 ) :v is a set of coset representatives for C 0 /Z 0 , and that the corresponding one-to-one map (C 0 ) :v ↔ C 0 /Z 0 is an isomorphism.

(n, k) group codes
In coding theory, if A is a field, then A n is a vector space, and any subspace C ⊆ A n of dimension k is called a linear (n, k) block code over A. Thus in the field case Z 0 = ker d is a linear (|V |, 1) block code over A, and B 1 = im d is a linear (|E|, |V | − 1) block code over A.
We now extend this nomenclature to abelian groups, which will allow us to extend elementary algebraic topology to the group setting.
Definition ((n, k) group codes). If A is an abelian group and I is an index set of size |I| = n, then any subgroup C ⊆ A I that is isomorphic to A k will be called an (n, k) group code over A.
In this spirit, given an (n, k) group code C over an abelian group A, we may call n its "length" and k its "dimension," even though, strictly speaking, the term "dimension" is inappropriate if A is not a field. We may also call A I a "space" and C ⊆ A I a "subspace. " We further extend this definition as follows: Definition (systematic (n, k) group codes, information sets, check sets). If A is an abelian group and I is an index set of size |I| = n, then a subgroup C ⊆ A I will be called a systematic (n, k) group code over A if the projection of C onto A J for some subset J ⊆ I of size |J | = k is an isomorphism to A J ∼ = A k . Any such subset J ⊆ I will be called an information set of C, and its complementJ = I \ J a check set of C.
A linear (n, k) block code C over a field F is any k-dimensional subspace of F n . Every such linear code C has a systematic k × n generator matrix that contains a k × k identity matrix as a submatrix, whose column positions are said to be an information set of C; the remaining column positions are called a check set. Thus every (n, k) linear block code over F is a systematic (n, k) group code over F, and our definitions of information and check sets are consistent in both settings.
The simplest example of a systematic (n, k) group code is a repetition code C = of length n over a group alphabet A, defined as where I is some coordinate index set of size |I| = n. C = is evidently a subgroup of A I that is isomorphic to A, and whose projection onto any coordinate is A. Thus C = is a systematic (n, 1) group code over A, and for any i ∈ I the singleton subset {i} is an information set.
For another example, a zero-sum code C + of length n over A is defined as where I is some coordinate index set of size |I| = n. C + is evidently a subgroup of A I . Moreover, since we may choose any n − 1 elements a i of a codeword a ∈ C + freely from A, and then choose the remaining element so that I a i = 0, it is evident that the projection of C + onto any subset J ⊂ I of size |J | = n − 1 is A J ∼ = A n−1 . Thus a zero-sum code of length n over A is a systematic (n, n − 1) group code over A, and every subset of I of size n − 1 is an information set. We now show that every systematic (n, k) group code has an I/O map, which will allow us to represent all of our realizations as I/O behaviors.
In system theory, a behavior of the form {(a J , ϕ C (a J )) | a J ∈ A J } is called an I/O behavior, where a J ∈ A J is regarded as the input, and ϕ C (a J ) ∈ AJ as the output. In this context, we will call the homomorphism ϕ C : A J → AJ an I/O map.
In the group case, to generalize the generator matrix concept, we note that a systematic (n, k) group code with information set J has a set of k "one-dimensional" subcodes that may be regarded as a systematic "basis," as follows. For each of the k coordinates i ∈ J , consider the subcode C i ⊆ C consisting of the codewords in C that are all-zero in the remaining k − 1 coordinates J \ {i}. By the isomorphism between A J and C, C i must be isomorphic to A via projection onto the ith coordinate. Moreover, C is evidently generated by the subcodes C i , so C must be their direct sum: For example, for the zero-sum code C + ⊂ A I , any subset {i} ⊂ I of size 1 is a check set, and the |I| − 1 "one-dimensional" subcodes (C + ) j , j = i, consisting of all codewords c ∈ C + such that c j = a, c i = −a, and all remaining coordinates are zero forms a "basis" for C + .
Finally, the support of an (n, k) group code C ⊆ A I is the subset J ⊆ I of indices such that the projection C |i of C onto the i th coordinate is nontrivial. If C has support J , then we may say that C is effectively a (|J |, k) group code, and that its effective length is |J |. For example, the subcodes C i defined above are effectively (n − k + 1, 1) group codes with supports {i} ∪J .

Elementary normal realizations
We will now construct normal realizations for the zero-coboundary space Z 0 = ker d and the coboundary space B 1 = im d, which will help to visualize their properties.
In general, a normal realization [5] is a graphical model based on a graph G = (V, E, H), in which the vertices (or "nodes") v ∈ V represent constraint codes C v , the edges e ∈ E represent internal variables, and the half-edges h ∈ H represent external variables. The constraint code C v is the set of all permissible ("valid") values of the variables corresponding to the edges and half-edges that are incident on vertex v. The set of all valid variable configurations-i.e., the configurations that are compatible with all constraints-is called the behavior B of the realization, and the projection of the behavior onto the half-edge variables is called its external behavior C, or the code C that it realizes. If all constraint codes are linear, then B and C are vector spaces; if all constraint codes are abelian groups, then B and C are abelian groups.
For this application, we need only elementary normal realizations, namely normal realizations that satisfy the following restrictions: • All internal and external variables have a common alphabet A, which is either a field F, or more generally an abelian group A with a well-defined dual (character) groupÂ; • All constraint codes are either repetition codes C = , which constrain all incident variables to be equal, or zero-sum codes C + , which constrain the sum of all incident variables to be zero. Thus if the degree of vertex v is n, then C v is either the (n, 1) repetition code C = over A, or the (n, n − 1) zero-sum code C + over A.
We will indicate repetition constraints by the symbol = , and zero-sum constraints by the symbol + . We may also employ the following simple manipulations and special symbols: • A repetition constraint of degree 2 may be simply replaced by an edge, since = = .
• A zero-sum constraint of degree 2 may be replaced by an edge with a small circle representing a sign inverter : + ⇒ • . We will sometimes call this an inverting edge.
• A repetition constraint of degree 2 plus a sign inverter may be replaced by an inverting edge, since =• = • .
• A zero-sum constraint of degree 2 plus a sign inverter may be replaced simply by an edge, since +• = .
• We may optionally put an arrow on an edge if we wish to indicate the direction of a causeand-effect relationship, as we will illustrate shortly below.
We now wish to study the image and kernel of the coboundary operator d : which is evidently a systematic (|V | + |E|, |V |) group code over A with information set V . Figure 2 shows an elementary normal realization of the I/O behavior W 01 for our example graph G. We observe that the graph G = (V G , E G , H G ) of this normal realization has |V G | = |V | + |E| vertices, |E G | = 2|E| edges, and |H G | = |V | + |E| half-edges. In Figure 2, a set x = {x v , v ∈ V } of |V | external input variables is associated with the vertices v ∈ V of G. Each vertex variable x v is replicated d v times via a repetition constraint, and passed on to a zero-sum constraint associated with one of the d v adjacent edges e ∈ E(v), through a sign inverter if v = h(e), thus making the input to the zero-sum constraint −M ev x v . For each edge e ∈ E, a zero-sum constraint on all the incident signed vertex variables and the output variable y e at edge e enforces the constraint y e + (−M e x) = 0; thus y = M x, as desired. Arrows on all edges indicate the directions of these cause-and-effect relationships. Now, to obtain a realization of the zero-coboundary space Z 0 = ker d = {x | M x = 0}, we constrain the external edge variables y e to equal zero, which simply removes them from the realization. (In other words, Z 0 is the cross-section (W 01 ) :0 = {x ∈ C 0 | (x, 0) ∈ W 01 } of the I/O behavior W 01 on C 0 .) Also, since +• = , we may simply use the latter realization for each edge. Thus we obtain the extremely simple realization of Z 0 that is shown in Figure 3. We have removed the arrows because the effects of the constraints now flow in all directions. Figure 3: Normal realization of Z 0 = ker d for graph G of Figure 1.
It is obvious from this realization that Z 0 is the (|V |, 1) repetition code C = ⊆ C 0 ; i.e., Figure  3 gives a pictorial proof of Theorem 1.
Moreover, if G were a disconnected graph with β 0 (G) > 1 connected components, then the corresponding realization of Z 0 = ker d as in Figure 3 would evidently consist of β 0 (G) disconnected (and therefore independent) repetition codes. (This is the principal reason why we have started in this paper with the coboundary operator d rather than the usual boundary operator ∂, since we regard connectedness as the most elementary topological concept.) Similarly, to get a realization of the coboundary space B 1 = im d, we simply remove the external vertex variables x v from Figure 2

Partitions and cut sets
We will now show that the coboundary space B 1 = im d may be thought of as the space generated by a certain set of cut set vectors, to be defined below. Given a connected graph G = (V, E), a partition P of G is specified by a disjoint partition V 1 ⊔ V 2 of the vertex set V into a subset V 1 ⊆ V and its complement V 2 =V 1 . Such a partition induces a partition of the edge set E into three subsets: a subset E 1 of edges whose ends are both in V 1 , a subset E 2 of edges whose ends are both in V 2 , and the remaining subset E P of edges that have one end in V 1 and one in V 2 . The subset E P is called the cut set of the partition P .
If one of V 1 or V 2 is empty, then the partition is said to be trivial, and the cut set E P is empty. If one of V 1 or V 2 is {v} for a single vertex v ∈ V , then the partition is said to be elementary, and the cut set E P is the set E(v) of indices of edges that are neighbors of vertex v.
A nontrivial partition P of a connected graph G thus partitions G into two disconnected subgraphs, G 1 = (V 1 , E 1 ) and G 2 = (V 2 , E 2 ), plus the cut set E P , comprising the edges that join G 1 to G 2 . The connection matrix M of G correspondingly partitions into six submatrices, namely the connection matrix M 1 of G 1 , the connection matrix M 2 of G 2 , two matrices M P 1 and M P 2 , each of which has a single nonzero value (M eh(e) or M et(e) ) in each of its |E P | rows, and two zero matrices, as follows: We will correspondingly write x ∈ C 0 as (x 1 , x 2 ) ∈ (C 0 ) 1 × (C 0 ) 2 , and y ∈ C 1 as (y 1 , y P , For a partition P of G, the cross-section (B 1 ) :P = {(y 1 , y P , y 2 ) ∈ B 1 | (y 1 , y 2 ) = (0, 0)} of B 1 will be called the cut set subspace of B 1 corresponding to P , and the elements of (B 1 ) :P will be called the cut set vectors of P .
Theorem 2 ((B 1 ) :P ). For any partition P of a connected graph G such that the resulting subgraphs G 1 and G 2 are connected, the cut set subspace (B 1 ) :P ⊆ B 1 is effectively an (|E P |, 1) group code over A, whose nonzero elements have support E P .
Proof : By Theorem 1 applied to G 1 , the set (Z 0 ) 1 of vertex vectors x 1 ∈ (C 0 ) 1 such that M 1 x 1 = 0 is the repetition code (C = ) 1 ⊆ (C 0 ) 1 , and similarly for (Z 0 ) 2 . Thus (B 1 ) :P is precisely the image of the two-dimensional subspace (C = ) 1 × (C = ) 2 ⊆ C 0 under the coboundary operator d. The kernel of this map is still the one-dimensional repetition code Z 0 = ker d, so its image (B 1 ) :P must be one-dimensional, by the fundamental theorem of homomorphisms.
For example, in our example graph G, the edges E P = {e 3 , e 4 , e 5 } form a cut set corresponding to the partition P = {v 1 , v 2 , v 3 } ⊔ {v 4 , v 5 } of V , as illustrated in Figure 5. Given a vertex vector x = (a1 1 , b1 2 ) that has the constant value a on G 1 and b on G 2 , the coboundary operator d produces an edge vector d(x) = (y 1 , y P , y 2 ) that is all-zero on G 1 and G 2 , but equal to either a − b or b − a (depending on the edge orientation) on the cut set E P . Figure 5 illustrates a typical such I/O pair.
We now find a set of |V | − 1 fundamental cut sets E P such that the corresponding onedimensional cut set subspaces (B 1 ) :P generate the (|V | − 1)-dimensional space B 1 ; i.e., we find a "basis" for Z 1 .
We start with any spanning tree T = (V, E T ) of G, where |E T | = |V | − 1. Since T is a tree, every edge e ∈ E T is a cut set of T that partitions the vertex set V of T into two subsets, say V 1 (e) and V 2 (e), such that the resulting subgraphs T 1 and T 2 are each connected.
The cut set E P (e) of G that corresponds to the same partition P (e) of the vertex set V of G will be defined as our eth fundamental cut set of G. Notice that the resulting subgraphs G 1 and G 2 are connected, because T 1 and T 2 are connected.
The cut set E P (e) must include e, but cannot include any other edges in E T , since their ends are either both in V 1 (e) or both in V 2 (e). Thus E P (e) ⊆ {e} ∪ ET .
For example, for our example graph G, deleting the β 1 (G) = 2 edges e 3 and e 5 yields a spanning tree T with ET = {e 3 , e 5 }. The respective cut sets in , (e 2 , e 5 ), (e 4 , e 3 , e 5 ), and (e 6 , e 3 ), as shown in Figure 6. The |V | − 1 corresponding cut set subspaces {(B 1 ) :P (e) , e ∈ E T } are all independent, since their supports are completely disjoint on E T . Since B 1 is (|V | − 1)-dimensional, it follows that every element of B 1 is a unique linear combination of elements of {(B 1 ) :P (e) , e ∈ E T }; i.e., any set of generators of these |V | − 1 subspaces is a "basis" for B 1 (where the quotes may be removed in the field case). The coboundary space B 1 is therefore sometimes called the "cut space" of G [4].

Input/output realizations
We have seen that Z 0 and B 1 are systematic (n, k) group codes, and we have identified their information sets. We will now construct I/O realizations with these information sets. Moreover, in order to obtain I/O realizations in which every edge may be labeled with a cause-and-effect arrow, we first analyze the unobservability (generator redundancy) and uncontrollability (constraint redundancy) properties of our previous realizations, and eliminate the corresponding redundancies.
As we have already seen, Z 0 = ker d is a (|V |, 1) repetition code over A, so the set {v} comprising any single vertex v ∈ V may be taken as an information set, and then the remaining vertices comprise the corresponding check set.
However, we can see that specifying an information set does not suffice to determine cause-andeffect relationships on the internal edges. The fundamental reason is that the realization of Z 0 in Figure 3 contains β 1 (G) = 2 redundant edge constraints. Indeed, it is easy to see that it would suffice to propagate the value of any single input vertex variable through a spanning tree T of G in order to generate all other output vertex variables correctly; moreover, in such a realization every edge in E T would have a definite direction, namely the direction "away" from the input vertex. Such a nonredundant realization of Z 0 is illustrated in Figure 7, where we choose the information set {v 1 } and E T = {e 1 , e 2 , e 4 , e 6 }.
The realization of Figure 3 thus has β 1 (G) = 2 "degrees of redundancy." This kind of constraint redundancy is called uncontrollability in [7,8]. More precisely, in [8] "uncontrollable" is defined as "having dependent constraints," which in this case are the β 1 (G) = 2 redundant edge constraints.
Next, we will develop an I/O realization for the coboundary space B 1 ⊆ A E . We have seen that B 1 is a systematic (|E|, |V | − 1) group code over A, and that E T ⊆ E is an information set for any spanning tree T of G.
However, we again observe that specifying an information set for the realization of B 1 in Figure  4 does not suffice to determine cause-and-effect relationships on the internal edges. In this case, the basic reason is that this realization has β 0 (G) = 1 internal degree of freedom corresponding to the unobservable behavior B u of this realization, namely the internal behavior when the external variables are fixed to zero. This kind of redundancy is called unobservability in [7,8]. (Alternatively, "unobservable" means "having redundant generators.") For the realization of B 1 in Figure 4, the unobservable behavior B u ⊆ C 1 is the behavior of the realization shown in Figure 8. This behavior is evidently the same as the internal behavior of the (observable) realization of Z 0 = ker d in Figure 3, since both may be obtained from the realization of W 01 in Figure  Since the unobservable behavior B u of Figure 4 is a repetition code, it follows that adding the same element of A to every vertex value does not change the output configuration in B 1 . (In physics, this kind of unobservability is sometimes called "global symmetry.") To obtain an observable realization of B 1 , we may therefore fix any internal vertex variable in Figure 4 to zero, thus breaking the global symmetry. We illustrate this in Figure 9, where we have chosen E T = {e 1 , e 2 , e 4 , e 6 } as the information set, and fixed x 1 = 0. Such an I/O realization could be used to simulate B 1 , by letting {y 1 , y 2 , y 4 , y 6 } run through all |A| 4 possible configurations. Figure 9: I/O realization of B 1 = im d, fixing x 1 = 0, and using {y 1 , y 2 , y 4 , y 6 } as information set.

Elements of duality theory
We now introduce some elementary duality theory for both the group and field cases. (See the Appendix for more on group duality theory, focussing on Fourier transforms over groups. ) We stipulate that A must have a well-defined dual groupÂ, for which the inner product â, a is well defined for allâ ∈Â, a ∈ A. If A is a field F, thenÂ may also be taken as F; if A is Z q , then A may also be taken as Z q ; more generally, if A is a finite abelian group, then A has a well-defined dual groupÂ (called its character group) that is isomorphic to A.
Given a coordinate index set I, the dual group to A I is thenÂ I , with the inner product between a ∈Â I and a ∈ A I defined in standard coordinatewise fashion: â, a = i∈I â i , a i . Two vectorŝ a ∈Â I and a ∈ A I are said to be orthogonal if â, a = 0. The dual code (or orthogonal code) C ⊥ to a group code C ⊆ A I is the set of allâ ∈Â I that are orthogonal to all a ∈ C.
Given a group code C ⊆ A I and an index subset J ⊆ I with complementJ = I \ J , the projection of C onto J is defined as C |J = {a J ∈ A J | ∃(a J , aJ ) ∈ C}, and the cross-section of C on J is defined as C :J = {a J ∈ A J | (a J , 0J ) ∈ C}. If C ⊥ is the dual code to C, then by projection/cross-section duality [5], (C |J ) ⊥ = (C ⊥ ) :J and (C : Given a homomorphism ϕ : A I → A J , its adjoint homomorphism is defined as the unique homomorphismφ :Â J →Â I such that φ(â), a = â, ϕ(a) for allâ ∈Â J , a ∈ A I . We define the I/O code of ϕ as W = {(a, ϕ(a)) ∈ A I × A J | a ∈ A I }, and its dual I/O code aŝ Because the inner product is defined coordinatewise, the inner product between (−φ(â),â) ∈Ŵ and (a, ϕ(a)) ∈ W is − φ(â), a + â, ϕ(a) = 0 for all a ∈Â J , a ∈ A I , by the definition ofφ. Therefore W andŴ are orthogonal. Indeed, they are dual codes, since dimŴ + dim W = |J | + |I|.
(c) The cross-section W : Thus, by projection/cross-section duality, W :I and (W ⊥ ) |I are dual codes.
In view of the I/O map lemma for systematic (n, k) group codes, we thus have the following generalization of well-known results for the field case: Theorem 3 (dual systematic group codes). If C ⊆ A I is a systematic (n, k) group code over A, then its dual code C ⊥ ⊆Â I is a systematic (n, n − k) group code over the dual groupÂ. Moreover, the information sets of C ⊥ are the check sets of C, and vice versa.
Proof : By the I/O map lemma, if C is a systematic (n, k) group code with information set J ⊆ I, then there exists a homomorphism ϕ C : group code overÂ with an information set J that is equal to the complement of the information set J of C.
For example, if C = ⊂ A I is an (n, 1) repetition code over A, then its dual code (C = ) ⊥ is the (n, n − 1) zero-sum code C + ⊂Â I . The information sets of C are the singleton sets {{i}, i ∈ I}, whereas the information sets of C ⊥ are the complementary sets {I \ {i}, i ∈ I}.

Duality in elementary algebraic topology
In algebraic topology, for historical reasons, the dual space to the space C 0 = A V of 0-cochains is called the space of 0-chains, denoted by C 0 =Â V . Similarly, the dualÂ E to the space C 1 = A E of 1-cochains is called the space of 1-chains, denoted by C 1 =Â E .
In our setting, C 0 will be the set of row vectorsx overÂ indexed by V , and C 1 the set of row vectorsŷ overÂ indexed by E, with inner products defined in standard componentwise fashion; e.g., for We callx a dual vertex vector andŷ a dual edge vector.
The boundary operator ∂ : It follows that: 2 Lemma. The boundary operator ∂ : C 1 → C 0 is the adjoint homomorphismd to the coboundary operator d : By the adjoint homomorphism lemma, this implies that the kernel of ∂, called the zero-boundary space Z 1 = ker ∂ ⊆ C 1 , is the dual code (B 1 ) ⊥ to the image B 1 = im d of d; and conversely the image of ∂, called the boundary space B 0 = im ∂ ⊆ C 0 , is the dual code (Z 0 ) ⊥ to the kernel Z 0 = ker d of d. Therefore we have: Proof. (a) By Theorem 1, Z 0 is the (|V |, 1) repetition code over A, so its dual code B 0 is the (|V |, |V | − 1) zero-sum code overÂ.

Dual normal realizations
We will now construct normal realizations of the boundary space B 0 = im ∂ and the zero-boundary space Z 1 = ker ∂ of G as dual realizations to our earlier realizations of the zero-coboundary space Z 0 = (B 0 ) ⊥ and the coboundary space In general, the dual realization to an elementary normal realization is obtained as follows: • The variable alphabet A is replaced by its dual alphabetÂ; • Repetition constraints ( = ) are replaced by zero-sum constraints ( + ), and vice versa; • Edges ( ) are replaced by inverting edges ( • ), and vice versa.
By the normal realization duality theorem [5], if the external behavior of the original normal realization is C, then the external behavior of the dual normal realization is C ⊥ . (If A is a finite abelian group, then this theorem is a corollary to the normal factor graph duality theorem; see Appendix.) We start with the dual I/O behavior W 10 = {(−ŷM,ŷ) |ŷ ∈ C 1 } of the boundary operator ∂, which by the adjoint homomorphism lemma is the dual code to the I/O behavior W 01 = {(x, xM ) | x ∈ C 0 } of the coboundary operator d; i.e., W 10 = (W 01 ) ⊥ . Thus W 10 is a systematic (|V |+|E|, |E|) group code overÂ with information set E.
We may thus obtain an elementary normal realization of W 10 by dualizing our earlier realization of W 01 in Figure 2, which results in the realization of Figure 10. Again, we have included arrows on all edges to indicate cause-and-effect relationships; note that all arrows are now reversed. In Figure 10, a setŷ = {ŷ e , e ∈ E} of |E| external input variables is associated with the edges e ∈ E of G. Each edge variableŷ e is replicated twice via a repetition constraint of degree 3. Each replica is passed on to the zero-sum constraint associated with one of the two vertices h(e), t(e), through a sign inverter if v = t(e), thus makingŷ e M ev the input to this zero-sum constraint. At each vertex v ∈ V of G, the zero-sum constraint on all these incident variables plus an output variablex v enforces the constraintx v = −(ŷM ) v ; thusx = −ŷM , as desired.
Again, to get a realization of the boundary space B 0 = im ∂ = {yM | y ∈ A E }, we may simply remove the external variablesŷ e in Figure 10, while leaving the two internal replica variables representing ±ŷ e . Since = • = • , we may simply use the latter realization for each edge. Thus we obtain the simple realization of B 0 shown in Figure 11. (Strictly, this realization realizes Similarly, to get a realization of the zero-boundary space Z 1 = ker ∂ = (B 1 ) ⊥ , we may either zero the external vertex variablesx v in Figure 10, or else dualize the realization of B 1 in Figure 4. By either method, we obtain the realization of Z 1 shown in Figure 12.

Simple paths and cycles
We will now show that Z 1 may be regarded as the space generated by a certain set of vectors representing cycles. Historically, this seems to have been the starting point of algebraic topology. In elementary graph theory, a simple path in G, denoted by p = (p 1 , . . . , p n ), consists of n edges e or reverse edges −e such that no intermediate vertex is visited more than once, and h(p j ) = t(p j+1 ), 1 ≤ j ≤ n − 1. The head vertex of p is h(p) = h(p n ), and its tail vertex is t(p) = t(p 1 ). A cycle is a simple path p that is closed; i.e., such that h(p) = t(p).
For a simple path p and anyâ ∈Â, we define a corresponding {0, ±â}-valued representative edge vectorŷ(p) ∈Â E such thatŷ e (p) =â if edge e is in p,ŷ e (p) = −â if reverse edge −e is in p, andŷ e (p) = 0 otherwise. For example, if p = (±e) is a simple path of length n = 1 consisting of a single edge ±e, thenŷ(±e) = ±âδ e , where δ e denotes the elementary edge vector with a single nonzero element 1 in its eth coordinate position.
The boundary of a simple nonclosed path p is defined as the pair b(p) = (t(p), h(p)). For a simple nonclosed path p and anyâ ∈Â, we may define a corresponding {0, ±â}-valued representative boundary vectorx Notice that ifŷ(p) is a representative edge vector for a simple nonclosed path p, then ∂(ŷ(p)) = y(p)M is a representative boundary vectorx(p) for p. The proof is that every vertex in p other than h(p) and t(p) occurs in p twice, once as a head vertex and once as a tail vertex, so their contributions to the boundary vectorŷ(p)M cancel. The vertex t(p) appears once as a tail vertex, so its contribution to the boundary vector is −âδ t(p) , and the vertex h(p) appears once as a head vertex, so its contribution to the boundary vector isâδ h(p) ; thusŷ(p)M =â(δ h(p) − δ t(p) ).
From this it follows that in a connected graph G = (V, E), the boundary space B 0 = im ∂ is the (|V |, |V | − 1) zero-sum code C + of length |V | overÂ, as Theorem 4(a) has shown. We next consider the kernel Z 1 of the boundary operator ∂ : C 1 → C 0 . By Theorem 4(b), Z 1 is a systematic (|E|, β 1 (G)) group code overÂ. We will now show that Z 1 has a "basis" consisting of β 1 (G) one-dimensional subcodes of Z 1 .
Notice that ifŷ(p) is a representative edge vector for a simple closed path p-i.e., a cycle-then h(p) = t(p), so ∂(ŷ(p)) = 0. In other words, if p is a cycle, thenŷ(p) is in the kernel Z 1 = ker ∂ of the boundary operator ∂. Such edge vectors will be called elementary zero-boundary edge vectors. For a given cycle p, the set of all such elementary zero-boundary edge vectors evidently forms a 1-dimensional zero-boundary subspace Z 1 (p) ⊆ Z 1 , whose support E(p) consists of the edges of p: Theorem 5 (Z 1 (p)). For any cycle p of a connected graph G, the zero-boundary subspace Z 1 (p) ⊆ Z 1 is a systematic (|E(p)|, 1) group code overÂ, whose nonzero elements have support E(p).
We now find a set of β 1 (G) cycles p e such that the corresponding one-dimensional zero-boundary subspaces Z 1 (p e ) generate the β 1 (G)-dimensional space Z 1 . We start with any spanning tree T = (V, E T ) of G and its complementT , where |ET | = |E| − |V | + 1 = β 1 (G). For each edge e ∈ ET , there exists a cycle of G comprising e and the path connecting its final vertex to its initial vertex in T , which we will call the fundamental cycle p e . Since the support E(p e ) of p e is a subset of {e} ∪ E T , it follows that the β 1 (G) corresponding one-dimensional zero-boundary subspaces Z 1 (p e ) are independent, since their supports are completely disjoint on ET .
For example, for our example graph G, deleting the β 1 (G) = 2 edges e 3 and e 5 yields a spanning tree T . Since Z 1 is β 1 (G)-dimensional, it follows that every element of Z 1 is a unique linear combination of elements of {Z 1 (p e ), e ∈ ET }; i.e., Z 1 is the direct sum of these β 1 (G) one-dimensional subspaces. The zero-boundary space Z 1 is therefore often called the "cycle space" of G.
We said earlier that β 1 (G) measures the number of independent cycles in G. This development makes this statement precise algebraically. Using a spanning tree T of G, we may identify β 1 (G) fundamental cycles p e , e ∈ ET , such that the corresponding one-dimensional zero-boundary subspaces Z 1 (p e ) generate the zero-boundary ("cycle") space Z 1 . For any other cycle p, the correspondinĝ y(p) is in Z 1 , and therefore must be a linear combination of {ŷ(p e ) | e ∈ ET }. For example, there is one other cycle in G, which is a linear combination of the two cycles shown in Figure 14.

Dual input/output realizations
As we have seen, the dual of an I/O realization is an I/O realization of the dual code with the complementary information set. For example, the dual to the I/O realization of Z 0 in Figure 7 is the dual I/O realization of the dual zero-sum code B 0 = (Z 0 ) ⊥ in Figure 15. Alternatively, to obtain this I/O realization, we could have started with the realization of B 0 in Figure 11. The unobservable behavior B u of this realization, shown in Figure 16, has dimension dim B u = β 1 (G) = 2; i.e., there are β 1 (G) = 2 internal degrees of freedom, corresponding to cycles in Z 1 = ker ∂ that do not affect the vertex vectorx (sometimes called "local symmetries"). It is shown in [7,8] that if a realization has dim B u "degrees of unobservability," then its dual realization has dim B u "degrees of uncontrollability," Thus the fact that the realization of B 0 in Figure 11 has β 1 (G) = 2 degrees of unobservability alternatively follows from the fact that the realization of Z 0 in Figure 3 has β 1 (G) = 2 degrees of uncontrollability. (However, whenever we have access to both a realization and its dual, as we do here, it is usually easiest to determine the controllability properties of a realization from the observability properties of its dual.) Finally, the dual to the I/O realization of B 1 in Figure 9 is a dual I/O realization of the dual code Z 1 = ker ∂, which is a systematic (|E|, β 1 (G)) group code overÂ, with the complementary information set E G\T , as shown in Figure 17.
Alternatively, we could have started with the realization of Z 1 in Figure 12. As we have just discussed, since this realization is the dual to the unobservable realization of B 1 in Figure 4 with dim B u = 1, it must have one "degree of uncontrollability." The reader may verify that the realization of Figure 12 continues to function correctly if any single zero-sum constraint ( + ) is removed. For example, Figure 17 is Figure 12 with the top left constraint removed.
We summarize the observability and controllability properties of the realizations of Z 0 , B 1 , Z 1 and B 0 in Figures 3, 4, 12 and 11 as follows: Fig. 4 no Fig. 8 yes Fig. 11 no Fig. 16 yes {0}

Homology spaces
In algebraic topology, homology spaces are quotient spaces (resp. quotient groups) whose dimensions (resp. "free ranks") are topological invariants of complexes. We will not delve deeply into this topic, but for future reference we give the homology spaces for the elementary one-dimensional complexes that we have studied in this section, and we exhibit nice dual realizations for them. The zeroth cohomology space of a graph G = (V, E) is defined as H 0 = Z 0 . We have seen that if G is connected, then dim Z 0 = 1, so dim H 0 = 1 for all connected graphs.
The zeroth homology space of G is defined as the quotient space H 0 = C 0 /B 0 . Since B 0 = (H 0 ) ⊥ , H 0 is the dual space to H 0 , and thus has the same dimension, namely dim H 0 = 1, again for all connected graphs.
More generally, it is easy to see that if G is not connected, but rather consists of β 0 (G) > 1 connected components, then H 0 = Z 0 consists of the direct sum of β 0 (G) independent repetition codes, one defined on each of the β 0 (G) components of G (see discussion under Figure 3). Thus in general dim H 0 = β 0 (G). Dually, B 0 = (Z 0 ) ⊥ consists of the direct sum of β 0 (G) independent zerosum codes, one defined on each of the β 0 (G) components of G, so in general dim B 0 = |V | − β 0 (G), and dim H 0 = β 0 (G).
In a 1-dimensional complex, the first homology space of G is defined as H 1 = Z 1 . We have seen that if G is connected, then dim Z 1 = β 1 (G), so dim H 1 = β 1 (G) for all connected graphs. Also, the first cohomology space of G is defined as H 1 = C 1 /B 1 . Since B 1 = (Z 1 ) ⊥ , H 1 is the dual space to H 1 , and thus has the same dimension, namely dim H 1 = β 1 (G), for all connected graphs.
More generally, it is easy to see that if G consists of β 0 (G) > 1 connected components, then H 1 = Z 1 consists of the direct sum of β 0 (G) independent codes of dimensions β 1 (G i ), one defined on each of the β 0 (G) components Dually, B 1 = (Z 1 ) ⊥ consists of the direct sum of β 0 (G) independent codes of dimensions |E i |−β 1 (G i ), one defined on each component G i of G, so in general dim B 1 = |E| − β 1 (G), and dim H 1 = β 1 (G).
The properties of these homology spaces are most succinctly captured by the unobservable behaviors B u of Figures 8 and 16, respectively, which we now relabel asH 0 andH 1 , and recapitulate in Figure 18. We note that these realizations are each others' duals, and thatH 0 ∼ = H 0 ∼ = H 0 and It seems to us that the simple, elegant and dual realizations of Figure 18 represent the Platonic essences of the zeroth cohomology space H 0 and the first homology space H 1 , respectively.

Ising-type models
We will now show how to extend these graphical models of various algebraic topology spaces to realize partition functions of Ising and related models of statistical physics.

Ising and Ising-type models
In statistical physics, an Ising model is defined as follows.
• Particles are associated with the vertex set V of a connected graph G = (V, E).
• Each particle may be in one of two states (often called "spins"). The state space is A = Z 2 , and the state of the particle at the vth vertex is denoted by where J e is the interaction strength for edge e. In other words, • The probability of a configuration x ∈ A V is then given by the Boltzmann distribution where β is the inverse temperature, and the partition function Z is 4 Evidently the probability of a configuration x ∈ A V depends only on the corresponding edge configuration y(x) = d(x) = M x ∈ A E . Thus where y e (x) = M e x = x h(e) − x t(e) . Moreover, where B 1 = im d, and |A| = | ker d| is the number of configurations in A V that map to each y ∈ B 1 .
More generally, we will define an Ising-type model as a statistical model based on a graph G = (V, E) in which • Particles are associated with the vertex set V and have states x v ∈ A, where the state space A may be any finite abelian group; • The probability of a configuration x ∈ A V depends only on the corresponding edge configuration y(x) = d(x) = M x ∈ A E , and is given by For example, a Potts model is an Ising-type model in which A = Z q for q > 2, and f e (0) = exp βJ e , while f e (y e ) = 1 for y e = 0. Much broader generalizations are evidently possible, but we do not know to what extent such generalizations have been studied in statistical physics.
The usual object of study is the partition function Z as a function of inverse temperature β. In an Ising model, as β → 0 (i.e., in the high-temperature limit), the weight w e (x) = exp(βJ e (−1) ye(x) ) tends to 1, independent of y e (x), so Z → |A| |V | and p(x) → |A| −|V | for all x ∈ A V ; i.e., in physical terms, the interaction between neighboring vertices disappears. On the other hand, as β → ∞ (i.e., in the low-temperature limit), and if J e > 0 (the ferromagnetic case), then the weight w e (x) is large if y e = 0 (x h(e) = x t(e) ) and small if y e = 0 (x h(e) = x t(e) ), which tends to force these two values to agree. If β → ∞ and if J e < 0 (the antiferromagnetic case), then the weight w e (x) becomes small if y e = 0 (x h(e) = x t(e) ) and large if y e = 0 (x h(e) = x t(e) ),which tends to force these two values to disagree.
Two partition functions Z and αZ, α > 0, are said to be equivalent up to scale, written Z ∝ αZ. Since scaling of p(x) and Z by the same factor α does not change the Boltzmann distribution, it is often satisfactory to compute a function αZ that is equivalent to Z up to scale.

From normal realizations to edge-weighted NFGs
Following [18,2], we will now show how the partition function of an Ising-type model may be represented by a normal factor graph (NFG), and in particular by an edge-weighted NFG.
Normal factor graphs [13,1,9] build on the concepts of normal realizations [5] and factor graphs [12]. NFGs are used to model functions that can be represented as real-or complex-valued sums of products, such as partition functions. (For more on partition functions of NFGs, see [9].) The semantics of NFGs are similar to those of normal realizations. Again, a normal factor graph is a graphical model based on a graph G = (V, E, H), in which the edges e ∈ E represent internal variables s e ∈ A e , and the half-edges h ∈ H represent external variables a h ∈ A h . However, the vertices v ∈ V now represent complex-valued functions f v (s v , a v ) of the values (s v , a v ) of all variables that correspond to the edges and half-edges that are incident on vertex v.
We will assume that all variable alphabets are finite abelian groups. The internal and external configuration spaces are then A E = E A e and A H = H A h , respectively. The NFG then represents the sum of products which is called the partition function (or "exterior function" [1], or "partition sum" [2]) of the NFG. NFGs generalize normal realizations in the following sense. Given a normal realization based on G = (V, E, H), if each vertex constraint code C v is replaced by its indicator function δ Cv (i.e., If all constraint codes C v are group codes, then the behavior and the external behavior are group codes B ⊆ A E × A H and C ⊆ A H , respectively. Moreover, if B is finite, then by the group property the number of elements of B that map to each element of C is the same, namely is the unobservable behavior of the realization. Therefore Z(a) = |B u |δ C (a). In summary: Lemma (Normal realization as an NFG). If all alphabets are finite groups, then a normal realization with external behavior C and unobservable behavior B u may be interpreted as a normal factor graph whose partition function is Z(a) = |B u |δ C (a).
Next, we extend this definition as follows. An edge-weighted NFG (EWNFG) consists of a normal realization of a group code C as above, in which all internal functions {f v , v ∈ V } are indicator functions δ Cv of group codes C v , plus a set {f h , h ∈ H} of edge-weighting functions f h attached to each external half-edge h ∈ H of the normal realization. The resulting NFG has no external variables, and its partition function is evidently the constant where B u is the unobservable behavior of the normal realization as above, and f (a) = H f h (a h ).
As [2,18] have observed, the partition functions of Ising-type models are naturally represented by edge-weighted NFGs. In particular, the partition function of an Ising-type model may be represented as an EWNFG based on a normal realization of the coboundary space B 1 = im d of a graph G = (V, E) over the finite group alphabet A, and an appropriate set of edge weight functions {f e (y e ), e ∈ E}. The partition function of such a model is thus where |B u | is the size of the unobservable behavior of the normal realization.
For example, Figure 19 shows the EWNFGs derived from the normal realizations of B 1 = im d of Figures 4 and 9, respectively. We recall that Figure 9 is an I/O realization using the information set y T = {y 1 , y 2 , y 4 , y 6 }.  We further recall that for the normal realization underlying Figure 19(a), we have |B u | = |A|, whereas for that of Figure 19(b), |B u | = 1. Thus the partition function of the EWNFG of Figure  19(a) is |A| y∈B 1 f (y) = Z, whereas for Figure 19(b), it is y∈B 1 f (y) = Z/|A|. The two EWNFGs are thus equivalent up to a scale factor of |A|.
Notice that such EWNFGs alternatively model the communications scenario in which the possible transmitted sequences are codewords y from the linear code B 1 , and the relative (unscaled) likelihood of each possible symbol y e ∈ A is f e (y e ). Indeed, it was the recognition of this analogy by Sourlas [20] in 1989 that led to the first connections between coding theory and the Ising models of statistical physics.
The dimension of B 1 is dim B 1 = |E| − β 1 (G) = |V | − 1, the number of edges in a spanning tree T of G. Thus Z may be computed as in [16] by choosing a spanning tree T ⊆ G, letting y T run freely through A E T , extending each y T to the corresponding y ∈ B 1 via a linear transformation, computing f e (y) = e∈E f e (y e ), summing these contributions, and finally multiplying by |A|. If we use an I/O realization of B 1 as in Figure 9, then the extension of each y T to the corresponding y ∈ B 1 occurs "automatically" by propagation through the I/O realization.
Molkaraie et al. [14,15] have proposed an importance sampling algorithm to estimate the partition function Z, using the information set y T . The idea is to choose a series of samples y T ∈ A E T according to an auxiliary probability distribution p(y T ), extend each such y T to the corresponding y ∈ B 1 , and then compute f e (y) for each sample. For the auxiliary probability distribution, they propose p(y T ) = f e (y T )/Z T , where Again, an I/O realization of B 1 could be used to compute this extension of y T to y "automatically."

Dual realizations
Molkaraie and Loeliger [18] observed that it is sometimes easier to compute the Fourier transform Z of Z than Z itself. Since Z is a constant function (i.e., not a function of any variables other than the inverse temperature β),Ẑ is actually equal to Z.
By the normal factor graph duality theorem [1,6,9], the dual of an NFG whose partition function is Z is an NFG whose partition function is the Fourier transformẐ of Z, up to scale. In the Appendix, we give the simplest proof we know (using an easy "edge replacement lemma") of this very powerful and general result.
The dual of an edge-weighted NFG based on a normal realization of some group or linear code C and edge-weighting functions {f e , e ∈ E} is evidently an edge-weighted NFG based on the dual normal realization with the dual (Fourier-transformed) edge weighting functions {f e , e ∈ E}.
In the Appendix, we consider interpreting a dual normal realization as an NFG. Considering all relevant scale factors, we show that Lemma (Dual normal realization as an NFG). If all alphabets are finite abelian groups, then the dual of a normal realization with behavior B and external behavior C may be interpreted as a dual NFG with partition functionẐ where As discussed in the Appendix, this lemma and the corresponding primal lemma imply that: (a) The external behavior of the dual normal realization is C ⊥ . Thus, when all alphabets are finite abelian groups, we obtain the normal realization duality theorem as a corollary.
(b) The size of the unobservable behavior of the dual normal realization is Thus the dual NR is observable and the NR is controllable if and only if |B||A E ||C V | −1 = 1. Intriguingly, this yields the controllability test of [8] for the finite abelian group case.
For Ising-type models, dualization of a normal realization of B 1 = im d as in Figure 4 or 9 gives a normal realization of Z 1 = ker ∂ = (B 1 ) ⊥ as in Figure 12 or Figure 17. Correspondingly, dualization of the corresponding edge-weighted NFGs in Figure 19 yields the dual EWNFGs shown in Figure 20.  We recall that Figure 17 is an I/O realization using the information set y G\T = {ŷ 3 ,ŷ 5 }. The dual partition function may be computed or sampled like the primal function, by letting y G\T range freely on the complement G \ T of any spanning tree T of G. Thus if we choose the same tree T for the primal and dual realizations, then the two information sets are complements of each other.
In the Appendix, we compute the scale factor for dual Ising-type models based on a graph G = (V, E). If the partition function of the primal edge-weighted NFG as in Figure 19(a) is Z, then the partition function of the dual edge-weighted NFG as in Figure 20(a) iŝ (This result was derived previously by Molkaraie [16].) 5 Dualization makes hard constraints into soft constraints, and vice versa. For example, an interaction weight function f e (y e ) represents a strict (equality) constraint if f e (y e ) ∝ δ {0} (y e ), for then only configurations y with y e = 0 contribute to the partition function. On the other hand, f e (y e ) represents no constraint if f e (y e ) ∝ 1 for all y e , for then it makes the same contribution for every configuration y. Since the dual code to {0} is the universe code A, the Fourier transform of a strict-constraint function is a no-constraint function, and vice versa. Similarly, in an Ising-type model, the Fourier transform of a low-temperature interaction weight function f e (y e ) is a hightemperature weight function, and vice versa. For this reason, an expression forẐ is sometimes called a high-temperature expansion of Z. High-temperature constraints are softer than low-temperature constraints, and have fewer long-range correlations, so convergence of Monte Carlo estimates is faster and less random [18].

Example: Single-cycle graph
Following [18], we now give an example of dual realizations of a partition function Z and its Fourier transformẐ on a single-cycle graph. In statistical physics, a single-cycle graph arises in a one-dimensional (1D) Ising-type model with periodic boundary conditions.
A single-cycle graph G of length n has n vertices v i , i ∈ Z n , and n edges e i , i ∈ Z n , such that edge e i connects vertices v i and v i+1 (with index arithmetic in Z n , so e n−1 connects v n−1 and v 0 ). Figure 21 shows an NFG with partition function Z for a 1D Ising-type model of length n over A = Z q with periodic boundary conditions. The realization is based on an image realization of B 1 = im d, which is the (n, n − 1) zero-sum code over Z q .
. . Since Z 0 = ker d is the (n, 1) repetition code over A, every codeword of B 1 = im d is the image of |A| different vertex vectors x+ a1, a ∈ A. Thus, if we like, we may fix any vertex variable to zero, say x 0 = 0, without affecting the partition function, up to a scale factor of |A|. We may also replace each repetition constraint of degree 2 plus its neighboring sign inverter by an inverting edge, since This results in the observable I/O realization of Figure 22, whose underlying graph T , a spanning tree of G, is a cycle-free chain graph. This shows that a 1D Ising-type model defined on T with fixed boundary conditions (i.e., x 0 = x n = 0) has the same partition function (up to a scale factor of |A|) as the same model with periodic boundary conditions (i.e., x 0 = x n ). Figure 22: NFG for 1D Ising-type model with fixed boundary conditions x 0 = x n = 0. Figure 23 shows the dual NFG, whose partition function is (up to scale) the Fourier transformẐ of the partition function Z of Figure 21. The underlying normal realization is a dual I/O realization of Z 1 = ker ∂, the (n, 1) repetition code overÂ. ThusẐ = ŷ∈Â if i (ŷ). Evidently, computinĝ Z is much easier than computing Z. Figure 23: Dual NFG realizing partition functionẐ for 1D Ising-type model.

Ising-type models with an external field
An Ising-type model may be generalized to include an external field as follows [14]. In addition to the interaction energies E e (x v , x v ′ ), there is an external field energy E v (x v ) for each particle v ∈ V . The external field weight function is defined as where β > 0 is again the inverse temperature. The probability of a configuration x ∈ A V is then given by the Boltzmann distribution where the partition function of the model is now defined as This partition function may be realized by starting with a realization of Z as in Figure 19, and attaching to each vertex v ∈ V a function vertex representing the external field weight function g v (x v ), as shown in Figure 24. The resulting EWNFG has no external variables, and evidently realizes the partition function of the model including an external field. Figure 24: EWNFG for partition function of Ising-type model with an external field, based on normal realization of I/O behavior Figure 2.
The normal realization underlying this EWNFG is that of the I/O behavior W 01 = {(x, d(x) | x ∈ C 0 } of the coboundary operator d, as illustrated in Figure 2. This behavior is a systematic (|E| + |V |, |V |) group code over A, for which the vertex set V is an information set.
Consequently, the dual EWNFG is based on the normal realization of the dual I/O behavior W 10 = {(−∂(ŷ),ŷ) |ŷ ∈ C 1 } of the boundary operator ∂, as illustrated in Figure 10. This behavior is a systematic (|E| + |V |, |E|) group code over A, for which the edge set E is an information set.  Figure 10.
The expression forẐ = Z that is given by the dual NFG shown in Figure 25 is called the high-temperature expansion of Z. Explicitly, For the special case of the Ising model (A = Z 2 ) with a constant external field, there are well-known explicit formulas for this high-temperature expansion ofẐ [19,11]. This expression for Z generalizes these high-temperature expansions to general finite abelian group alphabets A and non-constant external fields H v .
However, since |E| = |V | − 1 + β 1 (G), the dual I/O behavior will be higher-dimensional than the primal I/O behavior if β 1 (G) > 1; i.e., if G has more than one cycle. Thus with an external field it will generally be more complicated to computeẐ than to compute Z.

Alternative and hybrid I/O realizations
We see that whereas in the primal domain the presence of an external field adds only one dimension to the realization of Z (the difference between the dimensions of B 1 and W 01 ), in the dual domain it adds |V | − 1 dimensions (the difference between the dimensions of Z 1 and W 10 ). We will now suggest alternative realizations of the partition function Z and its Fourier transformẐ for Ising-type models with an external field, with the objective of simplifying their calculation.
As discussed above, Z is the partition function of an EWNFG based on a normal realization of the I/O behavior W 01 = {(x, d(x) | x ∈ A V } of the coboundary operator d, as illustrated in Figure  2, where W 01 is a linear (|E| + |V |, |V |) code over A.
We have seen that the vertex vector x ∈ A V is an obvious information set for W 01 . However, we will now show that for any v ∈ V and any edge set E T such that T is a spanning tree of G, (x v , y T ) ∈ A {v} × A E T is an information set for W 01 . Moreover, we will give an I/O realization of W 01 based on this information set.
We recall that the projection of W 01 onto the edge configuration space A E is B 1 = im d, which is an (|E|, |E| − β 1 (G)) = (|E|, |V | − 1) systematic group code with information set E T for any spanning tree T ⊆ G. Hence for any (x, y) ∈ W 01 , the edge vector y may be realized by taking y T as the input to an I/O realization of B 1 , such as the realization illustrated in Figure 9; the output is then the unique yT such that y = (y T , yT ) ∈ B 1 . Now we may extend an I/O realization of B 1 such as Figure 9 to obtain a vertex vector x(y T ) as another output, thus obtaining a pair (x(y T ), y) ∈ W 01 . Note that we have shown that a single vertex variable x v in Figure 9 can been fixed to 0; i.e., x v (y T ) = 0, where v ∈ V may be chosen arbitrarily; thus (xv(y T ), y) ∈ (W 01 ) :v . Moreover, the set of all pairs (x, y) ∈ W 01 that have edge vector y is the coset (x + Z 0 , y) of Z 0 × {0} that contains (x, y), where Z 0 = ker d is the (|E|, 1) repetition code over A = Z q .
It follows that W 01 may be generated by the normal realization shown in Figure 26. On the left, a single input vertex variable x v ∈ A {v} generates the unique vertex vector xv(x v ) = (x v , . . . , x v ) ∈ A V \{v} such that (x v , xv(x v )) ∈ Z 0 . On the right, an input edge vector y T ∈ A E T generates the unique edge vector yT (y T ) ∈ A E\E T such that y(y T ) = (y T , yT (y T )) ∈ B 1 , and an associated vertex vector xv(y T ) ∈ A V \{v} such that (x(y T ), y(y T )) ∈ W 01 , where x(y T ) = (0, xv(y T )) ∈ A V . The final output pair is (xv(x v , y T ), yT (y T )), where xv(x v , y T ) = xv(x v ) + xv(y T ), which together with the input pair (x v , y T ) give the unique pair (x, y) ∈ W 01 that is consistent with the inputs For a realization of the dual I/O map W 10 = (W 01 ) ⊥ , we need merely dualize this representation, as shown in Figure 27. On the left, the dual of the repetition code Z 0 is the zero-sum code B 0 . On the right, the dual of the cross-section (W 01 ) :v is the projection (W 10 ) |v , which may be realized by extending the I/O realization of Z 1 = ker ∂ in Figure 17, which usesŷT as an information set, in a dual manner to the extension of Figure 9 discussed above, which involves addingxv as a second information set. Finally, the remainder of the realization is dualized by replacing the zero-sum constraint by an equality constraint, and changing the directions of the arrows. 6 Thus we obtain the realization of Figure 27 These normal realizations may be used to realize partition functions Z andẐ by attaching edge weights. For example, the dual EWNFG of Figure 28 realizes a partition functionẐ by attaching edge weightsĝ(x) andf (ŷ) to components ofx andŷ, respectively. A hybrid alternative that may be attractive because of the simplicity of the repetition code Z 0 is shown in Figure 29. Here, using the edge replacement lemma (see Appendix), the left (vertex) side is realized in the primal domain, and the right (edge) side is realized in the dual domain, with a connection via a Fourier transform function (plus sign inverter) between the (|V |− 1)-dimensional primal and dual vertex vectors xv andxv. Figure 29: Hybrid NFG for Ising-type model.
In this hybrid realization, the left side is 1-dimensional, the right side is β 1 (G)-dimensional, and the two are linked by |V | − 1 edge variables, which require |V | − 1 Fourier transforms over A.

Two-dimensional algebraic topology
We now consider graphs that have well-defined faces. We will primarily consider connected planar graphs with no self-loops and no dangling edges, which is the simplest case.

Two-dimensional complexes
In elementary algebraic topology [3], a graph G = (V, E) plus a set F of faces is called a twodimensional complex G + = (V, E, F ). A face f ∈ F of G + is called a two-dimensional object.
Faces are defined according to the topological space on which G is imagined to be drawn. For instance, a planar graph is one that can be drawn on a plane without any edges crossing. The interior faces of G are then the areas of the plane that are bounded by the edges of G. We will assume that G has no "dangling" degree-1 vertices; 7 then every edge of G bounds either two interior faces of G, if it is an interior edge, or one interior face of G, if it is an exterior edge.
It is easy to see that in general the number of interior faces of a planar graph is |F | = β 1 (G). For example, as a planar graph, our example graph G in Figure 1 has two interior faces, one interior edge, and five exterior edges.
Alternatively, a planar graph G may be considered to be drawn on a sphere; then its "exterior face" is also taken to be a face, and every edge of G bounds precisely two faces of G. In this case, |F | = β 1 (G) + 1 = |E| − |V | + 2. For example, as a planar graph on a sphere, our example graph G has |V | = 5, |E| = 6, and |F | = 3.
In algebraic topology, the vector space C 2 = A F of column vectors over A indexed by F is called the space of 2-cochains of G + . Again, we will call such vectors face vectors, and write them as column vectors z. The dual vector space C 2 is called the space of 2-chains; again, we will call these dual face vectors, write them as row vectorsẑ ∈Â F , and use the standard inner product.
The boundary of a face f is a set E(f ) ⊆ E of directed edges. Each face f ∈ F is assumed to have an orientation, perhaps arbitrary; then each edge e ∈ E(f ) is given a sign α f e = 1 if the face and edge orientations are aligned, or α f e = −1 otherwise. If e / ∈ E(f ), then α f e = 0. The {0, ±1}-valued matrix M 2 = {α f e | f ∈ F, e ∈ E} will be called the second connection matrix of G.
Since an edge of G + is incident on two faces if it is an interior edge or on one face if it is an exterior edge, each of the |E| columns of M 2 has 1 or 2 nonzero values. The number of nonzero values in the f th row is the degree δ f of the face f , namely the number of edges bounding f .
The second boundary operator is defined as the homomorphism ∂ 2 : C 2 → C 1 ,ẑ →ẑM 2 ; i.e., the map whose matrix is the second connection matrix M 2 of G. Its kernel Z 2 = ker ∂ 2 is called the second zero-boundary space of G + , and its image B 1 = im ∂ 2 is the second boundary space of G + . For example, our example graph G of Figure 1 may be taken as a planar graph G + drawn on a plane, with two interior faces. If each face is given a clockwise orientation, then its second connection matrix is Note that only one edge is an interior edge, and that Z 2 = ker ∂ 2 is trivial; i.e., dim Z 2 = 0, for this graph and for planar graphs in general. Thus dim B 1 = 2. In general, dim B 1 = |F | = β 1 (G). However, if we consider our example graph to be drawn on a sphere, then G + has three faces, and all edges become interior edges. If the "exterior face" is given a counterclockwise orientation, Since all edges are now interior, each column of M 2 now has precisely 2 nonzero values ±1. Moreover, since the sum of the three rows is 0 ∈ C 1 , the second boundary operator ∂ 2 now has a nontrivial kernel Z 2 of dimension 1. Therefore dim Z 2 = 1 in this case and, by similar arguments, for general planar graphs. However, the image B 1 remains unchanged, regardless of whether we take G + as a graph on a plane or on a sphere. Thus its dimension remains dim B 1 = 2 for this example, or dim B 1 = β 1 (G) for general planar graphs.
Notice that the first two rows of M 2 are the edge vectorsŷ(p 1 ),ŷ(p 2 ) corresponding to the two cycles p 1 , p 2 that bound the two interior faces of G + , and therefore are elements of the zeroboundary space Z 1 , the kernel Z 1 of our original first boundary operator ∂ 1 : C 1 → C 0 ,ŷ →ŷM 1 . It follows that B 1 = Z 1 in this example, and, by similar arguments, for planar graphs in general.
Dually, the image of our original first coboundary operator d 1 : C 0 → C 1 , x → M 1 x will continue to be denoted as B 1 , and its kernel as Z 0 . Since d 1 is the adjoint homomorphism to ∂ 1 , B 1 = (Z 1 ) ⊥ and Z 0 = (B 0 ) ⊥ . Similarly, we define the second coboundary operator as the adjoint homomorphism to ∂ 2 -i.e., the operator d 1 : C 1 → C 2 , y → M 2 y. By the adjoint homomorphism lemma, the kernel Z 1 and image B 2 of d 2 then satisfy Z 1 = (B 1 ) ⊥ and B 2 = (Z 2 ) ⊥ .

Homology spaces
In general, it is straightforward to show that in any two-dimensional complex, the second boundary space B 1 is a subspace of the first zero-boundary space Z 1 = ker ∂ 1 , by showing that every row of M 2 is an edge vectorŷ(p) corresponding to a cycle p. Thus for a general two-dimensional complex we have B 1 ⊆ Z 1 . The first homology space is then defined as For a two-dimensional complex G + based on a planar graph G, we have seen that B 1 = Z 1 , so for our example planar graph and in general, we have dim H 1 = 0, whether we take G + as a graph on a plane or on a sphere.
In a general two-dimensional complex, the first cohomology space is defined as H 1 = Z 1 /B 1 = (B 1 ) ⊥ /(Z 1 ) ⊥ , which from linear algebra is the dual space to H 1 = Z 1 /B 1 . Thus for a planar graph dim H 1 = dim H 1 = 0; i.e., the image B 1 of d 1 is equal to the kernel Z 1 of d 2 .
In this context, Z 2 is alternatively called the second homology space H 2 of G + . We have seen that dim Z 2 = 0 if G is a planar graph defined on a plane, but dim Z 2 = 1 if G is defined on a sphere. The second cohomology space is defined as The dimensions of the homology or cohomology spaces H 0 , H 1 , H 2 are thus (1, 0, 0) if G is regarded as a planar graph on a plane, or (1, 0, 1) if G is regarded as a planar graph on a sphere. We see that these dimensions are universal for all planar graphs of these respective types [3]. Figure 30(a) depicts a normal realization of Z 2 = ker ∂ 2 when we view G + as being drawn on a sphere, so there is an exterior face f 0 as well as the two interior faces f 1 , f 2 . The three equality constraints correspond to the face variablesẑ 0 ,ẑ 1 ,ẑ 2 , and the six zero-sum constraints correspond to the edge variablesŷ 1 , . . . ,ŷ 6 , which have all been set to 0 in this kernel realization. One of the two incident face variables to each edge constraint is negated, according to the entries α f e of M 2 . Figure 30: Z 2 = ker ∂ 2 for G + : (a) normal realization; (b) simplified normal realization. Figure 30(b) depicts a simplified realization of Z 2 = ker ∂ 2 . Note the resemblance of this realization to that of Z 0 = ker d 1 in Figure 3 or 7.

Normal realizations
Similarly, Figure 31 depicts the dual realization of B 2 = im d 2 , which resembles that of B 0 = im ∂ 1 in Figure 11 or 15. We will now explain these resemblances.  Geometrically, we may construct this dual graph by putting vertices ofĜ inside each face of G (including the exterior face), and putting edges between two such vertices if and only if the corresponding faces share an edge, as illustrated for our example graph in Figure 32. The similarity of this dual graphĜ to the graphs of Figure 30 and 31 is no accident. For G + = (F, E, V ), the first boundary operator∂ 1 : C 1 → C 2 has matrixM 1 = (M 2 ) T , and thus maps the row vectorŷ ∈ C 1 toẑ =ŷ(M 2 ) T ∈ C 2 . This map is evidently the same up to transposition as that of the second coboundary operator d 2 : C 1 → C 2 of G + , which maps the column vector y ∈ C 1 to z = M 2 y. Similarly,∂ 2 : C 0 → C 1 is the same map up to transposition as d 1 : C 0 → C 1 , and the first and second coboundary operators,d 1 : C 2 → C 1 andd 2 : C 1 → C 0 , are the same up to transposition as ∂ 2 and ∂ 1 , respectively.

Dual graphs
It follows that the boundary and zero-boundary spaces forĜ + are simply the transposes of those for G + : Thus Figure 30 may be seen as realizing either Z 2 = ker ∂ 2 for G + , orẐ 0 = kerd 1 forĜ + . Similarly, Figure 31 may be seen as realizing either B 2 = im d 2 for G + , orB 0 = im∂ 1 forĜ + .
However, for a two-dimensional complex G + based on a planar graph G, we also have Z 1 = B 1 = im d 1 and B 1 = Z 1 = ker ∂ 1 ; therefore we may alternatively realize Z 1 as an image realization based on G as in Figure 4, or B 1 as a kernel realization based on G as in Figure 12. Since G has |E| edges and |V | = |E|−β 1 (G)+1 vertices, whereasĜ has |E| edges and β 1 (G)+1 vertices, the representation based on G (resp.Ĝ) will in general be simpler if β 1 (G) > |E|/2 (resp. β 1 (G) < |E|/2).

Realizations of partition functions for planar graphs
Let G + = (V, E, F ) be a two-dimensional complex based on a connected planar graph G. Then we have seen that the partition function Z(G) of an Ising-type model based on G with interaction weight functions {f e (a) | e ∈ E, a ∈ A} may be represented (up to scale) as the partition function of an EWNFG consisting of a realization of its first coboundary space B 1 = im d 1 with edge weights {f e (a)}. We recall that dim B 1 = |V | − 1 = |E| − β 1 (G).
As we have seen, with a planar graph we have B 1 = Z 1 = ker d 2 . Moreover, Z 1 may be realized asẐ 1 = ker∂ 1 for the dual graphĜ. Hence Z(G) may also be represented (up to scale) by a realization of the first zero-boundary spaceẐ 1 = ker∂ 1 ofĜ with edge weights {f e (a)}.
Furthermore, the Fourier transformẐ(G) of Z(G), which as we have seen is equal to Z(G) up to scale, may be represented (up to scale) by a kernel realization of its first zero-boundary space Z 1 = ker ∂ 1 , with Fourier-transformed edge weights {f e (a)}. We have dim Z 1 = β 1 (G), which can be less than dim B 1 = |V | − 1 = |E| − β 1 (G), as we have seen in Figures 21 and 23. Also, the Fourier transform will in general convert a low-temperature model to a high-temperature model, and vice versa.
If G is a planar graph, then Z 1 = B 1 , and B 1 may be realized asB 1 = imd 1 for the dual grapĥ G. ThusẐ(G) may also be represented (up to scale) by an image realization of the first coboundary spaceB 1 = imd 1 ofĜ, with Fourier-transformed edge weights {f e (a)}.
In summary, these possible representations of Z(G) andẐ(G) are summarized in the table below.
realizes space dimension realization type graph no. vertices edge wts.
Al-Bashabsheh and Vontobel [2] show that the partition function Z(G) of an EWNFG based on a connected planar graph G and edge weights {f e (a)} is equal up to scale to the partition function of an EWNFG based on the dual graphĜ with dual edge weights {f e (a)}. This follows from equating (up to scale) the first and fourth lines of this table.
For example, let G be a single-cycle graph of length N , which is a connected planar graph with |V | = |E| = N and β 1 (G) = 1. Its dual graphĜ thus has |V | = 2 and β 1 (Ĝ) = N − 1. Figure 21 shows a representation of the partition function Z(G) using an image realization of the (N, N − 1) linear code B 1 = im d 1 on the graph G, and Figure 23 shows a representation of its Fourier transformẐ(G) ∝ Z(G) using a kernel realization of the (N, 1) code Z 1 = ker ∂ 1 on G. We now see that Z(G) could alternatively be represented by a kernel realization using the (N, N − 1) codeẐ 1 = ker∂ 1 with edge weights {f e (a)} on the dual graphĜ, which has only 2 vertices, and thatẐ(G) ∝ Z(G) could alternatively be represented by an image realization using the (N, 1) codê Similarly, if we ask for representations of the partition function Z(Ĝ) of an Ising-type model based on the dual graphĜ with the same interaction weight functions {f e (a)}, we find that Z(Ĝ) may be represented (up to scale) using realizations ofB 1 or Z 1 , which are effectively the same (|E|, β 1 (G)) linear code, with edge weights {f e (a)}; and similarly, the Fourier transformẐ(Ĝ) may be represented (up to scale) using realizations ofẐ 1 or B 1 , with Fourier-transformed edge weights {f e (a)}, as summarized in the following table: realizes space dimension realization type graph no. vertices edge wts.

Conclusion
In this paper, we have presented an introduction to elementary algebraic topology using normal realizations, and, following [2,18], we have shown how such realizations may be used for calculating partition functions of Ising-type models. Indeed, using dual realizations and dual graphs, we have given multiple alternative ways of representing such partition functions, summarized in Section 4.5. While Molkaraie et al. [14,15,17,18], have successfully exploited such alternatives in Monte Carlo simulations using importance sampling, much more could be done. In particular, for the case of external fields, the hybrid models suggested in Section 3.6 should be explored further.
Our results are very general; in particular, they apply for any finite abelian group A. Physicists might be interested in exploring Ising-type models with group alphabets more general than Z q .
For the field of codes on graphs, this development suggests exploring graphical models that are inspired more by algebraic topology than by traditional system-theory models (e.g., trellises, tailbiting trellises, kernel and image representations). For example, we have recently found a simple and elegant "2-state" elementary normal realization of the (8,4,4) binary extended Hamming code on a 3-cube. Are there similarly "nice" realizations of more complex codes?

Appendix: The NFG duality theorem
The normal factor graph duality theorem (NFGDT) [1,6,9] is the key duality result for normal factor graphs (NFGs) over finite abelian groups. It shows that the partition function of a dual NFG is equal to the Fourier transform of the partition function of the primal NFG, up to a scale factor which was shown in [1] to be |A E | (see below for terminology and notation).
In this appendix we give the simplest proof we know of this result, and extend it to situations in which the NFG is based on a normal realization [5]; specifically, to NFGs that are based purely on normal realizations, and to edge-weighted NFGs, as discussed in the main text. We see that in both cases adjustments must be made to the scale factor given in [1].

A.1 Fourier transforms over finite abelian groups
Given an additive finite abelian group A, its dual group (or character group)Â may be defined as the set of all homomorphismsâ : A → R/Z, where R/Z is the additive group of real numbers modulo 1. It is well known thatÂ is a finite abelian group that is isomorphic to A. Also, the dual group toÂ is A, where a :Â → R/Z is defined by a(â) =â(a).
If f (a) is any complex-valued function f : A → C, then its Fourier transformf (â) is the complex-valued functionf :Â → C defined bŷ The matrix F = {e 2πi â,a | a ∈ A,â ∈Â} is called the Fourier transform matrix over A. We will regard F as a function of two variables with alphabets A andÂ.
Ifĝ(â) is any complex-valued functionĝ :Â → C, then its inverse Fourier transform g(a) is the complex-valued function g : A → C defined by The matrix F −1 = {|A| −1 e −2πi â,a | a ∈ A,â ∈Â} is called the inverse Fourier transform matrix over A, and will also be regarded as a function of two variables with alphabets A andÂ.
We may verify that F −1 is in fact the inverse of F by using the basic orthogonality relation Given a subgroup C ⊆ A, the orthogonal subgroup C ⊥ ⊆Â is the set {â ∈Â | â, a = 0, ∀a ∈ A}. The orthogonal subgroup to C ⊥ is C, and |C||C ⊥ | = |A|. It is well known, and easy to prove, that the Fourier transform of the indicator function δ C of C is the scaled indicator function |C|δ C ⊥ of C ⊥ . 8 The orthogonality relation follows from the special case in which C = {0} and C ⊥ =Â. 8 The simple and lovely proof goes as follows: (a) obvious forâ ∈ C ⊥ , since â, a = 0 for all a ∈ C; (b) ifâ / ∈ C ⊥ , then â, b = 0 for some b ∈ C; for this b, we have e 2πi â,b ( C e 2πi â,a ) = C e 2πi â,a+b = C e 2πi â,a , since C + b = C; but since e 2πi â,b = 1, this equation can hold only if C e 2πi â,a = 0.
Finally, if f (a) is a function of multiple variables a = {a i , i ∈ I}, then its Fourier transformf (â) is obtained by taking the Fourier transform of each variable separately, since â, a = I â i , a i ; i.e., the Fourier transform is separable. This is illustrated in Figure 34. Figure 34: The Fourier transform is separable.

A.2 Normal factor graphs
A normal factor graph (NFG) is based on a graph G = (V, E, H) consisting of a set of vertices indexed by a vertex index set V , a set of edges indexed by an edge index set E, and a set of half-edges indexed by a half-edge index set H. With each edge e ∈ E we associate an internal (state) variable s e whose alphabet is a finite abelian group denoted by A e , and with each half-edge we associate an external variable a h whose alphabet is a finite abelian group denoted by A h . The internal variable configuration space is defined as the Cartesian product With each vertex v ∈ V we associate a complex-valued function f v (s v , a v ) of the variables corresponding to the edges and half-edges that are incident on vertex v. The partition function (or "exterior function" [1]) of the NFG is then defined as the following function of its external variables: The dual normal factor graph to an NFG as defined above is based on the same graph G = (V, E, H), but with the following replacements: • For each edge e ∈ E, the variable s e ∈ A e is replaced by a dual variableŝ e ∈Â e , whereÂ e denotes the dual group to A e ; • For each half-edge h ∈ H, the variable a h ∈ A h is replaced by a dual variableâ h ∈Â h ; • For each vertex v ∈ V , the function f v (s v , a v ) is replaced by its Fourier transformf v (ŝ v ,â v ); • Finally, each edge is replaced by a sign-inverting edge; i.e., the primal constraint s e = s ′ e on the two variables s e , s ′ e at each end of edge e is replaced by the dual constraintŝ e = −ŝ ′ e . The normal factor graph duality theorem (NFGDT) says that the partition function of the dual NFG is the Fourier transform of the partition fiunction of the primal NFG, up to a scale factor that will be determined shortly. The key to the proof of the NFGDT is the following edge replacement lemma (an example of what is called a "holographic transformation" in [1,6,9]): Lemma (Edge replacement). In any NFG, any edge representing a variable whose alphabet is a finite abelian group A may be replaced by F • F , namely a cascade of F, a sign inverter, and F, plus a disconnected node |A| −1 that contributes a factor of |A| −1 to the partition function, without changing the partition function.
Proof : By the orthogonality relation, |A| −1 Â e 2πi â,a e −2πi â,a ′ = δ aa ′ . This lemma is illustrated by Figure 35. Figure 35: Edge replacement lemma: an edge with alphabet A is equivalent to a cascade of F, a sign inverter, and F, plus a disconnected constant function |A| −1 .
The NFGDT then follows: Theorem (NFG duality). If G = (V, E, H) is a normal factor graph with functions {f v | v ∈ V }, internal variable alphabets {A e | e ∈ E}, and external variable alphabets {A h | h ∈ H} whose partition function is Z(a), then the dual normal factor graph with functions {f v | v ∈ V }, internal variable alphabets {Â e | e ∈ E}, external variable alphabets {Â h | h ∈ H}, and with sign inverters inserted in each edge has partition function |A E |Ẑ(â), whereẐ(â) is the Fourier transform of Z(a), and the scale factor is |A E | = E |A e |.
Proof : If we have an NFG whose partition function is Z(a), then by definition and by separability the Fourier transformẐ(â) is the partition function of the NFG that results when each external half-edge, representing a variable with alphabet A h , h ∈ H, is replaced by F , namely a Fourier transform from A h to the dual external variable alphabetÂ h . By the edge replacement lemma, if we then replace each edge e ∈ E, representing an internal variable with alphabet A e , by F • F then the resulting NFG has Fourier transformẐ(ŷ), times |A E | = E |A e |. Now each function node f v , v ∈ V, in the NFG is surrounded by edge and half-edge segments of the form F . By the definition of the Fourier transform and by separability, each such node and its surrounding Fourier transform functions realizes the Fourier-transformed functionf v .
The scale factor |A E | is thus the product of all internal variable alphabet (state space) sizes |A e |, as in the version of the NFGDT derived in [1].

A.3 Scale factors of code indicator functions
In Section 3.2, we consider interpreting a normal realization as an NFG. Edges and half-edges represent the same internal and external variables, but a constraint code C v is now interpreted as its indicator function δ Cv . If the normal realization has external behavior C and unobservable behavior B u , then we conclude that the partition function of the resulting NFG is as follows: Lemma (Normal realization as an NFG). If all alphabets are finite abelian groups, then a normal realization with external behavior C and unobservable behavior B u may be interpreted as a normal factor graph whose partition function is Z(a) = |B u |δ C (a).
Consequently, if we dualize the NFG resulting from interpreting a group normal realization with external behavior C and unobservable behavior B u as an NFG, then we obtain an NFG whose partition function is δ C ⊥ (â), up to scale factors of: • |B u |, from converting the original NR to the NFG; • |C|, from dualizing δ C (a); • |A E | = E |A e |, from dualizing the edges of the NFG; and • |C V | −1 = V |C v | −1 , from dualizing the vertices of the NFG.
Thus the partition function of the dual NFG iŝ To summarize: Lemma (Dual normal realization as an NFG). The dual of a finite abelian group normal realization with behavior B and external behavior C may be interpreted as a dual NFG with partition function Z(â) = |B||A E ||C V | −1 δ C ⊥ (â), where |A E | = E |A e | and C V = V |C v |. Now if we denote the external behavior of the dual normal realization asĈ and its unobservable behavior asB u , then from the previous lemmaẐ(ŷ) = |B u |δĈ(y). We thus conclude that: (a) The external behaviorĈ of the dual normal realization is C ⊥ . Thus this development proves the normal realization duality theorem when all alphabets are finite abelian groups.
(b) The size |B u | of the unobservable behavior of the dual normal realization is |B||A E ||C V | −1 .
There is an interesting connection between result (b) and the notions of observability and controllability of normal realizations defined in [8]. A finite abelian group normal realization with unobservable behavior B u is observable if and only if |B u | = 1, and |B u | measures its "degree of unobservability." A finite abelian group normal realization whose dual has unobservable behavior B u is controllable if and only if |B u | = 1, and |B u | measures its "degree of uncontrollability." Thus as a further corollary we have the controllability test of [8]: Corollary (Controllability test [8]). Given a finite abelian group normal realization with behavior B, total constraint size |C V | = V |C v |, and total state space size |A E | = E |A e |, the unobservable behaviorB u of the dual normal realization has size |B u | = |B||A E ||C V | −1 ≥ 1. Thus the realization is controllable if and only if |B| = |C V |/|A E |.
This controllability test may be understood as follows. If all edges are removed from the realization, then its behavior is simply C V = V C v , the Cartesian product of the behaviors C v of each of its disconnected nodes. If we reinsert the the edge constraints, each of which is a degree-2 equality constraint between two variables with a common alphabet A e , then each such constraint will reduce the size of the behavior by a factor of |A e |, provided that it is independent of all previous constraints. Thus |B| ≥ |C V |/|A E |, with equality if and only if all constraints are independent.

A.4 Scale factors for edge-weighted NFGs
An edge-weighted NFG consists of an NFG based on a normal realization of a linear or group code C as above, in which all internal functions f v are indicator functions δ Cv of linear or group codes C v , plus edge-weighting functions f h attached to each external half-edge h ∈ H of the normal realization. The resulting NFG has no external variables, and its partition function is the constant where B u is the unobservable behavior of the normal realization as above, and f (a) = H f h (a h ).
As noted above, if C is a linear or group code, then the Fourier transform of δ C (s) is the scaled indicator function |C|δ C ⊥ (ŝ). Thus if we construct the "dual" edge-weighted NFG by replacing every node function δ Cv (s) simply by δ C ⊥ v (ŝ) rather than by |C v |δ C ⊥ v (ŝ), then the partition function will be reduced by a scale factor of |C V | −1 = V |C v | −1 .
Thus we obtain the following corollary of the NFG duality theorem: Corollary (Edge-weighted NFG duality). Given an edge-weighted NFG based on a graph G = (V, E, H) with internal functions {δ Cv | v ∈ V }, internal variable alphabets {A e | e ∈ E}, external variable alphabets {A h | h ∈ H}, and edge-weighting functions {f h | h ∈ H} that realizes a partition function Z = |B u | y∈C f (a), then the "dual edge-weighted NFG" with internal functions where |A E | = E |A e |, |C V | = v |C v |, and |B u | = |B||A E ||C V | −1 .
For example, let us consider an Ising-type model based on a graph G = (V, E), with variable alphabet A and edge-weighting functions {f e (y e ), e ∈ E}; for example, the edge-weighted NFG shown in Figure 19(a). The resulting edge-weighted NFG G = (V G , E G ) actually has |V G | = |V | + 2|E| vertices, consisting of |V | equality functions, |E| zero-sum functions, and |E| edgeweighting functions; |E G | = 3|E| edges, each representing an internal variable with alphabet A; and no half-edges, so its partition function is a constant Z.
If we wish to compute the partition functionẐ of the dual edge-weighted NFG as shown in Figure  19(b) from the partition function Z of the primal edge-weighted NFG, then we need to adjust Z as follows. Since the NFG has |E G | = 3|E| edges, we must multiply by the scale factor |A E | = |A| 3|E| . Since the primal NFG has |V | equality functions and |E| zero-sum weight functions of degree 3 with total dimension 2|E|, we need to divide by |C V | = |A| |V |+2|E| . ThereforeẐ = |A| |E|−|V | Z. 9