Paper
Learning Read-Once Determinants and the Principal Minor Assignment Problem
Authors
Abhiram Aravind, Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj, Chandan Saha
Abstract
A symbolic determinant under rank-one restriction computes a polynomial of the form $\det(A_0+A_1y_1+\ldots+A_ny_n)$, where $A_0,A_1,\ldots,A_n$ are square matrices over a field $\mathbb{F}$ and $rank(A_i)=1$ for each $i\in[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(A_0+A_1y_1+ \ldots+A_ny_n)$, where $A_0,A_1,\ldots,A_n$ are unknown square matrices over $\mathbb{F}$ and rank$(A_i)=1$ for each $i\in[n]$, find a square matrix $B_0$ and rank-one square matrices $B_1,\ldots,B_n$ over $\mathbb{F}$ such that $f=\det(B_0+B_1y_1+\ldots+B_ny_n)$. In this work, we give a randomized poly(n) time algorithm to solve this problem. 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. 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 \in \mathbb{F}^{n \times n}$ is unknown and $Y = diag(y_1,\ldots,y_n)$, find a $B\in\mathbb{F}^{n\times 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. We resolve black-box PMAP by investigating a property of dense matrices that we call the rank-one extension property.
Metadata
Related papers
Fractal universe and quantum gravity made simple
Fabio Briscese, Gianluca Calcagni • 2026-03-25
POLY-SIM: Polyglot Speaker Identification with Missing Modality Grand Challenge 2026 Evaluation Plan
Marta Moscati, Muhammad Saad Saeed, Marina Zanoni, Mubashir Noman, Rohan Kuma... • 2026-03-25
LensWalk: Agentic Video Understanding by Planning How You See in Videos
Keliang Li, Yansong Li, Hongze Shen, Mengdi Liu, Hong Chang, Shiguang Shan • 2026-03-25
Orientation Reconstruction of Proteins using Coulomb Explosions
Tomas André, Alfredo Bellisario, Nicusor Timneanu, Carl Caleman • 2026-03-25
The role of spatial context and multitask learning in the detection of organic and conventional farming systems based on Sentinel-2 time series
Jan Hemmerling, Marcel Schwieder, Philippe Rufin, Leon-Friedrich Thomas, Mire... • 2026-03-25
Raw Data (Debug)
{
"raw_xml": "<entry>\n <id>http://arxiv.org/abs/2603.04255v1</id>\n <title>Learning Read-Once Determinants and the Principal Minor Assignment Problem</title>\n <updated>2026-03-04T16:42:33Z</updated>\n <link href='https://arxiv.org/abs/2603.04255v1' rel='alternate' type='text/html'/>\n <link href='https://arxiv.org/pdf/2603.04255v1' rel='related' title='pdf' type='application/pdf'/>\n <summary>A symbolic determinant under rank-one restriction computes a polynomial of the form $\\det(A_0+A_1y_1+\\ldots+A_ny_n)$, where $A_0,A_1,\\ldots,A_n$ are square matrices over a field $\\mathbb{F}$ and $rank(A_i)=1$ for each $i\\in[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(A_0+A_1y_1+ \\ldots+A_ny_n)$, where $A_0,A_1,\\ldots,A_n$ are unknown square matrices over $\\mathbb{F}$ and rank$(A_i)=1$ for each $i\\in[n]$, find a square matrix $B_0$ and rank-one square matrices $B_1,\\ldots,B_n$ over $\\mathbb{F}$ such that $f=\\det(B_0+B_1y_1+\\ldots+B_ny_n)$. In this work, we give a randomized poly(n) time algorithm to solve this problem. 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. 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 \\in \\mathbb{F}^{n \\times n}$ is unknown and $Y = diag(y_1,\\ldots,y_n)$, find a $B\\in\\mathbb{F}^{n\\times 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. We resolve black-box PMAP by investigating a property of dense matrices that we call the rank-one extension property.</summary>\n <category scheme='http://arxiv.org/schemas/atom' term='cs.CC'/>\n <category scheme='http://arxiv.org/schemas/atom' term='math.AC'/>\n <category scheme='http://arxiv.org/schemas/atom' term='math.CO'/>\n <published>2026-03-04T16:42:33Z</published>\n <arxiv:primary_category term='cs.CC'/>\n <author>\n <name>Abhiram Aravind</name>\n </author>\n <author>\n <name>Abhranil Chatterjee</name>\n </author>\n <author>\n <name>Sumanta Ghosh</name>\n </author>\n <author>\n <name>Rohit Gurjar</name>\n </author>\n <author>\n <name>Roshan Raj</name>\n </author>\n <author>\n <name>Chandan Saha</name>\n </author>\n </entry>"
}