Murota K. Matrices and Matroids for Systems Analysis

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

3.2 Algebraic Implication of Dimensional Consistency 121

ring deﬁned appropriately with reference to physical dimensions. Several im-

plications of this fact are discussed in §3.3 in connection to the mathematical

framework for the structural analysis introduced in §3.1. To reﬂect the dual

viewpoint from structural analysis and dimensional analysis, the notion of

“physical matrix” is introduced as a mathematical model of a typical matrix

that we encounter in real physical systems. The concept of physical matrix

plays a central role, especially in the structural analysis of dynamical systems,

to be treated in Chap. 6.

3.2.2 Dimensioned Matrix

A physical system is usually described by a set of relations among relevant

physical quantities, to each of which is assigned a physical dimension. When

asetoffundamental dimensions, or equivalently, a set of fundamental quan-

tities, is chosen, the dimensions of the remaining physical quantities can be

uniquely expressed by the so-called dimensional formulas. For example, a

standard choice of fundamental quantities in mechanics consists of length L,

mass M and time T , and the dimensional formula for force is then given by

[LMT

−2

]=[L][M ][T ]

−2

or simply by LMT

−2

. In general, the exponents to

the fundamental dimensions, namely the powers in the dimensional formula,

may take on not only integers but also rational numbers.

Here we do not go into philosophical arguments such as those on what

the physical dimensions are and which set of physical quantities are most

fundamental. Instead we assume that the fundamental quantities with the

associated fundamental dimensions are given along with the dimensional for-

mulas for other quantities.

Let us consider a linear (or linearized) system represented by a system of

linear equations:

Ax = b, (3.21)

where we assume that the entries of the m × n matrix A =(A

), as well as

the components of x =(x

)andb =(b

), belong to some ﬁeld F , namely,

∈ F (i =1, ···,m; j =1, ···,n).

It is also assumed that F is an extension of the ﬁeld Q of rational numbers

(i.e., F ⊇ Q).

Let Z

, ···,Z

be a chosen set of fundamental quantities. Not only the

components of x and b but also the entries of A have physical dimensions,

expressed in the form of

]

···[Z

]

with exponents p

∈ Q (k =1, ···,d).

From the algebraic point of view, we may regard Z

, ···,Z

as indeter-

minates over F and consider the extension ﬁeld E of F generated over F by

all the formal fractional powers of Z

, ···,Z

; i.e.,

122 3. Physical Observations for Mixed Matrix Formulation

E = F ({Z

···Z

| p

∈ Q,k =1, ···,d}). (3.22)

Accordingly, (3.21) may be replaced by the following system of equations in

the extension ﬁeld E:

x =

b, (3.23)

where

= A



k=1

ijk

, ˜x

= x



k=1

= b



k=1

(3.24)

with the exponents p

ijk

, c

, r

of rational numbers representing the physical

dimensions. The ith equation of (3.23) reads



j:A

=0





k=1

ijk



= b



k=1

. (3.25)

The principle of dimensional homogeneity means the physical dimensional

consistency of the ith equation in the sense that

[Dimension of (i, j)entry]× [Dimension of jth column]

= [Dimension of ith row]

for each (i, j) with A

= 0. It follows from (3.25) that the physical dimen-

sional consistency is equivalent to the relations

ijk

= r

− c

(i =1, ···,m; j =1, ···,n; k =1, ···,d) (3.26)

among the exponents p

ijk

, c

, r

. Based on this observation we will deﬁne

the notion of dimensioned matrix as follows.

Let

A =(

) be a matrix over E (deﬁned by (3.22)) which is expressed

as in (3.24) with exponents p

ijk

∈ Q. We call

A a dimensioned matrix if

(3.26) holds for some suitably chosen r

and c

(∈ Q). The set of m × n

dimensioned matrices with ground ﬁeld F and fundamental quantities (i.e.,

indeterminates) Z

, ···,Z

will be denoted by D(F ; m, n; Z

, ···,Z

), or sim-

ply by D(F ; Z

, ···,Z

) if the size is not relevant.

The following proposition is a restatement of the deﬁnition, where

= diag



k=1

, ···,



k=1

(

, (3.27)

= diag



k=1

, ···,



k=1

(

(3.28)

with r

∈ Q and c

∈ Q (i =1, ···,m; j =1, ···,n; k =1, ···,d).

3.2 Algebraic Implication of Dimensional Consistency 123

Proposition 3.2.1. A matrix

A over E belongs to D(F ; m, n; Z

, ···,Z

) if

and only if it can be expressed as

A = D

−1

where A is a matrix over F ,andD

and D

are nonsingular diagonal matrices

of (3.27) and (3.28). 2

Example 3.2.2. Recall the mechanical system (Fig. 3.5) of Example 3.1.7.

As the fundamental quantities in dimensional analysis, we may choose time

T , length L and mass M. Then the dimensions of velocity and force are given

by T

−1

L and T

−2

LM, respectively. The physical dimensions associated with

the equations, i.e., with the rows of D(s)are

row 1 row 2 row 3 row 4 row 5 row 6

velocity velocity force force force velocity

−1

−2

LM T

−2

LM T

−2

LM T

−1

(3.29)

whereas those with the variables (x

and u), i.e., with the columns of D(s),

are

col 1 col 2 col 3 col 4 col 5 col 6 col 7

length length velocity velocity force velocity force

LLT

−1

−2

LM T

−1

−2

(3.30)

Accordingly, the diagonal matrices D

and D

of (3.27) and (3.28) are given

= diag [T

−1

L, T

−1

L, T

−2

LM, T

−2

LM, T

−2

LM, T

−1

L],

= diag [L, L, T

−1

L, T

−1

L, T

−2

LM, T

−1

L, T

−2

LM],

where T = Z

=time, L = Z

=length and M = Z

=mass.

In this example, any minor of Q(s)=[Q

− sQ

| Q

] of (3.18) can

easily be veriﬁed to be a monomial in s over Q. In fact, this is a general

phenomenon, to be discussed in §3.3; see Example 3.3.1. 2

3.2.3 Total Unimodularity of a Dimensioned Matrix

Let R be an integral domain, i.e., a commutative ring without zero divisors

and with a unit element. An element of R is called invertible if there exists

another element of R such that their product equals the unit element. A

matrix over R is said to be totally unimodular (over R) if every nonvanishing

minor (=subdeterminant) is an invertible element of R. We will denote by

U(R; m, n) the set of m × n totally unimodular matrices over R, or simply

by U(R) if the size is not relevant. The signiﬁcance of this concept

lies in

In the canonical case of R being the ring of integers, the total unimodularity of

incidence matrices of graphs is known to play substantial roles in combinatorial

optimization (Lawler [171], Schrijver [292]).

124 3. Physical Observations for Mixed Matrix Formulation

the fact that, if a matrix is totally unimodular over R, not only its inverse

but also all its pivotal transforms are matrices over R. The objective of this

section is to point out that the dimensioned matrices can be characterized as

totally unimodular matrices over a certain ring.

Consider a ring generated over F by all the formal fractional powers of

, ···,Z

F Z

, ···,Z

 = F [{Z

···Z

| p

∈ Q,k=1, ···,d}]. (3.31)

Obviously, F Z

, ···,Z

 is an integral domain whose quotient ﬁeld is the

ﬁeld E deﬁned in (3.22). An element of F Z

, ···,Z

 is invertible if and

only if it is of the form:



k=1

(α ∈ F \{0},p

∈ Q for k =1, ···,d).

As an immediate consequence of the deﬁnition, a dimensioned matrix is

totally unimodular over F Z

, ···,Z

.

Proposition 3.2.3. D(F ; Z

, ···,Z

) ⊆U(F Z

, ···,Z

).

That is, for

A ∈D(F ; Z

, ···,Z

) it holds that, for any (I,J),

det

A[I,J]=α



k=1

for some α ∈ F and p

∈ Q (k =1, ···,d).

Proof. The expression (3.24) of

A with p

ijk

= r

− c

implies

det

A[I,J] = det A[I,J] ·



k=1

with p



i∈I

−



j∈J

∈ Q.

Moreover, these two classes of matrices coincide with each other, as stated

in Theorem 3.2.4 below. This theorem, coupled with Proposition 3.2.1, pro-

vides us with a concrete representation of a totally unimodular matrix over

F Z

, ···,Z

.

Theorem 3.2.4. D(F ; Z

, ···,Z

)=U(F Z

, ···,Z

).

Proof. By Proposition 3.2.3, it suﬃces to show that every totally unimodular

matrix over F Z

, ···,Z

 is a dimensioned matrix. Furthermore, the proof

can be reduced to the case of d = 1 by induction on d,andthepresent

theorem follows from Proposition 3.2.5 below.

3.2 Algebraic Implication of Dimensional Consistency 125

Proposition 3.2.5. Let Z be an indeterminate over F ,andlet

A =(

)

be an m × n totally unimodular matrix over F Z, i.e.,

A ∈U(F Z; m, n).

Then there exist A

∈ F , r

∈ Q and c

∈ Q (i =1, ···,m; j =1, ···,n)

such that

= A

−c

’s are uniquely determined as A

Z=1

,whiler

’s and c

’s are not.)

Proof. By deﬁnition,

canbeexpressedas

= A

∈ F ,p

∈ Q).

Consider a bipartite (directed) graph G =(V

−

; E) associated with

where V

corresponds to the row set of

A and V

−

to the column set, and

the arc set E is deﬁned as E = {(i, j) |

=0}. By Theorem 2.2.35(2), p

canbeexpressedasp

= r

− c

for some suitable r

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

(j =1, ···,n) if the algebraic sum of p

’s along any circuit in G is equal to

zero.

Suppose, to the contrary, that there exists a circuit in G along which

the algebraic sum (cf. (2.59)) of p

’s is distinct from zero. Let C

be such a

circuit with the minimal number of arcs, and let i

, ···,i

(= j

)

be the sequence of vertices lying on C

, where I = {i

, ···,i

}⊆V

and

J = {j

, ···,j

}⊆V

−

. Then, putting

p =



r=1

,q=



r=1

r−1

we have p = q.

The minimal circuit C

has no chord, that is, if (i





) is an arc, then



−r



≡ 0or1(mods). Therefore the determinant of the submatrix

A[I,J]

is equal, up to a sign, to

Δ =



r=1

+(−1)

s−1



r=1

r−1

= αZ

+ βZ

where

α =



r=1

=0,β=(−1)

s−1



r=1

r−1

=0.

Since p = q, Δ is not invertible in F Z. This contradicts the total unimod-

ularity of

We conclude this section with a rather obvious remark on the use of the

principle of dimensional consistency in structural analysis. When we are given

a system of equations that is supposed to represent a physical system, we can

sometimes detect errors in its description by verifying the condition (3.26):

126 3. Physical Observations for Mixed Matrix Formulation

ijk

= r

− c

for dimensional homogeneity. In case r

and c

are known

along with p

ijk

, the test for (3.26) is straightforward. Even in the case where

only p

ijk

are given, without information about r

and c

, we can eﬃciently

decide whether (3.26) can be satisﬁed for some suitable r

and c

: Consider

a tree in the bipartite graph associated with A, and for each k,setr

and

so that the condition (3.26) may be satisﬁed for the tree arcs, and then

check if (3.26) holds for all cotree arcs (see the proof of Proposition 3.2.5).

Notes. This section is based on Murota [200] as well as Murota [204].

3.3 Physical Matrix

3.3.1 Physical Matrix

We have already introduced two concepts of matrices that we encounter in the

description of real systems, namely the mixed matrix and the dimensioned

matrix. The former is motivated by structural analysis while the latter derives

from dimensional analysis. In this section these two are combined to a third

concept of “physical matrix” which models a matrix arising from real-world

systems.

As has been discussed in §3.2.2, when we describe a physical system in the

form of Ax = b with an m×n matrix A over F , we usually know the physical

dimensions associated with its rows and columns. Then we can determine the

dimensioned matrix

A over F Z

, ···,Z

 that corresponds to A by (3.24)

and (3.26) (see (3.31) for the deﬁnition of F Z

, ···,Z

). We call

A the

dimensioned matrix corresponding to A (with the implicit understanding of

the given physical dimensions). By Proposition 3.2.1, this correspondence

between A and

A ∈D(F ; m, n; Z

, ···,Z

) is given by

A = D

−1

, (3.32)

where D

and D

are the known diagonal matrices of (3.27) and (3.28) rep-

resenting the physical dimensions of the rows (equations) and the columns

(variables).

When A is a mixed matrix of the form A = Q + T with a ground ﬁeld

K (⊆ F ), i.e., when A ∈ MM(K, F ; m, n), we can express the corresponding

dimensioned matrix

A of (3.32) as

A =

Q +

with

Q = D

−1

T = D

−1

This shows that

A is also a mixed matrix, but with the quotient ﬁeld of

KZ

···,Z

 as the ground ﬁeld. In a slight abuse of notation we may write

A ∈ MM(KZ

, ···,Z

, F Z

, ···,Z

; m, n). In particular,

Q is a matrix

3.3 Physical Matrix 127

over KZ

, ···,Z

. Note also that the matrices

Q and

T constituting the

mixed matrix

A coincide with the dimensioned matrices corresponding to Q

and T , respectively.

The most important physical observation to be made here is concerned

with the physical dimensions of the nonvanishing entries of Q. Usually, the

matrix Q represents various kinds of conservation laws or structural equa-

tions, and consists of incidence coeﬃcients such as those induced from the

underlying topological/geometrical incidence relations in electrical networks

and the stoichiometric coeﬃcients in chemical reactions. Thus it is natural

to expect that

The nonvanishing entries of Q are dimensionless. (3.33)

This statement is true of the examples considered above, provided that

the generality assumption GA2 is accepted. In fact, the claim (3.33) can

be veriﬁed easily for the coeﬃcient matrix (3.3) of the electrical network

of Example 3.1.2, for the matrices F , A and B in (3.17) of the mechanical

system of Example 3.1.7, and also for the Jacobian matrix (Fig. 3.4) of the

ethylene dichloride production system of Example 3.1.3.

The observation (3.33) above can be stated in algebraic terms as follows.

Let A = Q + T ∈ MM(K, F ) be a mixed matrix and

A be the corresponding

dimensioned matrix expressed as (3.24) with exponents p

ijk

of dimensions.

The condition that the nonvanishing entries of Q are dimensionless is equiv-

alent to:

= 0 implies p

ijk

=0 for k =1, ···,d; (3.34)

or alternatively,

−1

= Q (3.35)

with reference to (3.32). The condition (3.34), or (3.35), does not exclude

dimensionless nonvanishing entries from T ; for instance, in Example 3.1.2,

the parameters α and β contained in T are dimensionless.

We are now in the position to introduce the concept of physical matrices

as a mathematical model of the matrices that we encounter in real-world sys-

tems. It reﬂects the dual viewpoint from structural analysis and dimensional

analysis.

Suppose a matrix A over F is given along with a subﬁeld K of F and

a pair (D

) of diagonal matrices of the forms (3.27) and (3.28), respec-

tively. We say that a matrix A over F is a physical matrix with respect to

(K, F ; D

), if

(i) A = Q + T is a mixed matrix with respect to (K, F ), and

(ii) D

−1

= Q.

When (D

, D

) is understood, we say simply that A is a physical matrix with

respect to (K, F ).

128 3. Physical Observations for Mixed Matrix Formulation

3.3.2 Physical Matrices in a Dynamical System

In the previous section we considered the physical dimensional consistency

for mixed matrices to arrive at the concept of physical matrix. We now ex-

tend this approach to mixed polynomial matrices that describe linear time-

invariant dynamical systems.

Recalling the notation from §3.1.2 let

A(s)=



k=0



k=0



k=0

= Q(s)+T (s)

be an m ×n mixed polynomial matrix with A

= Q

+ T

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

Let (D

) be the pair of matrices of (3.27) and (3.28) representing the

physical dimensions of A = A(s), where we assume that time is chosen as

one of the fundamental dimensions, say Z

The most important fact to note here is:

The symbol s should have the dimension of Z

−1

(the inverse of time)

since it represents “d/dt” (the diﬀerentiation with respect to time).

It then follows that, for each k =0, 1, ···,N, the dimensions associated with

the coeﬃcient matrix A

is given by (D

−k

), since (D

) is associ-

ated with s

Let us now assume that the coeﬃcient matrix A

= Q

+ T

is a physical

matrix, namely, that

−k

)

−1

= Q

This implies

Q(s) D

−1



k=0

−1



k=0

(sZ

−1

)

= Q(sZ

−1

Substitution of Z

= s (and Z

=1fork ≥ 2) into this expression reveals a

remarkable identity: Q(s)=(D

)

−1

Q(1) (D

), that is,

Q(s) = diag [s

−r

, ···,s

−r

] · Q(1) · diag [s

, ···,s

]

using the exponents r

∈ Q and c

∈ Q in (3.27) and (3.28). This relation

shows the existence of r

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

∈ Q (j =1, ···,n)

such that r

− c

= deg

∈ Z for all (i, j) with Q

= 0. This implies the

existence of such r

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

∈ Z (j =1, ···,n) by Theorem

2.2.35(2). That is,

Q(s) = diag [s

, ···,s

] · Q(1) · diag [s

−c

, ···,s

−c

] (3.36)

for some r

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

∈ Z (j =1, ···,n). Note that, if r

∈ Z

and c

∈ Z, we may take r

= −r

and c

= −c

, and the exponents r

and

have a natural physical meaning.

3.3 Physical Matrix 129

We have thus revealed an important property (3.36) of the Q-part of a

mixed polynomial matrix that is subject to dimensional consistency. In other

words, we have identiﬁed a subclass of mixed polynomial matrices on the

basis of dimensional analysis.

Example 3.3.1. For the mechanical system (Fig. 3.5) treated in Examples

3.1.7 and 3.2.2, the matrix Q(s)=[Q

− sQ

| Q

] of (3.18) admits an

expression of the form (3.36):

−s 010000

0 −s 01000

0000−10 1

0 000100

0000−10 0

−ss00010

s 00000

0 s 0000

00s

000

00 0 s

00 0 0 s

00000s

−1010000

0 −101000

0000−10 1

0 000100

0000−10 0

−1100010

100000 0

010000 0

00s

−1

000 0

00 0 s

−1

00 0

00 0 0 s

−2

0 0

00 0 0 0 s

−1

000000s

−2

Note that the diagonal entries s

and s

−c

are determined from the negative

of the exponents to T (time) in (3.29) and (3.30) as

, ···,r

)=(1, 1, 2, 2, 2, 1), (c

, ···,c

)=(0, 0, 1, 1, 2, 1, 2).

The decomposition property (3.36) is equivalent to the total unimodular-

ity in K[s, 1/s], the ring of Laurent polynomials, as follows. Recall that

K[s, 1/s]={



k=−N

| 0 ≤ N

∈ Z,α

∈ K (−N

≤ k ≤ N

)}

and that an element of K[s, 1/s] is invertible if and only if it is of the form

αs

for some α ∈ K \{0} and p ∈ Z.Ifanm × n matrix Q(s) admits

a decomposition (3.36) with some r

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

∈ Z (j =

1, ···,n), then every subdeterminant of Q(s)isoftheformαs

with α ∈ K

and p ∈ Z.Thatis,Q(s) is a total unimodular matrix over K[s, 1/s]. The

following theorem reveals that the converse is also true.

Theorem 3.3.2. Let Q(s) be an m ×n matrix over K[s, 1/s].ThenQ(s) is

totally unimodular over K[s, 1/s] if and only if

130 3. Physical Observations for Mixed Matrix Formulation

Q(s) = diag [s

, ···,s

] · Q(1) · diag [s

−c

, ···,s

−c

] (3.37)

for some integers r

(i =1, ···,m) and c

(j =1, ···,n). For a polynomial

matrix Q(s), in particular, every (nonvanishing) subdeterminant of Q(s) is

a monomial in s over K if and only if (3.37) is true for some integers r

(i =1, ···,m) and c

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

Proof. This is a corollary of Theorem 3.2.4 (or rather Proposition 3.2.5).

Theorem 3.3.2 allows us to characterize the mixed polynomial matrices

having property (3.36) as those polynomial matrices A(s)=Q(s)+T (s)

which satisfy

(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,and

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

independent over K.

Namely, (MP-Q2) and (MP-T) characterize the physically meaningful sub-

class of mixed polynomial matrices subject to dimensional consistency.

The extra property (MP-Q2), or equivalently (3.36), has signiﬁcant im-

plications with respect to computational complexity in applications of mixed

polynomial matrices.

Proposition 3.3.3. Let M(Q(s)) denote the matroid deﬁned on the column

set of Q(s) by the linear independence of the column vectors over K(s).If

Q(s) is a total unimodular matrix over K[s, 1/s], then M(Q(s)) = M(Q(1)),

and therefore M(Q(s)) is representable over K. 2

Proposition 3.3.4. If Q(s) admits the decomposition (3.36), then

deg

det Q[I,J]=





i∈I

−



j∈J

(if det Q(1)[I,J] =0)

−∞ (otherwise).

Here Q(1) is a matrix over K and therefore det Q(1)[I,J] can be computed

by means of arithmetic operations over K. 2

In Chap. 6 we shall investigate some problems such as dynamical degree

and controllability for dynamical systems described by mixed polynomial

matrices A(s)=Q(s)+T (s) having the additional property (MP-Q2) for

K = Q.

Notes. This section is based on Murota [200] as well as Murota [204].