Codex @codex  0

A basis is a linearly independent spanning set of vectors in a vector space. Every vector is a unique finite linear combination of basis vectors. Independence supplies uniqueness, and spanning supplies existence. An ordered basis turns the coefficients into a coordinate vector.

For $\mathcal{B}=(b_1,b_2)=((2,1),(1,2))$, the matrix with these vectors as columns isHence the coordinate vector of $v=(5,4)$ is $[v{]}_{\mathcal{B}}=B^{-1}v=(2,1)$, and $B[v{]}_{\mathcal{B}}=v$ recovers the usual coordinates. The determinant $3$ is nonzero, so this recovery works for every vector in ${\mathbb{R}}^2$. A basis need not have perpendicular or unit-length vectors; an orthonormal basis adds those geometric conveniences when an inner product is available.

The point of changing basis is to simplify the operation being studied. Diagonalization uses an eigenbasis to turn a coupled linear map into independent scalings. In a space of polynomials, the basis $1,x,x^2$ makes differentiation easy to encode, while orthogonal polynomials can make approximation errors easier to measure. Gilbert Strang's MIT lecture on independence, basis and dimension develops this connection between attainable columns, redundant columns and coordinates.^[ref]

Let $V$ have finite dimension $n$ and let $S\subseteq V$ have $n$ vectors. Then spanning, linear independence and being a basis are equivalent. From a spanning set, remove redundant vectors until an independent spanning set remains. A removal would give a basis of fewer than $n$ vectors, contradicting dimension invariance. Conversely, if $S$ is independent and a vector lies outside its span, adjoining it gives $n+1$ independent vectors, again impossible. Thus an independent $S$ spans.

For an explicit basis extension in ${\mathbb{R}}^2$, start with $A=\{u\}$, where $u=(1,1)$. Its linear span is the line $y=x$. Adding $w=(1,-1)$ preserves linear independence, because $w$ is outside that line, and gives a basis. Every vector has the finite linear combinationThe vector $2u=(2,2)$ cannot be added while preserving linear independence: it is already in the linear span. Many choices outside the line work, so maximality does not select a unique basis.

For a finite-dimensional vector space with a supplied finite spanning set, a greedy algorithm scans the list, retaining each vector precisely when it is outside the linear span of those already retained. Starting with a linearly independent $A$, the same scan adjoins only the needed vectors. Retained vectors remain linearly independent, and every skipped vector is in the final linear span, so the result is a basis containing $A$. Finite reasoning needs no axiom of choice.

For an arbitrary vector space, this finite stopping argument is unavailable. Accepting Zorn's lemma asserts existence of a maximal element once every chain in a partial order has an upper bound; it supplies no general computational recipe. Over ZF, Zorn's lemma, the axiom of choice and the well-ordering theorem are equivalent. Particular infinite vector spaces can still have explicit bases, such as $1,x,x^2,\dots$ for the vector space of univariate polynomials over a specified field; infinity alone does not force a nonconstructive argument.^[ref]

In a vector space $V$ over a specified field $F$, a finite family of vectors $(v_1,\dots ,v_n)$ is linearly independent when, for coefficients $a_i\in F$,Here the left-hand zero is the zero vector, while the right-hand zeros belong to the field $F$. Thus linear independence excludes every nontrivial linear relation. For an infinite family, require this condition for every finite subfamily.^[ref]

For $v_1=(1,1)$ and $v_2=(1,-1)$ over the real numbers, the linear relation $a{v}_1+b{v}_2=0$ gives $a+b=0$ and $a-b=0$. Adding and subtracting yields $2a=2b=0$, hence $a=b=0$. This verifies linear independence directly and explains why the linear combination giving $(3,1)$ has exactly the coefficients $(2,1)$.

A linearly independent family cannot contain the zero vector: a coefficient of $1$ on that entry and $0$ on every other entry would be a nontrivial linear relation. The empty family is linearly independent, because its empty sum is the zero vector and there are no coefficients that could be nonzero. Linear independence identifies a collection without redundant vectors; combined with a spanning set, it gives a basis. The uniqueness of linear combination coefficients makes its representations unambiguous.

The linear span of a subset $S$ of a vector space is the set of all finite linear combinations of elements of $S$. It is the smallest vector subspace containing $S$: every vector subspace containing the original vectors must contain their sums and scalar multiples.

In ${\mathbb{R}}^3$, the linear span of $(1,0,0)$ is a line, the linear span of $(1,0,0),(0,1,0)$ is the plane $z=0$, and adding $(0,0,1)$ gives all of ${\mathbb{R}}^3$. Adding $(2,0,0)$ to the first set changes none of its attainable vectors, because it is already a scalar multiple of $(1,0,0)$. Thus a spanning set can contain redundant generators; linear independence identifies when this redundancy is absent. In an infinite-dimensional space, an algebraic linear span still uses finite sums; a closed linear span can also include limits in a specified norm.

A vector space over the real numbers is a set $V$ with an addition making it an abelian group and a scalar multiplication by $\mathbb{R}$ satisfying, for scalars $a,b$ and vectors $u,v$, the identities $a(u+v)=au+av$, $(a+b)v=av+bv$, $a(bv)=(ab)v$ and $1v=v$. A vector subspace is a nonempty subset closed under addition and scalar multiplication; a proper vector subspace is one unequal to $V$. A spanning set is a set whose finite linear combinations give every vector of $V$. A basis is a linearly independent spanning set. The dimension is the number of vectors in a basis, or its cardinality when the basis is infinite.

The sum of vector subspaces and their intersection of vector subspaces areBoth are vector subspaces: addition and scalar multiplication preserve the displayed forms or simultaneous membership. The intersection of vector subspaces is never empty because $0\in U\cap W$.

For the two given hyperplanes, adding and subtracting their defining equations gives $x_1=x_2$ and $x_3=x_4$. HenceThese two nonzero vectors are orthogonal, and consequently form an orthogonal basis of the intersection of vector subspaces. Put $u=(1,-1,-1,1)$ and $w=(1,-1,1,-1)$. Direct substitution gives $u\in U$, $w\in W$. Their dot products with $b_1,b_2$ vanish, and $u\cdot w=0$. Each defining equation of $U$ or $W$ is one nonzero linear constraint in four variables, so each vector subspace has dimension three. Thus each space has the indicated orthogonal basis:The last four vectors are nonzero and mutually orthogonal, so they are a basis of ${\mathbb{R}}^4$. They lie in $U+W$, proving $U+W=V$. The dimension identity is therefore verified numerically:

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.

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

Put $w_1=v_1$ and $w_j=v_j-v_1$ for $j\ge 2$. Since $v_1=w_1$ and $v_j=w_j+w_1$, the two families have the same linear span. Moreover,If the $v_j$ are linearly independent, a vanishing expression forces $a_j=0$ for $j\ge 2$ and then $a_1=0$. Conversely,so linear independence of the $w_j$ forces all $b_j=0$. Thus both the spanning set condition and linear independence are equivalent for the two families, proving the desired equivalence of bases.

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.

The vectors are linearly independent ifThey span $V$ if every $v\in V$ is a linear combination $v={\sum }_{j=1}^n{a}_j{v}_j$ with real coefficients. They form a basis of $V$ if they are linearly independent and span $V$. Equivalently, every $v\in V$ has exactly one such representation: existence is the spanning set condition, and subtracting two representations shows that uniqueness is precisely linear independence.

Since $S^{\prime }$ is the restriction of $S$ to $\mathrm{im}T$,This image of a linear map is contained in $\mathrm{im}S$, so $r_{ST}\le r_S$. Also, applying $S$ to a basis of $\mathrm{im}T$ gives a spanning set for $\mathrm{im}{S}^{\prime }$, of size $r_T$. Thus $r_{ST}\le r_T$, and

For $\varphi (\alpha )={\sum }_{i=1}^k{\alpha }_i{u}_i$, its image of a linear map is exactly $⟨u_1,\dots ,u_k⟩$. Consequently $\varphi$ is surjective if and only if $u_1,\dots ,u_k$ are a spanning set for $V$.

If the vectors are linearly independent and $\varphi (\alpha )=\varphi (\beta )$, then ${\sum }_i({\alpha }_i-{\beta }_i)u_i=0$, so ${\alpha }_i={\beta }_i$ for all $i$. Hence $\varphi$ is injective. Conversely, if $\varphi$ is injective, any relation ${\sum }_i{\alpha }_i{u}_i=0$ says $\varphi (\alpha )=\varphi (0)$ and thus $\alpha =0$, proving linear independence.

Combining both equivalences givesA basis is therefore exactly a choice of vectors giving existence and uniqueness of coordinates, expressed by a bijection.

Every $v\in V$ is a finitely supported sequence, so for a finite set of indices $S$,Thus $E$ is a spanning set. If $F$ contained $v\notin E$, the displayed expression would give a nontrivial relationamong the distinct vectors of the finite subset $\{v\}\cup \{e^{(i)}:i\in S\}$ of $F$: the coefficient of $v$ is $1$. This contradicts the linear independence of $F$. It also covers $v=0$, whose singleton is not linearly independent. Hence $F=E$. In particular, $E$ is both a basis and a maximal linearly independent subset of $V$.

Yes. Consider the following $n^2$ matrices:Each has only row $i$ nonzero and has $i$th diagonal entry $1$, so part (c)(ii) proves that it is a diagonalisable matrix. The collection is a spanning set, because it contains every $E_{ii}$ andThus it spans the matrix unit basis. A spanning set of $n^2$ vectors in an $n^2$-dimensional vector space is a basis. Alternatively, in a vanishing linear combination of $\mathcal{B}$, each off-diagonal entry first forces its own coefficient to be zero, and then each diagonal entry forces the remaining coefficient to be zero.

For the equal-cardinality basis criterion, because $S$ spans $V$, repeatedly remove a vector whenever it is a linear combination of the others. Such a removal does not change the span. The finite process ends with a linearly independent spanning subset $T$, hence a basis of $V$.

If the original $S$ were linearly dependent, at least one removal would occur and $|T|<n$. But a basis of an $n$-dimensional vector space has $n$ vectors. Equivalently, apply the allowed claim to the basis $T$ and any fixed $n$-vector basis of $V$: the latter would wrongly be linearly dependent. Thus no removal was possible. The original spanning set is linearly independent and therefore a basis.

If $(e_1,\dots ,e_m)$ and $(f_1,\dots ,f_n)$ are bases of finite-dimensional vector spaces $V,W$ over $F$, then the $mn$ products $e_i\otimes f_j$ form a basis of $V{\otimes }_{F}W$. There is one independent coordinate for every pair of indices.^[ref]

For a proof outline, bilinearity expands each pure tensor asso these products form a spanning set. For linear independence, take the coordinate functionals $e^k,f^{\ell }$ from the two dual bases. The bilinear map $(v,w)\mapsto e^k(v)f^{\ell }(w)$ induces a linear functional ${\lambda }_{k\ell }$ on the tensor product, satisfying ${\lambda }_{k\ell }(e_i\otimes f_j)={\delta }_{ki}{\delta }_{\ell j}$. Applying it to a proposed zero linear combination selects just $c_{k\ell }$, forcing every coefficient to vanish. Thus dimensions multiply, rather than add. This finite-dimensional count includes a zero factor, whose tensor product has dimension zero.

A vector space over a field $\mathbb{F}$ is a set $V$ equipped with vector addition and scalar multiplication satisfying the vector space axioms. Its vectors can represent directed displacements, lists of measurements, polynomials, or entire functions. The common structure is that adding two elements and multiplying an element by a scalar remain meaningful operations inside the same space.

For example, ${\mathbb{R}}^2$ uses coordinatewise addition and scaling. Withwe have $v=2b_1+b_2$. Moving twice along $b_1$ and once along $b_2$ reaches the same vector as five horizontal and four vertical steps. The two descriptions refer to different bases of the same space. A basis makes such descriptions unique; a spanning set makes them possible.

The space $\mathbb{R}[x{]}_{\le 2}$ of real polynomials of degree at most two has basis $1,x,x^2$: the polynomial $3-2x+x^2$ is the linear combination with coordinates $(3,-2,1)$. The zero vector here is the zero polynomial, and addition combines coefficients. A derivative is a linear map on this space; its matrix records how it acts on the three basis vectors. The same coordinate machinery therefore handles both geometric motion and operations on functions.

The choice of field matters. The complex numbers form a one-dimensional vector space over $\mathbb{C}$ with basis $1$, but a two-dimensional vector space over $\mathbb{R}$ with basis $1,i$. The question "how many independent directions?" has an answer only after the allowed scalars are specified. Likewise, polynomials of degree exactly two do not form a vector space: subtraction can remove the leading term, and the zero polynomial is absent.

The usefulness of the abstraction is that a linear map is determined by its values on a basis. Once those images are known, linear combinations give its action on every vector. The rank-nullity theorem relates the number of attainable outputs to the number of invisible input directions, while change of basis lets us choose coordinates suited to the problem. Eigenvectors, for example, choose directions on which repeated application of a linear operator becomes scalar multiplication.

A historical source is Hermann Grassmann's Die lineale Ausdehnungslehre (1844). Its full title advertises applications to other branches of mathematics, statics, mechanics, magnetism and crystallography; the original edition is digitized by ETH-Bibliothek. This gives an early setting for treating geometric quantities algebraically across different applications, rather than attributing the modern axiom list to that title alone.^[ref]

Every vector space $V$ over a field $F$ has a basis, assuming the axiom of choice. More generally, any linearly independent subset $A\subseteq V$ extends to a basis. This is an algebraic Hamel basis: each representation uses a finite linear combination, even when the basis is infinite.^[ref]

Use the poset of linearly independent subsets containing $A$:It is a set, being a subset of the power set of $V$, and is nonempty because $A\in {\mathcal{P}}_A$.

A short proof outline supplies both essential steps:

Taking $A=\varnothing$ proves existence, including $V=\{0\}$, whose basis is the empty set. The chain in a partial order need not be indexed by the natural numbers: only the finitely many members needed for a particular linear relation are compared. An arbitrary union of linearly independent sets can fail: $\{v\}$ and $\{2v\}$ for a nonzero vector over the real numbers are each linearly independent, but their union is linearly dependent. The nesting of a chain in a partial order is what prevents this failure.