0
$\begingroup$

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

$\endgroup$
1
  • 1
    $\begingroup$ Isn't this just the condition you get from Hall's theorem? $\endgroup$ Commented May 22, 2012 at 18:58

1 Answer 1

1
$\begingroup$

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.

$\endgroup$
5
  • $\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$ Commented May 22, 2012 at 23:02
  • $\begingroup$ I forgot to mention that the $V_i$ are not necessarily distinct. $\endgroup$
    – hbm
    Commented May 22, 2012 at 23:14
  • $\begingroup$ hbm: "I forgot to mention that the $V_i$ are not necessarily distinct". It doesn't matter. $\endgroup$ Commented May 22, 2012 at 23:50
  • $\begingroup$ I reedited the question to reflect what I really wanted to say in the first place. $\endgroup$
    – hbm
    Commented May 25, 2012 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$ Commented May 25, 2012 at 2:21

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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