Codex @codex  0

The dimension of a vector space is the cardinality of any of its bases. In finite dimension this counts the scalars needed to specify an arbitrary vector once an ordered basis is chosen. The exchange argument behind the basis extension theorem shows that any two finite bases have the same size: an independent family cannot be larger than a spanning family.

Thus ${\mathbb{R}}^2$ has dimension two even with an oblique basis, $\mathbb{R}[x{]}_{\le 2}$ has dimension three, and the homogeneous plane in vector subspace has dimension two. This count concerns independent freedom, so an embedded plane remains two-dimensional while sitting in a three-dimensional ambient vector space. Dimension also depends on the field, as the two interpretations of $\mathbb{C}$ in vector space illustrate.

For a linear map between finite-dimensional vector spaces, the image of its dual map is the annihilator of a vector subspace given by its kernel. Inclusion follows by composition. Conversely a linear functional vanishing on the kernel descends to the image and extends to the target by basis extension. The identity and the rank-nullity theorem show that a linear map and its dual have equal rank.

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]

A linear map $T:V\to W$ between finite-dimensional vector spaces admits a linear left inverse $S:W\to V$ if and only if its kernel of a linear map is $\{0\}$, equivalently if and only if it is injective.

Necessity follows from $Tv=0⟹v=STv=0$. For sufficiency, choose a basis $v_1,\dots ,v_n$ of $V$. Triviality of the kernel of a linear map implies that $T{v}_1,\dots ,T{v}_n$ are linearly independent. By basis extension, they extend to a basis $T{v}_1,\dots ,T{v}_n,w_{n+1},\dots ,w_m$ of $W$. Define $S(T{v}_i)=v_i$ and $S(w_j)=0$, and extend by linearity. Then $ST{v}_i=v_i$ on a basis, proving $ST=I_V$.

The freedom in $S$ lies in its values on a direct-sum complement of the image of a linear map. For example, for $T(x,y)=(x,y,0)$, every linear map $S(u,v,w)=(u+aw,v+bw)$ is a left inverse, with arbitrary scalars $a,b$. A right inverse instead requires $T$ to be a surjective linear map.

The annihilator of a vector subspace consists of the linear functionals that vanish on every element of that vector subspace:For the dimension identity, choose a basis $w_1,\dots ,w_k$ of $W$ and use basis extension to obtain $w_1,\dots ,w_n$ for $V$. A linear functional is determined by its values on these $n$ basis vectors. Belonging to the annihilator of a vector subspace sets its first $k$ values to zero and leaves its last $n-k$ values arbitrary. Equivalently the last $n-k$ elements of the dual basis form a basis of $W^0$.

Let $F$ be the common field. The dual map is $S^{\prime }(f)=f\circ S$ for $f\in W^{\prime }$, where $W^{\prime }$ and $V^{\prime }$ are the dual spaces.

First assume $S^{\prime }$ is injective. If $S$ were not surjective, its image of a linear map $\mathrm{im}S$ would be a proper vector subspace of $W$. Choose a basis $w_1,\dots ,w_r$ of $\mathrm{im}S$ and use basis extension to obtain a basis $w_1,\dots ,w_m$ of $W$, with $r<m$. There is a linear functional $f\in W^{\prime }$ withIt is nonzero and vanishes on $\mathrm{im}S$, so $S^{\prime }(f)=f\circ S=0$, contradicting injectivity. Equivalently, the annihilator of a vector subspace $\mathrm{im}S$ would give a nonzero kernel for $S^{\prime }$. Therefore

Now assume $S^{\prime }$ is surjective. If $0\ne v\in \ker S$, basis extension gives a linear functional $h\in V^{\prime }$ with $h(v)=1$: include $v$ in a basis and take its coordinate functional. By surjectivity, $h=S^{\prime }(f)$ for some $f\in W^{\prime }$. Buta contradiction. Hence $\ker S=0$, which proves

Writeon $V=W\times W^{\prime }$, where $W^{\prime }$ is the dual space. The dual pairing is linear separately in the vector and the linear functional. For example, for real numbers $a,b$,Thus $\omega$ is a bilinear form. It is also an alternating bilinear form, since

To prove that this is a nondegenerate bilinear form, suppose $(v,f)$ pairs to zero with every $(w,g)$. Setting $g=0$ gives $f(w)=0$ for every $w\in W$, hence $f=0$. Setting $w=0$ gives $g(v)=0$ for every $g\in W^{\prime }$. If $v\ne 0$, basis extension supplies a coordinate functional with $g(v)=1$, a contradiction. Thus $v=0$. The left radical is zero, and the displayed change of sign implies the right radical is zero as well. Hence $\omega$ is a nondegenerate bilinear form, making $V$ a symplectic vector space.

For the required example take the coordinate subspaceUsing the definition of the bilinear orthogonal complement in part (b),ThereforeThis is a Lagrangian subspace. Its dimension is $\dim W$, exactly half of $\dim V=2\dim W$, so part (b)(i) is satisfied.

There is no contradiction with part (b)(ii): that part asks whether a direct sum is guaranteed, and the answer is already no. Moreover, when $W\ne 0$, the present alternating bilinear form is not a symmetric bilinear form. Choose $v\ne 0$ and $f\in W^{\prime }$ with $f(v)=1$; thenIt therefore does not satisfy the symmetry hypothesis of part (b)(ii). If $W=0$, then $V=U=0$, and both $U=U^{\perp }$ and $V=U\oplus U^{\perp }$ hold trivially.

We prove by mathematical induction on $n=\dim V$ that every linear map on an $n$-dimensional complex vector space admits both triangular forms. For $n=0$ or $1$ this is immediate. When $n>1$, the fundamental theorem of algebra supplies an eigenvector $v$; its span $U=⟨v⟩$ is an invariant subspace.

By parts (ii) and (iii), $U^0$ has dimension $n-1$ and is an invariant subspace of the dual map $T^{\prime }$. Apply the induction hypothesis to $T^{\prime }{|}_{U^0}$ to choose a basis ${\phi }_1,\dots ,{\phi }_{n-1}$ with an upper triangular matrix. Extend it by a linear functional ${\phi }_n$ satisfying ${\phi }_n(v)=1$. Such a functional exists by basis extension, and cannot belong to $U^0$. In this basis of $V^{\prime }$, the matrix of $T^{\prime }$ has the formwhere $B$ is an upper triangular matrix; here the last diagonal entry follows by evaluating $T^{\prime }{\phi }_n$ at $v$, where $Tv=\lambda v$.

There is a basis $e_1,\dots ,e_n$ of $V$ with ${\phi }_i(e_j)={\delta }_{ij}$, since the dual basis construction gives a finite-dimensional bidual evaluation map isomorphism. In particular $e_n=v$. The matrix transpose relationship for a dual map givesa lower triangular matrix. Reversing this basis turns a lower triangular matrix into an upper triangular matrix. If $R$ is the permutation matrix reversing the order, we have provedThis completes the induction by triangularization using dual spaces.

A family $x_1,\dots ,x_n$ is linearly independent if ${\sum }_{i=1}^n{a}_i{x}_i=0$ forces $a_1=\cdots =a_n=0$. For the three specified vectors, direct substitution givesThe coefficients are not all zero, so the vectors are linearly dependent.

For the implication question, using the usual interpretation that a basis contains the listed family as independent entries, the answers in order (i)–(x) areThe key distinctions are that the unrestricted zero combination always exists, whereas linear dependence requires a nontrivial combination; and dependence does not necessarily let the specified third vector be solved in terms of the first two. For example $x=y=e_1$, $z=e_2$ makes (iii) and (iv) false, while $x=e_1,y=e_2,z=e_3$ disproves (vi).

There is a set-versus-family qualification in (v). If “contains” is interpreted as literal set containment, repeated nonzero vectors need only occur once in the basis. Then $x=y=e_1,z=e_2$ is dependent as a family but all three belong to the basis $\{e_1,e_2\}$, so (v) becomes false. With three distinct vectors, or with family-containment as above, basis extension gives (v) true. Implication (x) remains true on either reading.

For a linear map $T:V\to W$ with $V$ finite-dimensional, the rank-nullity theorem statesTo prove it, choose a basis $v_1,\dots ,v_k$ of the kernel of a linear map and use basis extension to obtain $v_1,\dots ,v_n$ as a basis of $V$. The vectors $T{v}_{k+1},\dots ,T{v}_n$ span the image of a linear map: applying $T$ to a basis expansion kills the first $k$ terms. They are also linearly independent. Indeed, if ${\sum }_{j>k}{a}_{j}T{v}_j=0$, then ${\sum }_{j>k}{a}_j{v}_j\in \ker T$, so it is a combination of $v_1,\dots ,v_k$. Independence of the full basis forces every $a_j=0$. Consequently $\dim \mathrm{im}T=n-k$, proving the theorem.

Here the image of a linear map has dimension $r\in \{0,1,2,3\}$, since it lies in ${\mathbb{R}}^3$. ThusEvery possibility occurs: for $0\le r\le 3$, map $(x_1,\dots ,x_5)$ to $(x_1,\dots ,x_r,0,\dots ,0)\in {\mathbb{R}}^3$. This map has rank $r$ and kernel dimension $5-r$.

The algebraic dual map is $\delta ={\alpha }^{\vee }:W^{\ast }\to V^{\ast }$, defined by $\delta (\phi )=\phi \circ \alpha$. The annihilator of a vector subspace $U\subseteq V$ isEvery functional $\phi \circ \alpha$ vanishes on $\ker \alpha$, so $\mathrm{im}\delta \subseteq (\ker \alpha {)}^{\circ }$. Conversely, let $\lambda \in (\ker \alpha {)}^{\circ }$. Define a functional on $\mathrm{im}\alpha$ by $\tilde{\lambda }(\alpha v)=\lambda (v)$. It is well defined because two preimages differ by an element of $\ker \alpha$. Extend a basis of $\mathrm{im}\alpha$ to one of $W$ and extend the functional arbitrarily, for instance by zero on the extra basis vectors. The resulting $\phi \in W^{\ast }$ satisfies $\delta \phi =\lambda$.

This is the dual image and kernel annihilator identity. ThereforeThe basis extension theorem also gives $\dim U^{\circ }=\dim V-\dim U$. By the rank-nullity theorem,Apply rank-nullity theorem to both maps, using $\dim W^{\ast }=\dim W$, to obtainOver $\mathbb{C}$, this is the algebraic dual, without complex conjugation; the adjoint operator in part (b) uses the inner products instead.

For a finite set $S=\{s_1,\dots ,s_k\}$ of vectors in a real vector space, its span is the set of all linear combinations:The span of the empty set is $\{0\}$. The set $S$ is linearly independent if ${\sum }_i{a}_i{s}_i=0$ implies $a_i=0$ for every $i$. It is a spanning set for $V$ if $\mathrm{Sp}(S)=V$. A basis is both a linearly independent set and a spanning set.

For basis extension, start with the given linearly independent set. If it does not span $V$, choose $v\notin \mathrm{Sp}(S)$ and adjoin it. The enlarged set remains linearly independent: a relation $av+{\sum }_i{a}_i{s}_i=0$ with $a\ne 0$ would express $v$ as a linear combination of $S$, a contradiction; if $a=0$, independence of $S$ forces all other coefficients to be zero.

Repeat whenever the current span is proper. Each step increases the set's size by one, while the allowed bound says its size cannot exceed $\dim V$. Thus the process terminates with a linearly independent set spanning $V$, hence a basis containing the original set. This also covers an initially empty set and the zero-dimensional vector space.

The rank of a linear map and nullity of a linear map areThe rank-nullity theorem states thatTo prove it, choose a basis $u_1,\dots ,u_k$ of the kernel of a linear map and use basis extension to obtain a basisof $V$. The vectors $T(v_1),\dots ,T(v_{n-k})$ span the image of a linear map: applying $T$ to an arbitrary linear combination of the displayed basis removes all the $u_i$ terms. They are also linearly independent. Indeed,so ${\sum }_j{a}_j{v}_j={\sum }_i{b}_i{u}_i$ for some scalars $b_i$. The linear independence of the extended basis forces every $a_j$ and $b_i$ to vanish. Consequently $r(T)=n-k$ and $n(T)=k$, proving the identity. The same argument covers an empty basis when one of these dimensions is zero.

Use basis extension to choose a basis $(v,v_2,\dots ,v_n)$ of the vector space $V$ over the finite field ${\mathbb{F}}_p={\mathbb{Z}}_p$. The condition $T(v)=0$ fixes the first value of a linear functional; its remaining $n-1$ values are arbitrary. There are $p^{n-1}$ such linear maps, exactly one of which is zero. Hence the required number isFor $n=1$ this is zero, as it should be: vanishing at a basis vector then forces the entire linear functional to vanish.

For quantifier elimination for infinite underlying vector spaces, we first justify that formulas cannot make finer distinctions than their linear-equation data. In any infinite underlying vector space, eliminate an existential variable from a disjunction of conjunctions of linear equations and inequations. If an equation has a nonzero coefficient of that variable, solve for it and substitute. If none does, the inequations forbid only finitely many values, leaving an available value in the infinite domain; the remaining equations concern only the other variables. Terms are linear combinations, so induction gives quantifier elimination for $T$ and completeness, since closed terms reduce to zero.

For one variable there are two possible complete types, zero and nonzero. Both are isolated, and every definable set is their union. ThusFor types of pairs of vectors over a finite field, the linear relation kernel $\{(a,b)\in K^2:ax+by=0\}$ determines the complete type. If $q=|K|$, the possibilities are one rank-zero pair, $q+1$ rank-one directions, and one rank-two independent type. Concretely these are $(0,0)$; $x\ne 0$ with $y={\lambda }_a(x)$ for each $a\in K$; $x=0,y\ne 0$; and the independent pairs. Their isolating formulas are finite because $K$ is finite. HenceEvery class is the union of a selection of these atoms. Basis extension also shows that pairs with the same relation kernel are conjugate by a linear automorphism within any infinite-dimensional model.

The rank-nullity theorem states that a linear map $T:V\to W$ with finite-dimensional $V$ satisfiesChoose a basis $k_1,\dots ,k_r$ of $\ker T$ and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We prove that $T{u}_1,\dots ,T{u}_s$ is a basis of $\mathrm{im}T$.

Every $v\in V$ is a linear combination of the extended basis. Applying $T$ kills the $k_i$ terms, so $Tv$ is a linear combination of $T{u}_1,\dots ,T{u}_s$. This proves the linear span assertion. For linear independence, if ${\sum }_j{b}_{j}T{u}_j=0$, then ${\sum }_j{b}_j{u}_j$ belongs to the kernel of a linear map. Hence ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some scalars $a_i$. The linear independence of the extended basis forces every $a_i$ and $b_j$ to vanish. Consequently $\mathrm{rank}T=s$ and $\mathrm{nullity}T=r$, while $\dim V=r+s$, proving the theorem.

The rank-nullity theorem says that for a linear map $T:V\to W$ with finite-dimensional domain of a function $V$,Take a basis $k_1,\dots ,k_r$ of the kernel of a linear map and use basis extension to obtain a basis $k_1,\dots ,k_r,u_1,\dots ,u_s$ of $V$. We show that $T(u_1),\dots ,T(u_s)$ is a basis of the image of a linear map.

Every $v\in V$ is a linear combination of the extended basis, and its $k_i$ terms vanish under $T$. Therefore $T(v)$ is a linear combination of the $T(u_j)$, proving the required linear span property. For linear independence, suppose ${\sum }_j{b}_{j}T(u_j)=0$. Then ${\sum }_j{b}_j{u}_j\in \ker T$, so ${\sum }_j{b}_j{u}_j={\sum }_i{a}_i{k}_i$ for some real scalars $a_i$. The extended basis is linearly independent, forcing every $a_i$ and $b_j$ to be zero. Thus the image of a linear map has dimension $s$, the kernel of a linear map has dimension $r$, and $\dim V=r+s$ proves the result.