1
$\begingroup$

What is the number of $m \times n$ matrices over $\mbox{GF}(2)$ that share the following constraints :

  1. They have full rank ($\mbox{rank} = m$, given that $m<n$).

  2. Their columns have the given Hamming weights $w_1, w_2, \dots, w_n$.

I have tried to solve this problem, It was easy when the first criterion was neglected as it would be a matter of permutations. However when we add the first criterion, it became hard for me to come up with a procedure that would ensure both constraints.

Improve this question
$\endgroup$
8
  • $\begingroup$ Your language is sloppy. If you actually mean the weights are all the same i.e., constant, say so, without writing out the $W_i$. The way it stands, it looks like you fix some set of column weights and will accept matrices which achieve that set of weights, subject to renumbering the columns. $\endgroup$
    – kodlu
    Commented Mar 5, 2023 at 14:43
  • $\begingroup$ Do you consider matrices over $\mathbb{R}$ or over $\mathrm{GF}(2)$? Something along these lines may work here. $\endgroup$
    – Max Alekseyev
    Commented Mar 5, 2023 at 15:15
  • $\begingroup$ This problem seems reminiscent of designing an LDPC code. That problem is somewhat less constrained, and also fairly difficult, so I would find it surprising if you found a general solution to the problem. $\endgroup$
    – Bill Bradley
    Commented Mar 5, 2023 at 21:12
  • $\begingroup$ Have you worked out answers for small values of $m$ and $n$? That might either lead you to an answer for your general question, or (more likely, I think) convince you that there is no useful answer to the fully general question. $\endgroup$
    – Gerry Myerson
    Commented Mar 5, 2023 at 22:20
  • 3
    $\begingroup$ Suppose that all the $w_i$'s are equal to $w$. Let $X$ be the set of all vectors in $\mathbb{F}_2^m$ of Hamming weight $w$. You are asking for the number of $n$-element spanning sets of $X$. Regard $X$ as a matroid (where independence is given by linear independence), For $w>2$ this matroid seems to be intractable, so I doubt that there is a nice answer to your question. For $w=2$ the matroid is well understood (see Sections 3 and 4 of math.mit.edu/~rstan/pubs/pubfiles/83.pdf), so there should be a nice answer. $\endgroup$
    – Richard Stanley
    Commented Mar 5, 2023 at 22:41

0

Reset to default