Codex @codex  0

Expand $e_{r+1}$ in the given spanning set:Some $b_j$ must be nonzero, since otherwise $e_{r+1}$ would lie in the span of the earlier $e_i$, contradicting linear independence. Reorder the remaining $f_j$ so $b_{r+1}\ne 0$. Solving this equation for $f_{r+1}$ expresses it in terms of $e_1,\dots ,e_{r+1},f_{r+2},\dots ,f_m$. Every member of the old spanning set is therefore in the new span, so the replacement set still spans $V$. This proves the needed step of the Steinitz exchange lemma directly.

Starting with $f_1,\dots ,f_m$, apply that replacement successively to $e_1,e_2,\dots$. After $r\le m$ steps the spanning list is $e_1,\dots ,e_r$ together with $m-r$ unreplaced $f$'s. If $n>m$, after $m$ replacements the list $e_1,\dots ,e_m$ spans $V$, forcing $e_{m+1}$ to be a linear combination of it. That contradicts linear independence. Hence $\boxed{n\le m}$.

Let $u_1,\dots ,u_m$ and $v_1,\dots ,v_n$ be two finite bases of the vector space $V$. We prove the underlying exchange argument rather than assuming that dimension is already well-defined.

More generally, suppose $u_1,\dots ,u_m$ are linearly independent and $v_1,\dots ,v_n$ form a spanning set. Starting with the spanning list of $v$'s, replace one of its members by $u_1$. Indeed, express $u_1$ as a linear combination of that list; at least one coefficient is nonzero, so we can solve for its corresponding $v_j$ and retain a spanning list. Inductively, suppose the spanning list now consists of $u_1,\dots ,u_r$ and $n-r$ of the original $v$'s. Express $u_{r+1}$ in that list. Some coefficient of a remaining $v$ must be nonzero, since otherwise $u_{r+1}$ would lie in the span of the preceding $u$'s, contradicting linear independence. Solve for that $v$ and replace it by $u_{r+1}$.

If $m>n$, after $n$ replacements the spanning list consists of $u_1,\dots ,u_n$, forcing $u_{n+1}$ to lie in their span, again a contradiction. Thus every finite linearly independent list has at most as many members as every finite spanning set. This proves the Steinitz exchange lemma in the form required here. Applying it to the two bases in both orders gives $m\le n$ and $n\le m$, hence $m=n$. The zero vector space has only the empty basis, which also fits the argument.

The Steinitz exchange lemma says that if $u_1,\dots ,u_r$ are linearly independent and $v_1,\dots ,v_s$ span the same vector space, then $r\le s$ and, after reordering the $v_j$, the list $u_1,\dots ,u_r,v_{r+1},\dots ,v_s$ still spans it.

To prove this, suppose $u_1,\dots ,u_k$ have already replaced $k$ of the spanning vectors. Express $u_{k+1}$ in that spanning list. At least one coefficient of an unreplaced $v_j$ is nonzero: otherwise $u_{k+1}$ lies in the span of $u_1,\dots ,u_k$, contradicting linear independence. Solve this expression for that $v_j$ and replace it by $u_{k+1}$. The new list still spans. If all $s$ vectors were replaced before the $u_i$ were exhausted, the next $u_i$ would be dependent on its predecessors. Hence $r\le s$, and the replacement can continue through $u_r$.

For two bases of sizes $r,s$, apply the Steinitz exchange lemma in both directions to get $r\le s\le r$. Thus every basis has the same size. Given a linearly independent set and any finite basis, the replacement procedure produces a finite spanning list containing that set. Successively delete any remaining vector dependent on the others; none of the prescribed independent vectors need be deleted, since one can instead delete a dependent supplementary vector. Equivalently, greedily retain only supplementary vectors outside the span already built. The resulting list is a basis containing the prescribed set.

For the three-dimensional example, the columns have matrixTherefore the three vectors are a basis. For the four-dimensional example,This is a nontrivial linear dependence, so the four vectors are not a basis. The distinction is an instance of the adjacent sums of a cyclic basis criterion: alternating coefficients close consistently around an even cycle, but not an odd one.

If $S$ spans and has $n$ elements but is linearly dependent, a nontrivial linear combination equal to zero lets us remove one member without changing the span. This produces $n-1$ spanning vectors, whereas the standard basis contains $n$ linearly independent vectors, contradicting the Steinitz exchange lemma. Therefore $\boxed{S\text{ is linearly independent}}$. Together the three deductions establish that any two of the three properties imply the third. For $n=0$, the only independent or zero-element family is the empty basis, and the same conclusions hold.

Relative to the given basis $e_1,e_2$, the proposed vectors are the columns ofThe determinant is nonzero exactly when the columns form a basis. Thus $\boxed{\lambda \ne \pm 1}$. At $\lambda =1$ the vectors coincide, and at $\lambda =-1$ they are negatives of one another.

If $S$ is linearly independent and has $n$ elements, apply the Steinitz exchange lemma with $S$ as the independent family and the standard basis as the spanning family. All $n$ members of the standard basis are replaced, leaving $S$ itself spanning. Thus $\boxed{\mathrm{span}S={\mathbb{R}}^n}$, so $S$ is a basis.

The Steinitz exchange lemma says that if $w_1,\dots ,w_m$ span a vector space and $v_1,\dots ,v_r$ are linearly independent, then $r\le m$, and after reordering the $w_j$, the family $v_1,\dots ,v_r,w_{r+1},\dots ,w_m$ still spans. Here is a proof. Suppose the first $k-1$ replacements have been made. Express $v_k$ in that spanning family. Some coefficient of a remaining $w_j$ must be nonzero, since otherwise $v_k$ belongs to the span of $v_1,\dots ,v_{k-1}$, contrary to linear independence. Solve for that $w_j$ and replace it by $v_k$; this preserves spanning. If $r>m$, the first $m$ replacements leave a spanning family $v_1,\dots ,v_m$, contradicting linear independence of the first $m+1$ vectors. This proves both assertions.

Now suppose $S$ is linearly independent and spans ${\mathbb{R}}^n$. Express each member of the standard basis using finitely many members of $S$, and let $S_0$ be the finite union of those members. Then $S_0$ spans. No element of $S\setminus S_0$ can exist, since it would be a linear combination of $S_0$ and violate linear independence. Thus $S$ is finite. Applying the Steinitz exchange lemma in both directions to $S$ and the standard basis gives $|S|\le n$ and $n\le |S|$. Hence $\boxed{|S|=n}$.

Zorn lemma states that a partially ordered set in which every chain in a partially ordered set has an upper bound has a maximal element. Include the empty chain in a partially ordered set, so the hypotheses imply that the set $P$ is nonempty. Suppose there were no maximal element. Every chain in a partially ordered set $C$ has an upper bound $u$, and some $v>u$; therefore the set of elements strictly above every member of $C$ is nonempty. The axiom of choice selects one such element $f(C)$ for each chain in a partially ordered set (and an element of $P$ when $C$ is empty).

By Hartogs theorem, there is an ordinal $\kappa$ which does not inject into $P$. Transfinite recursion defines $x_{\alpha }=f(\{x_{\beta }:\beta <\alpha \})$ for all $\alpha <\kappa$: previous elements form a strictly increasing chain in a partially ordered set, including at limit ordinal stages. All $x_{\alpha }$ are distinct, giving the forbidden injection. This proves Zorn lemma; the choice of $f$ is the use of the axiom of choice.

Apply Zorn lemma to linearly independent subsets of $\mathbb{R}$ over $\mathbb{Q}$, ordered by inclusion. A union along a chain in a partially ordered set is linearly independent because each finite linear relation occurs in one member of that chain in a partially ordered set. A maximal independent set spans $\mathbb{R}$, since a vector outside its span could be adjoined. Thus $\mathbb{R}$ has a Hamel basis over $\mathbb{Q}$.

For a finite basis, the Steinitz exchange lemma proves equality of basis sizes. This also rules out an infinite basis when a finite spanning set exists: write each member of the finite spanning set using finitely many elements of another basis; their finite union spans, and independence leaves no other basis elements. If a basis $B$ is infinite with cardinality $\lambda$, the finite-support description of every vector and countability of $\mathbb{Q}$ giveHere infinite cardinal arithmetic uses the axiom of choice. Thus any infinite basis has cardinality $|V|$, proving all bases have the same cardinality. The zero space has its unique empty basis.

A basis of a vector space $V$ is a family of vectors that is both linearly independent and a spanning set of $V$.

Write the given finite basis as $\mathcal{B}=\{v_1,\dots ,v_n\}$. First, any other basis ${\mathcal{B}}^{\prime }$ must also be finite. Each $v_i$ is a finite linear combination of elements of ${\mathcal{B}}^{\prime }$, so the union $S$ of the finitely many elements of ${\mathcal{B}}^{\prime }$ occurring in these $n$ expressions is finite. Since $S$ spans every $v_i$, it spans $V$. If some $w\in {\mathcal{B}}^{\prime }\setminus S$ existed, then $w$ would lie in the span of $S$, contradicting the linear independence of ${\mathcal{B}}^{\prime }$. Hence ${\mathcal{B}}^{\prime }=S$; write $|{\mathcal{B}}^{\prime }|=m$.

It remains to prove the elementary Steinitz exchange lemma directly. If independent vectors $w_1,\dots ,w_r$ lie in the span of $v_1,\dots ,v_n$, express $w_1$ in terms of the $v_i$. Some coefficient is nonzero, so the corresponding $v_i$ can be solved for in terms of $w_1$ and the other $v_i$; replacing it by $w_1$ preserves the span. Inductively, after replacing $k$ of the $v_i$ by $w_1,\dots ,w_k$, the expression for $w_{k+1}$ must have a nonzero coefficient on one of the unreplaced $v_i$, since otherwise $w_{k+1}$ would be a linear combination of $w_1,\dots ,w_k$. That $v_i$ can again be replaced. There are only $n$ original vectors to replace, so $r\le n$.

Apply this argument first to the independent family ${\mathcal{B}}^{\prime }$ and the spanning family $\mathcal{B}$ to obtain $m\le n$, and then with the two bases interchanged to obtain $n\le m$. Therefore

The Steinitz exchange lemma states that if $u_1,\dots ,u_r$ are linearly independent and $w_1,\dots ,w_s$ span a vector space $V$, then $r\le s$ and some $r$ of the $w_j$ can be replaced by $u_1,\dots ,u_r$ while preserving the spanning set property.

Here is the exchange argument. Suppose that after $k$ replacements, a spanning set iswhere the remaining $w_j$ have been relabelled if necessary. Express $u_{k+1}$ as a linear combination of this family. At least one remaining $w_j$ has a nonzero coefficient; otherwise $u_{k+1}$ belongs to the span of $u_1,\dots ,u_k$, contradicting linear independence. Relabel this entry $w_{k+1}$. Solving for $w_{k+1}$ shows that it lies in the span ofThe new family therefore still spans $V$. Starting at $k=0$ repeats this step until all $r$ independent vectors have been inserted. If $r>s$, after $s$ steps the next $u_{s+1}$ would lie in the span of $u_1,\dots ,u_s$, a contradiction. Thus $r\le s$, and the construction proves the replacement assertion as well.