The Converse of the Real Orthogonal Holant Theorem
Abstract
The Holant theorem is a powerful tool for studying the computational complexity of counting problems. Due to the great expressiveness of the Holant framework, a converse to the Holant theorem would itself be a very powerful counting indistinguishability theorem. The most general converse does not hold, but we prove the following, still highly general, version: if any two sets of real-valued signatures are Holant-indistinguishable, then they are equivalent up to an orthogonal transformation. This resolves a partially open conjecture of Xia (2010). Consequences of this theorem include the well-known result that homomorphism counts from all graphs determine a graph up to isomorphism, the classical sufficient condition for simultaneous orthogonal similarity of sets of real matrices, and a combinatorial characterization of sets of simultaneosly orthogonally decomposable (odeco) symmetric tensors.
Keywords and phrases:
Holant, Counting Indistinguishability, OdecoCategory:
Track A: Algorithms, Complexity and Games2012 ACM Subject Classification:
Mathematics of computing Combinatorics ; Mathematics of computing Graph theory ; Theory of computation Problems, reductions and completenessAcknowledgements:
The author thanks Jin-Yi Cai for helpful discussions and Ashwin Maran for his suggestion which improved the proof of Theorem 27. The author also thanks Guus Regts for pointing out reference [32].Editors:
Keren Censor-Hillel, Fabrizio Grandoni, Joël Ouaknine, and Gabriele PuppisSeries and Publisher:

1 Introduction
Holant problems
Holant problems were introduced by Cai, Lu, and Xia [12] as a highly expressive framework for studying the computational complexity of counting problems. The problem is defined by a set of signatures, where a signature of arity on domain is a tensor in , or equivalently a function . Given a signature grid – a multigraph in which every degree- vertex is assigned a -ary signature from – the problem is to compute the Holant value of , which is the value of the contraction of as a tensor network (see Subsection 2.1 for formal definitions). For various , captures a wide variety of natural counting problems on graphs, including counting partial or perfect matchings, graph homomorphisms, proper vertex or edge-colorings, or Eulerian orientations. Major complexity dichotomies classifying as either polynomial-time tractable or #P-hard, depending on , have been proved for various combinations of restrictions on – for example, requiring that the signatures in be real- or nonnegative-real-valued, symmetric (invariant under reordering of their inputs), or on the Boolean domain [22, 9, 7, 23, 35].
Holant problems were motivated by Valiant’s technique of holographic transformations [39]. In particular, Valiant’s Holant theorem (Theorem 7 below) states roughly that two pairs of signature sets and equivalent up to a certain linear transformation are Holant-indistinguishable, meaning that every bipartite signature grid has the same Holant value whether its vertices are assigned signatures from or from . Many problems which do not otherwise appear tractable are in fact tractable under a Holographic transformation to a known tractable problem [38]. Xia [41] conjectured the converse of the Holant theorem: if and are Holant-indistinguishable, then they are equivalent up to linear transformation. Xia’s general conjecture is false (see Subsection 2.2), but one case highlighted by Xia was left open. This paper proves that case, which is as follows.
Theorem (Theorem 9, informal).
Sets and of real-valued signatures are equivalent under a real orthogonal transformation if and only if and are Holant-indistinguishable.
Vertex and edge coloring models
This work uses and generalizes ideas from the theory of vertex coloring models and edge coloring models, two well-studied classes of Holant problems. De la Harpe and Jones [14] defined vertex and edge coloring models as extensions of statistical mechanics models (e.g. the Ising model), calling them “spin models” and “vertex models”, respectively. A vertex coloring model (also called a spin system) is defined by a graph with edge and possibly vertex weights. Given an input graph , one aims to compute the partition function, the number of (weighted) homomorphisms from to . As we discuss in Subsection 2.1, computing the partition function of a vertex coloring model without vertex weights is equivalent to , where is the weighted adjacency matrix of and is the set of equality signatures (we can model vertex weights by replacing with , the set of weighted equalities). An edge coloring model is defined by a set of symmetric signatures containing exactly one signature of each arity, and the problem of computing its partition function is equivalent to (this restriction on ensures that edge coloring models take ordinary graphs, rather than signature grids, as input).
One thread of prior work on vertex and edge coloring models characterizes which graph parameters (scalar-valued functions defined on isomorphism classes of graphs) are expressible as vertex coloring models [20, 34] or as edge coloring models [37, 32, 16, 29]. Another, related, line of works compute the rank of connection matrices for vertex coloring models [25] and edge coloring models [28, 17]. See Regts’s thesis [30] for an overview of many of the above results. Following Freedman, Lovász, and Schrijver [20], these works all use some form of (labeled) quantum graphs, algebras of formal linear combinations of graphs equipped with labeled vertices or “half edges” incident to a single vertex. Each labeled quantum graph defines a tensor by evaluating its partition function when its labeled vertices are fixed to input values. All such constructions are special cases of our quantum gadgets below (see 12). Many of these works also apply techniques from invariant theory, either of the symmetric group in the case of vertex coloring models [34], or, as in this work, of the orthogonal group in the case of edge-coloring models [37, 32, 16, 28, 17, 29].
Counting Indistinguishability Theorems
Theorem 9 is a very general and powerful algebraic counting indistinguishability theorem. Such a theorem proves that two signatures, or sets of signatures, are indistinguishable as parameters for a counting problem if and only if they are equivalent under an algebraic transformation. These theorems exist for both vertex and edge coloring models, as well as other counting problems [15, 21, 18]. Since the Holant framework captures a wide variety of counting problems, including both vertex and edge coloring models, many such theorems are special cases of Theorem 9 (see Section 4). If the counting problem in question is a generalized vertex coloring model ( for some ), then the algebraic transformation is isomorphism, and if the counting problem is, as in this work, a generalized edge coloring model, then it is orthogonal. The first counting indistinguishability theorem, proved by Lovász [26], states that two graphs are isomorphic if and only if they admit the same number of homomorphisms from all graphs. Much later, Lovász [25] extended this theorem to vertex coloring models with nonnegative real weights, followed by extensions to complex edge weights by Schrijver [34], and to weights from any field of characteristic zero by Cai and Govorov [8]. Young [42] extended Cai and Govorov’s proof to #CSP, or for any .
For edge coloring models, Schrijver [32] showed that and define indistinguishable real edge coloring models if and only if and are equivalent under a real orthogonal transformation. This is a special case of our Theorem 9. Schrijver’s proof exploits the specific nature of edge coloring models – that and consist of symmetric signatures and exactly one signature per arity – to transform input graphs into polynomials expressible in variables (for and on domain ), where a monomial with variable multiset corresponds to the -entry of the unique -ary signature in . This enables the application of invariant-theoretic tools for polynomial rings. Another form of this result (allowing a complex orthogonal transformation) follows from Regts’s proof of [29, Lemma 5], which similarly encodes and as polynomials.
Holant-like indistinguishability theorems also arise in tensor network theory, where they are called fundamental theorems. It has been shown that two tensors are equivalent up to a gauge transformation (a concept similar to holographic transformation) if and only if they yield the same quantum state (roughly, Holant gadget signature) on every instance of certain vertex-regular tensor networks studied in quantum physics, e.g. PEPS tensor networks [1].
Mančinska and Roberson [27] introduced a new form of counting indistinguishability theorem, showing that two graphs are quantum isomorphic – an abstract relaxation of isomorphism – if and only if they admit the same number of homomorphisms from all planar graphs. Cai and Young [13] translated Mančinska and Roberson’s proof into the Holant framework and extended it to planar (or , where restricts to planar signature grids), showing that real-valued and are planar--indistinguishable iff they are quantum isomorphic.
Odeco signature sets
A real-valued symmetric signature (tensor) is orthogonally decomposable, or odeco [31], if it is orthogonally transformable to a signature in , the set of generalized equality signatures, which take nonzero values only when all of their inputs are equal. Hence odeco tensors generalize diagonalizable matrices. Call a set of signatures odeco if the signatures are simultaneously odeco (there is a single orthogonal transformation mapping into ). In counting complexity, if is odeco, then is polynomial-time tractable, as maps into , a trivially tractable set, under an orthogonal holographic transformation. Indeed, the tractability of Fibonacci signature sets [11] can, with one exception, be explained by such sets being simultaneously odeco (see e.g. [4, Section 2.2]). Fibonacci sets constitute almost all nontrivial tractable cases of problems (an important variant of Holant which assumes the presence of all unary signatures) for symmetric signatures on the Boolean domain [12]. Odeco sets are a natural starting point for extending Fibonacci signatures to higher domains [24, 10], where no full complexity dichotomy for is known.
Boralevi, Draisma, Horobeţ, and Robeva [2], resolving a conjecture of Robeva [31], showed using techniques from algebraic geometry that a single tensor is odeco if and only if the signature of a certain -gadget is symmetric. Using Theorem 9, we in Theorem 27 extend this characterization to sets of simultaneously odeco signatures: is odeco if and only if every connected -gadget has a symmetric signature. The latter condition is equivalent to the symmetry of the signatures of all gadgets in a set of small gadgets constructed from every pair of signatures in . Therefore, if is finite, our characterization yields a simple -time algorithm (for on domain with maximum arity ) for deciding whether is odeco. This algorithm, and other potential bounded-time combinatorial algorithms using Theorem 9 to check whether there exists an orthogonal holographic transformation between two signature sets, could prove useful in making the tractability or intractability conditions of future higher-domain dichotomy theorems decidable. Our characterization also deepens the connection between Fibonacci and odeco signatures, as the original proof of tractability of any Fibonacci signature set [11] relied on the fact that every connected -gadget has a signature which is itself Fibonacci (in particular, is symmetric). One can view the (iii) (ii) result in Theorem 27 as a general-domain version of this proof.
Overview
The proof of Theorem 9 begins with a combinatorial-algebraic duality (Theorem 15) showing that combinatorial quantum -gadgets exactly capture all tensors invariant under the algebraic action of the group of orthogonal transformations stabilizing . The proof of Theorem 15 uses an invariant-theoretic result of Schrijver [33], and generalizes a proof of a similar result of Regts [28] for edge coloring models. Unifying the perspective of Regts with that of Mančinska and Roberson and Cai and Young [27, 13, 42], we find our proof of Theorem 15 analogous to proofs of similar results in the latter line of work (see [43, Remark 3.1]). However, Mančinska and Roberson and Cai and Young’s proofs of their counting indistinguishability theorems use orbits of the (quantum) symmetric group on the domain set , which do not exist for the orthogonal group. Instead, we apply a novel method: induction on the domain size . We show in 19 that, if and contain a nontrivial diagonal matrix (binary signature) , then we can separate into smaller subdomains and apply induction to complete the proof. Then we use Theorem 15 to show that, unless and are trivially transformable, we can add such a to and .
In Section 4 we show that Theorem 9 encompasses a range of existing counting indistinguishability theorems, and yields some novel variations of these theorems. In Section 5 we show that Theorem 9 does not extend to complex-valued signatures, and conjecture an extension of the results of Mančinska and Roberson [27] and Cai and Young [13] to planar-Holant-indistinguishability and quantum orthogonal transformations. Our proof of Theorem 9, particularly the connections developed in [43, Section 3], is designed to be transformable into a proof of this conjecture; in Subsection 5.2, we discuss the remaining roadblocks to completing the proof.
2 Preliminaries, Background, and the Main Theorem
2.1 Holant Problems, Gadgets, and Signature Matrices
Let be the set of natural numbers, including 0. A signature of finite arity on finite domain is function . We will often take , in which case we also view as a tensor in . For , abbreviate . Signature is symmetric if its value depends only on the multiset of inputs, not on their order. Signatures in a set have a common domain, denoted .
For a signature set , a signature grid (or -grid) consists of an underlying multigraph with vertex set and edge set , and an assignment of a -ary signature to each , along with an ordering of (the edges incident to ) such that, if is an assignment of a value in to each edge of , then evaluates to . The problem is to compute the Holant value
(1) |
The Holant value of a disconnected signature grid is the product of the Holant values of its connected components. For signature sets and , define the problem on bipartite -grids , with the vertices in the two bipartitions assigned signatures in and , respectively.
For example, if is on the Boolean domain and consists of, for each arity , a symmetric signature which evaluates to 1 on input strings of Hamming weight 1 and 0 on all other input strings, then equals the number of perfect matchings in the multigraph underlying . For another example, let be the adjacency matrix of weighted graph , and define the set of equality signatures, where is 1 if , and is 0 otherwise. For an -grid , let be the graph resulting from ignoring (treating as edges) the degree-two vertices assigned in the underlying graph of . Then the vertex coloring model equals the number of graph homomorphisms from to . See Figure 1.
Instead of viewing a signature as a tensor in or function in , we can partition its inputs in two to view it naturally as a matrix.
Definition 1 ().
For and with , define the -signature matrix, or flattening, of by, for and ,
where we use to index . Write – the signature vector of .
We will often identify binary signatures in with their signature matrices in .
Definition 2 ().
For a signature set , an -gadget is a -grid equipped with an ordered set of dangling edges with zero or one endpoints. Define to be the set of all -gadgets, and to be the set of gadgets with dangling edges drawn with dangling ends in counterclockwise cyclic order around the gadget, with and on the left and right, respectively, from top to bottom.
See Figure 2 for examples of gadgets. A gadget in defines an -ary signature in flattened form, with dangling edges representing inputs, as follows (cf. (1)):
Definition 3 ().
Define the signature matrix of by
In other words, equals the Holant value of when the left and right dangling edges are fixed to the domain elements in and , respectively. For , there is a unique , the signature of , such that . Note that does not depend on the particular left/right partition (i.e. choice of and ) of a fixed cyclic order of ’s dangling edges.
Define gadget operations , illustrated in Figure 2 (see [43, Definition 2.4] for formal definitions). The three gadget operations induce the respective operations – composition, Kronecker product, transpose – on their signature matrices. See e.g. [4, Section 1.3].
Definition 4 ().
For real-valued and -ary -gadgets and , construct the signature grid by connecting the th dangling edges of and , for . If and have signatures and , then define (the standard inner product on ).
Define .
2.2 The Holant Theorem
Definition 5 ().
For invertible and , let be the signature with vector – that is, (see Figure 3).
For set , define .
We usually have , the (real) orthogonal group. Throughout this work, we assume pairs and of signature sets are similar, meaning they have the same domain size and there is a bijection such that, for -ary , the image of , called the signature corresponding to and denoted by , has the same arity .
Definition 6 ().
For (similar) sets and and gadget , define the gadget by replacing every assigned to a vertex in by the corresponding . If has zero dangling edges then it is an -grid , and is transformed to a -grid .
The following theorem of Valiant [39] is a powerful reduction tool and the original motivation for Holant. For and , define similarly to , by .
Theorem 7 (The Holant Theorem).
For any -grid and matrix ,
Xia [41] conjectured that the converse of Theorem 7 holds as long as one of or contain a signature with arity greater than one: if for every -grid , then there is an such that and . However, Cai, Guo, and Williams [9, Section 4.3] observe that this conjecture is false. They consider
for any not both 0, where and are symmetric signatures on the Boolean domain of arity , respectively, specified by their values on input strings of Hamming weight through . These signature sets satisfy the hypothesis of Xia’s conjecture, as they differ by the vanishing (Holant-indistinguishable from 0) signature set , but there is no satisfying and .
Cai, Guo, and Williams’ counterexample exists due to the bipartiteness of , as , so and are not indistinguishable on general (non-bipartite) signature grids. To avoid such counterexamples, we consider the following well-known form of Theorem 7 that applies to non-bipartite grids . Replace each edge in by a path of length two, with central vertex assigned . This does not change the Holant value of , which is now a -grid. Any satisfies , so Theorem 7 gives:
Corollary 8 (The Orthogonal Holant Theorem).
If for orthogonal matrix , then for every -grid .
Xia also considers the converse of 8, and proves that it holds for specific and consisting of symmetric signatures with small domain and/or arity. The main result of this work is the converse of 8 for any sets and of real-valued signatures, with no restrictions.
Theorem 9 (Main Result).
The following are equivalent for sets , of real-valued signatures:
-
(i)
for every -grid (, are Holant-indistinguishable).
-
(ii)
There is a real orthogonal matrix such that (, are ortho-equivalent).
3 The Proof of Theorem 9
Henceforth, assume all signatures are real-valued.
Definition 10 ().
Let be the set of all domain- signatures.
Definition 11 (, ).
For a subgroup and , define
The following objects generalize the (labeled) quantum graphs originally introduced by Freedman, Lovász, and Schrijver [20], so-called because they are “superpositions” of graphs.
Definition 12 (, ).
An -quantum -gadget is a formal (finite) -linear combination of gadgets in . Extend the signature matrix function linearly to the set of quantum -gadgets and define the quantum gadget closure of as the set of quantum -gadget signatures:
If sets and are similar, then and are similar, with the signature of corresponding to the signature of .
The next two lemmas are nonplanar, orthogonal versions of [13, Lemmas 31 and 32].
Lemma 13.
and are Holant-indistinguishable iff and are Holant-indistinguishable.
Proof.
Any -grid or -grid is also a -grid or -grid, respectively, giving the direction. For , we can express any -grid as a quantum -grid by, for every vertex in assigned a signature , replacing the subgadget of induced by by the quantum -gadget with signature , then linearly expanding to obtain a quantum -grid. Do the same for . By assumption, the resulting corresponding quantum and -grids have the same values, so .
Lemma 14.
For any orthogonal , iff (in particular, ).
14, proved in the full version [43, Lemma 4.1.2], follows from the fact that orthogonal transformations respect the operations used to construct quantum gadgets.
The following key theorem, also proved in the full version [43, Theorem 3.2], extends an edge coloring model result of Regts [28, Theorem 3].
Theorem 15.
Let be a set of signatures on domain . Then .
The inclusion of Theorem 15 again follows from the fact that orthogonal transformations respect the operations used to construct quantum gadgets, so any orthogonal matrix stabilizing stabilizes any quantum -gadget signature. The proof of the much deeper inclusion, which shows that every tensor in is concretely realizable as a quantum gadget signature, uses an invariant-theoretic result of Schrijver [33].
Definition 16 ().
Let be -ary signatures on domains , , both of size . The direct sum of and is an -ary signature on domain defined by
For signature sets and , define .
View as a block matrix indexed by and . The next lemma is the only nonconstructive step in the proof of Theorem 9.
Lemma 17.
If and are Holant-indistinguishable, then contains a matrix which is not block-diagonal.
Proof.
Suppose every is block-diagonal. Then the block-diagonal matrix satisfies , or equivalently (see Figure 3), for every . Thus , so, by Theorem 15, is realizable as the signature of a quantum gadget: there exist binary ()-gadgets and such that
(2) |
Any connected component of a gadget disconnected from the component(s) of containing the two dangling edges contributes only an overall multiplicative factor; by absorbing this factor into , we may assume each has no components without a dangling edge. By definition of , inputting an along a dangling edge of forces any edge assignment with nonzero value to assign an element of to every edge in that dangling edge’s connected component. So, for any , we have . Similar reasoning applies to , so the and blocks of (2) are
(3) |
respectively. Let be the -grid resulting from connecting the two dangling edges of . Then taking the trace of the equations in (3) gives
so there is some for which .
The next definition and its applications use a simple but powerful idea of Shao and Cai [35, Section 8.2]: isolating all vertices of an -grid assigned , the rest of is an -gadget.
Definition 18 (Subgadget, ).
Let be a gadget. A subgadget induced by a subset of vertices of is a gadget composed of the vertices in and all of their incident edges: internal edges of incident to exactly one vertex in become new dangling edges of . For any , there is a unique (induced by ), called the complement of , such that, upon reconnecting the new dangling edges of and , we recover .
We often take to be a signature grid (0-ary gadget) , in which case .
We next state the main inductive lemma.
Lemma 19.
Let and be signature sets on domain , and suppose Theorem 9 holds for all , on domain smaller than . If and are Holant-indistinguishable and contain corresponding copies of a diagonal matrix (binary signature) , then and are ortho-equivalent.
The proof of 19 in the full version [43, Lemma 4.3] proceeds roughly as follows. The quantum gadget closure of is a vector space closed under both entrywise sum and entrywise product (the latter equivalent to composition, as is diagonal). Therefore, by a standard Vandermonde interpolation argument, implies that contains the binary signatures and for a nontrivial partition of the domain, where e.g. acts as on and 0 on . Replacing, say, each edge of an - or -grid by , we effectively obtain an - or -grid, respectively (where is the restriction of to the subdomain ). Thus and are Holant-indistinguishable, so, inductively, and are ortho-equivalent. Similarly, and are ortho-equivalent. These two subdomain transformations alone do not necessarily transform the “off-diagonal blocks” of into the corresponding blocks of , so some more work is required. We add some useful auxiliary signatures to and between the successive and subdomain transformations, using subgadgets to show Holant-indistinguishability is preserved, and finally obtain a full transformation from to .
The final step is to realize the diagonal matrix in the statement of 19 and apply induction. Say is quantum-gadget-closed if .
Proof of Theorem 9.
is 8. We show . Let be Holant-indistinguishable. We proceed by induction on the domain size . The full version shows the case in the proof of [43, Theorem 2.3], so assume . Lemmas 13 and 14 show that replacing and by and does not affect their Holant-indistinguishability or ortho-equivalence, so we may assume and are quantum-gadget-closed. By 17, there is an with, WLOG, nonzero block . Let be the singular value decomposition of this block, with orthogonal and diagonal. Replace with and with (this does not change whether and are Holant-indistinguishable or ortho-equivalent). This replaces with (by [43, Equation A.1]), which, by [43, Proposition 4.2], replaces with . In particular, is replaced with
To summarize, after transforming by and by , we have for nonzero diagonal . We consider two cases for : either or . First, suppose , so for . Let be nonzero -ary signatures with . By part 3 of [43, Proposition 3.1] (see Figure 3), gives
(4) |
By [43, Proposition A.1] (with ) and [43, Equation 2.2], we can write (4) as a block matrix equation
(5) |
The bottom-left block of (5) is ; using , this is equivalent to
(6) |
Then
(7) |
As and are quantum-gadget-closed, there are some with arity , so (7) gives . Now applying (6) to any -ary pair with gives , so , with .
For unary () and , since and are quantum-gadget-closed, they contain the ternary signatures and , respectively. So, by the previous paragraph, , or equivalently , which implies . Combining the non-unary and unary cases, we have .
Otherwise, . We will show and are Holant-indistinguishable, then apply 19.
Consider an -grid with at least one vertex assigned (if has no such vertex then we are done, as and are Holant-indistinguishable). Let be the subgadget induced by all vertices assigned . Any connected component of is either a cycle or a binary path gadget with signature for some . The multiplicative factors from corresponding -cycles in and cancel, so assume consists of disconnected path gadgets. By rearranging the dangling edges of and , we may assume with for , and furthermore that , and that connecting the th left input and th right input of , for , reconstructs (see Figure 4). Since is an -gadget and is quantum-gadget-closed, has signature for some . Then, with ,
(8) |
As in (4), part 3 of [43, Proposition 3.1] gives . As in (5), the bottom left block of this equation is . Now applying (8), we have
Thus and are Holant-indistinguishable. By induction, 19 gives that and are ortho-equivalent. Therefore and are ortho-equivalent.
4 Consequences of Theorem 9
In this section, we exploit the expressiveness of the Holant framework to show that Theorem 9 encompasses a variety of existing results, and derive a few novel consequences.
4.1 Counting CSP and graph homomorphisms
For a signature set , define the counting constraint satisfaction problem with constraint function set to be the problem . Vertices assigned signatures in and are constraints and variables, respectively, and an -grid is a constraint-variable incidence graph, where a variable appears in all of its incident constraints. Then is the sum over all variable assignments of the product of the constraint evaluations. Like Holant, is a well-studied problem in counting complexity, with broad dichotomy theorems classifying as either tractable or #P-hard [3, 19, 6, 5].
By inserting a dummy degree-2 constraint vertex assigned between adjacent variable vertices and combining adjacent constraint vertices assigned and into a single constraint vertex assigned , we see that is equivalent to . Say and are isomorphic if there exists a permutation matrix satisfying – in other words, and are the same up to relabeling of their domains. Using a standard Vandermonde interpolation argument, Xia [41] shows that satisfies if and only is a permutation matrix. Say that and are -indistinguishable if and are Holant-indistinguishable (in other words, every instance has the same value whether we use constraint functions from or from ). Applying Theorem 9 to and , we obtain the main result of Young [42] for real-valued constraint functions.
Corollary 20.
Let and be sets of real-valued constraint functions. Then and are isomorphic if and only if and are -indistinguishable.
As discussed in Subsection 2.1, counts the number of homomorphisms to the graph . Therefore 20 is a generalization of the classical theorem of Lovász [26] that two graphs are isomorphic if and only if they admit the same number of homomorphisms from every graph.
Let be the set of equality signatures of even arity. Schrijver [33] shows222The First Fundamental Theorem for (the group of signed permutation matrices) states that . It follows as in the proof of Theorem 15 that . The fact that (the group of permutation matrices) similarly follows from the First Fundamental Theorem for , which states that . that satisfies if and only if is a signed permutation matrix (a matrix with entries in and exactly one nonzero entry in each row and column). As above, is equivalent to (critically, if and , then ). Then, defining as restricted to instances in which every variable appears an even number of times [7, 22], we have
Corollary 21.
Let and be sets of real-valued constraint functions. Then there is a signed permutation matrix satisfying if and only if and are -indistinguishable.
In particular, since (unweighted) graph adjacency matrices and have entries in , we have , where is the permutation matrix created by flipping every entry of to . Therefore we have the following novel (to our knowledge) sharpening of Lovász’s theorem.
Corollary 22.
Graphs and are isomorphic if and only if they admit the same number of homomorphisms from those graphs in which all vertices have even degree.
4.2 Simultaneous matrix similarity
Let and be sets of binary signatures, thought of as matrices. Any connected -grid is a cycle. Breaking an edge of the cycle, we obtain a binary path gadget with signature matrix , where, depending on its orientation, each or . Connecting the path’s two dangling edges, we reform , which thus has Holant value . Let be the set of all finite products of matrices in and . Define similarly and, for a word , construct by replacing every character or in by the corresponding or , respectively. For orthogonal , we have for every (see Figure 3), so, in this setting, Theorem 9 is equivalent to the following real-valued case of a classical theorem from representation theory, due to Specht [36] and Wiegmann [40]. Grohe, Rattan, and Seppelt [21] also give a combinatorial proof.
Corollary 23.
Let . Then there is an such that for every if and only if for every .
Suppose and for graphs and . Transform an -grid to a -grid by inserting a dummy degree-2 vertex assigned between every consecutive pair of vertices in the cycle. Recall from Subsection 2.1 that counts the number of homomorphisms from graph to , where is the graph obtained from by ignoring the vertices assigned . Here is a cycle, so we have the following well-known result, an alternate formulation of this case of 23.
Corollary 24.
Let and be graphs. Then there is an orthogonal matrix satisfying if and only if and admit the same number of homomorphisms from all cycles.
A matrix is pseudo-stochastic if all of its rows and columns sum to 1. Dell, Grohe, and Rattan [15] proved that graphs and admit the same number of homomorphisms from all paths if and only if there is a pseudo-stochastic matrix such that . Theorem 9 gives a novel combination of this result with 24, and reproduces a combinatorial explanation for the connection between pseudo-stochastic matrices and homomorphisms from paths [21].
Corollary 25.
Let and be graphs. Then there is a pseudo-stochastic orthogonal matrix satisfying if and only if and admit the same number of homomorphisms from all cycles and paths.
Proof.
Consider . Any -grid is a disjoint union of cycles composed of signatures assigned and paths with degree-2 internal vertices assigned and degree-1 endpoints assigned . As discussed before 24, every cycle -grid has the same Holant value as iff and admit the same number of homomorphisms from every cycle. Similarly, the Holant value of each path component is the number of homomorphisms to from the underlying path. Thus and admit the same number of homomorphisms from all cycles and all paths iff and are Holant-indistinguishable. By Theorem 9, this is equivalent to the existence of an orthogonal satisfying and . The vector form of is the all-ones vector, so if and only if the rows of sum to and (since ) the columns of sum to 1.
4.3 Odeco signature sets
Definition 26 (, odeco).
Define the set of general equalities (or weighted equalities) on domain as , where is the symmetric -ary signature defined by if , and otherwise. A set of symmetric signatures is orthogonally decomposable, or odeco, if there is an such that .
Robeva [31] coined the term “odeco” for individual symmetric tensors (signatures). A binary signature has a diagonal signature matrix, so the spectral theorem states that every (real) symmetric binary signature is odeco. Any nonzero edge assignment for a connected -gadget must assign all edges, including dangling edges, the same value, so, if has arity and is composed of vertices assigned signatures with weights , then has signature , where denotes entrywise product. Thus, if , then is polynomial-time tractable.
For symmetric signatures , construct the signature from by connecting an input of and an input of (see Figure 5).
For and , we have (with vectors viewed as input lists)
Theorem 27.
Let be a set of real-valued symmetric tensors. The following are equivalent.
-
(i)
is odeco.
-
(ii)
Every connected -gadget has a symmetric signature.
-
(iii)
For every , is symmetric.
Robeva [31] conjectured the equivalence of items (i) and (iii) when contains a single signature. Boralevi, Draisma, Horobeţ, and Robeva [2] confirmed this conjecture using techniques from algebraic geometry. Using Theorem 9, we give a combinatorial proof for any set of symmetric signatures.
Remark 28.
If is a set of symmetric binary signatures (matrices), then (a matrix product). Symmetric matrices commute iff their product is symmetric, so Theorem 27 encompasses the fact that commuting symmetric matrices are simultaneously diagonalizable.
Proof of Theorem 27.
(i) (ii),(iii): Suppose for some . Let be the signature of a connected -gadget (e.g. ). By 14, , where is the signature of a connected -gadget. Then , so , and thus , are symmetric.
(ii) (i): By [43, Proposition 5.1], we may replace every by to assume all signatures in have even arity. For , let be the matrix of the binary signature constructed by connecting all but one pair of inputs of (see Figure 5). Every , and every for , is symmetric by assumption. Thus, as in 28, the for all commute.
Claim 29.
If is a connected binary -gadget with vertices, assigned signatures , then .
We prove 29 by induction on . For , by the symmetry of , every connected binary -gadget with a single vertex has signature . Now suppose . Then contains a vertex whose removal does not disconnect . Assume WLOG that is assigned signature . Construct from by breaking all but one edge between and other vertices (see Figure 6). Since remains connected, its signature is symmetric by assumption. Create a binary gadget from by arbitrarily pairing up and connecting all but one dangling edge incident to , and similarly pairing up and connecting all but one dangling edge incident to the other vertices of . We may also recover from by connecting possibly different pairs of dangling edges (reforming the edges broken to create ) and, since the signature of is symmetric, the signature of a gadget produced by connecting dangling edges of does not depend on which pairs of dangling edges we connect (although the underlying graphs of the gadgets differ). Therefore .
Let be the subgadget of induced by . Then (see Figure 6), and . So, applying induction to , which has vertices, gives (recall that the commute). This proves 29.
The matrices for are symmetric and commute, so they are simultaneously diagonalizable: there is an such that, for every , for some . Replace with to assume each (this does not change whether is odeco). Define , a set similar to . Let be an -grid, containing signatures . Break some edge of to produce a connected binary -gadget . By 29,
Reconnecting the dangling edges of , we find . Thus and are Holant-indistinguishable, so, by Theorem 9, and are ortho-equivalent. Hence is odeco.
(iii) (ii): Let be the -ary signature of a connected -gadget . Every unary signature is trivially symmetric, so assume . It suffices to show that, for any fixed partial input to and any , we have (where we assume WLOG that and are the first two inputs to by reordering the dangling edges of ). Let and be the vertices of incident to the first and second dangling edges of (after reordering). If then we are done, as every is symmetric. Otherwise, since is connected, it contains a path from to , where is assigned signature , for . Let be the edges of , including the dangling edges and incident to and , respectively. Then and are inputs to for all . For any fixed assignment , define the matrix by (that is, fix the inputs to from edges outside of ). Then
(9) |
where is the ordered list of the last dangling edges of and
On the RHS of (9), and appear only in . Thus it suffices to show that, for any fixed , . For any and ,
where the fourth equality uses the assumption that is symmetric. Thus is symmetric. Both and are symmetric, as and are symmetric, so, as in 28, and commute. Therefore
5 Possible Variations of Theorem 9
5.1 Complex-valued signatures
Although we have focused on real-valued signatures and matrices, the general and orthogonal Holant Theorems hold for complex-valued signatures and matrices. However, Theorem 9 does not hold for general sets and of complex-valued signatures, even when we allow to be complex. Cai, Guo, and Williams [9] and Draisma and Regts [17] consider another counterexample involving vanishing signatures, namely the unary signature defined by and . Any -grid with at least one vertex satisfies , as is a disjoint union of complete graphs, each with value . Thus is Holant-indistinguishable from 0, but there is no orthogonal matrix , real or complex, satisfying .
Cai and Young [13] and Young [42] prove their counting indistinguishability theorems for complex-valued signature sets with the assumption that the sets are conjugate-closed, meaning they must contain the entrywise conjugate of each of their complex signatures. It is feasible that Theorem 9 could similarly hold for complex-valued conjugate-closed and and complex orthogonal (this invalidates the above counterexample, as ).
5.2 Quantum orthogonal matrices and planar signature grids
A quantum orthogonal matrix is, roughly, a matrix whose entries are self-adjoint elements of an abstract, not necessarily commutative, -algebra, satisfying the relation , where is the identity element of the -algebra. Just as a permutation matrix is an orthogonal matrix that stabilizes , a quantum permutation matrix is a quantum orthogonal matrix that stabilizes (see e.g. [13, Equation 27]). The main theorem of Cai and Young [13], extending the result of Mančinska and Roberson [27], is a planar, quantum version of 20: and are -indistinguishable (planar-#CSP-indistinguishable) if and only if there is a quantum permutation matrix satisfying ( and are quantum isomorphic). Removing , we should obtain the following planar, quantum version of Theorem 9.
Conjecture 30.
Let , be sets of real-valued signatures. Then the following are equivalent.
-
(i)
for every planar -grid .
-
(ii)
There is a quantum orthogonal matrix such that .
Cai and Young [13, Theorem 5] prove (ii) (i) when is a quantum permutation matrix; however, their proof only relies on being a quantum orthogonal matrix. Therefore, to prove 30, it suffices to show (i) (ii). The Tannaka-Krein duality for the quantum symmetric group used by Mančinska and Roberson and Cai and Young [13, Theorem 3] has a more general version for the quantum orthogonal group [27, Theorem 2.13]. This version is analogous to the theorem of Schrijver used to prove Theorem 15, but concerning quantum stabilizer subgroups of and planar gadgets. Then, following the proof of [13, Theorem 4], but ommitting the gadgets and used to construct , we will obtain a quantum analogue of our Theorem 15 for planar quantum -gadgets, giving a quantum analogue of 17. The rest of the proof of Theorem 9, however, involves nonplanar signature grid manipulations (e.g. in Figure 4 it is in general impossible to embed such that every instance of lies on the outer face) and, more critically, relies on the existence of the singular value decomposition of a submatrix of a real orthogonal matrix, then on viewing the resulting diagonal matrix as a signature. It is yet unclear whether the same or similar reasoning applies to a submatrix of a quantum orthogonal matrix.
References
- [1] Arturo Acuaviva, Visu Makam, Harold Nieuwboer, David Pérez-García, Friedrich Sittner, Michael Walter, and Freek Witteveen. The minimal canonical form of a tensor network. In 64th IEEE Annual Symposium on Foundations of Computer Science, FOCS 2023, Santa Cruz, CA, USA, November 6-9, 2023, pages 328–362, Los Alamitos, CA, USA, November 2023. IEEE. doi:10.1109/FOCS57990.2023.00027.
- [2] Ada Boralevi, Jan Draisma, Emil Horobeţ, and Elina Robeva. Orthogonal and unitary tensor decomposition from an algebraic perspective. Israel Journal of Mathematics, 222(1):223–260, October 2017. doi:10.1007/s11856-017-1588-6.
- [3] Andrei A. Bulatov. The complexity of the counting constraint satisfaction problem. J. ACM, 60(5):34:1–34:41, October 2013. doi:10.1145/2528400.
- [4] Jin-Yi Cai and Xi Chen. Complexity Dichotomies for Counting Problems, volume 1. Cambridge University Press, 2017. doi:10.1017/9781107477063.002.
- [5] Jin-Yi Cai and Xi Chen. Complexity of counting CSP with complex weights. J. ACM, 64(3):19:1–19:39, June 2017. doi:10.1145/2822891.
- [6] Jin-Yi Cai, Xi Chen, and Pinyan Lu. Nonnegative weighted #csp: An effective complexity dichotomy. SIAM J. Comput., 45(6):2177–2198, 2016. doi:10.1137/15M1032314.
- [7] Jin-Yi Cai, Zhiguo Fu, Heng Guo, and Tyson Williams. A holant dichotomy: Is the FKT algorithm universal? In Venkatesan Guruswami, editor, IEEE 56th Annual Symposium on Foundations of Computer Science, FOCS 2015, Berkeley, CA, USA, 17-20 October, 2015, pages 1259–1276. IEEE, IEEE Computer Society, 2015. doi:10.1109/FOCS.2015.81.
- [8] Jin-yi Cai and Artem Govorov. On a theorem of lovász that (&sdot, H) determines the isomorphism type of H. ACM Trans. Comput. Theory, 13(2):11:1–11:25, 2021. doi:10.1145/3448641.
- [9] Jin-Yi Cai, Heng Guo, and Tyson Williams. A complete dichotomy rises from the capture of vanishing signatures. SIAM J. Comput., 45(5):1671–1728, 2016. doi:10.1137/15M1049798.
- [10] Jin-Yi Cai and Jin Soo Ihm. Holant* dichotomy on domain size 3: A geometric perspective, 2025. doi:10.48550/arXiv.2504.14074.
- [11] Jin-yi Cai, Pinyan Lu, and Mingji Xia. Holographic algorithms by fibonacci gates and holographic reductions for hardness. In 49th Annual IEEE Symposium on Foundations of Computer Science, FOCS 2008, October 25-28, 2008, Philadelphia, PA, USA, pages 644–653. IEEE, IEEE Computer Society, 2008. doi:10.1109/FOCS.2008.34.
- [12] Jin-yi Cai, Pinyan Lu, and Mingji Xia. Computational complexity of holant problems. SIAM J. Comput., 40(4):1101–1132, 2011. doi:10.1137/100814585.
- [13] Jin-Yi Cai and Ben Young. Planar #csp equality corresponds to quantum isomorphism - A holant viewpoint. ACM Trans. Comput. Theory, 16(3):18:1–18:41, September 2024. doi:10.1145/3689486.
- [14] Pierre de la Harpe and Vaughan F. R. Jones. Graph invariants related to statistical mechanical models: Examples and problems. J. Comb. Theory B, 57(2):207–227, March 1993. doi:10.1006/jctb.1993.1017.
- [15] Holger Dell, Martin Grohe, and Gaurav Rattan. Lovász meets weisfeiler and leman. In Ioannis Chatzigiannakis, Christos Kaklamanis, Dániel Marx, and Donald Sannella, editors, 45th International Colloquium on Automata, Languages, and Programming, ICALP 2018, July 9-13, 2018, Prague, Czech Republic, volume 107 of LIPIcs, pages 40:1–40:14, Dagstuhl, Germany, 2018. Schloss Dagstuhl – Leibniz-Zentrum für Informatik. doi:10.4230/LIPIcs.ICALP.2018.40.
- [16] Jan Draisma, Dion C. Gijswijt, László Lovász, Guus Regts, and Alexander Schrijver. Characterizing partition functions of the vertex model. Journal of Algebra, 350(1):197–206, January 2012. doi:10.1016/j.jalgebra.2011.10.030.
- [17] Jan Draisma and Guus Regts. Tensor invariants for certain subgroups of the orthogonal group. Journal of Algebraic Combinatorics, 38(2):393–405, September 2013. doi:10.1007/s10801-012-0408-7.
- [18] Zdenek Dvorák. On recognizing graphs by numbers of homomorphisms. J. Graph Theory, 64(4):330–342, 2010. doi:10.1002/jgt.20461.
- [19] Martin E. Dyer and David Richerby. An effective dichotomy for the counting constraint satisfaction problem. SIAM J. Comput., 42(3):1245–1274, 2013. doi:10.1137/100811258.
- [20] Michael Freedman, László Lovász, and Alexander Schrijver. Reflection positivity, rank connectivity, and homomorphism of graphs. Journal of the American Mathematical Society, 20(1):37–51, 2007.
- [21] Martin Grohe, Gaurav Rattan, and Tim Seppelt. Homomorphism tensors and linear equations. In Mikolaj Bojanczyk, Emanuela Merelli, and David P. Woodruff, editors, 49th International Colloquium on Automata, Languages, and Programming, ICALP 2022, July 4-8, 2022, Paris, France, volume 229 of LIPIcs, pages 70:1–70:20. Schloss Dagstuhl – Leibniz-Zentrum für Informatik, 2022. doi:10.4230/LIPIcs.ICALP.2022.70.
- [22] Sangxia Huang and Pinyan Lu. A dichotomy for real weighted holant problems. Comput. Complex., 25(1):255–304, 2016. doi:10.1007/s00037-015-0118-3.
- [23] Jiabao Lin and Hanpin Wang. The complexity of boolean holant problems with nonnegative weights. SIAM J. Comput., 47(3):798–828, 2018. doi:10.1137/17M113304X.
- [24] Yin Liu. A combinatorial view of holant problems on higher domains. In Computing and Combinatorics: 30th International Conference, COCOON 2024, Shanghai, China, August 23–25, 2024, Proceedings, Part II, pages 368–380, Berlin, Heidelberg, 2025. Springer-Verlag. doi:10.1007/978-981-96-1093-8_31.
- [25] László Lovász. The rank of connection matrices and the dimension of graph algebras. Eur. J. Comb., 27(6):962–970, 2006. doi:10.1016/j.ejc.2005.04.012.
- [26] László Lovász. Operations with structures. Acta Mathematica Hungarica, 18(3-4):321–328, 1967.
- [27] Laura Mancinska and David E. Roberson. Quantum isomorphism is equivalent to equality of homomorphism counts from planar graphs. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 661–672. IEEE, 2020. doi:10.1109/FOCS46700.2020.00067.
- [28] Guus Regts. The rank of edge connection matrices and the dimension of algebras of invariant tensors. Eur. J. Comb., 33(6):1167–1173, August 2012. doi:10.1016/j.ejc.2012.01.014.
- [29] Guus Regts. A characterization of edge-reflection positive partition functions of vertex-coloring models. In The Seventh European Conference on Combinatorics, Graph Theory and Applications, CRM Series, pages 305–311, Pisa, 2013. Scuola Normale Superiore. doi:10.1007/978-88-7642-475-5_49.
- [30] Guus Regts. Graph parameters and invariants of the orthogonal group. PhD thesis, Universiteit van Amsterdam, 2013.
- [31] Elina Robeva. Orthogonal decomposition of symmetric tensors. SIAM J. Matrix Anal. Appl., 37(1):86–102, January 2016. doi:10.1137/140989340.
- [32] Alexander Schrijver. Graph Invariants in the Edge Model. In Martin Grötschel, Gyula O. H. Katona, and Gábor Sági, editors, Building Bridges: Between Mathematics and Computer Science, pages 487–498. Springer, Berlin, Heidelberg, 2008. doi:10.1007/978-3-540-85221-6_16.
- [33] Alexander Schrijver. Tensor subalgebras and first fundamental theorems in invariant theory. Journal of Algebra, 319(3):1305–1319, February 2008. doi:10.1016/j.jalgebra.2007.10.039.
- [34] Alexander Schrijver. Graph invariants in the spin model. J. Comb. Theory B, 99(2):502–511, 2009. doi:10.1016/j.jctb.2008.10.003.
- [35] Shuai Shao and Jin-Yi Cai. A dichotomy for real boolean holant problems. In Sandy Irani, editor, 61st IEEE Annual Symposium on Foundations of Computer Science, FOCS 2020, Durham, NC, USA, November 16-19, 2020, pages 1091–1102. IEEE, 2020. doi:10.1109/FOCS46700.2020.00105.
- [36] Wilhelm Specht. Zur theorie der matrizen. ii. Jahresbericht der Deutschen Mathematiker-Vereinigung, 50:19–23, 1940.
- [37] Balázs Szegedy. Edge coloring models and reflection positivity. Journal of the American Mathematical Society, 20(4):969–988, May 2007. doi:10.1090/S0894-0347-07-00568-1.
- [38] Leslie G. Valiant. Accidental algorithms. In 47th Annual IEEE Symposium on Foundations of Computer Science (FOCS 2006), 21-24 October 2006, Berkeley, California, USA, Proceedings, pages 509–517. IEEE, IEEE Computer Society, 2006. doi:10.1109/FOCS.2006.7.
- [39] Leslie G. Valiant. Holographic algorithms. SIAM J. Comput., 37(5):1565–1594, 2008. doi:10.1137/070682575.
- [40] NA Wiegmann. Necessary and sufficient conditions for unitary similarity. Journal of the Australian Mathematical Society, 2(1):122–126, 1961.
- [41] Mingji Xia. Holographic reduction: A domain changed application and its partial converse theorems. In Samson Abramsky, Cyril Gavoille, Claude Kirchner, Friedhelm Meyer auf der Heide, and Paul G. Spirakis, editors, Automata, Languages and Programming, 37th International Colloquium, ICALP 2010, Bordeaux, France, July 6-10, 2010, Proceedings, Part I, volume 6198 of Lecture Notes in Computer Science, pages 666–677. Springer, Springer, 2010. doi:10.1007/978-3-642-14165-2_56.
- [42] Ben Young. Equality on all #csp instances yields constraint function isomorphism via interpolation and intertwiners, 2022. doi:10.48550/arXiv.2211.13688.
- [43] Ben Young. The converse of the real orthogonal holant theorem, 2024. doi:10.48550/arXiv.2409.06911.