Hostname: page-component-8448b6f56d-sxzjt Total loading time: 0 Render date: 2024-04-23T17:13:31.699Z Has data issue: false hasContentIssue false

Singular 0/1-Matrices, and the Hyperplanes Spanned by Random 0/1-Vectors

Published online by Cambridge University Press:  07 April 2006

THOMAS VOIGT
Affiliation:
Inst. Mathematics, MA 6-2, TU Berlin, D-10623 Berlin, Germany (e-mail: tvoigt@math.tu-berlin.de, ziegler@math.tu-berlin.de)
GÜNTER M. ZIEGLER
Affiliation:
Inst. Mathematics, MA 6-2, TU Berlin, D-10623 Berlin, Germany (e-mail: tvoigt@math.tu-berlin.de, ziegler@math.tu-berlin.de)

Abstract

Let ${P_s(d)}$ be the probability that a random 0/1-matrix of size $d \times d$ is singular, and let ${E(d)}$ be the expected number of 0/1-vectors in the linear subspace spanned by $d-1$ random independent 0/1-vectors. (So ${E(d)}$ is the expected number of cube vertices on a random affine hyperplane spanned by vertices of the cube.)

We prove that bounds on ${P_s(d)}$ are equivalent to bounds on ${E(d)}$: \[{P_s(d)} = \bigg(2^{-d} {E(d)} + \frac{d^2}{2^{d+1}} \bigg) (1 + \so(1)). \] We also report on computational experiments pertaining to these numbers.

Type
Paper
Copyright
2006 Cambridge University Press

Access options

Get access to the full version of this content by using one of the access options below. (Log in options will check for institutional or personal access. Content may require purchase if you do not have access.)