Let $t \lt n-1$,

A family { $V_1, V_2, ..., V_n$ } sub-spaces of an $n$-dimensional vector space $V$ is called $t$-feasible if it satisfies conditions (i) and (ii) below:

(i) $\dim(V_i) = t$, for all $i$ $(1 \leq i \leq n)$

(ii) for any $k$ $(2 \leq k \leq n)$, if $1 \leq i_1 \lt i_2 \lt ...\lt i_k \leq n$ , then $\dim(\cap_{j=1}^kV_{i_j}) \le n-k$


Given a $t$-feasible family { $V_1, V_2, ..., V_n$ } and a basis $B= ${$v_1, v_2, ..., v_n$} of $V$, is there a permutation $\pi \in S_n$ so that the family { span$(V_1 \cup v_{\pi(1)})$ , span$(V_2 \cup v_{\pi(2)})$, ...,span$(V_n \cup v_{\pi(n)})$ } is $(t+1)$-feasible?


Using Hall's Marriage theorem, one could prove that there is a permutation $\pi \in S_n$ so that the new family satisfy condition (i). The difficulty is in proving condition (ii). Specifically, when increasing the dimension of each sub-space by $1$, there is no guarantee that the dimension of some intersection will not increase by more than $1$.

  • $\begingroup$ Do you have any particular reason to believe it's true? $\endgroup$ – Felix Goldberg Jun 7 '12 at 9:45
  • $\begingroup$ It would make a construction I am working on goes smoother. I am hoping it is true. $\endgroup$ – hbm Jun 7 '12 at 11:26

A counterexample for the case $t = n-1$:

Take $t = 1$, $V = \mathbb{R}^2$, $v_1 = (1,0)$, $v_2 = (0;1)$, $V_1 = span(v_1)$, $V_2 = span(v_2)$. Since there are only two permutations, it is possible to check that the conditions (i) or (ii) do not hold for any permutation:

$\pi = (1;2)$: the new family $\{ span(V_1 \cup v_1), span(V_2 \cup v_2) \}$ equals to the old family $\{ V_1, V_2 \}$

$\pi = (2;1)$: the new family $\{ span(V_1 \cup v_2), span(V_2 \cup v_1) \}$ equals $\{\mathbb{R}^2, \mathbb{R}^2 \}$, and $\dim \mathbb{R}^2 \cap \mathbb{R}^2 = 2$, but $\max \{ 0, t+1-k\} = 0$

A counterexample for the case $t = n-2$:

Take $t = 1$, $V = \mathbb{R}^3$, $v_1 = (1,0,0)$, $v_2 = (0,1,0)$, $v_3 = (0,0,1)$, $V_1 = span(v_1)$, $V_2 = span(v_2)$, $V_3 = span(v_3)$.

Then, for the identical permutation, the condition (i) fails. For any other permutation, there are at least two 2-dimensional subspaces, whose intersection is a 1-dimensional or 2-dimensional subspace, and the condition (ii) fails for $k=2$ and these subspaces.

| cite | improve this answer | |
  • $\begingroup$ I was thinking of $t$ below $n-1$. Maybe at most $n-2$. $\endgroup$ – hbm Jun 7 '12 at 11:24
  • $\begingroup$ I edited the question to reflect that. $\endgroup$ – hbm Jun 7 '12 at 11:32
  • $\begingroup$ The answer is updated as well. $\endgroup$ – Stanislav Jun 7 '12 at 12:12
  • $\begingroup$ The upper bound in condition (ii) should not depend on $t$. It should be $n-k$. Sorry for that. $\endgroup$ – hbm Jun 7 '12 at 13:27
  • $\begingroup$ o.k., now it's more interesting... $\endgroup$ – Stanislav Jun 8 '12 at 8:37

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.