An ensemble of high rank matrices arising from tournaments

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

.

Recommendations

Cites work

Cited in

(6)

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