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

  • 1
    $\begingroup$ Isn't this just the condition you get from Hall's theorem? $\endgroup$ – 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.

| cite | improve this answer | |
  • $\begingroup$ 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. $\endgroup$ – Gerry Myerson May 22 '12 at 23:02
  • $\begingroup$ I forgot to mention that the $V_i$ are not necessarily distinct. $\endgroup$ – hbm May 22 '12 at 23:14
  • $\begingroup$ hbm: "I forgot to mention that the $V_i$ are not necessarily distinct". It doesn't matter. $\endgroup$ – Steven Landsburg May 22 '12 at 23:50
  • $\begingroup$ I reedited the question to reflect what I really wanted to say in the first place. $\endgroup$ – hbm May 25 '12 at 1:25
  • $\begingroup$ hbm: Following your re-edit, I reiterate my answer. Have you tried working through the proof of Hall's Theorem? $\endgroup$ – Steven Landsburg May 25 '12 at 2:21

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.