Concentration of the mixed discriminant of well-conditioned matrices

DOI10.1016/J.LAA.2015.11.040zbMATH Open1329.15019OpenAlexW2962938949MaRDI QIDQ905709FDOQ905709

Authors Alexander Barvinok 

Publication date 28 January 2016

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1506.03308

zbMATH Keywords

algorithmconcentrationscalingmixed discriminant

Mathematics Subject Classification ID

Convex programming (90C25) Analysis of algorithms and problem complexity (68Q25) Determinants, permanents, traces, other special matrix functions (15A15) Miscellaneous inequalities involving matrices (15A45)

Abstract: We call an n-tuple Q_1, ..., Q_n of positive definite nxn matrices alpha-conditioned for some alpha > 1 if the ratio of the largest among the eigenvalues of Q_1, ..., Q_n to the smallest among the eigenvalues of Q_1, ..., 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.

Recommendations

• Stability and complexity of mixed discriminants
• A deterministic polynomial-time algorithm for approximating mixed discriminant and mixed volume
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• Mixed discriminants of positive semidefinite matrices
• The Van der Waerden conjecture for mixed discriminants

Cites Work

• scientific article; zbMATH DE number 3458807 (Why is no real title available?)
• scientific article; zbMATH DE number 480253 (Why is no real title available?)
• scientific article; zbMATH DE number 1033392 (Why is no real title available?)
• scientific article; zbMATH DE number 6026126 (Why is no real title available?)
• A Relationship Between Arbitrary Positive Matrices and Doubly Stochastic Matrices
• A deterministic algorithm for approximating the mixed discriminant and mixed volume, and a combinatorial corollary
• A short proof of Minc's conjecture
• Mixed discriminants of positive semidefinite matrices
• New permanental upper bounds for nonnegative matrices
• The Van der Waerden conjecture for mixed discriminants
• Upper bounds for permanents of $\left( {0,\,1} \right)$-matrices
• Van der Waerden/Schrijver-Valiant like conjectures and stable (aka hyperbolic) homogeneous polynomials: one theorem for all

Cited In (5)

• On linearized versions of matrix inequalities
• The Van der Waerden conjecture for mixed discriminants
• Stability and complexity of mixed discriminants
• Bézout-Type Inequality in Convex Geometry
• Short note on some geometric inequalities derived from matrix inequalities

This page was built for publication: Concentration of the mixed discriminant of well-conditioned matrices

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q905709)