1

Let $B = \{\vec{u}_1, \vec{u}_2, \vec{u}_3, \ldots,\vec{u}_n\}$ and $B' = \{\vec{v}_1, \vec{v}_2, \vec{v}_3,\ldots,\vec{v}_n\}$ be two bases in the subspace $V$ of $\mathbb R^n.$

Prove that for each $\vec{u}_i \in B$ we can find a $\vec{v}_j \in B'$ such that $ (B \setminus \{\vec{u}_i\}) \cup \{\vec{v}_j\}$ and $ (B' \setminus \{\vec{v}_i \}) \cup \{\vec{u}_j \}$ are both bases in $V$.

maki
  • 213
  • 1
    The line below is between just one pair of double dollar signs. $$ (B' \setminus {\vec{v}_i }) \cup {\vec{u}_j } $$ And here it is between just one pair of single dollar signs: $(B' \setminus {\vec{v}_i }) \cup {\vec{u}_j }$. You shouldn't keep alternating in and out of MathJax in the course of writing a line like this. I cleaned it up. $\qquad$ – Michael Hardy Oct 17 '16 at 16:58
  • Related and related. The "replacement lemma" or "replacement theorem" is basically what you're trying to prove here. – Greg Martin Oct 17 '16 at 21:37

2 Answers2

2

Fix $i$. Since $B'$ is a basis, we may write $u_i = \sum_{t=1}^n a_t v_t$ for some $a_t \in \mathbb R$, and since $u_i \ne 0$, there is at least one $t$ such that $a_t \ne 0$. Moreover, there is at least one $j\in \{t : a_t\ne 0\}$ such that, writing $v_j = \sum_{s=1}^n b_s u_s$ (possible since $B$ is a basis), we have $b_i \ne 0$ (do you see why?). This is your desired $v_j$ for $u_i$, which will take a little bit more work to prove.

  • What is the $j\in {t : a_t\ne 0}$ ?? I see at least one t and i exists. – maki Oct 17 '16 at 22:31
  • If no such $j$ exists, then the equation $u_i = \sum_{t=1}^n a_t v_t$ gives a linear dependence among the elements of $B$. –  Oct 17 '16 at 22:46
1

This proof is based on a result in Prasalov's problem book in linear algebra.

Let the row vector $u_i = \begin{pmatrix} u_{i1} & u_{n2} & \dots & u_{in} \end{pmatrix}$ denote the coordinates of $\vec{u_i}$ with respect to the ordered basis $B'=\{\vec{v_1},\dots,\vec{v_n}\}$ and let $U$ denote the matrix with rows $u_1,\dots,u_n.$ Clearly the row vector $e_i$ which has $1$ for its $i$th entry and $0$ for all other entries represents the vector $\vec{v_i}$ in this basis.

Expanding $\operatorname{det}(U)$ along the first row we have: $$\operatorname{det}(U) = \sum_{j=1}^{n} (-1)^{1+j} u_{1j} M_{1j},$$ where $M_{1j}$ is the determinant of the matrix obtained by deleting the first row and the $j$th column of $U$. Since $\operatorname{det}(U) \neq 0$, at least one term in the above sum is not $0$ so assume $u_{1k} \neq 0$ and $M_{1k} \neq 0$.

This implies $ \operatorname{det}\left( \begin{matrix} u_1\\ e_1\\ e_2\\ \dots\\ e_{k-1}\\ e_{k+1}\\ \dots \\ e_n \end{matrix} \right) = \operatorname{det}(A) \text{ (say)} =(-1)^{1+k} u_{1k} \neq 0$ and $\operatorname{det}\begin{pmatrix}e_k \\ u_2 \\ u_3 \\ \dots\\ u_n \end{pmatrix} = \operatorname{det}(B) \text{ (say)} = (-1)^{1+k}M_{1k} \neq 0$. The non-singularity of $A$ implies $\{\vec{u_1},\vec{v_1},\vec{v_2},\dots,\vec{v_{k-1}},\vec{v_{k+1}},\dots,\vec{v_n}\}$ forms a basis and the non-singularity of $B$ implies $\{\vec{v_k},\vec{u_2},\dots,\vec{u_n}\}$ forms a basis.

Arin Chaudhuri
  • 6,349