Skip to main content
added 152 characters in body
Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

Let me denote this smallest size by $d\left(n,k\right)$.

It is easy to see that there exists a complement repository of cardinality $\dbinom{n}{k}$. Namely, fix a basis $\left(e_1,e_2,\ldots,e_n\right)$ of the $F$-vector space $V$. For each subset $S$ of $\left\{1,2,\ldots,n\right\}$, let $E_S$ be the $F$-vector subspace of $V$ spanned by the $e_s$ with $s \in S$. Then, the set $\left\{E_S \mid S \subseteq \left\{1,2,\ldots,n\right\};\ \left|S\right| = k\right\}$ is a complement repository of cardinality $\dbinom{n}{k}$.

This gives an upper bound on the smallest size of a complement repository: namely, $d\left(n,k\right) \leq \dbinom{n}{k}$. For a lower bound, I so far can only see $k\left(n-k\right)+1$$d\left(n,k\right) \geq k\left(n-k\right)+1$ for $F = \mathbb{C}$, and I am not sure of that either. (An old MO answer claims that a smooth projective variety of dimension $d$ over $\mathbb{C}$ cannot covered by less than $d+1$ affine open subsets. Applying this to the Grassmannian $\operatorname{Gr}\left(V,n-k\right)$, which I hope is smooth and has dimension $k\left(n-k\right)$, we conclude that $\operatorname{Gr}\left(V,n-k\right)$ cannot be covered by less than $d+1$ affine open subsets. But if $P$ is a $k$-dimensional subspace of $V$, then the complements of $P$ form an affine open subvariety of $\operatorname{Gr}\left(V,n-k\right)$. Hence, a complement repository of cardinality $g$ would induce a covering of $\operatorname{Gr}\left(V,n-k\right)$ by $g$ affine open subsets, and as we know this is impossible for $g < k\left(n-k\right)+1$. This should at least take care of the case $F = \mathbb{C}$; but I doubt that the bound thus obtained is anywhere near optimal.)

It is also clear that $d\left(n,1\right) = d\left(n,n-1\right) = n$. Moreover, a simple argument using orthogonal subspaces in dual spaces shows that $d\left(n,k\right) = d\left(n,n-k\right)$.

It is easy to see that there exists a complement repository of cardinality $\dbinom{n}{k}$. Namely, fix a basis $\left(e_1,e_2,\ldots,e_n\right)$ of the $F$-vector space $V$. For each subset $S$ of $\left\{1,2,\ldots,n\right\}$, let $E_S$ be the $F$-vector subspace of $V$ spanned by the $e_s$ with $s \in S$. Then, the set $\left\{E_S \mid S \subseteq \left\{1,2,\ldots,n\right\};\ \left|S\right| = k\right\}$ is a complement repository of cardinality $\dbinom{n}{k}$.

This gives an upper bound on the smallest size of a complement repository. For a lower bound, I so far can only see $k\left(n-k\right)+1$, and I am not sure of that either. (An old MO answer claims that a smooth projective variety of dimension $d$ over $\mathbb{C}$ cannot covered by less than $d+1$ affine open subsets. Applying this to the Grassmannian $\operatorname{Gr}\left(V,n-k\right)$, which I hope is smooth and has dimension $k\left(n-k\right)$, we conclude that $\operatorname{Gr}\left(V,n-k\right)$ cannot be covered by less than $d+1$ affine open subsets. But if $P$ is a $k$-dimensional subspace of $V$, then the complements of $P$ form an affine open subvariety of $\operatorname{Gr}\left(V,n-k\right)$. Hence, a complement repository of cardinality $g$ would induce a covering of $\operatorname{Gr}\left(V,n-k\right)$ by $g$ affine open subsets, and as we know this is impossible for $g < k\left(n-k\right)+1$. This should at least take care of the case $F = \mathbb{C}$; but I doubt that the bound thus obtained is anywhere near optimal.)

Let me denote this smallest size by $d\left(n,k\right)$.

It is easy to see that there exists a complement repository of cardinality $\dbinom{n}{k}$. Namely, fix a basis $\left(e_1,e_2,\ldots,e_n\right)$ of the $F$-vector space $V$. For each subset $S$ of $\left\{1,2,\ldots,n\right\}$, let $E_S$ be the $F$-vector subspace of $V$ spanned by the $e_s$ with $s \in S$. Then, the set $\left\{E_S \mid S \subseteq \left\{1,2,\ldots,n\right\};\ \left|S\right| = k\right\}$ is a complement repository of cardinality $\dbinom{n}{k}$.

This gives an upper bound on the smallest size of a complement repository: namely, $d\left(n,k\right) \leq \dbinom{n}{k}$. For a lower bound, I so far can only see $d\left(n,k\right) \geq k\left(n-k\right)+1$ for $F = \mathbb{C}$, and I am not sure of that either. (An old MO answer claims that a smooth projective variety of dimension $d$ over $\mathbb{C}$ cannot covered by less than $d+1$ affine open subsets. Applying this to the Grassmannian $\operatorname{Gr}\left(V,n-k\right)$, which I hope is smooth and has dimension $k\left(n-k\right)$, we conclude that $\operatorname{Gr}\left(V,n-k\right)$ cannot be covered by less than $d+1$ affine open subsets. But if $P$ is a $k$-dimensional subspace of $V$, then the complements of $P$ form an affine open subvariety of $\operatorname{Gr}\left(V,n-k\right)$. Hence, a complement repository of cardinality $g$ would induce a covering of $\operatorname{Gr}\left(V,n-k\right)$ by $g$ affine open subsets, and as we know this is impossible for $g < k\left(n-k\right)+1$. This should at least take care of the case $F = \mathbb{C}$; but I doubt that the bound thus obtained is anywhere near optimal.)

It is also clear that $d\left(n,1\right) = d\left(n,n-1\right) = n$. Moreover, a simple argument using orthogonal subspaces in dual spaces shows that $d\left(n,k\right) = d\left(n,n-k\right)$.

Source Link
darij grinberg
  • 33.8k
  • 4
  • 118
  • 253

How few $k$-dimensional subspaces of $V$ are enough to have a complement to each $n-k$-dimensional subspace?

Let $n$ and $k$ be nonnegative integers such that $k\leq n$. Let $F$ be a field, and let $V$ be an $n$-dimensional $F$-vector space. A set $\mathcal{S}$ of $k$-dimensional subspaces of $V$ is said to be a complement repository if for every $n-k$-dimensional subspace $U$ of $V$, there exists some $P \in \mathcal{S}$ such that $V = U \oplus P$ (internal direct sum). (Of course, $V = U \oplus P$ is equivalent to $U \cap P = 0$, since $\dim U + \dim P = n = \dim V$.)

Question: What is the smallest size of a complement repository (for given $n$ and $k$) ?

It is easy to see that there exists a complement repository of cardinality $\dbinom{n}{k}$. Namely, fix a basis $\left(e_1,e_2,\ldots,e_n\right)$ of the $F$-vector space $V$. For each subset $S$ of $\left\{1,2,\ldots,n\right\}$, let $E_S$ be the $F$-vector subspace of $V$ spanned by the $e_s$ with $s \in S$. Then, the set $\left\{E_S \mid S \subseteq \left\{1,2,\ldots,n\right\};\ \left|S\right| = k\right\}$ is a complement repository of cardinality $\dbinom{n}{k}$.

(Here is a proof that this set is a complement repository: Set $\mathcal{S} = \left\{E_S \mid S \subseteq \left\{1,2,\ldots,n\right\};\ \left|S\right| = k\right\}$. We need to show that $\mathcal{S}$ is a complement repository. Let $U$ be an $n-k$-dimensional subspace of $V$. Let $\left(u_1,u_2,\ldots,u_{n-k}\right)$ be a basis of $U$. Thus, the list $\left(u_1,u_2,\ldots,u_{n-k}\right)$ is linearly independent, and spans $U$. By the Steinitz exchange lemma (applied to the linearly independent list $\left(u_1,u_2,\ldots,u_{n-k}\right)$ of vectors, and the basis $\left(e_1,e_2,\ldots,e_n\right)$ of $V$), we have $n-k \leq n$ (which is no surprise), and possibly after reordering the basis $\left(e_1,e_2,\ldots,e_n\right)$, the list $\left(u_1,u_2,\ldots,u_{n-k},e_{n-k+1},e_{n-k+2},\ldots,e_n\right)$ spans $V$. We can WLOG assume that the basis $\left(e_1,e_2,\ldots,e_n\right)$ is already reordered in such a way that the list $\left(u_1,u_2,\ldots,u_{n-k},e_{n-k+1},e_{n-k+2},\ldots,e_n\right)$ spans $V$ (because reordering the basis $\left(e_1,e_2,\ldots,e_n\right)$ does not change the set $\mathcal{S}$). The list $\left(u_1,u_2,\ldots,u_{n-k},e_{n-k+1},e_{n-k+2},\ldots,e_n\right)$ spans $V$, and thus is a basis of $V$ (since it has length $n = \dim V$). Thus, the span of the first $n-k$ entries of this list and the span of the last $k$ entries of this list are complementary subspaces of $V$. But since the former span is $U$ (because the list $\left(u_1,u_2,\ldots,u_{n-k}\right)$ spans $U$), while the latter span is $E_{\left\{n-k+1,n-k+2,\ldots,n\right\}}$ (because $E_{\left\{n-k+1,n-k+2,\ldots,n\right\}}$ is defined as the span of $\left(e_{n-k+1},e_{n-k+2},\ldots,e_n\right)$), this rewrites as follows: The spaces $U$ and $E_{\left\{n-k+1,n-k+2,\ldots,n\right\}}$ are complementary subspaces of $V$. Thus, $V = U \oplus E_{\left\{n-k+1,n-k+2,\ldots,n\right\}}$. Hence, there exists some $P \in \mathcal{S}$ such that $V = U \oplus P$ (namely, $P = E_{\left\{n-k+1,n-k+2,\ldots,n\right\}}$). This shows that $\mathcal{S}$ is a complement repository.)

This gives an upper bound on the smallest size of a complement repository. For a lower bound, I so far can only see $k\left(n-k\right)+1$, and I am not sure of that either. (An old MO answer claims that a smooth projective variety of dimension $d$ over $\mathbb{C}$ cannot covered by less than $d+1$ affine open subsets. Applying this to the Grassmannian $\operatorname{Gr}\left(V,n-k\right)$, which I hope is smooth and has dimension $k\left(n-k\right)$, we conclude that $\operatorname{Gr}\left(V,n-k\right)$ cannot be covered by less than $d+1$ affine open subsets. But if $P$ is a $k$-dimensional subspace of $V$, then the complements of $P$ form an affine open subvariety of $\operatorname{Gr}\left(V,n-k\right)$. Hence, a complement repository of cardinality $g$ would induce a covering of $\operatorname{Gr}\left(V,n-k\right)$ by $g$ affine open subsets, and as we know this is impossible for $g < k\left(n-k\right)+1$. This should at least take care of the case $F = \mathbb{C}$; but I doubt that the bound thus obtained is anywhere near optimal.)