Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
Isn't this just the condition you get from Hall's theorem? –  Gjergji Zaimi May 22 '12 at 18:58
add comment

1 Answer

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.

share|improve this answer
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. –  Gerry Myerson 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. –  Steven Landsburg 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? –  Steven Landsburg May 25 '12 at 2:21
add comment

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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