Subspaces of (Z_2)^n
john baez
How many have dimension k?
How many have a basis given by vectors with k 1's in them?
Randall Dougherty
>How many linear subspaces does (Z_2)^n have?
>How many have dimension k?
Let f(n,k) be the number of k-dimensional subspaces of (Z_2)^n.
Let g(n,k) be the number of sequences of k linearly independent
members of (Z_2)^n (or of any n-dimensional vector space over Z_2).
Then g(n,k) is easy to compute: when choosing the (j+1)'th vector
in the sequence, the only vectors not allowed are the ones in
the subspace spanned by the previous j vectors, and there
are 2^j of these. Therefore,
g(n,k) = (2^n - 1)(2^n - 2)(2^n - 4)(2^n - 8) ... (2^n-2^{k-1}).
Each k-dimensional subspace of (Z_2)^n can be specified by giving
a sequence of k linearly independent vectors which is a basis for it.
But there is more than one such sequence for a given subspace;
in fact, the number of basis sequences for a given k-dimensional
space is exactly g(k,k), regardless of which space it is.
Hence, we get the formula
f(n,k) = g(n,k)/g(k,k).
One can give simple estimates for these numbers. If k isn't very close
to n, then g(n,k) is only slightly less than 2^{nk}. For the case k=n,
g(k,k) is about c*2^{k^2}, where c ~ 0.2888 (precisely,
c = (1/2)(3/4)(7/8)(15/16)...). So a good estimate for
f(n,k) is 2^{k(n-k)}/c, except when k is very close to 0 or n, in
which case the coefficient 1/c changes a little.
The total number of subspaces is the sum of f(n,k) over all k;
this sum works out to about 7.37*2^{n^2/4}.
>How many have a basis given by vectors with k 1's in them?
I don't see how to attack this one.
Randall Dougherty r...@math.ohio-state.edu
Department of Mathematics, Ohio State University, Columbus, OH 43210 USA
"I have yet to see any problem, however complicated, that when looked at in the
right way didn't become still more complicated." Poul Anderson, "Call Me Joe"
charles yeomans
> How many linear subspaces does (Z_2)^n have?
\sum_{i=0}^{n}(answer_to_next_question_in_dimension_i)
> How many have dimension k?
One way is to count the number of sets of k linearly independent vectors
in n-space and then divide by the cardinality of GL_k = # of sets of k
independent vectors in k-dimensional space. I suppose this is the
Grassmann variety-as-homogeneous-space approach.
The number of sets of k independent vectors in n-space is
prod_{i=0}^{k-1}(2^n - 2^i) (k >=1)
Now you can write down the formula.
> How many have a basis given by vectors with k 1's in them?
I can work this out in a grubby sort of way, but it's getting late. If
you don't get an elegant answer, I can provide an argument.
Charles Yeomans
Johannes M. Heinrich
|> How many linear subspaces does (Z_2)^n have?
|> How many have dimension k?
|> How many have a basis given by vectors with k 1's in them?
|>
question 2:
==============
(I'm not quite sure if my answer is correct, my solution seems a
little bit too easy...)
let
F=Z/2Z
E=F^n
F<U> = subspace of E generated by U
d(k) = the number of k-dim. subspaces of E
1)
You've got (2^n-1) possibilities to choose a vector e_1
different from zero in E.
So d(1)=(2^n-1).
2)
The next step is to compute d(k+1) from d(k) :
Suppose you have a k-dim. subspace V = F < e_1, ... e_k > .
To get a k+1 dim. subspace you have to add one more linear
independent vector x.
Obviously there are (2^n - 2^(k-1)) vectors x in E which are not
contained in V.
Now, let x and x' be two vectors not contained in V.
Then
F<x> + V = F<x'> + V
<=> x' in f<x> + V
<=> there exist l_1,...l_k in F such that
x' = l_1 e_1 + ... + l_k e_k + x
So we know that for (2^(k-1)) different choices of x we get the same subspace.
Thus:
d(k+1) = d(k) * (2^n - 2^(k-1)) / (2^(k-1)).
question 1:
============
sum up d(k) over the possible k's .
perhaps there is a more elegant formula for this term ..
Johannes M. Heinrich
this is a followup to the article I posted half an hour ago.
I used xrn to post and did not notice that the configuration on our site
is wrong, so the address the newsreader includes is wrong:
My correct address is j...@math.uni-sb.de
Johannes Heinrich
(j...@math.uni-sb.de)
Gareth McCaughan
> How many linear subspaces does (Z_2)^n have?
> How many have dimension k?
Let's start with the question: How many bases does (Z_2)^n have?
Answer:
First basis vector: 2^n-1 choices
Second basis vector: 2^n-2 choices
Third basis vector: 2^n-4 choices
...
n'th basis vector: 2^n-2^(n-1) choices.
Overall: <the product of these>.
That's counting rearrangements of a given basis as different.
Calling this mess B(n), this means that any subspace of dimension k
has B(k) bases.
Next question: How many strings of k linearly independent vectors
are there?
Of course this is just the same as the above, except that we
stop after k steps. Er, let's call that B(n,k).
Conclusion: There are B(n,k) strings of k linearly independent
vectors; the set of these giving any particular subspace is B(k);
so we want B(n,k)/B(k).
That's
(2^n-1) (2^n-2) ... (2^n-2^(k-1))
--------------------------------- .
(2^k-1) (2^k-2) ... (2^k-2^(k-1))
Or, taking out some factors of 2,
(2^n-1) (2^(n-1)-1) ... (2^(n-k+1)-1)
------------------------------------- .
(2^k-1) (2^(k-1)-1) ... (2^1-1)
That's the number of subspaces of dimension k. For the total number
of subspaces, just add these up.
I get the first few numbers to be
1
1 1
1 3 1
1 7 7 1
1 15 35 15 1
1 31 155 155 31 1
1 63 651 1395 651 63 1 .
I make a lot of mistakes, so I would advise you to check the above
carefully...
> How many have a basis given by vectors with k 1's in them?
No idea at all. Sorry.
--
Gareth McCaughan Dept. of Pure Mathematics & Mathematical Statistics,
gj...@pmms.cam.ac.uk Cambridge University, England. [Research student]
Tomaz Slivnik
And asymptotically a brief calculation gives
$C_e . 2^{n^2/4} (1+o(1))$ subspaces if $n$ is even and
$C_o . 2^{n^2/4} (1+o(1))$ subspaces if $n$ is odd.
Here $C_e$ is about 7.37197 and $C_o$ is about 7.37195. In general, $F_q^n$
has
$C_e . q^(n^2/4) (1+o(1))$ subspaces if $n$ is even and
$C_o . q^(n^2/4) (1+o(1))$ subspaces if $n$ is odd.
where $C_e = \sum_{n \in \Z} q^(-n^2) / Z$,
$C_o = \sum_{n \in \Z} q^(-(n+1/2)^2) / Z$,
and $Z = \product_{n=1}^{\infty} (1-q^(-i))$
are finite positive constants.
Steven Finch -Rs. Calkin
What can be said about the asymptotics for the number of
chains of subspaces
0 < U < V < ... < W < (Z_2)^n
(ordered by inclusion)? References? Please e-mail.
Thank you!
Steven Finch
sfi...@mathsoft.com