6
$\begingroup$

Let $\mathcal{M}_{n,m}(\mathbb{F_q})$ be the set of $n$ by $m$ matrices over the finite field of order $q$, with $n \geq m$.

For a (non-trivial) subspace $V \subset \mathcal{M}_{n,m}(\mathbb{F_q})$, we denote by $f(V) := \frac{|\{M \in V \, \setminus \, \{0\} \, : \, M \text{ does not have full rank} \}|}{|V \, \setminus \, {0}|}$ the fraction of non-zero matrices in $V$ which does not have full rank.

For $V$ chosen uniformly at random of dimension $d$, the average of $f(V)$ is equal to $f(\mathcal{M}_{n,m}(\mathbb{F_q})) \approx q^{m-n-1}$, because all nonzero matrices have the same probability of being included in $V$.

I'm looking for a concentration bound for $f(V)$, saying that with very high probability over the choice of $V$ we have that $f(V)$ is not much higher than $f(\mathcal{M}_{n,m}(\mathbb{F_q}))$.

Any help is greatly appreciated!

Improve this question
$\endgroup$
3
  • $\begingroup$ $V$ is a linear subspace, right? $\endgroup$ Commented May 30 at 6:14
  • $\begingroup$ +1 I wish the bounty was started in $345$ seconds later. :-) $\endgroup$ Commented May 30 at 9:14
  • $\begingroup$ @DanielWeber, yes $V$ is a linear subspace. $\endgroup$ Commented May 30 at 14:23

0

Reset to default

You must log in to answer this question.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.