Polynomial matrix spectral factorization

• Comment: largely unsourced Seraphim System ^(talk) 11:19, 23 May 2017 (UTC)

---

Polynomial matrices are widely studied in the fields of systems theory and control theory and have seen other uses relating to Stable polynomials. In stability theory, Spectral Factorization has been used to find determinental matrix representations for bivariate stable polynomials and real zero polynomials. A key tool used to study these is a matrix factorization known as either the Polynomial Matrix Spectral Factorization or the Matrix Fejer-Riesz Theorem.

Given a univariate positive polynomial $p(t)$, a polynomial which takes on positive values for any real input $t$, the Fejer-Riesz Theorem yields the polynomial spectral factorization $p(t)=q(t)q({\bar {t}})^{*}$. Results of this form are generically referred to as Positivstellensatz.

Often polynomial matrices show up in a context in which, when viewed as a function from the reals to scalar matrices, have all positive definite matrices in their image. This should be viewed as the matrix-analogue of a real coefficient polynomial who takes on all nonnegative values for real inputs. The Polynomial Matrix Spectral Factorization, also known as the Matrix Valued Fejer-Riesz Theorem, yields a Polynomial Matrix decomposition for such polynomial matrices which is meant to simultaneously be the polynomial analogue of the Cholesky decomposition for scalar matrices and the spectral factorization of a nonnegative real coefficient univariate polynomial. This result was originally proven by Wiener in a more general context which was concerned with integrable matrix-valued functions that also had integrable log determinant. Because applications are often concerned with the polynomial restriction, simpler proofs have appeared since of this specific case. This article follows the recent proof method of Lasha Ephremidzewhich relies only on elementary Linear algebra and Complex analysis.

Spectral Factorization is used extensively in Linear–quadratic–Gaussian control. Because of this application there have been many algorithms to calculate spectral factors. Some modern algorithms focus on the more general setting originally studied by Wiener. In the $1\times 1$ case the problem is known as polynomial spectral factorization, or Fejer-Riesz Theorem, and has many classical algorithms and some modern algorithms with improvements.

Statement

Let $P(t)={\begin{bmatrix}p_{11}(t)&\ldots &p_{1n}(t)\\\vdots &\vdots &\vdots \\p_{n1}(t)&\cdots &p_{nn}(t)\\\end{bmatrix}}$be a polynomial matrix where each entry $p_{ij}(t)$is a complex coefficient polynomial of degree at most $N$. Suppose that for all $t\in \mathbb {R}$ we have $P(t)$ is a positive definite hermitian matrix. Then there exists a polynomial matrix $Q(t)$ such that $P(t)=Q(t)Q(t)^{*}$ for all $t\in \mathbb {R}$. We can furthermore find $Q(t)$ which is nonsingular on the lower half plane.

Extension to Complex Inputs

Note that if $Q(t)={\begin{bmatrix}q_{11}(t)&\ldots &q_{1n}(t)\\\vdots &\vdots &\vdots \\q_{n1}(t)&\cdots &q_{nn}(t)\\\end{bmatrix}}$then $Q({\bar {t}})^{*}={\begin{bmatrix}q_{11}({\bar {t}})^{*}&\ldots &q_{n1}({\bar {t}})^{*}\\\vdots &\vdots &\vdots \\q_{1n}({\bar {t}})^{*}&\cdots &q_{nn}({\bar {t}})^{*}\\\end{bmatrix}}$. When $q_{ij}(t)$ is a complex coefficient polynomial or complex coefficient rational function we have $q_{ij}({\bar {t}})^{*}$is also a polynomial or rational function respectively. For $t\in \mathbb {R}$ we have$$P(t)=Q(t)Q(t)^{*}=Q(t)Q({\bar {t}})^{*}$$Since the entries of $Q(t)Q({\bar {t}})^{*}$ and $P(t)$ are complex polynomials which agree on the real line, they are in fact the same polynomials. We can conclude they in fact agree for all complex inputs.

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 $A$, we are guaranteed by Cholesky decomposition $A=LL^{*}$ where $L$ is a lower triangular matrix. If we don't restrict to lower triangular matrices we can consider all factorizations of the form $A=VV^{*}$. 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=LU$.

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}^{*}\end{bmatrix}}$$Solving these in terms of $a_{ij}$ we get$$l_{11}={\sqrt {a_{11}}}$$$$\mathbf {l} _{21}={\frac {1}{\sqrt {a_{11}}}}a_{12}$$$$L_{22}L_{22}^{*}=A_{22}-{\frac {1}{a_{11}}}a_{12}a_{12}^{*}$$

Since $A$ is positive definite we have $a_{11}$is a positive real number, so it has a square root. The last condition from induction since the right hand side is the Schur complement of $A$, which is itself positive definite.

Decomposition for Rational Matrices

Now consider $P(t)={\begin{bmatrix}p_{11}(t)&\ldots &p_{1n}(t)\\\vdots &\vdots &\vdots \\p_{n1}(t)&\cdots &p_{nn}(t)\\\end{bmatrix}}$where the $p_{ij}(t)$are complex rational functions and $P(t)$ is positive definite hermitian for almost all real $t$. Then by the symmetric 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)^{*}$for real $t$. Once we have that then we can solve for $l_{11}(t),\mathbf {l} _{21}(t)$. Since the 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}$.

Square-Roots of Positive Rational Functions

To prove that there exists rational $q_{11}(t)$ with$p_{11}(t)=q_{11}(t)q_{11}(t)^{*}$, we write $p_{11}(t)=c{\frac {\prod _{i}(x-\alpha _{i})}{\prod _{i}(x-\beta _{i})}}$where $\alpha _{i}\neq \beta _{j}$. Since $P(t)$ is positive definite hermitian for almost all real $t$ we have $p_{11}(t)$ is positive real for almost all real $t$. Letting $x\to \infty$we can conclude that $c$ is real and positive. The numerator and denominator have distinct sets of roots, so all real roots which show up in either must have even multiplicity. We can divide out these real roots to reduce to the case where $p_{11}(t)$ has only complex roots and poles. By hypothesis we have $p_{11}(t)=c{\frac {\prod _{i}(x-\alpha _{i})}{\prod _{i}(x-\beta _{i})}}=c{\frac {\prod _{i}(x-{\bar {\alpha _{i}}})}{\prod _{i}(x-{\bar {\beta _{i}}})}}$. Since all of the $\alpha _{i},\beta _{j}$are complex (and hence not fixed points of conjugation) they both come in conjugate pairs.

Extension to Polynomial Decompositions

To prove the existence of polynomial matrix spectral factorization, we begin with the rational polynomial matrix Cholesky Decomposition and modify it to remove the poles. Namely given $P(t)={\begin{bmatrix}p_{11}(t)&\ldots &p_{1n}(t)\\\vdots &\vdots &\vdots \\p_{n1}(t)&\cdots &p_{nn}(t)\\\end{bmatrix}}$with each entry $p_{ij}(t)$ a complex coefficient polynomial we have rational polynomial matrix $L(t)$ with $P(t)=L(t)L(t)^{*}$for real $t$. Given a rational polynomial matrix $U(t)$ which is unitary valued for real $t$, there exists another decomposition,$P(t)=L(t)L(t)^{*}=(L(t)U(t))(L(t)U(t))^{*}$.

Removing Lower Half Plane Poles

If any entry of $L(t)$ has a pole, $a$, in the lower half plane we multiply by $$U(t)={\text{diag}}(1,\ldots ,{\frac {z-a}{z-{\bar {a}}}},\ldots ,1)$$For real $z$, $|{\frac {z-a}{z-{\bar {a}}}}|=1$ since the numerator and denominator are complex conjugates of each other.

Removing Lower Half Plane Singularities

If $det(L(a))=0$ then there exists a scalar unitary matrix $U$such that $Ue_{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)={\text{diag}}(1,\ldots ,{\frac {z-{\bar {a}}}{z-a}},\ldots ,1)$$$L(t)UU(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.

Extend Analyticity to all of $\mathbb {C}$

After modifications, the decomposition $P(t)=Q(t)Q(t)^{*}$satisfies $Q(t)$ is analytic and invertible on the lower half plane. From our observation in Extension to Complex Inputs, we have

$P(t)=Q(t)Q({\bar {t}})^{*}$for all complex numbers. This implies $Q({\bar {t}})=(P(t)Q(t)^{-1})^{*}$. Since $det(Q(t))$ has no zeroes in the lower half plane, by the Adjugate matrix formula we have $Q(t)^{-1}$is analytic in the lower half plane. Thus the right hand side is analytic on the lower half plane, which implies $Q(t)$ is analytic on the upper half plane. Finally if $Q(t)$ has a pole on the real line then $Q({\bar {t}})^{*}$has the same pole on the real line which contradicts the fact $P(t)$ has no poles on the real line (it is analytic everywhere by hypothesis).

The above shows that $Q(t)$ is analytic and invertible on the lower half plane implies $Q(t)$ is analytic everywhere and hence a polynomial matrix.

Uniqueness

Given two polynomial matrix decompositions which are invertible on the lower half plane$P(t)=Q(t)Q({\bar {t}})^{*}=R(t)R({\bar {t}})^{*}$ we rearrange to $(R(t)^{-1}Q(t))(R({\bar {t}})^{-1}Q({\bar {t}}))^{*}=I$. Since $R(t)$ is analytic on the lower half plane and nonsingular, $R(t)^{-1}Q(t)$is a rational polynomial matrix which is analytic and invertible on the lower half plane. Then by the same argument as above we have $R(t)^{-1}Q(t)$ is in fact a polynomial matrix which is unitary for all real $t$. This means that if $\mathbf {q} _{i}(t)$ is the $i$th row of $Q(t)$then $\mathbf {q} _{i}(t)\mathbf {q} _{i}({\bar {t}})^{*}=1$. For real $t$ this is a sum of non-negative polynomials which sums to a constant, implying each of the summands are in fact constant polynomials. Then $Q(t)=R(t)U$where $U$is a scalar unitary matrix.