2026-07-22T19:09:46Z https://drops.dagstuhl.de/oai

oai:drops-oai.dagstuhl.de:25559 2026-03-19T13:34:59Z ddc:004 open_access

A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices Pant, Priyanshu Chakrabartty, Surabhi Singh, Ranveer permanent matrix rank #P-completeness graph algorithms permanental polynomial spectral graph theory The rank of an n × n matrix A is equal to the maximum order of a square submatrix with a nonzero determinant; it can be computed in O(n^{2.37}) time. Analogously, the maximum order of a square submatrix with nonzero permanent is defined as the permanental rank ρ_{per}(A). Computing the permanent or the coefficients of the permanental polynomial per(xI-A) is #P-complete. The permanental nullity η_{per}(A) is defined as the multiplicity of zero as a root of the permanental polynomial. We establish a permanental analog of the rank–nullity theorem, ρ_{per}(A) + η_{per}(A) = n for symmetric nonnegative matrices, positive semidefinite matrices, and adjacency matrices of balanced signed graphs. Using this theorem, we can compute the permanental nullity for these classes in polynomial time. For {0,± 1}-matrices, we also provide a complete characterization of when the permanental rank-nullity identity holds. Schloss Dagstuhl – Leibniz-Zentrum für Informatik Priyanshu Pant and Surabhi Chakrabartty and Ranveer Singh 2026 Is Part Of LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026) InProceedings Text doc-type:ResearchArticle publishedVersion application/pdf doi:10.4230/LIPIcs.STACS.2026.70 urn:nbn:de:0030-drops-255590 https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.70 eng https://creativecommons.org/licenses/by/4.0/legalcode