View source for Matrix factorization

''factorization of matrices''

Factorizations of matrices over a field are useful in quite a number of problems, both analytical and numerical; for example, in the (numerical) solution of linear equations and eigenvalue problems. A few well-known factorizations are listed below.

==<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201401.png" />-factorization.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201402.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201403.png" />-matrix with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201404.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201405.png" />. Then there exist a unitary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201406.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201407.png" /> and a right-triangular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201408.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m1201409.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014010.png" />. Here, a right-triangular <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014011.png" />-matrix, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014012.png" />, is of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014013.png" /></td> </tr></table>

A real (respectively, complex) non-singular matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014014.png" /> has a factorization <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014015.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014016.png" /> orthogonal (respectively, unitary) and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014017.png" /> having all elements positive. Such a factorization is unique and given by the Gram–Schmidt orthogonalization process (cf. [[Orthogonalization method|Orthogonalization method]]). The frequently used <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014019.png" />-algorithm for eigenvalue problems (cf. [[Iteration methods|Iteration methods]]) is based on repeated <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014020.png" />-factorization.

==Singular value factorization.==
Let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014021.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014022.png" />-matrix over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014023.png" /> of rank <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014024.png" />. Then it can be written as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014025.png" />, with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014026.png" /> a unitary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014027.png" />-matrix, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014028.png" /> a unitary <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014029.png" />-matrix and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014030.png" /> of the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014031.png" /></td> </tr></table>

where <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014032.png" /> is diagonal with as entries the singular values <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014033.png" /> of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014034.png" />, i.e. the positive square roots of the eigenvalues of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014035.png" /> (equivalently, of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014036.png" />).

==<img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014037.png" />-factorization.==
An <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014038.png" />-matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014039.png" /> (over a field) such that the leading principal minors are non-zero,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014040.png" /></td> </tr></table>

can be written as a product <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014041.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014042.png" /> a lower-triangular matrix and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014043.png" /> an upper-triangular matrix. This is also known as triangular factorization. This factorization is unique if the diagonal elements of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014044.png" /> (respectively, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014045.png" />) are specified (e.g., all equal to <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014046.png" />); see, e.g., [[#References|[a2]]], p. 821. Conversely, if <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014047.png" /> is invertible and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014048.png" />, then all leading principal minors are non-zero.

In general, permutations of rows (or columns) are needed to obtain a triangular factorization. For any <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014049.png" />-matrix there are a permutation matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014050.png" />, a lower-triangular matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014051.png" /> with unit diagonal and an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014052.png" /> echelon matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014053.png" /> such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014054.png" />. Here, an echelon matrix can be described as follows:

i) the non-zero rows come first (the first non-zero entry in a row is sometimes called a pivot);

ii) below each pivot is a column of zeros;

iii) each pivot lies to the right of the pivot in the row above. For example,

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014055.png" /></td> </tr></table>

where the pivots are denoted by <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014056.png" />. <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014057.png" />-factorization is tightly connected with Gaussian elimination, see [[Gauss method|Gauss method]] and [[#References|[a3]]].

==Iwasawa decomposition.==
The <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014058.png" />-factorization for real non-singular matrices immediately leads to the Iwasawa factorization <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014059.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014060.png" /> orthogonal, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014061.png" /> diagonal and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014062.png" /> an upper (or lower) triangular matrix with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014063.png" />s on the diagonal, giving an Iwasawa decomposition for any non-compact real semi-simple [[Lie group|Lie group]].

==Choleski factorization.==
For each Hermitean positive-definite matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014064.png" /> over <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014065.png" /> (i.e., <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014066.png" />, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014067.png" /> for all <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014068.png" />) there is a unique lower-triangular matrix <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014069.png" /> with positive diagonal entries such that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014070.png" />. If <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014071.png" /> is real, so is <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014072.png" />. See, e.g., [[#References|[a4]]], p. 180ff. This <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014073.png" /> is called a Choleski factor. An incomplete Choleski factorization of a real positive-definite symmetric <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014074.png" /> is a factorization of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014075.png" /> as <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014076.png" /> with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014077.png" /> a positive-definite diagonal matrix and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014078.png" /> lower-triangular.

==Decomposition of matrices.==
Instead of  "factorization" , the word  "decomposition"  is also used: Choleski decomposition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014080.png" />-decomposition, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014082.png" />-decomposition, triangular decomposition.

However, decomposition of matrices can also mean, e.g., block decomposition in block-triangular form:

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014083.png" /></td> </tr></table>

and a decomposable matrix is generally understood to mean a matrix that, via a similarity transformation, can be brought to the form

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014084.png" /></td> </tr></table>

Still other notions of decomposable matrix exist, cf., e.g., [[#References|[a10]]].

==Matrices over function fields.==
For matrices over function fields there are (in addition) other types of factorizations that are important. E.g., let <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014085.png" /> be an <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014086.png" />-matrix with coefficients in the field of rational functions <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014087.png" /> and without poles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014088.png" /> or at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014089.png" />. Assume also that <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014090.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014091.png" />. Then there are rational function matrices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014092.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014093.png" />, also without poles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014094.png" /> or at <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014095.png" />, and integers <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014096.png" /> such that

<table class="eq" style="width:100%;"> <tr><td valign="top" style="width:94%;text-align:center;"><img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014097.png" /></td> </tr></table>

and

a) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014098.png" /> has no poles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m12014099.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140100.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140101.png" />;

b) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140102.png" /> has no poles in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140103.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140104.png" /> for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140105.png" />;

c) <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140106.png" />; <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140107.png" />. This is called a Wiener–Hopf factorization; more precisely, a right Wiener–Hopf factorization with respect to the real line. There are also left Wiener–Hopf factorizations (with <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140108.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140109.png" /> interchanged) and Wiener–Hopf factorizations with respect to the circle (or any other contour in <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140110.png" />).

In the scalar case, <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140111.png" />, the factors <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140112.png" /> and <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140113.png" /> are unique. This is no longer the case for <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140114.png" /> (however, the indices <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140115.png" /> are still unique). See also [[Integral equation of convolution type|Integral equation of convolution type]].

If all indices in the decomposition are zero, one speaks of a right canonical factorization. For more, and also about spectral factorization and minimal factorization, and applications, see [[#References|[a5]]], [[#References|[a6]]], [[#References|[a7]]].

==Matrix polynomials.==
The factorization of matrix polynomials, i.e., the study of the division structure of the ring of <img align="absmiddle" border="0" src="https://www.encyclopediaofmath.org/legacyimages/m/m120/m120140/m120140116.png" />-matrices with polynomial entries, is a quite different matter. See [[#References|[a8]]], [[#References|[a9]]] for results in this direction.

====References====
<table><TR><TD valign="top">[a1]</TD> <TD valign="top">  B. Noble,   J.W. Daniel,   "Applied linear algebra" , Prentice-Hall  (1969)  pp. Sect. 9.4–9.5</TD></TR><TR><TD valign="top">[a2]</TD> <TD valign="top">  D.M. Young,   R.T. Gregory,   "A survey of numerical mathematics" , '''II''' , Dover  (1988)</TD></TR><TR><TD valign="top">[a3]</TD> <TD valign="top">  G. Strang,   "Linear algebra and its applications" , Harcourt–Brace–Jovanovich  (1976)</TD></TR><TR><TD valign="top">[a4]</TD> <TD valign="top">  J. Stoer,   R. Bulirsch,   "Introduction to numerical analysis" , Springer  (1993)</TD></TR><TR><TD valign="top">[a5]</TD> <TD valign="top">  H. Bart,   I. Gohberg,   M.A. Kaashoek,   "Minimal factorization of matrix and operator functions" , Birkhäuser  (1979)</TD></TR><TR><TD valign="top">[a6]</TD> <TD valign="top">  K. Clancey,   I. Gohberg,   "Factorization of matrix functions and singular integral operators" , Birkhäuser  (1981)</TD></TR><TR><TD valign="top">[a7]</TD> <TD valign="top">  I. Gohberg,   S. Goldberg,   M.A. Kaashoek,   "Classes of linear operators" , '''I–II''' , Birkhäuser  (1990–1993)</TD></TR><TR><TD valign="top">[a8]</TD> <TD valign="top">  A.N. Malyshev,   "Matrix equations: Factorization of matrix polynomials"  M. Hazewinkel (ed.) , ''Handbook of Algebra'' , '''I''' , Elsevier  (1995)  pp. 79–116</TD></TR><TR><TD valign="top">[a9]</TD> <TD valign="top">  L. Rodman,   "Matrix functions"  M. Hazewinkel (ed.) , ''Handbook of Algebra'' , '''I''' , Elsevier  (1995)  pp. 117–154</TD></TR><TR><TD valign="top">[a10]</TD> <TD valign="top">  M. Marcus,   H. Minc,   "A survey of matrix theory and matrix inequalities" , Dover  (1992)  pp. 122ff</TD></TR></table>