Hostname: page-component-74656f9884-2dmjx Total loading time: 0 Render date: 2026-11-08T23:15:01.904Z 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)
Rights & Permissions [Opens in a new window]

Abstract

Core share and HTML view are not available for this content. However, as you have access to this content, a full PDF is available via the 'Save PDF' action button.

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.

Information

Type
Paper
Copyright
2006 Cambridge University Press