# Polynomial matrix spectral factorization > Mediated Wiki article. Canonical URL: https://mediated.wiki/source/Polynomial_matrix_spectral_factorization > Markdown URL: https://mediated.wiki/source/Polynomial_matrix_spectral_factorization.md > Source: https://en.wikipedia.org/wiki/Polynomial_matrix_spectral_factorization > Source revision: 1342699573 > License: Creative Commons Attribution-ShareAlike 4.0 International (https://creativecommons.org/licenses/by-sa/4.0/) **Polynomial Matrix Spectral Factorization** or **Matrix Fejer–Riesz Theorem** is a tool used to study the [matrix decomposition](/source/Matrix_decomposition) of [polynomial matrices](/source/Polynomial_matrix). Polynomial matrices are widely studied in the fields of [systems theory](/source/Systems_theory) and [control theory](/source/Control_theory) and have seen other uses relating to [stable polynomials](/source/Stable_polynomial). In [stability theory](/source/Stability_theory), Spectral Factorization has been used to find determinantal matrix representations for bivariate stable polynomials and real zero polynomials.[1] Given a positive real [trigonometric polynomial](/source/Trigonometric_polynomial) p(t) > 0 for all t \in \mathbb{R}, the [Fejer–Riesz Theorem](/source/Trigonometric_polynomial#Fejér-Riesz_theorem) yields the factorization p(t) = q(t)\bar{q}(t) called the **spectral factorization** (or **Wiener-Hopf factorization**) of p(t).[2] Results of this form are generically referred to as [Positivstellensatz](/source/Positivstellensatz). Likewise, the Polynomial Matrix Spectral Factorization provides a factorization for [positive definite](/source/Definite_matrix) polynomial matrices. This decomposition also relates to the [Cholesky decomposition](/source/Cholesky_decomposition) for scalar matrices A =LL^*. This result was originally proven by [Norbert Wiener](/source/Norbert_Wiener) in a more general context which was concerned with integrable matrix-valued functions that also had integrable log determinant.[3] Because applications are often concerned with the polynomial restriction, simpler proofs and individual analysis exist focusing on this case.[4] Weaker positivstellensatz conditions have been studied, specifically considering when the polynomial matrix has positive definite image on semi-algebraic subsets of the reals.[5] Spectral factorization is used extensively in [linear–quadratic–Gaussian control](/source/Linear%E2%80%93quadratic%E2%80%93Gaussian_control) and many algorithms exist to calculate spectral factors.[6] Some modern algorithms focus on the more general setting originally studied by Wiener while others have used [Toeplitz matrix](/source/Toeplitz_matrix) advances to speed up factor calculations.[7][8] ## Definition Consider the n \times n [polynomial matrix](/source/Polynomial_matrix) P(x) = \sum_{k=0}^N P_{k}x^{k} = \begin{bmatrix}p_{11}(x) &\ldots &p_{1n}(x) \\ \vdots & \ddots & \vdots\\ p_{n1}(x) & \cdots& p_{nn}(x)\\ \end{bmatrix}, where each element p_{ij}(x) is a [complex polynomial](/source/Complex_polynomial) of at most N-degree. If P(x) is a [positive semi-definite matrix](/source/Definite_matrix) for all x \in \mathbb{R}, then there exists an n \times n polynomial matrix Q(x) with complex polynomials q_{ij}(x) such that P(x) = Q(x) Q^*(x), where Q^*(x) is the [conjugate transpose](/source/Conjugate_transpose).[9] When the elements of Q(x) are complex polynomials or complex coefficient [rational functions](/source/Rational_function) then so are the elements of its conjugate transpose. We can furthermore find Q(x) which is nonsingular on the lower half plane.[10] ## Rational spectral factorization Let p(t) be a [rational function](/source/Rational_function) where p(t) > 0 for all t \in \mathbb{R}. Then there exists a rational function q(t) such that p(t) = q(t)\bar{q}(t) and q(t) has no poles or zeroes in the lower half plane. This decomposition is unique up to multiplication by complex scalars of norm 1. To prove existence write p(x) = c \frac{\prod_i (x- \alpha_i)}{\prod_j (x-\beta_j)}, where \alpha_i \neq \beta_j. Letting x \to \infty, we can conclude that c is real and positive. Dividing out by \sqrt{c} we reduce to the monic case. The numerator and denominator have distinct sets of roots, so all real roots which show up in either must have even multiplicity (to prevent a sign change locally). We can divide out these real roots to reduce to the case where p(t) has only complex roots and poles. By hypothesis we have p(x) = \frac{\prod_i (x- \alpha_i)}{\prod_j (x-\beta_j)} = \frac{\prod_i (x- \bar{\alpha}_i)}{\prod_j (x-\bar{\beta}_j)} = \overline{p(x)}. Since all of the \alpha_i, \beta_jare complex (and hence not fixed points of conjugation) they both come in conjugate pairs. For each conjugate pair, pick the zero or pole in the upper half plane and accumulate these to obtain q(t). The uniqueness result follows in a standard fashion. ## Cholesky decomposition The inspiration for this result is a factorization which characterizes positive definite matrices. ### Decomposition for scalar matrices Given any positive definite [scalar matrix](/source/Scalar_matrix) A, the [Cholesky decomposition](/source/Cholesky_decomposition) allows us to write A = LL^* where L is a [lower triangular matrix](/source/Lower_triangular_matrix). If we don't restrict to lower triangular matrices we can consider all factorizations of the form A = V V^*. It is not hard to check that all factorizations are achieved by looking at the orbit of L under right multiplication by a unitary matrix, V = L U. To obtain the lower triangular decomposition we induct by splitting off the first row and first column: \begin{bmatrix} a_{11} & \mathbf{a}_{12}^* \\ \mathbf{a}_{12} & A_{22} \\ \end{bmatrix} = \begin{bmatrix} l_{11} & 0 \\ \mathbf{l}_{21} & L_{22} \end{bmatrix} \begin{bmatrix} l_{11}^* & \mathbf{l}_{21}^* \\ 0 & L_{22}^* \end{bmatrix} = \begin{bmatrix} l_{11} l_{11}^* & l_{11} \mathbf{l}_{21}^* \\ l_{11}^* \mathbf{l}_{21} & \mathbf{l}_{21} \mathbf{l}_{21}^*+ L_{22} L_{22}^* \end{bmatrix} Solving these in terms of a_{ij} we get l_{11} = \sqrt{a_{11}} \mathbf{l}_{21} = \frac{1}{\sqrt{a_{11}}}\mathbf{a}_{12} L_{22} L_{22}^* = A_{22} - \frac{1}{a_{11}} \mathbf{a}_{12} \mathbf{a}^*_{12} Since A is positive definite we have a_{11}is a positive [real number](/source/Real_number), so it has a [square root](/source/Square_root). The last condition from induction since the right hand side is the [Schur complement](/source/Schur_complement) of A, which is itself positive definite. ### Decomposition for rational polynomial matrices A **rational polynomial matrix** is defined as a matrix P(t) = \begin{bmatrix}p_{11}(t) &\ldots &p_{1n}(t) \\ \vdots & \ddots & \vdots\\ p_{n1}(t) & \cdots& p_{nn}(t)\\ \end{bmatrix}, where each entry p_{ij}(t) is a complex [rational function](/source/Rational_function). If P(t) is a positive definite [Hermitian matrix](/source/Hermitian_matrix) for all t\in\mathbb{R}, then by the symmetric [Gaussian elimination](/source/Gaussian_elimination) we performed above, all we need to show is there exists a rational q_{11}(t) such that p_{11}(t) = q_{11}(t) q_{11}(t)^*, which follows from our rational spectral factorization. Once we have that then we can solve for l_{11}(t), \mathbf{l}_{21}(t). Since the [Schur complement](/source/Schur_complement) is positive definite for the real t away from the poles and the Schur complement is a rational polynomial matrix we can induct to find L_{22}. It is not hard to check that we get P(t) = L(t) L(t)^*where L(t) is a rational polynomial matrix with no poles in the lower half plane. ## Extension to polynomial decompositions One way to prove the existence of polynomial matrix spectral factorization is to apply the Cholesky decomposition to a rational polynomial matrix and modify it to remove lower half plane singularities. That is, given P(t) = \begin{bmatrix}p_{11}(t) &\ldots &p_{1n}(t) \\ \vdots & \ddots & \vdots\\ p_{n1}(t) & \cdots& p_{nn}(t)\\ \end{bmatrix}, where each entry p_{ij}(t) is a complex coefficient polynomial for all t\in\mathbb{R}, a rational polynomial matrix L(t) with no lower half plane poles exists such that P(t) = L(t) L(t)^*. Given a rational polynomial matrix U(t) which is unitary valued for real t, there exists another decomposition[clarification needed] P(t) = L(t) L(t)^* = L(t) U(t)U(t)^*L(t)^*. If \det(L(a)) = 0 then there exists a [scalar](/source/Scalar_matrix) [unitary matrix](/source/Unitary_matrix) U such that U e_1 = \frac{a}{|a|}. This implies L(t) U has first column vanish at a. To remove the singularity at a we multiply by U(t) = \operatorname{diag}(1, \ldots, \frac{z - \bar{a}}{z - a}, \ldots, 1) L(t) U U(t) has determinant with one less zero (by multiplicity) at a, without introducing any poles in the lower half plane of any of the entries. ### Example Consider the following rational matrix decomposition A(t) = \begin{bmatrix} t^2 + 1 & 2 t \\ 2 t & t^2 + 1 \\ \end{bmatrix} = \begin{bmatrix} t - i & 0 \\ \frac{2t}{t + i} & \frac{t^2 - 1}{t + i} \\ \end{bmatrix} \begin{bmatrix} t + i & \frac{2t}{t - i} \\ 0 & \frac{t^2 - 1}{t - i} \\ \end{bmatrix}. This decomposition has no poles in the upper half plane. However \det\left(\begin{bmatrix} t - i & 0 \\ \frac{2t}{t + i} & \frac{t^2 - 1}{t + i} \\ \end{bmatrix}\right)=\frac{(t-1) (t-i) (t+1)}{t+i}, so we need to modify our decomposition to get rid of the singularity at -i. First we multiply by a scalar unitary matrix U =\frac{1}{\sqrt{2}} \begin{bmatrix}1 & 1 \\ i & -i \\ \end{bmatrix}, such that \begin{bmatrix} t - i & 0 \\ \frac{2t}{t + i} & \frac{t^2 - 1}{t + i} \\ \end{bmatrix} U = \frac{1}{\sqrt{2}}\begin{bmatrix} t-i & t - i \\ i \frac{(t-i)^2}{t+i} & -i(t+i) \\ \end{bmatrix}, becomes a new candidate for our decomposition. Now the first column vanishes at t=i, so we multiply through (on the right) by U(t) =\frac{1}{\sqrt{2}} \begin{bmatrix}\frac{t+i}{t-i} & 0 \\ 0 & 1\end{bmatrix}, to obtain Q(t) = \frac{1}{\sqrt{2}}\begin{bmatrix} t-i & t - i \\ i \frac{(t-i)^2}{t+i} & -i(t+i) \\ \end{bmatrix} U(t) = \frac{1}{2}\begin{bmatrix} t + i & t - i \\ i(t-i) & -i(t+i) \\ \end{bmatrix}, where \det(Q(t)) = i(1-t^2). This is our desired decomposition A(t) = Q(t) Q(t)^* with no singularities in the lower half plane. ### Extend analyticity to all of C After modifications, the decomposition P(t)=Q(t) Q(t)^*satisfies Q(t) is [holomorphic](/source/Holomorphic) and invertible on the lower half plane. To extend analyticity to the upper half plane we need this key observation: If an invertible rational matrix Q(t) is holomorphic in the lower half plane, Q(t)^{-1} is holomorphic in the lower half plane as well. The analyticity follows from the [adjugate matrix](/source/Adjugate_matrix) formula (since both the entries of Q(t) and \det(Q(t))^{-1}are analytic on the lower half plane). The determinant of a rational polynomial matrix can only have poles where its entries have poles, so \det(Q(t)) has no poles in the lower half plane. Subsequently, Q(t)=(P(t)Q(t)^{-1})^*. Since Q(t)^{-1} is analytic on the lower half plane, Q(t) is analytic on the upper half plane. Finally if Q(t) has a pole on the real line then Q(t)^* has the same pole on the real line which contradicts the hypothesis that P(t) has no poles on the real line (i.e. it is analytic everywhere). The above shows that if Q(t) is analytic and invertible on the lower half plane indeed Q(t) is analytic everywhere and hence a polynomial matrix. ## See also - [Matrix factorization of a polynomial](/source/Matrix_factorization_of_a_polynomial) ## Notes 1. Grinshpan et al. 2016, pp. 1–26. 1. Böttcher & Halwass 2013, pp. 4760–4805. 1. Wiener & Masani 1957, pp. 111–150. 1. Tim N.T. Goodman Charles A. Micchelli Giuseppe Rodriguez Sebastiano Seatzu (1997). "Spectral factorization of Laurent polynomials". *Advances in Computational Mathematics*. **7** (4): 429–454. [doi:10.1023/A:1018915407202](https://doi.org/10.1023/A:1018915407202). [S2CID 7880541](https://api.semanticscholar.org/CorpusID:7880541) 1. Aljaž Zalar (2016). "Matrix Fejér–Riesz theorem with gaps". *Journal of Pure and Applied Algebra*. **220** (7): 2533–2548. [arXiv:1503.06034](https://arxiv.org/abs/1503.06034). [doi:10.1016/j.jpaa.2015.11.018](https://doi.org/10.1016/j.jpaa.2015.11.018). [S2CID 119303900](https://api.semanticscholar.org/CorpusID:119303900) 1. Sayed & Kailath 2001, pp. 467–496. 1. Janashia, Lagvilava & Ephremidze 2011, pp. 2318–2326. 1. Bini et al. 2003, pp. 217–227. 1. van der Woude 2014, pp. 214–220. 1. Ephremidze, Lasha (2014). "An Elementary Proof of the Polynomial Matrix Spectral Factorization Theorem". *Proceedings of the Royal Society of Edinburgh, Section A*. **144** (4): 747–751. [CiteSeerX 10.1.1.755.9575](https://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.755.9575). [doi:10.1017/S0308210512001552](https://doi.org/10.1017/S0308210512001552). [S2CID 119125206](https://api.semanticscholar.org/CorpusID:119125206) ## References - Bini, D.A.; Fiorentino, G.; Gemignani, L.; Meini, B. (2003). "Effective Fast Algorithms for Polynomial Spectral Factorization". *Numerical Algorithms*. **34** (2–4): 217–227. [Bibcode:2003NuAlg..34..217B](https://ui.adsabs.harvard.edu/abs/2003NuAlg..34..217B). [doi:10.1023/B:NUMA.0000005364.00003.ea](https://doi.org/10.1023/B:NUMA.0000005364.00003.ea). [ISSN 1017-1398](https://www.worldcat.org/issn/1017-1398) - Böttcher, Albrecht & Halwass, Martin (2013). "Wiener–Hopf and spectral factorization of real polynomials by Newton's method". *Linear Algebra and Its Applications*. **438** (12): 4760–4805. [doi:10.1016/j.laa.2013.02.020](https://doi.org/10.1016/j.laa.2013.02.020) - Dritschel, Michael A. & Rovnyak, James (2010). "The Operator Fejér-Riesz Theorem". *A Glimpse at Hilbert Space Operators*. Basel: Springer Basel. [doi:10.1007/978-3-0346-0347-8_14](https://doi.org/10.1007/978-3-0346-0347-8_14). ISBN 978-3-0346-0346-1. - Grinshpan, Anatolii; Kaliuzhnyi-Verbovetskyi, Dmitry S.; Vinnikov, Victor; Woerdeman, Hugo J. (2016). "Stable and real-zero polynomials in two variables". *Multidimensional Systems and Signal Processing*. **27** (1): 1–26. [arXiv:1306.6655](https://arxiv.org/abs/1306.6655). [Bibcode:2016MSySP..27....1G](https://ui.adsabs.harvard.edu/abs/2016MSySP..27....1G). [doi:10.1007/s11045-014-0286-3](https://doi.org/10.1007/s11045-014-0286-3). [ISSN 0923-6082](https://www.worldcat.org/issn/0923-6082) - Janashia, G; Lagvilava, E; Ephremidze, L (2011). "A New Method of Matrix Spectral Factorization". *IEEE Transactions on Information Theory*. **57** (4): 2318–2326. [arXiv:0909.5361](https://arxiv.org/abs/0909.5361). [Bibcode:2011ITIT...57.2318J](https://ui.adsabs.harvard.edu/abs/2011ITIT...57.2318J). [doi:10.1109/TIT.2011.2112233](https://doi.org/10.1109/TIT.2011.2112233). [ISSN 0018-9448](https://www.worldcat.org/issn/0018-9448) - Sayed, A. H. & Kailath, T. (2001). ["A survey of spectral factorization methods"](http://infoscience.epfl.ch/record/233037). *Numerical Linear Algebra with Applications*. **8** (6–7): 467–496. [doi:10.1002/nla.250](https://doi.org/10.1002/nla.250). [ISSN 1070-5325](https://www.worldcat.org/issn/1070-5325) - Wiener, N. & Masani, P. (1957). "The prediction theory of multivariate stochastic processes: I. The regularity condition". *Acta Mathematica*. **98**: 111–150. [doi:10.1007/BF02404472](https://doi.org/10.1007/BF02404472). [ISSN 0001-5962](https://www.worldcat.org/issn/0001-5962) - van der Woude, Jacob (2014). "A straightforward proof of the polynomial factorization of a positive semi-definite polynomial matrix". *Linear Algebra and Its Applications*. **456**: 214–220. [doi:10.1016/j.laa.2014.02.013](https://doi.org/10.1016/j.laa.2014.02.013) --- Adapted from the Wikipedia article [Polynomial matrix spectral factorization](https://en.wikipedia.org/wiki/Polynomial_matrix_spectral_factorization) by Wikipedia contributors ([contributor history](https://en.wikipedia.org/wiki/Polynomial_matrix_spectral_factorization?action=history)). Available under [Creative Commons Attribution-ShareAlike 4.0 International](https://creativecommons.org/licenses/by-sa/4.0/). Changes may have been made.