Basis removal gives a basis

Question

Let $V$ be a vector space. Let us say that a finite set $X$ of vectors in $V$ is harmonic if for $B \subseteq X$, $$ B \text{ is a basis of } V \implies X \setminus B \text{ is a basis of }V. $$ Let us say that the basis number of a harmonic set $X$ is the number of subsets of $X$ that are bases of $V$.

Which integers arise as the basis number of some harmonic set?

Clearly, the number of bases is even (unless $X$ is empty). Can it be an arbitrary even number? Can we get, e.g., 10 or 6?

---

This set of integers is closed with respect to multiplication and contains 2. But it consists of not only powers of 2. It is easy to obtain, e.g., 18 (take 6 vectors in a 3-dimensional space: 3 vectors from a plane and 3 from another plane in general position).

Answer 1

There is a theorem about the number of bases of a general matroid:

Theorem: An $n$ element matroid with rank $r$, in which any $s$ element set is independent, has at least $\binom{n−r+s}{s}$ bases; equality holds if and only if the matroid is the direct sum of a uniform matroid $U_{n−r+s,s}$ and a free matroid on $r−s$ elements.

A particular instance of this was proved in this paper of A.Bruen and T.Bruen, and I learned about the general form in this blog post of Peter Cameron.

One can define the notion of harmonic matroid in an obvious way. My proof for the fact that $10$ can not be the basis number of a harmonic matroid is basically the same as the one by domotorp: If there are two dependent elements then the basis number will be divisible by $4$. Otherwise, if the rank is $r$, there are at least $\binom{r+2}{2}$ bases. So the only possibility is when $r=3$, which we can rule out because the equality case in our theorem is not a harmonic matroid.

Similarly one can rule out $14$ and $22$ as possible basis numbers of harmonic matroids by using the same kind of argument.

Answer 2

Here is a proof that you cannot get $10$. Call two vectors twins if they are scalar multiples of each other. In a harmonic sets there cannot be triplets, i.e., every vector has at most one twin. Moreover, in any basis of a harmonic set we have exactly one member of any twin. This means that if we have a construction with a twin that shows $2k$ is a basis number, then $k$ is also a basis number. Since basis numbers are even, there cannot be a twin in a construction that gives $10$.

In the rest suppose for simplicity that we are in $3$-dimensions and we have $6$ vectors in our set. We give a lower bound for the number of ordered bases. There are $6\cdot 5$ ways to pick the first two vectors, any such pair can be extended into a basis as there are no twins. Moreover, in a harmonic set there cannot be only one vector that is not in the plane generated by them, so any such pair has at least two extensions. This already gives $60$ ordered bases, which is the same as $10$ bases, so we must have exactly two extensions for any two vectors. This would mean that we have four vectors on one plane, and four vectors on another, giving two vectors on a line, which means twins, a contradiction.

Answer 3

We can generalize domotorp's argument. If a harmonic set has $2k$ vectors in some $k$-dimensional space, then each basis in the set must contain exactly $k$ vectors, so every other vector must live in some complement to this subspace, so the harmonic set is reducible.

If we restrict our attention to irreducible harmonic sets, we then have at most $2k-1$ in each $k$-dimensional subspace. So to choose a basis for an $n$-dimensional irreducible harmonic set, we can choose any vector, then any other vector, then any vector other than the at most $3$ in the $2$-dimensional space generated by those $2$, then any vector other than the at most $5$ in the $3$-dimensional space generated by those $3$, and so on. This gives a lower bound for the number of bases at:

$$ \frac{ 2n (2n-1) (2n-3) \dots 1}{n (n-1) (n-2) \dots 1}$$

we also have the trivial upper bound of $\left( \begin{array}{c} 2n \\ n \end{array}\right)$. This gives us the possible intervals:

$n=1$: $[2,2]$

$n=2$: $[4,6]$

$n=3$: $[15,20]$

$n=4$: $[35,70]$

$n=5$: $[78.75,252]$

$n=6$: $[173.25,924]$

I think after $n=6$, these intervals continue to overlap, which means we cannot rule out any further numbers. But we at least rule out all numbers which do not appear in these intervals: $8,10,12,14,22,$ and so on, from being the number of bases of an irreducible harmonic set. Since every harmonic set whose number of bases is not a multiple of $4$ is irreducible, we can rule out $10$, $14$, $22$, $26$, $30$, $34$, $74$, and $78$ as being the number of bases of a harmonic set. We can also rule out $28$, because it cannot be independent and it can only be written as $2 \times 14$.

$\left( \begin{array}{c} 2n \\ n \end{array}\right)$ is achievable for each $n$ by $2n$ generic vectors in $n$-dimensional space. This means we can get $6$ and $12=2 \times 6$, so the first number I don't know if we can get is $18$. The next number is $36$.

EDIT: As domotorp points out, $\left( \begin{array}{c} 2n \\ n \end{array}\right)-2$ is achievable, so $18$ and $36$ are. The next number I do not know is $38$.