Source-linked AI summary
Fast Odd-Permutation Sums in Characteristic Two and Shortest Even Directed Cycles
Hanqing Li
TL;DR
Although determinant and permanent coincide in characteristic two, the odd-permutation sum contains parity-class information that neither gives separately. The paper evaluates Φ and its full derivative matrix using complementary-minor aggregation and singular-input handling, with a matrix-multiplication-time bound. On a graph without an even cycle, the algorithm always reports that fact correctly.
Problem
Although determinant and permanent coincide in characteristic two, the odd-permutation sum contains parity-class information that neither gives separately.
Source: §1 · p. 1Method
The paper evaluates Φ and its full derivative matrix using complementary-minor aggregation and singular-input handling, with a matrix-multiplication-time bound.
Source: §1 · p. 2, §8 · p. 12Results
On a graph without an even cycle, the algorithm always reports that fact correctly.
Source: §1 · p. 2Takeaways & Limitations
The evaluator applies to arbitrary matrices over characteristic-two fields, including singular inputs, and supports shortest even-cycle length and arc-support computation.
Source: §1 · p. 2, §8 · p. 12Small-instance implementations using classical elimination or naive polynomial convolution do not implement the stated fast asymptotic bounds.
Source: §8 · p. 12
Abstract
from arXiv · showhide
For a matrix $A$ over a field of characteristic two, let $\Phi(A)$ be the sum of its permutation monomials indexed by odd permutations. Although determinant and permanent coincide in this characteristic, this parity sub-sum retains information that neither gives separately. We show that $\Phi(A)$ and all its first partial derivatives can be computed deterministically in $O(n^\tau)$ field operations for every $n\times n$ matrix, where $2<\tau\le3$ is any fixed admissible matrix multiplication exponent. The result includes singular matrices and the binary field. An inversion-count identity expresses $\Phi$ through complementary minors. For invertible matrices, a decomposition along two binary interval trees aggregates these minors by matrix multiplication; a Boolean border of constant size handles the remaining ranks. We also give an explicit matrix formula for the full gradient. Applied to $\Phi(I+zW)$ for a randomly weighted adjacency matrix $W$, the evaluator computes the shortest even directed-cycle length in $\widetilde{O}(n^{\tau+1})$ bit operations, improving the $\widetilde{O}(n^{\tau+3})$ bound of Bj\"orklund, Husfeldt, and Kaski with the same multiplication exponent. The same time bound recovers the union of the arcs of all shortest even cycles with high probability, and deterministically outputs the cycle under a unique-shortest-cycle promise. For general graphs, exact maintenance of a nonzero coefficient gives an $\widetilde{O}(n^4)$ algorithm that outputs a shortest even cycle with high probability. Complementary extraction methods improve this bound for short cycles and for cycles that omit few vertices.
1 Introduction
The paper gives a deterministic matrix-multiplication-time evaluator for the odd-permutation sum and its full gradient over characteristic-two fields, then applies it to shortest even directed cycles. Its graph algorithms recover shortest-cycle length and arc support, with separate methods for producing an actual cycle.
1 Introduction
- The odd-permutation sum remains distinct information even though determinant and permanent coincide in characteristic two; the paper’s proportional-row expansion is not claimed as a new combinatorial device.The parity cycle-cover polynomial framework originates with Vazirani and Yannakakis.Source: §1 · pp. 1, 3
- For any characteristic-two field and any input matrix, Φ and its full derivative matrix are computed deterministically in O(n^τ) field operations, without nonsingularity or field-size assumptions.Under the stated workspace assumption, the algorithm stores O(n^2) field elements.Source: §1 · pp. 1–2
- With probability 1 − O(n^-3), the graph algorithm computes the shortest even-cycle length and the union of arcs in all shortest even cycles in eO(n^(τ+1)) bit operations.It always correctly reports an even-cycle-free graph.Source: §1 · p. 2
- With a unique shortest even cycle, setting every arc weight to one deterministically recovers it; without uniqueness, the support may combine arcs from different cycles and is not a witness.A separate randomized algorithm outputs an actual simple even cycle with probability 1 − O(n^-3) when one exists.Source: §1 · p. 2
- For invertible inputs, inversion-count expansion and Jacobi’s identity reduce Φ to complementary minors, which binary interval trees aggregate in O(n^τ) time.A constant-size Boolean border handles the remaining singular ranks; the same complementary-minor identity shows Φ vanishes at corank at least three.Source: §1 · pp. 2–3
- An explicit full-gradient formula extends the derivative computation to all ranks, with at most eight bordered evaluations needed when gradients remain nonzero at corank three.The gradient matrix is oriented so its ith column gives coefficients for replacing row i.Source: §1 · pp. 2–3
2 Preliminaries
The preliminaries fix notation and characteristic-two identities used to express the odd-permutation sum through complementary minors. They also specify the field and interpolation tools used by the algorithms.
2 Preliminaries
- For equally sized index sets, A[I,J] denotes the submatrix and A[−I,−J] its complementary submatrix; the empty determinant is one.The paper sets Φ to zero for matrices of order zero or one.Source: §2 · p. 3
- Jacobi’s complementary-minor identity relates minors of an invertible matrix to complementary minors of its inverse, while matrix-multiplication-time routines supply determinant, inverse, and rank operations.For graph algorithms, the paper uses F2^d with d = O(log n) and the Schwartz–Zippel bound; degree-at-most-n interpolation at n+1 fixed field elements costs O(n^2) operations.Source: §2 · pp. 3–4
- In characteristic two, determinant equals permanent, and the odd-permutation sum is the parity cycle-cover enumerator for permutations with an odd number of even-length cycles.The identity 2Φ = per − det holds over the integers; the paper defines Φ directly as a polynomial in characteristic two.Source: §2 · pp. 3–4
3 Fast Evaluation on Invertible Matrices
An inversion-count expansion expresses the odd-permutation sum through complementary minors, which are aggregated efficiently for invertible matrices by two binary interval trees. The resulting block traces can be evaluated in O(n^τ) operations.
3.1 An inversion-count identity
- The parity of a permutation's inversion count is its oddness indicator, yielding an expansion in products of two entries and complementary determinants.For rank at most n−3, the complementary determinants vanish.Source: §3.1 · p. 4
3.2 Two interval trees and block traces
- Two interval trees assign each ordered quadruple of indices to one row-node and column-node pair, whose block trace accounts for that term exactly once.The lowest common ancestors of the ordered index pairs determine the unique blocks.Source: §3.2 · p. 5
- All block traces together cost O(N^τ) operations and O(N^2) space by computing products with the smaller output dimension.Padding to the next power of two preserves Φ; the smaller-output-size choice is necessary for the claimed bound.Source: §3.2 · p. 5
- The depth-cost sum uses τ>2; at τ=2 this particular summation gives O(n^2 log^2 n), so no endpoint bound is claimed.After computing the inverse and determinant, the interval-tree sums complete the invertible case.Source: §3.2 · p. 5
4 Singular Inputs by a Boolean Border
A Boolean border converts singular-input evaluations into evaluations on invertible matrices. This handles every rank, including over F2, within the same O(n^τ) bound.
4 Singular Inputs by a Boolean Border
- The complementary-minor identity makes Φ vanish when corank is at least three, leaving only coranks one and two for scalar evaluation.A rank-size invertible submatrix supplies the initial rank block.Source: §4 · p. 6
- The border construction works over F2 and, with the invertible case, gives deterministic O(n^τ) evaluation for every characteristic-two field and every input rank.The proof's independent row and column permutations analyze invertibility only; evaluation uses the matrix in its original order.Source: §4 · p. 6
- For corank k=1 or 2, at most 2k≤4 bordered matrices of order at most n+2 are invertible and suffice to extract Φ(A).The border identity holds as a polynomial identity in the added variables.Source: §4 · p. 6
5 An Explicit Gradient at Every Rank
An explicit matrix expression computes the full gradient from invertible-matrix quantities, while proportional-row identities provide replacement coefficients. Bordering extends the derivative computation to singular inputs, including corank three.
5.1 Proportional rows and replacement coefficients
- Once F, B, and Δ are known, the full-gradient formula costs two matrix multiplications and O(n^2) additional operations.The gradient matrix expression is given for invertible A.Source: §5.1 · p. 7
- A proportional-row identity yields all replacement-coefficient columns at once by multiplying the matrix with columns h on the left by B.For a specified row, its coefficients can then be computed in O(n^2) operations when A, B, Δ, and F are available.Source: §5.1 · pp. 6–7
5.2 Why corank three matters
- Scalar vanishing at corank three does not imply gradient vanishing: a derivative can leave Φ(J3), so this rank case must be handled.When corank is at least four, both Φ and its gradient vanish.Source: §5.2 · pp. 7–8
- For coranks one through three, differentiating the fixed-border identity uses at most eight invertible bordered matrices and remains valid at a rank boundary.For corank at least four, one-row replacements have rank at most n−3 and their Φ-values vanish.Source: §5.2 · p. 8
6 Shortest Even Cycles and Their Arc Support
The minimum nonzero coefficient of the cycle polynomial identifies the shortest even directed-cycle length, and gradient evaluations identify its arc support. Randomized interpolation gives the length and arc union, while deterministic cycle output is provided under a unique-shortest-cycle promise.
6.1 The minimum coefficient
- If the shortest even directed-cycle length is ℓ, the cycle polynomial has zero coefficients below degree ℓ, and its degree-ℓ terms correspond to cycles distinguished by arc sets.If no even cycle exists, Q is identically zero.Source: §6.1 · p. 8
6.2 Fixed-point interpolation for the length
- The interpolation algorithm returns ℓ with probability at least 1−ℓ/|F|≥1−n^-3 and never underestimates it.It always returns +∞ on an input without an even cycle; its bit complexity is eO(n^(τ+1)).Source: §6.2 · p. 9
- Repeated runs reduce the stated error bound to (ℓ/|F|)^h, and even-cycle existence testing takes eO(n^τ) bit operations with no false positives.The length method's randomized object is the coefficient polynomial before specialization, not the individual interpolation points.Source: §6.2 · p. 9
6.3 All shortest-cycle arcs by one gradient pass
- The target-degree arc polynomial is nonzero precisely when its arc belongs to a shortest even cycle.The arc polynomial collects terms of Q that use that arc.Source: §6.3 · p. 9
- A second gradient pass recovers the union of shortest-cycle arcs within O(n^(τ+1)) operations, with the stated high-probability guarantee.The method processes fixed points successively and uses quadratic space.Source: §6.3 · p. 9
- Under a unique-shortest-cycle promise, the cycle can be output deterministically in eO(n^(τ+1)) bit operations, but the algorithm does not certify that promise on unrestricted inputs.With weights all one, the two interpolation passes recover the unique cycle's arcs.Source: §6.3 · p. 10
6.4 Vertex deletion and the limits of coefficient information
- Deleting a vertex yields all coefficients for the remaining graph in O(n^(τ+1)) operations, but that batch must be recomputed after each deletion.The current graph changes after a deletion.Source: §6.4 · p. 10
- The union of shortest-cycle arcs can contain longer cycles, and an allowed cancellation event can produce a finite degree that is not an actual cycle length.The length algorithm never underestimates the optimum and has one-sided error for existence, while any cycle produced by the witness algorithm is actual.Source: §6.4 · p. 10
7 Extracting a Cycle by Exact Row Maintenance
Exact row maintenance preserves a nonzero even-cycle coefficient while reducing the graph to one of outdegree at most one, from which a shortest cycle can be extracted. The method uses truncated-series evaluation and has an eO(n^4) worst-case bound.
7.1 Computing in a truncated series ring
- Truncated evaluation computes Φ(I + zW) mod z^(L+1), with its inverse and determinant, in eO(n^τL) operations and O(n^2L) space.Precision doubling searches for a positive even coefficient, and after finding degree r, subsequent maintenance needs only precision r.Source: §7.1 · pp. 10–11
7.2 A single-row update
- A single-row replacement updates Φ, the determinant, and the inverse using the old state, at a cost of O(n^2) ring operations plus one unit inversion.The unchanged artificial loops ensure the scalar d has constant term 1, so the inverse remains legitimate in the truncated ring.Source: §7.2 · p. 11
7.3 Preserving a nonzero coefficient
- Each row replacement preserves a nonzero degree-r coefficient, and the final graph has maximum original outdegree one while retaining an even cycle.If r is the original shortest even-cycle length, the final graph's shortest even cycle also has length r.Source: §7.3 · p. 11
- When retaining one outgoing arc, the procedure requires Lq = 0 so its contribution cannot cancel the retained artificial-loop contribution.A nonzero arc contribution alone would not guarantee preservation of the coefficient.Source: §7.3 · p. 11
- A nonzero degree-r term yields an even cycle, and the outdegree bound permits cycle extraction by following successors in linear time.When r is optimal, a surviving odd permutation on r moved vertices must consist of one r-cycle and fixed points.Source: §7.3 · p. 11
- With probability at least 1 − n^-3, the randomized procedure outputs a shortest even cycle; every output is an actual simple cycle, and cycle-free inputs are reported correctly.Its worst-case running time is eO(n^4).Source: §7.3 · p. 12
8 Discussion
The paper’s algebraic evaluator works independently of graph encoding, while graph witness extraction remains slower than shortest-length and support computation except under a uniqueness promise. Fast asymptotic bounds also have a workspace caveat for direct truncated-series extraction.
8 Discussion
- The evaluator computes Φ and its full first derivative for any matrix over any characteristic-two field in O(n^τ) operations.Interval decomposition aggregates complementary minors, and constant-size bordering handles singular inputs without a field-size assumption.Source: §8 · p. 12
- Length and simultaneous shortest-cycle support take eO(n^(τ+1)) time, but exact general witness extraction has an eO(n^4) bound.A unique-shortest-cycle promise permits deterministic witness output, but testing that promise is not part of the result.Source: §8 · p. 12
- Scalar and gradient algorithms can use quadratic workspace, whereas direct truncated-series extraction can require cubic workspace.Small-instance implementations using classical elimination or naive polynomial convolution do not by themselves implement the stated fast asymptotic bounds.Source: §8 · p. 12
A Complementary Bounds for Witness Extraction
The appendix presents two extraction methods that complement exact row maintenance and describes how to choose between them without knowing the optimum length. Its randomized choices use a binary extension field sized from the vertex count.
A Complementary Bounds for Witness Extraction
- The appendix's complementary extraction methods are selected without assuming the optimum length is known, and use a binary extension field with size at least n^6 and degree O(log n).The field is selected from the original vertex count n.Source: A Complementary Bounds for Witness… · p. 12
A.1 Short cycles by grouped arc deletions
Grouped arc deletions use randomized containment queries to isolate a shortest cycle of target length ℓ. Under correct queries, the retained arcs form one ℓ-cycle, with a query bound depending on ℓ and the arc count.
A.1 Short cycles by grouped arc deletions
- For target length ℓ, a nonzero coefficient [z^ℓ]Φ(I + zWH(w)) characterizes whether H contains an ℓ-cycle, and randomized queries cost eO(n^τℓ) field operations.Each query has no false positives and false-negative probability at most ℓ/|F|.Source: §A.1 · p. 12
- A balanced tree of arc blocks deletes a block when its removal preserves an ℓ-cycle, recursively splitting blocks whose deletion does not.Retained singleton arcs are those whose deletion fails the containment query.Source: §A.1 · p. 12
- With all queries correct, the final arc set is one ℓ-cycle and uses at most 1 + 2ℓ(h + 1) queries, where h = ⌈log2 max{1, m}⌉.Every deletion preserves a target cycle, and an arc outside a final target cycle would be dispensable.Source: §A.1 · p. 13
- The method takes eO(n^τℓ^2) time and O(n^2ℓ) field elements of space; its final arc set is checked for exactly ℓ arcs forming one even cycle.The verification is linear in the residual arc count and ℓ, including on erroneous executions.Source: §A.1 · p. 13
A.2 Cycles omitting few vertices
The section combines deletion-based extraction for cycles omitting few vertices with adaptive selection among three methods. It gives a high-probability shortest-cycle guarantee while bounding every execution, including erroneous initial specializations.
A.2 Cycles omitting few vertices
- eO((n−ℓ)n^τ+1) time and quadratic space suffice for deletion extraction when the target length ℓ is correct.A successful run makes n−ℓ deletions, and each round can find a valid deletion with failure probability at most ℓ/|F| without a union bound over vertices.Source: §A.2 · p. 13
- Fixed weights can make every deletion coefficient zero despite an existing target cycle, so deletion extraction uses fresh weighting.The example has three two-cycles sharing a center; exact row maintenance avoids this issue by using an additive identity.Source: §A.2 · p. 13
A.3 Selecting a method and bounding every execution
- With probability 1 − O(n^-3), the combined algorithm returns a shortest cycle; every execution takes at most eO(n^4) bit operations and uses at most O(n^3) field elements.The output is an actual simple even cycle, no detection, or failure; the combined algorithm makes no unconditional quadratic-space claim.Source: §A.3 · pp. 14–15
- The algorithm compares f1(r)=n^3r, f2(r)=n^τr^2, and f3(r)=(n−r+1)n^τ+1+r^3, then runs the least-cost method.It retains the initial arc weights for exact maintenance and uses fresh randomness for the query-based and deletion methods.Source: §A.3 · p. 15