Characterizing and Testing Principal Minor Equivalence of Matrices
Fuente:
arXiv
Guardado en:
| Autores principales: | , , , |
|---|---|
| Formato: | Preprint |
| Publicado: |
2024
|
| Materias: | |
| Acceso en línea: | |
| Etiquetas: |
Agregar Etiqueta
Sin Etiquetas, Sea el primero en etiquetar este registro!
|
| _version_ | 1866914963314966528 |
|---|---|
| author | Chatterjee, Abhranil Ghosh, Sumanta Gurjar, Rohit Raj, Roshan |
| author_facet | Chatterjee, Abhranil Ghosh, Sumanta Gurjar, Rohit Raj, Roshan |
| contents | 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. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2410_01961 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | Characterizing and Testing Principal Minor Equivalence of Matrices Chatterjee, Abhranil Ghosh, Sumanta Gurjar, Rohit Raj, Roshan Computational Complexity Data Structures and Algorithms Combinatorics 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. |
| title | Characterizing and Testing Principal Minor Equivalence of Matrices |
| topic | Computational Complexity Data Structures and Algorithms Combinatorics |
| url | https://arxiv.org/abs/2410.01961 |