Concentration of the mixed discriminant of well-conditioned matrices

2015/06/02 by Barvinok, Alexander
#15A15 #15A45 #68Q25 #90C25 #Combinatorics (math.CO) #FOS: Mathematics #Metric Geometry (math.MG)

paper · doi:10.48550/arxiv.1506.03308

Abstract

We call an n-tuple Q₁, ..., Q_n of positive definite nxn matrices alpha-conditioned for some alpha > 1 if the ratio of the largest among the eigenvalues of Q₁, ..., Q_n to the smallest among the eigenvalues of Q₁, ..., Q_n does not exceed alpha. An n-tuple is called doubly stochastic if the sum of Q_i is the identity matrix and the trace of each Q_i is 1. We prove that for any fixed alpha > 1 the mixed discriminant of an alpha-conditioned doubly stochastic n-tuple is n^O(1) e^-n. As a corollary, for any alpha > 1 fixed in advance, we obtain a polynomial time algorithm approximating the mixed discriminant of an alpha-conditioned n-tuple within a polynomial in n factor.

Related

• Stability and complexity of mixed discriminants
• Van der Waerden Conjecture for Mixed Discriminants
• A simple polynomial time algorithm to approximate the permanent within a simply exponential factor
• A characterization of the mixed discriminant
• Matrix Concentration: Order versus Anti-order