Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Consider $\mathbb{R}^n$ as a vector space over $\mathbb{R}$. Consider the subset $\mathrm{S}^n = \{(x_1,\ldots,x_n) \in \mathbb{R}^n | x_i = 0 \; \mathrm{or} \; 1\;\forall i = 1,\ldots,n\}$. How many bases of $\mathbb{R}^n$ does $\mathrm{S}^n$ contain? e.g. for n = 2, $\mathrm{S}^2 = \{(0,0),(0,1),(1,0),(1,1)\}$ and it contains three bases namely $\{(0,1),(1,0)\},\;\{(0,1),(1,1)\},\textrm{ and }\{(1,0),(1,1)\}$. I want a general expression for n.

share|improve this question
    
As noted in Fly by Night's answer, this is $\frac{1}{n!} a_n$, where $a_n$ is the number of invertible $(0,1)$ matrices. $a_n$ is discussed further at math.stackexchange.com/questions/54246/… and on Math Overflow at mathoverflow.net/questions/18636/… . –  Kevin Costello Oct 12 '12 at 19:16
    
But this is not a proof. This is just a guess about the n-th term based on the first few terms of the sequence. –  deb Oct 13 '12 at 8:38
3  
But, deb, the vectors form a basis if and only if the matrix whose columns are those vectors is invertible --- no guessing here, the answer to your questions is absolutely certainly $(n!)^{-1}a_n$. –  Gerry Myerson Oct 13 '12 at 12:09

1 Answer 1

This is a really nice problem. It is easy to understand, but is not easy to solve.

I've written a program in Maple to find out the first few terms of the sequence. Maple gets stuck after $n=5$ because the numbers involved grow exponentially. (My program is probably very inefficient too and uses too much RAM.)

If $b_n$ denotes the number of sub-bases, then I get the sequence to be: $(b_n) = (1,3,29,940,104286,\ldots)$

A similar sequence appears on the on-line encyclopedia of integer sequences. In fact, the encyclopedia suggests that $b_6 = 40050850$, $b_7 = 53640013886$ and $b_8 = 251995529844792.$

The sequence $(b_n)$ seems to be given by $n! \cdot b_n = a_n$, where more information about the sequence $(a_n)$ can be found here. In particular, the previous link talks about "Classification of small $(0,1)$ matrices", and supplies literature references.

In terms of trying to solve it for yourself, well, I think that an inductive argument could be very successful. Although, I haven't manage to construct one myself. A key fact is that if you remove an element of a basis for $\mathbb{R}^n$ then you're still left with a basis for $\mathbb{R}^{n-1}.$ Conversely, the bases for $\mathbb{R}^n$ can be built from the bases for $\mathbb{R}^{n-1}.$ If you the kind of vectors you need to add to a basis for $\mathbb{R}^{n-1}$ in order to get a basis for $\mathbb{R}^n$, and you know $b_{n-1}$, then you will know $b_n.$ I suspect that you will be able to prove, by induction, a recurrence relation, which you will then be able to solve.

For example, if you know the elements of $S^{n-1}$, then you need only add an extra number at the end of each element, one a $0$ and one a $1$, to get the elements of $S^n.$

share|improve this answer

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.