Weizmann Logo
ECCC
Electronic Colloquium on Computational Complexity

Under the auspices of the Computational Complexity Foundation (CCF)

Login | Register | Classic Style



REPORTS > DETAIL:

Paper:

TR24-150 | 2nd October 2024 21:51

Characterizing and Testing Principal Minor Equivalence of Matrices

RSS-Feed




TR24-150
Authors: Abhranil Chatterjee, Sumanta Ghosh, Rohit Gurjar, Roshan Raj
Publication: 5th October 2024 14:14
Downloads: 89
Keywords: 


Abstract:

Two matrices are said to be principal minor equivalent if they have equal
corresponding principal minors of all orders. We give a characterization of
principal minor equivalence and a deterministic polynomial time algorithm to
check if two given matrices are principal minor equivalent. Earlier such
results were known for certain special cases like symmetric matrices,
skew-symmetric matrices with {0, 1, -1}-entries, and matrices with no cuts
(i.e., for any non-trivial partition of the indices, the top right block or the
bottom left block must have rank more than 1).
As an immediate application, we get an algorithm to check if the
determinantal point processes corresponding to two given kernel matrices (not
necessarily symmetric) are the same. As another application, we give a
deterministic polynomial-time test to check equality of two multivariate
polynomials, each computed by a symbolic determinant with a rank 1 constraint
on coefficient matrices.



ISSN 1433-8092 | Imprint