PaperlayerView exact revision on arXiv

Source-linked AI summary

Entrywise Logarithmic Matrix Algebra and Dichotomy of Planar Graph Homomorphisms

Jin-Yi Cai, Zhuxiao Tang

arXiv:2610.00828v2cs.CC

TL;DR

The paper addresses the difficulty of classifying planar graph homomorphism problems beyond the Boolean domain, where tractable cases can combine through tensor products. It builds an algebra from realizable matrices and uses it to classify tractability for positive full-rank matrices, then extends the classification to nonnegative matrices.

  • Problem

    Classifying planar graph homomorphism problems on larger domains is difficult because tensor products of tractable cases yield highly nontrivial tractable problems.

    Source: §1 · p. 4

  • Method

    The authors form an entrywise-logarithmic algebra of realizable matrices and use a polynomial homomorphism to derive graph distances and classify the resulting distance-regular graphs.

    Source: §1 · pp. 5–6

  • Results

    The paper gives a dichotomy for entrywise-positive full-rank matrices and extends the classification to nonnegative matrices, with tractable nonnegative cases constrained by the component forms in Theorem 1.2.

    Source: §1 · p. 6

  • Takeaways & Limitations

    The positive full-rank classification is the core of the extension to nonnegative matrices.

    Source: §1 · p. 6

    The homogeneous-setting result assumes a fixed entrywise-positive full-rank matrix M and that Pl-GH(M) is not #P-hard.

    Source: §3.3 · p. 12

Abstract

from arXiv · show

We prove a complexity classification of counting planar graph homomorphisms with non-negative weights. For a real symmetric matrix $M$ with nonnegative entries, the problem $\GH(M)$ is either (1) P-time computable over all graphs, or (2) \#P-hard in general but P-time computable over planar graphs, or (3) \#P-hard over planar graphs. Furthermore, $\GH(M)$ in (2) consists of precisely those that involve the P-time FKT algorithm to count planar perfect matchings with a holographic transformation. The dichotomy for entrywise positive and full rank matrices lies at the core of the proof. In this setting, the main tool is a matrix algebra ${A}$ (a vector space with bilinear multiplication) formed by taking the real span of (centered) entrywise logarithms of all realizable matrices from $M$ using planar edge gadgets and polynomial interpolation. We then define a multiplicative homomorphism $F(\cdot)$ on the algebra ${A}$, which turns out to be a polynomial map. The exponents of prime factorization of component polynomials of $F$ induce graph distances for distance-regular graphs. These graphs are either the Hamming graphs or Doob graphs using a classification result for distance-regular graphs (if $\PlGH(M)$ is not \#P-hard), after obtaining their intersection numbers. The dichotomy is proved in either case. We then extend the complexity classification to all nonnegative matrices.

1 Introduction

The paper classifies the complexity of planar graph homomorphism problems and asks whether every planar tractable case arises from holographic transformation with FKT. Its proof develops an algebra of realizable matrices and uses the resulting structure to characterize tractable cases.

1 Introduction

  • The classification separates problems solvable in polynomial time on all graphs, problems hard generally but tractable on planar graphs, and problems hard even on planar graphs.For Boolean-domain #CSP, category (2) consists precisely of problems solvable by Valiant’s holographic algorithm using FKT [1].Source: §1 · p. 4
  • Extending the Boolean-domain classification to larger domains is difficult because tensor products of tractable planar problems create many nontrivial tractable cases.For domain sizes 3 and 4, classifications required individually tailored gadgets and analyses [13] [14].Source: §1 · pp. 4–5
  • Planar edge gadgets and spectral criteria address hardness, but quantum automorphism groups can prevent diagonal separation and obstruct the vertex separation method.The spectral method applies when the relevant largest eigenvalue is multiplicatively independent of the others, including some cases with nontrivial quantum automorphism groups [40].Source: §1 · p. 5
  • The authors characterize realizable matrices by taking entrywise logarithms, which turn entrywise products and real powers into vector-space operations and yield an algebra.Realizability also supports ordinary matrix multiplication after entrywise logarithms, using small thickening, stretching, and differentiation.Source: §1 · pp. 5–6
  • A polynomial homomorphism on this algebra yields graph metrics whose distance-regular structure is classified using Hamming and Doob graphs; excluding Doob graphs leaves tensor products of Ising models as tractable cases.The paper identifies the tractable cases through this graph classification and a planar gadget that rules out the Doob family.Source: §1 · p. 6
  • For entrywise-positive full-rank matrices, the planar problem is #P-hard except for the tractable form in Theorem 1.1; the paper extends its classification to nonnegative matrices.For nonnegative matrices, the theorem describes tractable components as certain rank-one modifications of the matchgate tensor or its bipartite form.Source: §1 · p. 6

2 Preliminaries

The preliminaries define the graph-homomorphism and Holant formulations, establish mathematical conventions, and collect the graph classifications and hardness results used later.

2.1 Definitions and Notations

  • Graph homomorphism problems use a symmetric matrix as edge weights, and planar graph homomorphisms are equivalent to planar Holant problems with equality signatures.The partition function sums products of edge weights over assignments; the Holant formulation places the matrix signature on edges and equality signatures at graph vertices.Source: §2.1 · pp. 6–7

2.2 Linear Algebra

  • The linear-algebra preliminaries define entrywise matrix functions, projections onto the all-ones direction and its orthogonal complement, and spectral decompositions for symmetric matrices.Commuting real symmetric matrices have a common orthonormal eigenbasis.Source: §2.2 · pp. 7–8

Convex analysis

  • The convex-analysis preliminaries specify affine span, convex hull, relative interior, and equivalent definitions of affine forms.A vector with strictly positive coefficients summing to one lies in the relative interior of the convex hull of the listed vectors.Source: Convex analysis · p. 8

2.3 Analytic Functions

  • The analytic-function preliminaries supply Taylor expansion, derivatives, and identity and inverse function theorems for finite-dimensional real spaces.The identity theorem extends vanishing on a nonempty open subset to the entire domain.Source: §2.3 · pp. 8–9

2.4 Distance-regular Graphs and the Hamming Classification

  • Distance-regular graphs have intersection numbers independent of the chosen vertex pair, and graphs matching Hamming intersection numbers are Hamming or Doob graphs.The paper uses this classification for coordinate graphs, then excludes the Doob case by proving planar hardness.Source: §2.4 · pp. 9–10

2.5 Known Dichotomies and Hardness Results

  • The preliminaries record known planar hardness criteria for two-state matrices and Potts models, along with a nonconstant-diagonal hardness result.The cited Potts result gives planar #P-hardness for n-state models with n ≥ 3 and nonnegative interaction weight different from 1.Source: §2.5 · p. 10

3 Planar Edge Gadgets and the Homogeneous Setting

The section develops planar gadget operations that preserve realizability and establishes a homogeneity condition for realizable positive matrices when the planar problem is not #P-hard.

3 Planar Edge Gadgets and the Homogeneous Setting

  • The framework allows realizable matrices to be asymmetric, since ordinary products of symmetric matrices may be asymmetric, and defines realizability through planar reductions.In the homogeneous setting, every realizable matrix has constant diagonal and constant row and column sums.Source: §3 · p. 10, §3.3 · pp. 12–13

3.1 Thickening Gadgets

  • Thickening gadgets realize entrywise products of realizable matrices while preserving planarity and the partition-function value.Polynomial interpolation also realizes arbitrary real entrywise powers when the signature is positive.Source: §3.1 · p. 11

3.2 Stretching Gadgets

  • Stretching gadgets realize ordinary matrix products of realizable matrices while preserving planarity and the partition-function value.Polynomial interpolation likewise extends realizability to arbitrary real matrix powers.Source: §3.2 · p. 11

3.3 The Homogeneous Setting

  • If planar GH(M) is not #P-hard, every positive realizable binary matrix has constant diagonal, row sums, and column sums.The proof realizes these diagonal and sum vectors as unary signatures; nonconstant realizable unaries would imply planar hardness.Source: §3.3 · p. 12

4 The Entrywise Logarithmic Matrix Algebra

Relative to the fixed matrix M, the section forms an entrywise logarithmic matrix algebra from centered logarithms of realizable positive matrices. Exponentiating its elements recovers realizable matrices, while the algebra’s structural properties support a normalized map back to stochastic matrices.

4.1 Definition of the Entrywise Logarithmic Matrix Algebra

  • Centering each realizable matrix’s entrywise logarithm with P yields elements whose row and column sums are zero, and exponentiating any algebra element gives a realizable matrix.The centered logarithm is log◦K − µJ, where µ is the average of the entries of log◦K.Source: §4.1 · pp. 13–14
  • The real vector space A is a transpose-closed matrix algebra, with multiplication closure established using realizable stretched products and differentiation.Every element of A has constant diagonal and zero row and column sums.Source: §4.1 · pp. 14–15

4.2 Basic Properties of the Matrix Algebra

  • A is contained in the auxiliary algebra B, has dimension at most n, and has a multiplicative unit E acting as the identity on every element.The dimension bound follows from dim B ≤ n; E is the projection onto the support of A.Source: §4.2 · p. 16

4.3 Exponentiating Back

  • Normalizing exp◦C by its constant row sum gives K(C), a positive realizable doubly stochastic matrix; products K(C)K(D) are represented as K(H) for an algebra element H.Transposition also commutes with this normalization: K(C)^T = K(C^T).Source: §4.3 · p. 17

5 Polynomial Homomorphism on the Matrix Algebra

This section constructs the polynomial multiplicative homomorphism F on A and establishes affine factorizations of its entries, with multiplicities encoded by affine forms. It also shows that F(X) is realizable for interior points of the cone and that its entries share a common degree, supporting the later use of factorization exponents to induce graph distances.

5 Polynomial Homomorphism on the Matrix Algebra

  • F is a block-diagonal polynomial map on A that extends the local multiplicative homomorphism to the entire space.The normalized entrywise exponential K is not itself multiplicative; F is constructed by pulling back through its S-block and then applying K.Source: §5 · p. 19

5.1 Definition of the Polynomial Homomorphism

  • Every entry of F(X) factors into affine forms, possibly with multiplicities; all entries have common degree d, and transposition induces an involution on the irreducible factors.The factorization exponents are used in later sections to induce graph distances.Source: §5 · p. 19

5.2 When is F(·) Realizable

  • For every X in int C, some C in A satisfies Φ(C) = X, making F(X) realizable; in particular, F(tE) is realizable for every t in (0, 1).int C is the interior in A of the convex hull of the statistic matrices Txy; F has row sums one, and their weighted mean is X.Source: §5 · p. 19, §5.2 · p. 25
  • For every X in the interior of C, F(X) is entrywise positive and realizable; this also holds for F(tE) for every t in (0, 1).The proof places each tE in the interior of C, then applies the result for interior points.Source: §5.2 · pp. 26–27

5.3 Affine Factorization of the Polynomial Homomorphism

  • Every irreducible polynomial factor of each entry of F(X) is affine linear, with affine forms encoding the factors’ multiplicities.For each factor a, ℓa(Txy) equals its multiplicity ha(x, y), and the factor is a nonzero scalar multiple of ℓa.Source: §5.3 · pp. 27, 29, 30
  • All entries F(X)xy have the same positive integer degree.The common degree is the sum of the affine multiplicity forms evaluated at any Txy.Source: §5.3 · p. 30
  • Transposition induces an involution τ on the factor indices, mapping ℓa(X) to ℓa(XT) and exchanging multiplicities ha(x, y) with ha(y, x).Applying transpose twice returns each factor index to itself.Source: §5.3 · pp. 30–31

6 Distances and Color Bijection Induced by the Polynomial Homomorphism

This section develops distance structures and equivalence classes from the polynomial homomorphism F, using endpoint- and complementary-factor exponents and positive semidefinite matrices. It partitions basis indices into orbits and identifies the colors [n] bijectively with a Cartesian product of these classes, with orbit distances that are well-defined, positive, and symmetric.

6.2 Complementary Indices and the Distance ∆ω(·, ·)

  • For complementary-factor orbits ω, ∆ω measures multiplicity decrease; its zero relation Lω is an equivalence relation, and ∆ω depends only on the classes of its arguments.∆ω need not be a distance on [n]; the paper states that it becomes a distance on the set of equivalence classes in the following section.Source: §6 · p. 31, §6.2 · p. 36

6 Distances and Color Bijection Induced by the Polynomial Homomorphism

  • The color bijection maps [n] bijectively to the Cartesian product of the Lω-equivalence classes, capturing the correspondence between indices and tensor factors when M is a tensor product.If Pl-GH(M) is not #P-hard, the paper states that the resulting ∆ω functions must be highly regular graph distances.Source: §6 · p. 31

6.1 Endpoint Indices and the Distance δ(·, ·)

  • Endpoint-factor multiplicities define δ, and perturbation asymptotics plus the homomorphism identity show that δ is a distance on [n].The proof establishes nonnegativity, identity of indiscernibles, symmetry, and the triangle inequality.Source: §6 · p. 31, §6.1 · p. 33
  • For every coordinatewise 0 ≤ β ≤ α(x, y), some z satisfies α(x, z) = β and α(z, y) = α(x, y) − β along a δ-geodesic.Here α(x, y) records the endpoint-factor multiplicities, and δ(x, y) = δ(x, z) + δ(z, y).Source: §6.1 · pp. 33, 35

6.2 Complementary Indices and the Distance ∆ω(·, ·)

  • For each complementary factor r, its gradient Gr lies in the center of A, while its symmetrization Sr is nonzero and positive semidefinite.Source: §6.2 · pp. 36–37
  • Each orbit ω yields a nonzero positive semidefinite matrix Wω in Zsym(A), whose zero-distance relation is an equivalence relation with at least two classes.For singleton orbits Wω = Gr; for two-element orbits Wω = Gr + Gᵀr = 2Sr.Source: §6.2 · p. 40
  • The sets Iω, indexed by ω ∈ Ω, form a partition of I; for every i ∈ I, ⟨Wω, Bi⟩ is either 0 or 1, and these values sum to 1 across ω ∈ Ω.Source: §6.2 · p. 41

6.3 The Color Bijection

  • For any S, T ⊆ Ω, the relations RS and RT compose to RS∪T; when S and T are disjoint, each related pair has a unique intermediate element.This composition property supports the construction of the color bijection.Source: §6.3 · p. 42
  • The map sending each x ∈ [n] to its equivalence class in every Xω is a bijection from [n] to the product of the color-class sets.Injectivity follows from the distances summing to δ; surjectivity constructs an element matching any chosen class in each orbit.Source: §6.3 · pp. 43–44
  • For each ω, hi(x, y) for i ∈ Iω and ∆ω(x, y) depend only on the equivalence classes of x and y in Xω.This makes ∆ω well-defined on pairs of classes.Source: §6.3 · pp. 44–45
  • On Xω, ∆ω is nonnegative, vanishes exactly when its arguments are equal, and is symmetric.These properties are established using the color bijection and the corresponding properties of ∆ω on [n].Source: §6.3 · p. 45

7 Recover Hamming Intersection Numbers

The section constructs coordinate graphs from the functions Δω and recovers their Hamming intersection numbers. It does so by comparing polynomial encodings of Hamming and coordinate-graph distances.

7.3 Hamming Intersection Numbers of Coordinate Graphs

  • For each ω, the coordinate graph Γω joins classes in Xω exactly when Δω equals 1, and its graph distance is Δω.The section establishes that Δω is a distance and that Γω is connected with this graph distance.Source: §7 · p. 45, §7.3 · p. 50

7.1 Distance Polynomials of Hamming Graphs

  • Hamming distance polynomials and their generating functions provide the comparison framework for recovering intersection numbers.The section introduces these polynomials before defining corresponding polynomials for the coordinate graphs.Source: §7 · p. 45, §7.1 · p. 46

7.2 Distance Polynomials of Coordinate Graphs

  • The coordinate-graph polynomials Fω have constant row sum 1 and satisfy Fω(s)Fω(t) = Fω(st), supplying the algebraic identity used in the comparison.The construction uses the coordinate classes and parameters Dω and Qω.Source: §7.2 · pp. 47–49

7.3 Hamming Intersection Numbers of Coordinate Graphs

  • Each coordinate graph Γω is distance-regular and has the same intersection numbers as the Hamming graph H(Dω, Qω).This establishes the section’s main recovery result.Source: §7.3 · p. 51

8 Completing the Dichotomy

For entrywise-positive full-rank M in the homogeneous setting, the proof separates the case with some Qω ≥ 3, which is #P-hard, from the case where every Qω = 2, which yields a tractable Ising tensor. The section completes this dichotomy by proving both branches and applying them to the main classification.

8.1 Hardness Proof

  • For every ω ∈ Ω and real t ∈ (0, 1), Pl-GH(Fω(t)) ≤T Pl-GH(M); polynomial interpolation recovers RG(0) = cω(t)^m · n|Xω| · ZFω(t)(G).Oracle access to RG(0) gives ZFω(t)(G).Source: §8.1 · pp. 52–53
  • If some Qω ≥ 3, Pl-GH(M) is #P-hard; the proof realizes a Hamming-graph matrix whose planar homomorphism problem is already #P-hard.The coordinate graph is either Hamming or Doob; the Hamming case reduces to MQ(1/(Q + 1)), while the Doob case is handled in the appendix.Source: §8.1 · p. 53

8.2 Recover Ising Tensor

  • When every Qω = 2, the coordinate graphs are binary Hamming graphs, yielding a bijection from [n] onto {−1, 1}^d and the sign-matrix representation needed to recover M.The resulting matrix has the form (1.1) up to simultaneous row and column permutation, and Pl-GH(M) is tractable.Source: §8.2 · pp. 53–54

8.3 Completing the Dichotomy

  • In the homogeneous setting, the dichotomy follows by testing the integers Qω: any value at least 3 gives hardness, whereas all values equal to 2 give the tractable form (1.1).Outside the homogeneous setting, Pl-GH(M) is already #P-hard.Source: §8.3 · p. 55

A Exclude the Doob Case

The appendix excludes the Doob-graph case by proving that it also makes Pl-GH(M) #P-hard. It constructs a gadget-transformed tensor product and reduces from the planar homomorphism problem for P4.

A Exclude the Doob Case

  • Replacing each input edge with a Wheatstone gadget transforms N into W(N), while preserving a reduction from Pl-GH(W(N)) to Pl-GH(N).The gadget disrupts the original prime-2 entries, enabling a prime-generator reduction.Source: A Exclude the Doob Case · pp. 57, 60
  • The transformed tensor product admits a specialization reducing Pl-GH(M) to Pl-GH(P4), which is #P-hard.Setting the prime generator 3 and the remaining generators to 1 yields the specialized matrix; its partition function gives access to ZP4(G).Source: A Exclude the Doob Case · p. 60
  • If any coordinate graph Γω is a Doob graph, then Pl-GH(M) is #P-hard.A Doob graph here is a Cartesian product of Shrikhande graphs and complete graphs K4.Source: A Exclude the Doob Case · pp. 56, 60

B Proof of Nonconstant Diagonal Hardness

For positive-definite matrices with positive entries and nonconstant diagonal, the proof establishes planar #P-hardness by ruling out a minimal counterexample. Its route derives rigid diagonal-level structure and ultimately reduces a 2-by-2 #P-hard matrix to that counterexample.

B Proof of Nonconstant Diagonal Hardness

  • Theorem B.1 establishes that a positive-definite matrix with positive entries and nonconstant diagonal has a #P-hard planar graph-homomorphism problem.Source: B Proof of Nonconstant Diagonal Hardness · p. 60
  • The proof assumes a minimal positive-definite counterexample, then derives a contradiction by reducing a 2-by-2 #P-hard matrix to it.The minimal-counterexample setup applies when the matrix has positive entries and nonconstant diagonal and its planar problem is not #P-hard.Source: B Proof of Nonconstant Diagonal Hardness · pp. 60–61
  • Every positive realizable unary must satisfy stringent conditions; otherwise it yields a smaller counterexample, and the diagonal entries must form a geometric progression.The resulting diagonal levels have nearly binomial data, which the proof sharpens to the exact binomial form before the final reduction.Source: B Proof of Nonconstant Diagonal Hardness · pp. 60–61

B.1.1 Polynomial Interpolation

This subsection uses polynomial interpolation to recover realizable signatures and reduce planar graph-homomorphism problems to restricted matrices. It also invokes matrix-analysis facts, including preservation of positive definiteness under entrywise products and the matrix geometric mean.

B.1.1 Polynomial Interpolation

  • For a unary w with entries in (0,1] and a nonempty set C of entries equal to 1, the principal submatrix M_C reduces to the planar problem with M and w.Interpolation isolates assignments taking values only in C.Source: §B.1.1 · pp. 61–62
  • If the multiplicative relation lattice of unary signatures x is contained in that of y, realizability of x implies realizability of y.The proof interpolates partition-function values after replacing occurrences of y with repeated copies of x.Source: §B.1.1 · p. 62
  • Replacing every nonzero entry of a nonnegative symmetric M by 1 yields a matrix K whose planar problem reduces to that for M.Thickening and polynomial interpolation recover the partition function for K.Source: §B.1.1 · p. 63

B.1.2 Matrix Analysis

  • The Schur product theorem preserves positive definiteness under entrywise products, and the matrix geometric mean is defined for positive-definite matrices.The geometric mean is obtained by solving GX^-1G = Y for its unique positive-definite solution.Source: §B.1.2 · p. 63

B.2 Diagonal Levels and Their Data

For a minimal counterexample, the diagonal entries lie in a geometric progression and define integer diagonal levels. Realizable matrices then have constrained row-generating polynomials, forcing the level counts toward binomial form.

B.2 Diagonal Levels and Their Data

  • Every positive realizable unary has entries proportional to a power of the diagonal, u_i = cM_ii^γ.Source: §B.2 · p. 63
  • The diagonal entries of a minimal counterexample satisfy M_ii = κρ^k_i, with integer levels k_i whose minimum is 0, maximum is D, and gcd is 1.The counts of indices at each level are called the diagonal level data.Source: §B.2 · pp. 64–65
  • Comparing coefficients in the row-generating polynomials constrains the diagonal-level counts to a near-binomial form, with every level from 0 through D represented.Source: §B.2 · pp. 65, 67
  • For any realizable positive-definite K, each row generating polynomial has form U(z)^(D−k_i)V(z)^k_i for nonproportional positive linear polynomials U and V.This structure is established for each row using the diagonal levels of the minimal counterexample.Source: §B.2 · p. 66

B.3 Binomial Diagonal Level Data

The proof sharpens near-binomial diagonal-level data to an exact binomial form by showing that both endpoint levels occur once. It uses realizability and parity constraints to establish the required structure.

B.3 Binomial Diagonal Level Data

  • Parity and endpoint-indicator unary signatures are realizable, enabling construction of the parity-modified matrices used in the proof.Source: §B.3 · pp. 68, 71, 72
  • A realizable positive-definite matrix whose nonzero entries only join indices of the same level parity must be diagonal.This parity restriction is applied to a matrix built from a realizable matrix and its parity modification.Source: §B.3 · pp. 69, 71, 72
  • A cycle gadget with K on its cycle edges and Mθ on original edges realizes Qθ as a planar graph-homomorphism instance from M.Each original vertex is replaced by a cycle whose length equals its degree.Source: §B.3 · pp. 70–71, Figure 5 · p. 70
  • Both endpoint levels occur once: n_0 = n_D = 1.The proof rules out repeated endpoint levels using the polynomial structure of A(z).Source: §B.3 · p. 73
  • For every minimal counterexample M with diagonal-level data (n_a) for 0 ≤ a ≤ D, the parameter n satisfies n = 2D.The endpoint counts satisfy n_0 = n_D = 1.Source: §B.3 · p. 73

B.4 Hardness Proof

The section proves that an entrywise positive, full-rank matrix with a nonconstant diagonal yields a #P-hard planar graph homomorphism problem. Its proof reduces planar instances to a two-state matrix defined by the extreme diagonal levels.

B.4 Hardness Proof

  • For a minimal counterexample M with diagonal levels (k1, ..., kn), x0 and xD are the unique indices whose levels are 0 and D, respectively; the matrix W is indexed by {0, 1}.Source: §B.4 · p. 74
  • For every planar graph G, the partition functions satisfy Z_M(G) = Z_W(G)^D.The proof establishes the identity for pinned instances by induction, then specializes to the unpinned case.Source: §B.4 · p. 74
  • W is positive definite with unequal diagonal entries, so its planar problem is hard and reduces to Pl-GH(M), contradicting minimality.This contradiction completes the nonconstant-diagonal hardness argument.Source: §B.4 · p. 75
  • For entrywise positive, full-rank M with a nonconstant diagonal, Pl-GH(M) is #P-hard.The proof establishes this nonconstant-diagonal hardness theorem for the planar problem.Source: §B.4 · p. 75

C Extension to Nonnegative Matrices

The paper extends its planar graph homomorphism dichotomy to nonnegative matrices by classifying the connected components that avoid #P-hardness. The preliminaries supply reductions for removing zero rows, isolating components, and handling thresholded matrices and powers.

C Extension to Nonnegative Matrices

  • Pl-GH(M) is #P-hard unless, after zero rows and columns are removed, each connected component has one of the specified tractable forms.These forms include an Ising tensor with a positive rank-one weighting and a bipartite counterpart; the theorem states that such components are tractable.Source: C Extension to Nonnegative Matrices · pp. 75–76

C.1 Preliminaries

  • For a nonnegative matrix A with entries at most 1, the matrix marking exactly its entries equal to 1 is reducible to Pl-GH(A).The proof recovers the coefficient of product value 1 by querying powers and solving a Vandermonde system.Source: §C.1 · pp. 76–77
  • The problem for any connected component of a nonnegative symmetric matrix reduces to the problem for the full matrix.This component reduction is stated for arbitrary connected components.Source: §C.1 · p. 77
  • Removing zero rows and columns preserves complexity, and the proof reduces to a nonzero connected matrix.The argument assumes non-hardness and derives one of the theorem’s tractable forms.Source: §C.1 · p. 77

C.2 Remove Proportional Rows

This section compresses a nonnegative matrix by grouping proportional rows and proves that the compressed matrix’s planar problem reduces to the original one. A planar gadget enforces the grouping at each original vertex, reproducing the compressed partition function.

C.2 Remove Proportional Rows

  • Rows are grouped when one is a nonzero scalar multiple of the other, and the resulting equivalence classes define the compression of M.The compressed matrix is well-defined because its entries do not depend on the representatives chosen from each class.Source: §C.2 · p. 77
  • Pl-GH(C) reduces to Pl-GH(M) for the compressed matrix C.The construction replaces each vertex by a cycle labeled with RA and attaches the unary s^-1 at every new vertex.Source: §C.2 · pp. 77–78
  • The gadget’s nonzero assignments map every cycle to a single proportional class, so summing them gives Z_M,RA,s(G′) = Z_C(G).This equality establishes the planar reduction from the compressed problem to the original one.Source: §C.2 · pp. 78–79
  • Raising a symmetric nonnegative matrix with pairwise nonproportional rows to a positive integer power preserves that property.Source: §C.2 · p. 79

C.3 Nonbipartite Case

For a nonzero, connected, nonbipartite nonnegative matrix, the section shows that avoiding planar #P-hardness forces an Ising-tensor structure with a positive rank-one weighting. The proof first compresses proportional rows, then uses positive-matrix results and realizable unaries to recover the weighting.

C.3 Nonbipartite Case

  • For positive matrices, the Ising-tensor condition is characterized by the entrywise logarithm belonging to a cube space associated with a bijection to {−1, 1}^d.The section also states that a basis for this space consists of the all-ones matrix and the coordinate sign-product matrices.Source: §C.3 · p. 80
  • A nonnegative connected nonbipartite matrix with pairwise nonproportional rows must be an Ising tensor up to simultaneous permutation if its planar problem is not #P-hard.The proof takes a sufficiently large odd power to obtain an entrywise positive matrix, applies the positive-matrix result, then transfers the form back.Source: §C.3 · p. 81
  • Under non-hardness, all proportional classes have the same multiset of diagonal scaling values s_i.The proof uses realizable unary modifications and equality of elementary symmetric polynomials across classes.Source: §C.3 · p. 82
  • If M is nonzero, connected, and nonbipartite, then non-hardness implies M = K ⊗ wwT up to simultaneous row and column permutation, with K an Ising tensor and w entrywise positive.Source: §C.3 · p. 82
  • The shared multisets allow the original matrix to be reordered into the tensor product K ⊗ wwT.The compressed matrix supplies K, while the common class values supply w.Source: §C.3 · pp. 82–83

C.4 Bipartite Case

For nonzero connected bipartite matrices, the planar problem is #P-hard unless the matrix has the stated Ising-based form. The proof extends this characterization to nonnegative matrices and gives a tractability criterion through decomposition into basic blocks.

C.4 Bipartite Case

  • A nonzero connected bipartite matrix defines a #P-hard planar problem unless it has the specified Ising-based form.The form is an Ising tensor with positive vectors, up to simultaneous row and column permutation.Source: §C.4 · pp. 83, 89
  • Stretching a connected bipartite matrix produces a positive matrix to which the positive-case lemma applies, yielding an Ising tensor form for the original matrix.The proof then recovers the original matrix as an Ising tensor up to the same row and column permutations.Source: §C.4 · pp. 87–88
  • If the planar problem for a nonnegative connected bipartite matrix is not #P-hard, its proportional classes have matching multisets on each side of the bipartition.The proof derives this from agreement of the corresponding polynomials and their roots, counted with multiplicity.Source: §C.4 · pp. 88–89

C.5 Dichotomy for Nonnegative Matrices

  • When the nonnegative-matrix criterion holds, the planar problem is tractable because the matrix decomposes into direct sums of tensor products of basic tractable blocks.The proof of hardness analyzes connected components after removing zero rows and columns, distinguishing nonbipartite and bipartite cases.Source: §C.5 · p. 90
Loading 2610.00828v2…