On the probability that a random ±1-matrix is singular

Abstract

We report some progress on the old problem of estimating the probability, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, that a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="n times n plus-or-minus 1"> <mml:semantics> <mml:mrow> <mml:mi>n</mml:mi> <mml:mo>×<!-- × --></mml:mo> <mml:mi>n</mml:mi> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> </mml:mrow> <mml:annotation encoding="application/x-tex">n \times n \pm 1</mml:annotation> </mml:semantics> </mml:math> </inline-formula>-matrix is singular: <bold>Theorem</bold>. <italic>There is a positive constant</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon"> <mml:semantics> <mml:mi>ε<!-- ε --></mml:mi> <mml:annotation encoding="application/x-tex">\varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> <italic>for which</italic> <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline greater-than left-parenthesis 1 minus epsilon right-parenthesis Superscript n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>&gt;</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>ε<!-- ε --></mml:mi> <mml:msup> <mml:mo stretchy="false">)</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} &gt; {(1 - \varepsilon )^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. This is a considerable improvement on the best previous bound, <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline equals upper O left-parenthesis 1 slash StartRoot n EndRoot right-parenthesis"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mi>O</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo>/</mml:mo> </mml:mrow> <mml:msqrt> <mml:mi>n</mml:mi> </mml:msqrt> <mml:mo stretchy="false">)</mml:mo> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} = O(1/\sqrt n )</mml:annotation> </mml:semantics> </mml:math> </inline-formula>, given by Komlós in 1977, but still falls short of the often-conjectured asymptotical formula <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P Subscript n Baseline equals left-parenthesis 1 plus o left-parenthesis 1 right-parenthesis right-parenthesis n squared 2 Superscript 1 minus n"> <mml:semantics> <mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>P</mml:mi> <mml:mi>n</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo>+</mml:mo> <mml:mi>o</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo stretchy="false">)</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mi>n</mml:mi> <mml:mn>2</mml:mn> </mml:msup> </mml:mrow> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mn>2</mml:mn> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mn>1</mml:mn> <mml:mo>−<!-- − --></mml:mo> <mml:mi>n</mml:mi> </mml:mrow> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">{P_n} = (1 + o(1)){n^2}{2^{1 - n}}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>. The proof combines ideas from combinatorial number theory, Fourier analysis and combinatorics, and some probabilistic constructions. A key ingredient, based on a Fourier-analytic idea of Halász, is an inequality (Theorem 2) relating the probability that <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="a underbar element-of bold upper R Superscript n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mi>a</mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msup> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mi mathvariant="bold">R</mml:mi> </mml:mrow> </mml:mrow> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\underline a \in {{\mathbf {R}}^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is orthogonal to a random <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon underbar element-of left-brace plus-or-minus 1 right-brace Superscript n"> <mml:semantics> <mml:mrow> <mml:munder> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:mo>∈<!-- ∈ --></mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>±<!-- ± --></mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> </mml:mrow> <mml:annotation encoding="application/x-tex">\underline \varepsilon \in {\{ \pm 1\} ^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> to the corresponding probability when <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon underbar"> <mml:semantics> <mml:munder> <mml:mi>ε<!-- ε --></mml:mi> <mml:mo>_<!-- _ --></mml:mo> </mml:munder> <mml:annotation encoding="application/x-tex">\underline \varepsilon</mml:annotation> </mml:semantics> </mml:math> </inline-formula> is random from <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="left-brace negative 1 comma 0 comma 1 right-brace Superscript n"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:mo fence="false" stretchy="false">{</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo>,</mml:mo> <mml:mn>0</mml:mn> <mml:mo>,</mml:mo> <mml:mn>1</mml:mn> <mml:msup> <mml:mo fence="false" stretchy="false">}</mml:mo> <mml:mi>n</mml:mi> </mml:msup> </mml:mrow> <mml:annotation encoding="application/x-tex">{\{ - 1,0,1\} ^n}</mml:annotation> </mml:semantics> </mml:math> </inline-formula> with <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="upper P r left-parenthesis epsilon Subscript i Baseline equals negative 1 right-parenthesis equals upper P r left-parenthesis epsilon Subscript i Baseline equals 1 right-parenthesis equals p"> <mml:semantics> <mml:mrow> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mo>−<!-- − --></mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>P</mml:mi> <mml:mi>r</mml:mi> <mml:mo stretchy="false">(</mml:mo> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:mo>=</mml:mo> <mml:mn>1</mml:mn> <mml:mo stretchy="false">)</mml:mo> <mml:mo>=</mml:mo> <mml:mi>p</mml:mi> </mml:mrow> <mml:annotation encoding="application/x-tex">Pr({\varepsilon _i} = - 1) = Pr({\varepsilon _i} = 1) = p</mml:annotation> </mml:semantics> </mml:math> </inline-formula> and <inline-formula content-type="math/mathml"> <mml:math xmlns:mml="http://www.w3.org/1998/Math/MathML" alttext="epsilon Subscript i"> <mml:semantics> <mml:mrow class="MJX-TeXAtom-ORD"> <mml:msub> <mml:mi>ε<!-- ε --></mml:mi> <mml:mi>i</mml:mi> </mml:msub> </mml:mrow> <mml:annotation encoding="application/x-tex">{\varepsilon _i}</mml:annotation> </mml:semantics> </mml:math> </inline-formula>’s chosen independently.

Keywords

Affiliated Institutions

• Rutgers, The State University of New Jersey US
• Hungarian Academy of Sciences HU

Related Publications