On evaluation of permanents

Andreas Björklund, Thore Husfeldt, Petteri Kaski, Mikko KoivistoarXiv 2009 · OpenReview

Introduction

The permanent of a matrix is a fundamental construction in combinatorics, appearing in problems ranging from graph theory (counting perfect matchings) to quantum physics. While its definition mirrors that of the determinant—differing only by the absence of alternating signs—its computational complexity is vastly different. While the determinant can be computed in polynomial time via Gaussian elimination, the permanent is #P-complete, making it one of the most challenging problems in algorithmic complexity.

This paper addresses the evaluation of the permanent for rectangular $m \times n$ matrices ($m \le n$) over various algebraic structures, including semirings and rings, both commutative and non-commutative. The authors present a suite of algorithms that optimize computation by leveraging the "transposition" of traditional methods, focusing complexity on the smaller dimension $m$.

The Computational Challenge

The permanent of an $m \times n$ matrix $A$ is defined as the sum of products of $m$ elements, where no two elements share a row or column. Most existing literature focuses on square matrices over fields. However, many practical applications—such as solving sequencing problems or counting matchings—involve rectangular matrices or entries from semirings (where subtraction is unavailable) or non-commutative rings.

The authors aim to provide the most efficient simple algorithms for these diverse mathematical settings, particularly for cases where $m$ is significantly smaller than $n$.

Algorithmic Approaches by Algebraic Structure

The paper categorizes its methods based on the properties of the underlying algebraic structure:

1. General Semirings

In the most restrictive case—general semirings—the authors utilize a dynamic programming (DP) approach inspired by the Bellman–Held–Karp algorithm. This method tabulates results for subsets of columns, resulting in a time complexity of $O(m \binom{n}{\downarrow m})$.

2. Commutative Semirings: The Transposed DP

The core innovation for commutative semirings is the "Transposed DP." Traditional DP iterates through rows and subsets of columns. By transposing this logic—iterating through columns and subsets of rows—the state space is reduced from $2^n$ to $2^m$. Since $m \le n$, this provides a significant speedup when the matrix is wide.

3. General Rings

When the structure is a ring (allowing subtraction), the authors employ subset convolution. By using a divide-and-conquer strategy combined with Moebius transform techniques, they achieve a complexity bound of $O(m \binom{n}{\downarrow m/2})$.

4. Commutative Rings: Transposed Ryser’s Formula

For commutative rings, the authors adapt Ryser’s classic inclusion-exclusion formula. By applying the transposition principle, they derive an algorithm that is linear in $n$ and exponential only in $m$. This approach is particularly space-efficient, requiring only $O(n)$ space.

Key Results and Complexity Bounds

The primary contribution of the paper is summarized in the following complexity bounds for an $m \times n$ matrix ($m \le n$):

  • General Semirings: Time $O(m \binom{n}{\downarrow m})$, Space $O(\binom{n}{\downarrow m})$.
  • Commutative Semirings: Time $O(m(n - m + 1)2^m)$, Space $O((n - m + 1)2^m)$.
  • General Rings: Time $O(m \binom{n}{\downarrow m/2})$, Space $O(\binom{n}{\downarrow m/2})$.
  • Commutative Rings: Time $O((mn - m^2 + n)2^m)$, Space $O(n)$.

These results represent a significant improvement over previous state-of-the-art algorithms, particularly in the commutative ring setting where the space complexity is reduced to linear in $n$. The authors demonstrate that these bounds can be achieved using relatively simple algorithms rather than more involved algebraic techniques.

Discussion and Limitations

The efficiency of the "transposed" algorithms relies heavily on the commutativity of the matrix entries. While the authors suggest a theoretical "transposed definition" of the permanent for non-commutative cases, it does not align with the standard definition used in most applications.

Furthermore, the paper focuses on exact evaluation. For instances where $m$ is large, the exponential nature of these algorithms remains a bottleneck. In such cases, approximation algorithms or specialized techniques like the Fast Fourier Transform (FFT) for complex numbers—which might reduce time to $O(n \log^2 m)$—remain areas for further exploration.

Conclusion

By systematically applying the principle of transposition to dynamic programming and inclusion-exclusion methods, this paper provides a definitive guide to the exact evaluation of permanents for rectangular matrices. The results demonstrate that the computational cost of the permanent is highly sensitive to the algebraic properties of the entries and the aspect ratio of the matrix.

Summary updated

Abstract

We study the time and space complexity of matrix permanents over rings and semirings.
BibTeX
@misc{bjorklund2009evaluation,
  author = {Andreas Björklund and Thore Husfeldt and Petteri Kaski and Mikko Koivisto},
  title = {{On evaluation of permanents}},
  year = {2009},
  eprint = {0904.3251},
  archivePrefix = {arXiv},
  url = {https://arxiv.org/abs/0904.3251},
}

Loading related content...

Figure