# Augmenting $t$-dimensional sub-spaces into $t+1$-dimensional sub-spaces through a basis

Let $V_1, V_2, ..., V_n$ be $t$-dimensional sub-spaces of an $n$-dimensional vector space $V$ where $t \lt n$.

Under what conditions the following would be true:

for any $B= \{v_1, v_2, ..., v_n\}$ a basis of $V$, there is a permutation $\pi \in S_n$ such that

for all $1 \leq i \leq n$, dim$($span$(V_i \cup v_{\pi(i)})) = t +1$ ?

• Isn't this just the condition you get from Hall's theorem? – Gjergji Zaimi May 22 '12 at 18:58

Taking the $V_i$ as given, Hall's Theorem gives a necessary and sufficient condition for the existence of some vectors $v_1,v_2,...v_n$ satisfying your condition. Namely: The complement of any $V_i$ is non-empty, the complement of any $V_i\cap V_j$ $(i\neq j)$ contains at least two elements, the complement of any $V_i\cap V_j\cap V_k$ ($i,j,k$ all distinct) contains at least three elements, etc.
I expect that if you work carefully through the proof of Hall's Theorem, you can piece together a method for determining whether any particular $v_1,v_2,...v_n$ satsifies your needs.
• I forgot to mention that the $V_i$ are not necessarily distinct. – hbm May 22 '12 at 23:14
• hbm: "I forgot to mention that the $V_i$ are not necessarily distinct". It doesn't matter. – Steven Landsburg May 22 '12 at 23:50