8
$\begingroup$

Suppose $ m $ vectors from the vector space $ \mathbb{F}_2^n $ are selected independently according to a distribution $ P $ over $ \mathbb{F}_2^n $. Here $ \mathbb{F}_2 $ denotes the field with two elements. My question is this: for which $ P $ is the probability of them being linearly independent maximized? EDIT as a clarification: Equivalently, an $ m\times n $ matrix is formed by sampling the rows independently from a distribution $ P $ over $ \mathbb{F}_2^n $. For which $ P $ is the probability of the matrix being full-rank maximized?

It seems obvious that, for any $ m \in \{2, \ldots,n\} $, the maximum is attained when $ P $ is uniform over all the non-zero vectors ($ \mathbb{F}_2^n \setminus \{0\} $). This is indeed true when $ m = 2 $, which can be concluded based on concavity arguments, but the general case seems less trivial. Does anyone have an idea how this could be (dis)proved?

Improve this question
$\endgroup$
5
  • 3
    $\begingroup$ I know it's an obvious and silly question, but: obviously the 'best' $P$ will assign $0$ weight to $0$. (Otherwise, just re-assign that weight to any non-$0$ vector to increase the "linear independence probability".) Suppose that it assigns different weights $p$ and $q$ to two non-$0$ vectors $v$ and $w$. Can it ever happen that the distribution that assigns the average weight $(p + q)/2$ to both $v$ and $w$, and is otherwise unchanged, has a lower "linear independence probability"? $\endgroup$
    – LSpice
    Commented Jan 11, 2021 at 21:38
  • $\begingroup$ Also, just to be clear, if a vector is ever selected twice, you count that as a failure, right? (That is, you are really looking at the indexed family of selections, not just the set of selected vectors?) $\endgroup$
    – LSpice
    Commented Jan 11, 2021 at 21:38
  • 1
    $\begingroup$ @LSpice To your first question - I don't know :) To your second question - yes, selecting some vector twice would mean that the condition of linear independence is violated. I'll edit my question to clarify. $\endgroup$
    – aleph
    Commented Jan 11, 2021 at 21:50
  • 3
    $\begingroup$ Do not have an answer for fixed n, but there is asymptotic sense in which the distribution doesn't matter unless it is very localized, see 1) Kahn J. and Komlós J. (2001), Singularity Probabilities for Random Matrices over Finite Fields, Combinatorics, Probability and Computing, 10(2), 137-157 and 2) Vinh L. A. (2012), Singular matrices with restricted rows in vector spaces over finite fields, Discrete Mathematics, 312(2), 413-418. $\endgroup$
    – Ofir Gorodetsky
    Commented Jan 11, 2021 at 22:19
  • $\begingroup$ @OfirGorodetsky Thanks for the references, I wasn't aware of the second one. $\endgroup$
    – aleph
    Commented Jan 12, 2021 at 8:07

0

Reset to default

You must log in to answer this question.