In mathematics, a matrix is a rectangular array of numbers, symbols, or expressions arranged in rows and columns. Matrices are a central object of linear algebra. They encode linear maps between vector spaces, compactly represent systems of linear equations, and organize tabular data. The same notation supports operations such as addition, multiplication, and inversion, and these operations follow rules that differ in important ways from ordinary arithmetic on real numbers. For example, matrix multiplication is generally not commutative.
The subject combines algebra, geometry, and analysis. Key quantities attached to a square matrix, such as its determinant, rank, and eigenvalues and eigenvectors, reveal structural properties of the linear map it represents, and they remain invariant under changes of basis. Matrices are also studied as elements of rings and Lie groups, which connects them to abstract-algebra and group-theory.
Matrices are indispensable across the sciences and engineering. They describe rotations and quantum states, form the covariance matrices of statistics, underpin principal component analysis, and are the basic data structures of neural networks. The article below covers the definition and basic operations, special classes of matrices, the core theory of determinants, inverses, rank, and eigenvalues, the main matrix decompositions and numerical methods, the historical development of the subject, and its applications and generalizations.
Definition and notation
Matrices and their entries
An matrix is a rectangular array of entries arranged in horizontal rows and vertical columns. Each entry is located by a pair of indices, the first giving the row and the second the column. The entry in row and column is written , and the whole array is written , or when the ranges need to be stated. For example,
is a matrix with and . Row consists of the entries , and column consists of . Mathematical texts usually number rows and columns from 1, whereas many programming environments start from 0.
The entries are drawn from a fixed set, most often a field. The set of all matrices with entries in a field is written or . The cases and dominate elementary and applied work, so one speaks of the sets and . When , the matrix is called square, and the set of square matrices is abbreviated . The integers and are the dimensions or the size of the matrix, and the size is part of the matrix's identity: a matrix is not just a list of numbers but a list arranged in a specific shape.
Row vectors, column vectors, and scalars
Matrices with a single row or a single column are the most important special cases. A matrix is a row vector, and an matrix is a column vector. By convention, the elements of in the sense of a vector space are identified with column vectors, which is why vectors are so often written vertically. Row vectors appear when a linear functional is written as a matrix acting from the left, and when one computes a row-by-column product that produces a scalar.
A matrix has exactly one entry, and it is in effect a scalar. Strictly speaking, the matrix and the number are different kinds of object, but the two are routinely identified, particularly in products such as a row vector times a column vector, whose result is a matrix that is read as a number. In this sense, scalars are the degenerate case . The same conventions connect the broader subject of linear algebra to the language of matrices, where vectors and scalars are handled through a single notation.
Equality and the function viewpoint
Two matrices and are equal exactly when they have the same size and agree in every position. That is, if is and is , then holds if and only if , , and for all and . Size is therefore essential. The row and the column with entries 1 and 2 contain the same numbers but are different matrices, and a matrix can never equal a matrix, even if the two contain the same multiset of entries.
Because every entry is determined by its index pair, an matrix can be viewed as a function from into the entry set , sending the pair to . Under this view, the rectangular layout is only one way of displaying data indexed by two finite sets. The function viewpoint explains the notation for entries and clarifies what it means for two matrices to be equal, since equal functions have equal values at every point of their common domain. It also makes the generalizations straightforward: an infinite matrix is a function on , and a tensor is a function on a product of more than two index sets. These extensions are treated in the later Generalizations section.
Matrix operations
Addition and scalar multiplication
Two matrices can be added only when they have the same size. If and are both , their sum is the matrix whose entry is . Addition is performed entry by entry, so it is commutative and associative, and the zero matrix (all entries zero) is its neutral element. For a scalar from the underlying field, the product has entries , and this operation is defined for matrices of any size. Together, these two operations make the set of all matrices over a field a vector space of dimension . A basis is given by the matrix units, which have a 1 in one position and zeros elsewhere. This is why matrices are often treated as vectors in their own right, and why the operations of linear algebra apply to them directly.
Matrix multiplication
Multiplication is defined by the row-by-column rule. If is and is , the product is , with entries
Each entry is the dot product of row of with column of . The number of columns of must equal the number of rows of , because each term in the sum pairs an entry of a row of with an entry of a column of . When this condition holds, the product exists even if does not, and when both are defined the sizes of and may differ.
Matrix multiplication is associative, , and it distributes over addition from both sides: and . These identities make the square matrices of a fixed size into a ring, which is developed in the algebraic-structure section. The operation is not commutative, however. For instance, with
one computes but . Thus . Commuting pairs exist, such as a matrix and any polynomial in itself, but they are the exception rather than the rule. The identity matrix satisfies whenever the sizes allow it.
Transpose and conjugate transpose
The transpose of an matrix is the matrix with ; rows become columns. The basic identities are
The reversal of order in the last identity is important: transposition reverses the order of factors in a product. For complex matrices, the conjugate transpose combines transposition with entrywise complex conjugation. It satisfies , , , and . For real matrices, the conjugate transpose and the transpose coincide.
Block matrices
A matrix can be partitioned into rectangular submatrices called blocks, for example
Block addition works blockwise whenever the blocks have matching sizes. Block multiplication works as if the blocks were scalars, provided the partitions are conformable: the column partition of the left factor must match the row partition of the right factor. If is partitioned as above and has conformable blocks, then
The ordering of factors within each block product must be preserved, because the blocks themselves need not commute. Block structure is useful for computation, since a large product can be organized into smaller products that fit into memory or can be computed in parallel, and it is also the natural language for block-diagonal matrices, which represent direct sums of linear maps.
Special types of matrices
A matrix is square when it has as many rows as columns, so . Square matrices are the setting in which a single matrix can be multiplied by itself and can act on one vector space, which is why determinants, eigenvalues, and diagonalization are defined only for them. The zero matrix is the additive identity: for every matrix of the same size, and for square . The identity matrix has entries , equal to 1 on the diagonal and 0 elsewhere, and it is the multiplicative identity, so . Multiplying by a scalar corresponds to , which scales every vector by the same factor.
A diagonal matrix has nonzero entries only on its main diagonal. Multiplying on the left by scales each row by , and multiplying on the right scales each column. Products and sums of diagonal matrices are again diagonal, and is invertible exactly when every , in which case its inverse is . Diagonal matrices are therefore the simplest model of a coordinate-wise scaling operator.
Triangular matrices generalize this idea. An upper triangular matrix has whenever , and a lower triangular matrix has whenever . Both classes are closed under addition and multiplication, the determinant of a triangular matrix is the product of its diagonal entries, and its eigenvalues are exactly those diagonal entries. Triangular linear systems can be solved directly by forward or back substitution, which is the reason that LU decomposition and Gaussian elimination reduce general systems to triangular ones.
Symmetric, skew-symmetric, and Hermitian matrices are defined by the behavior of the matrix under transposition. A real matrix is symmetric when , so . A skew-symmetric matrix satisfies , which forces zeros on the diagonal. Every odd-order skew-symmetric matrix is singular, and its eigenvalues are zero or purely imaginary. Over the complex numbers, the relevant class is Hermitian matrices, defined by , where is the conjugate transpose. Their diagonal entries must be real, and every real symmetric matrix is a special case. Hermitian matrices have real eigenvalues and can be diagonalized by a unitary matrix, as stated by the spectral theorem. The complex counterpart of a real skew-symmetric matrix is the skew-Hermitian matrix, which satisfies . Multiplying such a matrix by produces a Hermitian matrix, so the two classes differ by a factor of the imaginary unit.
Orthogonal and unitary matrices are the matrices that preserve geometry. A real square matrix is orthogonal when , and a complex square matrix is unitary when . Equivalently, their columns form an orthonormal basis. Such matrices preserve inner products, , and therefore preserve lengths, , and angles. They are the linear isometries of Euclidean and Hilbert space. In the real case the determinant is : matrices with determinant are rotations, and those with determinant include reflections. In two dimensions, the rotation by an angle is . The orthogonal matrices of a fixed size form the group , and the unitary matrices form , both of which are important examples of Lie groups.
A sparse matrix is one in which most entries are zero. Such matrices arise naturally from graphs, from discretized partial differential equations, and from large data sets in which each variable interacts with only a few others. Storing the full array requires numbers regardless of content, whereas sparse formats store only the nonzero entries together with index information. The coordinate (COO) format stores a list of (row, column, value) triplets, so its storage grows with the number of nonzeros. The compressed sparse row (CSR) format replaces the row indices with a pointer array of length , so that the entries of row occupy a contiguous block of the value array. The compressed sparse column (CSC) format plays the same role for columns, and specialized formats such as DIA exploit banded structure. Because the cost of a matrix–vector product depends on the number of nonzeros rather than on , sparse storage reduces both memory use and computation time, and it is essential for large-scale numerical methods such as the iterative solvers used for huge systems. The layout of the format also affects memory access patterns and performance on parallel hardware.
Matrices as linear maps
Matrices are the coordinate form of linear maps. Let be an -dimensional vector space over a field with ordered basis , and let be an -dimensional space with basis . A linear map is determined by the images , and each image has a unique expansion . The scalars form an matrix , whose -th column is the coordinate vector of . With this convention, the coordinates of are obtained from the coordinates of by , that is, . Taking the standard bases of and , the map is itself a linear map, and every linear map arises this way from exactly one matrix. The space of such maps therefore has dimension , matching the number of entries.
The row-by-column rule for matrix multiplication was chosen so that it corresponds to composition. If is an matrix representing , and is a matrix representing , then is a matrix representing . This follows because for every vector . The order of the factors reflects the order in which the maps are applied, which is one conceptual reason matrix multiplication is generally not commutative: and need not coincide, and they need not even be defined on the same spaces.
The same linear map has different matrices in different bases, so a matrix is always a representation relative to chosen bases. Suppose has matrix in a basis , and let be another basis. Let be the change-of-basis matrix whose columns are the coordinates of the new basis vectors in the old basis, so that . If is the matrix of in , then comparing with gives
For a map between different spaces, changing the basis in both gives , where is the change-of-basis matrix in . Matrices related in this way by invertible factors on both sides are called equivalent, and over a field they are classified exactly by their rank.
When and the same basis is used on both sides, the relation defines similarity of square matrices. Two similar matrices represent the same linear operator in different bases. Several properties are invariant under similarity: the determinant, the trace, the characteristic polynomial and hence the eigenvalues with their algebraic multiplicities, the rank and nullity, invertibility, and diagonalizability. Properties that depend on the coordinate system are not invariant. Entries, symmetry, and orthogonality of the matrix change under similarity, which is why a symmetric matrix can become non-symmetric after a change of basis. Eigenvectors, by contrast, transform in a predictable way: if , then the coordinate vector of in the new basis is .
The kernel and image of a linear map correspond directly to parts of its matrix. The kernel of corresponds to the null space , since coordinates of kernel vectors are exactly the solutions of this homogeneous system. The image of is spanned by the vectors , so in coordinates it is the column space of , the span of the columns of . The nullity of is the dimension of its null space, and the rank is the dimension of its column space. These quantities satisfy the rank–nullity theorem: . A nonzero kernel vector is a nontrivial linear relation among the columns of , so is injective exactly when the columns are linearly independent, and surjective exactly when .
As an example, consider the differentiation map on polynomials of degree at most 3, with basis , into polynomials of degree at most 2, with basis . Since , , , and , the matrix is
Its rank is 3, so the image is all of the degree-at-most-2 polynomials, and its nullity is 1, spanned by the constant column. The kernel of is the set of constant polynomials, and the rank–nullity relation holds.
Determinants
The determinant is a scalar attached to each square matrix. For a 2×2 matrix it is . For larger matrices it is defined by a combinatorial sum or by a recursive expansion, and its main uses are testing invertibility, computing volumes, and describing how linear maps scale space.
Definition: Leibniz formula and cofactor expansion
For an matrix , the Leibniz formula is
where is the symmetric group of permutations of and is for even permutations and for odd ones. Each term of the sum picks exactly one entry from each row and each column, so the formula has terms. For there are six terms, which is the origin of the familiar diagonal rule.
The formula can also be organized recursively. The minor is the determinant of the submatrix obtained by deleting row and column , and the cofactor is . Expansion along any row gives
and the same value results from expanding along any column. An induction on shows that this recursive form agrees with the Leibniz sum; this is the cofactor expansion of the determinant. Because the recursion does roughly work, it is suited to hand calculation of small matrices, not to large numerical problems.
Main properties
Several properties follow from the permutation definition and are used constantly:
- Row operations. Swapping two rows multiplies the determinant by , and two equal rows force the determinant to be zero. Multiplying one row by a scalar multiplies the determinant by . Adding a multiple of one row to another leaves the determinant unchanged. These rules make Gaussian elimination a practical way to compute determinants: reduce the matrix to triangular form, track the swaps and scalings, and multiply the diagonal entries.
- Multilinearity. The determinant is linear in each row (or column) separately when the others are held fixed.
- Transpose. , so the same properties hold for columns.
- Multiplicativity. for square matrices of the same size. Consequently , and similar matrices have equal determinants.
- Triangular matrices. The determinant of a triangular matrix is the product of its diagonal entries.
- Singularity criterion. A square matrix is invertible (see inverse matrix) exactly when its determinant is nonzero. Equivalently, when the rows or columns are linearly dependent, which means the matrix is singular and has a nontrivial null space.
Geometric meaning
For a real matrix, the columns can be treated as edge vectors of a parallelepiped in . Its volume is . In the plane, the parallelogram spanned by and has area . The sign records orientation: a positive determinant means the map preserves orientation, and a negative one means it reverses it. A linear map therefore multiplies all volumes by the same factor , which explains why multiplicativity holds: composing two maps multiplies their scaling factors.
This scaling property is the basis of the change-of-variables formula for integrals. If is a continuously differentiable map with invertible Jacobian matrix , then
In polar coordinates the Jacobian determinant is , which gives the familiar factor .
Historical development
The idea appeared in several places before it had a settled theory. Seki Takakazu in Japan worked with determinant-like arrays in the 1680s, using them for elimination and for finding common roots of polynomials. He handled sizes up to , though without a term for the concept. In Europe, Gottfried Wilhelm Leibniz wrote in 1693 to the Marquis de l'Hôpital, describing the condition for consistency of a linear system in terms of coefficients indexed by two numbers. Leibniz's letter was not published until much later, and his work was largely unnoticed in his lifetime.
Gabriel Cramer's 1750 treatment of algebraic curves gave an explicit rule for solving linear systems with determinants, the rule that now bears his name. Because it was published and widely read, it introduced determinants to a broad audience. Étienne Bézout (1764) established a recursive law for computing them, and Alexandre-Théophile Vandermonde (1771) was the first to study determinants as independent functions. Pierre-Simon Laplace (1772) developed expansion by minors, which generalizes the cofactor expansion. In 1812, Jacques Binet and Augustin-Louis Cauchy presented work on the multiplication theorem; Cauchy's memoir is usually regarded as the point at which determinants were treated as a general theory with the modern meaning of the term. The name "determinant" is credited to Carl Friedrich Gauss, who used it for the discriminant of a quadratic form.
In the nineteenth and early twentieth centuries, determinants were a central topic. Thomas Muir's multi-volume history, completed in the 1920s, summarizes results up to about 1920. Their role in mainstream mathematics declined afterward, as matrix theory, linear transformations over abstract fields, and numerical linear algebra provided more direct methods for many of the problems determinants had addressed.
Inverses and invertibility
A square matrix of order is invertible (or non-singular) if there is a matrix with , where is the identity matrix. When it exists, the inverse is unique. If and both satisfy the defining equations, then . For square matrices, a one-sided inverse is automatically two-sided, so alone implies . Inverses reverse the order of products, , and commute with transposition, .
Equivalent conditions for invertibility
For a square matrix over a field, the following statements are equivalent:
- is invertible.
- .
- , so the columns (and rows) are linearly independent and span the whole space.
- The null space of is trivial, that is, . Equivalently, the map is injective.
- For every right-hand side , the equation has exactly one solution.
- Zero is not an eigenvalue of .
- is row equivalent to .
These conditions describe one fact from different angles: the linear map represented by is a bijection of . The rank-nullity theorem links the two dimensions, since rank plus nullity equals , so a trivial kernel and full rank are the same condition. A square matrix that fails these conditions is called singular.
Computing inverses
The adjugate formula gives the inverse in closed form. The adjugate is the transpose of the matrix of cofactors, and it satisfies . Hence, when ,
For a matrix this reduces to . The formula is convenient for small or symbolic matrices, but cofactor expansion grows factorially with , so it is impractical for large matrices.
Gauss-Jordan elimination is the standard numerical method. One forms the augmented matrix and applies elementary row operations until the left block becomes . The right block then holds . If no nonzero pivot can be found in some column, the matrix is singular. The work is on the order of arithmetic operations, the same order as an LU factorization. In practice, software rarely forms explicitly. It factors once and solves for each right-hand side, which is cheaper and usually more accurate. For the elimination procedure itself, see Gaussian elimination.
Cramer's rule
If , the unique solution of has components
where is obtained from by replacing its -th column with . The rule is named after Gabriel Cramer, who published it in 1750. It gives an explicit formula for each unknown, which is useful in theory. It shows, for example, how a solution depends continuously on parameters when the determinant stays away from zero.
As a computational method, it is rarely used. It requires determinants. Computed by cofactor expansion, the cost is enormous. Even with elimination-based determinants, each costing about operations, the total is roughly , compared with about for a single elimination. Its results also depend on accurate determinant values, and in floating-point arithmetic a nearly singular system can produce inaccurate components. Solvers therefore use elimination-based factorizations instead.
One-sided inverses and the pseudoinverse
Non-square matrices cannot have two-sided inverses, but they can have one-sided ones. An matrix with and full column rank has a left inverse , an matrix with . One choice is , which exists because is then invertible. Similarly, a matrix with full row rank and has a right inverse with , for instance . These one-sided inverses are generally not unique, and a left inverse does not satisfy in general.
The Moore-Penrose pseudoinverse extends the idea to every matrix over the real or complex numbers. It is the unique matrix satisfying four Penrose conditions: , , and the products and are Hermitian. Using the singular value decomposition , one has , where inverts each nonzero singular value and leaves zeros in place. If is invertible, . If has full rank, reduces to one of the one-sided inverses above. For any , the vector minimizes , and among all minimizers it has the smallest norm. This is why the pseudoinverse underlies the solution of least-squares problems. The concept goes back to E. H. Moore in 1920 and was rediscovered and characterized by Roger Penrose in 1955. In floating-point computation, deciding which singular values count as zero requires a tolerance, and the result is sensitive to the condition number of .
Rank and linear systems
Rank and the equality of row and column rank
The rank of an matrix over a field is the dimension of its column space, the subspace of spanned by its columns. The row space, spanned by the rows in , has its own dimension, called the row rank. The two dimensions are always equal, so the rank is unambiguous and satisfies .
Elimination shows why the two numbers agree. Elementary row operations leave the row space unchanged, and they preserve every linear relation among the columns, because each operation is multiplication on the left by an invertible matrix. In a row echelon form, the nonzero rows are linearly independent and their number equals the number of pivots. The pivot columns are independent, and every other column is a combination of them. The row rank and the column rank of the echelon form therefore both equal the number of pivots, and since the original matrix has the same count, the two ranks coincide. An equivalent characterization is the largest size of a square submatrix with nonzero determinant.
Gaussian elimination and row echelon form
Gaussian elimination reduces a matrix to row echelon form using three operations: swapping two rows, multiplying a row by a nonzero scalar, and adding a multiple of one row to another. In the result, zero rows lie at the bottom, and the leading entry (pivot) of each nonzero row lies strictly to the right of the pivot in the row above. Further reduction to reduced row echelon form, where each pivot equals 1 and the entries above and below it are zero, makes that form unique. The rank is then the number of pivots.
The same procedure solves a system of linear equations. Applying the operations to the augmented matrix produces an equivalent system, which is solved by back-substitution. Variables in non-pivot columns are free parameters. Elimination on an system takes on the order of arithmetic operations. In floating-point computation, rounding can make a true zero pivot appear tiny but nonzero, so numerical rank is usually determined more reliably by the singular value decomposition than by elimination alone.
The rank–nullity theorem
For a linear map between finite-dimensional spaces, the dimension of the kernel plus the dimension of the image equals the dimension of . Applied to an matrix regarded as a map , the theorem reads
where is the set of solutions of . The theorem constrains solution sets in the following way.
For a homogeneous system , the solution set is the null space, a subspace of dimension . Nontrivial solutions exist exactly when , which is the same as saying the columns are linearly dependent.
For an inhomogeneous system , the system is consistent exactly when lies in the column space, that is, when . When a particular solution exists, the full solution set is , a translate of the null space. It is a single point when and otherwise a translate of a subspace of dimension .
As an illustration, take and . Subtracting twice the first row from the second gives a zero row, so the rank is 1. With , the null space has dimension 2, and the solutions form the plane with and free. By contrast, and reduce to . The coefficient rank is 1 while the augmented rank is 2, so the system has no solution.
Classification of solutions by rank
Let be , let , and consider .
- No solution: , so is outside the column space.
- Exactly one solution: .
- Infinitely many solutions: . Over an infinite field the solution set is infinite; over a finite field with elements it contains solutions.
Two special cases follow directly. If (full row rank), the column space is all of , so every yields a consistent system. If is square with , it is invertible, and every right-hand side gives exactly one solution.
Eigenvalues and diagonalization
Eigenvalues, eigenvectors and eigenspaces
For a square matrix of size , a nonzero vector is an eigenvector with eigenvalue when . Rewriting this as shows that is an eigenvalue exactly when the matrix has a nontrivial kernel, which happens if and only if . The function is the characteristic polynomial. It is monic of degree , so over the complex numbers it has roots counted with multiplicity, and these roots are the eigenvalues. Its coefficients encode invariants of : the constant term is , and the coefficient of is , so the sum of the eigenvalues equals the trace and their product equals the determinant.
For each eigenvalue , the set of all eigenvectors together with the zero vector forms the null space of . This subspace is the eigenspace . Its dimension is the geometric multiplicity of . The algebraic multiplicity is the number of times appears as a root of the characteristic polynomial. For every eigenvalue, the geometric multiplicity is at least 1 and does not exceed the algebraic multiplicity. The two numbers can differ. A standard example is the matrix with a single repeated eigenvalue 1 and a Jordan block, where the eigenspace is one-dimensional while the algebraic multiplicity is 2.
Diagonalizability
A matrix is diagonalizable when it is similar to a diagonal matrix, that is, when there exist an invertible matrix and a diagonal matrix with . The columns of are then eigenvectors and the diagonal entries of are the corresponding eigenvalues. Equivalently, is diagonalizable if and only if (or , when the eigenvalues are real) has a basis made of eigenvectors of . The criterion in terms of multiplicities is that for every eigenvalue the geometric multiplicity equals the algebraic multiplicity. Two sufficient conditions follow from this. If all eigenvalues are distinct, eigenvectors belonging to different eigenvalues are linearly independent, so is diagonalizable. Also, if the characteristic polynomial splits into linear factors and every root has a full set of eigenvectors, the matrix is diagonalizable.
Failure of diagonalizability can come from two sources. Over the reals, a characteristic polynomial may have no real roots: a rotation through 90 degrees has none, so it has no real diagonalization, although over it diagonalizes with eigenvalues . The other source is a deficiency in eigenvectors, as in the Jordan-block example above. Such matrices are handled by the Jordan canonical form, which replaces the diagonal matrix with blocks that are diagonal except for superdiagonal ones.
The spectral theorem
The spectral theorem gives a strong guarantee for two important classes. For a real symmetric matrix, all eigenvalues are real, and there exists an orthogonal matrix such that is diagonal. For a complex Hermitian matrix , all eigenvalues are real, and there exists a unitary matrix such that . In both cases the eigenvectors can be chosen to form an orthonormal basis, and eigenvectors belonging to distinct eigenvalues are automatically orthogonal. The real case is sometimes called the principal axis theorem. Each statement can be proved by first triangularizing with a unitary matrix, as in the Schur decomposition. Hermitian symmetry then forces the triangular factor to be diagonal. Because orthogonal and unitary matrices preserve lengths and inner products, the theorem says that every symmetric or Hermitian linear operator acts on suitable orthogonal coordinates as a pure stretch along mutually perpendicular axes. The spectral theorem holds for the larger class of normal matrices, meaning those commuting with their conjugate transpose, which are exactly the matrices that are unitarily diagonalizable.
Applications: matrix powers and differential equations
Diagonalization makes repeated multiplication easy. If , then for every integer , and is obtained by raising each diagonal entry to the th power. The Fibonacci recurrence is a standard illustration. The matrix has eigenvalues , and its powers produce closed-form expressions for the Fibonacci numbers.
The same idea solves constant-coefficient linear systems of differential equations . The solution with initial value is , where the matrix exponential is defined by a power series. When is diagonalizable, , and is the diagonal matrix with entries . Each eigenvalue therefore contributes a basic exponential mode, and the eigenvectors determine how these modes are combined to match the initial condition. For non-diagonalizable matrices the same formula holds, but the computation uses the Jordan form or a finite expansion based on the Cayley–Hamilton theorem, which shows that is a polynomial in of degree less than .
Matrix decompositions
A matrix decomposition, or factorization, writes a matrix as a product of matrices with special structure. Problems such as solving linear systems, fitting least-squares models, or computing eigenvalues can then be reduced to simpler steps. Matrix factorization gives the general framing, and the methods below are the ones most used in numerical linear algebra.
LU decomposition
Gaussian elimination can be recorded as a factorization , where is unit lower triangular and is upper triangular. Once this is available, a system is solved in two triangular stages: forward substitution for , then back substitution for . Computing the factors costs about floating-point operations, but the cost is paid once and reused for every new right-hand side, which is why this route is preferred over repeating the elimination.
Plain elimination breaks down when a pivot is zero and can be unstable when a pivot is very small. Partial pivoting swaps rows so that the largest available entry in the current column becomes the pivot, giving with a permutation matrix . Complete pivoting also swaps columns and bounds element growth more strictly, but it is more expensive, so partial pivoting is the usual default. Pivoting therefore concerns numerical stability as well as existence: an invertible matrix such as has no LU factorization without row exchanges.
QR decomposition
A QR decomposition writes , where has orthonormal columns and is upper triangular. When is square, is an orthogonal matrix. Classical Gram–Schmidt orthogonalization computes the factors directly but loses orthogonality in floating-point arithmetic. Modified Gram–Schmidt, Householder reflections, and Givens rotations are more robust, and Householder reflections are the standard choice in numerical software.
The main application is least squares. For a real matrix with and full column rank, the goal is to minimize . The textbook route solves the normal equations , but this squares the condition number, since , and accuracy can be lost quickly. Working from yields , which is solved by back substitution and avoids the squaring. The same idea of repeated QR steps underlies the QR algorithm for eigenvalues.
Cholesky decomposition
If is Hermitian (symmetric in the real case) and positive definite, then for a lower triangular with positive diagonal entries, and this factor is unique. The cost is about operations, roughly half that of LU. No pivoting is needed, because positive definiteness keeps every pivot positive and the process stable. The algorithm also works as a test in practice: if it attempts to take the square root of a nonpositive number, the matrix is not positive definite. Cholesky factors are used to sample from a multivariate normal distribution, since multiplying a vector of independent standard normal variables by produces the covariance .
Schur decomposition
Every complex square matrix admits a Schur decomposition , with unitary and upper triangular. The eigenvalues appear on the diagonal of in some order. Issai Schur established this result in 1909. Unlike diagonalization, it always exists, because it does not require a complete set of eigenvectors. When is normal, is diagonal, which recovers the spectral theorem. For real matrices, the real Schur form uses a real orthogonal and a block triangular whose blocks hold complex conjugate eigenvalue pairs.
Singular value decomposition
Every complex matrix factors as , where and are unitary and is diagonal with nonnegative entries , the singular values. These are the square roots of the eigenvalues of , and the number of nonzero singular values equals the rank. Geometrically, rotates or reflects the input, stretches the coordinate axes by the singular values, and rotates or reflects the result. The unit sphere is thus carried onto an ellipsoid whose semi-axes have lengths .
Keeping the largest singular values and discarding the rest gives the best rank- approximation of in both the spectral and Frobenius norms, a result known as the Eckart–Young–Mirsky theorem. The spectral-norm error of this truncation equals . Storing the truncated factors requires numbers instead of , which underlies image compression and the dimension reduction used in principal component analysis. Inverting only the nonzero singular values also yields the pseudoinverse, and the ratio gives the condition number of a full-rank matrix in the spectral norm.
Norms, conditioning, and numerical methods
Norms assign a size to matrices. They make it possible to bound errors, to measure how strongly a matrix distorts vectors, and to quantify how sensitive a computed answer is to rounding and to noise in the input data.
Matrix norms
A matrix norm can be built from a vector norm. For an matrix , the induced (operator) norm is
A matrix norm of this kind can describe how far the operator can stretch vectors. The induced norm is therefore the largest factor by which lengthens any unit vector. Because it is defined through the supremum, it satisfies and the submultiplicative rule . The first of these inequalities follows directly from the definition of an induced norm.
The most common cases are the 1-norm, which equals the largest absolute column sum; the -norm, which equals the largest absolute row sum; and the 2-norm, which equals the largest singular value of . The 2-norm is the one usually meant by "the operator norm" for Euclidean vectors.
Not every useful matrix norm is induced. The entrywise norms treat an matrix as a vector of length . The Frobenius norm is the most important of them:
The Frobenius norm is not an induced norm; it belongs instead to the family of Schatten norms. The Schatten norms are computed from the singular values of the matrix. Because the entrywise norms treat the matrix as a vector, they are directly tied to the norms of the vector space. For a column or row vector, the Frobenius norm coincides with the ordinary Euclidean length.
Condition number
For an invertible square matrix, the condition number is
With the 2-norm, , the ratio of the largest to the smallest singular value. A large condition number means that the solution of a linear system may be highly sensitive to perturbations or errors in the right-hand side. When the condition number is small, the solution changes relatively little when the data changes.
The quantity is best understood as a worst-case bound. For a perturbed system , one has
so the relative error in the solution can be amplified by up to . A condition number therefore records the worst-case sensitivity to small perturbations. Perturbation theory also shows that for least-squares problems the sensitivity of some components can be as large as the square of the condition number. For a least-squares problem, the sensitivity of the components depends on the right-hand side and may be as high as the square of the condition number. This is one reason why forming the normal equations, whose coefficient matrix has condition number , is avoided when is ill-conditioned. The Hilbert matrix is a standard example of rapid growth: its condition number grows very fast as its size increases.
Finite-precision arithmetic and stability
Real computations use floating-point numbers. In IEEE double precision the unit roundoff is , so each arithmetic operation introduces a relative error of about this size. A very large condition number leads to a substantial loss of significant digits in the computed solution. As a rough rule, the relative error of a computed solution can be of order , so about decimal digits may be lost.
For this reason numerical analysis asks for backward stability. An algorithm is backward stable if the computed is the exact solution of a nearby problem, , with . Gaussian elimination with partial pivoting, which underlies LU decomposition, is backward stable in practice. Pivoting keeps the multipliers small and limits the growth of entries, which would otherwise magnify rounding errors. Methods that form or that use explicit inverses are generally less accurate than factorizations applied directly to .
Iterative methods for large sparse systems
Many systems from discretized partial differential equations or large optimization problems have very large dimension but only a few nonzero entries per row, which is the setting of sparse matrices. Iterative algorithms are suited to sparse systems that are too large for direct methods such as Cholesky factorization. Factorizations can create fill-in, destroying sparsity and memory efficiency, so iterative solvers are often preferred.
Krylov subspace methods form one major family. They access the matrix only through matrix-vector products and work with the resulting vectors. The method thus can avoid storing matrix factors, and it can exploit sparsity to reduce storage and computation. At step , the iterate is chosen from the Krylov subspace , where is the initial residual. At each iteration, the best linear combination of the Krylov basis vectors is chosen to form an improved solution.
The conjugate gradient method is the classic choice when is real, symmetric and positive definite. In that case the method enforces that the residual is orthogonal to the Krylov subspace, which yields short recurrences and low memory use. Its error after steps is bounded in terms of the condition number, roughly
where . Here is the ratio of the largest to the smallest eigenvalue. Convergence is therefore fast when is close to 1 and slow when is large. This motivates preconditioning, in which the system is transformed into one with a more favorable spectrum. For nonsymmetric matrices, GMRES chooses the iterate so that the residual norm is minimized over the Krylov subspace. BiCGSTAB is applicable to nonsymmetric matrices, and it does not require the transpose of .
Algebraic structure
For a fixed size and a field , the set of all matrices with entries in is a ring under entrywise addition and matrix multiplication. Its zero element is the zero matrix and its identity element is the identity matrix . Because it is closed under both operations and satisfies the associativity and distributive laws, is a unital associative F-algebra of dimension , with the matrix units as a basis. This makes it one of the basic examples in ring theory and in abstract-algebra.
Noncommutativity and zero divisors
For the ring is just itself and is commutative. For multiplication is never commutative in general. Take and . Then and , which are different. The same example shows that zero divisors exist: although neither factor is zero. Over a field, the left and right zero divisors coincide, and they are exactly the singular matrices, that is, those with determinant zero. Units (two-sided invertible elements) are exactly the matrices with nonzero determinant. Since a nonzero singular matrix exists whenever , the ring is never a domain in that case.
Nilpotent elements
A matrix is nilpotent if for some positive integer . For matrices, whenever is nilpotent, a consequence of the Cayley–Hamilton theorem. Strictly upper triangular matrices are the standard examples: satisfies . Every nonzero nilpotent matrix is a zero divisor, since if with minimal, then with both factors nonzero. The nilpotent matrices do not form a subring with identity, and the ring is semisimple, so its Jacobson radical is zero. Nilpotent elements therefore do not contribute to a radical in this ring, although they are central to the study of its non-semisimple subalgebras.
The general linear group and its subgroups
The units of form the multiplicative group of invertible matrices, called the general linear group. Its center consists of the scalar matrices with . The determinant is a group homomorphism , and its kernel is the special linear group of matrices with determinant one, a normal subgroup. Over the real or complex numbers, the orthogonal group consists of matrices satisfying , and the unitary group consists of matrices satisfying . Their intersections with the determinant-one condition give and . Other important subgroups include the upper triangular matrices in , which form a solvable subgroup, and the permutation matrices, which form a finite subgroup. Over or , these groups are Lie groups, and their tangent spaces at the identity are matrix Lie algebras such as and .
Representations of groups and algebras
A linear representation of a group of degree over is a group homomorphism . An algebra representation of an -algebra is an algebra homomorphism . Choosing a basis of an -dimensional vector space identifies linear operators with matrices, and changing basis replaces by for some invertible . Thus the study of representations reduces to the study of matrix-valued homomorphisms up to this equivalence. This viewpoint underlies representation-theory, where the Artin–Wedderburn theorem describes semisimple algebras as products of matrix rings over division rings, and where matrix groups serve as the basic examples of symmetry groups in physics.
The trace as a linear functional
The trace , the sum of the diagonal entries, is a linear functional. It satisfies , and as a consequence it is invariant under similarity: . Over an algebraically closed field, the trace equals the sum of the eigenvalues counted with algebraic multiplicity, which links it to the spectrum of a matrix. The trace is not multiplicative, so it is not a ring homomorphism, but its kernel is a Lie subalgebra of codimension one, since the commutator of two matrices always has trace zero.
Computational complexity of matrix multiplication
The naive algorithm
Computing for two matrices directly from the definition, where each entry is , needs scalar multiplications and additions, or scalar operations in total. The cost therefore grows as . For rectangular matrices of sizes and , the count of multiplications is . Gaussian elimination, the standard method for solving linear systems and computing determinants, has the same cubic cost, and until the late 1960s the cubic exponent was widely assumed to be the true cost of the problem.
Strassen's algorithm
In 1969 Volker Strassen showed that the product of two block matrices can be formed with seven block multiplications instead of eight, at the price of extra block additions. Because the formulas use only ring operations, they remain valid when the blocks are themselves matrices, and they can be applied recursively to matrices whose size is a power of two. Matrices of other sizes are padded with zeros. The recurrence yields a cost of . The exact scalar operation count is smaller than the naive count only above a crossover size, which is roughly 654 by one published count. Winograd later showed that seven multiplications is optimal for matrices, although his variant uses fewer additions than Strassen's.
The exponent ω and later improvements
The exponent of matrix multiplication, usually written , is the infimum of the exponents for which matrices can be multiplied in arithmetic operations. Strassen's result gave . Through the late 1970s and 1980s, researchers including Pan, Bini, Schönhage, Romani and Strassen himself lowered the bound step by step, reaching about 2.497 in 1986. In 1990 Coppersmith and Winograd obtained about 2.376 by analysing powers of a particular tensor, and this bound stood for roughly two decades.
From 2014 onward the gains came from refinements of the "laser method" of Strassen, which analyse powers of the Coppersmith–Winograd tensor and compensate for losses when the pieces are combined. Reported bounds fell to about 2.3729 in 2014 and 2020, to about 2.371866 in 2023 (Duan, Wu and Zhou), to 2.371552 in 2024 (Vassilevska Williams, Xu, Xu and Zhou), and to 2.371339 in a later 2024 paper by Alman and coauthors. A 2026 preprint reports by extending the same analysis to a deeper recursion level. Over the 35 years after 1990 the bound changed only slightly, which is why the improvements are described as incremental. Most of the constants involved are very large, so these algorithms are not used in practice.
Lower bounds and open questions
The only general lower bound is , which holds simply because the output has entries that must each be written. No larger unconditional lower bound on is known, and many researchers conjecture that . Several papers show that the laser method applied to the Coppersmith–Winograd tensor cannot prove , and more general barriers suggest that a wide class of known techniques cannot reach . Concrete lower bounds exist for restricted models. For example, computing the product of two matrices over the binary field requires at least about multiplications. These bounds concern the number of multiplications in particular models, not the exponent itself. Whether quadratic-time matrix multiplication is achievable therefore remains open.
Practical performance
Asymptotic gains come at a cost. Strassen-type recursion needs extra memory, adds additions that can reduce numerical stability, and performs poorly on small blocks. For this reason, high-performance libraries normally use a blocked cubic algorithm tuned to cache hierarchies and to parallel hardware such as the graphics processing units used in deep-learning. Strassen-type recursion is typically applied only above a cutoff size. Algorithms with exponents below 2.81 are described in the literature as almost never implemented, and when they are compared in practice, Strassen's scheme often remains the favoured choice.
Relation to other linear algebra tasks
The cost of matrix multiplication sets the cost of many other operations. Strassen's 1969 work already gave a block formula for inversion whose cost is of the same order as multiplication, and later results showed that the determinant, the matrix inverse, LU decomposition and the solution of linear systems can all be computed in operations. The reverse reductions also hold for many of these tasks, so that they have essentially the same exponent as multiplication. Since is at most 2.38 for every known method, all these problems are asymptotically faster than the cubic Gaussian elimination. Matrix-based methods such as QR decomposition and singular value decomposition are more involved, and their exact complexity depends on the algorithm and on the required accuracy.
History
Early elimination methods in China
The earliest systematic procedures for simultaneous linear equations come from ancient China. The Nine Chapters on the Mathematical Art is usually dated to around the first century BCE, and its compilers are anonymous. The chapter on Fangcheng includes 18 practical problems, such as determining yields from mixed bundles of rice or prices of livestock. Chapter 7, "Excess and Deficit," handles two-unknown linear problems by a principle that Western authors later called false position. Each of the 18 problems in the Fangcheng chapter reduces to solving a system of simultaneous linear equations.
The method was carried out on a counting board. Coefficients and constants were arranged into a rectangular array, with each row representing an equation and the columns corresponding to the variables plus the right-hand side. Elimination then proceeded by manipulating these columns, and the procedure is often compared with the elimination later associated with Gauss. Systems of linear equations were solved by a principle similar to Gaussian elimination. Historians disagree about how much the text advanced beyond existing practice. An older consensus saw little development beyond the basic technique, while more recent re-examinations of the reconstructed text point to refinements inherited from the earlier Book of Computation. The previous consensus of historians of Chinese mathematics suggests that the Nine Chapters showed little development beyond the initial practice of fangcheng, however a closer examination of the extant source outlines comparable developments.
Determinants and linear systems in Europe
In Europe, determinants appeared in the late seventeenth century. In a 1693 letter to Guillaume de l'Hôpital, Leibniz stated the compatibility condition for three linear equations in two unknowns, which is a determinant condition. He stressed the usefulness of two indices when writing the coefficients of the equations. He also knew that a determinant could be expanded along any column, a result now called Laplace expansion. He also knew that a determinant could be expanded using any column. Dating his discoveries is itself contested. One account states that this method for solving systems of linear equations based on determinants was found in 1684 by Leibniz, while Gabriel Cramer published his findings in 1750.
Determinant ideas also arose independently in Japan. Seki Takakazu arrived at the notion of a determinant while solving the problem of finding common roots of algebraic equations. In print, the early European results came from Scottish mathematician Colin Maclaurin. His Treatise of Algebra appeared only in 1748, after his death, and it contains the first published results on determinants, proving Cramer's rule for 2 × 2 and 3 × 3 systems and indicating how the 4 × 4 case would work. Cramer then gave the general rule for n×n systems in his 1750 work on algebraic curves. The rule is named after him, as he introduced it in 1750 in Introduction à l'Analyse des lignes Courbes algébriques.
Matrices as objects in the nineteenth century
The word "matrix" was introduced in the 1850s by James Joseph Sylvester. Sources differ on the exact year, giving 1848, 1850, or 1851. Sylvester defined a matrix as an oblong arrangement of terms, and he regarded it as the source of various determinants taken from square arrays within it. Arthur Cayley then turned arrays of numbers into objects with their own algebra. By 1853 Cayley had published a note giving, for the first time, the inverse of a matrix. His 1858 memoir is the best-known landmark. In that memoir he introduced the term "matrix" for a square array of numbers and observed that such arrays could be added and multiplied to form what is now called a linear associative algebra. Cayley also showed that earlier coefficient arrays from quadratic forms and linear transformations were special cases of the general concept.
The memoir was not an immediate success. Cayley's celebrated memoir went generally unnoticed, especially outside England, until the 1880s. Cayley verified the Cayley–Hamilton theorem for 2 × 2 matrices and stated it for 3 × 3 matrices, and Frobenius later attributed the general result to Cayley, although Frobenius had been the first to prove the general theorem. Frobenius also adopted the term "matrix" only after he became aware of Cayley's memoir in 1896. Earlier, Cauchy had shown that real symmetric matrices have real eigenvalues. Cauchy's 1829 memoir provided the first general proof that the eigenvalues of a symmetric matrix are real. German algebraists such as Weierstrass, Kronecker, and Frobenius then developed canonical forms for bilinear forms and matrix pencils.
Axiomatic and abstract linear algebra in the twentieth century
Early in the twentieth century, linear algebra shifted from concrete arrays toward abstract vector spaces over arbitrary fields. Earlier steps included Hermann Grassmann's Ausdehnungslehre (1844) and Giuseppe Peano's axiomatic definition of vector spaces in 1888. David Hilbert's work on integral equations between about 1904 and 1910 introduced infinite-dimensional spaces, where operators need not be finite matrices. This work was followed by contributions from Erhard Schmidt and Frigyes Riesz. Hilbert's broader commitment to the axiomatic method, shown in his Grundlagen der Geometrie (1899), shaped how these ideas were presented. In the 1920s and early 1930s, John von Neumann supplied the abstract axiomatic definition of the spaces now called Hilbert spaces and used them to formulate quantum mechanics. Stefan Banach's work on normed spaces ran in parallel. Textbooks such as van der Waerden's Moderne Algebra presented vector spaces in an abstract algebraic form, and this viewpoint became the standard approach to linear-algebra and functional-analysis.
Applications in physics
Matrices entered physics in 1925, when Werner Heisenberg, Max Born, and Pascual Jordan reformulated quantum theory in matrix language. Matrix mechanics is a formulation of quantum mechanics created by Werner Heisenberg, Max Born, and Pascual Jordan in 1925. Born and Jordan saw that the quantities Heisenberg had been manipulating followed the multiplication rules of matrix algebra, which made noncommutativity a central feature of the theory. Born, Heisenberg, and Jordan then took Hermitian matrices as the mathematical stand-ins for measurable quantities. The reason is that a Hermitian operator's expectation values are real, so all physical observables are associated with Hermitian operators. The eigenvalues of such an operator are real and are read as possible measurement outcomes, while its eigenvectors describe the corresponding states.
Matrix mechanics and the Schrödinger picture were later shown to be equivalent. In a fixed basis, the state of a system is a column vector of complex amplitudes, the Hamiltonian is a Hermitian matrix, and the time-dependent Schrödinger equation becomes a linear system of first-order differential equations for those amplitudes. Its formal solution is generated by the matrix exponential of the Hamiltonian multiplied by . That propagator is unitary, which is why it preserves the norm of the state and therefore total probability. Diagonalizing the Hamiltonian, as described in the eigenvalue section, gives the energy levels and stationary states directly.
The Pauli matrices are the simplest nontrivial example. They are three complex matrices, , , and , which together with the identity form a basis for the Hermitian matrices. The Pauli matrices are traceless, each of them squares to the identity matrix, and their determinants are −1. Because they square to the identity, their eigenvalues can only be . For a spin-½ particle, the spin operator is written as , so the measurable spin components along each axis take the values . Rotations of a spin-½ state are generated by the same matrices. The rotation operator lies in the group SU(2), which double-covers the group of ordinary three-dimensional rotations, SO(3). This is why a spinor returns to its original state only after a turn, a fact noted for spin-½ particles. Ordinary rotations of spatial vectors, by contrast, are represented by orthogonal matrices with determinant one.
The density matrix generalizes the state vector to mixed states. If a system is in state with probability , then . In general, a density matrix is a Hermitian, positive semi-definite, trace-1 matrix. A pure state gives , whereas for a mixed state the purity is strictly less than one, so the purity distinguishes the two cases. Two different ensembles of states can have identical density matrices, and therefore quantum mechanically represent identical states. The maximally mixed state of a -level system is . For a qubit, every density matrix can be written as a combination of the identity and the Pauli matrices, and the admissible coordinates fill the unit ball, the Bloch ball, whose surface holds the pure states. In quantum information, density matrices are needed when a subsystem is entangled with another system, or when a system is open and interacts with its environment, which causes decoherence. In those cases the state of the subsystem cannot be described by a single state vector.
General relativity uses matrix-like arrays in a more structured way. In four-dimensional spacetime, the metric tensor has at each point ten independent components, which form a symmetric array. It defines the spacetime interval through , using the Einstein summation convention. In flat spacetime in Cartesian coordinates it reduces to the Minkowski metric , a Lorentzian signature that defines the light cone. The inverse matrix raises indices, and its determinant enters the invariant volume element . The Einstein field equations relate the Einstein tensor, built from the metric and its derivatives, to the stress-energy tensor, and both sides are symmetric component arrays. The matrix of components is not itself a geometric object, however. Under a change of coordinates it transforms through the Jacobian matrix of the coordinate map, so the coordinate-independent content lies in the tensor as a whole.
Applications in statistics and data analysis
Multivariate statistics is built on matrices. Each observation is a vector of measurements, and a data set is an array with one row per observation. Several central objects in the field are matrices with specific algebraic properties.
Covariance matrix
For a random vector with mean vector , the covariance matrix is . Its entry is , so the diagonal holds the variances. The matrix is symmetric, and for any fixed vector the quadratic form equals , which is nonnegative. Hence is positive semidefinite, and it is positive definite when no nonzero linear combination of the components is almost surely constant. An affine transformation acts on the matrix in a simple way: the covariance of is . The spectral theorem gives with orthogonal and nonnegative diagonal , so the eigenvalues are the variances along the principal axes of the distribution. The density of a multivariate normal distribution is written with and .
For a data matrix , subtracting each column's mean yields a centered matrix , and the sample covariance matrix is . Scaling each entry by the product of the corresponding standard deviations produces the correlation matrix, which has ones on its diagonal.
Least squares in matrix form
A linear model writes the response vector as , where is the design matrix. Ordinary least squares chooses to minimize . Setting the gradient to zero gives the normal equations
When has full column rank, is invertible and . The matrix is the Gram matrix of the columns of . The fitted values are , where projects orthogonally onto the column space of . If the errors have covariance , then .
Forming explicitly squares the condition number of , so numerical software usually relies on QR decomposition or the singular value decomposition instead of inverting the normal matrix. Ridge regression modifies the system to , which remains invertible for even when is rank-deficient.
Principal component analysis
Principal component analysis finds orthogonal directions along which the centered data have the greatest variance. Eigendecomposing gives the principal directions as the columns of . Each eigenvalue is the variance along its direction, and is the share of total variance it explains. Projecting the data onto the leading directions gives the scores .
The same result follows from the SVD , where . This route avoids forming and is therefore the preferred numerical method. Keeping only the largest singular values gives the best rank- approximation of in the Frobenius and spectral norms (Eckart–Young theorem), which underlies dimension reduction and data compression.
Design matrices
A design matrix encodes an experimental or observational setup. Each row corresponds to a run or subject, and each column to a regressor, which may be a continuous covariate, an indicator for a factor level, or an interaction term. In a one-way analysis of variance with three groups, for instance, the columns can be an intercept and two 0/1 indicators. Other coding schemes change the meaning of the coefficients without changing the fitted values. Full column rank is needed for every coefficient to be estimable, and a rank deficiency, such as an intercept together with indicators for all levels, signals aliasing or collinearity.
Because the covariance of the estimates is proportional to , design criteria act on this matrix. D-optimality maximizes , which minimizes the volume of the confidence ellipsoid for the coefficients. A-optimality minimizes , the sum of the coefficient variances. Orthogonal designs make diagonal, so the estimated coefficients are uncorrelated. In multivariate analysis the model becomes , where is an response matrix. The same design matrix serves every response column, so , and the design's structure shapes all outcomes at once, as in multivariate analysis of variance.
Machine learning and neural networks
In a feedforward neural network, the basic computation of a layer is a matrix-vector product followed by a nonlinear activation. If a layer takes an input and produces outputs, its parameters are a weight matrix and a bias vector , and its output is . The function , such as ReLU, sigmoid or tanh, acts entrywise. Stacking layers composes these maps. Without the nonlinearity, the composition would collapse into a single affine map, since a product of matrices is again a matrix. The activation is therefore what gives depth its expressive effect.
Training and inference process many inputs at once. If a batch of input vectors is stored as the columns of , the whole layer becomes one matrix-matrix product, . Multiplying two matrices takes about floating-point operations but reads and writes only about numbers, so the ratio of arithmetic to memory traffic grows with size. This regularity suits hardware. Graphics processing units contain thousands of simple cores that run the same operation on different data, and dedicated matrix units, such as NVIDIA's Tensor Cores, multiply small blocks at reduced precision (for example FP16 or BF16). These designs execute large matrix products far faster than sequential processors. As a result, the cost of parallel matrix multiplication strongly shapes model design, including layer widths and batch sizes, which are often chosen to fit hardware-friendly block sizes.
In transformer models, self-attention relies on several learned matrices. For a sequence of token vectors stored as the rows of , the model forms , and , where and are trained. It then computes
The matrix holds pairwise similarity scores between tokens, and the row-wise softmax converts each row into nonnegative weights that sum to one. Multi-head attention runs several such sets of projections in parallel and combines their outputs through a further learned matrix. The input vocabulary is handled by an embedding matrix , where is the vocabulary size and each row is the learned vector for one token. Multiplying a one-hot row vector by selects a single row, so the lookup is a matrix product in principle, though it is implemented as indexing. Some models reuse this matrix, transposed, as the output projection.
Training relies on matrix calculus. Consider a layer with , and a scalar loss , and suppose the gradient has already been obtained from the layers above by the backpropagation procedure. The chain rule gives , an outer product with the same shape as , and . The gradient passed to the previous layer is , so the transpose of each weight matrix appears in the backward pass. Here is computed from the gradient with respect to by an entrywise product with . For a batch, the weight gradient becomes a single product of the matrix of vectors with , averaged over the batch.
The same objects describe the geometry of optimization. For a vector-valued function , the Jacobian has entries , and the chain rule for composed layers becomes a product of Jacobians. For a scalar loss , the Hessian is symmetric when the second derivatives are continuous. At a critical point, a positive definite Hessian indicates a local minimum. The spread of its eigenvalues, measured by the condition number, governs how slowly gradient descent converges along poorly scaled directions. A network with parameters has an Hessian, which is too large to form for modern models, so practical methods use diagonal or low-rank approximations, Hessian-vector products, or Krylov-type iterations.
Economics, graph theory, and other fields
A graph with n vertices is commonly encoded as an n×n matrix of zeros and ones. The (i,j) entry of this adjacency matrix is 1 if there is an edge from vertex vᵢ to vertex vⱼ and 0 otherwise. For simple graphs every entry is 0 or 1, and for undirected graphs the matrix is symmetric, while in directed graphs row sums give out-degrees and column sums give in-degrees. The main use of this encoding is that matrix powers count paths. The (u,v) entry of Aⁿ equals the number of walks of length n from u to v. The reason is that each product of entries along a sequence of edges contributes one walk, and matrix multiplication sums these contributions over all intermediate vertices. Two consequences follow directly. The distance between two vertices is the smallest nonnegative integer n for which the (i,j) entry of Aⁿ is positive. Also, for an undirected simple graph, the number of triangles equals the trace of A³ divided by 6, the division correcting for the six orderings in which each triangle can be traversed. An incidence matrix, with vertices as rows and edges as columns, plays a complementary role; its product with its own transpose gives the degree matrix plus the adjacency matrix in the unsigned case.
A Markov chain with finitely many states is described by a transition matrix P whose entries are probabilities. The rows of the matrix represent the current state, while the columns represent the next state. Because each row describes a complete set of outgoing probabilities, each row sums to 1. A stationary distribution is a probability row vector π that is unchanged by one step of the chain, so that π = πP. Equivalently, π is a left eigenvector of P with eigenvalue 1, which is why the computation reduces to linear algebra. Existence is guaranteed for finite chains: every finite Markov chain has at least one stationary distribution, but it may not be unique. Uniqueness holds under stronger hypotheses; any irreducible and aperiodic Markov chain has exactly one stationary distribution. In that case the powers of the transition matrix stabilize, and the matrix Pⁿ converges to a matrix whose rows are all equal to π. In a weather model with sunny, cloudy and rainy states, for example, the long-run frequencies of the three states are the entries of π, regardless of the starting state.
The Leontief input-output model is an early large-scale application of matrices in economics. Wassily Leontief developed the model in 1941 in the field of econometrics, and in 1973 Leontief earned the Nobel Prize in economics for his work on the input-output model. The economy is divided into sectors, and the technical coefficients matrix A has entries where each entry aᵢⱼ measures the dollars of input from industry i needed to produce one dollar of output in industry j. If x is the vector of total outputs and f is the vector of final demand, the balance condition reads x = Ax + f, which gives x = (I−A)⁻¹f. The matrix (I−A)⁻¹ is the Leontief inverse, and its entries capture both direct and indirect requirements, since each entry gives the total output of industry i required, directly and indirectly, to deliver one dollar of final demand for industry j's product. This makes it possible to ask questions such as how much steel is embedded in a car, or how a tariff on one sector propagates to others. The model comes in an open form, in which some production is consumed internally and the rest goes to external demand, and a closed form, in which the entire production is consumed by industries.
Matrices are also central to information and geometric technologies. In cryptography, the Hill cipher of 1929 encodes blocks of letters as vectors and multiplies them by an invertible key matrix modulo the alphabet size, so decryption requires the key's inverse modulo that size. In coding theory, a linear error-correcting code over a finite field is specified by a generator matrix G, whose rows span the code, and a parity-check matrix H, where a vector c is a codeword exactly when Hcᵀ = 0. The Hamming code of length 7 uses such matrices to detect and correct any single bit error. In computer graphics, rotations and scalings of two- and three-dimensional points are represented by matrices, and sequences of transformations are composed by matrix multiplication. Because matrix multiplication is not commutative, the order of the transformations matters, and translations are usually incorporated through 4×4 homogeneous-coordinate matrices so that all transformations can be combined the same way.
Generalizations
Tensors
A tensor of order with dimensions can be modeled as a function from the product of index sets into a field , so every entry is addressed by a -tuple of indices. The number of entries of such a tensor is the product of its dimensions. Scalars, vectors, and matrices are the cases of order 0, 1, and 2. In the matrix case the two directions of the array, rows and columns, are called modes, and the number of modes gives the order.
The natural analogue of matrix multiplication for higher-order arrays is tensor contraction. Two tensors are contracted along one index from each, provided those indices have the same length, and the result sums the product over that shared index. The order of the result of a contraction is , where and are the orders of the inputs. Contraction is therefore a direct generalization of the matrix product: when both operands are matrices, the contraction is the ordinary matrix product. Two broad types are distinguished: an "external" contraction between two tensors, which extends the dot product, and an "internal" contraction within a single tensor, which extends the trace.
A second product, the tensor product, combines two arrays without summing over indices. Applied to an matrix and an matrix, it produces an block array in which each entry of the first matrix scales a full copy of the second. Tensor contractions and products are central in multilinear algebra, in the study of tensor networks, and in computations with index notation.
Infinite matrices and operators on Hilbert spaces
The matrix viewpoint extends to infinite index sets. Continuous linear functions on a Hilbert space are described by infinite matrices, in the same way that linear transformations on are represented by finite matrices. Once an orthonormal basis is chosen, the operator acts by the infinite analogue of the usual sum, , and the matrix determines the operator uniquely. Boundedness is the decisive condition: an operator between Hilbert spaces is continuous exactly when it is bounded.
Concrete examples show how subtle the infinite case is. The Hilbert matrix, with entries , acts as a bounded operator on , but it is not a compact operator. Its operator norm on is known in closed form, for . Computing with such matrices is harder than in the finite case, because products and actions involve infinite series that can rarely be evaluated explicitly. Moreover, the conjugate-transpose recipe for the adjoint does not automatically yield a bounded, everywhere defined operator, so the adjoint is usually defined abstractly through the inner product instead.
Matrices over rings and finite fields
Matrices can also be defined with entries from any ring or field. Over a finite field, the situation becomes combinatorial: for a prime power , there is a unique finite field of order , and the invertible matrices over it form the general linear group , a finite group whose size can be counted explicitly.
This setting is central to coding theory. A codeword is produced by multiplying a message vector by a generator matrix ; the set of all such codewords forms a subspace of the ambient vector space, and when the rows of are linearly independent, is called a generator matrix for that code. The quality of the code depends on finer properties of the matrix. A systematic generator matrix of the form generates a maximum distance separable code precisely when is full superregular, a condition on all minors that are not trivially zero. This ties determinantal conditions over finite fields to error-correcting performance.
Linear operators in functional analysis and the limits of finite dimension
Most of the theory in this article, including rank, determinants, Gaussian elimination, and the spectral decomposition, relies on finite dimensionality. In functional analysis, vector spaces are infinite-dimensional and operators are typically bounded, unbounded, compact, or of other special kinds. Many finite-dimensional statements survive in modified form; for example, the spectral theory of self-adjoint operators on Hilbert spaces is a substantial extension of the finite Hermitian case, but it must handle continuous spectrum and operators defined only on dense domains. Where a finite matrix can be diagonalized by an orthonormal eigenbasis, an infinite-dimensional operator may have no such basis, so the matrix representation alone does not capture its behavior. The finite-dimensional tools therefore serve as a guide and as a source of intuition rather than as a complete theory of linear operators.
References
- Sparse Matrices — GSL 2.8 documentationgnu.org
- Optimizing Sparse Matrix Multiplications for Graph Neural Networksarxiv.org
- Optimizing Sparse Matrix-Vector Multiplication on Emerging Many-Core Architecturesarxiv.org
- Sparse Matrix Formats — NVPL SPARSEdocs.nvidia.com
- Sparse Storage Formatsintel.com
- Hermitian matrixen.wikipedia.org
- Skew-Hermitian matrixen.wikipedia.org
- Matrices and determinants - MacTutor History of Mathematicsmathshistory.st-andrews.ac.uk
- Linear Algebra - Determinantstheory.stanford.edu
- 12 PREFACE CHAPTER I DETERMINANTSpublish.illinois.edu
- 8 DETERMINANTS.sayahna.org
- Determinantenlink.springer.com
- DETERMINANTS 1. Introduction In these notes we discuss ...sites.math.washington.edu
- Leibniz formula for determinantsen.wikipedia.org
- Cofactor Expansionstextbooks.math.gatech.edu
- An Introduction to Algebraic Combinatoricsarxiv.org
- Eigenvalue and Eigenvector Calculatorpearson.com
- Diagonalizationtextbooks.math.gatech.edu
- Matrix Reference Manual: Eigenvaluesee.ic.ac.uk
- 5.4: Diagonalization - Mathematics LibreTextsmath.libretexts.org
- EIG-0050: Diagonalizable Matrices and Multiplicity - Ximeraximera.osu.edu
- Recitation 8. November 5web.mit.edu
- The Spectral Theoremsites.millersville.edu
- VII.D. THE SPECTRAL THEOREM 253 VII.D. The spectral theoremmath.wustl.edu
- Lecture 3.26. Hermitian, unitary and normal matrices A. Eremenko March 10, 2023math.purdue.edu
- SPECTRAL THEOREM Orthogonal Diagonalizablemath.jhu.edu
- Lecture 28: The Spectral Theorem 28 The Spectral Theorem 28.1ocw.mit.edu
- Math 4571 (Advanced Linear Algebra) Lecture #28web.northeastern.edu
- 10.3: Solution by the Matrix Exponential - Mathematics LibreTextsmath.libretexts.org
- Matrix exponentialen.wikipedia.org
- Spectral Methods in Complex Systemsarxiv.org
- Matrix normen.wikipedia.org
- 4.2: Matrix Norms - Engineering LibreTextseng.libretexts.org
- Lectures on Randomized Numerical Linear Algebraarxiv.org
- Linear Algebra, Part 5: Matrix norms (Mathematica)cfm.brown.edu
- CS 3220: The condition number of a matrix Instructor: Anil Damle Disclaimercs.cornell.edu
- NORTH- HOLLAND Condition Numbers and Their Condition Numbers Desmond J. Highamwebhomes.maths.ed.ac.uk
- Perturbation Theory for the Solution of Systems of ... - DTICapps.dtic.mil
- MATH 3795 Lecture 6. Sensitivity of the Solution of a Linear Systemwww2.math.uconn.edu
- Condition number for finite element discretisation of nonlocal PDE systems with applications to biologyarxiv.org
- Krylov-space-based quasi-newton preconditioner for full-wavefield inversionimage-ppubs.uspto.gov
- Applications of Conjugate Gradient in Bayesian computationarxiv.org
- Krylov subspace methods and CG: OxRSE Trainingtrain.rse.ox.ac.uk
- Characterization of the equivalence of robustification and regularization in linear and matrix regressionarxiv.org
- CONJUGATE GRADIENT METHODS We shall present ...math.uci.edu
- Krylov subspace methods and preconditioners L. Grigori ALPINESwho.rocq.inria.fr
- Zero divisoren.wikipedia.org
- January 2, 2024 Rings Table of Contents 1. Definitions and constructions 1people.math.osu.edu
- graphsearch.epfl.chgraphsearch.epfl.ch
- Strassen's 2x2 matrix multiplication algorithm: A conceptual perspectiveresearchgate.net
- Strassen Formulas -- from Wolfram MathWorldmathworld.wolfram.com
- Tiled Algorithms for Matrix Computations on Multicore Architecturesarxiv.org
- GEOMETRY AND THE COMPLEXITY OF MATRIX MULTIPLICATION J.M. LANDSBERGpeople.tamu.edu
- arxiv.orgarxiv.org
- An overview of the recent progress on matrix multiplicationpeople.csail.mit.edu
- New Bounds for Matrix Multiplication: from Alpha to Omegaarxiv.org
- par.nsf.govpar.nsf.gov
- New Breakthrough Brings Matrix Multiplication Closer to Idealquantamagazine.org
- More Asymmetry Yields Faster Matrix Multiplicationarxiv.org
- Matrix Multiplication Exponent Improved to 2.371177emergentmind.com
- Lower Bounds for Conjunctive Query Evaluationarxiv.org
- Tensor Rank and Complexityarxiv.org
- Fangcheng (mathematics) — Grokipediagrokipedia.com
- Fangcheng (mathematics)en.wikipedia.org
- The Nine Chapters on the Mathematical Art — Grokipediagrokipedia.com
- The Nine Chapters on the Mathematical Arten-academic.com
- Fangcheng Procedure in the Nine Chapters on the Mathematical Arts Revisitedretrospectjournal.com
- Gottfried Wilhelm Leibnizen.wikipedia.org
- Using Cramer’s Rule to Solve a System of Two Equations in Two Variablescourses.lumenlearning.com
- Cayley, Sylvester, and Early Matrix Theoryresearchgate.net
- Algebraic generality vs arithmetic generality in the controversy between C. Jordan and L. Kronecker (1874)arxiv.org
- Cayley, Sylvester, and Early Matrix Theory Nicholas J. Higham January 2008webhomes.maths.ed.ac.uk
- Cayley, Sylvester, and Early Matrix Theory Nick Higham School of Mathematicspdfs.semanticscholar.org
- A Brief History of Linear Algebra and Matrix Theoryconvexoptimization.com
- 1.2: Matrix Mechanics - Chemistry LibreTextschem.libretexts.org
- Perturbing a subject's contextualization of a proposition about an item considered in a quantum representation by altering the itemimage-ppubs.uspto.gov
- Quantum Information Processing: An Essential Primerarxiv.org
- GENERAL I ARTICLE Heisenberg, Matrix Mechanics, and the Uncertainty Principleias.ac.in
- From Heisenberg and Schr\"odinger to the P vs. NP Problemarxiv.org
- Density matrixen.wikipedia.org
- Relativistic Quantum Dynamics: A non-traditional perspective on space, time, particles, fields, and action-at-a-distancearxiv.org
- Pauli Matrix - an overviewsciencedirect.com
- 9.3: Adjacency Matrices - Engineering LibreTextseng.libretexts.org
- Algebraic and geometric methods in enumerative combinatoricsarxiv.org
- Matrix Powersdatafireball.com
- What is a Markov Chain? - dida.dodida.do
- Notes on Randomized Algorithmsarxiv.org
- Stationary Distributions of Markov Chainsbrilliant.org
- Markov Chain Monte Carlo Methods in Quantum Field Theories: A Modern Primerarxiv.org
- PageRank: Standing on the shoulders of giantsarxiv.org
- Input-Output Analysis and Leontief Modelsmaseconomics.com
- 7.2 Application to economics: Leontief Modelmath.ksu.edu
- AI HL Walks and Adjacency Matrices Notes - IB Demystifiedibdemystified.com
- The arithmetic complexity of tensor contractionsarxiv.org
- FLAASH: Flexible Accelerator Architecture for Sparse High-Order Tensor Contractionarxiv.org
- Bounded Linear Operators on Hilbert Spaceslink.springer.com
- The Coding Theory Workbook A companion to EE 567 Version 1.1 Spring 2016community.wvu.edu
- Tensor Algebra and its Applications to Data Science and Statisticsarxiv.org
- Tensor Product - an overviewsciencedirect.com
- Infinite dimensional Hilbert tensors on spaces of analytic functionsarxiv.org
- On the Hilbert matrix operator: a brief surveyarxiv.org
- Chapter 5 Operators on Hilbert space Paragraph ex- panded in version of Dec. 18web.math.ku.dk
- Superregular Matrices over Finite Fieldsmdpi.com
- Finite field matrix channels for network codingarxiv.org