Linear algebra

• 1. Introduction

  ›

  Linear algebra is the branch of mathematics concerning linear equations, linear maps, and their representations in vector spaces and through matrices. It sits at the center of almost every other area of the subject. Geometry leans on it to define lines, planes, and rotations. Functional analysis, a branch of mathematical analysis, can be read as linear algebra applied to function spaces.

  Most sciences and fields of engineering reach for it too, because it lets people model natural phenomena and compute with those models efficiently. Even systems that are not linear bend toward it. The differential of a multivariate function at a point is the linear map that best approximates the function nearby, so linear algebra handles first-order approximations of problems it cannot model directly.

  How did a subject this broad take shape? Why did counting rods in ancient China, coordinates in seventeenth-century France, and a single Latin word for womb all feed into the same field? And what are the objects, vectors, maps, matrices, and determinants, that let it reach from quantum mechanics to weather forecasting? The chapters that follow open up each piece.

• 2. From Counting Rods To Quaternions

  ›

  Counting rods solved simultaneous linear equations in ancient China long before the word matrix existed. The procedure, now called Gaussian elimination, appears in Chapter Eight: Rectangular Arrays of The Nine Chapters on the Mathematical Art. Its use is illustrated in eighteen problems, with two to five equations each.

  In 1637 René Descartes introduced coordinates into geometry, and systems of linear equations arose in Europe as a result. In this new Cartesian geometry, lines and planes were represented by linear equations, so finding their intersections meant solving such systems. The first systematic methods used determinants, first considered by Leibniz in 1693. In 1750 Gabriel Cramer used them to give explicit solutions, now called Cramer's rule. Gauss later described the method of elimination, initially listed as an advancement in geodesy.

  Hermann Grassmann published his Theory of Extension in 1844, introducing foundational topics of what is today called linear algebra. In 1848 James Joseph Sylvester introduced the term matrix, which is Latin for womb. The four-dimensional system of quaternions was discovered by W.R. Hamilton in 1843, and the term vector was introduced as representing a point in space. Around this period the field also drew on ideas from the complex plane, where line segments of the same length and direction were called equipollent.

  Arthur Cayley introduced matrix multiplication and the inverse matrix in 1856, making the general linear group possible. Crucially, he used a single letter to denote a matrix, treating it as one aggregate object. He wrote that there would be many things to say about the theory of matrices which should precede the theory of determinants. James Clerk Maxwell's 1873 publication of A Treatise on Electricity and Magnetism, prompted by the telegraph, instituted a field theory of forces and required differential geometry. The first modern definition of a vector space was introduced by Peano in 1888, setting up the abstract form the subject would take in the twentieth century.

• 3. Spaces, Maps, And Bases

  ›

  A vector space over a field, often the real numbers or the complex numbers, is a set equipped with two binary operations. Its elements are called vectors, and the elements of the field are called scalars. Vector addition takes two vectors and outputs a third. Scalar multiplication takes a scalar and a vector and outputs a new vector. The axioms include associativity and commutativity of addition, a zero vector, additive inverses, two distributivity laws, compatibility of scalar multiplication with field multiplication, and an identity scalar. The first four axioms mean the space is an abelian group under addition.

  Elements of a vector space may be tuples, sequences, functions, polynomials, or matrices. Linear algebra studies the properties common to all of them. Linear maps are the mappings between vector spaces that preserve this structure, compatible with both addition and scalar multiplication. When the two spaces are the same, a linear map is called a linear operator. A bijective linear map is an isomorphism, and two isomorphic spaces are essentially the same from the linear algebra point of view.

  Linear subspaces are subsets that are themselves vector spaces under the induced operations. The image and the kernel, or null space, of a linear map are subspaces of this kind. Taking linear combinations of a set S of vectors forms the span of S, the smallest linear subspace containing S. A set of vectors is linearly independent when none lies in the span of the others. A linearly independent set that spans a space is called a basis.

  Any two bases of a vector space have the same cardinality, called the dimension; this is the dimension theorem for vector spaces. Two spaces over the same field are isomorphic if and only if they share the same dimension. Bases matter because they are at once minimal generating sets and maximal independent sets, the pivot point from which matrices enter the picture.

• 4. The Matrix Connection

  ›

  Matrices allow explicit manipulation of finite-dimensional vector spaces and linear maps. Choosing a basis of a space of dimension m gives a bijection from the sequences of m field elements onto the space, an isomorphism of vector spaces. This lets a vector be represented by its coordinate vector, written as a column matrix. A linear map is then determined by its values on basis elements and represented by a matrix with as many rows and columns as the two dimensions require.

  Matrix multiplication is defined so that the product of two matrices is the matrix of the composition of the corresponding linear maps. The product of a matrix and a column matrix is the column matrix that results from applying the map to the vector. It follows that the theory of finite-dimensional vector spaces and the theory of matrices are two languages for the same concepts.

  Two matrices that encode the same transformation in different bases are called similar. They are similar if and only if one can be turned into the other by elementary row and column operations. Row operations correspond to a change of basis in the target space, and column operations to a change of basis in the source. Every matrix is similar to an identity matrix possibly bordered by zero rows and columns. Gaussian elimination is the basic algorithm for finding these operations and proving these results.

• 5. Solving Linear Systems

  ›

  A finite set of linear equations in a finite set of variables is called a system of linear equations, or a linear system. Historically, linear algebra and matrix theory were developed for solving such systems. To a given system one may associate its matrix and its right-member vector, then read a solution as an element of the preimage of that vector under the associated linear transformation.

  The associated homogeneous system puts the right-hand sides to zero, and its solutions are exactly the elements of the kernel of the transformation. Gaussian elimination performs elementary row operations on the augmented matrix to put it in reduced row echelon form. These operations do not change the set of solutions. A system whose matrix is square and invertible has a unique solution.

  This matrix interpretation pays off broadly. The same methods used to solve systems also handle many operations on matrices and linear transformations, including the computation of ranks, kernels, and matrix inverses. The square case opens onto a deeper structure: linear maps from a space to itself.

• 6. Endomorphisms And Eigenvectors

  ›

  A linear endomorphism maps a vector space to itself, and if the space has a basis of n elements, it is represented by a square matrix of size n. Such maps appear in geometric transformations, coordinate changes, and quadratic forms, among many other parts of mathematics. The determinant of a square matrix is defined through the group of permutations of n elements and the parity of each permutation. A matrix is invertible if and only if its determinant is nonzero over a field. Cramer's rule expresses solutions in terms of determinants, but apart from very small systems it is rarely used for computing, since Gaussian elimination is faster.

  An eigenvector of an endomorphism is a nonzero vector that the map sends to a scalar multiple of itself, and that scalar is the eigenvalue. Rewriting the defining equation with the identity matrix shows that the relevant matrix must be singular, so its determinant equals zero. The eigenvalues are therefore the roots of the characteristic polynomial, a monic polynomial of degree n when the space has dimension n, giving at most n eigenvalues.

  When a basis of eigenvectors exists, the matrix becomes diagonal, with eigenvalues on the main diagonal and zeros elsewhere, and the endomorphism is called diagonalizable. A symmetric matrix is always diagonalizable. Some matrices are not, the simplest being one whose square is the zero matrix. For those, the Frobenius normal form needs no field extension and makes the characteristic polynomial immediately readable, while the Jordan normal form extends the field to contain all eigenvalues and differs from the diagonal form only by entries of 1 just above the main diagonal.

• 7. Duality And Inner Products

  ›

  A linear form is a linear map from a vector space to its field of scalars. Equipped with pointwise addition and scalar multiplication, the linear forms make up the dual space, usually written with a star. From a basis of a finite-dimensional space one can build a dual basis. The canonical map from a space into the dual of its dual, the bidual, is an isomorphism when the space is finite-dimensional, allowing the space to be identified with its bidual. This complete symmetry motivates the bra-ket notation used in this context. The dual, or transpose, of a linear map acts between the dual spaces, and over dual bases its matrix is the transpose of the original, obtained by exchanging rows and columns.

  An inner product gives a vector space a geometric structure by defining length and angles. It is a kind of bilinear form satisfying conjugate symmetry, linearity in the first argument, and positive-definiteness. From it one defines the length of a vector and proves the Cauchy-Schwarz inequality, which lets a quantity be called the cosine of the angle between two vectors.

  Two vectors are orthogonal when their inner product is zero, and an orthonormal basis has basis vectors of length 1 that are mutually orthogonal. Any finite-dimensional space admits such a basis through the Gram-Schmidt procedure. The inner product also yields the Hermitian conjugate of a transform. Normal matrices, those equal to a certain commuting condition, turn out to be precisely the matrices with an orthonormal system of eigenvectors that span the space.

• 8. Where Linear Algebra Lives

  ›

  Cartesian coordinates, introduced by René Descartes in 1637, began the strong relationship between linear algebra and geometry. Points became sequences of three real numbers in ordinary space, lines and planes became linear equations, and computing their intersections became solving linear systems. Most geometric transformations, including translations, rotations, reflections, rigid motions, isometries, and projections, send lines into lines, so they can be defined and studied as linear maps. The same holds for homographies and Möbius transformations on a projective space. By the end of the nineteenth century, mathematicians saw that geometric spaces defined by axioms and those built from vector spaces were essentially equivalent, and today geometry is often presented at an elementary level as a subfield of linear algebra.

  Functional analysis studies function spaces such as Hilbert spaces, drawing on linear algebra for quantum mechanics through wave functions and for Fourier analysis through orthogonal bases. Scientific computation rests on it almost entirely, and its algorithms have been highly optimized, with BLAS and LAPACK among the best known implementations. Since the 1960s there have been processors with specialized instructions for these operations, and some contemporary graphics processing units are designed with a matrix structure for the same reason.

  Complex systems modeled by partial differential equations are solved by dividing space into small interacting cells, with very large matrices involved. Weather forecasting is a typical case, where the atmosphere is divided into cells of roughly 100 km in width and height. In fluid mechanics, fluid dynamics, and thermal energy systems, linear algebra linearizes the differential equations of fluid motion, underpins computational fluid dynamics and the Navier-Stokes equations, and supports power systems analysis through matrix operations and eigenvalue problems.

  The subject also reaches past elementary textbooks. Replacing the field of scalars with a ring R gives a module, where some structures have no basis at all. Multilinear algebra studies maps linear in several variables and describes them through tensor products. A vector space with a bilinear vector product is called an algebra, and infinite-dimensional spaces gain norms, metrics, and topologies, leading to Banach spaces and, with an inner product, Hilbert spaces. Among the Lp spaces studied in functional analysis, the space of square-integrable functions is the only Hilbert space, and it provides the framework underlying the Fourier transform.