# Exact Matching in Matrix Multiplication Time

Preprint · Ryotaro Sato, Yutaro Yamaguchi

- Archive id: arxiv:2508.04081
- Published: 2025-08-06
- arXiv: https://arxiv.org/abs/2508.04081
- Source URL: https://arxiv.org/abs/2508.04081
- PDF: https://arxiv.org/pdf/2508.04081
- Provenance: arxiv

## Abstract

Let $A\_0,A\_1\\in\\mathbf{F}^{n\\times n}$ be square matrices over a finite field $\\mathbf{F}$ and consider the matrix pencil $A\_0+yA\_1$ with indeterminate $y$. We observe that, once $A\_0+λA\_1$ is nonsingular for some $λ\\in\\mathbf{F}$, the polynomial $\\det(A\_0+yA\_1)$ can be reconstructed by computing one determinant, one inverse matrix, and the characteristic polynomial of a single matrix. Consequently, this determinant polynomial can be computed in $\\mathrm{O}(n^ω)$ field operations, avoiding the polylogarithmic overhead of a general polynomial-matrix determinant algorithm in this special setting. Applying this observation to random evaluation of the Tutte matrix of a graph, we obtain a matrix-multiplication-time randomized algorithm for the so-called exact matching problem. Specifically, one can decide, simultaneously for all $k$, whether a given $0/1$-weighted graph has a perfect matching of weight exactly $k$ in $\\mathrm{O}(n^ω)$ field operations, where $n$ denotes the number of vertices in the graph. We also discuss the analogous extension to the exact linear matroid parity problem and its consequences for a perfect packing of Mader's $\\mathcal{S}$-paths of minimum total length and for a shortest cycle through three specified vertices.

_Abstract reproduced under CC0-1.0 (arXiv descriptive metadata)._

---
Space Kitty Archive · https://space-kitty.com · API: https://space-kitty.com/api/v1 · MCP: https://space-kitty.com/mcp · Premium: $0.20/request via x402 (Base Sepolia (testnet)). Metadata: arXiv (CC0), OpenAlex (CC0), Europe PMC (CC BY/CC0 works), ClinicalTrials.gov.