Available online at www.sciencedirect.

com

Linear Algebra and its Applications 429 (2008) 11141134

www.elsevier.com/locate/laa

Algorithms for multidimensional spectral factorization

and sum of squares
D. Napp Avelli, H.L. Trentelman
Research Institute for Mathematics and Computing Science, P.O. Box 800, 9700 AV Groningen, The Netherlands

Received 30 October 2006; accepted 7 June 2007

Available online 16 June 2007
Submitted by A. Ran

Abstract

In this paper, algorithms are developed for the problems of spectral factorization and sum of squares
of polynomial matrices with n indeterminates, and a natural interpretation of the tools employed in the
algorithms is given using ideas from the theory of lossless and dissipative systems. These algorithms are
based on the calculus of 2n-variable polynomial matrices and their associated quadratic differential forms,
and share the common feature that the problems are lifted from the original n-variable polynomial context
to a 2n-variable polynomial context. This allows to reduce the spectral factorization problem and the sum of
squares problem to linear matrix inequalities (LMIs), to the feasibility of a semialgebraic set or to a linear
eigenvalue problem.
2007 Elsevier Inc. All rights reserved.

Keywords: Polynomial multidimensional spectral factorization; Two-variable polynomial matrices; Quadratic differential
forms; Dissipativity; Sum of squares; Linear matrix inequalities

1. Introduction

The spectral factorization problem was originally used by Wiener in [16] to obtain a frequency
domain solution to optimal filtering problems. Later it has arisen in different areas of systems
and control, such as the polynomial and behavioral approaches to H control problems, theory
of dissipative systems, and in LQG theory (see for instance [4]). The related problem of sum of
squares (SOS) has appeared earlier and has a venerable history. It has connections with Hilberts

Corresponding author. Tel.: +31 50 3633998; fax: +31 50 3633976.

E-mail addresses: [email protected] (D.N. Avelli), [email protected] (H.L. Trentelman).

0024-3795/$ - see front matter ( 2007 Elsevier Inc. All rights reserved.
doi:10.1016/j.laa.2007.06.003
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1115

17th problem, that he posed at the International Congress of Mathematicians in 1900. Recently,
much attention has been directed to SOS methods in order to test feasibility of semialgebraic sets
[7], and to the problem of finding Lyapunov functions for nonlinear systems [9].
Most of the vast literature on these problems deal with either the 1-dimensional case (i.e., the
case of polynomials in one indeterminate) or the scalar case (as opposed to the matrix case). In
this paper we present a unified framework to address both the problem of spectral factorization
and the problem of SOS for polynomial matrices, giving gentle and systematic algorithms. Also,
a natural interpretation of the tools employed in the algorithms is given using ideas from the
theory of lossless and dissipative systems. In this paper we will pay particular attention to the
theory of dissipative distributed systems, as recently developed in [11]. This theory is underlying
most of our algorithms and proofs, where the problem is lifted from the original n-variable
polynomial context to a 2n-variable polynomial context. The key is that factorizations of 2n-
variable polynomial matrices can essentially be performed by doing factorizations of constant
real symmetric matrices. Similar ideas were used in [14] for spectral factorization of polynomial
matrices in one variable and in [12] for SOS of polynomials in n variables.
The problem of multidimensional spectral factorization is stated as follows. Denote the n-
dimensional indeterminate by = (1 , 2 , . . . , n ). Given a para-hermitian real q q n-variable
polynomial matrix Z( ), i.e. a real n-variable polynomial matrix with the property that Z T ( ) =
Z( ), the problem is to compute another real n-variable polynomial matrix F ( ) (called a spectral
factor) such that Z( ) = F T ( )F ( ). We also address the case when F ( ) is allowed to be a
rational polynomial matrix.
The problem of sum of squares is stated here as follows. Given a real symmetric positive
semidefinite q q n-variable polynomial matrix Z( ), i.e. a real n-variable polynomial matrix
with the property that Z( )T = Z( ) and Z( ) ! 0 for all Rn , the problem is to compute
another n-variable polynomial matrix F ( ) such that Z( ) = F T ( )F ( ).
This paper is organized as follows. Section 2 contains the basic background material on
multidimensional systems, quadratic differential forms and 2n-variable polynomial matrices.
Sections 3 and 4 connect the problem of polynomial spectral factorization with 2n-variable
polynomial matrices and the problem of factorizing a constant matrix that is obtained from solving
a linear matrix inequality (LMI). Also, in Section 4, we reduce the problem of rational spectral
factorization to the problem of finding a feasible point of a semialgebraic set and to a linear
eigenvalue problem. Finally, in Section 5, we connect the sum of squares problem to 2n-variable
polynomial matrices and linear matrix inequalities.

2. nD multidimensional systems and 2n-variable polynomial matrices

In the behavioral approach to system theory, the behavior is a subset of the space WT consisting
of all trajectories from T, the indexing set, to W, the signal space. In this paper we consider
systems with T = Rn (from which the terminology nD-system derives) and W = Rq . We call
B a linear differential nD behavior if it is the solution set of a system of linear, constant-coefficient
partial differential equations, more precisely, if B is the subset of C (Rn , Rq ) (the set of smooth
functions) consisting of all solutions to
! "
d
R w = 0, (1)
dx
where R is a polynomial matrix in the n-dimensional indeterminate = (1 , 2 , . . . , n ), and
d ! !
dx = ( !x1 , . . . , !xn ). We call (1) a kernel representation of B and write B = ker(R). In general,
1116 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

there are many other ways to represent an nD system. Let B be the subset of C (Rn , Rq )
consisting of all functions w for which there exits C (Rn , Rq ) such that
! "
d
w=M . (2)
dx
d
Here M is a polynomial matrix in the indeterminate = (1 , 2 , . . . , n ), and again dx = ( !x!1 , . . . ,
!
!xn
). We call (2) an image representation of B and the variable is called the latent variable. In
this case we write B = im(M). Image representations often appear in physics, where the latent
variables in a such a representation are called potentials. An important propery of behaviors is
controllability, see [10]. It can be shown that a behavior admits an image representation if and
only if it is controllable.
In many modelling and control problems for linear systems it is necessary to study quadratic
functionals of the system variables and their derivatives, for example, in linear quadratic optimal
control and H -control. We will use polynomial matrices in 2n variables as a tool to express
quadratic functionals of functions of n variables (see [17,11]). We will now review the notational
conventions for quadratic differential forms and discuss the results that are relevant to the problems
of multivariable spectral factorization and sums of squares.
For convenience, denote x := (x1 , . . . , xn ). Multi-indices are denoted by k := (k1 , . . . , kn ) and
l := (l1 , . . . , ln ), and indeterminates by := (1 , . . . , n ) and := (1 , . . . , n ). We also denote
k := 1k1 2k2 nkn and k := 1k1 2k2 nkn . Let Rqq [, ] denote the set of real polynomial
q q matrices in the 2n indeterminates and ; that is, an element of Rqq [, ] is of the form
#
!(, ) = !k,l k l , (3)
k,l
qq
where !k,l R ; the sum ranges over the multi-indices k, l Nn , and is assumed to be finite.
The 2n-variable polynomial matrix !(, ) is called symmetric if !(, ) = !(, )T , equiva-
lently if !k,l = !Tl,k for all l and k. In this paper we restrict our attention to the symmetric elements
qq
in Rqq [, ], and denote this subset by Rs [, ]. Any symmetric ! induces a quadratic
functional

Q! : C (Rn , Rq ) C (Rn , R),

# ! d k w "T dl w
Q! (w) := !k,l .
dx k dx l
k,l

dk dk !k1 !kn dl
where the kth derivative operator dx k
is defined as dx k
:= k k (similarly for dx l
). We will
!x1 1 !xnn
call Q! the quadratic differential form (in the following abbreviated with
$ QDF) associated with
!. For a given symmetric 2n-variable polynomial matrix !(, ) = k,l !k,l k l , the n-tuple
k Nn is called the degree of the monomial k := 1k1 2k2 nkn . In the 1-variable case (n = 1)
it is of course clear how to order the monomials k with increasing degree. In that case one can
write

!0,0 !0,1 !0,N Iq
!1,0 !1,1 !1,N
Iq
!(, ) = (Iq , Iq , . . . , N Iq ) .
.. ..

. . . . ,
.. .. ..
!N,0 !N,1 !N,N N Iq
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1117

where the symmetric matrix in the middle is called the coefficient matrix of !(, ), denoted by
mat(!). In order to define the coefficient matrix mat(!) for symmetric 2n-variable polynomial
matrices !(, ) for general n > 1, we first need to introduce an ordering on the monomials
1k1 2k2 nkn , equivalently, on the n-tuples of degrees (k1 , k2 , . . . , kn ). Many orderings are
possible, here we choose the anti-lexicographic ordering, which is defined as follows:
Given (a1 , a2 , . . . , an ), (b1 , b2 , . . . , bn ) Nn we define: (a1 , a2 , . . . , an ) < (b1 , b2 , . . . , bn )
if and only if the rightmost nonzero entry of (a1 b1 , a2 b2 , . . . , an bn ) is < 0.
As an example, let n = 2, and consider the set of all 2-tuples (a1 , a2 ) with 0 " a1 " N1 , 0 "
a2 " N2 with N1 , N2 positive integers. The 2-tuples in this set are ordered as follows:

(0, 0) < (1, 0) < (2, 0) < < (N1 , 0)

< (0, 1) < (1, 1) < (2, 1) < < (N1 , 1)
.. .. .. ..
. . . .
< (0, N2 ) < (1, N2 ) < (2, N2 ) < < (N1 , N2 ).
qq
Using the above anti-lexicographic ordering, for a given symmetric !(, ) Rs [, ] a unique
coefficient matrix mat(!) is defined, and mat(!) is symmetric. The matrix mat(!) has as block
entries the coefficients !k,l , with k and l ordered according to the given ordering. We will explain
this now in more detail for n = 2. Let
N1
# N2
#
!(, ) = !(k1 ,k2 )(l1 ,l2 ) 1k1 2k2 1l1 1l2 .
k1 ,l1 =0 k2 ,l2 =0

Define V (1 ) = (I, 1 I, . . . , 1N1 I ), with I the q q identity matrix. Then !(, ) can be written
as
(0,0)
! !(0,1) !(0,N2 ) V (1 )
!(1,0) !(1,1) !(1,N2 ) V (1 )
N2 ,
!(, ) = (V (1 ), 2 V (1 ), . . ., 2 V (1 )) . .. .. .. ..
.. . . . .
!(N2 ,0) !(N2 ,1) !(N2 ,N2 ) N2 V (1 )
(4)

where the (N1 + 1)q (N1 + 1)q matrices !(i,j ) are defined by

!(0,i)(0,j ) !(0,i)(1,j ) !(0,i)(N1 ,j )
!(1,i)(0,j ) !(1,i)(1,j ) !(1,i)(N1 ,j )

!(i,j ) := .. .. .. .. .
. . . .
!(N1 ,i)(0,j ) !(N1 ,i)(1,j ) !(N1 ,i)(N1 ,j )

Note that !(i,j ) has as block entries the coefficient matrices !(k1 ,i)(l1 ,j ) of !(, ) with multi-
indices (k1 , i) and (l1 , j ) ordered in the given ordering. The matrix in the middle of (4) is
the coefficient matrix mat(!) of !(, ). We will denote (V (1 ), 2 V (1 ), . . . , 2N2 V (1 )) by
V2 (1 , 2 ). Observe that
. . .
V2 (1 , 2 ) = (I, 1 I, . . . , 1N1 I ..2 I, 2 1 I, . . . , 2 1N1 I .. . . . ..2N2 I, 2N2 1 I, . . . , 2N2 1N1 I ),
1118 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

and that the monomials 1k1 2k2 appearing in this matrix from the left to the right are indeed
ordered according to the given ordering. As shorthand notation, we will sometimes write mat(!) =
{!(i,j ) }i,j =0,1,...,N2 .
Of course, in the same way we can define the coefficient matrix of a given n-variable polynomial
matrix F ( ). If F ( ) = %k Fk k , then the anti-lexicographic ordering on the multi-indices k Nn
uniquely defines the coefficient matrix of F ( ), which will be denoted by mat(F ).
For a given 2n-variable polynomial matrix, factorizations of the coefficient matrix will give
rise to factorizations of the 2n-variable polynomial matrix. Our algorithms will actually reduce
the problems of spectral factorization and sum of squares to factorization problems for these
coefficient matrices, which are of course constant real matrices. It is important to note that the
qq
correspondence between Rs [, ] and the set of real symmetric matrices is bijective and that
the size of mat(!) depends on the highest monomial degree of and in !(, ).
qq
We will also consider vectors & (Rs [, ])n , i.e. n-tuples of symmetric 2n-variable poly-
qq
nomial matrices & = (&1 , . . . , &n ) with &i Rs [, ]. In the same way that ! induces a
QDF, & induces a vector of quadratic differential forms (VQDF), defined as

Q" : C (Rn , Rq ) (C (Rn , R))n ,

+ ,
Q" (w) := Q"1 (w), Q"2 (w), . . ., Q"n (w) .

We review the notion of divergence of a VQDF (see [11]). Given a VQDF Q" as above, its
divergence is defined as the QDF
! !
(divQ" )(w) := Q"1 (w) + + Q"n (w) (5)
!x1 !xn
for w C (Rn , Rq ).
It was shown in [11] that the 2n-variable polynomial matrix associated with the divergence of
a VQDF Q" is given by the 2n-variable polynomial matrix " defined by

"(, ) := (1 + 1 )"1 (, ) + + (n + n )"n (, ).

In this paper we are interested in mat("), i.e., in the underlying real symmetric coefficient matrix.
For the sake of simplicity consider again the case n = 2. First, for i = 1, 2, define the i-block
right-shift and i-block downward-shift operators, i,R and i,D respectively, as follows: with
mat(!) = {!(i,j ) }i,j =0,1,...,N2 we define
-! ".
0 !(i,j )
1,R (mat(!)) = ,
0q 0 i,j =0,1,...,N2
-! ".
0 0q
1,D (mat(!)) = ,
!(i,j ) 0 i,j =0,1,...,N2
! "
0 mat(!)
2,R (mat(!)) = ,
0(N1 +1)q 0
! "
0 0(N1 +1)q
2,D (mat(!)) = .
mat(!) 0

Here 0q denotes the q q zero matrix, and 0(N1 +1)q the (N1 + 1)q (N1 + 1)q zero matrix.
The sizes of the other 0-matrices appearing in the above should be apparent from the context. It
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1119

is straightforward to verify that mat((1 + 1 )!(, )) = (1,D + 1,R )(mat(!)) and mat((2 +
2 )!(, )) = (2,D + 2,R )(mat(!)). Thus, if " = ("1 , "2 ), we find that
= (1,D + 1,R )(mat("1 )) + (2,D + 2,R )(mat("2 )).
mat(")
We now explain how this generalizes to general n > 1. Let ! be a symmetric 2n-variable poly-
nomial matrix with highest monomial degree (N1 , N2 , . . . , Nn ). In order to express !(, )
in terms of its coefficient matrix using monomials in the lexicographic ordering, we define
V1 (1 ) := V (1 ), and in addition to V2 (1 , 2 ) we define recursively for k = 2, 3, . . . , n:
. . .
Vk (1 , 2 , .., k ) := (Vk1 (1 , 2 , .., k1 )..k Vk1 (1 , 2 , .., k1 ).. . . . ..kNk Vk1 (1 , 2 , .., k1 )).
The monomials appearing from left to right in the matrix Vn (1 , 2 , . . . , n ) are then ordered in
the anti-lexicographic ordering, and therefore we have
!(, ) = Vn (1 , 2 , . . . , n )mat(!)Vn (1 , 2 , . . . , n )T .
In this way we can see that multiplication of !(, ) by k and k corresponds to appropriate
downward-shift and right-shift of blocks within the coefficient matrix mat(!), respectively. These
shift operators are called the k-block downward-shift and k-block right-shift operators, k,D and
k,R (k = 1, 2 . . . , n), respectively. Thus, for " = ("1 , "2 , . . . , "n ), we obtain:
= (1,D + 1,R )(mat("1 )) + (2,D + 2,R )(mat("2 ))
mat(")
+ + (n,D + n,R )(mat("n )).

We conclude this section by noting that the notion of divergence of a VQDF can be given a physical
interpretation in the context of dissipative nD systems (see [11]). Indeed, if B is a controllable nD
qq
behavior with image representation B = im(M), and ! Rs [, ], then the VQDF Q" with
qq
" (Rs [, ]) is said to be a storage function for B with respect Q! if
n

(divQ" )() " Q! (w) (6)

for all C (Rn , Rq ) and w = M( dx d
). If such storage function exists, then B is called
dissipative with respect to Q! . If the first coordinate x1 designates time t, and the remaining
x2 , . . . , xn are space coordinates, then the inequality (6) can be rewritten as
! ! " " / 0
! d ! ! !
Q"1 () " Q! M Q"2 () + Q"3 () + + Q"n () .
!t dx !x2 !x3 !xn
This can be interpreted as saying that the change in stored energy !!t Q"1 () in an infinitesimal
d
volume does not exceed the difference between the supply Q! (M( dx )) into the infinitesimal
volume and the energy lost by the volume due to energy flux flowing out of the volume in the
directions x2 , . . . , xn . The difference between the right hand side and the left hand side is the rate
at which energy is dissipated within the volume. This difference is called the dissipation rate.

3. Lifting n variable to 2n variable polynomial matrices

In the section following the present one, we show how the problem of multi-dimensional
spectral factorization can be reduced to factorization of a real symmetric constant matrices. This
result will be achieved by lifting the spectral factorization problem to a 2n-variable polynomial
context, i.e., by associating with the to-be-factored n-variable polynomial matrix Z( ) a suitable
2n-variable polynomial matrix. Lifting the problem to a 2n-variable polynomial matrix context
1120 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

allows us to formulate the problem of spectral factorization in terms of the related coefficient
matrices. In the present section we will discuss this lifting procedure. $
Let Z( ) be a real para-hermitian n-variable polynomial matrix, Z( ) = k Zk k with Zk
qq
R . Note that Z( ) is para-hermitian if and only if the coefficient matrices Zk satisfy
T
Z(k1 ,k2 ,...,kn )
= (1)k1 +k2 ++kn Z(k1 ,k2 ,...,kn )
for all multi-indices (k1 , k2 , . . . , kn ). In the following, we will associate with Z( ) symmetric,
2n-variable polynomial matrices !(, ) with the property that
!(, ) = Z( ). (7)
For a given Z( ) there are always infinitely many !s such that this property holds. For example,
whenever ! satisfies (7) then also ! (, ) := !(, ) + (1 + 1 )#1 (, ) + (2 + 2 )#2 (, ) +
qq
+ (n + n )#n (, ) satisfies (7), for any choice of #1 , . . . , #n Rs [, ]. One possible
choice of ! such that (7) holds is given by
1 T
!(, ) := (Z ( ) + Z()).
2
Since !(, )T = 21 (Z() + Z T ( )) = !(, ), !(, ) is indeed symmetric. Using Z T ( ) =
Z( ), ! satisfies (7). Note that for this particular choice of !(, ), the highest monomial degree
of and occurring in the entries of !(, ) is equal to the highest monomial degree occurring
in Z( ). This is not true for all choices of !(, ).
In the following, we will establish a characterization of all symmetric 2n-variable polynomial
matrices !(, ) such that !(, ) = Z( ). For the special case that n = 1 this was done in
[14]. In fact, there the following was proven:

Proposition 3.1. Let Z( ) be a para-hermitian 1-variable $ polynomial matrix, Z( ) = Z0 +

Z1 + Z2 2 + ZM M , with ZM =/ 0. Let !(, ) = k,j !k,j k j be a symmetric two-
variable polynomial matrix. Then !(, ) = Z( ) if and only if !0,k !1,k1 + !2,k2
+ (1)k !k,0 = Zk for all k = 0, 1, . . . , M.

In terms of the coefficient matrix mat(!), this requires that the M + 1 anti-diagonals, with an
appropriate sign-pattern, add up to the coefficients of Z( ).
In the present paper, we will concentrate first on the case n = 2, and comment later on how
to generalize this to the general case n > 2. Let a para-hermitian 2-variable polynomial matrix
Z(1 , 2 ) be given by
M1 #
# M2
Z(1 , 2 ) = Zk,l 1k 2l .
k=0 l=0
On the other hand, let !(1 , 2 , 1 , 2 ) be a symmetric 4-variable polynomial matrix given by
N1
# N2
#
!(1 , 2 , 1 , 2 ) = !(k1 ,k2 )(l1 ,l2 ) 1k1 2k2 1l1 2l2 .
k1 ,l1 =0 k2 ,l2 =0

Clearly,
N1
# N2
#
!(1 , 2 , 1 , 2 ) = !(k1 ,k2 )(l1 ,l2 ) (1)k1 +k2 1k1 +l1 2k2 +l2 . (8)
k1 ,l1 =0 k2 ,l2 =0
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1121

Thus, a necessary condition for !(, ) = Z( ) is that 2N1 ! M1 and 2N2 ! M2 . Therefore,
for notational convenience, we will write
2N1 #
# 2N2
Z(1 , 2 ) = Zk,l 1k 2l ,
k=0 l=0
where we define Zk,l := 0 for k = M1 + 1, . . . , 2N1 or l = M2 + 1, . . . , 2N2 . We will describe
now the relations between the Zk,l and the !(k1 ,k2 )(l1 ,l2 ) that are necessary and sufficient for
!(, ) = Z( ). Recall
(0,0)
! !(0,1) !(0,N2 )
!(1,0) !(1,1) !(1,N2 )

mat(!) = . . .. .. ,
.. .. . .
!(N2 ,0) !(N2 ,1) !(N2 ,N2 )
where for i, j = 0, 1, . . . , N1 we have

!(0,i)(0,j ) !(0,i)(1,j ) !(0,i)(N1 ,j )
!(1,i)(0,j ) !(1,i)(1,j ) !(1,i)(N1 ,j )

!(i,j ) := .. .. .. .. .
. . . .
!(N1 ,i)(0,j ) !(N1 ,i)(1,j ) !(N1 ,i)(N1 ,j )
We first consider the Zk,0 , k = 0, 1, . . . , 2N1 . It follows from (8) that these coefficient matrices
are determined by the block !(0,0) , in particular by taking the sum of the blocks on the 2N1 + 1
anti-diagonals of this matrix, with an appropriate sign pattern. Note that

!(0,0)(0,0) !(0,0)(1,0) !(0,0)(N1 ,0)
!(1,0)(0,0) !(1,0)(1,0) !(1,0)(N1 ,0)

!(0,0) := .. .. .. .. .
. . . .
!(N1 ,0)(0,0) !(N1 ,0)(1,0) !(N1 ,0)(N1 ,0)
The conditions are:

Zk,0 = !(0,0)(k,0) !(1,0)(k1,0) + + (1)k1 !(k1,0)(1,0) + (1)k !(k,0)(0,0)

(k = 0, 1, . . . , N1 ),
ZN1 +k,0 = (1)k !(k,0)(N1 ,0) + (1)k+1 !(k+1,0)(N1 1,0) +
+(1)N1 1 !(N1 1,0)(k+1,0) + (1)N1 !(N1 ,0)(k,0) (k = 1, 2, . . . , N1 ).

In particular, Z0,0 = !(0,0)(0,0) , Z1,0 = !(0,0)(1,0) !(1,0)(0,0) , Z2,0 = !(0,0)(2,0) !(1,0)(1,0) +

!(2,0)(0,0) up to, finally, Z2N1 ,0 = (1)N1 !(N1 ,0)(N1 ,0) .
Next, we consider the Zk,l , k = 0, 1, . . . , 2N1 , first for l = 1, 2, . . . , N2 . These turn out to be
determined by the anti-diagonal blocks !(0,l) , !(1,l1) , !(2,l2) , . . . , !(l1,1) , !(l,0) of mat(!).
The easiest way to visualize the conditions are by forming a matrix $l defined by

0 0 0 !(0,l)
0 0 !(1,l1) 0

$l := . .. .. ,
.. . .
!(l,0) 0 0 0 0
with blocks !(i,li) on the main anti-diagonal, and zeroes elsewehere. Starting in the upper right
corner at !(0,l) , going down to the lower left corner at !(l,0) one can form 2N1 + 1 anti-diagonals
1122 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

with blocks !(k1 ,k2 )(l1 ,l2 ) . By taking the sum of the blocks on the kth anti-diagonal, with appropriate
sign pattern, one obtains the Zk,l , for k = 0, 1, . . . , 2N1 . The sign of each term is determined by
(1)k1 +k2 .
For example, Zk,1 (k = 0, 1, . . . , 2N1 ) is determined by
! "
0 !(0,1)
$1 = .
!(1,0) 0
Indeed, Z0,1 = !(0,0)(0,1) !(0,1)(0,0) , Z11 = !(0,0)(1,1) !(1,0)(0,1) !(0,1)(1,0) + !(1,1)(0,0) ,
etc.
Finally we consider the Zk,N2 +l , k = 0, 1, . . . , 2N1 , for l = 1, 2, . . . , N2 . These are determined
by the anti-diagonal blocks !(l,N2 ) , !(l+1,N2 1) , !(l+2,N2 2) , . . . , !(N2 1,l+1) , !(N2 ,l) of mat(!).
We form a matrix $l defined by

0 0 0 !(l,N2 )
0
0 !(l+1,N2 1) 0
$l := . . .. ,
.. .. .
!(N2 ,l) 0 0 0 0
with blocks !(l+i,N2 i) on the main anti-diagonal, and zeroes elsewehere. Starting in the upper
right corner at !(l,N2 ) , going down to the lower left corner at !(N2 ,l) one can form 2N1 + 1
anti-diagonals with blocks !(k1 ,k2 )(l1 ,l2 ) . Again by taking the sum of the blocks on the kth anti-
diagonal, with appropriate sign pattern, one obtains the Zk,N2 +l , for k = 0, 1, . . . , 2N1 . The sign
of each term is determined by (1)k1 +k2 . For example, Z2N1 ,2N2 , determined by !(N1 ,N2 ) , is equal
to (1)N1 +N2 !(N1 ,N2 )(N1 ,N2 ) .

Example 3.1. As a simple example, consider the case that q = 1 and Z(1 , 2 ) is the scalar 2-
variable polynomial given by Z(1 , 2 ) = 12 22 + 21 2 12 + 1. By the above considerations, it
is possible to find a scalar 4-variable polynomial matrix !(1 , 2 , 1 , 2 ) with highest monomial
degree (N1 , N2 ) = (1, 1). The (unknown) coefficient matrix mat(!) is therefore a symmetric
4 4 matrix:

!(0,0)(0,0) !(0,0)(1,0) !(0,0)(0,1) !(0,0)(1,1)
!(1,0)(0,0) !(1,0)(1,0) !(1,0)(0,1) !(1,0)(1,1)
mat(!) = !(0,1)(0,0) !(0,1)(1,0) !(0,1)(0,1) !(0,1)(1,1) .

!(1,1)(0,0) !(1,1)(1,0) !(1,1)(0,1) !(1,1)(1,1)

The conditions for Z( ) = !(, ) then become:

Z0,0 = !(0,0)(0,0) ,
Z1,0 = !(0,0)(1,0) !(1,0)(0,0) ,
Z2,0 = !(1,0)(1,0) ,
Z0,1 = !(0,0)(0,1) !(0,1)(0,0) ,
Z1,1 = !(0,0)(1,1) !(1,0)(0,1) !(0,1)(1,0) + !(1,1)(0,0) ,
Z2,1 = !(1,0)(1,1) + !(1,1)(1,0) ,
Z0,2 = !(0,1)(0,1) ,
Z1,2 = !(0,1)(1,1) + !(1,1)(0,1) ,
Z2,2 = !(1,1)(1,1) .
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1123

In our example, Z0,0 = 1, Z2,0 = 1, Z1,1 = 2, Z2,2 = 1, and the remaining Zk,l are 0. One
particular choice of mat(!) is therefore given by

1 0 0 1
0 1 0 1
mat(!) = 0 0 0 2 .
(9)
1 1 2 1

Pre- and post-multiplying with (1, 1 , 2 , 1 2 ) and (1, 1 , 2 , 1 2 )T yields the corresponding
!(1 , 2 , 1 , 2 ).

In [14], for a given para-hermitian 1-variable polynomial matrix Z( ), an explicit formula

for a minimal degree symmetric !(, ) satisfying !(, ) = Z( ) was obtained. In fact, if
Z( ) = Z0 + Z1 + Z2 2 + ZM M , with ZM = / 0, and M even, then a 2-variable polynomial
matrix of minimal degree is given in terms of its coefficient matrix by

2Z0 Z1 Z2 Z M 1 ZM
2 2
ZT 0 0 0 Z M +1
1 2

T
Z2 0 0 0 Z M +2
1 2
mat(!) =
.. .. .. . . .
. .
. .
(10)
2 . . . . . .
T M
Z M 1 0 0 0 (1) 2 1 ZM1
2 M M

Z TM Z TM Z TM (1) 2 1 ZM1
T 2(1) 2 ZM
2 2 +1 2 +2

Note that the two-variable polynomial matrix ! defined in this way has degree M 2 . A related !,
with degree M+1 2 , can be defined for the case that M is odd.
We will now extend this result to the case n = 2. Let Z( ) be a para-hermitian 2-variable
$ 1 $M2
q q polynomial matrix, Z(1 , 2 ) = M k=0 l=0 Zk,l 1 2 , with M1 , M2 both even. For j =
k l

0, 1, 2, . . . , M2 , define

Z0,j Z1,j Z M1 1,j Z M1 ,j
2 2
0 0 0 Z M1 +1,j

2
0 0 0 Z M1 +2,j
Zj := 2
,
.
. .
.. . .. .
.. .
..
.
M1
0 0 0 (1) 2 ZM1 ,j
Also define
1
!(0,0) := (Z0 + Z0T ),
2
1 M2
!(0,j ) := Zj , j = 1, 2, . . . , ,
2 2
1 M2
!(j,0) := ZjT , j = 1, 2, . . . , ,
2 2
M2 M2
!(i, 2 ) := (1)i Z M2 +i , i = 1, 2 . . . , ,
2 2
1124 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

M2 M2
!( 2 ,i) := (1)i Z TM2 , i = 1, 2 . . . , ,
2 +i 2
(
M2 M2 1 M2
T
! 2 , 2 ) := (1) 2 (ZM2 + ZM ).
2 2

By applying the formulas obtained earlier in this section, one finds that if we take
M2 M2
!(0,0) !(0,1) !(0, 2 1) !(0, 2 )
M2
!(1,0) 0 0 !(1, 2 )

.. .. .. .. ..

mat(!) = 1 . . . . . ,
2 1 2
M2 1,0 M2 M2
1, 2
! 2 0 2 0 ! 12
1 1 2 2
M2 M2 M2 M2 M2
2 , 2 1
M2
2 ,1 2 , 2
!( 2 ,0) ! ! !
then !(1 , 2 , 1 , 2 ) satifies !(1 , 2 , 1 , 2 ) = Z(1 , 2 ). The highest monomial degree of
! is ( M21 , M22 ), which corresponds to mat(!) having size ( M21 + 1)( M22 + 1)q. Clearly, mat(!)
has minimal size over all ! such that !(, ) = Z( ). In a similar manner, if M1 and M2 are
odd, then ! can be found with coefficient matrix of minimal size ( M12+1 + 1)( M22+1 + 1)q. If M1
is even and M2 is odd then the minimal size is ( M21 + 1)( M22+1 + 1)q, and if M1 is odd and M2
is even the minimal size is ( M12+1 + 1)( M22 + 1)q.
All of the above can be generalized to the general case n > 1 by applying similar ideas to
the more complicated block structure that was described at the end of the previous section. The
notation however becomes rather cumbersome. We omit the details here.

4. Spectral factorization

In this section we will present algorithms for multidimensional spectral factorization. We

distinguish two different spectral factorization problems. In the first one we will search for spectral
factors which are polynomial matrices and reduce the problem to a linear matrix inequality. In the
second case we will allow the spectral factors to be rational matrices, and connect it to a linear
eigenvalue problem, and to a problem of finding a feasible point of a semialgebraic set.

Theorem 4.1. Let Z( ) be a q q para-hermitian n-variable polynomial matrix. Let !(, )

Rqq [, ] be any symmetric 2n-variable polynomial matrix such that !(, ) = Z( ). Then
the following statements are equivalent:

(i) Z( ) admits a spectral factorization, i.e. there exists a positive integer r and a r q
n-variable polynomial matrix F ( ) such that

Z( ) = F T ( )F ( ). (11)

(ii) There exists an n-tuple of symmetric 2n-variable polynomial matrices "(, ) =

qq
("1 (, ), . . . , "n (, )), with "i Rs [, ], i = 1, . . . , n, such that
! 0.
mat(! ") (12)

(iii) There exists a symmetric 2n-variable polynomial matrix 3

!(, ) such that 3
!(, ) = Z( )
and mat(!) ! 0.
3
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1125

Assume that any of these conditions hold. Then an F such that (11) holds can be computed as
follows: find "(, ) = ("1 (, ), . . ., "n (, )), such that (12) holds, and factorize
=F
mat(! ") 4T F
4, (13)

where F 4 is a constant matrix with full row rank, say r. Then the polynomial matrix F ( ) with
4 (i.e., mat(F ) = F
coefficient matrix F 4) satisfies (11).

Proof. (i) (ii) Clearly !(, ) F T ( )F ( ) = 0. By [11, Theorem 4], there exists a vec-
tor of 2n-variable polynomial matrices "(, ) = ("1 (, ), . . ., "n (, )) with "i Rqq [, ]
such that !(, ) F T ( )F () = "(, ) = (1 + 1 )"1 (, ) + + (n + n )"n (, ).
This equality can be written, in terms of the associated coefficient matrices as mat(!) F 4T F4=
4 4T
mat("), where F is the coefficient matrix of F ( ). This implies (12) since F F ! 0.
4
(ii) (i) Since mat(! ") is a symmetric positive semi definite matrix we can factorize
4T 4
it as mat(! ") = F F . Now let F ( ) be the n-variable polynomial matrix with coefficient
matrix F
4. Then we obtain !(, ) "(, ) = F T ( )F (). By taking = and = we
T
then obtain Z( ) = !(, ) = F ( )F ( ).
!(, ) := F T ( )F ().
(i) (iii) Define 3
(iii) (i) Factor mat(3
!) = F 4T F
4 and define F ( ) as the n-variable polynomial matrix such
that mat(F ) = F . #
4

Remark 4.1. Condition (ii) above can be reformulated in terms of the underlying QDFs as
div(Q" (w)) " Q! (w) for all w C (Rn , Rq ), equivalently, the nD system with behavior B =
C (Rn , Rq ) is dissipative with respect to the supply rate Q! , and Q" is a storage function. Thus,
the idea of the theorem is to compute a spectral factor F ( ) of Z( ) by means of computing
a storage function Q" for the Q! -dissipative system C (Rn , Rq ). In fact, F ( dx d
)w2 is the
corresponding dissipation rate, see also [11].

The central issue is that the inequality (12) is in fact a linear matrix inequality, and a solution
can be computed, for instance, using the LMI Toolbox in Matlab.
In [14], the above theorem was used for spectral factorization of 1-variable polynomial matrices.
Here, we will now take a closer look at the case n = 2. In this case, for a given !(1 , 2 , 1 , 2 )
with highest monomial degree (N1 , N2 ), the size of mat(!) is equal to q(N1 + 1)(N2 + 1), so the
sizes of the unknowns mat("1 ) and mat("2 ) are qN1 (N2 + 1) and q(N1 + 1)N2 , respectively.
The LMI (12) then becomes:
mat(!) 1,R (mat("1 )) 1,D (mat("1 )) 2,R (mat("2 )) 2,D (mat("2 )) ! 0.
If we partition the unknown mat("1 ) as
(i,j )
mat("1 ) = {"1 }i,j =0,1,...,N2 ,
(i,j )
with "1 of size qN1 qN1 , then we have
-! (i,j ) ".
0 "1
1,R (mat("1 )) = ,
0q 0 i,j =0,1,...,N2
-! ".
0 0q
1,D (mat("1 )) = (i,j ) ,
"1 0 i,j =0,1,...,N 2
1126 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134
! "
0 mat("2 )
2,R (mat("2 )) = ,
0(N1 +1)q 0
! "
0 0(N1 +1)q
2,D (mat("2 )) = .
mat("2 ) 0

For general n > 2, the linear matrix inequality (12) involves all k-block downward and right-shift
operators k,D and k,R (k = 1, 2, . . . , n) and takes the form

mat(!) (1,D + 1,R )(mat("1 )) (2,D + 2,R )(mat("2 ))

(n,D + n,R )(mat("n )) ! 0.

5 ) has highest monomial degree (N1 , N2 , . . . , Nn ), then mat("i ) has size ni :=

If !(,
qNi nj=1,j =i
/ (Nj + 1). Since the "i , equivalently the matrices mat("i ), can always be taken to
$
be symmetric, the actual number of unknowns in the LMI (12) is equal to ni=1 ni (n2i +1) .

Example 4.1. We continue with Example 3.1 here. Take !(1 , 2 , 1 , 2 ) with mat(!) given by
(9). Since the highest monomial degree (N1 , N2 ) = (1, 1), the unknowns mat("1 ) and mat("2 )
both have size 2 2. Write
! " ! "
a b p q
mat("1 ) = , mat("2 ) = .
b c q r
We have

0 a 0 b 0 0 0 0
0 0 0 0 a 0 b 0
1,R (mat("1 )) =
0
, 1,D (mat("1 )) = ,
b 0 c 0 0 0 0
0 0 0 0 b 0 c 0

0 0 p q 0 0 0 0
0 0 q r 0 0 0 0
2,R (mat("2 )) =
0
, 2,D (mat("2 )) = .
0 0 0 p q 0 0
0 0 0 0 q r 0 0

Thus the LMI in the unknowns a, b, c, p, q, r becomes

1 a p 1+b+q
a 1 b+q 1+r
! 0.
p b+q 0 2+c
1+b+q 1+r 2+c 1+c
A solution is obtained by taking a = 1, b, p, q, r = 0, c = 2. Indeed, with these values we
obtain

1 1 0 1
1 1 0 1
,
0 0 0 0
1 1 0 1

which can be factored as (1101)T (1101). By multiplying (1101) with the vector of monomials
(11 2 1 2 )T , this yields a spectral factor
F (1 , 2 ) = 1 + 1 + 1 2 .
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1127

In the first part of this section we have dealt with factorization of polynomial matrices, where
the spectral factors were again required to be polynomial matrices. In general, for a given para-
hermitian polynomial matrix, a necessary condition for the existence of a polynomial spectral
factor is that Z(i) ! 0 for all Rn . For the case of one indeterminate this is also a sufficient
condition, and several algorithms exist for obtaining polynomial spectral factors, see [2,4,6,13,14].
For n > 1 the condition Z(i) ! 0 for all Rn is no longer sufficient for the existence of a
polynomial spectral factor. This situation changes if we allow the spectral factor F ( ) to be a
rational matrix, i.e., F ( ) Rrq ( ). In that case, the requirement Z(i) ! 0 for all Rn is
a necessary and sufficient condition.

Theorem 4.2. Let Z( ) be a q q para-hermitian n-variable polynomial matrix. Let !(, )

Rqq [, ] be any symmetric 2n-variable polynomial matrix such that !(, ) = Z( ). Then
the following three statements are equivalent:

(i) There exists an integer r and an n-variable rational matrix F ( ) Rrq ( ) such that
Z( ) = F T ( )F ( ). (14)
(ii) There exists an n-tuple of symmetric 2n-variable polynomial matrices "(, ) =
qq
("1 (, ), . . . , "n (, )) with "i Rs [, ], i = 1, . . . , n, and a polynomial p R[ ]
such that
! 0,
mat(! ") (15)
with ! (, ) := !(, )p( )p();
(iii) Z(i) ! 0 for all Rn .

Assume that any of these conditions hold. Then an F such that (14) holds can be computed as
follows: find a "(, ) = ("1 (, ), . . ., "n (, )) and a polynomial p( ), such that (15) holds,
and factorize
=D
mat(! ") 4T D,
4 (16)
where D4 is a constant matrix with full row rank, say r. Define D( ) as the polynomial matrix
4 Finally define F ( ) := p( )1 D( ).
4 (i.e., mat(D) = D).
with coefficient matrix D

Proof. The equivalence of (i) and (iii) is proved in [11]. ((i) (ii)) Let the polynomial p( ) be
the least common multiple of the denominators in the entries of F ( ). Then obviously F ( ) =
p( )1 D( ) for some polynomial matrix D( ). Now define 3 !(, ) := !(, )p( )p()
D T ( )D(). Since 3!(, ) = 0 there exists "(, ) = ("1 (, ), .., "n (, )) with "i
qq
Rs [, ], i = 1, . . . , n such that 3
!(, ) = "(, ). This implies that
mat((!(, )p( )p() "(, )) = mat(D T ( )D()),
and since mat(D T ( )D()) ! 0 one obtains (ii).
=D
((ii) (i)) Factorize mat(! ") 4T D.
4 Define a polynomial matrix D( ) with coefficient
matrix D 4 (i.e., mat(D) = D).
4 Then ! (, ) "(, ) = D( )T D() and setting = =
1 T 1
we get Z( ) = !(, ) = (p ( )D( )) p ( )D( ) which implies (i). #

Remark 4.2. Condition (21) can be restated as p( )!(, )p() "(, ) = D T ( )D(), equiv-
d d 2
alently, div(Q" ()) Q! (p( dx )) = D( dx ) for all C (R , Rq ). This says that the
n
1128 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

nD system behavior B = C (Rn , Rq ), written in image representation w = Ip( dx d

), is Q!
d
dissipative, and has storage function Q" () with corresponding dissipation rate D( dx )2 .

In the inequality (15) the unknowns are the entries of mat("i ), i = 1, 2, . . . n, and the coeffi-
cients of p. Of course, the coefficients of p appear quadratically in the inequality, and therefore
(15) is no longer a linear matrix inequality. An additional complication is that the highest monomial
degree appearing in p( ) is unknown, so the number of unknowns in the inequality is also an
unknown.
In the remainder of this section we will propose two different ideas for possible algorithms to
solve the inequality (15).
Our first algorithm reduces the nonlinear problem to a linear eigenvalue problem. In order
to avoid too cumbersome notation, we consider for this first algorithm only the case n = 2. For
the sake of simplicity, we will also assume that !(, ) can be chosen such that its coefficient
matrix mat(!) is nonsingular. Let p(1 , 2 ) be a real polynomial with highest monomial degree
(M1 , M2 ) given by

p(1 , 2 )= p0,0 + p1,0 1 + p2,0 12 + + pM1 ,0 1M1

+p0,1 2 + p1,1 1 2 + + pM1 ,1 1M1 2 +
+p0,M2 2M2 + p1,M2 1 2M2 + + pM1 ,M2 1M1 2M2
= (P0T P1T T
PM 2
)(U (1 ) 2 U (1 ) 2M2 U (1 ))T ,

where PiT := (p0,i , p1,i . . . , pM1 ,i ) for i = 0, . . . , M2 and U (1 ) := (1, 1 , . . . , 1M1 ). Let I de-
note the q q identity matrix, and for i = 0, 1, . . . , N1 , define shift operators i acting on
P R(M1 +1)1 , P = (p0 , p1 . . . , pM1 ) by
1 2T
i (P ) = 0qqi .. .. .. .. .. ,
. p0 I . p1 I . ... . pM1 I . 0q(N1 i)q

and a (M1 + N1 + 1)(M2 + 1)q (N1 + 1)q matrix % by

0 (P0 ) 1 (P0 ) ... N1 (P0 )
(P ) 1 (P1 ) ... N1 (P1 )
0 1

% := .. .. .. .. .

. . . .
0 (PM2 ) 1 (PM2 ) . . . N1 (PM2 )

For i = 0, 1, . . . , N2 define

0(M1 +N1 +1)qi(N1 +1)q
i (%) := % .
0(M1 +N1 +1)(N2 i)q(N1 +1)q

Finally, define a (M1 + N1 + 1)(M2 + N2 + 1)q (N1 + 1)(N2 + 1)q matrix M by

1 2
M := 0 (%) ... 1 (%) ... 2 (%) ... . . . ... N (%) .
2
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1129

It is a matter of straightforward calculation to check that the coefficient matrix of p( )!(, )p()
is Mmat(!)M T . Define
! " ! "
mat(") M Mmat(!)M T mat(") 0
A= and B = .
MT mat(!)1 0 mat(!)1

Then we have
! " ! "
I Mmat(!) I 0
A = B.
0 I mat(!)M T I

Note that Mmat(!)M T mat(") is the Schur-complement of mat(!)1 in B and that the sig-
natures of A and B are equal. Thus we find that the (nonlinear) matrix inequality Mmat(!)M T
mat(") ! 0 has a solution if and only if A has the same number of negative eigenvalues as the
matrix mat(!)1 . It is important to note that A depends linearly on the unknowns. The solution
of this linear eigenvalue problem will provide a p and a "(, ) such that mat(! mat(")) is
positive semidefinite. Moreover, we can then construct the spectral factor F ( ) as explained in
Theorem 4.2.
We conclude this section with our second conceptual algorithm to solve the nonlinear inequality
(15). In the following, we will denote the unknowns appearing in (15) by 1 , 2 , . . . , k (where k
is also unknown), and collect them in a single vector Rk . The inequality (15) can be written
as S(1 , . . . , k ) ! 0, where S() is a real symmetric matrix function, say of size N. In the
following, we will reduce this inequality to checking feasability of a semi-algebraic set. In order
to proceed, let L () := det(S() I ) be the characteristic polynomial of S(). Write

L () = N + sN1 ()N1 + + s1 () + s0 ().

The coefficients si () are all real polynomials in the indeterminate . Since S() is symmetric
for all , the roots of L are all real. Our aim is to find Rk such that all these roots
are nonnegative. In order to find such s, consider the polynomial L (). Obviously, the
number of negative roots of L () is equal to the number of positive roots of L (). By
Descartes rule of signs, the number of positive eigenvalues of L () is equal to the number
of sign changes between the consecutive nonzero coefficients in this polynomial. We there-
fore conclude that L () has only nonnegative roots if and only if (1)N+i si () ! 0 for all
i = 1, . . . , N 1. Hence, the inequality (15) has a solution if and only if the semi-algebraic
set

U := { Rk |(1)N+i si () ! 0, i = 1, . . . , N 1}

is not empty. A feasible point in U correspond to a polynomial p and to a "(, ) such that
mat(! ") is positive semidefinite. Moreover after finding a feasable , we can construct
a spectral factor F ( ) as explained in Theorem 4.2. Unfortunately, even if we know that the
semialgebraic set U is not empty, in general, to find a feasible point is a difficult problem.
However recent developments have led to an approach using semidefinite programming to deal
with semialgebraic sets [7,8].
Since the degree of p is unknown, we may have to execute these algorithms for different
degrees of p.
Another important difference between the case n = 1 and n > 1 is that, under the condition
that a spectral factor exists, in the multidimensional case it is not always possible to find a square
1130 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

spectral factor, not even in the scalar case with n = 2, see [5,1]. In the case that n = 1 this is
always possible.

5. Sum of squares

Let Z( ) R[ ] be a polynomial in n indeterminates, and assume that Z( ) = F T ( )F ( )

for some n-variable polynomial row vector F ( ). Substituting = i yields Z(i) = F T (i)
F (i). If F (i) is decomposed into real and imaginary parts as F (i) = A() + iB(), we have
Z(i) = A2 () + B 2 (). Thus, one can see that representation as sum of squares is at the heart
of the problem of spectral factorization, and therefore we expect that similar techniques can be
used in order to treat the sum of squares problem.
A given n-variable polynomial q q matrix Z( ) is called positive semi-definite if Z( )T =
Z( ) and Z( ) ! 0 for all Rn . In the following, we will associate with Z( ) symmetric,
2n-variable polynomial q q matrices !(, ) with the property that
!(, ) = Z( ). (17)
For a given Z there are always infinitely many !s such that this property holds. One possible
choice of ! such that (17) holds is given by
1 T
!(, ) := (Z ( ) + Z()).
2
Since !(, )T = 21 (Z() + Z T ( )) = !(, ), !(, ) is symmetric. Using Z T ( ) = Z( ), this
! indeed satisfies (17).
For a given n-variable polynomial matrix Z( ), it is possible to characterize all symmetric 2n-
variable polynomial matrices !(, ) such that (17) holds. The procedure to do that is analogous
to the one described in section 3 to characterize all symmetric 2n-variable polynomial matrices
!(, ) such that !(, ) = Z( ). The only difference is that, in the present case, there is no
alternating sign pattern: the signs of the blocks on the various anti-diagonals are all positive. We
omit the details here.
In the following we will use skew-symmetric 2n-variable polynomial matrices. A given !
Rqq [, ] will be called skew-symmetric if !(, )T = !(, ). It is easily verified that ! is
skew-symmetric if and only if is coefficient matrix is skew-symmetric, i.e., mat(!)T = mat(!).
qq
Lemma 5.1. Let ! Rs [, ]. Then the following statements are equivalent:

(i) !(, ) = 0,
(ii) There exist an n-tuple "(, ) = (("1 (, ), . . ., "n (, )) with "i Rqq [, ], i =
1, . . . , n, skew-symmetric such that
!(, ) = (1 1 )"1 (, ) + + (n n )"n (, ). (18)

Proof. (i) (ii) Define ! (, ) := !(, ). Clearly ! (, ) = 0, so there exists an n-

tuple "(, ) = ("1 (, ), . . . , "n (, )) such that ! (, ) = (1 + 1 )"1 (, ) + + (n +
n )"n (, ). This implies (18). We see that the "i can be chosen skew-symmetric. Indeed,
using that !(, )T = !(, ) it can be shown that !(, ) = (1 1 )"1 (, ) + + (n
n )"n (, ), with "i (, ) := 21 ("i (, ) "i (, )T ) skew-symmetric.
(ii) (i) Obvious by substitution. #
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1131

Analogous to theorem 4.1, we obtain the following theorem for SOS.

Theorem 5.1. Let Z( ) Rqq [ ] be a positive semidefinite n-variable polynomial matrix.

qq
Let !(, ) Rs [, ] be such that !(, ) = Z( ). Then the following statements are
equivalent:

(i) Z( ) is sum of squares, i.e. there exists a positive integer r and an r q polynomial matrix
F ( ) such that

Z( ) = F T ( )F ( ). (19)

(ii) There exist an n-tuple of skew-symmetric 2n-variable polynomial matrices "(, ) =

("1 (, ), . . ., "n (, )) with "i Rqq [, ], i = 1, . . . , n such that

mat(! ") ! 0, (20)

with "(, ) := (1 1 )"1 (, ) + (2 2 )"2 (, ) + + (n n )"n (, ).

(iii) There exists a symmetric 2n-variable polynomial matrix 3 !(, ) such that 3 !(, ) = Z( )
and mat(!) ! 0.
3

Assume that any of these conditions hold. Then an F such that (19) holds can be computed as
follows: find "(, ) = ("1 (, ), . . ., "n (, )), such that (20) holds, and factorize
4T F
mat(! ") = F 4, (21)
4 is a constant matrix with row rank, say r. Then the polynomial matrix F ( ) with coefficient
where F
4 (i.e., mat(F ) = F
matrix F 4) satisfies (19).

Proof. (i) (ii) Clearly !(, ) F T ( )F ( ) = 0. By proposition 5.1, there exists a vector of
skew-symmetric 2n-variable polynomial matrices "(, ) = ("1 (, ), . . ., "n (, )) with "i
Rqq [, ] such that !(, ) F T ( )F () = "(, ) = (1 1 )"1 (, ) + + (n n )
"n (, ). This equality can be written in terms of the associated coefficient matrices as
mat(!) F 4T F
4 = mat("), where F 4 is the coefficient matrix of F ( ). This implies (20) since
4 T
F F ! 0.
4
(ii) (i) Since mat(! ") is a symmetric positive semidefinite matrix we can factorize
it as mat(! ") = F 4T F
4, with row rank, say r. Now let F ( ) be the n-variable polynomial
4. Then we obtain !(, ) "(, ) = F T ( )F (). By taking
matrix with coefficient matrix F
= = we then obtain Z( ) = !(, ) = F T ( )F ( ).

!(, ) := F T ( )F ().
(i) (iii) Define 3

(iii) (i) Factor mat(3 4T F

!) = F 4 and define F ( ) as the n-variable polynomial matrix such
that mat(F ) = F . #
4

We note that, in a different form, condition (iii) in the above theorem can also be found in [3]
and [12] in the context of sum of squares of real polynomials.
As in the previous section, in order to be able to apply the above theorem, we need to be able
to express (20) as an LMI. Thus we need to express mat(") in terms of shifts of the coefficient
1132 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

matrices mat("i ). It is easy to see that mat((i i )"i (, )) = (i,D i,R )(mat("i )) for
i = 1, . . . , n and therefore the inequality (20) can be expressed as

mat(!) (1,D 1,R )(mat("1 )) (2,D 2,R )(mat("2 ))

(n,D n,R )(mat("n )) ! 0.

If the highest monomial

5 degree of !(, ) is equal to (N1 , N2 , . . . , Nn ) then, as before, mat("i )
has size ni := qNi nj=1,j =i / (Nj + 1)(i = 1, 2 . . . , n). Since the "i , or equivalently the matrices
mat("i ), can always
$ be taken to be skew-symmetric, the actual number of unknowns in the LMI
(20) is equal to ni=1 ni (n2i 1) .
We illustrate the use of the previous theorem for SOS by means of the following example:
1 2
1 21 + 12 + (12 2 )2 1 12
Example 5.1. Let Z( ) = 1 12 1 21 + 212 + (12 2 )2
. We want to find, if these
exist, a positive integer r and an F ( ) Rr2 [ ] such that Z( ) = F T ( )F ( ).
We first construct !(, ) R22 s [, ] such that !(, ) = Z( ). This condition can be ex-
pressed in terms of the appropriate anti-diagonals of the coefficient matrix of !, with positive
signs only. Thus we find that we can take
!(, ) equal to

1 0 1 1 21 1 0 0 0 0 0 0
0 1 0 1 0 1 0 0 0 0 0 0


1 0 0 0 0 0 0 0 0 0 0 0
I
1 1 0 0 0 0 0 0 0 0 0 0
I
1 0 0 0 0 0 0 0 0 0 0 0 1
2 2
I
2 2 1 1 0 0 0 0 0 0 0 0 0 0 1
(I, I 1 , I 1 |I 2 , I 1 2 , I 1 2 )

,
0 0 0 0 0 0 0 0 0 0 0 0
I 2
0 0 0 0 0 0 0 0 0 0 0 0
I 1 2
0 0 0 0 0 0
0 0 0 0 0 0 I 2 I 2
1

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1

where I denotes the 2 2 identity matrix. Next, we search for "1 (, ), "2 (, ) R22 [, ],
skew-symmetric, with highest monomial degrees (2, 0) and (1, 1) respectively. Their (unknown)
coefficient matrices are given by

0 a1 a2 a3 a4 a5 a6 a7
a1 0 a8 a9 a10 a11 a12 a13

a2 a8 0 a14 a15 a16 a17 a18

a3 a9 a14 0 a19 a20 a21 a22
mat("1 ) =
a4
,
a10 a15 a19 0 a23 a24 a25

a5 a11 a16 a20 a23 0 a26 a27

a6 a12 a17 a21 a24 a26 0 a29
a6 a13 a18 a22 a25 a27 a29 0
 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134 1133

0 b1 b2 b3 b4 b5
b1 0 b6 b7 b8 b9

b2 b6 0 b10 b11 b12
mat("2 ) =
b3
,
b7 b10 0 b13 b14

b4 b8 b11 b13 0 b15
b5 b9 b12 b14 b15 0

and the LMI we want to solve is

mat(!) (1,D 1,R )(mat("1 )) (2,D 2,R )(mat("2 )) ! 0.

One solution of this inequality is given by

0 0 21 1 0 0 0 0
0 0 0 1 0 0 0 0
1
0 0 0 0 0 0 0
2
1 1 0 0 0 0 0 0
mat("1 ) =
0
,
0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0

and mat("2 ) the zero matrix. This yields

1 0 1 1 0 0 0 0 0 0 0 0
0 1 0 1 0 0 0 0 0 0 0 0

1 0 1 1 0 0 0 0 0 0 0 0

1 1 1 2 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0
mat(! ") = ! 0.
0 0 0 0 0 0 0 0 0 0 0 0
0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 0 0

0 0 0 0 0 0 0 0 0 0 1 0
0 0 0 0 0 0 0 0 0 0 0 1
The rank of this matrix is equal to 4, and it can be factorized as mat(! ") = F 4T F
4, with F
4
given below. This gives

I
I 1
1 0 1 1 0 0 0 0 0 0 0 0 2

0 1 0 1 0 0 0 0 0 0 0 0 I 1
F ( ) = ,
0 0 0 0 0 0 0 0 0 0 1 0 I 2

0 0 0 0 0 0 0 0 0 0 0 1 I 1 2

I 12 I 2
1134 D.N. Avelli, H.L. Trentelman / Linear Algebra and its Applications 429 (2008) 11141134

Hence,
! "! "T
1 1 0 12 2 0 1 1 0 12 2 0
Z( ) = F T ( )F ( ) = .
1 1 1 0 12 2 1 1 1 0 12 2

6. Conclusions

In this paper we have presented a new framework in which is possible to develop algorithms
to address the problems of spectral factorization and sum of squares, even for the matrix case,
with any number of indeterminates. The algorithms are based on the idea of associating with
the (n-variable) polynomial matrix Z to be factored, a 2n-variable polynomial matrix !. For the
case n = 2 explicit formulas for such ! have been given. This allows us to relate the problem of
spectral factorization with the theory of multidimensional dissipative systems, and give, in most
cases, a physical interpretation of the elements of the algorithms.
We expect that this approach will provide further results in this area. Future research will treat,
for instance, the presense of uniform denominators in the spectral factorization problem (see also
[15]), the reduction of the number of unknowns in the matrix inequalities presented, rational
factors for SOS, and so on.

References

[1] S. Basur, On spectral factorization in multidimensions, in: The Second International Workshop on Multidimensional
(nD) Systems (Czocha Castle, 2000), Tech. Univ. Press, Zielona Gra, 2000. 93B17 (15A23), pp. 3946.
[2] F.M. Callier, On polynomial spectral factorization by symmetric factor extraction,IEEE Trans. Aut. Contr., 30 (1985)
453464.
[3] M.D. Choi, T.Y. Lam, B. Reznick, Sums of squares of real polynomials, Proc. Sympos. Pure Math, vol. 58, American
Mathematical Society, 1995, pp. 103126.
[4] W.A. Coppel, Linear systems, Notes in Pure Mathematics, Australian National University, 1972.
[5] A. Kummert, Spectral factorization of two-variable para-hermitian polynomial matrices, Multidimens. Systems
Signal process. 1 (1990) 327339.
[6] H. Kwakernaak, M. ebek, Polynomial J-spectral factorization, IEEE Trans. Aut. Contr. 39 (2) (1994) 315328.
[7] P.A. Parrilo, B. Sturmfels, Minimizing polynomial functions, in: Algorithmic and quantitative real algebraic ge-
ometry, DIMACS Series in Discrete Mathematics and Theoretical Computer Science, vol. 60, AMS, 2003, pp.
8399.
[8] P.A. Parrilo, Semidefinite programming relaxations for semialgebraic problems, Algebr. Geom. Methods Discrete
Optim 96 (2003) 293320.
[9] A. Papachristodoulou, S. Prajna, On the construction of Lyapunov functions using the sum of squares decomposition,
in: Proceedings of the 39th IEEE Conference on Desition and Control, December 2000, pp. 34823487.
[10] H.K. Pillai, S. Shankar, A behavioral approach to control of distributed systems, SIAM J. Control Optim. 37 (2)
(1998) 388408.
[11] H.K. Pillai, J.C. Willems, Lossless and disipative distributed systems, SIAM J. Contr. Optim. 40 (5) (2002) 1406
1430.
[12] V. Powers, T. Wrmann, An algorithm for sums of squares of real polynomials, J. Pure Appl. Algebra 127 (1998)
99104.
[13] A.C.M. Ran, L. Rodman, Factorization of matrix polynomials with symmetries, IMA Preprint Series, no. 993, 1992.
[14] P. Rapisarda, H.L. Trentelman, New algorithms for polynomial J-spectral factorization, Math. Control Signals
Systems 12 (1999) 2461.
[15] B. Reznick, Uniform denominators in Hilberts seventeenth problem, Math. Z. 220 (1) (1995) 7597.
[16] N. Wiener, Extrapolation, Interpolation, and Smoothing of Stationary Time Series with Engineering Applications,
The Technology Press of the Massachusetts Institute of Technology, Cambridge, MA, 1949.
[17] J.C. Willems, H.L. Trentelman, On quadratic differential forms, SIAM J. Contr. Optim. 36 (5) (1998) 17031749.