{"id":"arxiv:2508.04081","kind":"preprint","title":"Exact Matching in Matrix Multiplication Time","authors":["Ryotaro Sato","Yutaro Yamaguchi"],"author_count":2,"year":2025,"published":"2025-08-06","venue":null,"cited_by":null,"doi":null,"arxiv_id":"2508.04081","nct_id":null,"source_url":"https://arxiv.org/abs/2508.04081","archive_url":"https://space-kitty.com/papers/arxiv:2508.04081","updated":"2026-08-10","pmid":null,"pmcid":null,"openalex_id":null,"pdf_url":"https://arxiv.org/pdf/2508.04081","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_license":"CC0-1.0 (arXiv descriptive metadata)","license":null,"is_open_access":false,"retracted":false,"peer_reviewed":false,"categories":["cs.DS","cs.SC","math.CO"],"details":null,"provenance":"arxiv","attribution":"Abstract: arXiv descriptive metadata (CC0). Thank you to arXiv for use of its open access interoperability. This service was not reviewed or approved by, nor does it necessarily express or reflect the policies or opinions of, arXiv.","topics":[],"cited_in_dossiers":[]}