Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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).

share|improve this question
2  
I don't think this makes any sense. "any of its basis" --- a finite set of vectors doesn't have a basis. A vector space has a basis, and a finite set of vectors isn't a vector space (unless it's just the zero element, or we're working over a finite field). The complement of a basis will never be a basis, since (for one thing) a basis can't contain the zero vector. Sorry, the question is incomprehensible. –  Gerry Myerson Aug 27 '13 at 23:42
1  
Gerry: I agree. Perhaps the OP means to be working with a vector space $V$ over some field (which one? are all of them allowed?), and by a basis $B$ of a subset $X$ of $V$ he simply means a subset of $X$ which is a basis of $V$. –  Joël Aug 27 '13 at 23:45
1  
I think I understand the question, and have reworded it to clarify. Anton, if I've got it wrong, sorry - please just edit it back. –  Tom Leinster Aug 27 '13 at 23:54
3  
You can get 6. Just take X to be any four vectors in a 2-dimensional space such that none is a scalar multiple of any other. –  Tom Leinster Aug 27 '13 at 23:56
1  
I think that your example with n-n vectors on two hyperplanes has basis number ${2n\choose n} -2$. –  domotorp Aug 30 '13 at 18:38
show 7 more comments

3 Answers

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.

share|improve this answer
add comment

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.

share|improve this answer
    
"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". How? I'm not getting this... –  fedja Aug 30 '13 at 19:35
1  
@fedja, if there is a pair of twins, then the other vectors must lie in some hyperplane $U$, because otherwise we would have a basis avoiding these twins and the harmony would give a basis containing the twins; this is a contradiction. So, all vectors except this pair of twins is a harmonic subset of $U$. –  Anton Klyachko Aug 30 '13 at 20:31
    
Thanks! Looks like I'm a bit dense today :(. –  fedja Aug 30 '13 at 21:45
add comment

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$.

share|improve this answer
    
I do not understand about 28. Can you clarify? –  Anton Klyachko Aug 31 '13 at 4:12
1  
@Anton: since 28 is not in an interval, it cannot be irreducible, so it is the product of two basis numbers. Since all basis numbers are even, it must factor as 2x14, but 14 is not in an interval, a contradiction. –  domotorp Aug 31 '13 at 7:27
    
Oh, thank you, @domotorp! –  Anton Klyachko Aug 31 '13 at 11:17
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.