Matrix

A matrix represents a linear map after bases have been chosen for its domain and codomain.

A matrix with the same number of rows and columns represents an endomorphism of a finite-dimensional vector space after choosing a basis. Square matrices support trace, determinant, powers and the matrix exponential.

For $A=P+iQ$ with real matrices $P,Q$, the same linear map viewed over the reals has block matrix $\left(\begin{array}{cc}P& -Q\\ Q& P\end{array}\right)$ in grouped real/imaginary coordinates. Interleaved coordinates merely permute the basis. Its complexification splits into the matrices $A$ and $\overline{A}$, giving the realification determinant identity.

The realification of a complex matrix has real determinant $|{\det }_{\mathbb{C}}A{|}^2$. Indeed the invertible complex coordinate change $(x,y)\mapsto (x+iy,x-iy)$ conjugates its complexified block matrix to $\mathrm{diag}(A,\overline{A})$. Taking determinants gives the identity, including singular matrices.

For a real matrix $M$, the entrywise L1 norm is ${\sum }_{r,s}|M_{rs}|$, the L1 norm of its vector of entries. It is the usual penalty in the all-entry convention for the Graphical Lasso.

Applying a scalar function separately to each matrix entry: $(f[X]{)}_{ij}=f(X_{ij})$. This differs from spectral matrix functional calculus. In particular, $\arcsin [Y]$ in Gaussian hyperplane rounding is entrywise, and its contribution to a matrix trace can be restricted to selected blocks by the support of the other matrix.

The matrix with entries $(P\circ Q{)}_{ij}=P_{ij}{Q}_{ij}$. It differs from ordinary matrix multiplication. The Schur product theorem states that it preserves positive semidefiniteness when both factors are positive semidefinite matrices.

For integer $k\ge 1$, the entrywise power has entries $X_{ij}^k$ and equals the repeated Hadamard product. The zero power is the all-ones matrix, even at zero entries, because it represents the constant function one. Every nonnegative integer Hadamard power of a positive semidefinite matrix is positive semidefinite by the Schur product theorem. It is not an ordinary matrix power.

The Hermite normal form is a canonical triangular form for an integer matrix under integer elementary row operations or, in the column convention, column operations. In the row convention for a nonsingular rank-two matrix, positive diagonal entries and reduction of the upper-right entry modulo the lower diagonal entry give the row Hermite normal form in rank two.

The row lattice of an integer matrix with $m$ rows is the set of their integer linear combinations. It is an Euclidean lattice in its real span, since it is contained in the discrete set ${\mathbb{Z}}^n$ and spans that real vector space. For a nonsingular two-by-two integer matrix, the row Hermite normal form in rank two gives a canonical basis and proves that its index in ${\mathbb{Z}}^2$ is the absolute value of its determinant.

For a finite-index subgroup $L\le {\mathbb{Z}}^2$, its projection to the first coordinate is $a\mathbb{Z}$ and its intersection with the second axis is $\{0\}\times d\mathbb{Z}$, with $a,d>0$. Choose $(a,b)\in L$, reducing $b$ modulo $d$. Together with $(0,d)$ it is a basis of this row lattice: subtracting a multiple of $(a,b)$ from any vector leaves a vector on the second axis. These parameters are unique, and reduction of the two coordinates shows $[{\mathbb{Z}}^2:L]=ad$. Consequently an integral matrix of positive determinant $n$ has a unique representative of this form under left multiplication by $S{L}_2(\mathbb{Z})$, with $ad=n$. This proves the lattice facts underlying determinant-n matrix representatives for Hecke operators.

A square real matrix is doubly stochastic if its entries are nonnegative and every row and column sums to $1$. Its positive-entry support satisfies the condition of the Hall marriage theorem: for a row subset $S$, $|S|\le |N(S)|$ by summing column capacities. Consequently its support contains a permutation matrix.

Every doubly stochastic matrix is a convex combination of permutation matrices. Equivalently, the extreme points of the doubly stochastic convex polytope are exactly the permutation matrices. The extreme-point assertion follows from an alternating-cycle perturbation of a doubly stochastic matrix; the convex-hull assertion follows because a bounded finite-dimensional polytope is the convex hull of its vertices. Permutation matrices are extreme since their zero entries force the same zeros in every convex decomposition.

For a doubly stochastic matrix, the Hall marriage theorem supplies a perfect matching in its positive-entry support. Subtract the smallest matched entry times the corresponding permutation matrix. The residual has equal row and column sums and smaller support unless it vanishes. Repeating gives a convex combination of permutation matrices. With $r$ initially positive entries, there are at most $r-n+1$ terms, since a positive-mass residual has at least $n$ positive entries. Elementary augmenting-path matching gives $O(n^5)$ arithmetic operations.

For a doubly stochastic matrix with a fractional entry, form the row-column bipartite graph of entries strictly between zero and one. Every incident vertex has degree at least two, so there is an even cycle. A matrix supported on that cycle with alternating entries $+1,-1$ has zero row and column sums. A sufficiently small positive multiple can be both added and subtracted while preserving entry bounds. The original matrix is then the midpoint of two distinct doubly stochastic matrices, so it is not an extreme point.

A rational matrix is a matrix whose entries are rational numbers. Multiplying by a common denominator produces an integer matrix and preserves its homogeneous solution set.

A real matrix is nonnegative when every entry is nonnegative. This entrywise condition differs from being a positive semidefinite matrix: the symmetric matrix $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ is nonnegative but has eigenvalues $1$ and $-1$.

A square nonnegative matrix $A$ is irreducible if for each pair $(i,j)$ there is an integer $k\ge 0$ with $(A^k{)}_{ij}>0$. This says that every index can reach every other through positive entries. The Perron–Frobenius theorem then gives a positive leading eigenvector and an algebraically simple eigenvalue. Irreducibility alone permits other eigenvalues of the same modulus: the cyclic permutation matrix $\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right)$ has eigenvalues $1,-1$.

A square nonnegative matrix $A$ is primitive if some positive integer power $A^k$ has strictly positive entries. It is therefore an irreducible nonnegative matrix. The Perron–Frobenius theorem gives a leading eigenvalue whose modulus is strictly larger than that of every other eigenvalue. Every strictly positive matrix is primitive; the two-cycle permutation matrix is irreducible but not primitive.

The strictly positive case states that a real square matrix $W$ with $W_{ij}>0$ has a positive simple eigenvalue $\lambda$ and positive left and right eigenvectors, with all other eigenvalues strictly smaller in modulus. The Brouwer fixed-point theorem applied to $v\mapsto Wv/(1^{T}Wv)$ on the nonnegative unit simplex gives $v>0$ and $Wv=\lambda v$. For another eigenvector $z$, maximize $|z_i|/v_i$; the triangle inequality gives $|\mu |\le \lambda$. Equality forces every modulus ratio and complex argument to agree because every entry is positive, so $z$ is proportional to $v$ and $\mu =\lambda$. Apply the same argument to $W^T$ for a positive left eigenvector; its positive pairing with $v$ rules out a generalized eigenvector at $\lambda$, establishing algebraic simplicity. For merely nonnegative matrices a nonnegative leading eigenvector exists. An irreducible nonnegative matrix has a positive leading eigenvector and simple Perron eigenvalue; a primitive nonnegative matrix has the strict modulus gap.

The all-ones matrix $J=\mathbf{e}{\mathbf{e}}^T$ has every entry equal to one, where $\mathbf{e}=(1,\dots ,1{)}^T$. On ${\mathbb{R}}^n$, the matrix $J/n$ is the orthogonal projection matrix onto $\mathrm{span}\{\mathbf{e}\}$.

The column space of a matrix $A$ is the linear span of its columns. It is the image of a linear map represented by $A$.

A binary matrix is a matrix all of whose entries belong to $\{0,1\}$.

A submatrix is obtained from a matrix by retaining selected rows and selected columns. A principal submatrix of a square matrix retains the same index set for its rows and columns.

A matrix minor is the determinant of a square submatrix.

A principal minor is the determinant of a square submatrix selected using the same index set for rows and columns. For a three-by-three matrix, the coefficient of $\lambda$ in its monic characteristic polynomial is the sum of its three principal minors of order two.

The entrywise maximum norm is the largest absolute value of a matrix entry. For compatible vectors $x$ and $y$,

A tridiagonal matrix has zero entries outside its main diagonal and the two adjacent diagonals. Linear systems with a nonsingular tridiagonal coefficient matrix can be solved in linear time by the Thomas algorithm.

A block matrix partitions its rows and columns into rectangular submatrices called blocks, allowing a matrix calculation to be expressed in terms of those blocks.

A block matrix is block diagonal if all off-diagonal blocks vanish. It represents independent actions on a direct sum of vector spaces. Its determinant is the product of the diagonal-block determinants.

A block tridiagonal matrix has nonzero blocks only on its main block diagonal and the two adjacent block diagonals. It is the block analogue of a tridiagonal matrix.

A square matrix is diagonally dominant when the absolute value of every diagonal entry is at least the sum of the absolute values of the other entries in its row.

A matrix is strictly diagonally dominant when every diagonal-dominance inequality is strict. A real symmetric strictly diagonally dominant matrix with positive diagonal is positive definite by the Gershgorin circle theorem.

The matrix transpose interchanges rows and columns: $(A^T{)}_{ij}=A_{ji}$. On a fixed matrix space, $A\mapsto A^T$ is the transposition map, a linear map that preserves the trace norm but is not completely positive in dimensions greater than one.

For a positive-definite Hermitian matrix with spectral decomposition $A=U\mathrm{diag}({\lambda }_j)U^{\ast }$, the matrix logarithm is $\log A=U\mathrm{diag}(\log {\lambda }_j)U^{\ast }$. More generally it is a branch of the inverse of the matrix exponential when such a branch exists.

On complex symmetric matrices with positive-definite real part, the determinant has a nonzero analytic square root normalized positively on real positive matrices. It is continued within this accretive domain. For $A=G+iB$, put $C=G^{-1/2}B{G}^{-1/2}$ with real eigenvalues $b_j$; then $d(A)=\sqrt{\det G}{\prod }_j\sqrt{1+i{b}_j}$, using positive-real-part roots for each factor. The principal scalar square root of the product determinant need not equal this continued root: accumulated determinant arguments can cross the scalar branch cut. The principal matrix logarithm instead tracks all factors consistently.

For a positive-definite Hermitian operator $A={\sum }_j{t}_j|u_j⟩⟨u_j|$ and a unit vector $v$, the weights $|⟨v|u_j⟩{|}^2$ form a probability distribution. Scalar logarithmic concavity bounds their average of $\log t_j$ by the logarithm of their average of $t_j$. Positive semidefinite operators follow by a limiting convention. Using the eigenbasis of a density operator $\rho$ gives $S(\rho \Vert \sigma )\ge D(r\Vert q)$, where $r$ is the spectrum of $\rho$ and $q$ the diagonal of $\sigma$ in that basis. This yields nonnegativity of quantum relative entropy without commutativity.

An invertible complex Jordan block $\lambda I+N$, with $N^s=0$, has logarithm $\ell I+{\sum }_{k=1}^{s-1}(-1{)}^{k+1}(N/\lambda {)}^k/k$, where $e^{\ell }=\lambda$. Applying this construction blockwise and conjugating back proves surjectivity of the matrix exponential on the complex general linear group. There is no globally single-valued continuous choice of logarithm.

For positive-definite Hermitian matrices $A,B$, Klein's inequality giveswith equality exactly when $A=B$. To prove it, let $a_i,b_j$ be their eigenvalues and $u_i,v_j$ their orthonormal eigenvectors. The weights $w_{ij}=|⟨u_i,v_j⟩{|}^2$ have row and column sums one. The difference between the two sides isby the scalar logarithm inequality $\ln t\le t-1$. Equality requires $a_i=b_j$ whenever $w_{ij}>0$, implying $A=B$. Limits extend the result to positive semidefinite matrices with the appropriate support condition. Applying it to trace-one matrices proves nonnegativity of quantum relative entropy.

For a square matrix $A$ and a nonnegative integer $k$, the matrix power is the repeated productwith $A^0=I$.

A matrix element $A_{ij}$ is the entry in row $i$ and column $j$ of a matrix $A$.

A sparse matrix has few nonzero matrix elements in each row or column compared with its dimension. Algorithms normally require an efficient oracle that lists the positions and values of those entries.

The matrix unit $E_{ij}$ has entry one in row $i$, column $j$, and zero in every other position. The matrix units form the standard basis of the vector space of matrices of a fixed size.

The rank of a matrix is the dimension of its column space, equivalently the dimension of its row space.

Two rectangular matrices are related by invertible left and right multiplication exactly when their ranks agree. The rank-$r$ orbit in ${\mathrm{Mat}}_{b\times a}(k)$ has dimension $r(a+b-r)$: choose its image in a Grassmannian, then a surjective map to that image. These are the representation orbits of the one-arrow quiver.

The image of the linear map $A+B$ is contained in the sum of the images of $A$ and $B$. Since the dimension of a vector space of this sum is at most the sum of their dimensions, matrix rank is subadditive. Iteration shows that a sum of $r$ matrices of matrix rank at most one has matrix rank at most $r$, over any field.

An $m\times n$ matrix has full column rank when its rank is $n$, equivalently when its columns are linearly independent vectors.

An $m\times n$ matrix has full row rank when its rank is $m$, equivalently when its rows are linearly independent vectors.

The identity matrix has ones on its main diagonal and zeros elsewhere, and satisfies $IA=AI=A$ whenever the products are defined.

A nonzero matrix has rank one exactly when it can be written as an outer product $u{v}^T$.

An upper bidiagonal matrix can have nonzero entries only on its main diagonal and first superdiagonal.

Matrix multiplication represents composition of linear maps. Its entries are $(AB{)}_{ij}={\sum }_k{A}_{ik}{B}_{kj}$.

The outer product of column vectors $u$ and $v$ is the rank-at-most-one matrix $u{v}^T$, whose $(i,j)$ entry is $u_i{v}_j$.

An upper Hessenberg matrix has zero entries below its first subdiagonal: $a_{ij}=0$ whenever $i>j+1$.

A permutation matrix has exactly one entry equal to one in each row and column and zeros elsewhere. Left or right multiplication permutes coordinates, and $P^{-1}=P^T$.

A signed permutation matrix has exactly one nonzero entry in each row and column, and every nonzero entry is $1$ or $-1$. It is a product of a diagonal sign matrix and a permutation matrix.

Given ordered bases $\mathcal{B}=(v_j)$ and $\mathcal{C}=(w_i)$, the matrix $[T{]}_{\mathcal{C}\leftarrow \mathcal{B}}$ has column $j$ equal to the $\mathcal{C}$-coordinate vector of $T(v_j)$.

For matrices $A$ and $B$, the Kronecker product $A\otimes B$ replaces each entry $a_{ij}$ by the block $a_{ij}B$. It satisfieswhenever the products are defined.

The Kronecker sum of square matrices combines their Kronecker products with identity matrices. If $Ax=\lambda x$ and $By=\mu y$, then $x\otimes y$ is an eigenvector with eigenvalue $\lambda +\mu$. Tensor-product spatial grids therefore turn separated coordinate Laplacians into a Kronecker sum. Two Hermitian matrices give a Hermitian Kronecker sum, allowing an energy method without computing every eigenvector.