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$) ?

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

(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: 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)$.

• @YCor: Good idea about the notation; done. I don't have small values, I'm afraid. – darij grinberg Oct 15 '16 at 23:37
• On small values. $d(4,2)=5$, since only finite number of lines cross 4 generic lines in $P^3$ (so no line crosses generic 5 lines). All this supports formula $k(n-k)+1$... – Ilya Bogdanov Oct 15 '16 at 23:44
• Maybe I'm missing something, but is it clear that the answer does not depend on the field? – Sam Hopkins Oct 15 '16 at 23:45
• Hmm. My intuition says that it probably doesn't, but no, it's certainly not clear. – darij grinberg Oct 15 '16 at 23:47
• Actually making computations makes me doubt that $d(4,2)=5$ over other fields, even maybe in $\mathbf{R}$, (ugly) computations produce quadratic equations, which make me believe that if they have no solution then we get $d(4,2)=4$ in these fields. Namely, choose carefully 4 2-planes in the 4-space; then the set of 2-plane supplement to all of those is finite and computing this finite set is likely to yield a degree 2 equation. – YCor Oct 16 '16 at 0:16

See these papers:

Covering by Complements of Subspaces, II., W. Edwin Clark and Boris Shekhtman, Proc. Amer. Math. Soc.125 (1997), no. 1, 251--254. (link here, unrestriced access; MR review)

Covering by Complements of Subspaces, W. Edwin Clark and Boris Shekhtman, Linear and Multilin. Algebra, Vol 49,1995, pp. 1--13. (link here, restricted accessMR review)

• It might be helpful to summarize the results in these papers. (However, from what I can tell briefly skimming through them, they study the exact problem of the OP and contain all results mentioned so far: $d(n,k) = k(n-k)+1$ for algebraically closed fields; $d(4,2) = 5$ if the field is quadratically closed and $4$ otherwise.) – Sam Hopkins Oct 18 '16 at 18:51
• Did you ever try to find an explicit construction of a complement repository of size $k\left(n-k\right)+1$ ? Did you run into some serious obstructions, or just a lack of constructions that appeared to work? – darij grinberg Oct 18 '16 at 19:24
• It has been a long time since we thought about this problem, so I cannot add anything to what is in the papers. – W. Edwin Clark Oct 18 '16 at 19:37

If $F$ is algebraically closed then $d(n,k)=k(n-k)+1$.

For $W\subset V$ of dimension $k$, write $X_W\subset Gr(V,n-k)$ for the set of $n-k$-dimensional subspaces of $V$ that intersect $W$ non-trivially. Then $X_W$ is a subvariety of codimension $1$, and $\{W_i\}$ is a complement repository iff $\cap X_{W_i}=\varnothing$.

Claim: If $A\subset Gr(V,n-k)$ is a non-empty Zariski closed subset, then there exists $W$ such that $\dim(A\cap X_{W})\leq\dim(A)-1$.

Proof: Suppose $A$ is irreducible. Then $\dim(A\cap X_{W})\leq \dim(A)-1$ if and only if $A\not\subset X_W$. Define $$Y_A:=\left\{W\in Gr(V,k): A\not\subset X_W\right\}.$$ Certainly $Y_A$ is non-empty (it contains any complement of any point in $A$), and $Y_A$ is Zariski open. So in the case $A$ is irreducible, we may take $W$ to be any element of $Y_A$.

If $A$ is not irreducible, there is a decomposition into irreducible components $A=\cup A_i$. Then $\cap Y_{A_i}$ is non-empty (it is a finite intersection of non-empty Zariski open sets), and every $W\in \cap Y_{A_i}$ has the desired property.$\blacksquare$

By induction, we can find a sequence $W_1$, $W_2$, $\ldots$, $W_{k(n-k)+1}$ such that $$\dim\left(\bigcap_{i} X_{W_i}\right)\leq \dim(Gr(V,n-k))-\big(k(n-k)+1\big)=-1.$$ Thus $\cap X_{W_i}=\varnothing$, so $\{W_i\}$ is a complement repository of size $k(n-k)+1$.

• +1. Looks correct (and nice), as far as I can tell with my informal understanding of dimension and irreducible components. Am I seeing it right that this doesn't give any concrete construction of a complement repository, short of picking lots of generic elements? – darij grinberg Oct 16 '16 at 2:47
• @darijgrinberg yes and no: say for the complex numbers, set $p=k(n-k)+1$, you get a concrete construction if you pick $kpn$, f algebraically independent elements $(t_{ijq})_{1\le i\le k, 1\le j\le n,1\le q\le p}$ (this can be explicit) and define $k$-planes $P_1,\dots,P_p$, with $P_q$ generated by the vectors $v_{1q},\dots,v_{kq}$, where $v_{iq}=(t_{i1q},\dots,t_{inq})$. Then $(P_1,\dots,P_p)$ is a complement repository. – YCor Oct 16 '16 at 3:04

Here is a particular case showing that $d(n,k)=d_K(n,k)$ definitely depends on the field $K$ in general, beyond pathologies of finite fields:

$d_{\mathbf{R}}(4,2)=4$

(although $d(4,2)=5$ in the algebraically closed case).

Possibly a similar argument yields $d_K(4,2)=4$ as soon as $K$ has non-squares but I haven't checked details.

Consider the 2-planes in $K^4$ $$A=\{(t,s,0,0)\},\;B=\{(0,0,t,s)\},\; C=\{(t,s,t,s)\},\;D=\{(t,t+2s,t+s,s)\},$$ where $(t,s)$ is understood to range over $K^2$. To prove $d_{\mathbf{R}}(4,2)\le 4$ ($d_K(4,2)\ge 4$ is an elementary verification for an arbitrary field $K$), let's prove that

$\{A,B,C,D\}$ is a complement repository as soon as $-1$ is not a square in $K$.

Proof:

For the moment, $K$ is an arbitrary field.

For $(e,f)\in K^2\smallsetminus \{(0,0)\}$, define $P_{e,f}$ to be the 2-plane $\{(te,tf,se,sf):(t,s)\in K^2\}$. Write $\mathcal{P}=\{P_{e,f}:(e,f)\neq (0,0)\}$.

Clearly $P_{e,f}$ intersects nontrivially each of $A,B,C$ (taking $s=0$, $t=0$, $t=s$ respectively). I claim that conversely if a 2-plane $P$ intersects nontrivially each of $A,B,C$, then $P\in\mathcal{P}$. This is a simple exercise. Indeed, if $P$ intersects $A,B$ nontrivially, then $P=(P\cap A)\oplus (P\cap B)$ and hence there exists $(c,f,a,b)$ with $(c,f),(a,b)\neq (0,0)$ such that $P=\{(tc,tf,sa,sb):(t,s)\in K^2\}$. If $P\cap C$ is nontrivial, for some $(t,s)\neq (0,0)$ we have $tc=sa$ and $tf=sb$. This means that both $(a,c)$ and $(b,f)$ are collinear to the nonzero vector $(t,s)$. If $(b,f)=(0,0)$ we deduce $P=P_{1,0}$. Otherwise, $(a,c)=e(b,f)$ for some $e\in K$. So we have $P=\{(tef,tf,seb,sb):(t,s)\in K^2\}=P_{e,1}$.

Therefore, the final claim that $\{A,B,C,D\}$ is a complement repository is equivalent to showing that $D\cap P_{e,f}=\{0\}$ for every $(e,f)\in K^2 \smallsetminus\{(0,0)\}$.

Since a basis of $P_{e,f}$ is $((e,f,0,0),(0,0,e,f))$ and a basis of $D$ is $((0,2,1,1),(1,1,1,0))$, this amounts to showing that the determinant $\delta(e,f)=\begin{vmatrix}e & f & 0 & 0\\0 & 0 & e & f\\ 0 & 2 & 1 & 1\\ 1 & 1 & 1 & 0\end{vmatrix}$ is nonzero for all $(e,f)\in K^2\smallsetminus\{(0,0)\}$. The computation yields $\delta(e,f)=e^2+f^2$.

Therefore the non-vanishing holds if and only if $-1$ is not a square in $K$. This means that $\{A,B,C,D\}$ is a complement repository if and only if $-1$ is not a square in $K$.

• This just shows $d_{\mathbb{R}}(4,2) \leq 4$, right? – Sam Hopkins Oct 16 '16 at 2:20
• @SamHopkins Right; $d_K(4,2)\ge 4$ is an elementary exercise for an arbitrary field $K$ anyway. – YCor Oct 16 '16 at 2:37
• That's a beautiful argument! – darij grinberg Oct 16 '16 at 2:52
• How does one prove $d_K(4,2) \geq 4$? – HeinrichD Oct 16 '16 at 12:37
• If $x^2 + ax + b$ is a quadratic polynomial without a root in $K$, we can take $D$ to be spanned by $(1,0,-a,1)$ and $(0,1,-b,0)$. The corresponding determinant is $\delta(e,f)=e^2+aef+bf^2$. So your argument does indeed apply to any field that isn't quadratically closed. – Julian Rosen Oct 16 '16 at 13:50