Basis (linear algebra)
Basis (linear algebra)
In mathematics, a set B of elements (vectors) in a vector space V is called a basis, if every element of V may be written in a unique way as a (finite) linear combination of elements of B. The coefficients of this linear combination are referred to as components or coordinates on B of the vector. The elements of a basis are called basis vectors.
Equivalently B is a basis if its elements are linearly independent and every element of V is a linear combination of elements of B.[1] 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 of the vector space.
Definition
A basis B of a vector space V over a field F (such as the real numbers R or the complex numbers C) is a linearly independent subset of V that spans V. This means that a subset B of V is a basis if it satisfies the two following conditions:
the linear independence property:
- for every finite subset{b1, ..., bn}ofBand everya1, ..., aninF, ifa1b1
- ⋅⋅⋅ + a
the spanning property:
- for every (vector)vinV, it is possible to choosev1, ..., vninFandb1, ..., bninBsuch thatv = v1b1
- ⋅⋅⋅ + v
The scalars v**i are called the coordinates of the vector v with respect to the basis B, and by the first property they are uniquely determined.
A vector space that has a finite basis is called finite-dimensional. In this case, the subset {b1, ..., b**n} that is considered (twice) in the above definition may be chosen as B itself.
It is often convenient or even necessary to have an ordering on the basis vectors, e.g. for discussing 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 (m, n)-matrices, the (i, j)th element (in the ith row and jth column) can be referred to the (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, but e.g. a sequence, or an indexed family, or similar; see Ordered bases and coordinates below.
Examples
This picture illustrates the standard basis in R2. 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 R2 of the ordered pairs of real numbers is a vector space for the component-wise addition
More generally, if F is a field, the set of n-tuples of elements of F is a vector space for similarly defined addition and scalar multiplication. Let
If F is a field, the polynomial ring F[X] of the polynomials in one indeterminate has a basis B, called the monomial basis, consisting of all monomials:
Properties
Many properties of finite bases result from the Steinitz exchange lemma, which states that, given a finite spanning set S and a linearly independent subset L of n elements of S, one may replace n well chosen elements of S by the elements of L for getting a spanning set containing L, having its other elements in S, and having the same number of elements as 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 V is a vector space over a field F, then:
If L is a linearly independent subset of a spanning set S ⊆ V, then there is a basis B such that
V has a basis (this is the preceding property with L being the empty set, and S = V).
All bases of V have the same cardinality, which is called the dimension of V. This is the dimension theorem.
A generating set S is a basis of V if and only if it is minimal, that is, no proper subset of S is also a generating set of V.
A linearly independent set 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 V is a vector space of dimension n, then:
A subset of V with n elements is a basis if and only if it is linearly independent.
A subset of V with n elements is a basis if and only if it is spanning set of V.
Coordinates
Let V be a vector space of finite dimension n over a field F, and
be a basis of V. By definition of a basis, for every v in V may be written, in a unique way,
Change of basis
Typically, the new basis vectors are given by their coordinates over the old basis, that is,
for i = 1, ..., n.
- and
be the column vectors of the coordinates of v in the old and the new basis respectively, then the formula for changing coordinates is
The formula can be proven by considering the decomposition of the vector x on the two bases: one has
and
for i = 1, ..., n.
Related notions
Free module
If one replaces the field occurring in the definition of a vector space by a ring, one gets the definition of a module. For modules, linear independence and spanning sets are defined exactly as for vector spaces, although "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 resolutions.
Analysis
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 spaces – a large class of vector spaces including e.g. Hilbert spaces, Banach spaces, or Fréchet spaces.
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
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
for suitable (real or complex) coefficients a**k, b**k. But many[2] 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
Random basis
Empirical distribution of lengths N of pairwise almost orthogonal chains of vectors that are independently randomly sampled from the n-dimensional cube [−1, 1]n 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.[6]
For a probability distribution in Rn 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 x1, ..., xn in Rn should satisfy the equation det[x1, ..., xn] = 0 (zero determinant of the matrix with columns xi), and the set of zeros of a non-trivial polynomial has zero measure. This observation has led to techniques for approximating random bases.[5][6]
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). Let θ be a small positive number. Then for
(Eq. 1) |
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 [−1, 1]n 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 π/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 π/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 partially ordered by inclusion, which is denoted, as usual, by ⊆.
Let Y be a subset of X that is totally ordered by ⊆, and let LY 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 LY is a subset of an element of Y, which is a linearly independent subset of V, and hence every finite subset of LY is linearly independent. Thus LY is linearly independent, so LY is an element of X. Therefore, LY 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 Lmax of X satisfying the condition that whenever Lmax ⊆ L for some element L of X, then L = Lmax.
It remains to prove that Lmax is a basis of V. Since Lmax belongs to X, we already know that Lmax is a linearly independent subset of V.
If Lmax would not span V, there would exist some vector w of V that cannot be expressed as a linear combination of elements of Lmax (with coefficients in the field F). In particular, w cannot be an element of Lmax. Let Lw = Lmax ∪ {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 Lmax, and Lmax is independent). As Lmax ⊆ Lw, and Lmax ≠ Lw (because Lw contains the vector w that is not contained in Lmax), this contradicts the maximality of Lmax. Thus this shows that Lmax spans V.
Hence Lmax 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.[8] Thus the two assertions are equivalent.
See also
Change of basis
Frame of a vector space
Spherical basis