Equivalence Testing of Principal Minors

For a square matrix A with n rows and n columns and a subset S of [n], the corresponding principal minor is the determinant of the submatrix of A with rows and columns indexed by elements in S i.e. det(A[S, S]). Two operations on a matrix A that preserve all the principal minors are:

1. Taking the transpose of the matrix.
2. Multiplying it by an invertible diagonal matrix on one side and by its inverse on the other.

The matrices DAD^{-1} and DA^TD^{-1} are called diagonally similar to A when D is an invertible diagonal matrix.

For a square matrix A of dimension n, a subset S of [n] of size at least two and at most n-2 is called a cut if the rank of both the submatrices A[S, [n]-S] and A[[n]-S, S] is less than two. In a couple of works, Raphael and Loewy showed that for an irreducible matrix A with no cuts, another matrix B has the same principal minors if and only if B is diagonally similar to A. 

In this work, we give an extension of their result by giving a complete characterization of when two matrices can have the same principal minors and give a polynomial time algorithm to test it. We also present some applications of equivalence testing of principal minors in Combinatorics and Polynomial Identity Testing.

This is joint work with Abhranil Chatterjee, Rohit Gurjar, and  Sumanta Ghosh.

Short Bio:

Roshan Raj is a PhD student in the CSE department at IIT Bombay working under the mentorship of Prof. Rohit Gurjar. He holds a Betch degree in CSE from IIT BHU.