An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality
Aditi Laddha, Madhusudhan Reddy Pittu · 2025
Read An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality by Aditi Laddha, Madhusudhan Reddy Pittu (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2509-08121.txt.
Introduction
Aditi Laddha and 1 co-author find new upper bounds for a famously hard count in a 2025 paper. The count is the permanent of a matrix. It looks like the determinant, but with no minus signs to cancel terms. Exact values are out of reach for large inputs. Bounds are the next best thing.
The work starts from a new formula in the style of Schur, built on a new kind of matrix inverse. A step-by-step process, much like Gaussian elimination, then gives bounds a computer can find. The bounds are best when the matrix is close to diagonal in shape. Permanents count matchings in networks and arise in quantum optics, so tighter bounds have real use.
Catalog record
| CREATOR | Aditi Laddha, Madhusudhan Reddy Pittu |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 56 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2509-08121
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
An Algorithmic Upper Bound for Permanents via a Permanental Schur Inequality Aditi Laddha, Madhusudhan Reddy Pittu Abstract Computing the permanent of a non-negative matrix is a computationally challenging, #P-complete problem with wide-ranging applications. We introduce a novel permanental analogue of Schur’s determinant formula, leveraging a newly defined permanental inverse . Building on this, we introduce an iterative, deterministic procedure called the permanent process , analogous to Gaussian elimination, which yields constructive and algorithmically computable upper bounds on the permanent. Our framework provides particularly strong guarantees for matrices exhibiting approximate diagonal dominance-like properties, thereby offering new theoretical and computational tools for analyzing and bounding permanents. 1 Introduction The permanent of a matrix, despite its deceptively simple definition, is notoriously difficult to compute. It is well-known that the exact computation of the permanent is #P-complete [ 22 ] , situating it at the forefront of complexity theory and establishing its computational intractability for all but trivially sized matrices. Despite this difficulty, permanents play a critical role across diverse areas such as combinatorics, graph theory (particularly in counting perfect matchings in bipartite graphs [ 12 ] ), quantum computing (specifically within boson sampling experiments aimed at demonstrating quantum advantage [ 1 ] ), and statistical physics (e.g., in dimer covering models [ 8 ] ). Due to the permanent’s computational complexity, significant effort has been directed towards deriving efficient upper bounds and approximation algorithms. Classical results, such as the Bregman-Minc inequality and its numerous refinements, form a rich and diverse body of work (e.g., [ 11 , 13 , 4 , 16 , 12 , 17 , 7 , 9 , 15 , 19 , 20 , 6 ] ). Recently, there has been growing interest in approximating the permanents of positive semidefinite (PSD) matrices [ 3 , 23 , 10 , 5 ] . Permanents of PSD matrices appear naturally in quantum optics and boson sampling in quantum computing [ 2 , 18 , 21 ] . However, existing bounds have largely emerged from combinatorial, scaling, or probabilistic frameworks. In contrast, this work develops a deterministic, iterative procedure rooted in linear algebraic principles. Our main result is an algorithm for establishing upper bounds on the permanent of non-negative matrices and positive semidefinite matrices. The approach provides a new algorithmic pathway that is both theoretically sound and computationally feasible. We systematically adapt powerful and intuitive tools from determinant theory. The main contributions of this paper are summarized as follows. A Permanental Inverse and Schur’s Formula for Permanents. We define a novel analogue of the matrix inverse, constructed from permanents of submatrices. While it lacks multiplicative inverse properties, this permanental inverse satisfies structural inequalities that enable us to derive new permanental inequalities and to establish our algorithmic upper bound on the permanent. Definition 1.1 (Permanental Inverse) . The permanental inverse of a non-negative matrix B\in\mathbb{R}^{d\times d}_{\geq 0} with \per(B)\neq 0 is the matrix C with entries \displaystyle c_{i,j}=\frac{\per(B_{j,i})}{\per(B)}, where B_{j,i} is the matrix obtained by removing the j^{\text{th}} row and i^{\text{th}} column of B . We use B^{*} to denote the permanental inverse of B . Leveraging the permanental inverse, we establish an analogue of Schur’s formula for determinants for permanents. This result provides the core theoretical engine for our upper bounds. Theorem 1.2 (Permanental Schur’s Formula) . Let A\in\mathbb{R}^{n\times n}_{\geq 0} be a block matrix of the form \displaystyle A=\begin{bmatrix}B&Y\\ X^{\top}&W\end{bmatrix}, where B\in\mathbb{R}^{d\times d} has non-zero permanent. Then the permanent of A satisfies \displaystyle\per(A)\leq\per(B)\cdot\per\left(W+X^{\top}B^{*}Y\right). (1) See Section 3.1 and Section 3.3 for more details regarding the permanental inverse and Theorem 1.2 . A Constructive Algorithmic Upper Bound. We introduce an iterative procedure, called the Permanent Process , inspired by Gaussian elimination. This algorithm yields a provable upper bound on the permanent of any non-negative or PSD matrix, while being computationally efficient, requiring only O(n^{3}) operations for an n\times n matrix (Algorithm 1 ). Algorithm 1 The Permanent Process Input. A\in\mathbb{R}^{n\times n} , A non-negative or PSD A^{(1)}\leftarrow A for t=1\text{ to }n-1 do for i=t+1\text{ to }n do for j=t+1\text{ to }n do a_{i,j}^{(t+1)}\leftarrow a_{i,j}^{(t)}+\dfrac{a_{i,t}^{(t)}\cdot a_{t,j}^{(t)}}{a_{t,t}^{(t)}} end for end for end for Return A^{(n)} Observe that the i,j -th entry of A remains unchanged after step \min(i,j)-1 of the outer loop. In other words, for t\geq\min(i,j) , A^{(t)}_{i,j}=A^{(t-1)}_{i,j} . Our main technical result shows that the entries of the matrix returned by Algorithm 1 can be used to upper bound the permanent of A as follows. Theorem 1.3 (Permanent Process) . Let A be a real nonnegative matrix or a real PSD matrix. The permanent of A is upper bounded by the product of the diagonal entries of A^{(n)} : \displaystyle\per(A)\leq\prod_{1\leq i\leq n}a_{i,i}^{(i)}=\prod_{1\leq i\leq n}a_{i,i}^{(n)}. See Section 4 for further details regarding the permanent process and its properties. 1.4 . If, in the update rule a_{i,j}^{(t+1)}\leftarrow a_{i,j}^{(t)}+\dfrac{a_{i,t}^{(t)}\cdot a_{t,j}^{(t)}}{a_{t,t}^{(t)}} , we replace the “ + ” with a “ - ”, then the determinant of A is exactly equal to the product of the diagonal entries of A^{(n)} (see Corollary 2.3 ). 1.5 . It is not immediately clear whether the representation size of the entries of A^{(t)} remains polynomially bounded throughout the process. We establish that it does for non-negative matrix in Theorem 5.2 in Section 5 . Provable Guarantees for Structured Matrices: We show that for matrices exhibiting a notion of approximate diagonal dominance, a structure common in numerical linear algebra and network models, our upper bound yields strong theoretical guarantees. See Section 4.3 for more details. Theorem 1.6 . Let A\in\mathbb{R}^{n\times n}_{\geq 0} be a non-negative matrix satisfying \displaystyle\frac{(1+\varepsilon)^{2}}{\varepsilon}\sum_{s=1}^{\min(i,j)}\frac{a_{i,s}a_{s,j}}{a_{s,s}}\leq a_{i,j} for some \varepsilon>0 . Then \per(A)\leq(1+\varepsilon)^{n}\cdot\prod_{i=1}^{n}a_{i,i}. Taken together, these results offer a new algorithmic perspective on permanents and expand the analytical toolbox for bounding them, with potential applications in combinatorics, statistical physics, and quantum computation. Organization of the paper. We provide preliminaries and results that we will use in Section 2 . In Section 3 , we prove Theorem 1.2 . In Section 4 , we prove Theorem 4.1 and discuss some applications of our framework. In Section 5 , we show that the representation size of the matrix entries remains polynomially bounded with respect to the representation size of the input during Algorithm 1 . 2 Preliminaries 2.1 Notation To discuss matrices, we will use the following standard notation. Let A be an n\times n matrix with real-valued entries, denoted A\in\mathbb{R}^{n\times n} . • Matrix Entries: (A)_{i,j} or a_{i,j} (the corresponding lowercase letter) refers to the entry in the i^{th} row and j^{th} column of A . • Submatrices by Selection: For index sets S,T\subseteq\{1,\dots,n\} , we denote by A(S,T) the submatrix formed by taking the rows indexed by S and columns indexed by T . By convention, \det(A(\emptyset,\emptyset))=\per(A(\emptyset,\emptyset))=1 . We will sometimes use \det_{A}(S,T):=\det(A(S,T)) . • Submatrices by Deletion: We use several notations for submatrices formed by deleting rows or columns. – The matrix A_{-i,.} denotes the matrix obtained by deleting the i^{th} row, and A_{.,-j} denotes the matrix obtained by deleting the j^{th} column. – A_{i,j} denotes the matrix obtained by deleting both the i^{th} row and the j^{th} column. – For deleting multiple rows and columns, the notation A(-S,-T) is shorthand for the submatrix formed by deleting the rows in set S and columns in set T