Murota K. Matrices and Matroids for Systems Analysis

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

4.8 Partitioned Matrix 231

4.8.1 Deﬁnitions

We consider an m × n matrix over a ﬁeld F whose row set and column set

are independently divided into groups:

A =

⎡

⎢

⎣

···A

1ν

···A

2ν

μ1

μ2

···A

μν

⎤

⎥

⎦

, (4.113)

which we call a partitioned matrix, where A

αβ

is an m

× n

matrix called

the (α, β)-submatrix of A for α =1, ···,μ and β =1, ···,ν. We are con-

cerned with a proper block-triangularization of A by means of an equivalence

transformation of the form

−1

⎡

⎢

⎣

O ··· O

O ··· OS

rμ

⎤

⎥

⎦

−1

⎡

⎢

⎣

···A

1ν

···A

2ν

μ1

μ2

···A

μν

⎤

⎥

⎦

⎡

⎢

⎣

O ··· O

O ··· OS

cν

⎤

⎥

⎦

(4.114)

with

α=1

rα

⎡

⎢

⎣

O ··· O

O ··· OS

rμ

⎤

⎥

⎦

β=1

cβ

⎡

⎢

⎣

O ··· O

O ··· OS

cν

⎤

⎥

⎦

(4.115)

being nonsingular matrices over F . Such an equivalence transformation, pre-

serving the given partition structure, is called a partition-respecting equiva-

lence transformation (or PE-transformation for short). Then our problem is

to bring a partitioned matrix A into a proper block-triangular form by means

of a PE-transformation.

The block-diagonal structure imposed on the transformation matrices S

and S

can be expressed in terms of two families of projection matrices,

Π = {Π

}

α=1

and Γ = {Γ

}

β=1

. The matrix Π

is an m × m projection

matrix such that the (α, α)-submatrix of Π

is the unit matrix I

of di-

mension m

and the other submatrices are zeroes. Similarly, Γ

is an n × n

projection matrix such that the (β,β)-submatrix of Γ

is the unit matrix I

of dimension n

and all the other submatrices are zeroes. Then a transfor-

mation S

−1

with nonsingular S

and S

is a PE-transformation if and

only if

= S

(α =1, ···,μ),Γ

= S

(β =1, ···,ν). (4.116)

232 4. Theory and Application of Mixed Matrices

Note that this condition is equivalent to the oﬀ-diagonal submatrices of S

and S

being zeroes. Sometimes we denote a partitioned matrix by a triple

(A, Π, Γ ) of matrix A and two families of projection matrices Π = {Π

}

α=1

and Γ = {Γ

}

β=1

The concepts of partitioned matrices and PE-transformations may be

described in terms of linear maps, as follows. Let U

∼

and V

∼

be F -linear spaces which are, respectively, expressed as direct sums of lower

dimensional component spaces:

U =

α=1

, dim

= m

(α =1, ···,μ), (4.117)

V =

β=1

, dim

= n

(β =1, ···,ν). (4.118)

A linear transformation f : V → U is deﬁned by a family of linear transfor-

mations

αβ

: V

→ U

,α=1, ···,μ; β =1, ···,ν.

When a family of bases for {U

}

α=1

and one for {V

}

β=1

are chosen, f is

represented by a partitioned matrix A, where A

αβ

corresponds to f

αβ

. A PE-

transformation corresponds to a change of “local basis families” for {U

}

α=1

and {V

}

β=1

. The block-triangularization of a partitioned matrix by a PE-

transformation amounts to ﬁnding a global hierarchical decomposition by

means of a local basis change.

Example 4.8.1. The block-triangularization of a partitioned matrix by a

PE-transformation is illustrated for a 4 × 5 partitioned matrix over F = Q:

A =

◦ ◦ ◦••



(

⎡

⎢

⎣

111

021

2 −2002

030

⎤

⎥

⎦

where μ =2,ν =2,m

=2,m

=2,n

=3,n

= 2. With the choice of

⎡

⎢

⎣

⎤

⎥

⎦

⎡

⎢

⎣

011

010

100

⎤

⎥

⎦

we have

A = S

−1

◦◦◦ • •



(

⎡

⎢

⎣

120

001

0 −1

03004

002

⎤

⎥

⎦

4.8 Partitioned Matrix 233

Using permutation matrices

⎡

⎢

⎣

1000

0010

0100

0001

⎤

⎥

⎦

⎡

⎢

⎣

10000

00100

00010

01000

00001

⎤

⎥

⎦

we can transform

A into an explicit upper block-triangular form:

A = P

◦•◦◦ •



(



(

⎡

⎢

⎣

1 2 0 1

3 0 4

O 1 −1

2 2

⎤

⎥

⎦

with two square blocks, a nonempty horizontal tail (|R

| =1,|C

| =2)and

an empty vertical tail. Note that this is a proper block-triangular matrix. 2

We now introduce a submodular function p

for a partitioned matrix,

which is a generalization of the (LM-)surplus function for a generic (or LM-)

matrix. We denote by W the family of all the subspaces of V that can be

represented as a direct sum of subspaces of V

’s, i.e.,

W = {W | W : subspace of V, Γ

W ⊆ W (β =1, ···,ν)}. (4.119)

For W

∈Wand W

∈W,wehaveW

+ W

∈Wand W

∩W

∈W,which

means that W forms a lattice. Furthermore, we have

dim W

+dimW

=dim(W

+ W

)+dim(W

∩ W

which means W is a modular lattice (not distributive in general). Regarding

= Π

A as a linear map, we deﬁne p

: W→Z by

(W )=



α=1

dim(A

W ) − dim W, W ∈W. (4.120)

We call p

: W→Z the PE-surplus function associated with a partitioned

matrix A.

Lemma 4.8.2. The PE-surplus function p

: W→Z is submodular, i.e.,

)+p

) ≥ p

+ W

)+p

∩ W

),W

∈W.

Proof. It suﬃces to show that dim(A

W ) is submodular for each α. This

follows from A

+ W

)=A

+ A

and A

∩ W

) ⊆ A

∩

The following proposition shows that the PE-surplus function p

is rel-

evant in dealing with the rank of partitioned matrices.

234 4. Theory and Application of Mixed Matrices

Proposition 4.8.3. For an m × n partitioned matrix A,

rank A ≤ min{p

(W ) | W ∈W}+ n ≤ term-rank A.

Proof. For any W ∈Wthere exists a matrix S

of the form of (4.115) such

that a subfamily of the column vectors of S

is a basis of W .Let

A =

⎛

⎜

⎝

J  WC\ J

,J]

,C \ J]

,J]

,C \ J]

,J]

,C \ J]

⎞

⎟

⎠

(4.121)

be obtained from A by a PE-transformation using such S

, where C = Col(

A),

=Row(

), and the subset of C indicated by “J  W” corresponds to

the subspace W (hence |J| =dimW ). Then, rank

,J]=dim(A

W )

for each α,and

rank A =rank

A ≤



α=1

rank

,J]+rank

A[R, C \ J]

≤



α=1

dim(A

W )+n − dim W = p

(W )+n. (4.122)

This establishes the ﬁrst inequality.

For the second inequality, let p

: Col(A) → Z be the surplus function

(2.39) associated with A, and let J ⊆ Col(A) be a minimizer of p

. Then we

have p

(J)+n = term-rank A by the Hall–Ore theorem (Theorem 2.2.17).

Deﬁne W to be the subspace of V spanned by the unit vectors corresponding

to J. Then W ∈W,dimW = |J| and



α=1

dim(A

W ) ≤ γ

(J) (cf. (4.46)).

Therefore p

(W )+n ≤ p

(J)+n = term-rank A.

It may be said that the relation

rank A ≤ min{p

(W ) | W ∈W}+ n (4.123)

states a weak duality of the same kind as the easier part of min-max relations.

Though the equality is not always guaranteed in (4.123), this weak duality

turns out to be most fundamental in that the strong duality (the equality

in (4.123)) is equivalent to the existence of a proper block-triangularization,

as will be stated in Theorem 4.8.6. Note in this connection that both rank A

and min p

are invariant under PE-transformations, whereas term-rank A is

not.

Example 4.8.4. A simplest partitioned matrix that cannot be brought into

a proper block-triangular form is A =



1 1



with μ = ν =2.Wehave

rank A = 1 while min p

+ 2 = 2 = term-rank A. 2

4.8 Partitioned Matrix 235

Remark 4.8.5. An LM-matrix A =

∈ LM(K, F ; m

,n)canbe

regarded as a partitioned matrix such that the column set is partitioned into

singletons (ν = n, n

=1forβ =1, ···,ν) and the row set is partitioned into

Row(Q) and singletons from Row(T )(μ =1+m

; m

= m

, m

=1for

α =2, ···,μ). Then, W

∼

Col(A)

, and the associated PE-surplus function

agrees with the LM-surplus function p deﬁned in (4.16). 2

4.8.2 Existence of Proper Block-triangularization

In Proposition 4.8.3 we have seen a weak duality between the rank and the

PE-surplus function p

for a partitioned matrix. We shall show that the

strong duality (the validity of the minimax formula) is equivalent to the

existence of a proper block-triangularization. The block-triangularization can

be constructed on the basis of the family of the minimizers of p

min

)={W ∈W|p

(W ) = min



∈W



)}, (4.124)

which forms a modular lattice (cf. Lemma 4.8.2 and Theorem 2.2.5).

Theorem 4.8.6. For an m×n partitioned matrix A, a proper block-triangular

matrix can be obtained by a PE-transformation (4.114) if and only if

rank A = min{p

(W ) | W ∈W}+ n. (4.125)

Proof. [“only if” part] Suppose

A is a proper block-triangular matrix obtained

from A by a PE-transformation. Since rank A and min p

are invariant under

PE-transformations, Proposition 4.8.3 implies

rank A =rank

A ≤ min{p

(W ) | W ∈W}+ n ≤ term-rank

in which rank

A = term-rank

A by Proposition 2.1.17.

[“if” part] Let C be a maximal chain of L

min

C : W

⊂

=

⊂

=

···

⊂

=

Denoting W

∩ V

by W

kβ

, we obtain from C a family of increasing chains

: W

0β

⊆ W

1β

⊆···⊆W

bβ

for β =1, ···,ν.LetΨ

kβ

be a set of linearly independent column vectors

spanning W

kβ

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

∞β

spanning V

such that

0β

⊆ Ψ

1β

⊆···⊆Ψ

bβ

⊆ Ψ

∞β

Then Ψ



β=1

kβ

spans W

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



β=1

∞β

becomes a basis of V . Order the n column vectors of Ψ as [Ψ

∞1

,Ψ

∞2

, ···,Ψ

∞ν

]

to get a nonsingular matrix S

β=1

cβ

236 4. Theory and Application of Mixed Matrices

Similarly, we obtain from C another family of increasing chains

C : A

⊆ A

⊆···⊆A

for α =1, ···,μ.LetΦ

kα

be a set of linearly independent column vectors

spanning A

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

∞α

spanning U

such that

0α

⊆ Φ

1α

⊆···⊆Φ

bα

⊆ Φ

∞α

Then Φ



α=1

kα

spans AW

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



α=1

∞α

be-

comes a basis of U. Order the m column vectors of Φ as [Φ

∞1

,Φ

∞2

, ···,Φ

∞μ

]

to get a nonsingular matrix S

α=1

rα

Put

A = S

−1

.LetC

⊆ Col(

A) be the column subset corresponding

,andR

⊆ Row(

A) the row subset corresponding to

, where

= Ψ

= Φ

= Ψ

\ Ψ

k−1

= Φ

\ Φ

k−1

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

∞

= Ψ \ Ψ

∞

= Φ \ Φ

Then the consistency of the basis vectors Ψ and Φ with the chains C and A

implies that

A[R

]=O if 0 ≤ l<k≤∞.

Since



l=0

|−



l=0

and p

k−1

)=p

) (= min p

)fork =1, ···,b, it holds that

| = |C

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

Furthermore it can be shown from (4.125) (see the proof of Theorem 4.4.4)

that

rank

A[R

] = min(|R

|, |C

|)fork =0, 1, ···,b,∞.

That is to say,

A is in a proper block-triangular form, where the number

of square blocks b is given by the length of C. This completes the proof of

Theorem 4.8.6.

When the strong duality (or the rank formula) (4.125) holds true, the

lattice L

min

) admits an alternative expression. Deﬁne L(A, Π, Γ )tobe

the family of subspaces W of V such that

W ⊆ W (β =1, ···,ν),Π

AW ⊆ AW (α =1, ···,μ), ker A ⊆ W.

(4.126)

Theorem 4.8.7. For an m × n partitioned matrix A, the rank formula

(4.125) holds true if and only if L(A, Π, Γ ) = ∅.IfL(A, Π, Γ ) = ∅, then

min

)=L(A, Π, Γ ).

4.8 Partitioned Matrix 237

Proof.ForW ∈Wwe have (cf. (4.122))

(W )=



α=1

dim(Π

AW ) − dim W

≥ dim(AW ) − dim W ≥−dim(ker A)=rankA − n.

It then follows that p

(W )+n =rankA if and only if



α=1

dim(Π

AW )=dim(AW ) = dim W − dim(ker A).

The ﬁrst equality here is equivalent to Π

AW ⊆ AW (α =1, ···,μ), and the

second to ker A ⊆ W . Therefore, the rank formula (4.125) holds true if and

only if L(A, Π, Γ ) = ∅. The ﬁnal claim is obvious from the above argument.

Remark 4.8.8. Theorems 4.8.6 and 4.8.7 imply that the nonemptyness of

L(A, Π, Γ ) is necessary and suﬃcient for the existence of a proper block-

triangular form under PE-transformations. It may be said that L(A, Π, Γ )

captures the geometric aspect of proper block-triangularization more directly,

while L

min

) gives a combinatorial representation of the same lattice. 2

A partitioned matrix A of full rank (i.e., rank A = min(m, n)) has a proper

block-triangular form by Theorem 4.8.6 and the following fact.

Proposition 4.8.9. The rank formula (4.125) holds true for a partitioned

matrix of full rank.

Proof. This follows from p

(0) = 0, p

(V ) ≤ m −n and the ﬁrst inequality

in Proposition 4.8.3.

A partitioned matrix A admitting a proper block-triangularization is

called PE-reducible if it can be transformed into a proper block-triangular

form with two or more nonempty blocks by a PE-transformation; otherwise

it is called PE-irreducible. Note that PE-reducibility or PE-irreducibility is

deﬁned only if A possesses a proper block-triangular form.

Proposition 4.8.10.

(1) A PE-irreducible partitioned matrix is of full rank.

(2) A partitioned matrix of full rank is PE-irreducible if and only if

min

⎧

⎨

⎩

{V } (if m<n)

{0,V} (if m = n)

{0} (if m>n) .

238 4. Theory and Application of Mixed Matrices

Proof. (1) and the “only if” part of (2) follow from the proof of Theorem

4.8.6. For the “if” part of (2), suppose that A can be brought to a proper

block-triangular matrix

A with two or more nonempty blocks by a PE-

transformation. Then there exists ∅ = I ⊆ Row(

A)and∅ = J ⊆ Col(

such that rank

A[I,J]=0,rank

A[Row(

A) \ I,J]=|Row(

A) \ I|,and

rank

A[I,Col(

A) \J]=|Col(

A) \J|. The subspace W ∈Wthat corresponds

to J (as in (4.121)) satisﬁes p

(W )=rankA − n. Furthermore, W = V if

m ≤ n and W =0ifm ≥ n.

A is a proper block-triangular matrix obtained from A by a PE-

transformation and if, in addition, all the diagonal blocks

A[R

]for

k =0, 1, ···,b,∞ are PE-irreducible, we say that

A is a PE-irreducible de-

composition of A, whereas the diagonal blocks

A[R

](k =0, 1, ···,b,∞)

are called the PE-irreducible components of A. The matrix

A constructed

in the proof of Theorem 4.8.6 is a PE-irreducible decomposition due to the

maximality of the chain C. The PE-irreducible components of a partitioned

matrix are uniquely determined up to PE-transformations, as follows.

Theorem 4.8.11. The set of PE-irreducible components of a partitioned

matrix is unique to within PE-transformations of each component.

Proof. The proof relies on a module-theoretic argument, in particular, on the

Jordan–H¨older theorem for modules. See Ito–Iwata–Murota [138] for details.

4.8.3 Partial Order Among Blocks

For a block-triangular matrix in general a partial order is deﬁned among

the blocks by the zero/nonzero structure of the oﬀ-diagonal blocks. Unlike

the CCF of LM-matrices, the partial order among the blocks is not uniquely

determined for partitioned matrices. Recall, by contrast, that the CCF gives a

unique decomposition of an LM-matrix that is ﬁnest not only with respect to

the partition into blocks but also with respect to the partial order among the

blocks. Mathematically, the nonuniqueness of the partial order for partitioned

matrices is ascribed to the nondistributivity of the lattice L

min

)ofthe

minimizers of the PE-surplus function p

, whereas the uniqueness for LM-

matrices is due to the distributivity of the lattice L

min

(p) of the minimizers

of the LM-surplus function p.

Let A be a partitioned matrix, as in §4.8.1, and

A = S

−1

be a proper

block-triangular matrix obtained from A by a PE-transformation. Denote by

; R

, ···,R

; R

∞

) and (C

; C

, ···,C

; C

∞

) the partitions of R =Row(

and C = Col(

A), respectively. The partial order  deﬁned among the blocks

is the reﬂexive and transitive closure of the relation given by: C

 C

A[R

] = O with the convention (2.15). We denote this partially ordered

set ({C

; C

, ···,C

; C

∞

}, )byP(

A). The order ideals of P(

A) constitute a

4.8 Partitioned Matrix 239

distributive sublattice of 2

, which we denote by D(

A); namely, D(

A)=L(P)

for P = P(

A) in the notation of (2.27).

A subset J of Col(

A) can be naturally identiﬁed with a subspace of V ,

on which the given A acts. We denote this subspace by ψ(J, S

), i.e.,

ψ(J, S

)=span{S

(0, ···, 0,

∨

, 0, ···, 0)

| j ∈ J}. (4.127)

Then

ψ(J

∪J

)=ψ(J

)+ψ(J

),ψ(J

∩J

)=ψ(J

)∩ψ(J

and hence

ψ(D(

A),S

)={ψ(J, S

) | J ∈D(

A)}

is a distributive sublattice of the modular lattice formed by the subspaces of

V .

Proposition 4.8.12. If

A = S

−1

is a proper block-triangular matrix ob-

tained from a partitioned matrix A by a PE-transformation, then ψ(D(

A),S

)

is a sublattice of L

min

)=L(A, Π, Γ ).

Proof.ForJ ∈D(

A) put W = ψ(J, S

). Since

A = S

−1

is a PE-

transformation, we have Γ

W ⊆ W for β =1, ···,ν. It follows from the

deﬁnition of a proper block-triangular form that ker A ⊆ W and from the

deﬁnition of the partial order that Π

AW ⊆ AW for α =1, ···,μ. Hence

W ∈L(A, Π, Γ ).

Suppose we have two proper block-triangular matrices,

A = S

−1

and



= S



−1



, obtained from A by PE-transformations. We say that

A is a ﬁner decomposition than



if ψ(D(



),S



) is a proper sublattice of

ψ(D(

A),S

). Furthermore, we say that

A is a ﬁnest-possible decomposition of

A if there exists no proper block-triangular matrix



which is obtained from

A by a PE-transformation and is ﬁner than

Theorem 4.8.13. Suppose that a partitioned matrix A has a proper block-

triangular form under PE-transformations. Then

A = S

−1

is a ﬁnest-

possible decomposition of A if and only if ψ(D(

A),S

) is a maximal distribu-

tive sublattice of L

min

)=L(A, Π, Γ ).

Proof. This follows from Proposition 4.8.12 and Lemma 4.8.14 below.

Lemma 4.8.14. For any distributive sublattice D



of L(A, Π, Γ ) there exists

a PE-transformation

A = S

−1

such that ψ(D(

A),S

) ⊇D



Proof. According to Birkhoﬀ’s representation theorem, the distributive lat-

tice D



can be represented by a partially ordered set P



=({Z

, ···,Z

}, ⊆)

240 4. Theory and Application of Mixed Matrices

consisting of the join-irreducible elements of D



except the minimum ele-

ment of D



(see Remark 2.2.6). We assume that k ≤ l if Z

⊆ Z

, and put

= min D



.Foreachβ =1, ···,ν,let

0β

be a set of basis vectors of

∩ V

.Fork =1, ···,b inductively deﬁne

kβ

to be a set of vectors such

that

kβ

∪





⊂Z

lβ



is a basis of Z

∩ V

, and ﬁnally let

∞β

be such

that Ψ

∞β

∪





k=0

kβ



is a basis of V

. Then deﬁne the matrix S

cβ

from the column vectors of Ψ

for β =1, ···,ν, and put S

β=1

cβ

.The

other transformation matrix S

α=1

rα

should be constructed similarly

from the basis vectors {

kα

| k =0, 1, ···,b,∞; α =1, ···,μ} compatible

with Π

for k =0, 1, ···,b and α =1, ···,μ. We claim that

A[R

]=O unless Z

⊆ Z

This is because Z

∈D



⊆L(A, Π, Γ ) implies Π

⊆ AZ

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

where Π

is spanned by



⊆Z

kα

. The claim in turn implies that

 C

⇒ Z

⊆ Z

. Hence ψ(D(

A),S

) ⊇D



An instance of nonunique partial order will be given in Example 4.8.24.

4.8.4 Generic Partitioned Matrix

We have seen that not every partitioned matrix admits a proper block-

triangularization. In this section we introduce a certain genericity assumption

on the nonzero entries with a view to identifying a subclass of partitioned

matrices for which the proper block-triangularization exists.

We consider a partitioned matrix A that is generic in the following sense.

Let K be a subﬁeld of a ﬁeld F , A



αβ

be an m

×n

matrix over K for α =

1, ···,μ and β =1, ···,ν,andT = {t

αβ

∈ F | α =1, ···,μ; β =1, ···,ν}

be algebraically independent over K. Then

A =

⎡

⎢

⎣

···A

1ν

···A

2ν

μ1

μ2

···A

μν

⎤

⎥

⎦

⎡

⎢

⎣



··· t

1ν



1ν



··· t

2ν



2ν

μ1



μ1

μ2



μ2

···t

μν



μν

⎤

⎥

⎦

is a partitioned matrix over the ﬁeld F , where A

αβ

= t

αβ



αβ

for α =1, ···,μ

and β =1, ···,ν. Such a matrix A is named a generic partitioned matrix (or

GP-matrix for short) of type (m

, ···,m

; n

, ···,n

) with ground ﬁeld K.

A GP-matrix of type (1, ···, 1; 1, ···, 1) is nothing but a generic matrix. A

GP-matrix is called a GP(2)-matrix if m

≤ 2forα =1, ···,μ and n

≤ 2

for β =1, ···,ν.

For a generic partitioned matrix it is natural to assume that the matrices

and S

in the PE-transformation (4.114) are nonsingular matrices over