An ensemble of high rank matrices arising from tournaments

DOI10.1016/J.LAA.2022.11.004MaRDI QIDQ2104983zbMATH OpenOpenAlexFDO

Authors Niranjan Balachandran, Srimanta Bhattacharya, Brahadeesh Sankarnarayanan

Publication date 8 December 2022

Published in Linear Algebra and its Applications (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/2108.10871

bisection closed family rank symmetric matrix Talagrand inequality tournament

Combinatorial aspects of matrices (incidence, Hadamard, etc.) (05B20) Directed graphs (digraphs), tournaments (05C20) Random matrices (algebraic aspects) (15B52)

Abstract: Suppose

m a t h b b F

is a field and let

m a t h b f a := (a_{1}, a_{2}, d o t s c)

be a sequence of non-zero elements in

m a t h b b F

. For

m a t h b f a_{n} := (a_{1}, d o t s c, a_{n})

, we consider the family

m a t h c a l M_{n} (m a t h b f a)

of

n i m e s n

symmetric matrices

M

over

m a t h b b 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

m a t h c a l M_{n} (m a t h b f a)

-- which can be naturally associated with transitive tournaments -- have rank at least

l f l o o r 2 n / 3 f l o o r - 1

. We also show that if

o p e r a t o r n a m e c h a r (m a t h b b F) e q 2

and

M

is a matrix chosen uniformly at random from

m a t h c a l M_{n} (m a t h b f a)

, then with high probability

.

Review text

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\).

Recommendations

Cites work

Cited in

(6)

This page was built for publication: An ensemble of high rank matrices arising from tournaments

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2104983)