# Augmenting sub-spaces through a basis

Let $t \lt n-1$,

A family { $V_1, V_2, ..., V_n$ } sub-spaces of an $n$-dimensional vector space $V$ is called $t$-feasible if it satisfies conditions (i) and (ii) below:

(i) $\dim(V_i) = t$, for all $i$ $(1 \leq i \leq n)$

(ii) for any $k$ $(2 \leq k \leq n)$, if $1 \leq i_1 \lt i_2 \lt ...\lt i_k \leq n$ , then $\dim(\cap_{j=1}^kV_{i_j}) \le n-k$

Question:

Given a $t$-feasible family { $V_1, V_2, ..., V_n$ } and a basis $B=${$v_1, v_2, ..., v_n$} of $V$, is there a permutation $\pi \in S_n$ so that the family { span$(V_1 \cup v_{\pi(1)})$ , span$(V_2 \cup v_{\pi(2)})$, ...,span$(V_n \cup v_{\pi(n)})$ } is $(t+1)$-feasible?

Note:

Using Hall's Marriage theorem, one could prove that there is a permutation $\pi \in S_n$ so that the new family satisfy condition (i). The difficulty is in proving condition (ii). Specifically, when increasing the dimension of each sub-space by $1$, there is no guarantee that the dimension of some intersection will not increase by more than $1$.

-
Do you have any particular reason to believe it's true? –  Felix Goldberg Jun 7 '12 at 9:45
It would make a construction I am working on goes smoother. I am hoping it is true. –  hbm Jun 7 '12 at 11:26

A counterexample for the case $t = n-1$:

Take $t = 1$, $V = \mathbb{R}^2$, $v_1 = (1,0)$, $v_2 = (0;1)$, $V_1 = span(v_1)$, $V_2 = span(v_2)$. Since there are only two permutations, it is possible to check that the conditions (i) or (ii) do not hold for any permutation:

$\pi = (1;2)$: the new family $\{ span(V_1 \cup v_1), span(V_2 \cup v_2) \}$ equals to the old family $\{ V_1, V_2 \}$

$\pi = (2;1)$: the new family $\{ span(V_1 \cup v_2), span(V_2 \cup v_1) \}$ equals $\{\mathbb{R}^2, \mathbb{R}^2 \}$, and $\dim \mathbb{R}^2 \cap \mathbb{R}^2 = 2$, but $\max \{ 0, t+1-k\} = 0$

A counterexample for the case $t = n-2$:

Take $t = 1$, $V = \mathbb{R}^3$, $v_1 = (1,0,0)$, $v_2 = (0,1,0)$, $v_3 = (0,0,1)$, $V_1 = span(v_1)$, $V_2 = span(v_2)$, $V_3 = span(v_3)$.

Then, for the identical permutation, the condition (i) fails. For any other permutation, there are at least two 2-dimensional subspaces, whose intersection is a 1-dimensional or 2-dimensional subspace, and the condition (ii) fails for $k=2$ and these subspaces.

-
I was thinking of $t$ below $n-1$. Maybe at most $n-2$. –  hbm Jun 7 '12 at 11:24
I edited the question to reflect that. –  hbm Jun 7 '12 at 11:32
The answer is updated as well. –  Stanislav Jun 7 '12 at 12:12
The upper bound in condition (ii) should not depend on $t$. It should be $n-k$. Sorry for that. –  hbm Jun 7 '12 at 13:27
o.k., now it's more interesting... –  Stanislav Jun 8 '12 at 8:37