Timeline for Number of full-rank binary matrices with given column Hamming weights [closed]
Current License: CC BY-SA 4.0
19 events
| when toggle format | what | by | license | comment | |
|---|---|---|---|---|---|
| Mar 31, 2023 at 17:43 | history | closed |
kodlu coudy Brian Hopkins Daniele Tampieri Dominic van der Zypen |
Needs details or clarity | |
| Mar 8, 2023 at 2:13 | comment | added | David E Speyer | Oh, whoops, it isn't just forests. It's also okay for any of the components to be a unicyclic grah with an odd cycle. Okay, this is not going to give nice answer even for $w=2$. | |
| Mar 8, 2023 at 2:04 | comment | added | Richard Stanley | @DavidESpeyer: I was incorrectly thinking about $\mathbb{R}^m$, not $\mathbb{F}_2^m$, when I made my comment about $w=2$. | |
| Mar 7, 2023 at 19:37 | comment | added | David E Speyer | When all the $w=2$, this is the number of $m$-edge forests on $n$ labeled vertices. So $n^{n-2}$ if $m = n-1$, and oeis.org/A138464 more generally. | |
| Mar 5, 2023 at 22:41 | comment | added | Richard Stanley | 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. | |
| Mar 5, 2023 at 22:20 | comment | added | Gerry Myerson | 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. | |
| Mar 5, 2023 at 21:12 | comment | added | Bill Bradley | 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. | |
| Mar 5, 2023 at 20:48 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
deleted 2 characters in body
|
| Mar 5, 2023 at 18:37 | history | edited | Rodrigo de Azevedo | CC BY-SA 4.0 |
added 2 characters in body; edited title
|
| Mar 5, 2023 at 15:24 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
better title
|
| Mar 5, 2023 at 15:15 | comment | added | Max Alekseyev | Do you consider matrices over $\mathbb{R}$ or over $\mathrm{GF}(2)$? Something along these lines may work here. | |
| Mar 5, 2023 at 15:07 | history | edited | Max Alekseyev | CC BY-SA 4.0 |
clarified item 2 as I understand it
|
| Mar 5, 2023 at 15:01 | review | Close votes | |||
| Mar 31, 2023 at 17:43 | |||||
| Mar 5, 2023 at 14:43 | comment | added | kodlu | 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. | |
| Mar 5, 2023 at 13:38 | history | edited | Sapiens | CC BY-SA 4.0 |
edited body
|
| Mar 5, 2023 at 13:34 | history | edited | Sapiens | CC BY-SA 4.0 |
added 4 characters in body
|
| Mar 5, 2023 at 13:32 | history | edited | Sapiens | CC BY-SA 4.0 |
added 11 characters in body
|
| S Mar 5, 2023 at 13:25 | review | First questions | |||
| Mar 5, 2023 at 14:47 | |||||
| S Mar 5, 2023 at 13:25 | history | asked | Sapiens | CC BY-SA 4.0 |