An ensemble of high rank matrices arising from tournaments

Abstract

Suppose $\mathbb{F}$ is a field and let $\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)$, we consider the family ${\mathcal{M}}_n(\mathbf{a})$ of $n\times n$ symmetric matrices $M$ over $\mathbb{F}$ with all diagonal entries zero and the $(i,j)$th element of $M$ either $a_i$ or $a_j$ for $i<j$. In this short paper, we show that all matrices in a certain subclass of ${\mathcal{M}}_n(\mathbf{a})$ -- which can be naturally associated with transitive tournaments -- have rank at least $\lfloor 2n/3\rfloor -1$. We also show that if $\mathrm{char}(\mathbb{F})\ne 2$ and $M$ is a matrix chosen uniformly at random from ${\mathcal{M}}_n(\mathbf{a})$, then with high probability $\mathrm{rank}(M)\ge (\frac{1}{2}-o(1))n$.

12 pages; addendum added; typo fixed in addendum

Cited by in corpus (2)

• On hierarchically closed fractional intersecting families
• Low-rank matrices, tournaments, and symmetric designs