2
$\begingroup$

I'm having trouble with the following problem:

Given a subspace $V$ of $\mathbb{F}_q^n$, let $\alpha(V)$ be the number of subsets of $V$ and $\beta(V)$ the number of spanning subsets of $V$. Here a subset $W$ of $V$ is spanning if $V$ equals the vector space spanned by all the vectors in $W$. (On the other hand, the vectors in $W$ are not necessarily independent.) Show that $$ \alpha(V) = 2^{q^{\dim(V)}} \text{ and } \alpha(V) - 1 = \sum_{U \leq V} \beta(U) $$ (Note that the empty subset of $V$ does not span a subspace.) Deduce that the number of spanning sets of $\mathbb{F}_q^n$ is $$ \sum_{k=0}^n \binom{n}{k}_q (-1)^{n-k} q^{\binom{n-k}{2}} (2^{q^k}-1) $$

I have proven the first identity combinatorially, but I'm having trouble showing that summing over the numbers of spanning subsets of $V$ is equal to the number of subsets of $V$. Conceptually, I understand that if I have a subset that does not span $V$, it spans something, and that something is some $U$ that is accounted for by the sum. Just not sure how to prove that formally.

I am also confused on how to deduce the third identity. I think the $q^{\binom{n-k}{2}}$ is throwing me off the most. Don't see how that comes into play.

Thanks!

$\endgroup$
  • $\begingroup$ The $-1$ in $\alpha\left(V\right)-1$ looks wrong. $\endgroup$ – darij grinberg Nov 11 '16 at 6:37
  • $\begingroup$ Your conceptual understanding is correct. More formally, you are arguing that the number of subsets of $V$ is the sum of the numbers of subsets of $U$ spanning $U$ over all $U \leq V$. In fact, each addend in the former sum appears exactly once in the latter double sum, with the $U$ corresponding to its span. Conversely, each addend in the latter double sum appears exactly once in the former sum. $\endgroup$ – darij grinberg Nov 11 '16 at 6:39
  • $\begingroup$ The "Deduce" part probably makes use of Möbius inversion for the lattice of subspaces of $\mathbb{F}_q^n$. Have you seen that? $\endgroup$ – darij grinberg Nov 11 '16 at 6:39
  • $\begingroup$ The $-1$ accounts for the fact that $\emptyset$ spans nothing. $\endgroup$ – Tyler Durden Nov 11 '16 at 7:14
  • $\begingroup$ How do I show that each addend in the sum of the numbers of subsets of $U$ spanning $U$ appears exactly once? In essence, how do I show these are disjoint? I am guessing this is the correct approach to show this? $\endgroup$ – Tyler Durden Nov 11 '16 at 7:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.