Murota K. Matrices and Matroids for Systems Analysis

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

272 5. Polynomial Matrix and Valuated Matroid

Note that d

k−1

(s) divides d

(s) by the Laplace expansion (Proposition 2.1.2).

Furthermore, it is known that e

k−1

(s) divides e

(s)fork =1, ···,r (see

Example 5.2.16 for a combinatorial proof).

We call a polynomial matrix U (s) unimodular if it is square and its deter-

minant is a nonvanishing constant (in F ). A square polynomial matrix U(s)

is invertible (i.e., ∃ U

−1

with (U

−1

)

∈ F [s]) if and only if it is unimodular.

The following fundamental result claims the existence of a canonical diagonal

form under the unimodular equivalence.

Theorem 5.1.1 (Smith normal form). For a polynomial matrix A(s),

there exist unimodular matrices U (s) and V (s) such that

U(s)A(s)V (s) = diag (e

(s), ···,e

(s), 0, ···, 0),

where r =rankA(s),ande

(s)(k =1, ···,r) are polynomials such that

k−1

(s) divides e

(s) for k =2, ···,r. Furthermore, e

(s) coincides with the

kth invariant factor given by (5.2). 2

The Smith normal form is uniquely determined by (5.2) and is invariant

under unimodular equivalence transformations. A signiﬁcance of the Smith

normal form is indicated by the following fact.

Lemma 5.1.2. For a polynomial matrix A(s) and a polynomial vector b(s),

there exists a polynomial vector x(s) such that A(s)x(s)=b(s) if and only

if A(s) and [A(s) | b(s)] have the same invariant factors. 2

Remark 5.1.3. The invariant factors e

(s) are also called the elementary

divisors, though some books (e.g., Gantmacher [87]) distinguish between the

two, deﬁning elementary divisors to be the prime powers appearing in the

factorization of the invariant factors. 2

Remark 5.1.4. The theorem on the Smith normal form holds true more

generally for a matrix over a PID (principal ideal domain), of which a Eu-

clidean domain (e.g., the ring of polynomials in a single variable) is a spe-

cial case. A square matrix U overaPID,sayR, is invertible (i.e., ∃ U

−1

with (U

−1

)

∈ R) if and only if its determinant is an invertible element

in R. Such a matrix U is said to be unimodular over R. Theorem 5.1.1

can be generalized as follows: For a matrix A over R, there exist unimod-

ular matrices U and V such that UAV = diag (e

, ···,e

, 0, ···, 0), where

r =rankA and e

k−1

divides e

for k =1, ···,r. Furthermore, e

= d

k−1

with d

=gcd{det A[I,J] ||I| = |J| = k} (k =1, ···,r). See Newman [252]

for the proof. 2

5.1.2 Rational Matrix and Smith–McMillan Form at Inﬁnity

Let A(s)=(A

(s)) be an m × n rational function matrix with A

(s) being

a rational function in s with coeﬃcients from a certain ﬁeld F (i.e., A

(s) ∈

5.1 Polynomial/Rational Matrix 273

F (s)). Typically F is the real number ﬁeld R.Inthisbook,weareoften

concerned with the highest degree of a minor (subdeterminant) of order k of

A(s):

= δ

(A) = max{deg

det A[I,J] ||I| = |J| = k} (k =0, 1, 2, ···). (5.3)

By convention δ

(A) = 0, and δ

(A)=−∞ for k>r.

A rational function f(s) is called proper if deg

f(s) ≤ 0, where the degree

of a rational function f(s)=p(s)/q(s) (with p(s)andq(s) being polynomials)

is deﬁned by

deg

f(s) = deg

p(s) − deg

q(s),f(s)=p(s)/q(s).

By convention we put deg

(0) = −∞.

We call a rational matrix A(s)=(A

(s)) proper if its entries are proper

rational functions, i.e., deg

(s) ≤ 0 for all (i, j). A square proper ra-

tional matrix is called biproper if it is invertible and its inverse is a proper

rational matrix. A proper rational matrix A(s) is biproper if and only if

deg

det A(s)=0.

Since the proper rational functions form a Euclidean ring, any proper

rational matrix can be brought into a canonical form (the Smith form) ac-

cording to the general principle explained in Remark 5.1.4. This is sometimes

referred to as the structure at inﬁnity in the control literature. From this we

see further that any rational matrix can be brought into the Smith–McMillan

form at inﬁnity, as stated below (Verghese–Kailath [329]).

Theorem 5.1.5 (Smith–McMillan form at inﬁnity). For a rational

function matrix A(s), there exist biproper matrices U(s) and V (s) such that

U(s)A(s)V (s)=



Γ (s) O



where

Γ (s) = diag (s

, ···,s

r =rankA(s),andt

= t

(A)(k =1, ···,r) are integers with t

≥···≥t

Furthermore, t

can be expressed in terms of the minors of A as

(A)=δ

(A) − δ

k−1

(A)(k =1, ···,r) (5.4)

using δ

(A) in (5.3). 2

The integers t

(k =1, ···,r), uniquely determined by (5.4), are referred

to as the contents at inﬁnity. If they are positive, t

(k =1, ···,r)arethe

orders of the poles at inﬁnity, and if negative, −t

(k =1, ···,r)arethe

orders of the zeroes at inﬁnity. It should be noted in (5.4) that δ

(A)’s are

invariant under biproper equivalence transformations, that is,

274 5. Polynomial Matrix and Valuated Matroid

(A)=δ



)(k =1, ···,r) (5.5)

if A



(s)=U(s)A(s)V (s) with biproper matrices U (s)andV (s).

A signiﬁcance of the Smith–McMillan normal form at inﬁnity is indicated

by the following fact.

Lemma 5.1.6. For a rational function matrix A(s) and a rational function

vector b(s), there exists a vector x(s) of proper rational functions such that

A(s)x(s)=b(s) if and only if A(s) and [A(s) | b(s)] have the same contents

at inﬁnity. 2

Remark 5.1.7. A (proper) rational function matrix typically appears as

the transfer function matrix of a linear time-invariant dynamical system,

and the Smith–McMillan form at inﬁnity of the transfer function matrix has

control-theoretic signiﬁcances (decoupling, disturbance rejection, etc.). See

Bhattacharyya [11], Commault–Dion [37], Descusse–Dion [47], Hautus [103],

Hautus–Heymann [104, 105], Svaricek [307], and Verghese–Kailath [329].

The transfer function matrix of a system in the descriptor form

x(t)=Ax(t)+Bu(t), y

(t)=Cx(t)

with “state” x(t) ∈ R

, input u(t), and output y(t), is given by

P (s)=C(sF − A)

−1

provided that det(sF − A) = 0 (while F can be singular). In such a case it

is desirable to express the Smith–McMillan form at inﬁnity of P (s) directly

from the matrices F , A, B and C, without referring to the entries of P (s)

explicitly. From the formula (cf. Proposition 2.1.7)

det



A − sF B





= det(A − sF ) · det[−C



(A − sF )

−1



where C



denotes a submatrix of C with k rows and B



is a submatrix of B

with k columns, it follows that

(P )=δ

N+k

(D; I

) − δ

(A − sF ),

where

D(s)=



A − sF B



and J

are respectively the row and column sets corresponding to the

N × N nonsingular submatrix A − sF ,and

N+k

(D; I

) = max{deg

det D[I,J] | I ⊇ I

,J⊇ J

, |I| = |J| = N + k}

means the highest degree of a minor of order N + k that contains row set

and column set J

. Note that δ

N+k

(D; I

)=δ

N+k

(

D) − 2Nd for a

suﬃciently large integer d and

D(s)=



diag (s

, ···,s

) O



A − sF B



diag (s

, ···,s

) O



5.1 Polynomial/Rational Matrix 275

5.1.3 Matrix Pencil and Kronecker Form

A polynomial matrix A(s)=(A

(s)) with deg

(s) ≤ 1 for all (i, j)is

called a pencil. Obviously, a pencil A(s) can be represented as A(s)=sX +Y

in terms of a pair of constant matrices X and Y . A pencil A(s) is said to be

regular if it is square and det A(s) is a nonvanishing polynomial. A pencil is

called singular if it is not regular.

A pencil can be brought into a canonical block-diagonal matrix by means

of strict equivalence PA(s)Q using constant nonsingular matrices P and Q.

The block-diagonal matrix is known as the Kronecker form (Gantmacher [87,

Chap. XII]). For m ≥ 1andε ≥ 0, we deﬁne an m × m bidiagonal matrix

(s)andanε × (ε + 1) bidiagonal matrix L

(s)by

(s)=

⎛

⎜

⎝

1 s

⎞

⎟

⎠

(s)=

⎛

⎜

⎝

1 s

⎞

⎟

⎠

For η ≥ 0 we deﬁne U

(s) to be the transpose of L

(s).

Theorem 5.1.8 (Kronecker form). For a pencil A(s) over a ﬁeld F ,

there exist nonsingular matrices P and Q over F such that

PA(s)Q = block-diag (sI

+ B; N

(s), ···,N

(s);

(s), ···,L

(s); U

(s), ···,U

(s)), (5.6)

where

≥···≥m

≥ 1,ε

≥···≥ε

≥ 0,η

≥···≥η

≥ 0,

and B is an m

× m

matrix over F . The indices, m

; b, m

, ···,m

; c,

, ···,ε

; d, η

, ···,η

, are uniquely determined. Denoting r =rankA and

using δ

(A)(k =0, 1, 2, ···) in (5.3), we have

b = r − max

k≥0

(A),c= |Col(A)|−r, d = |Row(A)|−r, (5.7)

= δ

(A) −



i=1

−



j=1

, (5.8)

= δ

r−k

(A) − δ

r−k+1

(A)+1 (k =1, ···,b). (5.9)

For a regular pencil, in particular, the indices, m

; b, m

, ···,m

, are deter-

mined by δ

(A)(k =0, 1, 2, ···).

276 5. Polynomial Matrix and Valuated Matroid

Proof.

The formulas (5.7)–(5.9) can be derived from the block diagonal struc-

ture (5.6). The uniqueness of the indices ε

, ···,ε

and η

, ···,η

is not dif-

ﬁcult to establish.

The existence of block diagonal form (5.6) is proven here. Put A(s)=

sX + Y , where X and Y are matrices over F .

Claim: There exist nonsingular matrices

P and

Q over F and partitions

, ···,R

; R

∞

) and (C

, ···,C

; C

∞

)oftherowsetR and the column set

C of

A(s)=s

X +

Y =

P (sX + Y )

Q such that

rank

X[R

]=0 (1≤ j ≤ μ, j ≤ i ≤∞),

rank

Y [R

]=0 (1≤ j ≤ μ, j +1≤ i ≤∞),

rank

X[R

j−1

]=|C

| (2 ≤ j ≤ μ),

rank

X[R

∞

]=|C

∞

rank

Y [R

]=|R

| (1 ≤ i ≤ μ).

Here R

, R

∞

,andC

∞

can be empty, whereas other blocks are nonempty.

Note that

A(s) is an upper block-triangular matrix and that the rank condi-

tions imply

|≥|R

|≥|C

|≥|R

|≥···≥|C

|≥|R

|, |R

∞

|≥|C

∞

The upper block-triangular form in the claim can be constructed as fol-

lows. The column set C

is determined by a column-transformation for X,

since

X[R, C

]=O and

X[R, C \ C

] is of full-column rank by the rank

conditions. Then the row set R

is determined by a row-transformation for

the submatrix Y [R, C

], since

Y [R \R

]=O and

Y [R

] is of full-row

rank. Next, C

is determined by a column-transformation for the submatrix

X[R \R

,C\C

] (with X denoting the modiﬁed X), since

X[R \R

]=O

and

X[R \ R

, (C \ C

) \ C

)] is of full-column rank. Then the row set R

is determined from the submatrix Y [R \ R

]. Continuing this way, we

eventually arrive at C

μ+1

= ∅ for some μ ≥ 0; then we terminate by deﬁning

∞

and C

∞

to be the complements of



i=1

and



j=1

, respectively.

In the above claim we may further assume that

X[R

]=O unless 2 ≤ j = i +1≤ μ or i = j = ∞,

Y [R

]=O unless 1 ≤ i = j ≤∞,

X[R

j−1





(2 ≤ j ≤ μ),

X[R

∞



∞



Y [R





(1 ≤ i ≤ μ),

The present proof, valid for an arbitrary F ,iscommunicatedbyS.Iwata.See

Gantmacher [87, Chap. XII, §2] for an alternative proof in the case of F = C.

5.1 Polynomial/Rational Matrix 277

where I

denotes the identity matrix of order N . Then the matrix

A(s) takes

the form depicted in Fig. 5.1 for μ =4.

- - - - -

∞

Fig. 5.1. Matrix

A(s) in the proof for the Kronecker form (μ =4)

Consider the submatrix



i=1



j=1

]. With suitable permutations

of rows and columns, it can be put into a block-diagonal form with each

diagonal block being equal to N

(s) with 1 ≤ m ≤ μ or L

(s) with 0 ≤ ε ≤

μ−1, where N

(s) appears with multiplicity |R

|−|C

m+1

| (note: |C

μ+1

| =0)

and L

(s) with multiplicity |C

ε+1

|−|R

ε+1

|. Namely,



i=1



j=1

] = block-diag (N

(s), ···,N

(s); L

(s), ···,L

(s))

with

b =



i=1

|−



j=2

|,c=



j=1

|−



i=1

|{k | m

= m}| = |R

|−|C

m+1

| (1 ≤ m ≤ μ),

278 5. Polynomial Matrix and Valuated Matroid

|{k | ε

= ε}| = |C

ε+1

|−|R

ε+1

| (0 ≤ ε ≤ μ − 1).

For the submatrix

A[R

∞

], we apply the above argument to its trans-

pose. Let (

, ···,

ˆμ

;

∞

) and (

, ···,

ˆμ

;

∞

) be the resulting parti-

tions of R

∞

and C

∞

, respectively. Since rank

X[R

∞

]=|C

∞

|,wehave

| = |

i+1

| for i =1, ···, ˆμ − 1and|

ˆμ

| = 0. This means that there exist

nonsingular matrices

P and

Q such that

A[R

∞

]

Q = block-diag (U

(s), ···,U

(s); s

∞

where

∞

is nonsingular. Finally, we can transform

∞

to the identity ma-

trix to obtain the desired block-diagonal form (5.6).

The matrices N

(s)(k =1, ···,b) are called the nilpotent blocks and

the number m

= max

1≤k≤b

is the index of nilpotency. The indices

{ε

, ···,ε

} and {η

, ···,η

} are called Kronecker column indices and row

indices, respectively. For algorithms to compute the Kronecker form, see the

references in Golub–Van Loan [97, pp. 389–390].

Remark 5.1.9. The Kronecker form is a fundamental tool for the analysis

of a dynamical system in the descriptor form (Katayama [155], Luenberger

[182, 183]):

= Ax + Bu, (5.10)

where the matrix F is square (n×n) but not necessarily nonsingular. Consider

the Laplace transform

of the above system:

A − sF





= −F x(0−),

where s is the symbol (or indeterminate) standing for the diﬀerentiation with

respect to time, and

x and

u are the Laplace transforms of x(t)andu(t),

respectively. For the unique solvability, as a system of diﬀerential equations

in x, the matrix A − sF is usually assumed to be a regular pencil.

Then, by Theorem 5.1.8, there exist two real-constant nonsingular matri-

ces P and Q such that

P (A − sF )Q = block-diag (A

− sI

; I

− sJ

, ···,I

− sJ

) ,

where J

is an m × m matrix deﬁned by N

(s)=I

+ sJ

. Using this we

can rewrite the descriptor form (5.10) into

= A

+ B

u, (5.11)

= x

+ B

u (k =1, ···,b), (5.12)

To be more precise, L

−

transform (Kailath [152, §1.2]) deﬁned by

x(s)=



∞

0−

x(t)e

−st

dt.

5.1 Polynomial/Rational Matrix 279

where x

∈ R

for k =0, 1, ···,b and

⎛

⎜

⎝

⎞

⎟

⎠

= Q

−1

⎛

⎜

⎝

⎞

⎟

⎠

= PB.

The subsystems in (5.11) and (5.12) admit explicit solutions:

(t) = exp(A

t)x

(0) +



exp[A

(t − τ )]B

u(τ)dτ,

(t)=−



−2



p=0

(p)

(t)J

p+1



(0−) −

−1



p=0

(p)

(t)

(k =1, ···,b),

where δ

(p)

(t)andu

(p)

(t)arethepth derivatives of the Dirac delta func-

tion (the unit impulse function) and the input-vector u(t), respectively.

Thus the ﬁrst subsystem (5.11), in the standard form, expresses the ex-

ponential modes, while the second (5.12) accounts for the impulse modes.

In this context, m

= deg

det(A − sF ) is sometimes called the dynami-

cal degree (Hayakawa–Hosoe–Ito [108]), which stands for the number of ex-

ponential modes, whereas the number of impulse modes is represented by



k=1

− 1) = rank F − deg

det(A − sF ). See Suda [303] for more about

the role of the Kronecker form in control theory. 2

Remark 5.1.10. The index of nilpotency has an important signiﬁcance in

numerical analysis of a system of equations consisting of a mixture of dif-

ferential and algebraic relations, which is often abbreviated to DAE in the

literature of numerical analysis. For a linear time-invariant DAE in general,

say Ax = b with A = A(s) being an n ×n nonsingular polynomial matrix in

s, the index is deﬁned by

ν(A) = max

i,j

deg

−1

)

+1.

Here it should be clear that each entry (A

−1

)

of A

−1

is a rational function

in s. An alternative expression for ν(A)is

ν(A)=δ

n−1

(A) − δ

(A)+1.

When deg

(s) ≤ 1 for all (i, j), the index ν(A) agrees with the index of

nilpotency of A as a matrix pencil; namely, we have ν(A)=m

The solution x to Ax = b is of course given by x = A

−1

b, and therefore

ν(A) − 1 equals the highest order of the derivatives of the input b that can

possibly appear in the solution x. As such, a high index indicates the diﬃculty

280 5. Polynomial Matrix and Valuated Matroid

in numerical solution of the DAE, and sometimes even the inadequacy in

mathematical modeling. The structural approach to the DAE index has been

expounded in Chap. 1. See Brenan–Campbell–Petzold [21], Gear [88, 89],

Hairer–Wanner [101], and Ungar–Kr¨oner–Marquardt [324] for more about

the index of DAE. 2

Remark 5.1.11. It turns out that the Smith form of a polynomial matrix is

closely related, at least in the generic case, to the DM-decomposition and the

CCF of LM-matrices (to be explained in §6.3). The combinatorial properties

of the degree of subdeterminants, on the other hand, will be investigated in

the next section in a more abstract framework of “valuated matroids.” 2

5.2 Valuated Matroid

5.2.1 Introduction

While matroids are a combinatorial abstraction of matrices over a ﬁeld with

respect to linear independence, valuated matroids originate from a combina-

torial structure of polynomial/rational matrices with respect to the degree of

determinants. The axiomatic development will be motivated and illustrated

by the special case of polynomial/rational matrices. The concept of valuated

matroids was introduced by Dress–Wenzel [54, 57].

A valuated matroid is a pair M =(V,ω) of a ﬁnite set V and a function

ω :2

→ R ∪ {−∞} such that

B = {B ⊆ V | ω(B) = −∞} (5.13)

is nonempty and that the following exchange property holds:

(VM) For B, B



∈Band u ∈ B \ B



, there exists v ∈ B



\ B such

that B − u + v ∈B, B



+ u − v ∈B,and

ω(B)+ω(B



) ≤ ω(B −u + v)+ω(B



+ u − v). (5.14)

If this is the case, B satisﬁes the simultaneous exchange property:

(BM

)ForB,B



∈Band for u ∈ B \ B



, there exists v ∈ B



\ B

such that B −u + v ∈Band B



+ u − v ∈B

introduced in §2.3.4, and accordingly B forms the basis family of a matroid.

Therefore, we can alternatively say that a valuated matroid is a triple M =

(V,B,ω), where (V,B) is a matroid (deﬁned in terms of the basis family) and

ω : B→R is a function satisfying (VM). It is also said that ω is a valuation

of the matroid (V,B). We denote by r the rank of the underlying matroid

(V,B).

A valuated matroid M =(V,B,ω) such that ω(B) = 0 for all B ∈Bcan

be identiﬁed with the underlying matroid (V,B). In fact, (VM) for ω :2

→

{0, −∞} reduces to (BM

). This ω is called the trivial valuation.

5.2 Valuated Matroid 281

Remark 5.2.1. As we have seen in §2.3, the theory of matroids oﬀers deep

and useful results for a pair of matroids (independent matchings as well as

intersection in §2.3.5 and union in §2.3.6). The most interesting part of the

theory of valuated matroids lies in a generalization of these results, to be

described in §5.2.9. Speciﬁcally, for two valuated matroids M

=(V,B

,ω

)

and M

=(V, B

,ω

), the “sum” ω

+ ω

turns out to be a nice combi-

natorial object, though it is not a valuated matroid in general. Note that

(ω

+ ω

)(B) > −∞ if and only if B is a common base (i.e., B ∈B

∩B

). 2

5.2.2 Examples

Examples of valuated matroids are shown.

Example 5.2.2. A linear weighting on a matroid (V,B) is a valuation. That

is, for p : V → R and α ∈ R, the function ω : B→R deﬁned by

ω(B)=α +



{p(u) | u ∈ B} (B ∈B)

is a matroid valuation, satisfying (VM) with equality in (5.14). Such ω is

called a separable valuation. 2

Example 5.2.3. Let A(s)beanm × n matrix of rank m with each en-

try being a rational function in a variable s,andlet(C, B) denote the

(linear) matroid deﬁned on the column set C of A(s) in terms of the

linear independence of the column vectors (cf. Example 2.3.8). Namely,

B = {B ⊆ C | det A[R, B] =0}, where R denotes the row set of A. Then

ω : B→

Z deﬁned by

ω(B) = deg

det A[R, B](B ∈B) (5.15)

is a valuation of (C, B). In fact, by considering the degree of the terms in the

Grassmann–Pl¨ucker identity (Proposition 2.1.4):

det A[R, B] · det A[R, B





j∈B



det A[R, B − i + j] · det A[R, B



+ i − j]

for i ∈ B \ B



, we obtain

ω(B)+ω(B



) ≤ max

j∈B



[ω(B − i + j)+ω(B



+ i − j)] ,

the exchange axiom (VM). This observation by Dress–Wenzel [57] is the origin

of the concept of valuated matroids.

A concrete instance of (nonseparable) valuation of this kind is provided

A(s)=

s +1 s 10

1111