View source for Basis (linear algebra)

{{redirect|Basis vector|basis vector in the context of crystals|Crystal structure|a more general concept in physics|Frame of reference}}
{{redirects here|Basis (mathematics)||Basis (disambiguation)#Mathematics{{!}}Basis}}
[[File:3d two bases same vector.svg|130px|thumb|The same vector can be represented in two different bases (purple and red arrows).]]
In [[mathematics]], a set {{mvar|B}} of elements (vectors) in a [[vector space]] {{math|''V''}} is called a '''basis''', if every element of {{math|''V''}} may be written in a unique way as a (finite) [[linear combination]] of elements of {{mvar|B}}. The coefficients of this linear combination are referred to as '''components''' or '''coordinates''' on {{mvar|B}} of the vector. The elements of a basis are called '''{{visible anchor|basis vectors}}'''.

Equivalently {{mvar|B}} is a basis if its elements are linearly independent and every element of {{mvar|V}} is a linear combination of elements of {{mvar|B}}.<ref>{{cite book |last=Halmos |first=Paul Richard |authorlink=Paul Halmos |year=1987 |title=Finite-Dimensional Vector Spaces |edition=4th |publisher=Springer |location=New York |url=https://books.google.com/books?id=mdWeEhA17scC&pg=PA10 |page=10 |isbn=978-0-387-90093-3 }}</ref>  In more general terms, a basis is a linearly independent [[spanning set]].

A vector space can have several bases; however all the bases have the same number of elements, called the [[dimension (vector space)|dimension]] of the vector space.

== Definition ==
A '''basis''' {{math|''B''}} of a [[vector space]] {{math|''V''}} over a [[field (mathematics)|field]] {{math|''F''}} (such as the [[real numbers]] {{math|'''R'''}} or the [[complex number]]s {{math|'''C'''}}) is a [[Linear independence|linearly independent]] subset of {{math|''V''}} that [[linear span|span]]s {{mvar|''V''}}.
This means that a subset {{mvar|B}} of {{math|''V''}} is a basis if it satisfies the two following conditions:
* the ''linear independence'' property:
:: for every finite subset {{math|{''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>}{{void}}}} of {{mvar|B}} and every {{math|''a''<sub>1</sub>, ..., ''a''<sub>''n''</sub>}} in  {{math|''F''}}, if {{math|1=''a''<sub>1</sub>''b''<sub>1</sub> + ⋅⋅⋅ + ''a''<sub>''n''</sub>''b''<sub>''n''</sub> = 0}}, then necessarily {{math|1=''a''<sub>1</sub> = ⋅⋅⋅ = ''a''<sub>''n''</sub> = 0}};
* the ''spanning'' property:
:: for every (vector) {{math|''v''}} in {{math|''V''}}, it is possible to choose {{math|''v''<sub>1</sub>, ..., ''v''<sub>''n''</sub>}} in {{math|''F''}} and {{math|''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>}} in {{mvar|B}} such that {{math|1=''v'' = ''v''<sub>1</sub>''b''<sub>1</sub> + ⋅⋅⋅ + ''v''<sub>''n''</sub>''b''<sub>''n''</sub>}}.

The [[scalar (mathematics)|scalar]]s {{math|''v''<sub>''i''</sub>}} are called the coordinates of the vector {{math|''v''}} with respect to the basis {{math|''B''}}, and by the first property they are uniquely determined.

A vector space that has a [[finite set|finite]] basis is called [[Dimension (vector space)|finite-dimensional]]. In this case, the subset {{math|{''b''<sub>1</sub>, ..., ''b''<sub>''n''</sub>}{{void}}}} that is considered (twice) in the above definition may be chosen as {{mvar|B}} itself.

It is often convenient or even necessary to have an [[sequence|ordering]] on the basis vectors, e.g. for discussing [[orientation (vector space)|orientation]], or when one considers the scalar coefficients of a vector with respect to a basis, without referring explicitly to the basis elements. In this case, the ordering is necessary for associating each coefficient to the corresponding basis element. This ordering can be done by numbering the basis elements. For example, when dealing with [[matrix (mathematics)|(''m'', ''n'')-matrices]], the {{math|(''i'', ''j'')th}} element (in the {{mvar|i}}th row and {{mvar|j}}th column) can be referred to the {{math|(''m''⋅(''j'' - 1) + ''i'')}}th element of a basis consisting of the (''m'', ''n'')-unit-matrices (varying column-indices before row-indices). For emphasizing that an order has been chosen, one speaks of an '''ordered basis''', which is therefore not simply an unstructured [[Set (mathematics)|set]], but e.g. a [[sequence]], or an [[indexed family]], or similar; see ''[[#Ordered bases and coordinates|Ordered bases and coordinates]]'' below.

== Examples ==
[[File:Basis graph (no label).svg|thumb|400px|This picture illustrates the [[standard basis]] in '''''R'''<sup>2</sup>''. The blue and orange vectors are the elements of the basis; the green vector can be given in terms of the basis vectors, and so is [[linearly dependent]] upon them.]]
*The set [[exponentiation over sets|{{math|'''R'''<sup>2</sup>}}]] of the [[ordered pair]]s of [[real number]]s is a vector space for the component-wise addition
::<math>(a, b) + (c, d) = (a + c, b+d),</math>
:and scalar multiplication 
::<math>\lambda (a,b) = (\lambda a, \lambda b),</math>
:where <math>\lambda</math> is any real number. A simple basis of this vector space, called the [[standard basis]] consists of the two vectors {{math|1=''e''<sub>1</sub> = (1,0)}} and {{math|1=''e''<sub>2</sub> = (0,1)}}, since, any vector {{math|1=''v'' = (''a'', ''b'')}} of {{math|'''R'''<sup>2</sup>}} may be uniquely written as
::<math>v= ae_1+be_2.</math>
:Any other pair of linearly independent vectors of {{math|'''R'''<sup>2</sup>}}, such as {{math|(1, 1)}} and {{math|(−1, 2)}}, forms also a basis of '''R'''<sup>2</sup>.
*More generally, if {{mvar|F}} is a [[field (mathematics)|field]], the set <math>F^n</math> of [[tuple|{{mvar|n}}-tuples]] of elements of {{mvar|F}} is a vector space for similarly defined addition and scalar multiplication. Let
::<math>e_i = (0, \ldots, 0,1,0,\ldots, 0)</math>
: be the {{mvar|n}}-tuple with all components equal to 0, except the {{mvar|i}}th, which is 1. Then <math>e_1, \ldots, e_n</math> is a basis of <math>F^n,</math> which is called the ''standard basis'' of <math>F^n.</math>
*If {{mvar|F}} is a field, the [[polynomial ring]] {{math|''F''[''X'']}} of the [[polynomial]]s in one [[indeterminate (variable)|indeterminate]] has a basis {{mvar|B}}, called the [[monomial basis]], consisting of all [[monomial]]s:
::<math>B=\{1, X, X^2, \ldots\}.</math>
:Any set of polynomials such that there is exactly one polynomial of each degree is also a basis. Such a set of polynomials is called a [[polynomial sequence]]. Example (among many) of such polynomial sequences are [[Bernstein polynomial|Bernstein basis polynomial]]s, and [[Chebyshev polynomials]].

== Properties ==

Many properties of finite bases result from the [[Steinitz exchange lemma]], which states that, given a finite [[spanning set]] {{mvar|S}} and a [[linearly independent]] subset {{mvar|L}} of {{mvar|n}} elements of {{mvar|S}}, one may replace {{mvar|n}} well chosen elements of {{mvar|S}} by the elements of {{mvar|L}} for getting a spanning set containing {{mvar|L}}, having its other elements in {{mvar|S}}, and having the same number of elements as {{mvar|S}}.

Most properties resulting from the Steinitz exchange lemma remain true when there is no finite spanning set, but their proof in the infinite case requires generally the [[axiom of choice]] or a weaker form of it, such as the [[ultrafilter lemma]].

If {{mvar|V}} is a vector space over a field {{mvar|F}}, then:
* If {{mvar|L}} is a linearly independent subset of a spanning set {{math|''S'' ⊆ ''V''}}, then there is a basis {{mvar|B}} such that 
::<math>L\subseteq B\subseteq S.</math>
* {{mvar|V}} has a basis (this is the preceding property with {{mvar|L}} being the [[empty set]], and {{math|1=''S'' = ''V''}}).
* All bases of {{mvar|V}} have the same [[cardinality]], which is called the [[Dimension (vector space)|dimension]] of {{mvar|V}}. This is the [[dimension theorem for vector spaces|dimension theorem]].
* A generating set {{mvar|S}} is a basis of {{mvar|V}} if and only if it is minimal, that is, no [[subset|proper subset]] of {{mvar|S}} is also a generating set of {{mvar|V}}.
* A linearly independent set {{mvar|L}} is a basis if and only if it is maximal, that is, it is not a proper subset of any linearly independent set.

If {{mvar|V}} is a vector space of dimension {{mvar|n}}, then:
* A subset of {{mvar|V}} with {{mvar|n}} elements is a basis if and only if it is linearly independent.
* A subset of {{mvar|V}} with {{mvar|n}} elements is a basis if and only if it is spanning set of {{mvar|V}}.

== Coordinates {{anchor|Ordered bases and coordinates}} ==

Let {{mvar|V}} be a vector space of finite dimension {{mvar|n}} over a field {{mvar|F}}, and 
:<math>B=\{b_1, \ldots, b_n\}</math>
be a basis of {{mvar|V}}. By definition of a basis, for every {{mvar|v}} in {{mvar|V}} may be written, in a unique way,
:<math>v=\lambda_1 b_1 + \cdots + \lambda_n b_n,</math>
where the coefficients <math>\lambda_1, \ldots, \lambda_n</math> are scalars (that is, elements of {{mvar|F}}), which are called the ''coordinates'' of {{mvar|v}} over {{mvar|B}}. However, if one talks of the ''set'' of the coefficients, one looses the correspondence between coefficients and basis elements, and several vectors may have the same ''set'' of coefficients. For example, <math>3b_1 +2b_2</math> and <math>2b_1 +3b_2</math> have the same set of coefficients {{math|{2, 3}{{void}}}}, and are different. It is therefore often convenient to work with an '''ordered basis'''; this is typically done by [[index set|indexing]] the basis elements by the first natural numbers. Then, the coordinates of a vector form a [[sequence (mathematics)|sequence]] similarly indexed, and a vector is completely characterized by the sequence of coordinates. An ordered basis is also called a '''frame''', a word commonly used, in various contexts, for referring to a sequence of data allowing defining coordinates.

Let, as usual, <math>F^n</math> be the set of the [[tuple|{{mvar|n}}-tuples]] of elements of {{mvar|F}}. This set is an {{mvar|F}}-vector space, with addition and scalar multiplication defined component-wise. The map 
:<math>\varphi: (\lambda_1, \ldots, \lambda_n) \mapsto \lambda_1 b_1 + \cdots + \lambda_n b_n</math>
is a [[linear isomorphism]] from the vector space <math>F^n</math> onto {{mvar|V}}. In other words, <math>F^n</math> is the [[coordinate space]] of {{mvar|V}}, and the {{mvar|n}}-tuple <math>\varphi^{-1}(v)</math> is the [[coordinate vector]] of {{mvar|v}}.

The [[inverse image]] by <math>\varphi</math> of <math>b_i</math> is the {{mvar|n}}-tuple <math>e_i</math> all of whose components are 0, except the {{mvar|i}}th that is 1. The <math>e_i</math> form an ordered basis of <math>F^n,</math> which is called its [[standard basis]] or [[canonical basis]]. The ordered basis {{mvar|B}} is the image by <math>\varphi</math> of the canonical basis of <math>F^n.</math> 

It follows from what precedes that every ordered basis is the image by a linear isomorphism of the canonical basis of <math>F^n,</math> and that every linear isomorphism from <math>F^n</math> onto {{mvar|V}} may be defined as the isomorphism that maps the canonical basis of <math>F^n</math> onto a given ordered basis of {{mvar|V}}. In other words it is equivalent to define an ordered basis of {{mvar|V}}, or a linear isomorphism from <math>F^n</math> onto {{mvar|V}}.

== Change of basis ==
{{main|Change of basis}}
Let {{math|''V''}} be a vector space of dimension {{mvar|n}} over a field {{math|''F''}}. Given two (ordered) bases <math>B_\mathrm {old}=(v_1, \ldots, v_n)</math> and <math>B_\mathrm {new}=(w_1, \ldots, w_n)</math> of {{math|''V''}}, it is often useful to express the coordinates of a vector {{mvar|x}} with respect to <math>B_\mathrm {old}</math> in terms of the coordinates with respect to <math>B_\mathrm {new}.</math> This can be done by the ''change-of-basis formula'', that is described below. The subscripts "old" and "new" have been chosen because it is customary to refer to <math>B_\mathrm {old}</math> and <math>B_\mathrm {new}</math> as the ''old basis'' and the ''new basis'', respectively. It is useful to describe the old coordinates in terms of the new ones, because, in general, one has [[expression (mathematics)|expressions]] involving the old coordinates, and if one wants to obtain equivalent expressions in terms of the new coordinates; this is obtained by replacing  the old coordinates by their expressions in terms of the new coordinates.

Typically, the new basis vectors are given by their coordinates over the old basis, that is, 
:<math>w_j=\sum_{i=1}^n a_{i,j}v_i.</math>
If <math>(x_1, \ldots, x_n)</math> and <math>(y_1, \ldots, y_n)</math> are the coordinates of a vector {{mvar|x}} over the old and the new basis respectively, the change-of-basis formula is 
:<math>x_i = \sum_{j=1}^n a_{i,j}y_j,</math>
for {{math|1=''i'' = 1, ..., ''n''}}.

This formula may be concisely written in [[matrix (mathematics)|matrix]] notation. Let {{mvar|A}} be the matrix of the <math>a_{i,j},</math> and
:<math>X= \begin{pmatrix}x_1\\\vdots\\x_n\end{pmatrix}\quad</math> and <math>\quad Y= \begin{pmatrix}y_1\\\vdots\\y_n\end{pmatrix}</math>
be the [[column vector]]s of the coordinates of {{mvar|v}} in the old and the new basis respectively, then the formula for changing coordinates is
:<math>X=AY.</math>

The formula can be proven by considering the decomposition of the vector {{mvar|x}} on the two bases: one has 
:<math>x=\sum_{i=1}^n x_i v_i,</math>
and
:<math>\begin{align}
x&=\sum_{j=1}^n y_j w_j \\
 &=\sum_{j=1}^n y_j\sum_{i=1}^n a_{i,j}v_i\\
 &=\sum_{i=1}^n \left(\sum_{j=1}^n a_{i,j}y_j\right)v_i.
\end{align}</math>

The change-of-basis formula results then from the uniqueness of the decomposition of a vector over a basis, here <math>B_\mathrm {old};</math> that is
:<math>x_i = \sum_{j=1}^n a_{i,j}y_j,</math>
for {{math|1=''i'' = 1, ..., ''n''}}.

== Related notions ==
===Free module===
{{main|Free module|Free abelian group}} 
If one replaces the field occurring in the definition of a vector space by a [[ring (mathematics)|ring]], one gets the definition of a [[module (mathematics)|module]]. For modules, [[linear independence]] and [[spanning set]]s are defined exactly as for vector spaces, although "[[generating set of a module|generating set]]" is more commonly used than that of "spanning set".

Like for vector spaces, a ''basis'' of a module is a linearly independent subset that is also a generating set. A major difference with the theory of vector spaces is that not every module has a basis. A module that has a basis is called a ''free module''. Free modules play a fundamental role in module theory, as they may be used for describing the structure of non-free modules through [[free resolution]]s.

A module over the integers is exactly the same thing as an [[abelian group]]. Thus a free module over the integers is also a free abelian group. Free abelian groups have specific properties that are not shared by modules over other rings. Specifically, every subgroup of a free abelian group is a free abelian group, and, if {{mvar|G}} is a subgroup of a finitely generated free abelian group {{mvar|H}} (that is an abelian group that has a finite basis), there is a basis <math>e_1, \ldots, e_n</math> of {{mvar|H}} and an integer {{math|0 ≤ ''k'' ≤ ''n''}} such that <math>a_1e_1, \ldots, a_ke_k</math> is a basis of {{mvar|G}}, for some nonzero integers <math>a_1, \ldots, a_k.</math> For details, see {{slink|Free abelian group|Subgroups}}.

=== Analysis ===
In the context of infinite-dimensional vector spaces over the real or complex numbers, the term '''{{visible anchor|Hamel basis}}''' (named after [[Georg Hamel]]) or '''algebraic basis''' can be used to refer to a basis as defined in this article. This is to make a distinction with other notions of "basis" that exist when infinite-dimensional vector spaces are endowed with extra structure. The most important alternatives are [[orthogonal basis|orthogonal bases]] on [[Hilbert space]]s, [[Schauder basis|Schauder bases]], and [[Markushevich basis|Markushevich bases]] on [[normed linear space]]s. In the case of the real numbers '''R''' viewed as a vector space over the field '''Q''' of rational numbers, Hamel bases are uncountable, and have specifically the [[cardinality]] of the continuum, which is the [[cardinal number]] <math>2^{\aleph_0},</math> where <math>\aleph_0</math> is the smallest infinite cardinal, the cardinal of the integers.

The common feature of the other notions is that they permit the taking of infinite linear combinations of the basis vectors in order to generate the space. This, of course, requires that infinite sums are meaningfully defined on these spaces, as is the case for [[topological vector space]]s – a large class of vector spaces including e.g. [[Hilbert space]]s, [[Banach space]]s, or [[Fréchet space]]s.

The preference of other types of bases for infinite-dimensional spaces is justified by the fact that the Hamel basis becomes "too big" in Banach spaces: If ''X'' is an infinite-dimensional normed vector space which is [[complete space|complete]] (i.e. ''X'' is  a [[Banach space]]), then any Hamel basis of ''X'' is necessarily [[uncountable]]. This is a consequence of the [[Baire category theorem]]. The completeness as well as infinite dimension are crucial assumptions in the previous claim. Indeed, finite-dimensional spaces have by definition finite bases and there are infinite-dimensional (''non-complete'') normed spaces which have countable Hamel bases. Consider  <math>c_{00}</math>, the space of the [[sequence]]s <math>x=(x_n)</math> of real numbers which have only finitely many non-zero elements, with the norm <math>\|x\|=\sup_n |x_n|.</math> Its [[standard basis]], consisting of the sequences having only one non-zero element, which is equal to 1, is a countable Hamel basis.

==== Example ====
In the study of [[Fourier series]], one learns that the functions {1} ∪ { sin(''nx''), cos(''nx'') : ''n'' = 1, 2, 3, ... } are an "orthogonal basis" of the (real or complex) vector space of all (real or complex valued) functions on the interval [0, 2π] that are square-integrable on this interval, i.e., functions ''f'' satisfying

:<math>\int_0^{2\pi} \left|f(x)\right|^2\,dx<\infty.</math>

The functions {1} ∪ { sin(''nx''), cos(''nx'') : ''n'' = 1, 2, 3, ... } are linearly independent, and every function ''f'' that is square-integrable on [0, 2π] is an "infinite linear combination" of them, in the sense that

:<math>\lim_{n\rightarrow\infty}\int_0^{2\pi}\biggl|a_0+\sum_{k=1}^n \bigl(a_k\cos(kx)+b_k\sin(kx)\bigr)-f(x)\biggr|^2\,dx=0</math>

for suitable (real or complex) coefficients ''a''<sub>''k''</sub>, ''b''<sub>''k''</sub>.  But many<ref>Note that one cannot say "most" because the cardinalities of the two sets (functions that can and cannot be represented with a finite number of basis functions) are the same.</ref> square-integrable functions cannot be represented as ''finite'' linear combinations of these basis functions, which therefore ''do not'' comprise a Hamel basis. Every Hamel basis of this space is much bigger than this merely countably infinite set of functions. Hamel bases of spaces of this kind are typically not useful, whereas [[orthonormal bases]] of these spaces are essential in [[Fourier analysis]].

===Geometry===
The geometric notions of an [[affine space]], [[projective space]], [[convex set]], and [[Cone (linear algebra)|cone]] have related notions of {{anchor|affine basis}} ''basis''.<ref>{{cite book |title=Notes on Geometry |first=Elmer G. |last=Rees |location=Berlin |publisher=Springer |year=2005 |url=https://books.google.com/books?id=JkzPRaihGIYC&pg=PA7 |page=7 |isbn=978-3-540-12053-7 }}</ref> An '''affine basis''' for an ''n''-dimensional affine space is <math>n+1</math> points in [[general linear position]]. A  '''{{visible anchor|projective basis}}''' is <math>n+2</math> points in general position, in a projective space of dimension ''n''. A '''{{visible anchor|convex basis}}''' of a [[polytope]] is the set of the vertices of its [[convex hull]]. A '''{{visible anchor|cone basis}}'''<ref>{{cite journal |title=Some remarks about additive functions on cones |first=Marek |last=Kuczma |journal=[[Aequationes Mathematicae]] |year=1970 |volume=4 |issue=3 |pages=303–306 |doi=10.1007/BF01844160 }}</ref> consists of one point by edge of a polygonal cone. See also a [[Hilbert basis (linear programming)]].

===Random basis===
For a [[probability distribution]] in '''R'''<sup>''n''</sup> with a [[probability density function]], such as the equidistribution  in a ''n''-dimensional ball with respect to Lebesgue measure, it can be shown that ''n'' randomly and independently chosen vectors will form a basis [[with probability one]], which is due to the fact that ''n'' linearly dependent vectors '''x'''<sub>1</sub>, ..., '''x'''<sub>''n''</sub> in '''R'''<sup>''n''</sup> should satisfy the equation {{nowrap|1=det['''x'''<sub>1</sub>, ..., '''x'''<sub>''n''</sub>] = 0}} (zero determinant of the matrix with columns '''x'''<sub>''i''</sub>), and the set of zeros of a non-trivial polynomial has zero measure. This observation has led to techniques for approximating random bases.<ref>{{cite journal |first=B. |last=Igelnik |first2=Y.-H. |last2=Pao |title=Stochastic choice of basis functions in adaptive function approximation and the functional-link net |journal=IEEE Trans. Neural Netw. |volume=6 |issue=6 |year=1995 |pages=1320–1329 |doi=10.1109/72.471375 |pmid=18263425 }}</ref><ref name = "GorbanTyukin2016">{{cite journal
 | first1 = Alexander N. | last1 = Gorban | author1-link = Aleksandr Gorban
 | first2 = Ivan Y. | last2 = Tyukin | first3 = Danil V. | last3 = Prokhorov | first4 = Konstantin I. | last4 = Sofeikov
 | doi = 10.1016/j.ins.2015.09.021
 | pages = 129-145
 | journal = [[Information Sciences (journal)|Information Sciences]]
 | title = Approximation with Random Bases: Pro et Contra
 | volume = 364-365
 | year = 2016
 | arxiv = 1506.04631}}</ref>

[[File:Random almost orthogonal sets.png|thumb|270px|Empirical distribution of lengths N of pairwise almost orthogonal chains of vectors that are independently randomly sampled from the ''n''-dimensional cube {{nowrap|[−1, 1]<sup>''n''</sup>}} as a function of dimension, ''n''. Boxplots show the second and third quartiles of this data for each ''n'', red bars correspond to the medians, and blue stars indicate means. Red curve shows theoretical bound given by Eq. (1) and green curve shows a refined estimate.<ref name = "GorbanTyukin2016"/>]] 

It is difficult to check numerically the linear dependence or exact orthogonality. Therefore, the notion of ε-orthogonality is used. For [[Inner product space|spaces with inner product]],  ''x'' is  ε-orthogonal to ''y'' if <math>|\langle x,y \rangle|/(\|x\|\|y\|)<\epsilon</math> (that is, cosine  of the angle between ''x'' and ''y'' is less than ε).

In high dimensions, two independent random vectors are with high probability almost orthogonal, and the number of independent random vectors, which all are with given high probability pairwise almost orthogonal, grows exponentially with dimension. More precisely, consider equidistribution in ''n''-dimensional ball. Choose ''N'' independent random vectors from a ball (they are [[Independent and identically distributed random variables|independent and identically distributed]]). Let ''θ'' be a small positive number. Then for

{{NumBlk|:|<math>N\leq e^{\frac{\epsilon^2n}{4}}[-\ln(1-\theta)]^{\frac{1}{2}}</math>|Eq. 1}}

''N'' random vectors are all pairwise ε-orthogonal with probability {{nowrap|1 − ''θ''}}.<ref name = "GorbanTyukin2016"/> This ''N'' growth exponentially with dimension ''n'' and <math>N\gg n</math> for sufficiently big ''n''. This property of random bases is a manifestation of the so-called ''measure concentration phenomenon''.<ref>{{cite journal |first=S. |last=Artstein|authorlink=Shiri Artstein |title=Proportional concentration phenomena of the sphere |journal=[[Israel Journal of Mathematics|Israel J. Math.]] |volume=132 |year=2002 |issue=1 |pages=337–358 |doi=10.1007/BF02784520 |url=http://www.tau.ac.il/~shiri/israelj/ISRAJ.pdf |citeseerx=10.1.1.417.2375}}</ref>

The figure (right) illustrates distribution of lengths N of pairwise almost orthogonal chains of vectors that are independently randomly sampled from the ''n''-dimensional cube {{nowrap|[−1, 1]<sup>''n''</sup>}} as a function of dimension, ''n''. A point is first randomly selected in the cube. The second point is randomly chosen in the same cube. If the angle between the vectors was within {{nowrap|π/2 ± 0.037π/2}} then the vector was retained. At the next step a new vector is generated in the same hypercube, and its angles with the previously generated vectors are evaluated. If these angles are within {{nowrap|π/2 ± 0.037π/2}} then the vector is retained. The process is repeated until the chain of almost orthogonality breaks, and the number of such pairwise almost orthogonal vectors (length of the chain) is recorded. For each ''n'', 20 pairwise almost orthogonal chains where constructed numerically for each dimension. Distribution of the length of these chains is presented.

==Proof that every vector space has a basis==

Let '''V''' be any vector space over some field '''F'''.
Let '''X''' be the set of all linearly independent subsets of '''V'''.

The set '''X''' is nonempty since the empty set is an independent subset of '''V''',
and it is [[Partial order|partially ordered]] by inclusion, which is denoted, as usual, by {{math|⊆}}.

Let '''Y''' be a subset of '''X''' that is totally ordered by {{math|⊆}},
and let L<sub>'''Y'''</sub> be the union of all the elements of '''Y''' (which are themselves certain subsets of '''V''').

Since ('''Y''', ⊆) is totally ordered, every finite subset of L<sub>'''Y'''</sub> is a subset of an element of '''Y''',
which is a linearly independent subset of '''V''',
and hence every finite subset of L<sub>'''Y'''</sub> is linearly independent.
Thus L<sub>'''Y'''</sub> is linearly independent, so L<sub>'''Y'''</sub> is an element of '''X'''.
Therefore, L<sub>'''Y'''</sub> is an upper bound for '''Y''' in ('''X''', ⊆):
it is an element of '''X''', that contains every element '''Y'''.

As '''X''' is nonempty, and every totally ordered subset of ('''X''', ⊆) has an upper bound in '''X''', [[Zorn's lemma]] asserts that '''X''' has a maximal element. In other words, there exists some element L<sub>'''max'''</sub> of '''X''' satisfying the condition that whenever L<sub>'''max'''</sub> ⊆ L for some element L of '''X''', then L = L<sub>'''max'''</sub>.

It remains to prove that L<sub>'''max'''</sub> is a basis of '''V'''.  Since L<sub>'''max'''</sub> belongs to '''X''', we already know that L<sub>'''max'''</sub> is a linearly independent subset of '''V'''.

If L<sub>'''max'''</sub> would not span '''V''', there would exist some vector '''w''' of '''V''' that cannot be expressed as a linear combination of elements of L<sub>'''max'''</sub> (with coefficients in the field '''F'''). In particular, '''w''' cannot be an element of L<sub>'''max'''</sub>.
Let L<sub>'''w'''</sub>  =  L<sub>'''max'''</sub> ∪ {'''w'''}. This set is an element of '''X''', that is, it is a linearly independent subset of '''V''' (because '''w''' is not in the span of L<sub>'''max'''</sub>, and L<sub>'''max'''</sub> is independent). As L<sub>'''max'''</sub> ⊆ L<sub>'''w'''</sub>, and L<sub>'''max'''</sub> ≠ L<sub>'''w'''</sub> (because L<sub>'''w'''</sub> contains the vector '''w''' that is not contained in L<sub>'''max'''</sub>), this contradicts the maximality of L<sub>'''max'''</sub>. Thus this shows that L<sub>'''max'''</sub> spans '''V'''.

Hence L<sub>'''max'''</sub> is linearly independent and spans '''V'''. It is thus a basis of '''V''', and this proves that every vector space has a basis.

This proof relies on Zorn's lemma, which is equivalent to the [[axiom of choice]]. Conversely, it has been proved that if every vector space has a basis, then the axiom of choice is true.<ref>Blass, Andrea (1984). [http://www.math.lsa.umich.edu/~ablass/bases-AC.pdf ''Existence of bases implies the Axiom of Choice'']. Contemporary Mathematics. '''31'''. pp. 31-33.</ref> Thus the two assertions are equivalent.

==See also==
* [[Change of basis]]
* [[Frame of a vector space]]
* [[Spherical basis]]

==Notes==
{{Reflist}}

==References==

===General references===
* {{Citation | last1=Blass | first1=Andreas | title=Axiomatic set theory  | publisher=[[American Mathematical Society]] | location=Providence, R.I. | series=Contemporary Mathematics volume 31 | mr=763890 | year=1984 | chapter=Existence of bases implies the axiom of choice | pages=31–33|isbn=978-0-8218-5026-8}}
* {{Citation | last1=Brown | first1=William A. | title=Matrices and vector spaces | publisher=M. Dekker | location=New York | isbn=978-0-8247-8419-5 | year=1991|url=https://books.google.com/books?id=pFQYKlnW5Z0C&printsec=frontcover#v=onepage&q=basis&f=false}}
* {{Citation | last1=Lang | first1=Serge | author1-link=Serge Lang | title=Linear algebra | publisher=[[Springer-Verlag]] | location=Berlin, New York | isbn=978-0-387-96412-6 | year=1987}}

===Historical references===
* {{Citation | last1=Banach | first1=Stefan | author1-link=Stefan Banach | title=Sur les opérations dans les ensembles abstraits et leur application aux équations intégrales (On operations in abstract sets and their application to integral equations) | url=http://matwbn.icm.edu.pl/ksiazki/fm/fm3/fm3120.pdf | year=1922 | journal=[[Fundamenta Mathematicae]] | issn=0016-2736 | volume=3| pages=133–181 |language=fr| doi=10.4064/fm-3-1-133-181 }}
* {{Citation | last1=Bolzano | first1=Bernard | author1-link=Bernard Bolzano | title=Betrachtungen über einige Gegenstände der Elementargeometrie (Considerations of some aspects of elementary geometry) | url=http://dml.cz/handle/10338.dmlcz/400338 | year=1804|language=de}}
* {{Citation | last1=Bourbaki | first1=Nicolas | author1-link=Nicolas Bourbaki | title=Éléments d'histoire des mathématiques (Elements of history of mathematics) | publisher=Hermann | location=Paris | year=1969|language=fr}}
* {{Citation | last1=Dorier | first1=Jean-Luc | title=A general outline of the genesis of vector space theory | mr=1347828 | year=1995 | journal=[[Historia Mathematica]] | volume=22 | issue=3 | pages=227–261 | doi=10.1006/hmat.1995.1024}}
* {{Citation | last1=Fourier | first1=Jean Baptiste Joseph | author1-link=Joseph Fourier | title=Théorie analytique de la chaleur | url=https://books.google.com/books?id=TDQJAAAAIAAJ | publisher=Chez Firmin Didot, père et fils | year=1822|language=fr}}
* {{Citation | last1=Grassmann | first1=Hermann | author1-link=Hermann Grassmann | title=Die Lineale Ausdehnungslehre - Ein neuer Zweig der Mathematik | url=https://books.google.com/books?id=bKgAAAAAMAAJ&pg=PA1| year=1844|language=de}}, reprint: {{Citation | others=Kannenberg, L.C. | title=Extension Theory | publisher=[[American Mathematical Society]] | location=Providence, R.I. | isbn=978-0-8218-2031-5 | year=2000 | author=Hermann Grassmann. Translated by Lloyd C. Kannenberg.}}
* {{Citation | last1=Hamilton | first1=William Rowan | author1-link=William Rowan Hamilton | title=Lectures on Quaternions | url=http://historical.library.cornell.edu/cgi-bin/cul.math/docviewer?did=05230001&seq=9 | publisher=Royal Irish Academy | year=1853}}
* {{Citation |last1=Möbius |first1=August Ferdinand |author1-link=August Ferdinand Möbius |title=Der Barycentrische Calcul : ein neues Hülfsmittel zur analytischen Behandlung der Geometrie (Barycentric calculus: a new utility for an analytic treatment of geometry) |url=http://mathdoc.emath.fr/cgi-bin/oeitem?id=OE_MOBIUS__1_1_0 |year=1827 |language=de |url-status=dead |archiveurl=https://web.archive.org/web/20090412013616/http://mathdoc.emath.fr/cgi-bin/oeitem?id=OE_MOBIUS__1_1_0 |archivedate=2009-04-12 }}
* {{Citation | last1=Moore | first1=Gregory H. | title=The axiomatization of linear algebra: 1875–1940 | year=1995 | journal=[[Historia Mathematica]] | volume=22 | issue=3 | pages=262–303 | doi=10.1006/hmat.1995.1025}}
* {{Citation | last1=Peano | first1=Giuseppe | author1-link=Giuseppe Peano | title=Calcolo Geometrico secondo l'Ausdehnungslehre di H. Grassmann preceduto dalle Operazioni della Logica Deduttiva | year=1888 | location=Turin|language=it}}

==External links==
* Instructional videos from Khan Academy
**[https://web.archive.org/web/20120426050335/http://khanexercises.appspot.com/video?v=zntNi3-ybfQ Introduction to bases of subspaces]
**[https://web.archive.org/web/20120426050418/http://khanexercises.appspot.com/video?v=Zn2K8UIT8r4 Proof that any subspace basis has same number of elements]
* {{Cite web |title=Linear combinations, span, and basis vectors |work=Essence of linear algebra |date=August 6, 2016 |via=[[YouTube]] |url=https://www.youtube.com/watch?v=k7RM-ot2NWY&list=PLZHQObOWTQDPD3MizzM2xVFitgF8hE_ab&index=3 }}
* {{springer|title=Basis|id=p/b015350}}

{{linear algebra}}
{{tensors}}

{{DEFAULTSORT:Basis (Linear Algebra)}}
[[Category:Linear algebra]]
[[Category:Articles containing proofs]]
[[Category:Matroid theory]]
[[Category:Axiom of choice]]