Murota K. Matrices and Matroids for Systems Analysis

Подождите немного. Документ загружается.

332 6. Theory and Application of Mixed Polynomial Matrices

(MP-Q1) The coeﬃcients in Q(s)belongtoK,and

(MP-T) The collection T of nonzero coeﬃcients in T (s) is alge-

braically independent over K.

A mixed polynomial matrix with respect to (K, F ) is a mixed matrix with

respect to (K(s), F (s)). On expressing

A(s)=



k=0

,Q(s)=



k=0

,T(s)=



k=0

we have

= Q

+ T

(k =0, 1, ···,N)

and for each k, A

is a mixed matrix with respect to (K, F ).

A subclass of mixed polynomial matrices has been identiﬁed with reference

to the physical dimensional consistency. The subclass is characterized by

replacing (MP-Q1) with a stronger condition:

(MP-Q2) Every nonvanishing subdeterminant of Q(s) is a monomial

over K, i.e., of the form αs

with α ∈ K and an integer p.

Recall from Theorem 3.3.2 that (MP-Q2) holds if and only if

Q(s) = diag [s

, ···,s

] · Q(1) · diag [s

−c

, ···,s

−c

] (6.4)

for some integers r

(i =1, ···,m)andc

(j =1, ···,n).

An LM-polynomial matrix with respect to (K, F ) will mean a mixed poly-

nomial matrix with respect to (K, F ) which is an LM-matrix with respect to

(K(s), F (s)). Namely, an LM-polynomial matrix A(s) with respect to (K, F )

canbeexpressedas

A(s)=



Q(s)

T (s)



(6.5)

in such a way that (MP-Q1) and (MP-T) are satisﬁed. A subclass of LM-

polynomial matrices can be identiﬁed by imposing the condition (MP-Q2).

A generic polynomial matrix with respect to (K, F ) will mean a matrix

A(s) of polynomials in s over F such that the collection of nonzero coeﬃcients

is algebraically independent over K. In other words, a generic polynomial

matrix is a mixed polynomial matrix A(s)=Q(s)+T (s) with Q(s)=O,

which trivially satisﬁes (MP-Q2).

6.1.2 Relationship to Other Descriptions

In the literature of structural approach in control theory a number of diﬀer-

ent mathematical frameworks have been proposed to cope with the problem

of “parameter dependency.” In this section we consider to what extent the

mixed polynomial matrix description is general in comparison with other

frameworks.

6.1 Descriptions of Dynamical Systems 333

Firstly, the present framework includes the graph-theoretic approach

based on the standard form, in which all the nonvanishing entries of the

matrices A and B of (6.1) are assumed to be algebraically independent pa-

rameters, since the decomposition

[A − sI

| B]=[−sI

| O]+[A | B]

satisﬁes (MP-Q2) and (MP-T) with Q(s)=[−sI

| O]andT (s)=[A | B].

Similarly, the graph-theoretic approach based on the descriptor form, in which

all the nonvanishing entries of the matrices F , A,andB of (6.2) are assumed

to be algebraically independent parameters, also ﬁts the present setting.

Corfmat–Morse [42] considered the standard form (6.1) with the coeﬃ-

cients A and B “linearly parametrized” as

A = A



i=1

,B= B



i=1

, (6.6)

where P

(i =1, ···,k) are matrices such that all the entries are independent

parameters, and B

, C

, D

(i =1, ···,k)aswellasA

, B

are ﬁxed constant

matrices. The linear parametrization (6.6) for the standard form (6.1) may

be extended to that for the descriptor system (6.2) by assuming the following

forms of the coeﬃcients:

F = F



i=1

,A= A



i=1

,B= B



i=1

, (6.7)

where P

(i =1, ···,k) are matrices such that all the nonvanishing entries

are independent parameters, and F

, B

, C

, D

(i =1, ···,k)aswellasF

, B

are ﬁxed constant matrices. The case of P

being scalars is considered

by Hosoe–Hayakawa–Aoki [114].

A mixed polynomial matrix description for (6.7) can be obtained by set-

ting

F =

⎡

⎢

⎣

⎤

⎥

⎦

C =

⎡

⎢

⎣

⎤

⎥

⎦

D =

⎡

⎢

⎣

⎤

⎥

⎦

P =

⎡

⎢

⎣

⎤

⎥

⎦

and

B =[B

|···|B

], and introducing auxiliary variables

v =(C − sF )x + Du, w = P v.

Then the descriptor system (6.2) with (6.7) can be equivalently rewritten into

another descriptor system in descriptor-vector (x,

v, w) and input-vector u.

The coeﬃcient matrix is given by

⎡

⎣

− sF

O B B

C − sF −IOD

P −I O

⎤

⎦

334 6. Theory and Application of Mixed Polynomial Matrices

which is a mixed polynomial matrix Q(s)+T (s) with

Q(s)=

⎡

⎣

− sF

O B B

C − sF −IOD

OO−I

⎤

⎦

,T(s)=

⎡

⎣

OOO

POO

⎤

⎦

Thus, the linear parametrization as extended above is included in the present

framework. The stronger condition (MP-Q2) need not be satisﬁed from the

mathematical point of view, though it is likely to be the case for the physical

reason.

A special class of linearly parametrized systems is considered by Hayakawa

–Hosoe–Hayashi–Ito [106]. This class includes the so-called compartmen-

tal systems (see, e.g., Hayakawa–Hosoe–Hayashi–Ito [106, 107], Zazworsky–

Knudsen [351] for compartmental systems). Denote by a

(i =1, ···,n)and

(j =1, ···,m), respectively, the column-vectors of the matrices A and B

in the standard form (6.1), namely,

A =[a

, ···, a

],B=[b

, ···, b

It is assumed that the column vectors are expressed as

= A

(i =1, ···,n), b

= B

(j =1, ···,m)

with vectors p

and r

of independent parameters and ﬁxed constant matrices

and B

. By introducing auxiliary variables

= x

(i =1, ···,n), v

= u

(j =1, ···,m),

we obtain a descriptor system in descriptor-vector (x,

w, v) and input-vector

u, where

w =(w

, ···, w

)

and v =(v

, ···, v

)

. The coeﬃcient

matrix is then given by

⎡

⎣

−sI

A B O

P −IOO

OO−I

⎤

⎦

, (6.8)

where

A =[A

|···|A

], B =[B

|···|B

P =

⎡

⎢

⎣

⎤

⎥

⎦

R =

⎡

⎢

⎣

⎤

⎥

⎦

The matrix in (6.8) is a mixed polynomial matrix Q(s)+T (s) with

Q(s)=

⎡

⎣

−sI

A B O

O −IOO

OO−I

⎤

⎦

,T(s)=

⎡

⎣

OOO

POOO

OOO

⎤

⎦

6.2 Degree of Determinant of Mixed Polynomial Matrices 335

The matrix Q(s) meets the stronger condition (MP-Q2).

Anderson–Hong [6] considered the standard form (6.1) with A and B

expressed in the form of “matrix nets”:

A = A



i=1

,B= B



i=1

where μ

(i =1, ···,k) are scalar independent parameters, and A

and B

(i =0, 1, ···,k) are ﬁxed constant matrices. This does not seem to ﬁt in the

present framework of mixed polynomial matrices.

6.2 Degree of Determinant of Mixed Polynomial

Matrices

6.2.1 Introduction

In this section we investigate combinatorial characterizations of the highest

degree of a minor of order k:

(A) = max

I,J

{deg

det A[I,J] ||I| = |J| = k} (6.9)

for a mixed polynomial matrix A(s) with a view to laying a theoretical foun-

dation for the structural analysis of dynamical systems by means of mixed

polynomial matrices. Recall from §5.1.2 and §5.1.3 that the sequence of δ

(A)

(k =1, 2, ···) determines the Smith–McMillan form at inﬁnity and also the

structural indices of the Kronecker form.

We have already encountered the function δ(I,J) = deg

det A[I,J]as

an example of the abstract concept of a valuated bimatroid (see Example

5.2.15). In particular, Theorem 5.2.13 shows the concavity of the sequence

(A), δ

(A), ···, in the sense of

k−1

(A)+δ

k+1

(A) ≤ 2δ

(A)(1≤ k ≤ r − 1), (6.10)

where δ

(A)=0andr =rankA. It is emphasized that A(s) is not restricted

to a mixed polynomial matrix in this inequality.

The framework of the valuated independent assignment problem intro-

duced in §5.2.9 will play the major role in the investigation of δ

(A)fora

mixed polynomial matrix A(s).

Remark 6.2.1. In parallel to δ

(A) it is often meaningful (see Example

5.2.16) to consider

(A) = min

I,J

{ord

det A[I,J] ||I| = |J| = k}, (6.11)

336 6. Theory and Application of Mixed Polynomial Matrices

where ord

denotes the minimum degree of a nonzero term in a polynomial

in s. Since o

(A) is equal to −δ

(B)forB(s)=A(1/s), all the results for

(A) can be translated to those for o

(A). For instance, (6.10) yields

k−1

(A)+o

k+1

(A) ≥ 2o

(A)(1≤ k ≤ r − 1),

where o

(A)=0andr =rankA. 2

6.2.2 Graph-theoretic Method

Let us start with a graph-theoretic characterization of δ

(A) for a polynomial

matrix A(s). We consider a bipartite graph G(A)=(R, C; E), where R =

Row(A), C = Col(A), and E = {(i, j) | i ∈ R, j ∈ C, A

(s) =0}.Toarc

(i, j) ∈ E is attached a weight w

= deg

(s), and the weight of M ⊆ E

is deﬁned by w(M )=



(i,j)∈M

. The weighted matching problem treated

in §2.2.5 is closely related to δ

(A).

Theorem 6.2.2. Let A(s) be a polynomial matrix.

(1) δ

(A) ≤ max{w(M) | M: k-matching in G(A)},

where the right-hand side is equal to −∞ if no k-matching exists.

(2) The equality holds if A(s) is a generic polynomial matrix, i.e., if the

nonzero coeﬃcients in A(s) are algebraically independent.

Proof. Consider the deﬁning expansion of the determinant of a submatrix

A[I,J] of order |I| = |J| = k:

det A[I,J]=



σ:I→J

sgnσ



i∈I

iσ(i)

(s), (6.12)

where σ runs over all one-to-one correspondences from I to J, and sgnσ is

deﬁned with reference to a ﬁxed one-to-one correspondence. Put

(A)=

max{w(M) | M : k-matching}. It is easy to see that the highest degree of a

nonzero term

i∈I

iσ(i)

(s) is equal to

(A), i.e.,

max

|I|=|J|=k

max

σ:I→J

deg



i∈I

iσ(i)

(s) = max

|I|=|J|=k

max

σ:I→J



i∈I

iσ(i)

(A).

This expression, when combined with the deﬁnition (6.9) of δ

(A), shows that

(A) ≤

(A). The equality holds if A(s) is a generic polynomial matrix since

no cancellation occurs on the right-hand side of (6.12).

The above theorem is most fundamental among the graph-theoretic meth-

ods for degree of determinant as well as for structure at inﬁnity. The graph-

theoretic method for the DAE-index problem based on this theorem has been

fully demonstrated in §1.1. For graph-theoretic methods for structure at in-

ﬁnity and related topics, see Commault–Dion–Hovelaque [38], Commault–

Dion–Perez [39], Dion–Commault [48], Linnemann [174], Svaricek [307], van

der Woude [326, 327], and van der Woude–Murota [328].

6.2 Degree of Determinant of Mixed Polynomial Matrices 337

Remark 6.2.3. Theorem 6.2.2 can be translated for o

(A) deﬁned by (6.11).

Namely,

(A) = min{w(M) | M: k-matching in G(A)} (6.13)

for a generic polynomial matrix A(s). Henceforth no explicit statements will

be made on such translations for o

(A). 2

6.2.3 Basic Identities

We present basic identities concerning the degree of the determinant of (lay-

ered) mixed polynomial matrices.

Theorem 6.2.4. For a square mixed polynomial matrix A(s)=Q(s)+T (s),

deg

det A = max

|I|=|J|

I⊆R,J⊆C

{deg

det Q[I,J] + deg

det T [R \ I,C \ J]}. (6.14)

(It is implied that the right-hand side is equal to −∞ for a singular matrix

A.) In other words, the valuated bimatroid associated with A(s) by (5.29) is

the union of the valuated bimatroids deﬁned by Q(s) and T (s).

Proof. It follows from the deﬁning expansion (2.2) of determinant that

det A =



|I|=|J|

±det Q[I,J] · det T [R \ I,C \ J].

Since the degree of a sum is bounded by the maximum degree of a summand,

we obtain

deg

det A ≤ max

|I|=|J|

deg

(det Q[I,J] · det T [R \ I,C \ J])

= max

|I|=|J|

{deg

det Q[I,J] + deg

det T [R \ I,C \ J]},

where the inequality turns into an equality provided the highest-degree terms

do not cancel one another. The algebraic independence of the nonzero coef-

ﬁcients in T (s) ensures this.

The above theorem immediately yields a similar identity for an LM-

polynomial matrix A(s)=

Q(s)

T (s)

. Recall the notations R

=Row(Q),

=Row(T ), C = Col(A), m

= |R

|, m

= |R

|,andn = |C|.

Theorem 6.2.5. For a square LM-polynomial matrix A(s)=

Q(s)

T (s)

deg

det A = max

J⊆C,|J|=|R

{deg

det Q[R

,J]+deg

det T [R

,C\J]}. (6.15)

(It is implied that the right-hand side is equal to −∞ for a singular matrix

A.) 2

338 6. Theory and Application of Mixed Polynomial Matrices

In what follows we focus on an LM-polynomial matrix and consider a

variant of δ

. Namely, for A(s)=

Q(s)

T (s)

we deﬁne

(A) = max

I,J

{deg

det A[R

∪ I,J] |

I ⊆ R

,J ⊆ C, |I| = k, |J| = m

+ k}, (6.16)

where 0 ≤ k ≤ min(m

,n−m

). It should be clear that δ

(A) designates

the highest degree of a minor of order m

+ k with row set containing R

By convention, δ

(A)=−∞ if there exists no (I,J) that satisﬁes the

conditions on the right-hand side of (6.16). By substituting (6.15) into (6.16)

we obtain

(A) = max

I,J,B

{deg

det Q[R

,B] + deg

det T [I,J \ B] | I ⊆ R

B ⊆ J ⊆ C, |I| = k, |J| = m

+ k, |B| = m

}. (6.17)

We prefer to work with δ

for an LM-polynomial matrix rather than to

deal directly with δ

for a mixed polynomial matrix. This is because (i) any

algorithm for δ

canbeusedtocomputeδ

for a general mixed polyno-

mial matrix (as explained below), and (ii) our algorithm description is much

simpler for δ

The reduction of δ

to δ

is as follows. Given an m×n mixed polynomial

matrix A(s)=Q(s)+T (s)weconsidera(2m) × (m + n) LM-polynomial

matrix

A(s)=



Q(s)

T (s)





diag [s

, ···,s

] Q(s)

−diag [t

, ···,t

] T (s)



(6.18)

using “new” variables t

, ···,t

and exponents (integers)

= max

j∈C

deg

(s)(i ∈ R

), (6.19)

where R

=Row(A)andC

= Col(A).

Lemma 6.2.6. Let A(s) be an m ×n mixed polynomial matrix and

A(s) be

the associated LM-polynomial matrix deﬁned by (6.18) and (6.19).Then

(A)=δ

(

A) −



i=1

Proof. Deﬁne

A(s)=



diag (s

, ···,s

) Q(s)

−diag (s

, ···,s

) T(s)



The notation δ

(A) is deﬁned also for a rational matrix A(s) by (6.16).

6.2 Degree of Determinant of Mixed Polynomial Matrices 339

where R

=Row(Q)andR

=Row(T ) have a natural one-to-one cor-

respondence with R

. The matrix

A(s) is obtained from

A(s) by dividing

the (m + i)th row by t

and redeﬁning T

(s)/t

to be T

(s)(j ∈ C

)for

i =1, ···,m. The latter fact implies δ

(

A)=δ

(

A), where δ

(

A)is

deﬁned similarly to (6.16), though

A(s) is not an LM-polynomial matrix.

If J ⊇ R

,wehave

deg

det

A[R

∪ I,J] = deg

det A[I,C

∩ J]+



i=1

(I ⊆ R

). (6.20)

Hence, taking the maximum of this expression over all I and J with |I| =

|J|−m = k and J ⊇ R

, we see that δ

(A)+



i=1

is equal to

max{deg

det

A[R

∪ I,J] | I ⊆ R

⊆ J ⊆ C, |I| = k, |J| = m + k}.

It remains to be shown that the extra constraint “J ⊇ R

”canbere-

moved without aﬀecting the maximum value. Fix I ⊆ R

and let J ⊆ R

∪C

be a maximizer of deg

det

A[R

∪ I,J] satisfying J ⊇ R

. We claim that

A[R

∪I,J]

−1

A[R

∪I,C

\J] is a proper rational matrix. Then, by (5.24), J

is an optimum solution to the maximization problem without the constraint

“J ⊇ R

”.

The claim can be proven as follows. Denoting by I

and I

the copies of

I in R

and R

, respectively, we partition the matrix

A[R

∪I,R

∪C

]as

A[R

∪ I,R

∪ C

⎛

⎝

∩ I

\ I

∩ JC

\ J

∩ I

\ I

∩ I −D

⎞

⎠

with the obvious short-hand notations D

, Q

, T

, etc. for the relevant

submatrices of diag (s

, ···,s

), Q(s), T (s), etc. By row transformations

we obtain

⎛

⎝

−D

⎞

⎠

⇒

⎛

⎝

IOOD

−1

− Q

−1

]

OIOD

−1

− Q

−1

]

OO I A

−1

⎞

⎠

where A

= Q

. This shows

A[R

∪I,J]

−1

A[R

∪I,C

\J]=



(s)



with

(s) = diag (s

−d

, ···,s

−d

){Q[R

\ J] − Q[R

∩ J]B

(s)},

(s)=A[I,C

∩ J]

−1

A[I,C

\ J].

Here B

(s) is a proper rational matrix by the choice of J (cf. (6.20) and

(5.24)), and diag (s

−d

, ···,s

−d

)Q[R

] is also proper by the deﬁnition

(6.19) of d

. Therefore,

A[R

∪I,J]

−1

A[R

∪I,C

\J] is a proper rational

matrix.

340 6. Theory and Application of Mixed Polynomial Matrices

Example 6.2.7. Consider a 2 × 3 mixed polynomial matrix:

A(s)=

+1 s

+ α

s +1

+ α

s 0

with respect to (K, F )=(Q, Q(α

,α

)), where {α

,α

} is assumed

to be algebraically independent over Q.WehaveA(s)=Q(s)+T (s) with

Q(s)=

+1s

s 0

,T(s)=

0 α

The associated LM-polynomial matrix is given by

A(s)=

+1 s

s 0

T 1

−t

0 α

T 2

−t

where d

=3andd

= 2 in (6.19). It is easy to see by inspection that

(A) = deg

det A[r

]=3,

(A) = deg

det A[{r

}, {c

}]=3,

(

A) = deg

det

A[{r

T 1

}, {r

}]=3+5,

(

A) = deg

det

A[{r

T 1

T 2

}, {r

}]=3+5,

which verify the relation δ

(

A)=δ

(A)+(d

+ d

) in Lemma 6.2.6. 2

6.2.4 Reduction to Valuated Independent Assignment

We describe how the computation of δ

(A) for an LM-polynomial matrix

A(s)=

Q(s)

T (s)

can be reduced to solving a valuated independent assignment

problem of §5.2.9. Assuming Q(s) to be of full-row rank, we denote by M

, B

,ω

) the valuated matroid associated with Q(s) (see Example 5.2.3);

namely,

= {B ⊆ C

| det Q[R

,B] =0}, (6.21)

(B) = deg

det Q[R

,B](B ∈B

). (6.22)

Here and henceforth C

= {j

| j ∈ C} denotes a disjoint copy of the column

set C of A (with j

∈ C

denoting the copy of j ∈ C), whereas R

and R

mean, as before, the row sets of Q(s)andT (s), respectively, with |R

| = m

and |C| = n.

6.2 Degree of Determinant of Mixed Polynomial Matrices 341

We consider a valuated independent assignment problem deﬁned on a

bipartite graph G =(V

−

; E) with V

= R

∪ C

, V

−

= C,andE =

∪ E

, where

= {(i, j) | i ∈ R

,j ∈ C, T

(s) =0},E

= {(j

,j) | j ∈ C}.

The valuated matroids M

=(V

, B

,ω

)andM

−

=(V

−

, B

−

,ω

−

) at-

tached to V

and V

−

are deﬁned by

= {B

⊆ V

| B

∩ C

∈B

, |B

∩ R

| = k},

−

= {B

−

⊆ V

−

||B

−

| = m

+ k}

and

)=ω

∩ C

)(B

∈B

−

)=0 (B

−

∈B

−

The weight w

of an arc (i, j) ∈ E is deﬁned by



deg

(s)((i, j) ∈ E

)

0((i, j) ∈ E

(6.23)

The value of an independent assignment M is given by

(M)=w(M )+ω

(∂

M)+ω

−

(∂

−



(i,j)∈M ∩E

deg

(s) + deg

det Q[R

,∂

(M ∩ E

)].

We then have the following characterization of δ

(A) in terms of the

optimal value of the valuated independent assignment problem.

Theorem 6.2.8. For an LM-polynomial matrix A(s)=

Q(s)

T (s)

with Q(s) of

full-row rank and an integer k with 0 ≤ k ≤ min(m

,n− m

), δ

(A) of

(6.16) coincides with the optimal value of the valuated independent assign-

ment problem deﬁned above. That is,

(A) = max{Ω

(M) | M: independent assignment},

where the right-hand side is deﬁned to be −∞ if there exists no independent

assignment M.

Proof. Deﬁne

Δ(I,J,B) = deg

det Q[R

,B] + deg

det T [I,J \ B],

which is the function to be maximized in the expression (6.17) for δ

(A).

By virtue of the algebraic independence of the nonzero coeﬃcients in T (s),