Namespaces
Variants
Actions

Difference between revisions of "Matrix factorization"

From Encyclopedia of Mathematics
Jump to: navigation, search
(Importing text file)
 
m (tex,MR,ZBL,MSC, refs)
 
Line 1: Line 1:
 +
{{MSC|15}}
 +
{{TEX|done}}
 +
 
''factorization of matrices''
 
''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.
 
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.==
+
==$QR$-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
+
Let $A$ be an $(m\times n)$-matrix with $m\ge n$ over $\C$. Then there exist a unitary $(m\times m)$-matrix $Q$ and a right-triangular $m\times n$-matrix $R$ such that $A=QR$. Here, a right-triangular $(m\times n)$-matrix, $m\ge n$, 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.
+
$$\begin{pmatrix}
 +
r_{11} & r_{12} & \cdots & r_{1n} \\
 +
  0    & r_{22} & \cdots & r_{2n} \\
 +
\vdots &        & \ddots & \vdots \\
 +
  0    &    0  & \cdots & r_{nn} \\
 +
  0    &    0  & \cdots &  0    \\
 +
\vdots &        & \ddots & \vdots \\
 +
  0    &    0  & \cdots &  0    \\
 +
\end{pmatrix}.$$
 +
A real (respectively, complex) non-singular matrix $A$ has a factorization $QR$ with $Q$ orthogonal (respectively, unitary) and $R$ 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 $QR$-algorithm for eigenvalue problems (cf.
 +
[[Iteration methods|Iteration methods]]) is based on repeated $QR$-factorization.
  
 
==Singular value 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
+
Let $A$ be an $(m\times n)$-matrix over $\C$ of rank $k$. Then it can be written as $A=U\def\S{ {\Sigma}}\S V$, with $U$ a unitary $(m\times n)$-matrix, $V$ a unitary $(n\times n)$-matrix and $\S$ 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.==
+
$$\S = \begin{pmatrix} \def\cD{ {\mathcal D}} \cD & 0\\ 0 & 0\end{pmatrix},$$
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,
+
where $\cD$ is diagonal with as entries the singular values $s_1,\dots,s_k$ of $A$, i.e. the positive square roots of the eigenvalues of $AA^*$ (equivalently, of $A^* A$).
  
<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>
+
==$LU$-factorization.==
 +
An $(n\times n)$-matrix $A$ (over a field) such that the leading principal minors are non-zero,
  
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.
+
$$\det\begin{pmatrix}
 +
a_{11} & \cdots & a_{1i}\\
 +
\vdots &        & \vdots\\
 +
a_{i1} & \cdots & a_{ii}
 +
\end{pmatrix} \ne 0,\quad i=1,\dots,n,$$
 +
can be written as a product $A=LU$ with $L$ a lower-triangular matrix and $U$ an upper-triangular matrix. This is also known as triangular factorization. This factorization is unique if the diagonal elements of $L$ (respectively, $U$) are specified (e.g., all equal to $1$); see, e.g.,
 +
{{Cite|YoGr}}, p. 821. Conversely, if $A$ is invertible and $A=LU$, 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:
+
In general, permutations of rows (or columns) are needed to obtain a triangular factorization. For any $(m\times n)$-matrix there are a permutation matrix $P$, a lower-triangular matrix $L$ with unit diagonal and an $(m\times n)$ echelon matrix $U$ such that $PA=LU$. 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);
 
i) the non-zero rows come first (the first non-zero entry in a row is sometimes called a pivot);
Line 32: Line 47:
 
iii) each pivot lies to the right of the pivot in the row above. For example,
 
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>
+
$$\def\bu{\bullet}\begin{pmatrix}
 
+
0 & \bu & * & * & * & * & * & * & * & * \\
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]]].
+
0 &  0  &\bu& * & * & * & * & * & * & * \\
 +
0 &  0  & 0 & 0 & 0 &\bu& * & * & * & * \\
 +
0 &  0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\bu\\
 +
0 &  0  & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0  
 +
\end{pmatrix}$$
 +
where the pivots are denoted by $\bu$. $LU$-factorization is tightly connected with Gaussian elimination, see
 +
[[Gauss method|Gauss method]] and
 +
{{Cite|St}}.
  
 
==Iwasawa decomposition.==
 
==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]].
+
The $QR$-factorization for real non-singular matrices immediately leads to the Iwasawa factorization $A=QDR$ with $Q$ orthogonal, $D$ diagonal and $R$ an upper (or lower) triangular matrix with $1$s on the diagonal, giving an Iwasawa decomposition for any non-compact real semi-simple
 +
[[Lie group|Lie group]].
  
 
==Choleski factorization.==
 
==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.
+
For each Hermitean positive-definite matrix $A$ over $\C$ (i.e., $A = A^*$, $x^* Ax > 0$ for all $0\ne x\in\C^n$) there is a unique lower-triangular matrix $L$ with positive diagonal entries such that $A=LL^*$. If $A$ is real, so is $L$. See, e.g.,
 +
{{Cite|StBu}}, p. 180ff. This $L$ is called a Choleski factor. An incomplete Choleski factorization of a real positive-definite symmetric $A$ is a factorization of $A$ as $A=LDL^T$ with $D$ a positive-definite diagonal matrix and $L$ lower-triangular.
  
 
==Decomposition of matrices.==
 
==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.
+
Instead of  "factorization" , the word  "decomposition"  is also used: Choleski decomposition, $LU$-decomposition, $QR$-decomposition, triangular decomposition.
  
 
However, decomposition of matrices can also mean, e.g., block decomposition in block-triangular form:
 
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>
+
$$A=\begin{pmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{pmatrix}$$
 
 
 
and a decomposable matrix is generally understood to mean a matrix that, via a similarity transformation, can be brought to the form
 
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>
+
$$SAS^{-1}=\begin{pmatrix} A_{1} & 0 \\ 0 & A_{2} \end{pmatrix}.$$
 
+
Still other notions of decomposable matrix exist, cf., e.g.,
Still other notions of decomposable matrix exist, cf., e.g., [[#References|[a10]]].
+
{{Cite|MaMi}}.
  
 
==Matrices over function fields.==
 
==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
+
For matrices over function fields there are (in addition) other types of factorizations that are important. E.g., let $W$ be an $(m\times m)$-matrix with coefficients in the field of rational functions $\def\l{ {\lambda}}\C(\l)$ and without poles in $\R$ or at $\infty$. Assume also that $\det W(\l)\ne 0$ for $\l\in\R\cup\{\infty\}$. Then there are rational function matrices $W_+$ and $W_-$, also without poles in $\R$ or at $\infty$, and integers $k_1\le \cdots \le k_m$ 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>
 
  
 +
$$W(\l) = W_-(\l)\begin{pmatrix}
 +
\Big(\frac{\l-i}{\l+i}\Big)^{k_1} &      &        \\
 +
                                  &\ddots&        \\
 +
                                  &      & \Big(\frac{\l-i}{\l+i}\Big)^{k_m}
 +
\end{pmatrix}W_+(\l)$$
 
and
 
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" />;
+
a) $W_+$ has no poles in $\def\Im{ {\rm Im}\;}\Im \l \ge 0$ and $\det W_+(\l)\ne 0$ for $\Im \l \ge 0$;
  
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" />;
+
b) $W_-$ has no poles in $\Im \l \le 0$ and $\det W_-(\l)\ne 0$ for $\Im \l \le 0$;
  
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" />).
+
c) $\det W_+(\infty)\ne 0$; $\det W_-(\infty)\ne 0$. 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 $W_+$ and $W_-$ interchanged) and Wiener–Hopf factorizations with respect to the circle (or any other contour in $\C$).
  
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]].
+
In the scalar case, $m=1$, the factors $W_-(\l)$ and $W_+(\l)$ are unique. This is no longer the case for $m\ge 2$ (however, the indices $k_1,\dots,k_m $ 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]]].
+
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
 +
{{Cite|BaGoKa}},
 +
{{Cite|ClGo}},
 +
{{Cite|GoGoKa}}.
  
 
==Matrix polynomials.==
 
==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.
+
The factorization of matrix polynomials, i.e., the study of the division structure of the ring of $(m\times m)$-matrices with polynomial entries, is a quite different matter. See
 +
{{Cite|Ma}},
 +
{{Cite|Ro}} for results in this direction.
  
 
====References====
 
====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. MarcusH. Minc,  "A survey of matrix theory and matrix inequalities" , Dover  (1992) pp. 122ff</TD></TR></table>
+
{|
 +
|-
 +
|valign="top"|{{Ref|BaGoKa}}||valign="top"| H. Bart,  I. Gohberg,  M.A. Kaashoek,  "Minimal factorization of matrix and operator functions", Birkhäuser  (1979) {{MR|0560504}} {{ZBL|0424.47001}}
 +
|-
 +
|valign="top"|{{Ref|ClGo}}||valign="top"| K. Clancey,  I. Gohberg,  "Factorization of matrix functions and singular integral operators", Birkhäuser  (1981) {{MR|0657762}} {{ZBL|0474.47023}}
 +
|-
 +
|valign="top"|{{Ref|GoGoKa}}||valign="top"| I. Gohberg,  S. Goldberg,  M.A. Kaashoek,  "Classes of linear operators", '''I–II''', Birkhäuser  (1990–1993) {{MR|1130394}} {{MR|1246332}} {{ZBL|1065.47001}} {{ZBL|0789.47001}}
 +
|-
 +
|valign="top"|{{Ref|Ma}}||valign="top"| A.N. Malyshev,  "Matrix equations: Factorization of matrix polynomials"  M. Hazewinkel (ed.), ''Handbook of Algebra'', '''I''', Elsevier  (1995)  pp. 79–116 {{MR|1421799}} {{ZBL|0857.15003}}
 +
|-
 +
|valign="top"|{{Ref|MaMi}}||valign="top"|  M. Marcus,  H. Minc,  "A survey of matrix theory and matrix inequalities", Dover  (1992)  pp. 122ff {{MR|1215484}} {{ZBL|0126.02404}}
 +
|-
 +
|valign="top"|{{Ref|NoDa}}||valign="top"|  B. Noble,  J.W. Daniel,  "Applied linear algebra", Prentice-Hall  (1969)  pp. Sect. 9.4–9.5 {{MR|0572995}}  {{ZBL|0203.33201}}
 +
|-
 +
|valign="top"|{{Ref|Ro}}||valign="top"| L. Rodman,  "Matrix functions"  M. Hazewinkel (ed.), ''Handbook of Algebra'', '''I''', Elsevier  (1995)  pp. 117–154 {{MR|1421800}} {{MR|2035093}}  {{ZBL|0858.15011}} {{ZBL|1068.15035}}
 +
|-
 +
|valign="top"|{{Ref|St}}||valign="top"|  G. Strang,  "Linear algebra and its applications", Harcourt–Brace–Jovanovich  (1976)  {{MR|0384823}}  {{ZBL|0338.15001}}
 +
|-
 +
|valign="top"|{{Ref|StBu}}||valign="top"| J. Stoer,  R. Bulirsch,  "Introduction to numerical analysis", Springer  (1993) {{MR|1295246}} {{ZBL|0771.65002}}
 +
|-
 +
|valign="top"|{{Ref|YoGr}}||valign="top"|  D.M. YoungR.T. Gregory,  "A survey of numerical mathematics", '''II''', Dover  (1988) {{MR|1102901}} {{ZBL|0732.65003}}
 +
|-
 +
|}

Latest revision as of 22:47, 28 February 2015

2020 Mathematics Subject Classification: Primary: 15-XX [MSN][ZBL]

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.

$QR$-factorization.

Let $A$ be an $(m\times n)$-matrix with $m\ge n$ over $\C$. Then there exist a unitary $(m\times m)$-matrix $Q$ and a right-triangular $m\times n$-matrix $R$ such that $A=QR$. Here, a right-triangular $(m\times n)$-matrix, $m\ge n$, is of the form

$$\begin{pmatrix} r_{11} & r_{12} & \cdots & r_{1n} \\ 0 & r_{22} & \cdots & r_{2n} \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & r_{nn} \\ 0 & 0 & \cdots & 0 \\ \vdots & & \ddots & \vdots \\ 0 & 0 & \cdots & 0 \\ \end{pmatrix}.$$ A real (respectively, complex) non-singular matrix $A$ has a factorization $QR$ with $Q$ orthogonal (respectively, unitary) and $R$ having all elements positive. Such a factorization is unique and given by the Gram–Schmidt orthogonalization process (cf. Orthogonalization method). The frequently used $QR$-algorithm for eigenvalue problems (cf. Iteration methods) is based on repeated $QR$-factorization.

Singular value factorization.

Let $A$ be an $(m\times n)$-matrix over $\C$ of rank $k$. Then it can be written as $A=U\def\S{ {\Sigma}}\S V$, with $U$ a unitary $(m\times n)$-matrix, $V$ a unitary $(n\times n)$-matrix and $\S$ of the form

$$\S = \begin{pmatrix} \def\cD{ {\mathcal D}} \cD & 0\\ 0 & 0\end{pmatrix},$$ where $\cD$ is diagonal with as entries the singular values $s_1,\dots,s_k$ of $A$, i.e. the positive square roots of the eigenvalues of $AA^*$ (equivalently, of $A^* A$).

$LU$-factorization.

An $(n\times n)$-matrix $A$ (over a field) such that the leading principal minors are non-zero,

$$\det\begin{pmatrix} a_{11} & \cdots & a_{1i}\\ \vdots & & \vdots\\ a_{i1} & \cdots & a_{ii} \end{pmatrix} \ne 0,\quad i=1,\dots,n,$$ can be written as a product $A=LU$ with $L$ a lower-triangular matrix and $U$ an upper-triangular matrix. This is also known as triangular factorization. This factorization is unique if the diagonal elements of $L$ (respectively, $U$) are specified (e.g., all equal to $1$); see, e.g., [YoGr], p. 821. Conversely, if $A$ is invertible and $A=LU$, then all leading principal minors are non-zero.

In general, permutations of rows (or columns) are needed to obtain a triangular factorization. For any $(m\times n)$-matrix there are a permutation matrix $P$, a lower-triangular matrix $L$ with unit diagonal and an $(m\times n)$ echelon matrix $U$ such that $PA=LU$. 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,

$$\def\bu{\bullet}\begin{pmatrix} 0 & \bu & * & * & * & * & * & * & * & * \\ 0 & 0 &\bu& * & * & * & * & * & * & * \\ 0 & 0 & 0 & 0 & 0 &\bu& * & * & * & * \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 &\bu\\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{pmatrix}$$ where the pivots are denoted by $\bu$. $LU$-factorization is tightly connected with Gaussian elimination, see Gauss method and [St].

Iwasawa decomposition.

The $QR$-factorization for real non-singular matrices immediately leads to the Iwasawa factorization $A=QDR$ with $Q$ orthogonal, $D$ diagonal and $R$ an upper (or lower) triangular matrix with $1$s on the diagonal, giving an Iwasawa decomposition for any non-compact real semi-simple Lie group.

Choleski factorization.

For each Hermitean positive-definite matrix $A$ over $\C$ (i.e., $A = A^*$, $x^* Ax > 0$ for all $0\ne x\in\C^n$) there is a unique lower-triangular matrix $L$ with positive diagonal entries such that $A=LL^*$. If $A$ is real, so is $L$. See, e.g., [StBu], p. 180ff. This $L$ is called a Choleski factor. An incomplete Choleski factorization of a real positive-definite symmetric $A$ is a factorization of $A$ as $A=LDL^T$ with $D$ a positive-definite diagonal matrix and $L$ lower-triangular.

Decomposition of matrices.

Instead of "factorization" , the word "decomposition" is also used: Choleski decomposition, $LU$-decomposition, $QR$-decomposition, triangular decomposition.

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

$$A=\begin{pmatrix} A_{11} & A_{12} \\ 0 & A_{22} \end{pmatrix}$$ and a decomposable matrix is generally understood to mean a matrix that, via a similarity transformation, can be brought to the form

$$SAS^{-1}=\begin{pmatrix} A_{1} & 0 \\ 0 & A_{2} \end{pmatrix}.$$ Still other notions of decomposable matrix exist, cf., e.g., [MaMi].

Matrices over function fields.

For matrices over function fields there are (in addition) other types of factorizations that are important. E.g., let $W$ be an $(m\times m)$-matrix with coefficients in the field of rational functions $\def\l{ {\lambda}}\C(\l)$ and without poles in $\R$ or at $\infty$. Assume also that $\det W(\l)\ne 0$ for $\l\in\R\cup\{\infty\}$. Then there are rational function matrices $W_+$ and $W_-$, also without poles in $\R$ or at $\infty$, and integers $k_1\le \cdots \le k_m$ such that

$$W(\l) = W_-(\l)\begin{pmatrix} \Big(\frac{\l-i}{\l+i}\Big)^{k_1} & & \\ &\ddots& \\ & & \Big(\frac{\l-i}{\l+i}\Big)^{k_m} \end{pmatrix}W_+(\l)$$ and

a) $W_+$ has no poles in $\def\Im{ {\rm Im}\;}\Im \l \ge 0$ and $\det W_+(\l)\ne 0$ for $\Im \l \ge 0$;

b) $W_-$ has no poles in $\Im \l \le 0$ and $\det W_-(\l)\ne 0$ for $\Im \l \le 0$;

c) $\det W_+(\infty)\ne 0$; $\det W_-(\infty)\ne 0$. 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 $W_+$ and $W_-$ interchanged) and Wiener–Hopf factorizations with respect to the circle (or any other contour in $\C$).

In the scalar case, $m=1$, the factors $W_-(\l)$ and $W_+(\l)$ are unique. This is no longer the case for $m\ge 2$ (however, the indices $k_1,\dots,k_m $ are still unique). See also 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 [BaGoKa], [ClGo], [GoGoKa].

Matrix polynomials.

The factorization of matrix polynomials, i.e., the study of the division structure of the ring of $(m\times m)$-matrices with polynomial entries, is a quite different matter. See [Ma], [Ro] for results in this direction.

References

[BaGoKa] H. Bart, I. Gohberg, M.A. Kaashoek, "Minimal factorization of matrix and operator functions", Birkhäuser (1979) MR0560504 Zbl 0424.47001
[ClGo] K. Clancey, I. Gohberg, "Factorization of matrix functions and singular integral operators", Birkhäuser (1981) MR0657762 Zbl 0474.47023
[GoGoKa] I. Gohberg, S. Goldberg, M.A. Kaashoek, "Classes of linear operators", I–II, Birkhäuser (1990–1993) MR1130394 MR1246332 Zbl 1065.47001 Zbl 0789.47001
[Ma] A.N. Malyshev, "Matrix equations: Factorization of matrix polynomials" M. Hazewinkel (ed.), Handbook of Algebra, I, Elsevier (1995) pp. 79–116 MR1421799 Zbl 0857.15003
[MaMi] M. Marcus, H. Minc, "A survey of matrix theory and matrix inequalities", Dover (1992) pp. 122ff MR1215484 Zbl 0126.02404
[NoDa] B. Noble, J.W. Daniel, "Applied linear algebra", Prentice-Hall (1969) pp. Sect. 9.4–9.5 MR0572995 Zbl 0203.33201
[Ro] L. Rodman, "Matrix functions" M. Hazewinkel (ed.), Handbook of Algebra, I, Elsevier (1995) pp. 117–154 MR1421800 MR2035093 Zbl 0858.15011 Zbl 1068.15035
[St] G. Strang, "Linear algebra and its applications", Harcourt–Brace–Jovanovich (1976) MR0384823 Zbl 0338.15001
[StBu] J. Stoer, R. Bulirsch, "Introduction to numerical analysis", Springer (1993) MR1295246 Zbl 0771.65002
[YoGr] D.M. Young, R.T. Gregory, "A survey of numerical mathematics", II, Dover (1988) MR1102901 Zbl 0732.65003
How to Cite This Entry:
Matrix factorization. Encyclopedia of Mathematics. URL: http://encyclopediaofmath.org/index.php?title=Matrix_factorization&oldid=36319
This article was adapted from an original article by M. Hazewinkel (originator), which appeared in Encyclopedia of Mathematics - ISBN 1402006098. See original article