Matrix decomposition 253873 224843143 2008-07-10T17:44:17Z Giftlite 37986 /* Eigendecomposition (also called spectral decomposition) */ +. In the [[mathematics | mathematical]] discipline of [[linear algebra]], a '''matrix decomposition''' is a [[factorization]] of a [[matrix (math)|matrix]] into some [[canonical form]]. There are many different matrix decompositions; each finds use among a particular class of problems. == Example == In [[numerical analysis]], different decompositions are used to implement efficient matrix [[algorithm]]s. For instance, when solving a [[system of linear equations]] <math>Ax=b</math>, the matrix ''A'' can be decomposed via the [[LU decomposition]]. The LU decomposition factorizes a matrix into a [[lower triangular matrix]] ''L'' and an [[upper triangular matrix]] ''U''. The systems <math>L(Ux)=b</math> and <math>Ux=L^{-1}b</math> are much easier to solve than the original. == Decompositions related to solving [[System of linear equations|systems of linear equations]] == === [[LU decomposition]] === *Applicable to: [[square matrix]] ''A'' *Decomposition: <math>A=LU</math>, where ''L'' is [[triangular matrix|lower triangular]] and ''U'' is [[triangular matrix|upper triangular]] *Related: the [[LDU decomposition|''LDU'' decomposition]] is <math>A=LDU</math>, where ''L'' is [[triangular matrix|lower triangular]] with ones on the diagonal, ''U'' is [[triangular matrix|upper triangular]] with ones on the diagonal, and ''D'' is a [[diagonal matrix]]. *Related: the [[LUP decomposition|''LUP'' decomposition]] is <math>A=LUP</math>, where ''L'' is [[triangular matrix|lower triangular]], ''U'' is [[triangular matrix|upper triangular]], and ''P'' is a [[permutation matrix]]. *Existence: An LUP decomposition exists for any square matrix ''A''. When ''P'' is an [[identity matrix]], the LUP decomposition reduces to the LU decomposition. If the LU decomposition exists, the LDU decomposition does too. *Comments: The LUP and LU decompositions are useful in solving an ''n''-by-''n'' system of linear equations <math>Ax=b</math>. These decompositions summarize the process of [[Gaussian elimination]] in matrix form. Matrix ''P'' represents any row interchanges carried out in the process of Gaussian elimination; if the system can be solved by Gaussian elimination without row interchanges, then ''P=I'', so an LU decomposition exists. === [[LU Reduction]] === === [[Block LU decomposition]] === === [[Cholesky decomposition]] === *Applicable to: [[square matrix|square]], [[symmetric matrix|symmetric]], [[positive definite]] matrix ''A'' *Decomposition: <math>A=U^TU</math>, where ''U'' is upper triangular with positive diagonal entries *Comment: the Cholesky decomposition is a special case of the symmetric LU decomposition, with <math>L=U^T</math>. *Comment: the Cholesky decomposition is unique *Comment: the Cholesky decomposition is also applicable for complex hermitian positive definite matrices === [[QR decomposition]] === *Applicable to: ''m''-by-''n'' matrix ''A'' *Decomposition: <math>A=QR</math> where ''Q'' is an [[orthogonal matrix]] of size ''m''-by-''m'', and ''R'' is an [[triangular matrix|upper triangular]] matrix of size ''m''-by-''n'' *Comment: The QR decomposition provides an alternative way of solving the system of equations <math>Ax=b</math> without [[matrix inverse|inverting]] the matrix ''A''. The fact that ''Q'' is orthogonal means that <math>Q^TQ=I</math>, so that <math>Ax=b</math> is equivalent to <math>Rx=Q^Tb</math>, which is easier to solve since ''R'' is [[triangular matrix|triangular]]. == Decompositions based on [[eigenvalue]]s and related concepts == === [[Eigendecomposition (matrix)|Eigendecomposition]] (also called ''spectral decomposition'') === *Applicable to: [[square matrix]] ''A''. *Decomposition: <math>A=VDV^{-1}</math>, where ''D'' is a [[diagonal matrix]] formed from the [[eigenvalue]]s of ''A'', and the columns of ''V'' are the corresponding [[eigenvector]]s of ''A''. *Existence: An ''n''-by-''n'' matrix ''A'' always has ''n'' eigenvalues, which can be ordered (in more than one way) to form an ''n''-by-''n'' diagonal matrix ''D'' and a corresponding matrix of nonzero columns ''V'' that satisfies the [[Eigenvalue, eigenvector and eigenspace#Definitions: the eigenvalue equation|eigenvalue equation]] <math>AV=VD</math>. If the ''n'' eigenvalues are distinct (that is, none is equal to any of the others), then ''V'' is invertible, implying the decomposition <math>A=VDV^{-1}</math>. *Comment: The eigendecomposition is useful for understanding the solution of a system of linear ordinary differential equations or linear difference equations. For example, the difference equation <math>x_{t+1}=Ax_t</math> starting from the initial condition <math>x_0=c</math> is solved by <math>x_t = A^tc</math>, which is equivalent to <math>x_t = VD^tV^{-1}c</math>, where ''V'' and ''D'' are the matrices formed from the eigenvectors and eigenvalues of ''A''. Since ''D'' is diagonal, raising it to power <math>D^t</math>, just involves raising each element on the diagonal to the power ''t''. This is much easier to do and to understand than raising ''A'' to power ''t'', since ''A'' is usually not diagonal. === [[Jordan normal form|Jordan decomposition]] === *Applicable to: [[square matrix]] ''A'' *Comment: the Jordan decomposition generalizes the eigendecomposition to cases where there are repeated eigenvalues. === [[Schur decomposition]] === *Applicable to: [[square matrix]] ''A'' *Comment: there are two versions of this decomposition: the complex Schur decomposition and the real Schur decomposition. *Decomposition (complex version): <math>A=UTU^H</math>, where ''U'' is a [[unitary matrix]], <math>U^H</math> is the [[conjugate transpose]] of ''U'', and ''T'' is an [[upper triangular]] matrix called the complex [[Schur form]] which has the [[eigenvalue]]s of ''A'' along its diagonal. *Decomposition (real version): <math>A=VSV^T</math>, where ''A'', ''V'', ''S'' and <math>V^T</math> are matrices that contain real numbers only. In this case, ''V'' is an [[orthogonal matrix]], <math>V^T</math> is the [[matrix transpose|transpose]] of ''V'', and ''S'' is a [[block matrix|block upper triangular]] matrix called the real [[Schur form]]. The blocks on the diagonal of ''S'' are of size 1×1 (in which case they represent real eigenvalues) or 2×2 (in which case they are derived from [[complex conjugate]] eigenvalue pairs). === [[QZ decomposition]] (also called ''generalized Schur decomposition'') === *Applicable to: [[square matrix|square matrices]] ''A'' and ''B'' *Comment: there are two versions of this decomposition: complex and real. *Decomposition (complex version): <math>A=QSZ^H</math> and <math>B=QTZ^H</math> where ''Q'' and ''Z'' are [[unitary matrix|unitary matrices]], the ''H'' superscript represents [[conjugate transpose]], and ''S'' and ''T'' are [[upper triangular]] matrices. *Comment: in the complex QZ decomposition, the ratios of the diagonal elements of ''S'' to the corresponding diagonal elements of ''T'', <math>\lambda_i = S_{ii}/T_{ii}</math>, are the generalized [[eigenvalue]]s that solve the [[Eigendecomposition of a matrix#Additional topics|generalized eigenvalue problem]] <math>Av=\lambda Bv</math> (where <math>\lambda</math> is an unknown scalar and ''v'' is an unknown nonzero vector). *Decomposition (real version): <math>A=QSZ^T</math> and <math>B=QTZ^T</math> where ''A'', ''B'', ''Q'', ''Z'', ''S'', and ''T'' are matrices containing real numbers only. In this case ''Q'' and ''Z'' are [[orthogonal matrix|orthogonal matrices]], the ''T'' superscript represents [[matrix transpose|transposition]], and ''S'' and ''T'' are [[block matrix|block upper triangular]] matrices. The blocks on the diagonal of ''S'' and ''T'' are of size 1×1 or 2×2. === [[Singular value decomposition]] === *Applicable to: ''m''-by-''n'' matrix ''A''. *Decomposition: <math>A=UDV^H</math>, where ''D'' is a nonnegative [[diagonal matrix]], and ''U'' and ''V'' are [[unitary matrix|unitary matrices]], and <math>V^H</math> denotes the [[conjugate transpose]] of ''V'' (or simply the [[matrix transpose|transpose]], if ''V'' contains real numbers only). *Comment: The diagonal elements of ''D'' are called the [[singular value]]s of ''A''. *Comment: like the eigendecomposition, the singular value decomposition involves finding basis directions along which matrix multiplication is equivalent to scalar multiplication, but it has greater generality since the matrix under consideration need not be square. === Takagi's factorization === *Applicable to: square, complex, symmetric matrix ''A''. *Decomposition: <math>A=VDV^T</math>, where ''D'' is a real nonnegative [[diagonal matrix]], and ''V'' is [[unitary matrix|unitary]]. <math>V^T</math> denotes the [[matrix transpose]] of ''V''. *Comment: the diagonal elements of ''D'' are the nonnegative square roots of the eigenvalues of <math>AA^H</math>. *Comment: ''V'' may be complex even if ''A'' is real. == Other decompositions == * [[Polar decomposition]] * [[Proper orthogonal decomposition]] == See also == * [[Canonical form]] {{linear algebra}} [[Category:Matrix theory]] [[Category:Mathematical terminology]] [[is:Fylkjaliðun]] [[pl:Rozkład macierzy]] [[sv:Matrisfaktorisering]] [[uk:Розклад матриці]] [[zh:矩阵分解]]