DROPS

Document

RANDOM

DOI: 10.4230/LIPIcs.APPROX/RANDOM.2025.37

Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields

Authors: Fatemeh Ghasemi, Gal Gross, and Swastik Kopparty

Published in: LIPIcs, Volume 353, Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)

Abstract

This paper is motivated by basic complexity and probability questions about permanents of random matrices over small finite fields, and in particular, about properties separating the permanent and the determinant. Let q be a fixed odd prime, and let k ≤ n both be growing. For a uniformly random n × k matrix A over 𝔽_q, we study the probability that all k × k submatrices of A have zero permanent; namely that A does not have full permanental rank. When k = n, this is simply the probability that a random square matrix over 𝔽_q has zero permanent, which we do not understand. We believe that the probability in this case is 1/q + o(1), which would be in contrast to the case of the determinant, where the answer is 1/q + Ω_q(1). Our main result is that when k is O(√n), the probability that a random n × k matrix does not have full permanental rank is essentially the same as the probability that the matrix has a 0 column, namely (1 +o(1)) k/qⁿ. In contrast, for determinantal (standard) rank the analogous probability is Θ(q^k/q^n). At the core of our result are some basic linear algebraic properties of the permanent that distinguish it from the determinant.

Cite as

Fatemeh Ghasemi, Gal Gross, and Swastik Kopparty. Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields. In Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025). Leibniz International Proceedings in Informatics (LIPIcs), Volume 353, pp. 37:1-37:15, Schloss Dagstuhl – Leibniz-Zentrum für Informatik (2025)

Copy BibTex To Clipboard

@InProceedings{ghasemi_et_al:LIPIcs.APPROX/RANDOM.2025.37,
  author =	{Ghasemi, Fatemeh and Gross, Gal and Kopparty, Swastik},
  title =	{{Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields}},
  booktitle =	{Approximation, Randomization, and Combinatorial Optimization. Algorithms and Techniques (APPROX/RANDOM 2025)},
  pages =	{37:1--37:15},
  series =	{Leibniz International Proceedings in Informatics (LIPIcs)},
  ISBN =	{978-3-95977-397-3},
  ISSN =	{1868-8969},
  year =	{2025},
  volume =	{353},
  editor =	{Ene, Alina and Chattopadhyay, Eshan},
  publisher =	{Schloss Dagstuhl -- Leibniz-Zentrum f{\"u}r Informatik},
  address =	{Dagstuhl, Germany},
  URL =		{https://drops.dagstuhl.de/entities/document/10.4230/LIPIcs.APPROX/RANDOM.2025.37},
  URN =		{urn:nbn:de:0030-drops-244037},
  doi =		{10.4230/LIPIcs.APPROX/RANDOM.2025.37},
  annote =	{Keywords: Permanent, random matrices over a finite field}
}

Search Results

Documents authored by Gross, Gal

Permanental Rank vs Determinantal Rank of Random Matrices over Finite Fields

Abstract

Cite as

Thanks for your feedback!

Could not send message