Linear algebra

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

a_{1}x_{1}+\cdots +a_{n}x_{n}=b,

linear maps such as:

(x_{1},\ldots ,x_{n})\mapsto a_{1}x_{1}+\cdots +a_{n}x_{n},

and their representations in vector spaces and through matrices.^[1]^[2]^[3]

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 it allows modeling many natural phenomena, and computing efficiently with such models. For nonlinear systems, which cannot be modeled with linear algebra, it is often used for dealing with first-order approximations, using the fact that the differential of a multivariate function at a point is the linear map that best approximates the function near that point.

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.^[4]

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.^[5]

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.^[6] The term vector was introduced as $v = x i + y j + z k$ 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".^[5]

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

The telegraph required an explanatory system, and the 1873 publication of A Treatise on Electricity and Magnetism instituted a field theory of forces and required differential geometry for expression. Linear algebra is flat differential geometry and serves in tangent spaces to manifolds. Electromagnetic symmetries of spacetime are expressed by the Lorentz transformations, and much of the history of linear algebra is the history of Lorentz transformations.

The first modern and more precise definition of a vector space was introduced by Peano in 1888;^[5] by 1900, a theory of linear transformations of finite-dimensional vector spaces had emerged. Linear algebra took its modern form in the first half of the twentieth century, when many ideas and methods of previous centuries were generalized as abstract algebra. The development of computers led to increased research in efficient algorithms for Gaussian elimination and matrix decompositions, and linear algebra became an essential tool for modelling and simulations.^[5]

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) is a set $V$ equipped with two binary operations satisfying the following axioms. 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 $a v$ . 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$ .)^[8]

Axiom	Signification
Associativity of addition	$u + (v + w) = (u + v) + w$
Commutativity of addition	$u + v = v + u$
Identity element of addition	There exists an element $0$ in $V$ , called the zero vector (or simply zero), such that $v + 0 = v$ for all $v$ in $V$ .
Inverse elements of addition	For every $v$ in $V$ , there exists an element $- v$ in $V$ , called the additive inverse of $v$ , such that $v + (- v) = 0$
Distributivity of scalar multiplication with respect to vector addition	$a (u + v) = a u + a v$
Distributivity of scalar multiplication with respect to field addition	$(a + b) v = a v + b v$
Compatibility of scalar multiplication with field multiplication	$a (b v) = (ab) v$ ^[a]
Identity element of scalar multiplication	$1 v = v$ , where $1$ denotes the multiplicative identity of $F$ .

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

An element of a specific vector space may have various nature; for example, it could be a sequence, a function, a polynomial or a matrix. Linear algebra is concerned with those 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$ .

This implies that for any vectors $u, v$ in $V$ and scalars $a, b$ in $F$ , one has

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

When $V = W$ are the same vector space, a linear map $T : V \to 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 $a u$ 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 \to W$ , the image $T (V)$ of $V$ , and the inverse image $T -1 (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 $v 1, v 2, ..., v k$ are in $S$ , and $a 1, a 2, ..., a k$ 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 $a i$ .

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 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 \subseteq T$ , then there is a basis $B$ such that $S \subseteq B \subseteq 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.^[9]

If any basis of $V$ (and therefore every basis) has a finite number of elements, $V$ is a finite-dimensional vector space. If $U$ is a subspace of $V$ , then $dim U \leq dim V$ . In the case where $V$ is finite-dimensional, the equality of the dimensions implies $U = V$ .

If $U 1$ and $U 2$ are subspaces of $V$ , then

\dim(U_{1}+U_{2})=\dim U_{1}+\dim U_{2}-\dim(U_{1}\cap U_{2}),

where $U 1 + U 2$ denotes the span of $U 1 \cup U 2$ .^[10]

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 $(v 1, v 2, ..., v m)$ be a basis of $V$ (thus $m$ is the dimension of $V$ ). By definition of a basis, the map