On $\varepsilon$-Matrix Product Factorization of graphs

Bobby Miraftab; Farzad Maghsoudi; Sho Suda

On $\varepsilon$-Matrix Product Factorization of graphs

T0 review · 0 major / 7 minor · reviewed 2026-08-01 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read Approximate matrix-product factorization lets every complete graph, blow-up, and tree factor with error O(1/n), even where exact factorization is impossible.

desk verdict A clean, small paper that defines a Hamming relaxation of matrix-product factorization and shows the exact modulo-4 obstruction for K_n collapses under O(1/n) error; the constructions check out. read the letter →

arxiv 2607.27407 v1 pith:PGGR3ADJ submitted 2026-07-29 math.CO cs.DM

Farzad Maghsoudi , Bobby Miraftab , Sho Suda This is my paper · ORCID

classification math.COcs.DM MSC 05C5015A23

keywords matrixproductfactorizationapproximateadjacencycompletegraphstreesblow-upHammingdistanceCayley

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper introduces an approximate version of matrix-product factorization of graphs, in which two factor graphs on the same vertex set are required to reproduce the target adjacency matrix except on a small, explicitly marked set of ordered entries. The main results are constructions: every complete graph K_n admits such a factorization with error at most O(1/n), every blow-up of an r-vertex graph admits one with error at most r/n, and every tree on n ≥ 2 vertices admits one with error at most 1/n. These statements hold despite exact factorization being possible for K_n only when n ≡ 1 (mod 4), and impossible for any nontrivial tree. The paper argues that rigid congruence obstructions in the exact theory are zero-error phenomena only: they vanish when a vanishing proportion of entrywise errors is allowed.

What carries the argument

The central identity is the witness decomposition: for each vertex w, the set S_w = N_H(w) × N_K(w) collects all ordered pairs whose two-step walk through w uses an H-edge then a K-edge; outside the error set these sets form an approximate disjoint decomposition of the ordered adjacency relation of the target graph. Two construction tools carry the proofs: deletion of a few vertices from exact cyclic Cayley-graph factorizations of complete graphs, and matchings placed inside the parts of a blow-up so that the K-factor mirrors the structure of the target adjacency matrix.

What would settle it

Compute the exact minimal error δ_MPF(K_6) by exhaustive enumeration of all simple graphs H,K on six vertices; if the minimal number of error entries is not 6 or fewer, the claimed O(1/n) rate for n ≡ 2 (mod 4) would be falsified.

Watch

Extended reading notes

Core claim

The core discovery is a stability principle: the congruence obstructions to exact matrix-product factorization are not stable under small entrywise perturbations. Concretely, the paper constructs, for every complete graph K_n, a pair of simple graphs H,K on the same vertex set such that A(H)A(K) and A(K_n) agree on all but O(n) of the n^2 ordered entries. The construction deletes a small set D of vertices from an exact cyclic factorization of K_N for N ≡ 1 (mod 4) and counts errors as the ordered pairs whose unique two-step witness was deleted; depending on n mod 4, the error count is at most n or n+1. For a blow-up of a fixed r-vertex graph, the construction places a matching inside each pa

Load-bearing premise

The O(1/n) bound for complete graphs rests on the cited exact cyclic factorization of K_N when N ≡ 1 (mod 4): if that base factorization were false, the deletion argument would collapse.

Editorial extensions

If this is right

If correct, the exact congruence classification of complete graphs becomes an asymptotic irrelevance: K_n is O(1/n) close to a product for every n.
The blow-up bound ε ≤ r/n shows that any graph family that is a blow-up of a fixed r-vertex template is approximately factorizable with error shrinking linearly in the template size; complete multipartite graphs are a direct corollary.
The tree bound ε ≤ 1/n shows that sparse graphs, despite failing exact factorability, admit structured factorizations that preserve almost all two-step witness structure.
The walk-count and row-support inequalities give quantitative lower bounds on error in terms of factor degrees, usable as a diagnostic for candidate factorizations.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The deletion idea likely extends to other infinite families with exact factorizations: any exact factorization with a bounded-degree witness structure can be perturbed by deleting vertices, giving O(1/n) error for nearby sizes.
The matching-inside-parts construction suggests a general template principle: graphs that are quotients of a small template by independent set replacement are approximately factorizable; this might extend to graphons or limits of dense graph sequences.
The one-sided bipartite construction is inherently asymmetric; a two-sided analogue, realizing both orientations of almost all edges, would require pairing the two sides symmetrically and may yield improved constants, perhaps optimal O(m/n^2).
The open question about lower bounds on ε for non-factorizable graphs is a natural next step: determining the exact order of δ_MPF(K_n) for n not ≡ 1 mod 4 would confirm the optimality of the O(1/n) rate.

Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You can read this one. It defines ε-matrix-product factorization for graphs—where A(H)A(K) and A(G) may differ on at most εn^2 ordered entries—and proves that the rigid exact obstructions are unstable under vanishing entrywise error. The main results: every K_n admits an ε-factorization with ε = O(1/n) even when n ≠ 1 mod 4; every blow-up of an r-vertex graph admits ε ≤ r/n; every tree admits ε ≤ 1/n.

What is genuinely new is the stability parameter itself, which no one in the exact theory seems to have written down, and the constructions are not just routine scans of known cases. The papers is strongest where it counts: short elementary proofs, explicit error counts, and no fitted constants. I spot-checked the deletion arguments for K_4, the unmatched-column count in the blow-up, and the leaf case in the tree theorem; all are consistent. The paper also openly says it makes no optimality claim and ends by asking for lower bounds.

Soft spots, in proportion: the complete-graph theorem leans entirely on the cited exact cyclic factorization from [10], so if that reference had a gap, the O(1/n) bounds would fall. But I checked the difference set—for S={±1}, T={4q+2,4q+3}, every nonzero residue appears exactly once as t-s—so the base factorization is solid. The bipartite construction is genuinely one-sided: it realizes only the X→U orientation exactly and pays m or m+d_G(y0) for the reverse orientation. That is a limitation of the technique, not a hidden flaw. Also, because the zero-product bound gives 2m/n^2 automatically, the ε ≤ 1/n bound for trees is not impressive on its own; the authors acknowledge this and keep the unnormalized error count as the real claim. Minor typos and a few malformed displays, including the closing question's 'factrizable', do not affect the math.

This is a solid contribution to a small, active literature. It deserves a serious referee, and I would send it to peer review. I would also cite it if I were working on algebraic graph factorization.

Referee Report

0 major / 7 minor

Summary. The paper introduces a Hamming-type relaxation of matrix product factorization: a graph G on n vertices admits an ε-factorization if there exist simple graphs H,K on V(G) and a set E of at most εn² ordered pairs outside which A(H)A(K) agrees with A(G). After recording elementary equivalences and quantitative constraints (witness sets S_w=N_H(w)×N_K(w), walk-count and degree inequalities), the authors give three construction families. Theorem 3.3 shows every K_n has an ε-factorization with ε=O(1/n), with case-by-case bounds for n mod 4, using a cited exact cyclic factorization of K_N for N≡1 mod 4 and deleting vertices. Theorem 4.2 gives an ε≤r/n factorization for any blow-up of an r-vertex graph, exact when every non-isolated part has even size. Section 5 gives one-sided factorizations for bipartite graphs, yielding ε≤1/n for every tree. The paper concludes that exact congruence obstructions are unstable under a vanishing proportion of entrywise errors.

Significance. The main contribution is conceptual: it defines a natural stability parameter δ_MPF and demonstrates that the rigid exact theory becomes flexible under a small number of entrywise errors. The constructions are explicit and the error counts are exact and parameter-free. I checked the arithmetic in Theorem 3.3, the unmatched-column count in Theorem 4.2, and the matching-witness construction in Lemma 5.1/Corollary 5.2; all are consistent. The tree bound ε≤1/n improves on the trivial zero-product bound 2(n-1)/n² for n>2. The sole external dependency is the exact cyclic factorization of K_{4t+1} cited from [10]; the underlying difference-set identity is valid, so this dependency is not a correctness risk. If published, this paper should be useful to researchers studying matrix products of graphs and stability of factorization.

minor comments (7)

[Section 3, after Lemma 3.1] The paragraph beginning 'Here we have an example' defines A(H)=J_2⊗R_{2n}, A(K)=R_2⊗J_{2n} and computes A(H)A(K)=J_{4n}. Since J_{4n} is not the adjacency matrix of a simple graph, this is not an example of an exact factorization; as written it is disconnected from the surrounding argument. Please either remove it or state explicitly that it illustrates that products of 0-1 adjacency matrices need not be graphical.
[Theorem 3.3, proof] In Case 2, the text 'Also 1<N_QN(0)' presumably means '1∉N_QN(0)'. The current symbol is wrong and confusing.
[Section 2] The notation 'A(G)B{(i,j)∈[n]×[n] : ...}' contains a stray 'B' and appears to define the ordered adjacency set of G. It should read 'A(G):={(i,j) ...}' or use a different symbol, to avoid collision with the matrix A(G).
[Definition 3.2] The condition 'x,y, x,y, x^{-1}y∈S' is garbled; it should be simply 'x^{-1}y∈S'.
[Section 5, closing question] Typo: 'non-factrizable' should be 'non-factorizable'.
[Definition 1.1 / Lemma 2.1] The same symbol E is used both for a set of ordered pairs and for a 0-1 matrix. This is standard but should be noted explicitly for readability. Also, the phrase 'disagree in at most εn² entries' in the introduction is strictly equivalent only if E is chosen as the exact disagreement set; a one-sentence clarification would help.
[Section 1/Abstract] 'equivalent matrix, and witness formulations' should be 'equivalent matrix and witness formulations' (stray comma).

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity; constructions are explicit and the only external input is a published exact-factorization theorem.

full rationale

The paper's approximate results are obtained from explicit, parameter-free constructions. Definition 1.1 and Lemma 2.1 are reformulations of the same ε-factorization condition, not derived predictions. Theorem 3.3 uses the exact cyclic factorization of K_N for N≡1 (mod 4), cited from [10] and also described with explicit connection sets S={±1}, T={4q+2,4q+3}; this is a published, self-contained exact result whose assumptions do not include the target approximate statement, so relying on it is legitimate external support rather than a circular reduction. The deletion argument counts errors exactly from the deleted witnesses and the degrees of the cyclic factors, with no fitted parameter being renamed as a prediction. Theorem 4.2 constructs H=G and K as a matching inside parts, directly computing mismatched columns; Lemma 5.1 builds H,K from a matching on one bipartition class and computes the product explicitly. In each case the error bound is a proven consequence of the construction, not an input. There is no evidence that any cited self-result is invoked to forbid alternatives or that any ansatz is smuggled in via citation. The only minor self-citation is the exact K_N factorization, but it is independently checkable and does not make the central claim circular.

Assumptions & free parameters 0 free parameters · 2 assumptions · 0 invented entities

No free parameters: all constructions are explicit and parameter-free. The paper introduces new definitions (ε-factorization, error set, witness set) but no new mathematical objects in the sense of postulated entities with independent evidence burden. The main external dependencies are prior exact-factorization theorems [2,10].

assumptions (2)

domain assumption K_N has exact matrix-product factorization iff N ≡ 1 mod 4, with explicit cyclic factors Cay(Z_N,{-1,1}) and Cay(Z_N,T_N) satisfying A(P_N)A(Q_N)=A(K_N) for N=4t+1.
Invoked as Lemma 3.1 and used as the base construction in Theorem 3.3; cited from [10], not proved in this paper.
domain assumption Every nontrivial tree is not exactly factorizable [2].
Cited for contrast in the abstract and introduction; not used in the proofs of the approximate tree bound.

how reviews work

0 comments

Cite this review

Pith. "Pith review of On $\varepsilon$-Matrix Product Factorization of graphs." pith.science (2026). https://pith.science/paper/PGGR3ADJ

@misc{pith2026260727407,
  author       = {Pith},
  title        = {Pith review of: On $\varepsilon$-Matrix Product Factorization of graphs},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/PGGR3ADJ}},
  note         = {Machine review of arXiv:2607.27407}
}

abstract

We introduce an approximate version of matrix product factorization for graphs. A simple graph $G$ on $n$ vertices is said to admit an $\varepsilon$-matrix product factorization if there exist simple graphs $H$ and $K$ on the same vertex set such that $A(H)A(K)$ and $A(G)$ disagree in at most $\varepsilon n^{2}$ entries. This Hamming-type relaxation preserves, outside the error set, the exact interpretation of each edge as having a unique $H$-then-$K$ two-step witness. We establish equivalent matrix, and witness formulations, showing that the sets $N_H(w)\times N_K(w)$ form an approximate disjoint decomposition of the ordered adjacency relation of $G$, and we derive quantitative constraints involving walk counts and the degrees of the factor graphs. We then construct approximate factorizations for several graph families. Every complete graph $K_n$ has matrix-product-factorization distance $O(1/n)$, despite the exact congruence obstruction that permits exact factorization only when $n\equiv 1\pmod 4$. More generally, a blow-up of a fixed graph on $r$ vertices admits an $\varepsilon$-factorization with $\varepsilon\le r/n$, and the construction is exact whenever every non-isolated part has even order. For bipartite graphs, we give one-sided factorizations that realize one orientation of almost all edges. In particular, every tree on $n\ge2$ vertices admits an $\varepsilon$-factorization with $\varepsilon\le 1/n$, although no nontrivial tree is exactly factorizable. These results show that rigid exact obstructions may disappear under a vanishing proportion of entrywise errors.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

15 extracted references · 12 canonical work pages

[10]

On Matrix Product Factorization of graphs

Farzad Maghsoudi, Babak Miraftab, and Sho Suda. On matrix product factoriza- tion of graphs.Journal of Algebraic Combinatorics, 61(1), 2025.doi:10.1007/ s10801-024-01377-0. Article 12,doi:10.48550/arXiv.2312.08615

work page Pith review arXiv doi:10.48550/arxiv.2312.08615 2025
[1]

On prime matrix product factorizations

Saieed Akbari, Mohamad Parsa Elahimanes, and Bobby Miraftab. On prime matrix product factorizations. 2025.doi:10.48550/arXiv.2512.24864.doi:10.48550/ arXiv.2512.24864

work page doi:10.48550/arxiv.2512.24864 2025
[2]

Spec- tral methods for matrix product factorization.Linear Algebra and its Applications, 709:111–123, 2025.doi:10.1016/j.laa.2025.01.005

Saieed Akbari, Yi-Zheng Fan, Fu-Tao Hu, Babak Miraftab, and Yi Wang. Spec- tral methods for matrix product factorization.Linear Algebra and its Applications, 709:111–123, 2025.doi:10.1016/j.laa.2025.01.005

work page doi:10.1016/j.laa.2025.01.005 2025
[3]

Commuting decompositions of complete graphs

Saieed Akbari and Allen Herman. Commuting decompositions of complete graphs. Journal of Combinatorial Designs, 15(2):133–142, 2007.doi:10.1002/jcd.20112

work page doi:10.1002/jcd.20112 2007
[4]

Commutativity of the adjacency matrices of graphs.Discrete Mathematics, 309(3):595–600, 2009.doi:10

Saieed Akbari, Farideh Moazami, and Abbas Mohammadian. Commutativity of the adjacency matrices of graphs.Discrete Mathematics, 309(3):595–600, 2009.doi:10. 1016/j.disc.2008.09.006

2009
[5]

Arathi Bhat, K

K. Arathi Bhat, K. Manjunatha Prasad, and G. Sudhakara. Some matrix equations of graphs.Advances and Applications in Discrete Mathematics, 17(1):29–48, 2016.doi: 10.17654/AADMJan2016_029_048

work page doi:10.17654/aadmjan2016_029_048 2016
[6]

Arathi Bhat and G

K. Arathi Bhat and G. Sudhakara. Commuting decomposition ofK n1,n2,...,nk through realization of the productA(G)A(G P k ).Special Matrices, 6(1):343–356, 2018.doi: 10.1515/spma-2018-0028

work page doi:10.1515/spma-2018-0028 2018
[7]

Arathi Bhat, G

K. Arathi Bhat, G. Sudhakara, and M. Vinay. Algorithm to check the existence ofH for a givenGsuch thatA(G)A(H) is graphical.Discrete Mathematics, Algorithms and Applications, 14(5):2150159, 2022.doi:10.1142/S1793830921501597

work page doi:10.1142/s1793830921501597 2022

Show all 15 references

[8]

Herman and Bobby Miraftab

Allen W. Herman and Bobby Miraftab. On matrix product factorization of Cay- ley graphs. 2025.doi:10.48550/arXiv.2512.17110.doi:10.48550/arXiv.2512. 17110

2025 doi
[9]

Herman and Bobby Miraftab

Allen W. Herman and Bobby Miraftab. On matrix product factorization in asso- ciation schemes. 2026.doi:10.48550/arXiv.2607.14848.doi:10.48550/arXiv. 2607.14848

2026 doi arXiv
[11]

On the factorability of infinite graphs.Linear Algebra and its Applications, 728:409–418, 2026.doi:10.1016/j.laa

Babak Miraftab, Heydar Radjavi, and Sho Suda. On the factorability of infinite graphs.Linear Algebra and its Applications, 728:409–418, 2026.doi:10.1016/j.laa. 2025.09.011

2026 doi
[12]

Manjunatha Prasad, G

K. Manjunatha Prasad, G. Sudhakara, H. S. Sujatha, and K. V. Soumya. Matrix prod- uct (modulo-2) of graphs.Indian Journal of Pure and Applied Mathematics, 45(6):851– 860, 2014.doi:10.1007/s13226-014-0093-4. 15

2014 doi
[13]

Manjunatha Prasad, G

K. Manjunatha Prasad, G. Sudhakara, H. S. Sujatha, and M. Vinay. Matrix product of graphs. InCombinatorial Matrix Theory and Generalized Inverses of Matrices, pages 41–56. Springer India, 2013.doi:10.1007/978-81-322-1053-5_4

2013 doi
[14]

On a construction using commuting regular graphs.Discrete Mathematics, 340(3):532–540, 2017.doi:10.1016/j.disc

Marius Somodi, Katie Burke, and Jesse Todd. On a construction using commuting regular graphs.Discrete Mathematics, 340(3):532–540, 2017.doi:10.1016/j.disc. 2016.07.018

2017 doi
[15]

Sudhakara, Vinay Madhusudanan, and K

G. Sudhakara, Vinay Madhusudanan, and K. Arathi Bhat. On products of graph ma- trices. InApplied Linear Algebra, Probability and Statistics—A Volume in Honour of C. R. Rao and Arbind K. Lal, Indian Statistical Institute Series, pages 337–377. Springer Nature Singapore, 2023.do...

2023 doi

Pith tools

Reviewed August 1, 2026 · model on record in the stance chip above.

[1] [10]

On Matrix Product Factorization of graphs

Farzad Maghsoudi, Babak Miraftab, and Sho Suda. On matrix product factoriza- tion of graphs.Journal of Algebraic Combinatorics, 61(1), 2025.doi:10.1007/ s10801-024-01377-0. Article 12,doi:10.48550/arXiv.2312.08615

work page Pith review arXiv doi:10.48550/arxiv.2312.08615 2025

[2] [1]

On prime matrix product factorizations

Saieed Akbari, Mohamad Parsa Elahimanes, and Bobby Miraftab. On prime matrix product factorizations. 2025.doi:10.48550/arXiv.2512.24864.doi:10.48550/ arXiv.2512.24864

work page doi:10.48550/arxiv.2512.24864 2025

[3] [2]

Spec- tral methods for matrix product factorization.Linear Algebra and its Applications, 709:111–123, 2025.doi:10.1016/j.laa.2025.01.005

Saieed Akbari, Yi-Zheng Fan, Fu-Tao Hu, Babak Miraftab, and Yi Wang. Spec- tral methods for matrix product factorization.Linear Algebra and its Applications, 709:111–123, 2025.doi:10.1016/j.laa.2025.01.005

work page doi:10.1016/j.laa.2025.01.005 2025

[4] [3]

Commuting decompositions of complete graphs

Saieed Akbari and Allen Herman. Commuting decompositions of complete graphs. Journal of Combinatorial Designs, 15(2):133–142, 2007.doi:10.1002/jcd.20112

work page doi:10.1002/jcd.20112 2007

[5] [4]

Commutativity of the adjacency matrices of graphs.Discrete Mathematics, 309(3):595–600, 2009.doi:10

Saieed Akbari, Farideh Moazami, and Abbas Mohammadian. Commutativity of the adjacency matrices of graphs.Discrete Mathematics, 309(3):595–600, 2009.doi:10. 1016/j.disc.2008.09.006

2009

[6] [5]

Arathi Bhat, K

K. Arathi Bhat, K. Manjunatha Prasad, and G. Sudhakara. Some matrix equations of graphs.Advances and Applications in Discrete Mathematics, 17(1):29–48, 2016.doi: 10.17654/AADMJan2016_029_048

work page doi:10.17654/aadmjan2016_029_048 2016

[7] [6]

Arathi Bhat and G

K. Arathi Bhat and G. Sudhakara. Commuting decomposition ofK n1,n2,...,nk through realization of the productA(G)A(G P k ).Special Matrices, 6(1):343–356, 2018.doi: 10.1515/spma-2018-0028

work page doi:10.1515/spma-2018-0028 2018

[8] [7]

Arathi Bhat, G

K. Arathi Bhat, G. Sudhakara, and M. Vinay. Algorithm to check the existence ofH for a givenGsuch thatA(G)A(H) is graphical.Discrete Mathematics, Algorithms and Applications, 14(5):2150159, 2022.doi:10.1142/S1793830921501597

work page doi:10.1142/s1793830921501597 2022