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

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

1 Answer 1

Reset to default
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.

Improve this answer
$\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$
    – Gerry Myerson
    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$
    – Steven Landsburg
    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$
    – Steven Landsburg
    Commented May 25, 2012 at 2:21

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .