DROPS

Document

DOI: 10.4230/LIPIcs.STACS.2026.70

A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Authors: Priyanshu Pant, Surabhi Chakrabartty, and Ranveer Singh

Published in: LIPIcs, Volume 364, 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)

Abstract

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.

Cite as

Priyanshu Pant, Surabhi Chakrabartty, and Ranveer Singh. A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices. In 43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026). Leibniz International Proceedings in Informatics (LIPIcs), Volume 364, pp. 70:1-70:12, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2026)

Copy BibTex To Clipboard

@InProceedings{pant_et_al:LIPIcs.STACS.2026.70,
  author =	{Pant, Priyanshu and Chakrabartty, Surabhi and Singh, Ranveer},
  title =	{{A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices}},
  booktitle =	{43rd International Symposium on Theoretical Aspects of Computer Science (STACS 2026)},
  pages =	{70:1--70:12},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-412-3},
  ISSN =	{1868-8969},
  year =	{2026},
  volume =	{364},
  editor =	{Mahajan, Meena and Manea, Florin and McIver, Annabelle and Thắng, Nguy\~{ê}n Kim},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.STACS.2026.70},
  URN =		{urn:nbn:de:0030-drops-255590},
  doi =		{10.4230/LIPIcs.STACS.2026.70},
  annote =	{Keywords: permanent, matrix rank, #P-completeness, graph algorithms, permanental polynomial, spectral graph theory}
}

Search Results

Documents authored by Chakrabartty, Surabhi

A Permanental Analog of the Rank-Nullity Theorem for Symmetric Matrices

Abstract

Cite as

Thanks for your feedback!

Could not send message