Editing Matrix decomposition (section)

== Decompositions related to solving systems of linear equations ==

=== LU decomposition ===
{{main|LU decomposition}}
*Traditionally applicable to: [[square matrix]] ''A'', although rectangular matrices can be applicable.<ref>{{Cite book|last=Lay|first=David C.|url=https://www.worldcat.org/oclc/920463015|title=Linear algebra and its applications|date=2016|others=Steven R. Lay, Judith McDonald|isbn=978-1-292-09223-2|edition=Fifth Global|location=Harlow|pages=142|oclc=920463015}}</ref><ref group="nb">If a non-square matrix is used, however, then the matrix ''U'' will also have the same rectangular shape as the original matrix ''A''. And so, calling the matrix ''U'' upper triangular would be incorrect as the correct term would be that ''U'' is the 'row echelon form' of ''A''. Other than this, there are no differences in LU factorization for square and non-square matrices.</ref>
*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>PA=LU</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.
*Comments: The LUP and LU decompositions are useful in solving an ''n''-by-''n'' system of linear equations <math>A \mathbf{x} = \mathbf{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 Gaussian elimination produces the [[row echelon form]] without requiring any row interchanges, then ''P''&nbsp;=&nbsp;''I'', so an LU decomposition exists.

=== LU reduction ===
{{main|LU reduction}}

=== Block LU decomposition ===
{{main|Block LU decomposition}}

=== Rank factorization ===
{{main|Rank factorization}}
*Applicable to: ''m''-by-''n'' matrix ''A'' of rank ''r''
*Decomposition: <math>A=CF</math> where ''C'' is an ''m''-by-''r'' full column rank matrix and ''F'' is an ''r''-by-''n'' full row rank matrix
*Comment: The rank factorization can be used to [[Moore–Penrose pseudoinverse#Rank decomposition|compute the Moore–Penrose pseudoinverse]] of ''A'',<ref>{{cite journal|last1=Piziak|first1=R.|last2=Odell|first2=P. L.|title=Full Rank Factorization of Matrices|journal=Mathematics Magazine|date=1 June 1999|volume=72|issue=3|pages=193|doi=10.2307/2690882|jstor=2690882}}</ref> which one can apply to [[Moore–Penrose pseudoinverse#Obtaining all solutions of a linear system|obtain all solutions of the linear system]] <math>A \mathbf{x} = \mathbf{b}</math>.

=== Cholesky decomposition ===
{{main|Cholesky decomposition}}
*Applicable to: [[square matrix|square]], [[symmetric matrix|hermitian]], [[positive-definite matrix|positive definite]] matrix <math>A</math>
*Decomposition: <math>A=U^*U</math>, where <math>U</math> is upper triangular with real positive diagonal entries
*Comment: if the matrix <math>A</math> is Hermitian and positive semi-definite, then it has a decomposition of the form <math>A=U^*U</math> if the diagonal entries of <math>U</math> are allowed to be zero
*Uniqueness: for positive definite matrices Cholesky decomposition is unique. However, it is not unique in the positive semi-definite case.
*Comment: if <math>A</math> is real and symmetric, <math>U</math> has all real elements
*Comment: An alternative is the [[LDL decomposition]], which can avoid extracting square roots.

=== QR decomposition ===
{{main|QR decomposition}}
*Applicable to: ''m''-by-''n'' matrix ''A'' with linearly independent columns
*Decomposition: <math>A=QR</math> where <math>Q</math> is a [[unitary matrix]] of size ''m''-by-''m'', and <math>R</math> is an [[triangular matrix|upper triangular]] matrix of size ''m''-by-''n''
*Uniqueness: In general it is not unique, but if <math>A</math> is of full [[Matrix rank|rank]], then there exists a single <math>R</math> that has all positive diagonal elements. If <math>A</math> is square, also <math>Q</math> is unique.
*Comment: The QR decomposition provides an effective way to solve the system of equations <math>A \mathbf{x} = \mathbf{b}</math>. The fact that <math>Q</math> is [[orthogonal matrix|orthogonal]]  means that <math>Q^{\mathrm{T}}Q=I</math>, so that <math>A \mathbf{x} = \mathbf{b}</math> is equivalent to <math>R \mathbf{x} = Q^{\mathsf{T}} \mathbf{b}</math>, which is very easy to solve since <math>R</math> is [[triangular matrix|triangular]].

=== RRQR factorization ===
{{main|RRQR factorization}}

=== Interpolative decomposition ===

{{main|Interpolative decomposition}}