On $\epsilon$-Matrix Product Factorization of graphs

Abstract

We introduce an approximate version of matrix product factorization for graphs. A simple graph $G$ on $n$ vertices is said to admit an $\epsilon$-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 $\epsilon 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(\mathrm{mod}4)$. More generally, a blow-up of a fixed graph on $r$ vertices admits an $\epsilon$-factorization with $\epsilon \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\ge 2$ vertices admits an $\epsilon$-factorization with $\epsilon \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.

Topics & keywords