Positive-definite matrix

A real symmetric matrix $A$ is positive definite whenfor every nonzero real vector $x$. It therefore defines the inner product $⟨x,y{⟩}_A=x^{T}Ay$ and is invertible.

Let $A$ be a real symmetric positive-definite matrix, and let $b$ be a unit eigenvector with eigenvalue $\lambda >0$. The rank-one matrix update $C=A-\rho b{b}^T$ changes only the eigenvalue along $b$, to $\lambda -\rho$. Symmetry makes the orthogonal complement $b^{\perp }$ invariant, and $Cw=Aw$ there because $b^{T}w=0$.

In detail, write $x=tb+w$ with $w\perp b$. ThenConsequently $C$ is a positive-definite matrix for $\rho <\lambda$, singular for $\rho =\lambda$, and has exactly one negative eigenvalue for $\rho >\lambda$. In dimension at least two the last case is indefinite. In dimension one it is negative definite instead: there is no nonzero orthogonal-complement direction. The distinction matters when classifying a stationary point of a quadratic form.

Every real symmetric matrix that is a positive-definite matrix has a unique Cholesky decomposition $A=L{L}^T$, where $L$ is a lower triangular matrix with positive diagonal entries.^[ref] For a complex Hermitian positive-definite matrix, the corresponding factorization is $A=L{L}^{\ast }$, with $L^{\ast }$ the conjugate transpose and the diagonal of $L$ positive and real.^[ref] The factorization turns a linear system into two triangular systems.

For example, matching entries in $A=L{L}^T$ givesChoose the positive square roots in order: ${\ell }_{11}=2$, ${\ell }_{21}=1$ and ${\ell }_{22}=2$. ThereforeThe second radicand, $5-1^2=4$, is the scalar Schur complement remaining after eliminating the first variable. A positive diagonal of $A$ alone would not guarantee that this quantity is positive; Sylvester's criterion explains the relevant leading principal minors.

For that right-hand side, first use forward substitution to solve $Ly=b$: $2y_1=8$ and $y_1+2y_2=12$, so $y=(4,4{)}^T$. Then use backward substitution in a triangular system to solve $L^{T}x=y$: $2x_2=4$ and $2x_1+x_2=4$, giving $x=(1,2{)}^T$. No matrix inverse is required. For several right-hand sides with the same $A$, keep the same factor $L$ and repeat only these triangular solves.

For a real symmetric positive-definite matrix, the lower triangular matrix $C$ with positive diagonal in its Cholesky decomposition is its lower Cholesky factor; $C^T$ is the corresponding upper factor. If a full-column-rank matrix $B$ has a reduced QR decomposition $B=QR$ with positive diagonal of $R$, then $B^{T}B=R^{T}R$, so $R$ is the upper Cholesky factor of $B^{T}B$.

For any real vector $u$, a Cholesky decomposition gives the quadratic form identitySince $L$ is an invertible matrix, this squared Euclidean norm is positive whenever $u\ne 0$. The factorization thus certifies positive definiteness and gives coordinates in which the quadratic form is a sum of ordinary squares. For the matrix above,The level set $u^{T}Au=1$ is an ellipse; the linear map $z=L^{T}u$ sends it to the unit circle. The points $u=(1/2,0{)}^T$ and $u=(-1/4,1/2{)}^T$ go to $(1,0{)}^T$ and $(0,1{)}^T$, respectively.

The same factor works in the reverse direction for Gaussian random vectors. If $Z$ has independent unit-variance, zero-mean Gaussian random variables as coordinates, $X=LZ$ has covariance matrix $L{L}^T=A$. In this example $X_1=2Z_1$ and $X_2=Z_1+2Z_2$: their variances are $4$ and $5$, while their covariance is $2$. This is a concrete way to generate specified correlations from independent draws.

A triangular factor is not generally a square root of a matrix in the sense $B^2=A$. Here $L^2=\left(\begin{array}{cc}4& 0\\ 4& 4\end{array}\right)\ne A$. The Cholesky decomposition uses the product with the transpose, which is also what makes the quadratic form a squared Euclidean norm.

André-Louis Cholesky developed his calculation in the setting of geodetic adjustment: measured angles and lengths must satisfy geometric relations, while corrections should be small. The manuscript reproduced in Claude Brezinski's study is titled Sur la résolution numérique des systèmes d’équations linéaires and ends with the date 2 December 1910 at Vincennes. The manuscript reports a 56-equation calculation adjusting altitudes in an Algerian triangulation network. Its date establishes when this written account existed, rather than an exact invention date.^[ref]

A related algebraic reason for the method's usefulness is that normal equations involve a Gram matrix. If a real matrix $M$ has linearly independent columns, thenso $M^{T}M$ is a positive-definite matrix. That gives the structure needed by a Cholesky decomposition. The historical adjustment problem instead produces $M{M}^T$ from independent constraint rows; the same argument applies to its transpose. In numerical least squares, explicitly forming normal equations squares the condition number of a full-column-rank design matrix; a QR decomposition can therefore be preferable for accuracy. Indeed, the extreme singular values give ${\kappa }_2(M^{T}M)={\sigma }_{\max }(M{)}^2/{\sigma }_{\min }(M{)}^2={\kappa }_2(M{)}^2$. The factorization remains useful when a positive-definite matrix is already the natural input.

Given a Cholesky decomposition $A=L{L}^T$, a rank-one Cholesky update computes a triangular factor of $A+x{x}^T$ in $O(n^2)$ operations without refactorizing the matrix from scratch.

A Hermitian matrix $A$ is a positive-definite matrix exactly when its leading principal minorsare all positive. The leading principal minor uses the first $k$ rows and the first $k$ columns in the same ordering. For the two-by-two Cholesky decomposition example, ${\Delta }_1=4$ and ${\Delta }_2=4\cdot 5-2^2=16$, so the criterion proves positive definiteness without calculating eigenvalues.

The successive pivot elements before taking square roots are ${\Delta }_k/{\Delta }_{k-1}$, with ${\Delta }_0=1$. Here they are $4$ and $16/4=4$. In general, a leading triangular matrix factor has determinant equal to the product of its diagonal entries, soConversely, positive leading principal minors make each successive Schur complement pivot element positive, allowing the Cholesky decomposition to be constructed. The identity $u^{T}Au=\Vert L^{T}u{\Vert }_2^2$ then proves positive definiteness; for complex matrices, replace the transposes by conjugate transposes. This gives a short inductive proof of the criterion.

For $B=\left(\begin{array}{cc}1& 2\\ 2& 1\end{array}\right)$, the first minor is positive but $\det B=-3$. The second Cholesky radicand would be $1-2^2=-3$, and $v=(1,-1{)}^T$ directly gives $v^{T}Bv=-2<0$. Thus positive diagonal entries are insufficient. Replacing “positive” by “nonnegative” in just the leading-minor test is also insufficient for positive semidefiniteness: $\mathrm{diag}(0,-1)$ has leading minors $0,0$, but its quadratic form is negative on $(0,1{)}^T$.

The condition number of a problem measures how strongly relative perturbations of its input can amplify relative changes in its output. For an invertible matrix and a chosen operator norm, $\kappa (A)=\Vert A\Vert \Vert A^{-1}\Vert$.

For a real symmetric positive-definite matrix,It measures the sensitivity of the linear system and controls convergence bounds for iterative solvers.

A complex matrix $A$ is Hermitian positive definite when $A^{\ast }=A$ and $z^{\ast }Az>0$ for every nonzero complex vector $z$.

A Toeplitz matrix is constant along each diagonal, so its entries have the form $T_{nm}=t_{n-m}$.

An $m\times m$ symmetric tridiagonal Toeplitz matrix has one constant diagonal $\alpha$ and equal constant subdiagonal and superdiagonal $\beta$. Its eigenvectors are the discrete sine transform vectors $q_j^{(k)}=\sin (jk\pi /(m+1))$, with eigenvalues $\alpha +2\beta \cos (k\pi /(m+1))$.

An $M\times M$ Toeplitz antisymmetric tridiagonal matrix with diagonal $a$, superdiagonal $b$, and subdiagonal $-b$ has eigenvaluesAll such matrices share an orthonormal eigenbasis after the same diagonal unitary change from the discrete sine basis.