maths.free › Linear Algebra › Structure › Linear algebra

Linear algebra

Linear algebra is the branch of mathematics concerning linear equations such aslinear maps such as the following:and their representations in vector spaces and through matrices.Linear algebra is central to almost all…

Linear algebra

Linear algebra is the branch of mathematics concerning linear equations such as

\(a_1x_1+\cdots +a_nx_n=b,\)

linear maps such as the following:

\((x_1, \ldots, x_n) \mapsto a_1x_1+\cdots +a_nx_n,\)

and their representations in vector spaces and through matrices.

Linear algebra is central to almost all areas of mathematics. For instance, linear algebra is fundamental in modern presentations of geometry, including for defining basic objects such as lines, planes and rotations. Also, functional analysis, a branch of mathematical analysis, may be viewed as the application of linear algebra to function spaces.

Linear algebra is also used in most sciences and fields of engineering, because linear structures are natural models for many physical phenomena; it's also useful in many areas of computing, and is thus applied to most sciences. For nonlinear systems, linear algebra is often used for dealing with first-order approximations: the derivative of a manifold at a point gives the slope of a line which models the manifold's local behavior, and can itself be analyzed with linear algebra.

History

The procedure (using counting rods) for solving simultaneous linear equations now called Gaussian elimination appears in the ancient Chinese mathematical text Chapter Eight: Rectangular Arrays of The Nine Chapters on the Mathematical Art. Its use is illustrated in eighteen problems, with two to five equations.

Systems of linear equations arose in Europe with the introduction in 1637 by René Descartes of coordinates in geometry. In fact, in this new geometry, now called Cartesian geometry, lines and planes are represented by linear equations, and computing their intersections amounts to solving systems of linear equations.

The first systematic methods for solving linear systems used determinants and were first considered by Leibniz in 1693. In 1750, Gabriel Cramer used them for giving explicit solutions of linear systems, now called Cramer's rule. Later, Gauss further described the method of elimination, which was initially listed as an advancement in geodesy.

"The leading mathematicians of the nineteenth and early twentieth centuries developed and used most of the basic results and techniques of linear algebra for perhaps a hundred years, without even defining an abstract vector space: nor is there anything to suggest they suffered thereby." In 1844 Hermann Grassmann published his "Theory of Extension" which included foundational new topics of what is today called linear algebra. In 1848, James Joseph Sylvester introduced the term matrix, which is Latin for womb.

Linear algebra grew with ideas noted in the complex plane. For instance, two numbers w and z in \(\mathbb{C}\) have a difference w, z, and the line segments wz and 0(w − z) are of the same length and direction. The segments are equipollent. The four-dimensional system \(\mathbb{H}\) of quaternions was discovered by W.R. Hamilton in 1843. The term vector was introduced as v = xi + yj + zk representing a point in space. The quaternion difference p, q also produces a segment equipollent to pq. Other hypercomplex number systems also used the idea of a linear space with a basis.

Arthur Cayley introduced matrix multiplication and the inverse matrix in 1856, making possible the general linear group. The mechanism of group representation became available for describing complex and hypercomplex numbers. Crucially, Cayley used a single letter to denote a matrix, thus treating a matrix as an aggregate object. He also realized the connection between matrices and determinants and wrote "There would be many things to say about this theory of matrices which should, it seems to me, precede the theory of determinants".

Benjamin Peirce published his Linear Associative Algebra (1872), and his son Charles Sanders Peirce extended the work later.

Condensed: the full section is in Wikipedia.

Vector spaces

Until the 19th century, linear algebra was introduced through systems of linear equations and matrices. In modern mathematics, the presentation through vector spaces is generally preferred, since it is more synthetic, more general (not limited to the finite-dimensional case), and conceptually simpler, although more abstract.

A vector space over a field F (often the field of the real numbers or of the complex numbers) is a set V equipped with two binary operations. Elements of V are called vectors, and elements of F are called scalars. The first operation, vector addition, takes any two vectors v and w and outputs a third vector v + w. The second operation, scalar multiplication, takes any scalar a and any vector v and outputs a new vector av. The axioms that addition and scalar multiplication must satisfy are the following. (In the list below, u, v and w are arbitrary elements of V, and a and b are arbitrary scalars in the field F.)

The first four axioms mean that V is an abelian group under addition.

The elements of a specific vector space may have various natures; for example, they could be tuples, sequences, functions, polynomials, or matrices. Linear algebra is concerned with the properties of such objects that are common to all vector spaces.

Linear maps

Linear maps are mappings between vector spaces that preserve the vector-space structure. Given two vector spaces V and W over a field F, a linear map (also called, in some contexts, linear transformation or linear mapping) is a map

\(T:V\to W\)

that is compatible with addition and scalar multiplication, that is

\(T(\mathbf u + \mathbf v)=T(\mathbf u)+T(\mathbf v), \quad T(a \mathbf v)=aT(\mathbf v)\)

for any vectors u,v in V and scalar a in F.

An equivalent condition is that

\(T(a \mathbf u + b \mathbf v) = aT(\mathbf u) + bT(\mathbf v)\)

for any vectors u, v in V and scalars a, b in F.

When V = W are the same vector space, a linear map T : V → V is also known as a linear operator on V.

A bijective linear map between two vector spaces (that is, every vector from the second space is associated with exactly one in the first) is an isomorphism. Because an isomorphism preserves linear structure, two isomorphic vector spaces are "essentially the same" from the linear algebra point of view, in the sense that they cannot be distinguished by using vector space properties. An essential question in linear algebra is testing whether a linear map is an isomorphism or not, and, if it is not an isomorphism, finding its range (or image) and the set of elements that are mapped to the zero vector, called the kernel of the map. All these questions can be solved by using Gaussian elimination or some variant of this algorithm.

Subspaces, span, and basis

The study of those subsets of vector spaces that are in themselves vector spaces under the induced operations is fundamental, similarly as for many mathematical structures. These subsets are called linear subspaces. More precisely, a linear subspace of a vector space V over a field F is a subset W of V such that u + v and au are in W, for every u, v in W, and every a in F. (These conditions suffice for implying that W is a vector space.)

For example, given a linear map T : V → W, the image T(V) of V, and the inverse image T(0) of 0 (called kernel or null space), are linear subspaces of W and V, respectively.

Another important way of forming a subspace is to consider linear combinations of a set S of vectors: the set of all sums

\(a_1 \mathbf v_1 + a_2 \mathbf v_2 + \cdots + a_k \mathbf v_k,\)

where v1, v2, ..., vk are in S, and a1, a2, ..., ak are in F form a linear subspace called the span of S. The span of S is also the intersection of all linear subspaces containing S. In other words, it is the smallest (for the inclusion relation) linear subspace containing S.

A set of vectors is linearly independent if none is in the span of the others. Equivalently, a set S of vectors is linearly independent if the only way to express the zero vector as a linear combination of elements of S is to take zero for every coefficient ai.

A set of vectors that spans a vector space is called a spanning set or generating set. If a spanning set S is linearly dependent (that is not linearly independent), then some element w of S is in the span of the other elements of S, and the span would remain the same if one were to remove w from S. One may continue to remove elements of S until getting a linearly independent spanning set. Such a linearly independent set that spans a vector space V is called a basis of V. The importance of bases lies in the fact that they are simultaneously minimal-generating sets and maximal independent sets. More precisely, if S is a linearly independent set, and T is a spanning set such that S ⊆ T, then there is a basis B such that S ⊆ B ⊆ T.

Any two bases of a vector space V have the same cardinality, which is called the dimension of V; this is the dimension theorem for vector spaces. Moreover, two vector spaces over the same field F are isomorphic if and only if they have the same dimension.

\(\dim(U_1 + U_2) = \dim U_1 + \dim U_2 - \dim(U_1 \cap U_2),\)

Condensed: the full section is in Wikipedia.

Matrices

Matrices allow explicit manipulation of finite-dimensional vector spaces and linear maps. Their theory is thus an essential part of linear algebra.

Let V be a finite-dimensional vector space over a field F, and (v1, v2, ..., vm) be a basis of V (thus m is the dimension of V). By definition of a basis, the map

\(\begin{aligned} (a_1, \ldots, a_m)&\mapsto a_1 \mathbf v_1+\cdots a_m \mathbf v_m\\ F^m &\to V \end{aligned}\)

is a bijection from F, the set of the sequences of m elements of F, onto V. This is an isomorphism of vector spaces, if F is equipped with its standard structure of vector space, where vector addition and scalar multiplication are done component by component.

This isomorphism allows representing a vector by its inverse image under this isomorphism, that is by the coordinate vector (a1, ..., am) or by the column matrix

\(\begin{bmatrix}a_1\\\vdots\\a_m\end{bmatrix}.\)

If W is another finite dimensional vector space (possibly the same), with a basis (w1, ..., wn), a linear map f from W to V is well defined by its values on the basis elements, that is (f(w1), ..., f(wn)). Thus, f is well represented by the list of the corresponding column matrices. That is, if

\(f(w_j)=a_{1,j}v_1 + \cdots+a_{m,j}v_m,\)

for j = 1, ..., n, then f is represented by the matrix

\(\begin{bmatrix} a_{1,1}&\cdots&a_{1,n}\\ \vdots&\ddots&\vdots\\ a_{m,1}&\cdots&a_{m,n} \end{bmatrix},\)

with m rows and n columns.

Condensed: the full section is in Wikipedia.

Linear systems

A finite set of linear equations in a finite set of variables, for example, x1, x2, ..., xn, or x, y, ..., z is called a system of linear equations or a linear system.

Systems of linear equations form a fundamental part of linear algebra. Historically, linear algebra and matrix theory have been developed for solving such systems. In the modern presentation of linear algebra through vector spaces and matrices, many problems may be interpreted in terms of linear systems.

For example, let

be a linear system.

To such a system, one may associate its matrix

\(M = \left[\begin{array}{rrr} 2 & 1 & -1\\ -3 & -1 & 2 \\ -2 & 1 & 2 \end{array}\right].\)

and its right member vector

\(\mathbf{v} = \begin{bmatrix} 8\\-11\\-3 \end{bmatrix}.\)

Let T be the linear transformation associated with the matrix M. A solution of the system (S) is a vector

\(\mathbf{X}=\begin{bmatrix} x\\y\\z \end{bmatrix}\)

\(T(\mathbf{X}) = \mathbf{v},\)

\(\left[\!\begin{array}{c|c}M&\mathbf{v}\end{array}\!\right] = \left[\begin{array}{rrr|r} 2 & 1 & -1&8\\ -3 & -1 & 2&-11 \\ -2 & 1 & 2&-3 \end{array}\right]\)

\(\left[\!\begin{array}{c|c}M&\mathbf{v}\end{array}\!\right] = \left[\begin{array}{rrr|r} 1 & 0 & 0&2\\ 0 & 1 & 0&3 \\ 0 & 0 & 1&-1 \end{array}\right],\)

\(\begin{aligned}x&=2\\y&=3\\z&=-1.\end{aligned}\)

Condensed: the full section is in Wikipedia.

Endomorphisms and square matrices

A linear endomorphism is a linear map that maps a vector space V to itself. If V has a basis of n elements, such an endomorphism is represented by a square matrix of size n.

Concerning general linear maps, linear endomorphisms, and square matrices have some specific properties that make their study an important part of linear algebra, which is used in many parts of mathematics, including geometric transformations, coordinate changes, quadratic forms, and many other parts of mathematics.

Determinant

The determinant of a square matrix A is defined to be

\(\sum_{\sigma \in S_n} (-1)^{\sigma} a_{1\sigma(1)} \cdots a_{n\sigma(n)},\)

where Sn is the group of all permutations of n elements, σ is a permutation, and (−1) the parity of the permutation. A matrix is invertible if and only if the determinant is invertible (i.e., nonzero if the scalars belong to a field).

Cramer's rule is a closed-form expression, in terms of determinants, of the solution of a system of n linear equations in n unknowns. Cramer's rule is useful for reasoning about the solution, but, except for n = 2 or 3, it is rarely used for computing a solution, since Gaussian elimination is a faster algorithm.

The determinant of an endomorphism is the determinant of the matrix representing the endomorphism in terms of some ordered basis. This definition makes sense since this determinant is independent of the choice of the basis.

Eigenvalues and eigenvectors

If f is a linear endomorphism of a vector space V over a field F, an eigenvector of f is a nonzero vector v of V such that f(v) = av for some scalar a in F. This scalar a is an eigenvalue of f.

If the dimension of V is finite, and a basis has been chosen, f and v may be represented, respectively, by a square matrix M and a column matrix z; the equation defining eigenvectors and eigenvalues becomes

\(Mz=az.\)

Using the identity matrix I, whose entries are all zero, except those of the main diagonal, which are equal to one, this may be rewritten

\((M-aI)z=0.\)

As z is supposed to be nonzero, this means that M, aI is a singular matrix, and thus that its determinant det (M − aI) equals zero. The eigenvalues are thus the roots of the polynomial

\(\det(xI-M).\)

If V is of dimension n, this is a monic polynomial of degree n, called the characteristic polynomial of the matrix (or of the endomorphism), and there are, at most, n eigenvalues.

If a basis exists that consists only of eigenvectors, the matrix of f on this basis has a very simple structure: it is a diagonal matrix such that the entries on the main diagonal are eigenvalues, and the other entries are zero. In this case, the endomorphism and the matrix are said to be diagonalizable. More generally, an endomorphism and a matrix are also said diagonalizable, if they become diagonalizable after extending the field of scalars. In this extended sense, if the characteristic polynomial is square-free, then the matrix is diagonalizable.

A symmetric matrix is always diagonalizable. There are non-diagonalizable matrices, the simplest being

\(\begin{bmatrix}0&1\\0&0\end{bmatrix}\)

Condensed: the full section is in Wikipedia.

Duality

A linear form is a linear map from a vector space V over a field F to the field of scalars F, viewed as a vector space over itself. Equipped by pointwise addition and multiplication by a scalar, the linear forms form a vector space, called the dual space of V, and usually denoted V* or V′.

If v1, ..., vn is a basis of V (this implies that V is finite-dimensional), then one can define, for i = 1, ..., n, a linear map vi* such that vi*(vi) = 1 and vi*(vj) = 0 if j ≠ i. These linear maps form a basis of V*, called the dual basis of v1, ..., vn. (If V is not finite-dimensional, the vi* may be defined similarly; they are linearly independent, but do not form a basis.)

For v in V, the map

\(f\to f(\mathbf v)\)

is a linear form on V*. This defines the canonical linear map from V into (V*)*, the dual of V*, called the double dual or bidual of V. This canonical map is an isomorphism if V is finite-dimensional, and this allows identifying V with its bidual. (In the infinite-dimensional case, the canonical map is injective, but not surjective.)

There is thus a complete symmetry between a finite-dimensional vector space and its dual. This motivates the frequent use, in this context, of the bra, ket notation

\(\langle f, \mathbf x\rangle\)

for denoting f(x).

Dual map

Let

\(f:V\to W\)

be a linear map. For every linear form h on W, the composite function h ∘ f is a linear form on V. This defines a linear map

\(f^*:W^*\to V^*\)

between the dual spaces, which is called the dual or the transpose of f.

If V and W are finite-dimensional, and M is the matrix of f in terms of some ordered bases, then the matrix of f* over the dual bases is the transpose M of M, obtained by exchanging rows and columns.

If elements of vector spaces and their duals are represented by column vectors, this duality may be expressed in bra, ket notation by

\(\langle h^\mathsf T , M \mathbf v\rangle = \langle h^\mathsf T M, \mathbf v\rangle.\)

To highlight this symmetry, the two members of this equality are sometimes written

\(\langle h^\mathsf T \mid M \mid \mathbf v\rangle.\)

Inner-product spaces

Besides these basic concepts, linear algebra also studies vector spaces with additional structure, such as an inner product. The inner product is an example of a bilinear form, and it gives the vector space a geometric structure by allowing for the definition of length and angles. Formally, an inner product is a map.

\(\langle \cdot, \cdot \rangle : V \times V \to F\)

that satisfies the following three axioms for all vectors u, v, w in V and all scalars a in F:

  • Conjugate symmetry:

    \(\langle \mathbf u, \mathbf v\rangle =\overline{\langle \mathbf v, \mathbf u\rangle}.\)

In \(\mathbb{R}\), it is symmetric.

  • Linearity in the first argument:

    \(\begin{aligned} \langle a \mathbf u, \mathbf v\rangle &= a \langle \mathbf u, \mathbf v\rangle. \\ \langle \mathbf u + \mathbf v, \mathbf w\rangle &= \langle \mathbf u, \mathbf w\rangle+ \langle \mathbf v, \mathbf w\rangle. \end{aligned}\)

  • Positive-definiteness:

    \(\langle \mathbf v, \mathbf v\rangle \geq 0\)

with equality only for v = 0.

We can define the length of a vector v in V by

\(\|\mathbf v\|^2=\langle \mathbf v, \mathbf v\rangle,\)

and we can prove the Cauchy-Schwarz inequality:

\(|\langle \mathbf u, \mathbf v\rangle| \leq \|\mathbf u\| \cdot \|\mathbf v\|.\)

In particular, the quantity

\(\frac{|\langle \mathbf u, \mathbf v\rangle|}{\|\mathbf u\| \cdot \|\mathbf v\|} \leq 1,\)

and so we can call this quantity the cosine of the angle between the two vectors.

Two vectors are orthogonal if ⟨u, v⟩ = 0. An orthonormal basis is a basis where all basis vectors have length 1 and are orthogonal to each other. Given any finite-dimensional vector space, an orthonormal basis could be found by the Gram-Schmidt procedure. Orthonormal bases are particularly easy to deal with, since if v = a1 v1 + ⋯ + an vn, then

\(a_i = \langle \mathbf v, \mathbf v_i \rangle.\)

\(\langle T \mathbf u, \mathbf v \rangle = \langle \mathbf u, T^* \mathbf v\rangle.\)

Condensed: the full section is in Wikipedia.

Relationship with geometry

There is a strong relationship between linear algebra and geometry, which started with the introduction by René Descartes, in 1637, of Cartesian coordinates. In this new (at that time) geometry, now called Cartesian geometry, points are represented by Cartesian coordinates, which are sequences of three real numbers (in the case of the usual three-dimensional space). The basic objects of geometry, which are lines and planes are represented by linear equations. Thus, computing intersections of lines and planes amounts to solving systems of linear equations. This was one of the main motivations for developing linear algebra.

Most geometric transformation, such as translations, rotations, reflections, rigid motions, isometries, and projections transform lines into lines. It follows that they can be defined, specified, and studied in terms of linear maps. This is also the case of homographies and Möbius transformations when considered as transformations of a projective space.

Until the end of the 19th century, geometric spaces were defined by axioms relating points, lines, and planes (synthetic geometry). Around this date, it appeared that one may also define geometric spaces by constructions involving vector spaces (see, for example, Projective space and Affine space). It has been shown that the two approaches are essentially equivalent. In classical geometry, the involved vector spaces are vector spaces over the reals, but the constructions may be extended to vector spaces over any field, allowing considering geometry over arbitrary fields, including finite fields.

Presently, most textbooks introduce geometric spaces from linear algebra, and geometry is often presented, at the elementary level, as a subfield of linear algebra.

Now you No calculator settles this one, but the pieces of it are computable. Try one below, or type your own.

Keep your own working

A free account adds notes on every lesson, a record of what you have finished, your solved problems in one place, and a tutor you can ask about this page. The maths itself is open to everyone, signed in or not.

Sign Up Login

Symbols used here

Tap any symbol for the full definition, a picture, and what every letter in it means.

Questions people ask

What does a determinant mean geometrically?

It is the factor by which the matrix scales area (2×2) or volume (3×3), with a negative sign if orientation flips. Zero means the matrix flattens space and cannot be undone.

What is an eigenvector?

A direction the matrix does not turn: it only stretches it by the eigenvalue. Along eigenvectors a complicated matrix acts like multiplication by a number.

Why is matrix multiplication not commutative?

Because a matrix is a transformation and AB means "do B, then A". Rotating then reflecting is not the same as reflecting then rotating.

Parts of this page are adapted from Wikipedia (CC BY-SA 4.0). Condensed and re-explained here; errors are ours.

More in Linear Algebra