1
$\begingroup$

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

$\endgroup$
2
  • 1
    $\begingroup$ 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$ $\endgroup$ Oct 17, 2016 at 16:58
  • $\begingroup$ Related and related. The "replacement lemma" or "replacement theorem" is basically what you're trying to prove here. $\endgroup$ Oct 17, 2016 at 21:37

2 Answers 2

2
$\begingroup$

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.

$\endgroup$
2
  • $\begingroup$ What is the $j\in \{t : a_t\ne 0\}$ ?? I see at least one t and i exists. $\endgroup$
    – maki
    Oct 17, 2016 at 22:31
  • $\begingroup$ 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$. $\endgroup$
    – user379719
    Oct 17, 2016 at 22:46
1
$\begingroup$

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.

$\endgroup$

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.