Matrix factorization

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