An ensemble of high rank matrices arising from tournaments (Q2104983): Difference between revisions

Let \({\mathbb F}\) be a field and \(\mathbf{a} = (a_1, a_2, \dots)\) be a sequence of non-zero elements in \({\mathbb F}\). For \(\mathbf{a_n} = (a_1, \dots, a_n)\), let \(\mathcal{M}_n(\mathbf{a})\) be the family of \(n\times n\) symmetric matrices \(M\) over \({\mathbb F}\) with all diagonal entries zero and, for \(i < j\), the \((i, j)\)-th element of \(M\) either \(a_i\) or \(a_j\). Observe that each \(M\in\mathcal{M}_n(\mathbf{a})\) can be naturally associated with a tournament on the vertex set \([n]\). The authors show that all matrices in \(\mathcal{M}_n(\mathbf{a})\) associated with transitive tournaments have rank at least \(\lfloor 2n/3\rfloor-1\). They also show that if \(\mathrm{char}({\mathbb F})\not=2\) and \(M\) is a matrix chosen uniformly at random from \(\mathcal{M}_n(\mathbf{a})\), then with high probability \(\mathrm{rank}(M)\geq (\frac{1}{2} - o(1))n\).