pairing vectors of a basis with n-1-dimensianal subspaces spanned by another basis Let $\mathcal{B}=\{b_1,\cdots,b_n\}$ and $\mathcal{C}=\{c_1,\cdots,c_n\}$ be bases for a vector space $V$. Let $n-1$-dimensional subspace $S_i=span(c_{i_1},\cdots,c_{i_{n-1}})$ constructed by choosing $n-1$ $c_i$ from $\mathcal{C}$. There are $n=$$n \choose {n-1}$ different $S_i$.
How to prove we can pair each $b_j$ to each $S_j$ and call it $(b_{\alpha},S_{\alpha})$ so that $$b_{\alpha} \not \in S_{\alpha};\ \ \forall \alpha=1,\cdots,n$$
 A: From your other questions, I'm going to assume you have a good knowledge of the basics of linear algebra.
Suppose that it is proven already for $n=N$. Now we are trying to prove it for $n=N+1$.
You're basically asking: given an invertible square $(N+1)$-by-$(N+1)$ matrix, can we rearrange the columns so that the new matrix does not have a zero entry on the diagonal?
Let the entries of the original matrix be $a_{i,j}$. The determinant of the matrix can be expressed as $\displaystyle\sum_{k=1}^{N+1}(-1)^{N+1+k}a_{N+1,k}\det U_{n+1,k}$ where $U_{i,j}$ is the matrix that you get by deleting the $i^\text{th}$ row and the $j^\text{th}$ column of the original matrix.
Because the sum is non-zero, let us choose $K$ such that $a_{N+1,K}\neq0$ and $\det U_{n+1,K}\neq0$.
The first step in the rearrangement of the columns is to put the $K^\text{th}$ column in the position of the rightmost $(N+1)^\text{th}$ column. After you do this, the top left $N$-by-$N$ block will be an invertible matrix (because of the earlier statement that $\det U_{n+1,K}\neq0$). Immediately apply the induction hypothesis.
A: You can also prove this using Hall’s marriage theorem. (The conventional name of the theorem and the scenario and terminology typically used in discussing it make heteronormative assumptions – perhaps think of pairing applicants and jobs instead.)
For each $S_i$, consider the set $M_i=\left\{b_j\mid b_j\notin S_i\right\}$ of basis vectors that could be paired with $S_i$. You’re looking for a transversal of this family of sets, with a distinct element chosen from each set. By Hall’s marriage theorem, such a transversal exists if (and only if) the union of each subfamily $\mathcal M$ of the $M_i$ has at least as many elements as $\mathcal M$. This is indeed the case, since for a given index set $\mathcal I$ the union $\bigcup_{i\in\mathcal I}M_i$ contains all basis vectors that aren’t in the subspace $\bigcap_{i\in\mathcal I}S_i$; since $\mathcal C$ is a basis, this subspace has co-dimension $|\mathcal I|$, and since $\mathcal B$ is a basis, at least $|\mathcal I|$ of the $b_j$ are not in this subspace.
