A Study on Mixed Discriminating Factors: Stability and Complexity

ABSTRACT

As long as the distance of each matrix from the identity matrix in the operator norm does not exceed some absolute constant γ0 > 0, we prove that the mixed discriminant of n positive semidefinite n-by-n real symmetric matrices can be approximated within a relative error € > 0 in quasi polynomial n O (ln n - ln€) time. From the Marcus-Spielman-Srivastava bound on the roots of the mixed characteristic polynomial, we derive an analogous conclusion for the mixed discriminant of doubly stochastic n-tuples of matrices. Finally, if the operator norm of the matrix is strictly smaller than 1, we provide a quasi-polynomial technique to approximate the sum of the m-th powers of major minors. Gurvits proves that the issue of finding the mixed discriminant of positive semidefinite matrices of rank 2 is #P-hard.

FULL TEXT