Near invariance of the hypercube (Q2630874): Difference between revisions

Let \(M\) be a square matrix of order \(n\) with real entries and let \(\mathbf{x}\) be a vector chosen uniformly in the hypercube \(C_{n}= \{-1,1 \}^{n}\). The exact score function of \(M\) is defined as \(s_{0} (M)= \mathbf{P}_{\mathbf{x} \in C_{n}} (M\mathbf{x}\in C_{n})\). It constitutes a measure of how the hypercube is preserved under \(M\), or how far the random vector \(M\mathbf{x}\) is from being a Bernoulli vector. The structure of matrices \(M\) with \(s_{0} (M) >n^{-C}\), for some positive real number \(C\), is deduced. Indeed, for fixed \(0<\varepsilon<1\) and \(C\), there exists a submatrix \(M'\) of \(M\) of size \(n_{1} \times n_{2}\), with \(n_{1}, n_{2} = n- O_{C, \varepsilon} (n^{1-\varepsilon})\) and a set \(B\) of \(r= O_{C, \varepsilon}(1)\) vectors in \(R^{n_{1}}\) such that \(M'= M'' + F.\) Here, \(F\) is a \(\{-1,0,1\}\)-matrix of size \(n_{1} \times n_{2}\) where each row contains at most one nonzero entry and \(M''\) belongs to the GAP of size \(n^{O_{C, \varepsilon}(1)}\) generated by the vectors of \(B\). As a consequence, if \(M\) is nearly full rank, then \(F\) is nearly a permutation-reflection matrix modulo a low-rank perturbation. On the other hand, the authors also prove that general matrices of sufficient small entries cannot be near-invariant with respect to the hypercube. When \(M\) is an orthogonal matrix with \(s_{0} (M)> n^{-C},\) then all but \(O (n^{1-\varepsilon})\) rows of \(M\) contain a unique entry of absolute value at least \(1- O(n^{-1+\varepsilon})\). The lower bound \(1- O(n^{-1+o(1)})\) on the large entries is tight. The proof of this result is based on the inverse Littlewood-Offord theory [\textit{T. Tao} and \textit{V. H. Vu}, Ann. Math. (2) 169, No. 2, 595--632 (2009; Zbl 1250.60023)]. Thus, permutation-reflection matrices are ``essentially'' the only orthogonal matrices with large exact score function, i.e., \(s_{0} (M) > n^{-C}\) for some positive real number \(C\). Finally, in the case of stochastic square matrices of order \(n\) (rather than orthogonal matrices or matrices of bounded norm) such that \(\mathrm{Per} (M)\geq n^{-O(1)},\) then all but \(O(\log n)\) of its rows are dominated by a single large entry. In that sense, \(M\) is close to a ``permutation matrix''.