MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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

share|cite|improve this question
Do you have any particular reason to believe it's true? – Felix Goldberg Jun 7 '12 at 9:45
It would make a construction I am working on goes smoother. I am hoping it is true. – 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.

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

Your Answer


By posting your answer, you agree to the privacy policy and terms of service.

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