aiwiki.page
English

Matrix (mathematics)

A matrix is a rectangular array of numbers or symbols, arranged in rows and columns, used to represent linear maps, systems of equations, and data.

75 keywords466 linked from4 not yet writtenWritten by AI
Linear AlgebraLinear mapVector spaceSystem of Linear…Real NumberDeterminantMatrix RankEigenvalues and…Matrix (ma…

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 m×nm \times n matrix is a rectangular array of entries arranged in mm horizontal rows and nn 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 ii and column jj is written aija_{ij}, and the whole array is written A=(aij)A = (a_{ij}), or A=(aij)1≤i≤m, 1≤j≤nA = (a_{ij})_{1 \le i \le m,\ 1 \le j \le n} when the ranges need to be stated. For example,

A=(123456)A = \begin{pmatrix} 1 & 2 & 3 \\ 4 & 5 & 6 \end{pmatrix}

is a 2×32 \times 3 matrix with a12=2a_{12} = 2 and a23=6a_{23} = 6. Row ii consists of the entries ai1,…,aina_{i1}, \dots, a_{in}, and column jj consists of a1j,…,amja_{1j}, \dots, a_{mj}. 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 m×nm \times n matrices with entries in a field FF is written Mm×n(F)M_{m\times n}(F) or Fm×nF^{m\times n}. The cases F=RF = \mathbb{R} and F=CF = \mathbb{C} dominate elementary and applied work, so one speaks of the sets Rm×n\mathbb{R}^{m\times n} and Cm×n\mathbb{C}^{m\times n}. When m=nm = n, the matrix is called square, and the set of square matrices is abbreviated Mn(F)M_n(F). The integers mm and nn 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 1×n1 \times n matrix is a row vector, and an m×1m \times 1 matrix is a column vector. By convention, the elements of FnF^n 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 1×11 \times 1 matrix has exactly one entry, and it is in effect a scalar. Strictly speaking, the matrix (a)(a) and the number aa 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 1×11 \times 1 matrix that is read as a number. In this sense, scalars are the degenerate case m=n=1m = n = 1. 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 A=(aij)A = (a_{ij}) and B=(bij)B = (b_{ij}) are equal exactly when they have the same size and agree in every position. That is, if AA is m×nm \times n and BB is p×qp \times q, then A=BA = B holds if and only if m=pm = p, n=qn = q, and aij=bija_{ij} = b_{ij} for all ii and jj. Size is therefore essential. The row (1 2)(1\ 2) and the column with entries 1 and 2 contain the same numbers but are different matrices, and a 2×32 \times 3 matrix can never equal a 3×23 \times 2 matrix, even if the two contain the same multiset of entries.

Because every entry is determined by its index pair, an m×nm \times n matrix can be viewed as a function from {1,…,m}×{1,…,n}\{1, \dots, m\} \times \{1, \dots, n\} into the entry set FF, sending the pair (i,j)(i, j) to aija_{ij}. 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 N×N\mathbb{N} \times \mathbb{N}, 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 A=(aij)A=(a_{ij}) and B=(bij)B=(b_{ij}) are both m×nm\times n, their sum is the m×nm\times n matrix whose (i,j)(i,j) entry is aij+bija_{ij}+b_{ij}. 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 cc from the underlying field, the product cAcA has entries c aijc\,a_{ij}, and this operation is defined for matrices of any size. Together, these two operations make the set of all m×nm\times n matrices over a field a vector space of dimension mnmn. 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 AA is m×nm\times n and BB is n×pn\times p, the product ABAB is m×pm\times p, with entries

(AB)ij=∑k=1naik bkj.(AB)_{ij}=\sum_{k=1}^{n} a_{ik}\,b_{kj}.

Each entry is the dot product of row ii of AA with column jj of BB. The number of columns of AA must equal the number of rows of BB, because each term in the sum pairs an entry of a row of AA with an entry of a column of BB. When this condition holds, the product exists even if BABA does not, and when both are defined the sizes of ABAB and BABA may differ.

Matrix multiplication is associative, (AB)C=A(BC)(AB)C=A(BC), and it distributes over addition from both sides: A(B+C)=AB+ACA(B+C)=AB+AC and (A+B)C=AC+BC(A+B)C=AC+BC. 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

A=(0100),B=(0010),A=\begin{pmatrix}0&1\\0&0\end{pmatrix},\qquad B=\begin{pmatrix}0&0\\1&0\end{pmatrix},

one computes AB=(1000)AB=\begin{pmatrix}1&0\\0&0\end{pmatrix} but BA=(0001)BA=\begin{pmatrix}0&0\\0&1\end{pmatrix}. Thus AB≠BAAB\neq BA. Commuting pairs exist, such as a matrix and any polynomial in itself, but they are the exception rather than the rule. The identity matrix II satisfies IA=AI=AIA=AI=A whenever the sizes allow it.

Transpose and conjugate transpose

The transpose ATA^{\mathsf T} of an m×nm\times n matrix is the n×mn\times m matrix with (AT)ij=aji(A^{\mathsf T})_{ij}=a_{ji}; rows become columns. The basic identities are

(AT)T=A,(A+B)T=AT+BT,(cA)T=c AT,(AB)T=BTAT.(A^{\mathsf T})^{\mathsf T}=A,\qquad (A+B)^{\mathsf T}=A^{\mathsf T}+B^{\mathsf T},\qquad (cA)^{\mathsf T}=c\,A^{\mathsf T},\qquad (AB)^{\mathsf T}=B^{\mathsf T}A^{\mathsf T}.

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 A∗=A‾TA^{*}=\overline{A}^{\mathsf T} combines transposition with entrywise complex conjugation. It satisfies (A∗)∗=A(A^{*})^{*}=A, (A+B)∗=A∗+B∗(A+B)^{*}=A^{*}+B^{*}, (cA)∗=c‾ A∗(cA)^{*}=\overline{c}\,A^{*}, and (AB)∗=B∗A∗(AB)^{*}=B^{*}A^{*}. For real matrices, the conjugate transpose and the transpose coincide.

Block matrices

A matrix can be partitioned into rectangular submatrices called blocks, for example

M=(A11A12A21A22).M=\begin{pmatrix}A_{11}&A_{12}\\A_{21}&A_{22}\end{pmatrix}.

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 MM is partitioned as above and N=(B11B12B21B22)N=\begin{pmatrix}B_{11}&B_{12}\\B_{21}&B_{22}\end{pmatrix} has conformable blocks, then

MN=(A11B11+A12B21A11B12+A12B22A21B11+A22B21A21B12+A22B22).MN=\begin{pmatrix}A_{11}B_{11}+A_{12}B_{21}&A_{11}B_{12}+A_{12}B_{22}\\A_{21}B_{11}+A_{22}B_{21}&A_{21}B_{12}+A_{22}B_{22}\end{pmatrix}.

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 A∈Fn×nA \in \mathbb{F}^{n\times n}. 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 OO is the additive identity: A+O=AA + O = A for every matrix of the same size, and AO=OA=OAO = OA = O for square AA. The identity matrix InI_n has entries δij\delta_{ij}, equal to 1 on the diagonal and 0 elsewhere, and it is the multiplicative identity, so AIn=InA=AAI_n = I_nA = A. Multiplying by a scalar cc corresponds to cIncI_n, which scales every vector by the same factor.

A diagonal matrix D=diag⁡(d1,…,dn)D = \operatorname{diag}(d_1,\dots,d_n) has nonzero entries only on its main diagonal. Multiplying on the left by DD scales each row ii by did_i, and multiplying on the right scales each column. Products and sums of diagonal matrices are again diagonal, and DD is invertible exactly when every di≠0d_i \neq 0, in which case its inverse is diag⁡(1/d1,…,1/dn)\operatorname{diag}(1/d_1,\dots,1/d_n). Diagonal matrices are therefore the simplest model of a coordinate-wise scaling operator.

Triangular matrices generalize this idea. An upper triangular matrix has aij=0a_{ij}=0 whenever i>ji>j, and a lower triangular matrix has aij=0a_{ij}=0 whenever i<ji<j. 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 AT=AA^{\mathsf T}=A, so aij=ajia_{ij}=a_{ji}. A skew-symmetric matrix satisfies AT=−AA^{\mathsf T}=-A, 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 A∗=AA^{*}=A, where A∗A^{*} 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 A∗=−AA^{*}=-A. Multiplying such a matrix by ii 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 QQ is orthogonal when QTQ=IQ^{\mathsf T}Q=I, and a complex square matrix UU is unitary when U∗U=IU^{*}U=I. Equivalently, their columns form an orthonormal basis. Such matrices preserve inner products, ⟨Ux,Uy⟩=⟨x,y⟩\langle Ux, Uy\rangle = \langle x, y\rangle, and therefore preserve lengths, ∥Ux∥=∥x∥\|Ux\| = \|x\|, and angles. They are the linear isometries of Euclidean and Hilbert space. In the real case the determinant is ±1\pm 1: matrices with determinant +1+1 are rotations, and those with determinant −1-1 include reflections. In two dimensions, the rotation by an angle θ\theta is (cos⁡θ−sin⁡θsin⁡θcos⁡θ)\begin{pmatrix}\cos\theta & -\sin\theta\\ \sin\theta & \cos\theta\end{pmatrix}. The orthogonal matrices of a fixed size form the group O(n)O(n), and the unitary matrices form U(n)U(n), 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 mnmn 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 m+1m+1, so that the entries of row ii 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 mnmn, 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 VV be an nn-dimensional vector space over a field FF with ordered basis (v1,…,vn)(v_1,\dots,v_n), and let WW be an mm-dimensional space with basis (w1,…,wm)(w_1,\dots,w_m). A linear map T ⁣:V→WT\colon V\to W is determined by the images T(vj)T(v_j), and each image has a unique expansion T(vj)=∑i=1maijwiT(v_j)=\sum_{i=1}^{m} a_{ij}w_i. The scalars aija_{ij} form an m×nm\times n matrix AA, whose jj-th column is the coordinate vector of T(vj)T(v_j). With this convention, the coordinates of T(x)T(x) are obtained from the coordinates of xx by AA, that is, [T(x)]C=A [x]B[T(x)]_{C}=A\,[x]_{B}. Taking the standard bases of FnF^n and FmF^m, the map x↦Axx\mapsto Ax is itself a linear map, and every linear map Fn→FmF^n\to F^m arises this way from exactly one matrix. The space of such maps therefore has dimension mnmn, matching the number of entries.

The row-by-column rule for matrix multiplication was chosen so that it corresponds to composition. If AA is an m×nm\times n matrix representing T ⁣:Fn→FmT\colon F^n\to F^m, and BB is a p×mp\times m matrix representing S ⁣:Fm→FpS\colon F^m\to F^p, then BABA is a p×np\times n matrix representing S∘TS\circ T. This follows because (BA)x=B(Ax)(BA)x=B(Ax) for every vector xx. 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: S∘TS\circ T and T∘ST\circ S 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 T ⁣:V→VT\colon V\to V has matrix AA in a basis B\mathcal{B}, and let B′\mathcal{B}' be another basis. Let PP be the change-of-basis matrix whose columns are the coordinates of the new basis vectors in the old basis, so that [x]B=P [x]B′[x]_{\mathcal{B}}=P\,[x]_{\mathcal{B}'}. If A′A' is the matrix of TT in B′\mathcal{B}', then comparing AP[x]B′A P[x]_{\mathcal{B}'} with PA′[x]B′P A'[x]_{\mathcal{B}'} gives

A′=P−1AP.A' = P^{-1} A P.

For a map T ⁣:V→WT\colon V\to W between different spaces, changing the basis in both gives A′=Q−1APA' = Q^{-1} A P, where QQ is the change-of-basis matrix in WW. 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 V=WV=W and the same basis is used on both sides, the relation B=P−1APB = P^{-1}AP 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 Av=λvAv=\lambda v, then the coordinate vector of vv in the new basis is P−1vP^{-1}v.

The kernel and image of a linear map correspond directly to parts of its matrix. The kernel of TT corresponds to the null space {x:Ax=0}\{x : Ax=0\}, since coordinates of kernel vectors are exactly the solutions of this homogeneous system. The image of TT is spanned by the vectors T(v1),…,T(vn)T(v_1),\dots,T(v_n), so in coordinates it is the column space of AA, the span of the columns of AA. The nullity of AA is the dimension of its null space, and the rank is the dimension of its column space. These quantities satisfy the rank–nullity theorem: rank⁡(A)+nullity⁡(A)=n\operatorname{rank}(A)+\operatorname{nullity}(A)=n. A nonzero kernel vector is a nontrivial linear relation among the columns of AA, so TT is injective exactly when the columns are linearly independent, and surjective exactly when rank⁡(A)=m\operatorname{rank}(A)=m.

As an example, consider the differentiation map DD on polynomials of degree at most 3, with basis 1,x,x2,x31,x,x^2,x^3, into polynomials of degree at most 2, with basis 1,x,x21,x,x^2. Since D(1)=0D(1)=0, D(x)=1D(x)=1, D(x2)=2xD(x^2)=2x, and D(x3)=3x2D(x^3)=3x^2, the matrix is

(010000200003).\begin{pmatrix} 0 & 1 & 0 & 0 \\ 0 & 0 & 2 & 0 \\ 0 & 0 & 0 & 3 \end{pmatrix}.

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 DD is the set of constant polynomials, and the rank–nullity relation 3+1=43+1=4 holds.

Determinants

The determinant is a scalar attached to each square matrix. For a 2×2 matrix it is det⁡(abcd)=ad−bc\det\begin{pmatrix}a&b\\c&d\end{pmatrix}=ad-bc. 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 n×nn\times n matrix A=(aij)A=(a_{ij}), the Leibniz formula is

det⁡A=∑σ∈Snsgn⁡(σ)∏i=1nai,σ(i),\det A=\sum_{\sigma\in S_n}\operatorname{sgn}(\sigma)\prod_{i=1}^{n}a_{i,\sigma(i)},

where SnS_n is the symmetric group of permutations of {1,…,n}\{1,\dots,n\} and sgn⁡(σ)\operatorname{sgn}(\sigma) is +1+1 for even permutations and −1-1 for odd ones. Each term of the sum picks exactly one entry from each row and each column, so the formula has n!n! terms. For n=3n=3 there are six terms, which is the origin of the familiar diagonal rule.

The formula can also be organized recursively. The minor MijM_{ij} is the determinant of the submatrix obtained by deleting row ii and column jj, and the cofactor is Cij=(−1)i+jMijC_{ij}=(-1)^{i+j}M_{ij}. Expansion along any row ii gives

det⁡A=∑j=1naijCij,\det A=\sum_{j=1}^{n}a_{ij}C_{ij},

and the same value results from expanding along any column. An induction on nn shows that this recursive form agrees with the Leibniz sum; this is the cofactor expansion of the determinant. Because the recursion does roughly n!n! 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 −1-1, and two equal rows force the determinant to be zero. Multiplying one row by a scalar cc multiplies the determinant by cc. 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. det⁡AT=det⁡A\det A^{\mathsf T}=\det A, so the same properties hold for columns.
  • Multiplicativity. det⁡(AB)=det⁡A det⁡B\det(AB)=\det A\,\det B for square matrices of the same size. Consequently det⁡(A−1)=1/det⁡A\det(A^{-1})=1/\det A, 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, det⁡A=0\det A=0 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 n×nn\times n matrix, the columns can be treated as edge vectors of a parallelepiped in Rn\mathbb{R}^n. Its volume is ∣det⁡A∣|\det A|. In the plane, the parallelogram spanned by (a,c)(a,c) and (b,d)(b,d) has area ∣ad−bc∣|ad-bc|. The sign records orientation: a positive determinant means the map preserves orientation, and a negative one means it reverses it. A linear map TT therefore multiplies all volumes by the same factor ∣det⁡T∣|\det T|, 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 gg is a continuously differentiable map with invertible Jacobian matrix DgDg, then

∫g(U)f(y) dy=∫Uf(g(u)) ∣det⁡Dg(u)∣ du.\int_{g(U)}f(\mathbf y)\,d\mathbf y=\int_U f(g(\mathbf u))\,\bigl|\det Dg(\mathbf u)\bigr|\,d\mathbf u.

In polar coordinates the Jacobian determinant is rr, which gives the familiar factor r dr dθr\,dr\,d\theta.

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 5×55\times5, 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 AA of order nn is invertible (or non-singular) if there is a matrix A−1A^{-1} with AA−1=A−1A=InAA^{-1} = A^{-1}A = I_n, where InI_n is the identity matrix. When it exists, the inverse is unique. If BB and CC both satisfy the defining equations, then B=B(AC)=(BA)C=CB = B(AC) = (BA)C = C. For square matrices, a one-sided inverse is automatically two-sided, so BA=InBA = I_n alone implies AB=InAB = I_n. Inverses reverse the order of products, (AB)−1=B−1A−1(AB)^{-1} = B^{-1}A^{-1}, and commute with transposition, (AT)−1=(A−1)T(A^{\mathsf T})^{-1} = (A^{-1})^{\mathsf T}.

Equivalent conditions for invertibility

For a square matrix over a field, the following statements are equivalent:

  • AA is invertible.
  • det⁡A≠0\det A \neq 0.
  • rank⁡A=n\operatorname{rank} A = n, so the columns (and rows) are linearly independent and span the whole space.
  • The null space of AA is trivial, that is, {0}\{0\}. Equivalently, the map x↦Axx \mapsto Ax is injective.
  • For every right-hand side bb, the equation Ax=bAx = b has exactly one solution.
  • Zero is not an eigenvalue of AA.
  • AA is row equivalent to InI_n.

These conditions describe one fact from different angles: the linear map represented by AA is a bijection of FnF^n. The rank-nullity theorem links the two dimensions, since rank plus nullity equals nn, 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 adj⁡(A)\operatorname{adj}(A) is the transpose of the matrix of cofactors, and it satisfies A adj⁡(A)=adj⁡(A) A=det⁡(A) InA\,\operatorname{adj}(A) = \operatorname{adj}(A)\,A = \det(A)\,I_n. Hence, when det⁡A≠0\det A \neq 0,

A−1=1det⁡Aadj⁡(A).A^{-1} = \frac{1}{\det A}\operatorname{adj}(A).

For a 2×22\times 2 matrix this reduces to (abcd)−1=1ad−bc(d−b−ca)\begin{pmatrix} a & b \\ c & d \end{pmatrix}^{-1} = \frac{1}{ad-bc}\begin{pmatrix} d & -b \\ -c & a \end{pmatrix}. The formula is convenient for small or symbolic matrices, but cofactor expansion grows factorially with nn, so it is impractical for large matrices.

Gauss-Jordan elimination is the standard numerical method. One forms the augmented matrix [A∣In][A \mid I_n] and applies elementary row operations until the left block becomes InI_n. The right block then holds A−1A^{-1}. If no nonzero pivot can be found in some column, the matrix is singular. The work is on the order of n3n^3 arithmetic operations, the same order as an LU factorization. In practice, software rarely forms A−1A^{-1} explicitly. It factors AA 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 det⁡A≠0\det A \neq 0, the unique solution of Ax=bAx = b has components

xi=det⁡Aidet⁡A,i=1,…,n,x_i = \frac{\det A_i}{\det A}, \qquad i = 1,\dots,n,

where AiA_i is obtained from AA by replacing its ii-th column with bb. 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 n+1n+1 determinants. Computed by cofactor expansion, the cost is enormous. Even with elimination-based determinants, each costing about n3n^3 operations, the total is roughly n4n^4, compared with about n3n^3 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 m×nm\times n matrix AA with m>nm > n and full column rank has a left inverse LL, an n×mn\times m matrix with LA=InLA = I_n. One choice is L=(ATA)−1ATL = (A^{\mathsf T}A)^{-1}A^{\mathsf T}, which exists because ATAA^{\mathsf T}A is then invertible. Similarly, a matrix with full row rank and m<nm < n has a right inverse RR with AR=ImAR = I_m, for instance R=AT(AAT)−1R = A^{\mathsf T}(AA^{\mathsf T})^{-1}. These one-sided inverses are generally not unique, and a left inverse does not satisfy AL=IAL = I in general.

The Moore-Penrose pseudoinverse A+A^{+} extends the idea to every matrix over the real or complex numbers. It is the unique matrix satisfying four Penrose conditions: AA+A=AAA^{+}A = A, A+AA+=A+A^{+}AA^{+} = A^{+}, and the products AA+AA^{+} and A+AA^{+}A are Hermitian. Using the singular value decomposition A=UΣV∗A = U\Sigma V^{*}, one has A+=VΣ+U∗A^{+} = V\Sigma^{+}U^{*}, where Σ+\Sigma^{+} inverts each nonzero singular value and leaves zeros in place. If AA is invertible, A+=A−1A^{+} = A^{-1}. If AA has full rank, A+A^{+} reduces to one of the one-sided inverses above. For any bb, the vector x=A+bx = A^{+}b minimizes ∥Ax−b∥2\lVert Ax - b\rVert_2, 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 AA.

Rank and linear systems

Rank and the equality of row and column rank

The rank of an m×nm \times n matrix AA over a field FF is the dimension of its column space, the subspace of FmF^m spanned by its columns. The row space, spanned by the rows in FnF^n, has its own dimension, called the row rank. The two dimensions are always equal, so the rank is unambiguous and satisfies rank⁡(A)≤min⁡(m,n)\operatorname{rank}(A) \le \min(m,n).

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 [A∣b][A \mid b] produces an equivalent system, which is solved by back-substitution. Variables in non-pivot columns are free parameters. Elimination on an n×nn \times n system takes on the order of 23n3\tfrac{2}{3}n^3 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 T:V→WT : V \to W between finite-dimensional spaces, the dimension of the kernel plus the dimension of the image equals the dimension of VV. Applied to an m×nm \times n matrix regarded as a map Fn→FmF^n \to F^m, the theorem reads

rank⁡(A)+dim⁡null⁡(A)=n,\operatorname{rank}(A) + \dim \operatorname{null}(A) = n,

where null⁡(A)\operatorname{null}(A) is the set of solutions of Ax=0Ax = 0. The theorem constrains solution sets in the following way.

For a homogeneous system Ax=0Ax = 0, the solution set is the null space, a subspace of dimension n−rank⁡(A)n - \operatorname{rank}(A). Nontrivial solutions exist exactly when rank⁡(A)<n\operatorname{rank}(A) < n, which is the same as saying the columns are linearly dependent.

For an inhomogeneous system Ax=bAx = b, the system is consistent exactly when bb lies in the column space, that is, when rank⁡(A)=rank⁡([A∣b])\operatorname{rank}(A) = \operatorname{rank}([A \mid b]). When a particular solution xpx_p exists, the full solution set is xp+null⁡(A)x_p + \operatorname{null}(A), a translate of the null space. It is a single point when rank⁡(A)=n\operatorname{rank}(A) = n and otherwise a translate of a subspace of dimension n−rank⁡(A)n - \operatorname{rank}(A).

As an illustration, take x+2y+z=3x + 2y + z = 3 and 2x+4y+2z=62x + 4y + 2z = 6. Subtracting twice the first row from the second gives a zero row, so the rank is 1. With n=3n = 3, the null space has dimension 2, and the solutions form the plane x=3−2y−zx = 3 - 2y - z with yy and zz free. By contrast, x+2y=3x + 2y = 3 and 2x+4y=72x + 4y = 7 reduce to 0=10 = 1. The coefficient rank is 1 while the augmented rank is 2, so the system has no solution.

Classification of solutions by rank

Let AA be m×nm \times n, let r=rank⁡(A)r = \operatorname{rank}(A), and consider Ax=bAx = b.

  • No solution: rank⁡(A)<rank⁡([A∣b])\operatorname{rank}(A) < \operatorname{rank}([A \mid b]), so bb is outside the column space.
  • Exactly one solution: rank⁡(A)=rank⁡([A∣b])=n\operatorname{rank}(A) = \operatorname{rank}([A \mid b]) = n.
  • Infinitely many solutions: rank⁡(A)=rank⁡([A∣b])<n\operatorname{rank}(A) = \operatorname{rank}([A \mid b]) < n. Over an infinite field the solution set is infinite; over a finite field with qq elements it contains q n−rq^{\,n-r} solutions.

Two special cases follow directly. If r=mr = m (full row rank), the column space is all of FmF^m, so every bb yields a consistent system. If AA is square with r=nr = n, it is invertible, and every right-hand side gives exactly one solution.

Eigenvalues and diagonalization

Eigenvalues, eigenvectors and eigenspaces

For a square matrix AA of size n×nn\times n, a nonzero vector vv is an eigenvector with eigenvalue λ\lambda when Av=λvAv=\lambda v. Rewriting this as (A−λI)v=0(A-\lambda I)v=0 shows that λ\lambda is an eigenvalue exactly when the matrix A−λIA-\lambda I has a nontrivial kernel, which happens if and only if det⁡(A−λI)=0\det(A-\lambda I)=0. The function pA(λ)=det⁡(λI−A)p_A(\lambda)=\det(\lambda I-A) is the characteristic polynomial. It is monic of degree nn, so over the complex numbers it has nn roots counted with multiplicity, and these roots are the eigenvalues. Its coefficients encode invariants of AA: the constant term is ±det⁡A\pm\det A, and the coefficient of λn−1\lambda^{n-1} is −tr⁡A-\operatorname{tr}A, so the sum of the eigenvalues equals the trace and their product equals the determinant.

For each eigenvalue λ\lambda, the set of all eigenvectors together with the zero vector forms the null space of A−λIA-\lambda I. This subspace is the eigenspace EλE_\lambda. Its dimension is the geometric multiplicity of λ\lambda. The algebraic multiplicity is the number of times λ\lambda 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 2×22\times2 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 AA is diagonalizable when it is similar to a diagonal matrix, that is, when there exist an invertible matrix PP and a diagonal matrix DD with A=PDP−1A=PDP^{-1}. The columns of PP are then eigenvectors and the diagonal entries of DD are the corresponding eigenvalues. Equivalently, AA is diagonalizable if and only if Cn\mathbb{C}^n (or Rn\mathbb{R}^n, when the eigenvalues are real) has a basis made of eigenvectors of AA. 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 nn eigenvalues are distinct, eigenvectors belonging to different eigenvalues are linearly independent, so AA 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 2×22\times2 rotation through 90 degrees has none, so it has no real diagonalization, although over C\mathbb{C} it diagonalizes with eigenvalues ±i\pm i. 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 QQ such that QTAQ=DQ^{\mathsf T}AQ=D is diagonal. For a complex Hermitian matrix A=A∗A=A^*, all eigenvalues are real, and there exists a unitary matrix UU such that U∗AU=DU^*AU=D. 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 AA 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 A=PDP−1A=PDP^{-1}, then Ak=PDkP−1A^k=PD^kP^{-1} for every integer k≥0k\ge 0, and DkD^k is obtained by raising each diagonal entry to the kkth power. The Fibonacci recurrence is a standard illustration. The matrix (1110)\begin{pmatrix}1&1\\1&0\end{pmatrix} has eigenvalues (1±5)/2(1\pm\sqrt5)/2, and its powers produce closed-form expressions for the Fibonacci numbers.

The same idea solves constant-coefficient linear systems of differential equations y′=Ayy'=Ay. The solution with initial value y(0)y(0) is y(t)=etAy(0)y(t)=e^{tA}y(0), where the matrix exponential is defined by a power series. When AA is diagonalizable, etA=PetDP−1e^{tA}=Pe^{tD}P^{-1}, and etDe^{tD} is the diagonal matrix with entries eλite^{\lambda_i t}. 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 etAe^{tA} is a polynomial in AA of degree less than nn.

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 A=LUA = LU, where LL is unit lower triangular and UU is upper triangular. Once this is available, a system Ax=bAx = b is solved in two triangular stages: forward substitution for Ly=bLy = b, then back substitution for Ux=yUx = y. Computing the factors costs about 23n3\tfrac{2}{3}n^3 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 PA=LUPA = LU with a permutation matrix PP. 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 (0110)\begin{pmatrix}0&1\\1&0\end{pmatrix} has no LU factorization without row exchanges.

QR decomposition

A QR decomposition writes A=QRA = QR, where QQ has orthonormal columns and RR is upper triangular. When AA is square, QQ 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 m×nm \times n matrix AA with m≥nm \ge n and full column rank, the goal is to minimize ∥Ax−b∥2\|Ax - b\|_2. The textbook route solves the normal equations ATAx=ATbA^{\mathsf T}A x = A^{\mathsf T} b, but this squares the condition number, since κ(ATA)=κ(A)2\kappa(A^{\mathsf T}A) = \kappa(A)^2, and accuracy can be lost quickly. Working from A=QRA = QR yields Rx=QTbRx = Q^{\mathsf T} b, 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 AA is Hermitian (symmetric in the real case) and positive definite, then A=LL∗A = LL^* for a lower triangular LL with positive diagonal entries, and this factor is unique. The cost is about 13n3\tfrac{1}{3}n^3 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 LL produces the covariance LL∗LL^*.

Schur decomposition

Every complex square matrix admits a Schur decomposition A=QTQ∗A = QTQ^*, with QQ unitary and TT upper triangular. The eigenvalues appear on the diagonal of TT 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 AA is normal, TT is diagonal, which recovers the spectral theorem. For real matrices, the real Schur form uses a real orthogonal QQ and a block triangular TT whose 2×22\times 2 blocks hold complex conjugate eigenvalue pairs.

Singular value decomposition

Every m×nm \times n complex matrix factors as A=UΣV∗A = U\Sigma V^*, where UU and VV are unitary and Σ\Sigma is diagonal with nonnegative entries σ1≥σ2≥⋯≥0\sigma_1 \ge \sigma_2 \ge \cdots \ge 0, the singular values. These are the square roots of the eigenvalues of A∗AA^*A, and the number of nonzero singular values equals the rank. Geometrically, V∗V^* rotates or reflects the input, Σ\Sigma stretches the coordinate axes by the singular values, and UU rotates or reflects the result. The unit sphere is thus carried onto an ellipsoid whose semi-axes have lengths σi\sigma_i.

Keeping the kk largest singular values and discarding the rest gives the best rank-kk approximation of AA in both the spectral and Frobenius norms, a result known as the Eckart–Young–Mirsky theorem. The spectral-norm error of this truncation equals σk+1\sigma_{k+1}. Storing the truncated factors requires k(m+n+1)k(m+n+1) numbers instead of mnmn, 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 σ1/σr\sigma_1/\sigma_r 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 m×nm\times n matrix AA, the induced (operator) norm is

∥A∥=sup⁡x≠0∥Ax∥∥x∥=sup⁡∥x∥=1∥Ax∥.\|A\| = \sup_{x\neq 0}\frac{\|Ax\|}{\|x\|} = \sup_{\|x\|=1}\|Ax\|.

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 AA lengthens any unit vector. Because it is defined through the supremum, it satisfies ∥Ax∥≤∥A∥ ∥x∥\|Ax\|\le\|A\|\,\|x\| and the submultiplicative rule ∥AB∥≤∥A∥ ∥B∥\|AB\|\le\|A\|\,\|B\|. 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 ∞\infty-norm, which equals the largest absolute row sum; and the 2-norm, which equals the largest singular value of AA. 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 m×nm\times n matrix as a vector of length mnmn. The Frobenius norm is the most important of them:

∥A∥F=∑i,j∣aij∣2=tr⁡(A∗A).\|A\|_F = \sqrt{\sum_{i,j}|a_{ij}|^2} = \sqrt{\operatorname{tr}(A^*A)}.

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

κ(A)=∥A∥ ∥A−1∥.\kappa(A) = \|A\|\,\|A^{-1}\|.

With the 2-norm, κ2(A)=σmax⁡/σmin⁡\kappa_2(A)=\sigma_{\max}/\sigma_{\min}, 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 A(x+δx)=b+δbA(x+\delta x)=b+\delta b, one has

∥δx∥∥x∥≤κ(A) ∥δb∥∥b∥,\frac{\|\delta x\|}{\|x\|}\le \kappa(A)\,\frac{\|\delta b\|}{\|b\|},

so the relative error in the solution can be amplified by up to κ(A)\kappa(A). 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 κ(A)2\kappa(A)^2, is avoided when AA 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 u=2−53≈1.1×10−16u=2^{-53}\approx 1.1\times10^{-16}, 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 κ(A) u\kappa(A)\,u, so about log⁡10κ(A)\log_{10}\kappa(A) decimal digits may be lost.

For this reason numerical analysis asks for backward stability. An algorithm is backward stable if the computed x^\hat x is the exact solution of a nearby problem, (A+ΔA)x^=b(A+\Delta A)\hat x=b, with ∥ΔA∥/∥A∥=O(u)\|\Delta A\|/\|A\|=O(u). 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 A∗AA^{*}A or that use explicit inverses are generally less accurate than factorizations applied directly to AA.

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 kk, the iterate is chosen from the Krylov subspace Kk(A,r0)=span⁡{r0,Ar0,…,Ak−1r0}\mathcal K_k(A,r_0)=\operatorname{span}\{r_0,Ar_0,\dots,A^{k-1}r_0\}, where r0r_0 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 AA 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 kk steps is bounded in terms of the condition number, roughly

∥xk−x∗∥A≤2(κ−1κ+1)k∥x0−x∗∥A,\|x_k-x^*\|_A\le 2\left(\frac{\sqrt{\kappa}-1}{\sqrt{\kappa}+1}\right)^{k}\|x_0-x^*\|_A,

where ∥v∥A2=vTAv\|v\|_A^2=v^{T}Av. Here κ=κ2(A)\kappa=\kappa_2(A) is the ratio of the largest to the smallest eigenvalue. Convergence is therefore fast when κ\kappa is close to 1 and slow when κ\kappa 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 AA.

Algebraic structure

For a fixed size nn and a field FF, the set Mn(F)M_n(F) of all n×nn\times n matrices with entries in FF is a ring under entrywise addition and matrix multiplication. Its zero element is the zero matrix and its identity element is the identity matrix InI_n. Because it is closed under both operations and satisfies the associativity and distributive laws, Mn(F)M_n(F) is a unital associative F-algebra of dimension n2n^2, with the matrix units EijE_{ij} as a basis. This makes it one of the basic examples in ring theory and in abstract-algebra.

Noncommutativity and zero divisors

For n=1n=1 the ring is just FF itself and is commutative. For n≥2n\ge 2 multiplication is never commutative in general. Take A=E12A=E_{12} and B=E21B=E_{21}. Then AB=E11AB=E_{11} and BA=E22BA=E_{22}, which are different. The same example shows that zero divisors exist: E11E22=0E_{11}E_{22}=0 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 n≥2n\ge 2, the ring is never a domain in that case.

Nilpotent elements

A matrix NN is nilpotent if Nk=0N^k=0 for some positive integer kk. For n×nn\times n matrices, Nn=0N^n=0 whenever NN is nilpotent, a consequence of the Cayley–Hamilton theorem. Strictly upper triangular matrices are the standard examples: E12E_{12} satisfies E122=0E_{12}^2=0. Every nonzero nilpotent matrix is a zero divisor, since if Nk=0N^k=0 with kk minimal, then N⋅Nk−1=0N\cdot N^{k-1}=0 with both factors nonzero. The nilpotent matrices do not form a subring with identity, and the ring Mn(F)M_n(F) 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 Mn(F)M_n(F) form the multiplicative group GLn(F)GL_n(F) of invertible matrices, called the general linear group. Its center consists of the scalar matrices λIn\lambda I_n with λ≠0\lambda\ne 0. The determinant is a group homomorphism det⁡:GLn(F)→F×\det: GL_n(F)\to F^\times, and its kernel is the special linear group SLn(F)SL_n(F) of matrices with determinant one, a normal subgroup. Over the real or complex numbers, the orthogonal group O(n)O(n) consists of matrices satisfying ATA=IA^{\mathsf T}A=I, and the unitary group U(n)U(n) consists of matrices satisfying A∗A=IA^{*}A=I. Their intersections with the determinant-one condition give SO(n)SO(n) and SU(n)SU(n). Other important subgroups include the upper triangular matrices in GLn(F)GL_n(F), which form a solvable subgroup, and the permutation matrices, which form a finite subgroup. Over R\mathbb{R} or C\mathbb{C}, these groups are Lie groups, and their tangent spaces at the identity are matrix Lie algebras such as gln\mathfrak{gl}_n and sln\mathfrak{sl}_n.

Representations of groups and algebras

A linear representation of a group GG of degree nn over FF is a group homomorphism ρ:G→GLn(F)\rho: G\to GL_n(F). An algebra representation of an FF-algebra AA is an algebra homomorphism A→Mn(F)A\to M_n(F). Choosing a basis of an nn-dimensional vector space identifies linear operators with matrices, and changing basis replaces ρ\rho by SρS−1S\rho S^{-1} for some invertible SS. 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 tr⁡:Mn(F)→F\operatorname{tr}: M_n(F)\to F, the sum of the diagonal entries, is a linear functional. It satisfies tr⁡(AB)=tr⁡(BA)\operatorname{tr}(AB)=\operatorname{tr}(BA), and as a consequence it is invariant under similarity: tr⁡(S−1AS)=tr⁡(A)\operatorname{tr}(S^{-1}AS)=\operatorname{tr}(A). 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 sln\mathfrak{sl}_n of codimension one, since the commutator of two matrices always has trace zero.

Computational complexity of matrix multiplication

The naive algorithm

Computing C=ABC = AB for two n×nn \times n matrices directly from the definition, where each entry is cij=∑kaikbkjc_{ij} = \sum_k a_{ik} b_{kj}, needs n3n^3 scalar multiplications and n3−n2n^3 - n^2 additions, or 2n3−n22n^3 - n^2 scalar operations in total. The cost therefore grows as O(n3)O(n^3). For rectangular matrices of sizes m×km \times k and k×nk \times n, the count of multiplications is mknmkn. 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 2×22 \times 2 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 T(n)=7T(n/2)+O(n2)T(n) = 7T(n/2) + O(n^2) yields a cost of O(nlog⁡27)≈O(n2.807)O(n^{\log_2 7}) \approx O(n^{2.807}). 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 2×22 \times 2 matrices, although his variant uses fewer additions than Strassen's.

The exponent ω and later improvements

The exponent of matrix multiplication, usually written ω\omega, is the infimum of the exponents cc for which n×nn \times n matrices can be multiplied in O(nc+o(1))O(n^{c+o(1)}) arithmetic operations. Strassen's result gave ω≤log⁡27\omega \le \log_2 7. 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 ω<2.371177\omega < 2.371177 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 ω≥2\omega \ge 2, which holds simply because the output has n2n^2 entries that must each be written. No larger unconditional lower bound on ω\omega is known, and many researchers conjecture that ω=2\omega = 2. Several papers show that the laser method applied to the Coppersmith–Winograd tensor cannot prove ω<2.3078\omega < 2.3078, and more general barriers suggest that a wide class of known techniques cannot reach ω=2\omega = 2. Concrete lower bounds exist for restricted models. For example, computing the product of two n×nn \times n matrices over the binary field requires at least about 2.5n22.5n^2 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 2×22 \times 2 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 O(nω+o(1))O(n^{\omega+o(1)}) operations. The reverse reductions also hold for many of these tasks, so that they have essentially the same exponent as multiplication. Since ω\omega 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 −it/ℏ-i t/\hbar. 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 2×22\times 2 complex matrices, σx\sigma_x, σy\sigma_y, and σz\sigma_z, which together with the identity form a basis for the 2×22\times 2 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 ±1\pm 1. For a spin-½ particle, the spin operator is written as S=ℏ2σ\mathbf{S}=\tfrac{\hbar}{2}\boldsymbol{\sigma}, so the measurable spin components along each axis take the values ±ℏ/2\pm\hbar/2. Rotations of a spin-½ state are generated by the same matrices. The rotation operator exp⁡(−iθ n⋅σ/2)\exp(-i\theta\,\mathbf{n}\cdot\boldsymbol{\sigma}/2) 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 720∘720^\circ turn, a fact noted for spin-½ particles. Ordinary rotations of spatial vectors, by contrast, are represented by 3×33\times 3 orthogonal matrices with determinant one.

The density matrix generalizes the state vector to mixed states. If a system is in state ∣ψi⟩|\psi_i\rangle with probability pip_i, then ρ=∑ipi ∣ψi⟩⟨ψi∣\rho=\sum_i p_i\,|\psi_i\rangle\langle\psi_i|. In general, a density matrix is a Hermitian, positive semi-definite, trace-1 matrix. A pure state gives tr⁡ρ2=1\operatorname{tr}\rho^2=1, whereas for a mixed state the purity tr⁡ρ2\operatorname{tr}\rho^2 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 dd-level system is ρ=I/d\rho=I/d. 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 gμνg_{\mu\nu} has at each point ten independent components, which form a symmetric 4×44\times 4 array. It defines the spacetime interval through ds2=gμν dxμdxνds^2=g_{\mu\nu}\,dx^\mu dx^\nu, using the Einstein summation convention. In flat spacetime in Cartesian coordinates it reduces to the Minkowski metric diag⁡(−1,1,1,1)\operatorname{diag}(-1,1,1,1), a Lorentzian signature that defines the light cone. The inverse matrix gμνg^{\mu\nu} raises indices, and its determinant enters the invariant volume element −g d4x\sqrt{-g}\,d^4x. 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 4×44\times 4 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 X=(X1,…,Xn)TX=(X_1,\dots,X_n)^{\mathsf T} with mean vector μ\mu, the covariance matrix is Σ=E[(X−μ)(X−μ)T]\Sigma=\mathbb E[(X-\mu)(X-\mu)^{\mathsf T}]. Its (i,j)(i,j) entry is Cov⁡(Xi,Xj)\operatorname{Cov}(X_i,X_j), so the diagonal holds the variances. The matrix is symmetric, and for any fixed vector aa the quadratic form aTΣaa^{\mathsf T}\Sigma a equals Var⁡(aTX)\operatorname{Var}(a^{\mathsf T}X), which is nonnegative. Hence Σ\Sigma is positive semidefinite, and it is positive definite when no nonzero linear combination of the components is almost surely constant. An affine transformation Y=AX+bY=AX+b acts on the matrix in a simple way: the covariance of YY is AΣATA\Sigma A^{\mathsf T}. The spectral theorem gives Σ=QΛQT\Sigma=Q\Lambda Q^{\mathsf T} with orthogonal QQ and nonnegative diagonal Λ\Lambda, so the eigenvalues are the variances along the principal axes of the distribution. The density of a multivariate normal distribution is written with Σ−1\Sigma^{-1} and det⁡Σ\det\Sigma.

For a data matrix X∈Rn×pX\in\mathbb R^{n\times p}, subtracting each column's mean yields a centered matrix XcX_c, and the sample covariance matrix is S=1n−1XcTXcS=\frac{1}{n-1}X_c^{\mathsf T}X_c. 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 y=Xβ+εy=X\beta+\varepsilon, where X∈Rn×pX\in\mathbb R^{n\times p} is the design matrix. Ordinary least squares chooses β\beta to minimize ∥y−Xβ∥2\|y-X\beta\|^2. Setting the gradient to zero gives the normal equations

XTX β^=XTy.X^{\mathsf T}X\,\hat\beta = X^{\mathsf T}y.

When XX has full column rank, XTXX^{\mathsf T}X is invertible and β^=(XTX)−1XTy\hat\beta=(X^{\mathsf T}X)^{-1}X^{\mathsf T}y. The matrix XTXX^{\mathsf T}X is the Gram matrix of the columns of XX. The fitted values are y^=Hy\hat y=Hy, where H=X(XTX)−1XTH=X(X^{\mathsf T}X)^{-1}X^{\mathsf T} projects orthogonally onto the column space of XX. If the errors have covariance σ2I\sigma^2 I, then Cov⁡(β^)=σ2(XTX)−1\operatorname{Cov}(\hat\beta)=\sigma^2(X^{\mathsf T}X)^{-1}.

Forming XTXX^{\mathsf T}X explicitly squares the condition number of XX, 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 (XTX+λI)β=XTy(X^{\mathsf T}X+\lambda I)\beta=X^{\mathsf T}y, which remains invertible for λ>0\lambda>0 even when XX is rank-deficient.

Principal component analysis

Principal component analysis finds orthogonal directions along which the centered data have the greatest variance. Eigendecomposing S=VΛVTS=V\Lambda V^{\mathsf T} gives the principal directions as the columns of VV. Each eigenvalue λk\lambda_k is the variance along its direction, and λk/∑jλj\lambda_k/\sum_j\lambda_j is the share of total variance it explains. Projecting the data onto the leading kk directions gives the scores XcVkX_cV_k.

The same result follows from the SVD Xc=UΣVTX_c=U\Sigma V^{\mathsf T}, where λk=σk2/(n−1)\lambda_k=\sigma_k^2/(n-1). This route avoids forming XcTXcX_c^{\mathsf T}X_c and is therefore the preferred numerical method. Keeping only the largest singular values gives the best rank-kk approximation of XcX_c 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 (XTX)−1(X^{\mathsf T}X)^{-1}, design criteria act on this matrix. D-optimality maximizes det⁡(XTX)\det(X^{\mathsf T}X), which minimizes the volume of the confidence ellipsoid for the coefficients. A-optimality minimizes tr⁡((XTX)−1)\operatorname{tr}\bigl((X^{\mathsf T}X)^{-1}\bigr), the sum of the coefficient variances. Orthogonal designs make XTXX^{\mathsf T}X diagonal, so the estimated coefficients are uncorrelated. In multivariate analysis the model becomes Y=XB+EY=XB+E, where YY is an n×mn\times m response matrix. The same design matrix serves every response column, so B^=(XTX)−1XTY\hat B=(X^{\mathsf T}X)^{-1}X^{\mathsf T}Y, 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 x∈Rnx\in\mathbb{R}^n and produces mm outputs, its parameters are a weight matrix W∈Rm×nW\in\mathbb{R}^{m\times n} and a bias vector b∈Rmb\in\mathbb{R}^m, and its output is y=σ(Wx+b)y=\sigma(Wx+b). The function σ\sigma, 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 BB input vectors is stored as the columns of X∈Rn×BX\in\mathbb{R}^{n\times B}, the whole layer becomes one matrix-matrix product, σ(WX+b1T)\sigma(WX+b\mathbf{1}^{\mathsf T}). Multiplying two n×nn\times n matrices takes about 2n32n^3 floating-point operations but reads and writes only about 3n23n^2 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 TT token vectors stored as the rows of X∈RT×dX\in\mathbb{R}^{T\times d}, the model forms Q=XWQQ=XW_Q, K=XWKK=XW_K and V=XWVV=XW_V, where WQ,WK∈Rd×dkW_Q,W_K\in\mathbb{R}^{d\times d_k} and WV∈Rd×dvW_V\in\mathbb{R}^{d\times d_v} are trained. It then computes

Attention⁡(Q,K,V)=softmax⁡ ⁣(QKTdk)V.\operatorname{Attention}(Q,K,V)=\operatorname{softmax}\!\left(\frac{QK^{\mathsf T}}{\sqrt{d_k}}\right)V.

The T×TT\times T matrix QKTQK^{\mathsf T} 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 E∈RV×dE\in\mathbb{R}^{V\times d}, where VV is the vocabulary size and each row is the learned vector for one token. Multiplying a one-hot row vector by EE 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 z=Wx+bz=Wx+b, a=σ(z)a=\sigma(z) and a scalar loss LL, and suppose the gradient δ=∂L/∂z\delta=\partial L/\partial z has already been obtained from the layers above by the backpropagation procedure. The chain rule gives ∂L/∂W=δxT\partial L/\partial W=\delta x^{\mathsf T}, an outer product with the same shape as WW, and ∂L/∂b=δ\partial L/\partial b=\delta. The gradient passed to the previous layer is ∂L/∂x=WTδ\partial L/\partial x=W^{\mathsf T}\delta, so the transpose of each weight matrix appears in the backward pass. Here δ\delta is computed from the gradient with respect to aa by an entrywise product with σ′(z)\sigma'(z). For a batch, the weight gradient becomes a single product of the matrix of δ\delta vectors with XTX^{\mathsf T}, averaged over the batch.

The same objects describe the geometry of optimization. For a vector-valued function f:Rn→Rmf:\mathbb{R}^n\to\mathbb{R}^m, the Jacobian J∈Rm×nJ\in\mathbb{R}^{m\times n} has entries Jij=∂fi/∂xjJ_{ij}=\partial f_i/\partial x_j, and the chain rule for composed layers becomes a product of Jacobians. For a scalar loss ff, the Hessian Hij=∂2f/∂xi∂xjH_{ij}=\partial^2 f/\partial x_i\partial x_j 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 nn parameters has an n×nn\times n 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 kk with dimensions n1,…,nkn_1,\ldots,n_k can be modeled as a function from the product of index sets [n1]×⋯×[nk][n_1]\times\cdots\times[n_k] into a field K\mathbb{K}, so every entry is addressed by a kk-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 m+n−2m+n-2, where mm and nn 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 n1×n2n_1\times n_2 matrix and an m1×m2m_1\times m_2 matrix, it produces an (n1m1)×(n2m2)(n_1m_1)\times(n_2m_2) 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 Cn\mathbb{C}^n are represented by finite matrices. Once an orthonormal basis is chosen, the operator acts by the infinite analogue of the usual sum, yi=∑jaijxjy_i=\sum_j a_{ij}x_j, 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 1/(i+j+1)1/(i+j+1), acts as a bounded operator on ℓ2\ell^2, but it is not a compact operator. Its operator norm on ℓp\ell^p is known in closed form, π/sin⁡(π/p)\pi/\sin(\pi/p) for 1<p<∞1<p<\infty. 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 q=pnq=p^n, there is a unique finite field Fq\mathbb{F}_q of order qq, and the invertible n×nn\times n matrices over it form the general linear group GL(n,q)\mathrm{GL}(n,q), 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 GG; the set of all such codewords forms a subspace of the ambient vector space, and when the rows of GG are linearly independent, GG 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 [I∣B][I\mid B] generates a maximum distance separable code precisely when BB 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

  1. Sparse Matrices — GSL 2.8 documentationgnu.org
  2. Optimizing Sparse Matrix Multiplications for Graph Neural Networksarxiv.org
  3. Optimizing Sparse Matrix-Vector Multiplication on Emerging Many-Core Architecturesarxiv.org
  4. Sparse Matrix Formats — NVPL SPARSEdocs.nvidia.com
  5. Sparse Storage Formatsintel.com
  6. Hermitian matrixen.wikipedia.org
  7. Skew-Hermitian matrixen.wikipedia.org
  8. Matrices and determinants - MacTutor History of Mathematicsmathshistory.st-andrews.ac.uk
  9. Linear Algebra - Determinantstheory.stanford.edu
  10. 12 PREFACE CHAPTER I DETERMINANTSpublish.illinois.edu
  11. 8 DETERMINANTS.sayahna.org
  12. Determinantenlink.springer.com
  13. DETERMINANTS 1. Introduction In these notes we discuss ...sites.math.washington.edu
  14. Leibniz formula for determinantsen.wikipedia.org
  15. Cofactor Expansionstextbooks.math.gatech.edu
  16. An Introduction to Algebraic Combinatoricsarxiv.org
  17. Eigenvalue and Eigenvector Calculatorpearson.com
  18. Diagonalizationtextbooks.math.gatech.edu
  19. Matrix Reference Manual: Eigenvaluesee.ic.ac.uk
  20. 5.4: Diagonalization - Mathematics LibreTextsmath.libretexts.org
  21. EIG-0050: Diagonalizable Matrices and Multiplicity - Ximeraximera.osu.edu
  22. Recitation 8. November 5web.mit.edu
  23. The Spectral Theoremsites.millersville.edu
  24. VII.D. THE SPECTRAL THEOREM 253 VII.D. The spectral theoremmath.wustl.edu
  25. Lecture 3.26. Hermitian, unitary and normal matrices A. Eremenko March 10, 2023math.purdue.edu
  26. SPECTRAL THEOREM Orthogonal Diagonalizablemath.jhu.edu
  27. Lecture 28: The Spectral Theorem 28 The Spectral Theorem 28.1ocw.mit.edu
  28. Math 4571 (Advanced Linear Algebra) Lecture #28web.northeastern.edu
  29. 10.3: Solution by the Matrix Exponential - Mathematics LibreTextsmath.libretexts.org
  30. Matrix exponentialen.wikipedia.org
  31. Spectral Methods in Complex Systemsarxiv.org
  32. Matrix normen.wikipedia.org
  33. 4.2: Matrix Norms - Engineering LibreTextseng.libretexts.org
  34. Lectures on Randomized Numerical Linear Algebraarxiv.org
  35. Linear Algebra, Part 5: Matrix norms (Mathematica)cfm.brown.edu
  36. CS 3220: The condition number of a matrix Instructor: Anil Damle Disclaimercs.cornell.edu
  37. NORTH- HOLLAND Condition Numbers and Their Condition Numbers Desmond J. Highamwebhomes.maths.ed.ac.uk
  38. Perturbation Theory for the Solution of Systems of ... - DTICapps.dtic.mil
  39. MATH 3795 Lecture 6. Sensitivity of the Solution of a Linear Systemwww2.math.uconn.edu
  40. Condition number for finite element discretisation of nonlocal PDE systems with applications to biologyarxiv.org
  41. Krylov-space-based quasi-newton preconditioner for full-wavefield inversionimage-ppubs.uspto.gov
  42. Applications of Conjugate Gradient in Bayesian computationarxiv.org
  43. Krylov subspace methods and CG: OxRSE Trainingtrain.rse.ox.ac.uk
  44. Characterization of the equivalence of robustification and regularization in linear and matrix regressionarxiv.org
  45. CONJUGATE GRADIENT METHODS We shall present ...math.uci.edu
  46. Krylov subspace methods and preconditioners L. Grigori ALPINESwho.rocq.inria.fr
  47. Zero divisoren.wikipedia.org
  48. January 2, 2024 Rings Table of Contents 1. Definitions and constructions 1people.math.osu.edu
  49. graphsearch.epfl.chgraphsearch.epfl.ch
  50. Strassen's 2x2 matrix multiplication algorithm: A conceptual perspectiveresearchgate.net
  51. Strassen Formulas -- from Wolfram MathWorldmathworld.wolfram.com
  52. Tiled Algorithms for Matrix Computations on Multicore Architecturesarxiv.org
  53. GEOMETRY AND THE COMPLEXITY OF MATRIX MULTIPLICATION J.M. LANDSBERGpeople.tamu.edu
  54. arxiv.orgarxiv.org
  55. An overview of the recent progress on matrix multiplicationpeople.csail.mit.edu
  56. New Bounds for Matrix Multiplication: from Alpha to Omegaarxiv.org
  57. par.nsf.govpar.nsf.gov
  58. New Breakthrough Brings Matrix Multiplication Closer to Idealquantamagazine.org
  59. More Asymmetry Yields Faster Matrix Multiplicationarxiv.org
  60. Matrix Multiplication Exponent Improved to 2.371177emergentmind.com
  61. Lower Bounds for Conjunctive Query Evaluationarxiv.org
  62. Tensor Rank and Complexityarxiv.org
  63. Fangcheng (mathematics) — Grokipediagrokipedia.com
  64. Fangcheng (mathematics)en.wikipedia.org
  65. The Nine Chapters on the Mathematical Art — Grokipediagrokipedia.com
  66. The Nine Chapters on the Mathematical Arten-academic.com
  67. Fangcheng Procedure in the Nine Chapters on the Mathematical Arts Revisitedretrospectjournal.com
  68. Gottfried Wilhelm Leibnizen.wikipedia.org
  69. Using Cramer’s Rule to Solve a System of Two Equations in Two Variablescourses.lumenlearning.com
  70. Cayley, Sylvester, and Early Matrix Theoryresearchgate.net
  71. Algebraic generality vs arithmetic generality in the controversy between C. Jordan and L. Kronecker (1874)arxiv.org
  72. Cayley, Sylvester, and Early Matrix Theory Nicholas J. Higham January 2008webhomes.maths.ed.ac.uk
  73. Cayley, Sylvester, and Early Matrix Theory Nick Higham School of Mathematicspdfs.semanticscholar.org
  74. A Brief History of Linear Algebra and Matrix Theoryconvexoptimization.com
  75. 1.2: Matrix Mechanics - Chemistry LibreTextschem.libretexts.org
  76. Perturbing a subject's contextualization of a proposition about an item considered in a quantum representation by altering the itemimage-ppubs.uspto.gov
  77. Quantum Information Processing: An Essential Primerarxiv.org
  78. GENERAL I ARTICLE Heisenberg, Matrix Mechanics, and the Uncertainty Principleias.ac.in
  79. From Heisenberg and Schr\"odinger to the P vs. NP Problemarxiv.org
  80. Density matrixen.wikipedia.org
  81. Relativistic Quantum Dynamics: A non-traditional perspective on space, time, particles, fields, and action-at-a-distancearxiv.org
  82. Pauli Matrix - an overviewsciencedirect.com
  83. 9.3: Adjacency Matrices - Engineering LibreTextseng.libretexts.org
  84. Algebraic and geometric methods in enumerative combinatoricsarxiv.org
  85. Matrix Powersdatafireball.com
  86. What is a Markov Chain? - dida.dodida.do
  87. Notes on Randomized Algorithmsarxiv.org
  88. Stationary Distributions of Markov Chainsbrilliant.org
  89. Markov Chain Monte Carlo Methods in Quantum Field Theories: A Modern Primerarxiv.org
  90. PageRank: Standing on the shoulders of giantsarxiv.org
  91. Input-Output Analysis and Leontief Modelsmaseconomics.com
  92. 7.2 Application to economics: Leontief Modelmath.ksu.edu
  93. AI HL Walks and Adjacency Matrices Notes - IB Demystifiedibdemystified.com
  94. The arithmetic complexity of tensor contractionsarxiv.org
  95. FLAASH: Flexible Accelerator Architecture for Sparse High-Order Tensor Contractionarxiv.org
  96. Bounded Linear Operators on Hilbert Spaceslink.springer.com
  97. The Coding Theory Workbook A companion to EE 567 Version 1.1 Spring 2016community.wvu.edu
  98. Tensor Algebra and its Applications to Data Science and Statisticsarxiv.org
  99. Tensor Product - an overviewsciencedirect.com
  100. Infinite dimensional Hilbert tensors on spaces of analytic functionsarxiv.org
  101. On the Hilbert matrix operator: a brief surveyarxiv.org
  102. Chapter 5 Operators on Hilbert space Paragraph ex- panded in version of Dec. 18web.math.ku.dk
  103. Superregular Matrices over Finite Fieldsmdpi.com
  104. Finite field matrix channels for network codingarxiv.org