Concentration of the mixed discriminant of well-conditioned matrices

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

Authors: Alexander Barvinok 

Publication date: 28 January 2016

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

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.

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

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

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)

Cites Work

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

Cited In (4)

• On linearized versions of matrix inequalities
• The Van der Waerden conjecture for 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)