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

  • $\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$ 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$ 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$ 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.