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+\lambda A_1$ is nonsingular for some $\lambda\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^\omega)$ 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^\omega)$ 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.
From: Yutaro Yamaguchi [view email]
[v1]
Wed, 6 Aug 2025 04:51:07 UTC (14 KB)
[v2]
Mon, 10 Aug 2026 01:18:43 UTC (22 KB)
此内容由惯性聚合(RSS阅读器)自动聚合整理，仅供阅读参考。 原文来自 — 版权归原作者所有。