14
$\begingroup$

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

$\endgroup$
  • $\begingroup$ @YCor: Good idea about the notation; done. I don't have small values, I'm afraid. $\endgroup$ – darij grinberg Oct 15 '16 at 23:37
  • 3
    $\begingroup$ 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$... $\endgroup$ – Ilya Bogdanov Oct 15 '16 at 23:44
  • 3
    $\begingroup$ Maybe I'm missing something, but is it clear that the answer does not depend on the field? $\endgroup$ – Sam Hopkins Oct 15 '16 at 23:45
  • 1
    $\begingroup$ Hmm. My intuition says that it probably doesn't, but no, it's certainly not clear. $\endgroup$ – darij grinberg Oct 15 '16 at 23:47
  • 1
    $\begingroup$ 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. $\endgroup$ – YCor Oct 16 '16 at 0:16
5
$\begingroup$

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)

$\endgroup$
  • $\begingroup$ 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.) $\endgroup$ – Sam Hopkins Oct 18 '16 at 18:51
  • $\begingroup$ 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? $\endgroup$ – darij grinberg Oct 18 '16 at 19:24
  • $\begingroup$ It has been a long time since we thought about this problem, so I cannot add anything to what is in the papers. $\endgroup$ – W. Edwin Clark Oct 18 '16 at 19:37
10
$\begingroup$

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

$\endgroup$
  • $\begingroup$ +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? $\endgroup$ – darij grinberg Oct 16 '16 at 2:47
  • $\begingroup$ @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. $\endgroup$ – YCor Oct 16 '16 at 3:04
8
$\begingroup$

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

$\endgroup$
  • $\begingroup$ This just shows $d_{\mathbb{R}}(4,2) \leq 4$, right? $\endgroup$ – Sam Hopkins Oct 16 '16 at 2:20
  • 1
    $\begingroup$ @SamHopkins Right; $d_K(4,2)\ge 4$ is an elementary exercise for an arbitrary field $K$ anyway. $\endgroup$ – YCor Oct 16 '16 at 2:37
  • $\begingroup$ That's a beautiful argument! $\endgroup$ – darij grinberg Oct 16 '16 at 2:52
  • $\begingroup$ How does one prove $d_K(4,2) \geq 4$? $\endgroup$ – HeinrichD Oct 16 '16 at 12:37
  • 1
    $\begingroup$ 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. $\endgroup$ – Julian Rosen Oct 16 '16 at 13:50

Your Answer

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

Not the answer you're looking for? Browse other questions tagged or ask your own question.