Murota K. Matrices and Matroids for Systems Analysis

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

4.7 Related Decompositions 221

On the other hand, the deﬁnition of I implies

˜γ(X)=|I ∪

Γ (R, J)| = |I|. (4.102)

Combining (4.101) and (4.102), we obtain

˜p(X)=˜ρ(X)+˜γ(X) −|X|≤|W |−|J|,

which shows X ∈L

min

(˜p) by (4.98). Hence

A is the ﬁnest proper block-

triangular form under the admissible transformation (4.88).

Notes. Section 4.6.1 is based on Murota [198]. Theorem 4.6.8 was ﬁrst stated

in §24 of Murota [204], whereas the proof is improved here.

4.7 Related Decompositions

In the literature of electrical network theory, it has been known that a system

of equations describing an electrical network can be put in a block-triangular

form if one chooses appropriate bases (tree-cotree pairs) for Kirchhoﬀ’s laws

and rearranges the variables and the equations (for both Kirchhoﬀ’s laws and

element characteristics). A decomposition method, called 2-graph method,re-

ferring to a pair of current-graph and voltage-graph is investigated in Ozawa

[260, 261, 262] for networks involving controlled sources. Based on the re-

sult of Tomizawa–Iri [317], a decomposition of networks with admittance

expressions is considered by Iri [127] in relation to the independent-matching

problem. An attempt has been made in Nakamura–Iri [246] and Nakamura

[243, 244] to deﬁne a block-triangularization for a system of equations de-

scribing the most general class of networks with arbitrary mutual couplings

(such as those containing controlled sources, nullators, and norators) as an

application of the principal partition for a pair of matroids. This section is

devoted to clarifying the relationship of the CCF-based decomposition to

some of those decomposition techniques and to extending the concept of LM-

equivalence to multilayered matrices.

4.7.1 Decomposition as Matroid Union

For an LM-matrix A =

∈ LM(K, F ) the CCF of A has been constructed

on the basis of the LM-surplus function p which is submodular and charac-

terizes the rank of A (cf. Theorem 4.2.5). In Theorem 4.2.3, on the other

hand, we have encountered another submodular function that characterizes

the rank of A, namely, p

→ Z deﬁned by

(J)=ρ(J)+τ(J) −|J|,J⊆ C, (4.103)

which is only slightly diﬀerent from the LM-surplus function

222 4. Theory and Application of Mixed Matrices

p(J)=ρ(J)+γ(J) −|J|,J⊆ C.

It is quite natural to be tempted to apply to p

the Jordan–H¨older-type

theorem for submodular functions with a vague hope that some meaningful

decomposition of an LM-matrix might be obtained. Indeed it was claimed in

Nakamura–Iri [246] and Nakamura [243, 244] (before the CCF is established)

that this approach yielded a block-triangularization of a system of equations

(3.2) for an electrical network. It is certainly true that, for an LM-matrix in

general, the Jordan–H¨older-type theorem applied to p

yields a partition of

the column set (currents and voltages of branches in the case of electrical

networks) into partially ordered blocks. Let us call this decomposition the

principal partition with respect to the matroid union M(Q) ∨M(T ), as ρ and

τ are the rank functions of M(Q)andM(T ), respectively.

The objective of this subsection is to compare the CCF and the principal

partition with respect to M(Q) ∨M(T ) and to discuss the irrelevance of the

latter by identifying the corresponding admissible transformation, which is

diﬀerent from the LM-admissible transformation (4.35) for LM-equivalence.

Remember that partition of C in the CCF corresponds to L

min

(p) (the family

of the minimizers of p), while that in the principal partition with respect to

M(Q) ∨ M(T ) is given by L

min

Let us begin with two simple examples which demonstrate that the prin-

cipal partition with respect to M(Q) ∨ M(T ) provides a ﬁner partition of C

than the CCF does, and that it is too ﬁne for a useful block-triangularization.

Example 4.7.1. Consider an LM-matrix

A =





−t

It is easy to verify that

min

)={∅, {η

}, {η

,η

}, {ξ

,η

}, {ξ

,η

}, {ξ

,ξ

,η

}}

and therefore the principal partition with respect to M(Q) ∨M(T ) based on

yields a partition of C = {ξ

,ξ

,η

} into four singletons with partial

order given by {η

}≺{ξ

} (i, j =1, 2). However, it is clear by inspection

that {η

,η

} cannot be split in solving the system of equations. On the other

hand, the CCF is based on

min

(p)={∅, {η

,η

}, {ξ

,η

}, {ξ

,η

}, {ξ

,ξ

,η

}}

and gives a more natural partition C = {ξ

}∪{ξ

}∪{η

,η

} with partial

order {η

,η

}≺{ξ

} (i =1, 2).

4.7 Related Decompositions 223

It is mentioned that the above matrix A (with t

= t

= 1) appears as the

coeﬃcient matrix of a system of equations (3.2) that describes a free electrical

network consisting of two branches connected in series with complete mutual

couplings given in terms of admittances. As the notation shows, ξ

and η

are

the current in and the voltage across branch i (i =1, 2). 2

Example 4.7.2. Consider an electrical network consisting of two branches

connected in parallel, where branch 1 is a current source controlled by the

voltage across branch 2, i.e., ξ

= gη

, and the branch 2 is an ohmic resistor,

i.e., η

= rξ

. These equations, together with Kirchhoﬀ’s laws η

− η

and ξ

+ ξ

= 0, are put into the form (3.2) with

A =





1 −1

−1 g

r −1

where ξ

and η

are, as usual, the current in and the voltage across branch

i (i =1, 2). We have

min

)={∅, {η

}, {η

,η

}, {ξ

,ξ

,η

}},

min

(p)={∅, {η

}, {ξ

,ξ

,η

}}.

The former yields the partition {η

}∪{η

}∪{ξ

,ξ

} with partial order {η

}≺

{η

}≺{ξ

,ξ

}, whereas the latter gives {η

}∪{η

,ξ

} with partial order

{η

}≺{η

,ξ

}. It is obvious from the CCF of A:

1 −1

g −1

−1 r

that the variables {ξ

,ξ

} cannot be determined independently of η

. 2

The following proposition gives a precise comparison of the two decom-

positions.

Proposition 4.7.3. For an LM-matrix A ∈ LM(K, F ), the following hold.

(1) p

(J) ≤ p(J) for J ⊆ C.

(2) min p

= min p.

(3) L

min

) ⊇L

min

(p).

(4) min L

min

) = min L

min

(p).

Proof. (1) This is obvious from (4.10).

(2) This has been shown in the proof of Theorem 4.2.5.

224 4. Theory and Application of Mixed Matrices

(3) Immediate from (1) and (2) above.

(4) For J = min L

min

)letJ



(⊆ J) be a minimizer in (4.10), i.e., such

that τ(J)=γ(J



) −|J



| + |J|. From (2), we have

min p = min p

= ρ(J)+γ(J



) −|J



|≥ρ(J



)+γ(J



) −|J



| = p(J



i.e., J



∈L

min

(p). This implies J



= J = min L

min

(p) by (3).

In view of the correspondence between the distributive sublattices and

the partition into partially ordered blocks (§2.2.2), the inclusion L

min

) ⊇

min

(p) shows that the hierarchical decomposition of the column set C by the

principal partition with respect to M(Q)∨M(T ) is ﬁner than that of the CCF.

In other words, the column set of each block of the CCF is an aggregation of

some blocks of the principal partition with respect to M(Q) ∨ M(T ).

In Theorem 4.4.4 we have seen that the decomposition of C based on p

provides the ﬁnest block-triangular form under the equivalence transforma-

tion of the form (4.35). By a similar argument it can be shown on the basis of

Theorem 4.2.3 that the principal partition of C with respect to M(Q)∨M(T )

corresponds to a block-triangularization under a wider class of transforma-

tions of the following form:



0 S





, (4.104)

where S

∈ GL(m

, K), S

∈ GL(m

, F ), and P

and P

are permutation

matrices of orders m (= m

+ m

)andn, respectively. That is, we have the

following.

Theorem 4.7.4. For A ∈ LM(K, F ; m

,n), the partition of Col(A) by

the principal partition with respect to M(Q) ∨ M(T ) yields the ﬁnest proper

block-triangularization (“proper” in the sense of §2.1.4) under the transfor-

mation (4.104). 2

The transformation (4.104), however, does not seem natural and would be

diﬀerent from what is intended in considering a hierarchical decomposition of

a system into subsystems. Recall, for instance, the matrix A of Example 4.7.1.

Since its column set is decomposed into singletons by L

min

), it can be

put in a triangular form by the transformation of the form (4.104) with

=(y

)

−1

, which can be determined only after the parameter values y

are ﬁxed. This simple example demonstrates that the transformation (4.35)

for LM-equivalence is more suitable in practical situations than (4.104), and

hence p is more appropriate than p

. Note also that the transformed matrix

in (4.104) no longer belongs to LM(K, F ; m

,n). We shall come back

to this issue in §4.7.2.

4.7 Related Decompositions 225

4.7.2 Multilayered Matrix

In §4.7.1 (Theorem 4.7.4 in particular) we have seen that, for an LM-matrix

A =

∈ LM(K, F ), the principal partition with respect to M(Q) ∨M(T )

yields the ﬁnest proper block-triangularization under a transformation of the

form



0 S





(4.105)

with S

∈ GL(m

, K)andS

∈ GL(m

, F ). It has been mentioned at

the same time that the transformed matrix no longer belongs to the class of

LM-matrices. This suggests that the block-triangularization under a transfor-

mation of the form (4.105) should be considered in a wider class of matrices.

Let F

be an intermediate ﬁeld of K ⊆ F , i.e., K ⊆ F

⊆ F ,and

consider an (m

+ m

) ×n matrix A over F of the form A =

such that

(i) Q is an m

× n matrix over K,

(ii) T = Q

is an m

× n matrix over F , where Q

is an m

× n

matrix over F

,andT

is a diagonal matrix of order n with its

diagonal entries being algebraically independent numbers in F

over F

The set of such matrices A will be denoted by LC(K, F

, F ; m

,n).

This class of matrices is closed under the transformation (4.105) with S

∈

GL(m

, F

). Moreover, Theorem 4.2.3 and Theorem 4.7.4 can be extended

to this class.

Theorem 4.7.5. For A =

∈ LC(K, F

, F ; m

,n) it holds that

M(A)=M(Q) ∨ M(T ) and that

rank A = min{ρ

(J)+ρ

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

where ρ

(J)=rankQ[Row(Q),J] and ρ

(J)=rankT [Row(T ),J] for J ⊆

C = Col(A). The partition of C by the principal partition with respect to

M(Q) ∨ M(T ) yields the ﬁnest proper block-triangularization (“proper” in

the sense of §2.1.4) under the transformation (4.105) with S

∈ GL(m

, K)

and S

∈ GL(m

, F

Proof. Lemma 4.2.1 and Theorem 4.2.2 are still valid for A ∈ LC(K, F

, F ).

Then the subsequent arguments carry over to this case.

The considerations above naturally suggest an extension to a multilayered

matrix, which, by deﬁnition, is a matrix of the form

A =

⎡

⎢

⎣

⎤

⎥

⎦

(4.106)

226 4. Theory and Application of Mixed Matrices

such that A

is an m

× n matrix over K,andA

= Q

is an m

× n

matrix over F

, where K ⊆ F

⊆ F

⊆ ··· ⊆ F

is a sequence of ﬁeld

extensions, Q

is an m

×n matrix over F

α−1

,andT

is a diagonal matrix

of order n with its diagonal entries being algebraically independent numbers

in F

over F

α−1

(α =1, ···,μ). Putting C = Col(A) we deﬁne ˜p :2

→ Z

˜p(J)=ρ

(J)+ρ

(J)+···+ ρ

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

where ρ

(J)=rankA

[Row(A

),J], J ⊆ C,forα =0, 1, ···,μ.

Theorem 4.7.6. For a multilayered matrix A of (4.106) it holds that

rank A = min{˜p(J) | J ⊆ C} + |C|. (4.108)

Furthermore, the family L

min

(˜p) of the minimizers of ˜p yields the ﬁnest proper

block-triangularization (“proper” in the sense of §2.1.4) under the transfor-

mation

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

⎤

⎥

⎦

, (4.109)

where S

∈ GL(m

, K); S

∈ GL(m

, F

α−1

)(α =1, ···,μ);andP

and P

are permutation matrices. 2

Remark 4.7.7. An LM-matrix A =

∈ LM(K, F ; m

,n)canbe

regarded as a multilayered matrix (4.106) in a number of diﬀerent ways.

A canonical way is to take A

= Q and A

to be the αth row of T for

α =1, ···,m

(with μ = m

). Then the function ˜p of (4.107) agrees with

the LM-surplus function, and the transformation (4.109) is equivalent to the

LM-admissible transformation (4.35) for LM-matrices, so far as the block-

triangular decomposition is concerned. 2

Remark 4.7.8. The canonical form of multilayered matrices introduced

above seems to have a natural meaning for electrical networks involving

multiports (see Recski [277, §8.1] for an exposition on multiports from the

viewpoint of matroid theory). To be speciﬁc, consider an electrical network

consisting of μ multiports, each of which is described by a set of equations

with coeﬃcient matrix A

(α =1, ···,μ). Let A

denote the matrix (over

Q) for Kirchhoﬀ’s laws. Then the coeﬃcient matrix for the whole system

is written as (4.106), and the admissible transformation (4.109) reﬂects the

locality in the sense that we can choose an appropriate description for each

device. Furthermore, the assumption of the algebraic independence among

diﬀerent devices would be fairly realistic. 2

As an application of Theorem 4.7.5 we derive here the maximum-rank

minimum-term rank theorem for the pivotal transforms of a matrix, due to

Iri [122, 124]. For an m × n matrix N over K,apivotal transform means

4.7 Related Decompositions 227

N =





→ N





−1

−N

−1

− N

−1



for a nonsingular submatrix N

. This transformation is invertible, and hence

deﬁnes an equivalence relation ∼

among matrices (of the same size).

Theorem 4.7.9 (Maximum-rank minimum-term rank theorem).

For an m × n matrix N over K it holds that

max



∼

rank N



= min



∼

term-rank N



Moreover, there exists an m × n matrix N

◦

over K such that N

◦

∼

N and

rank N

◦

= term-rank N

◦

. (4.110)

Proof.PutQ =[I

N]andT =[I

N] D, where D = diag (t

, ···,t

m+n

)

with t

(i =1, ···,m+ n) being indeterminates over K, and consider A =

∈ LC(K, K, F ; m, m, m + n) where F = K(t

, ···,t

m+n

). The column

set C of A is given by C = Col(Q)  Row(N) ∪ Col(N ). By Theorem 4.7.5

there exists B ⊆ C such that rank Q[Row(Q),B]=|B| = m and rank A =

m +rankT [Row(T ),C \ B]. Put S = Q[Row(Q),B]

−1

Q = SQ,and

T =

ST, to obtain

A =

. This is the canonical block-triangular form of A

(cf. (4.64)). Since

A (with columns permuted) is of the form

A =



BC\ B

◦

· D

◦

· D

C\B



where N

◦

Q[Row(

Q),C\ B], D

= diag (t

| i ∈ B), D

C\B

= diag (t

| i ∈

C \ B), it can be seen that

term-rank

A = term-rank



◦



= m + term-rank N

◦

On the other hand, rank

A =rankA = m +rankT [Row(T ),C \ B]=m +

rank

T [Row(

T ),C \ B]=m +rankN

◦

by the choice of B. Finally, we have

rank

A = term-rank

A, since

A is in a proper block-triangular form. Hence

follows (4.110). Note that N

◦

is a pivotal transform of N with respect to

N[Row(N ) \ B,Col(N) ∩ B].

Remark 4.7.10. The matrix N

◦

constructed in the proof of Theorem 4.7.9

coincides with the combinatorial canonical form of N with respect to its piv-

otal transforms introduced by Iri [125]. Note that N

◦

can be put into a proper

block-triangular form by (4.110) and Proposition 2.1.17. See Iri [125] for its

relationship to the principal partition of graphs and to the topological de-

grees of freedom of electrical networks considered by Iri [122], Kishi–Kajitani

[157, 158, 159], Ohtsuki–Ishizaki–Watanabe [254]. Also see Maurer [189] for

a matroid theoretic generalization of Theorem 4.7.9. 2

228 4. Theory and Application of Mixed Matrices

4.7.3 Electrical Network with Admittance Expression

A decomposition method has been proposed by Iri [127] for electrical networks

with admittance expressions (see Iri [128] for an explicit illustration). We

discuss here its relationship to the CCF.

When the branch characteristics of an electrical network are given in terms

of self- and mutual admittances Y , the coeﬃcient matrix A of the system (3.2)

of equations in (ξ, η) takes the form:

A =

−IY

, (4.111)

where D is a fundamental cutset matrix and R is a fundamental circuit matrix

of the underlying graph. The column set C = Col(A) is the disjoint union of

two copies, say B

and B

, of the set B of branches; i.e., C = B

∪B

. Note

that Row(Y ) is identiﬁed with B

and Col(Y ) with B

. It is mentioned that

the above system of equations represents the “free” network that is obtained

after the branches of voltage sources are contracted and those of current

sources are deleted (see Recski [277] for more about this).

The unique solvability of the network is equivalent to the nonsingularity

of DY D

by the following lemma.

Lemma 4.7.11. Suppose D and R in (4.111) areoffull-rowrankand

ker D =(kerR)

⊥

.Thendet A = c · det(DY D

) for some c =0.

Proof. By the assumption there exist a matrix N, nonsingular matrices S

and S

, and permutation matrix P such that D = S

[I | N]P and R =

[−N

| I]P. We assume P = I for notational simplicity, and partition Y

as Y =(Y

| i, j =1, 2) accordingly. We observe

⎡

⎣

IOD

OIO

OO I

⎤

⎦

⎡

⎣

−IY

⎤

⎦

⎡

⎣

ODY

−IY

⎤

⎦



−1







−1

(DY D

−T

+ NY



−N



to prove the claim with c = ±(det S

/ det S

) =0.

The decomposition proposed by Iri [127, 128] may be described as follows.

Under the assumption that the nonvanishing entries of Y are algebraically

independent over Q, the nonsingularity of DY D

canbeexpressedinterms

of an independent matching problem, as has been explained in Remark 2.3.37.

Namely, we consider an independent matching problem on the bipartite graph

G =(V

−

;

A) with vertex sets V

=Row(Y )(=B

), V

−

= Col(Y )(=

4.7 Related Decompositions 229

), and arc set

A = {(i, j) | Y

=0}. The matroids M

and M

−

attached to

and V

−

are both isomorphic to the linear matroid M(D)=(B,μ) deﬁned

by the matrix D. It should be clear that μ(I)=rankD[Row(D),I](I ⊆ B),

which is equal to the rank of I (= maximum size of a circuit-free subset of I)

in the underlying graph. Then rank (DY D

) is equal to the maximum size

of an independent matching (cf. (2.78)). Though not explicit in Iri [127, 128],

Iri’s decomposition can be identiﬁed as the min-cut decomposition (§2.3.5)

for this independent matching problem.

To be speciﬁc, deﬁne

(J)={i ∈ B

|∃j ∈ J : Y

=0},J⊆ B

H = {(I,J) ∈ 2

× 2

| I ⊇ Γ

(J)},

(I,J)=



μ(I)+μ(B

\ J) − μ(B)((I,J) ∈H)

+∞ ((I,J) ∈H),

min

)={I ∪ J ⊆ B

∪ B

| p

(I,J) = min p

Then (I,J) ∈Hif and only if (I,B

\ J) is a cover in the independent

matching problem, and the cut capacity function κ : B

∪B

→ Z, as deﬁned

in (2.71), is given by

κ(I ∪ J)=p

\ I,B

\ J)+μ(B).

The min-cut decomposition is induced from the lattice L

min

(κ) of the mini-

mizers of κ. However, it is more convenient here to consider L

min

) in place

of L

min

(κ); obviously, I ∪J ∈L

min

(κ) ⇐⇒ (B

\ I) ∪ (B

\ J) ∈L

min

The decomposition of C = B

∪ B

proposed by Iri [127] is the one induced

from L

min

) according to the general principle of §2.2.2.

On the other hand, we may regard A as a member of LM(Q, R) with

A =





,Q=





,T=



−IY



where a trivial scaling of the constitutive equations (matrix T ) using tran-

scendental numbers is assumed to bring A into the class of LM(Q, R) (as in

Example 4.3.9). We shall show that the decomposition through the CCF of

A agrees essentially with Iri’s decomposition.

The LM-surplus function p associated with A is given by

p(I ∪ J)=μ(I)+ν(J)+|I ∪ Γ

(J)|−|I ∪ J|,I⊆ B

,J ⊆ B

where ν(J)=rankR[Row(R),J](J ⊆ B

), which is equal to the nullity of J

(= maximum size of a cutset-free subset of J) in the underlying graph. Since

ν(J)=μ(B

\ J)+|J|−μ(B),J⊆ B

we have

p(I ∪ J)=p

(I,J), (I,J) ∈H. (4.112)

230 4. Theory and Application of Mixed Matrices

Proposition 4.7.12.

(1) min{p(I ∪ J) | I ⊆ B

,J ⊆ B

} = min{p

(I,J) | I ⊆ B

,J ⊆ B

(2) L

min

(p) ⊇L

min

(3) {J ⊆ B

|∃I ⊆ B

: I ∪ J ∈L

min

(p)} = {J ⊆ B

|∃I ⊆ B

I ∪ J ∈L

min

)}.

Proof. (1) We have

min p = min{min{μ(I)+|Γ

(J) \ I||I ⊆ B

} + ν(J) −|J||J ⊆ B

}

= min{μ(Γ

(J)) + ν(J) −|J||J ⊆ B

which shows that the minimum of p is attained by an (I,J)inH.

(2) This is immediate from (4.112) and (1) above.

(3) Both sides of (3) agrees with the minimizers J (⊆ B

)ofμ(Γ

(J)) +

ν(J) −|J|.

Proposition 4.7.12(2) shows that the decomposition by the CCF applied to

(4.111) yields a ﬁner partition of the variables {ξ, η}. However, the diﬀerence

is not substantial, since, as indicated by Proposition 4.7.12(3), they provide

an identical partition for the voltage variables η which play the primary

role in (4.111); the current variables ξ are only secondary as they are readily

obtained from η as ξ = Y η. In this way, we may say that they give essentially

the same decomposition. However, the inclusion in Proposition 4.7.12(2) is

proper in general, as is exempliﬁed below.

Example 4.7.13. For a matrix

A =

−1 y

the CCF based on L

min

(p) decomposes {ξ

,ξ

,η

} into four singletons

with partial order: {η

}≺{η

}≺{ξ

}, {η

}≺{ξ

}. The decomposition by

min

), on the other hand, gives a partition into two blocks with {ξ

,η

}≺

{ξ

,η

}. 2

4.8 Partitioned Matrix

“Partitioned matrix,” investigated in Ito–Iwata–Murota [138], oﬀers a gen-

eral framework in which we can gain a deeper understanding of proper

block-triangularizations of matrices with respect to existence, uniqueness,

and algorithmic construction. Some of the nice properties enjoyed by the

DM-decomposition of generic matrices and the CCF of LM-matrices carry

over to this general setting, whereas the construction by combinatorial algo-

rithms does not.