Murota K. Matrices and Matroids for Systems Analysis

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

4.4 Combinatorial Canonical Form of LM-matrices 171

+ ξ

=0,ξ

− ξ

=0,ξ

− ξ

=0,

and two loops consisting of branches 1–5–4 and 2–3–4 for the KVL (Kirch-

hoﬀ’s voltage law) to obtain

+ η

− η

=0,η

+ η

− η

=0.

These conservation equations have been written in a matrix form:





= 0. (4.38)

The Kirchhoﬀ’s conservation laws could have been represented equally

well in a diﬀerent way. For example, another set of three nodes b, c, d for the

KCL yields

−ξ

+ ξ

=0, −ξ

+ ξ

=0,ξ

+ ξ

=0,

and another choice of two independent loops 1–5–4 and 1–2–3–5 for the KVL

leads to

−η

− η

+ η

=0, −η

+ η

− η

=0.

Then we would obtain







= 0 (4.39)

with another coeﬃcient matrix Q



, which is identical with Q



of (4.36).

There seems to be nothing with which to choose between the two expres-

sions (4.38) and (4.39) in themselves. The conservation laws claim that (ξ, η)

should belong to a linear subspace, but does not prescribe how the linear

space should be described. Both (4.38) and (4.39) are legitimate descriptions

of one and the same subspace, and as a consequence, the coeﬃcient matrices

Q and Q



are related as Q



= SQ. The transformation matrix S in the LM-

admissible transformation (4.35) serves to yield a hierarchical decomposition

independent of an arbitrary choice in the description of the conservation laws.

Such invariance or stability of the CCF should be compared favorably with

the susceptibility of the DM-decomposition. In fact, the DM-decomposition

of A yields a coarser decomposition

↑

∪ C

whereas that of

A is given by (4.37). 2

172 4. Theory and Application of Mixed Matrices

4.4.2 Theorem of CCF

This section is to establish the combinatorial canonical form (CCF) of LM-

matrices, which has already been introduced informally by means of examples

in §4.4.1. We shall prove the existence and uniqueness of the ﬁnest proper

block-triangular decomposition of an LM-matrix (“proper” in the sense of

§2.1.4) under the LM-admissible transformation (4.35).

The LM-surplus function p :2

→ Z deﬁned as p(J)=ρ(J)+γ(J) −|J|

in (4.16) plays a crucial role. Key facts about p are the following:

1. The rank of an LM-matrix is characterized by the minimum of p (cf. The-

orem 4.2.5).

2. The function p is submodular (cf. (4.17)).

3. The function p is invariant under LM-equivalence. Namely, if

A is LM-

equivalent to A, the LM-surplus function ˆp associated with

A is the same

as p.

Seeing that the rank of A is expressed by the minimum of p,itisnaturalto

look at the family of minimizers:

min

(p)={J ⊆ C | p(J) ≤ p(J



), ∀J



⊆ C}, (4.40)

which forms a sublattice of 2

by virtue of the submodularity (4.17) of p

(cf. Theorem 2.2.5).

We are going to make use of a general decomposition principle, the

Jordan–H¨older-type theorem for submodular functions, explained in §2.2.2.

According to this, the sublattice L

min

(p) determines a pair of a partition of

C = Col(A) and a partial order :

P(L

min

(p)) = ({C

; C

, ···,C

; C

∞

}, ). (4.41)

Here b ≥ 0andC

= ∅ for k =1, ···,b, whereas C

and C

∞

are distin-

guished blocks that can be empty. It is assumed that the blocks are indexed

consistently with the partial order in the sense that

 C

⇒ k ≤ l. (4.42)

The following theorem claims the existence of the CCF, a proper block-

triangular decomposition of an LM-matrix under LM-equivalence. It was es-

tablished ﬁrst in an unpublished report of Murota [201] in 1985 and published

by Murota [204] and Murota–Iri–Nakamura [239].

Theorem 4.4.4 (Combinatorial Canonical Form). For an LM-matrix

A ∈ LM(K, F ) there exists another LM-matrix

A which is LM-equivalent to

A and satisﬁes the following properties.

(B1) [Nonzero structure and partial order  ]

A is block-triangularized,

i.e.,

A[R

]=O if 0 ≤ l<k≤∞, (4.43)

4.4 Combinatorial Canonical Form of LM-matrices 173

with respect to partitions (R

; R

, ···,R

; R

∞

) and (C

; C

, ···,C

; C

∞

) of

the row set Row(

A) and the column set Col(

A) respectively, where b ≥ 0,

= ∅ and C

= ∅ for k =1, ···,b,andR

∞

and C

∞

can be empty.

Moreover, when Col(

A) is identiﬁed with Col(A), the above partition

; C

, ···,C

; C

∞

) agrees with that deﬁned by the lattice L

min

(p) and the

partial order on {C

, ···,C

} induced by the zero/nonzero structure of

agrees with the partial order  deﬁned by L

min

(p); i.e.,

A[R

]=O unless C

 C

(1 ≤ k, l ≤ b); (4.44)

A[R

] = O if C

≺· C

(1 ≤ k, l ≤ b). (4.45)

(B2) [Size of diagonal blocks]

| < |C

| or |R

| = |C

| =0,

| = |C

| > 0fork =1, ···,b,

∞

| > |C

∞

| or |R

∞

| = |C

∞

| =0.

(B3) [Rank of diagonal blocks]

rank

A[R

]=|R

rank

A[R

]=|R

| = |C

| for k =1, ···,b,

rank

A[R

∞

]=|C

∞

(B4) [Rank of submatrices of diagonal blocks]

rank

A[R

\{j}]=|R

| (j ∈ C

rank

A[R

\{i},C

\{j}]=|R

|−1=|C

|−1(i ∈ R

,j ∈ C

)

for k =1, ···,b,

rank

A[R

∞

\{i},C

∞

]=|C

∞

| (i ∈ R

∞

(B5) [Uniqueness]

A is the ﬁnest proper block-triangular matrix that

is LM-equivalent to A. Namely, if

A is LM-equivalent to A and is block-

triangularized with respect to certain partitions (

;

, ···,

;

∞

) and

(

;

, ···,

;

∞

) of Row(

A) and Col(

A) (= Col(A)) with the diagonal

blocks satisfying the conditions (B2) and (B3), then each

is a union of

some blocks in (C

; C

, ···,C

; C

∞

Proof. A constructive proof is given in §4.4.3.

The matrix

A in the theorem is called the CCF of A. The CCF is uniquely

determined so far as the partitions of the row and column sets as well as the

partial order among the blocks are concerned, whereas there remains some

indeterminacy, or degree of freedom, in the numerical values of the entries

in the Q-part. For example, elementary row transformations within a block

change numerical values without aﬀecting the block structure. When the

174 4. Theory and Application of Mixed Matrices

numerical indeterminacy is to be emphasized, such

A will be called a CCF,

instead of the CCF. In Example 4.4.1, for instance, both of

A =

⎡

⎣

⎤

⎦



⎡

⎣

−1

0 −1

⎤

⎦

are qualiﬁed as the CCF of A.

The submatrices

A[R

]and

A[R

∞

] are called the horizontal tail

and the vertical tail, respectively. The tails are nonsquare if they are not

empty, and the “discrepancies from squareness”:

= |C

|−|R

|,δ

∞

= |R

∞

|−|C

∞

indicate the rank deﬁciencies of the whole matrix A, since

= |C|−rank

A = |C|−rank A, δ

∞

= |R|−rank

A = |R|−rank A

by (B1) and (B3). Thus the rank deﬁciency is localized to the tails. In partic-

ular, A is nonsingular if and only if both tails are empty (i.e., C

= R

∞

= ∅).

For a nonsingular A, the CCF gives a ﬁner decomposition than the

DM-decomposition, as is expected from the comparison of the admissible

transformations: P





for the CCF and P

for the DM-

decomposition. This can be explained also in terms of the LM-surplus func-

tion p of (4.16) and the (original) surplus function p

of (2.39) deﬁned as

(J)=γ

(J) −|J|,J⊆ C,

with

(J)=|{i ∈ Row(A) |∃j ∈ J : A

=0}|,J⊆ C. (4.46)

Proposition 4.4.5. If A ∈ LM(K, F ) is nonsingular, then min p = min p

=0and L

min

(p) ⊇L

min

). Hence the decomposition of Col(A) in the CCF

of A is a reﬁnement of the one in the DM-decomposition.

Proof. First note that p(J) ≤ p

(J)forJ ⊆ C. By Theorem 4.2.5, A is

nonsingular if and only if min p = 0. This implies min p

= 0. The inclusion

min

(p) ⊇L

min

) is then evident.

Example 4.4.6. For a singular matrix the CCF is not necessarily a reﬁne-

ment of the DM-decomposition. Consider, e.g., a matrix A ∈ LM(Q, F ;4, 0, 4)

(for any F ⊇ Q) and its CCF

A =

1111

0011

A =

1111

0011

The CCF consists of tails only with C

= Col(A), |R

| =2,C

∞

= ∅ and

∞

| = 2. On the other hand, the DM-decomposition evidently decomposes

A into two square blocks. 2

4.4 Combinatorial Canonical Form of LM-matrices 175

4.4.3 Construction of CCF

This subsection gives a constructive proof of Theorem 4.4.4. The following

mathematical construction of the CCF will be polished up to a practically

eﬃcient algorithm in §4.4.4.

As already mentioned, we consider the submodular function p, the sub-

lattice L

min

(p) of its minimizers, and the associated partition

P(L

min

(p)) = ({C

; C

, ···,C

; C

∞

}, )

of C = Col(A) = Col(Q) = Col(T ) (see (4.16), (4.40), (4.41) for the deﬁ-

nitions of p, L

min

(p), and P(L

min

(p))). In accordance with (2.23) we deﬁne



l=0

for k =0, 1, ···,b to obtain

(= min L

min

(p))

⊂

=

⊂

=

⊂

=

···

⊂

=

(= max L

min

(p)), (4.47)

which is a maximal chain of L

min

(p) by (4.42).

Note that the LM-admissible transformation (4.35) is equivalent to







, (4.48)

which contains another permutation matrix P

. In what follows we will ﬁnd

these four matrices P

,S,P

that bring about the CCF.

[Matrix P

]: The permutation matrix P

is such that the column set C is

reordered as C

, ···,C

∞

, where the ordering of columns within each

block is arbitrary.

[Matrix S]: Recall the notation ρ(J)=rankQ[R

,J], J ⊆ C, and note

that Col(QP

) can be identiﬁed with C through permutation P

.Bythe

usual row elimination operations, we can bring QP

into a block-triangular

matrix (in the sense of §2.1.4) with column partition (C

; C

, ···,C

; C

∞

More precisely, we can ﬁnd a nonsingular matrix S ∈ GL(m

, K) and a

partition

; R

, ···,R

; R

Q∞

) (4.49)

of Row(SQP

) such that

Q = SQP

satisﬁes

Q[R

]=O (0 ≤ l<k≤∞) (4.50)

and

rank

Q[R

]=|R

| = ρ(X

rank

Q[R

]=|R

| = ρ(X

) − ρ(X

k−1

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

Q∞

| = m

− ρ(X

176 4. Theory and Application of Mixed Matrices

We may further impose that

For 0 ≤ k<l≤∞, the nonzero row vectors of

Q[R

]are

linearly independent of the row vectors of

Q[R

]. (4.52)

[Matrix P

]: Deﬁne a partition of R

=Row(T ):

T 0

; R

T 1

, ···,R

; R

T ∞

) (4.53)

T 0

= Γ (X

) \ Γ (X

k−1

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

T ∞

= R

\ Γ (X

)

using the notation Γ (J)={i ∈ R

|∃j ∈ J : T

=0} of (4.8). Let P

a permutation matrix which permutes R

compatibly with (4.53), so that

T = P

is in an explicit block-triangular form:

T [R

]=O (0 ≤ l<k≤∞), (4.55)

where it is understood that Row(

T )=Row(T ) and Col(

T ) = Col(T )=C

through the permutations P

and P

. Note that

T 0

| = γ(X

) − γ(X

k−1

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

T ∞

| = m

− γ(X

)

with γ(J)=|Γ (J)|.

[Matrix P

]: We have constructed two block-triangular matrices

Q and

T , the former being block-triangularized with respect to the partitions (4.41)

and (4.49) and the latter with respect to (4.41) and (4.53). Put these two

matrices together:

A =





and deﬁne a partition of Row(

A):

; R

, ···,R

; R

∞

) (4.57)

by R

= R

∪ R

for k =0, 1, ···,b,∞. By (4.50) and (4.55),

A is (essen-

tially) block-triangularized with respect to the partitions (4.41) and (4.57),

namely,

A[R

]=O (0 ≤ l<k≤∞).

To obtain an explicit block-triangular form, we use a matrix P

that reorders

Row(

A) compatibly with (4.57), and redeﬁne

A to be P

4.4 Combinatorial Canonical Form of LM-matrices 177

The matrix

A constructed above is LM-equivalent to A. Obviously, it is

block-triangularized, satisfying (4.43) in (B1). We go on to prove (B2), (B3),

(B4), and (B5), while deferring the proof of the claims (4.44) and (4.45)

concerning partial order.

[Proof of (B2)]: Since C

∈L

min

(p), ρ(C

)=|R

|,andγ(C

)=|R

T 0

we have

0=p(∅) ≥ min p = p(C

)=ρ(C

)+γ(C

) −|C

| = |R

|−|C

Hence |R

|≤|C

|. If the equality holds here, then p(∅) = min p, i.e., ∅∈

min

(p). Since C

= min L

min

(p), this implies C

= ∅ and therefore R

= ∅.

For k =1, ···,b,wehavep(X

k−1

)=p(X

) (= min p), i.e.,

ρ(X

k−1

)+γ(X

k−1

) −|X

k−1

| = ρ(X

)+γ(X

) −|X

This reduces to |R

| = |C

| by (4.51) and (4.56).

If C

∞

= ∅, then p(C) > min p = p(X

), i.e.,

ρ(C)+γ(C) −|C| >ρ(X

)+γ(X

) −|X

Combination of this with

|R|≥ρ(C)+γ(C), |R

∞

| = |R|−ρ(X

) − γ(X

), |C

∞

| = |C|−|X

yields |R

∞

| > |C

∞

[Proof of (B3)]: Put Y



l=0

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

min p = p(X

)=ρ(X

)+γ(X

) −|X

| = |Y

|−|X

| (k =0, 1, ···,b).

(4.58)

For k =0, 1, ···,b, it follows from (4.43), Theorem 4.2.5, and (4.58) that

rank

A[Y

]=rank

A[Row(

A),X

]=rankA[R, X

]

= min{p(X) | X ⊆ X

} + |X

| = |Y

which implies

rank

A[R

]=|R

| (k =0, 1, ···,b).

Since

A[R

∞

]=O and rank

A[Y

]=|Y

|,wehave

rank

A[R

∞

]=rank

A −|Y

| = min p + |C|−|Y

| = |C|−|X

| = |C

∞

[Proof of (B4)]: By (4.43) and Theorem 4.2.5,

rank

A[R

\{j}] = min{p(X) | X ⊆ C

\{j}}+ |C

|−1

≥ min p + |C

| = |R

178 4. Theory and Application of Mixed Matrices

For k =1, ···,b, put C



= X

\{j}. Similarly we have

rank

A[R

\{i},C

\{j}]=rank

A[R \{i},C



] −|Y

k−1

= min{p



(X) | X ⊆ C



} + |C



|−|Y

k−1

|, (4.59)

where p



→ Z, the LM-surplus function associated with

A[R \{i},C



is given by



(X)=rank

Q[Row(

Q) \{i},X]+|Γ (X) \{i}| − |X|,X⊆ C



We see p(X) − 1 ≤ p



(X) ≤ p(X)forX ⊆ C



,andp



(X)=p(X)for

X ⊆ X

k−1

. We further claim that min p



= min p, since otherwise there

exists X ⊆ C



with X ∈L

min

(p)andX ⊆ X

k−1

, which, combined with

k−1

∈L

min

(p), implies (cf. Theorem 2.2.5) that X ∪ X

k−1

∈L

min

(p)and

k−1

⊂

=

X ∪ X

k−1

⊂

=

, a contradiction to our assumption that (4.47) is a

maximal chain. Hence (4.59) is equal to min p+|C



|−|Y

k−1

| = |C



|−|X

k−1

| =

|−1. The ﬁnal case, rank

A[R

∞

\{i},C

∞

], can be treated mutatis mutandis

(by replacing C



with C, the index k with ∞,andk − 1 with b).

[Proof of (B5)]: Since

A is a block-triangular matrix with the rank

conditions in (B3), it holds that

rank

A = |C|−|

| + |

| (k =0, 1, ···,q),

where



l=0



l=0

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

On the other hand, since

A and A are LM-equivalent, they share the same

LM-surplus function p (i.e., the same ρ and γ). By virtue of this invariance

of p as well as Theorem 4.2.5, the rank of

A canbeexpressedas

rank

A = min p + |C|

in terms of the original LM-surplus function p. Hence follows

min p = |

|−|

| = ρ(

)+γ(

) −|

| = p(

where the second equality is due to the assumed rank condition of

A. That

is,

∈L

min

(p)fork =0, 1, ···,q. This implies the claim of (B5).

[Proof of (4.44)]: First we note that L

min

(p) is both ρ-andγ-skeleton,

since ρ and γ are submodular while p = ρ + γ −|·|is modular on L

min

(p)

(see §2.2.2 for the deﬁnition of skeleton). It then follows from Theorem 2.2.13

that

| = ρ(C

∪C

) − ρ(C

)(k =0, 1, ···,b), (4.60)

| = γ(C

∪C

) − γ(C

)(k =0, 1, ···,b), (4.61)

4.4 Combinatorial Canonical Form of LM-matrices 179

where

C

 =



| C

≺ C

} =



| C

 C

= C

}

for k =0, 1, ···,b,∞. It is emphasized that C

⊆C

 for k =1, ···,b,∞

according to the convention of (2.26), whereas C

 = ∅.

Lemma 4.4.7. For 1 ≤ k,l ≤ b, it holds that

Q[R

] = O ⇒ C

 C

Proof.PutR

 =



| C

≺ C

} for l =0, 1, ···,b. It suﬃces to show

Q[Row(

Q) \ (R

∪R

),C

]=O (4.62)

for l =0, 1, ···,b. We prove (4.62) by induction on l. First, (4.62) for l =0

holds true by (4.50). Next we consider a general l ≥ 1. If C

⊆C

, then

j<lby (4.42) and therefore, by the induction hypothesis,

Q[Row(

Q) \ (R

∪R

),C

]=O.

Since R

∪R

⊆R

, this yields

Q[Row(

Q) \R

,C

]=O

for all j with C

⊆C

. Therefore,

Q[Row(

Q) \R

, C

]=O. (4.63)

From this and (4.51) follows

|R

| =rank

Q[R

, C

]=rank

Q[Row(

Q), C

]=ρ(C

).

Hence, by (4.63) and (4.60),

rank

Q[Row(

Q) \R

,C

]=rank

Q[Row(

Q), C

∪C

] −|R

|

= ρ(C

∪C

) − ρ(C

)=|R

This means (4.62) by the condition (4.52).

Lemma 4.4.8. R

= Γ (C

) \ Γ (C

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

Proof. Since R

= Γ (X

k−1

∪C

) \Γ (X

k−1

)=Γ (C

) \Γ (X

k−1

) (cf. (4.54))

and Γ (C

∪C

) \ Γ (C

)=Γ (C

) \ Γ (C

), it follows from (4.61) that

| = |Γ (C

) \ Γ (X

k−1

)| = |Γ (C

) \ Γ (C

)|,

in which Γ (X

k−1

) ⊇ Γ (C

). Therefore, R

= Γ (C

) \ Γ (C

).

Lemma 4.4.9. For 1 ≤ k,l ≤ b, it holds that

T [R

] = O ⇒ C

 C

180 4. Theory and Application of Mixed Matrices

Proof. Suppose that

T [R

] = O, where we may assume 1 ≤ k<l≤ b.

Then, ∃ i ∈ R

, ∃ j ∈ C

: T

= 0. This implies i ∈ R

and i ∈ Γ (C

With the expression R

= Γ (C

) \ Γ (C

) (cf. Lemma 4.4.8) we see that

i ∈ Γ (C

), i.e.,

∃ l

: k ≤ l

≺ C

T [R

] = O,

where l

= l. Repeating this, we see that ∃ l

, ∃ l

, ···, ∃ l

: C

= C

≺

s−1

≺···≺C

≺ C

= C

The claim (4.44) is established by Lemmas 4.4.7 and 4.4.9, since

A[R

]

= O if and only if

Q[R

] = O or

T [R

] = O.

[Proof of (4.45)]: Suppose that C

≺· C

. We may assume 1 ≤ k<l≤ b

by (4.42). Put

I = {i | k<i<l,C

≺ C

},I

∗

= I ∪{k},

J = {j | k<j<l}\I, J

∗

= J ∪{l}.

We have (i) i ∈ I

∗

,j ∈ J ⇒ C

 C

, and (ii) i ∈ I ⇒ C

 C

.The

statement (i) is due to the transitivity of the partial order and the statement

(ii) is by the assumption C

≺· C

. It then follows that

i ∈ I

∗

,j ∈ J

∗

, (i, j) =(k, l) ⇒ C

 C

⇒

A[R

]=O,

where (4.44) is used.

A[R

]=O were the case, we would have



i∈I

∗



j∈J

∗

]=O.

Then ρ(X)+γ(X)=|Y

k−1

| +



j∈J

∗

| for X = X

k−1

∪





j∈J

∗



and

k−1



k−1

l=0

, and therefore X belongs to L

min

(p), since

p(X)=(ρ(X)+γ(X)) −|X|

⎛

⎝

k−1

| +



j∈J

∗

⎞

⎠

−

⎛

⎝

k−1

| +



j∈J

∗

⎞

⎠

= |Y

k−1

|−|X

k−1

| = min p,

where (B2) and (4.58) are used. Hence we have X ∈L

min

(p), C

⊆ X,and

⊆ X. This contradicts the deﬁnition (2.24) of C

 C

. Hence we must

have

A[R

] = O, completing the proof of (4.45).

The proof of Theorem 4.4.4 is completed.

Remark 4.4.10. The construction of the CCF is a natural generalization of

that of the DM-decomposition. Note in particular that both rely on the same

decomposition principle, the Jordan–H¨older-type theorem for submodular

functions, which is applied to the surplus functions, p

and p, respectively.

The admissible transformations are not explicit in this. The properties of

the resulting decompositions are established in relation to the admissible

transformations by virtue of the rank formulas expressed in terms of the

surplus functions. The corresponding items are compared in Table 4.1. 2