l The Rank of Skew-symmetric Random Matrices over Finite Fields
Speaker
l Lee Joonkyung (KAIST)
Date
l 2009-08-21
Link
l
DownLoad
l
Etc
l 2009 Combinatorics Workshop
Let an be the probability an 2n×2n random skew-symmetric matrix over the finite field GF(q)
is nonsingular, in which each entry is chosen uniformly at random from GF(q). Carlitz (1954)
proved that an converges to (1−q−1)(1−q−3)(1−q−5) · · · as n goes to infinity. This theorem
has several consequences; for instance, a random graph with an even number of vertices
would have an odd number of perfect matchings with the probability converging to about 42%.
We present two additional proofs for the above theorem. One proof is based on combinatorial
arguments, and the other proof is based on Markov chains and its stationary distributions. Our
new method provides further nontrivial generalizations.