# 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? 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.

• Aside to hbm --- if you are not familiar with Hall's Theorem, it is also called Hall's Marriage Theorem and is easily searchable with those keywords. May 22 '12 at 23:02
• 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. May 22 '12 at 23:50
• I reedited the question to reflect what I really wanted to say in the first place.
– hbm
May 25 '12 at 1:25
• hbm: Following your re-edit, I reiterate my answer. Have you tried working through the proof of Hall's Theorem? May 25 '12 at 2:21