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

1. T. C. Wei, S. Severini, Matrix permanent and quantum entanglement of permutation invariant states, Journal of Mathematical Physics 51 (9) (2010) 092203.
2. R. A. Brualdi, D. Cvetkovic, A Combinatorial Approach to Matrix Theory and its Applications, Chapman and Hall/CRC, Boca Raton, 2008.
3. L. G. Valiant, The complexity of computing the permanent, Theoretical Computer Science 8 (2) (1979) 189-201.
4. 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.
5. H. J. Ryser, Combinatorial mathematics, The Mathematical Association of America, 1963.
6. A. Nijenhuis, H. S. Wilf, Combinatorial algorithms: For computers and calculators, 2nd Edition, Academic Press, 1978.
7. D. G. Glynn, The permanent of a square matrix, European Journal of Combinatorics 31 (7) (2010) 1887-1891.
8. A. Z. Kucuk, On the evaluation of rectangular matrix permanents: A symmetric and combinatorial analysis, Symmetry 17 (4) (2025) 507.

9. 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.
10. U. Chabaud, A. Deshpande, S. Mehraban, Quantum-inspired permanent identities, Quantum 6 (2022) 877.
11. C. Masschelein, Efficient evaluation of Rectangular matrix permanents, Doctoral Dissertation McMaster University (2024) Hamilton.
12. D. Elbek, F. Tagyaran, B. Ugur, K. Kaya, SUperman: Efficient permanent computation on GPUs (2025). https://arxiv.org/abs/2502.16577, Accessed 10 Apr 2025.
13. X. Niu, S. Su, J. Zheng, A new fast computation of a permanent, in: 2nd International Conference on Communication, Network and Artificial Intelligence, Vol. 790 of IOP Conference Series: Materials Science and Engineering, IOP Publishing, Guangzhou, 2020, 012057.
14. A. Z. Kucuk, T. Sozer, The effect of the additive row operation on the permanent, Journal of New Theory (42) (2023) 8-13.