Learning Read-Once Determinants and the Principal Minor Assignment Problem
Open Access
- 9 June 2026
- conference paper
- Published by Association for Computing Machinery (ACM)
- p. 1672-1683
Abstract
A symbolic determinant under rank-one restriction computes a polynomial of the form det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are square matrices over a field F and rank(Ai) = 1 for each i ∈ [n]. This class of polynomials has been studied extensively, since the work of Edmonds (1967), in the context of linear matroids, matching, matrix completion and polynomial identity testing. We study the following learning problem for this class: Given black-box access to an n-variate polynomial f = det(A0 + A1y1 + … + Anyn), where A0, A1, …, An are unknown square matrices over F and rank(Ai) = 1 for each i ∈ [n], find a square matrix B0 and rank-one square matrices B1, …, Bn over F such that f = det(B0 + B1y1 + … + Bnyn). In this work, we give a randomized poly(n) time algorithm to solve this problem; the algorithm can be derandomized in quasi-polynomial time. To our knowledge, this is the first efficient learning algorithm for this class. As the above-mentioned class is known to be equivalent to the class of read-once determinants (RODs), we will refer to the problem as learning RODs. An ROD computes the determinant of a matrix whose entries are field constants or variables and every variable appears at most once in the matrix. Thus, the class of RODs is a rare example of a well-studied class of polynomials that admits efficient proper learning. The algorithm for learning RODs is obtained by connecting with a well-known open problem in linear algebra, namely the Principal Minor Assignment Problem (PMAP), which asks to find (if possible) a matrix having prescribed principal minors. PMAP has also been studied in machine learning to learn the kernel matrix of a determinantal point process. Here, we study a natural black-box version of PMAP: Given black-box access to an n-variate polynomial f = det(A + Y), where A ∈ Fn × n is unknown and Y = diag(y1, …, yn), find a B ∈ Fn× n such that f = det(B + Y). We show that black-box PMAP can be solved in randomized poly(n) time, and further, it is randomized polynomial-time equivalent to learning RODs. The algorithm and the reduction between the two problems can be derandomized in quasi-polynomial time. To our knowledge, no efficient algorithm to solve this black-box version of PMAP was known before. The insights developed along the way also help us give the first NC algorithm for the Principal Minor Equivalence problem, which asks to check if two given matrices have equal corresponding principal minors.Keywords
All Related Versions
This publication has 22 references indexed in Scilit:
- Linear Matroid Intersection is in Quasi-NCcomputational complexity, 2020
- Skew-symmetric matrices and their principal minorsLinear Algebra and its Applications, 2015
- An efficient algorithm for the symmetric principal minor assignment problemLinear Algebra and its Applications, 2015
- Principal minors, Part II: The principal minor assignment problemLinear Algebra and its Applications, 2006
- Principal minors and diagonal similarity of matricesLinear Algebra and its Applications, 1986
- On matrices having equal corresponding principal minorsLinear Algebra and its Applications, 1984
- On computing the determinant in small parallel time using a small number of processorsInformation Processing Letters, 1984
- Matrices diagonally similar to a symmetric matrixLinear Algebra and its Applications, 1980
- Probabilistic algorithms for sparse polynomials1979
- A probabilistic remark on algebraic program testingInformation Processing Letters, 1978