A Novel Algorithm for Permanent Computation
Abstract
This study computes the permanent of a square matrix by reducing it to triangular form. To achieve the triangularization of a matrix, this paper employs additive row operations. Although applying an additive row operation does not alter the determinant, it does affect the permanent, thereby increasing the complexity of the computational process. This difficulty has discouraged previous attempts to compute the permanent via triangularization. This paper addresses this challenge and introduces a novel approach for computing the permanent of a square matrix.
Keywords
Permanent, computational complexity, algorithm, triangularization
References
- T. C. Wei, S. Severini, Matrix permanent and quantum entanglement of permutation invariant states, Journal of Mathematical Physics 51 (9) (2010) 092203.
- R. A. Brualdi, D. Cvetkovic, A Combinatorial Approach to Matrix Theory and its Applications, Chapman and Hall/CRC, Boca Raton, 2008.
- L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (2) (1979) 189-201.
- L. Troyansky, N. Tishby, Permanent uncertainty: On the quantum evaluation of the determinant and the permanent of a matrix, in: T. Toffoli, M. Blafore (Eds.), Proceedings of the 4th Workshop on Physics and Computation (PhysComp '96), Boston, 1996, pp. 1-5.
- H. J. Ryser, Combinatorial mathematics, The Mathematical Association of America, 1963.
- A. Nijenhuis, H. S. Wilf, Combinatorial algorithms: For computers and calculators, 2nd Edition, Academic Press, 1978.
- D. G. Glynn, The permanent of a square matrix, European Journal of Combinatorics 31 (7) (2010) 1887-1891.
- A. Z. Kucuk, On the evaluation of rectangular matrix permanents: A symmetric and combinatorial analysis, Symmetry 17 (4) (2025) 507.
- A. Baykasoglu, A review and analysis of "graph theoretical-matrix permanent" approach to decision making with example applications, Artificial Intelligence Review 42 (2014) 573-605.
- U. Chabaud, A. Deshpande, S. Mehraban, Quantum-inspired permanent identities, Quantum 6 (2022) 877.