A stability result using the matrix norm to bound the permanent (Q1650024): Difference between revisions

Let \(A\in\mathbb C^{n\times n}\) have row vectors \(r_1,\dots,r_n\), let \(\|\cdot\|_p\) denote the \(l_p\) norm of a vector and the \(l_p\) operator norm of a matrix and \[ h_p=\frac{1}{n}(\|r_1\|_p+\dots+\|r_n\|_p). \] Further, let \(\mathcal P\) denote the set of matrices in \(\mathbb C^{n\times n}\) of the form \(PD\), where \(P\) is a permutation matrix and \(D\) is a unitary diagonal matrix. \textit{L. Gurvits} [Lect. Notes Comput. Sci. 3618, 447--458 (2005; Zbl 1156.68402)] proved that \(|\text{per}\,A|\leq\|A\|_2^n\) with equality if \(A\) is a scalar multiple of a matrix in \(\mathcal P\). \textit{S. Aaronson} and \textit{T. Hance} [Quantum Inf. Comput. 14, 541--559 (2014)] asked the following question: if \(|\text{per}\,A|\) is ``close'' to \(\|A\|_2^n\), must \(A/\|A\|_2\) be ``close'' to a matrix in \(\mathcal P\)? Further, \textit{S. Aaronson} and \textit{H. Nguyen} [Isr. J. Math. 212, No. 1, 385--417 (2016; Zbl 1350.15017)] posed the problem of characterizing \(A\) such that \(\|A\|_2\leq 1\) and there exists \(C>0\) with \(|\text{per}\,A|\geq n^{-C}\). Addressing these questions, the present authors prove by means of interesting probabilistic methods that if \(\|A\|_2\leq T\neq 0\), then \[ |\text{per}\,A|\leq 2T^n\exp\Big\{-\frac{3n}{100}\Big[1-\frac{\sqrt{\pi}h_2}{2T}- \Big(1-\frac{\sqrt{\pi}}2\Big)\frac{h_\infty}{T}\Big]^2\Big\} \] and \[ |\text{per}\,A|\leq2T^n\exp\Big[-\frac{n}{10^5}\Big(1-\frac{h_\infty}{T}\Big)^2\Big]. \] Finally, for \(A\in\mathbb{R}^{n\times n}\), \[ |\text{per}\,A|\leq(n+6)T^n\exp\Big[-\frac{1}{400}\sqrt{n\Big(1-\frac{h_\infty}{T}\Big)}\Big]. \]