Concentration of the mixed discriminant of well-conditioned matrices

详细信息    查看全文

• 作者：Alexander Barvinok ^{barvinok@umich.edu" class="auth_mail" title="E-mail the corresponding author}
• 关键词：15A15 ; 15A45 ; 90C25 ; 68Q25
• 刊名：Linear Algebra and its Applications
• 出版年：2016
• 出版时间：15 March 2016
• 年：2016
• 卷：493
• 期：Complete
• 页码：120-133
• 全文大小：315 K

文摘

We call an n  -tuple Q₁,…,Q_n$Q_1,\dots ,Q_n$ of positive definite n×n$n\times n$ real matrices α  -conditioned for some α≥1$\alpha \ge 1$ if for the corresponding quadratic forms q_i:Rⁿ⟶R$q_i:{\mathbb{R}}^n⟶\mathbb{R}$ we have q_i(x)≤αq_i(y)$q_i(x)\le \alpha q_i(y)$ for any two vectors x,y∈Rⁿ$x,y\in {\mathbb{R}}^n$ of Euclidean unit length and q_i(x)≤αq_j(x)$q_i(x)\le \alpha q_j(x)$ for all 1≤i,j≤n$1\le i,j\le n$ and all x∈Rⁿ$x\in {\mathbb{R}}^n$. An n  -tuple is called doubly stochastic if the sum of Q_i$Q_i$ is the identity matrix and the trace of each Q_i$Q_i$ is 1. We prove that for any fixed α≥1$\alpha \ge 1$ the mixed discriminant of an α-conditioned doubly stochastic n  -tuple is n^O(1)e⁻ⁿ$n^{O(1)}{e}^{-n}$. As a corollary, for any α≥1$\alpha \ge 1$ fixed in advance, we obtain a polynomial time algorithm approximating the mixed discriminant of an α-conditioned n-tuple within a polynomial in n factor.