Murota K. Matrices and Matroids for Systems Analysis

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

4. Theory and Application of Mixed Matrices

This chapter is devoted to a study on mixed matrices and layered mixed

matrices using matroid-theoretic methods. Particular emphasis is laid on the

combinatorial canonical form (CCF) of layered mixed matrices and related

decompositions, which generalize the Dulmage–Mendelsohn decomposition.

Applications to the structural solvability of systems of equations are also

discussed.

4.1 Mixed Matrix and Layered Mixed Matrix

In the previous section we have introduced the concept of mixed matrices

as a possible mathematical tool for systems analysis by means of matroid-

theoretic combinatorial methods. A mixed matrix is a matrix A expressed as

A = Q+T , where Q is a “constant” matrix and T is a “generic” matrix in the

sense that the nonzero entries of T are algebraically independent parameters.

A layered mixed (or LM-) matrix is deﬁned as a mixed matrix such that Q

and T have disjoint nonzero rows, i.e., no row of A = Q + T has both a

nonzero entry from Q and a nonzero entry from T.

The concept of a mixed matrix has been motivated by the physical ob-

servation that, when we describe a physical system in terms of elementary

variables, we can often distinguish two kinds of numbers, accurate numbers

and inaccurate numbers, together characterizing the physical system. The

“accurate numbers” constitute the matrix Q whereas the “inaccurate num-

bers” the matrix T . We may also refer to the numbers of the ﬁrst kind as

“ﬁxed constants” and to those of the second kind as “system parameters.”

In this chapter we shall investigate the mathematical properties of a mixed

matrix and an LM-matrix. Here is a preview of some nice properties enjoyed

by a mixed matrix or an LM-matrix.

• The rank is expressed as the minimum of a submodular function and can

be computed eﬃciently by a matroid-theoretic algorithm (§4.2).

• A concept of irreducibility is deﬁned with respect to a natural transforma-

tion of physical signiﬁcance. Irreducibility for an LM-matrix is an extension

of the well-known concept of full indecomposability for a generic matrix.

The irreducibility of an LM-matrix can be characterized, e.g., in terms

K. Murota, Matrices and Matroids for Systems Analysis,

Algorithms and Combinatorics 20, DOI 10.1007/978-3-642-03994-2

 Springer-Verlag Berlin Heidelberg 2010

132 4. Theory and Application of Mixed Matrices

of the irreducibility of determinant, which is an extension of Frobenius’s

characterization of a fully indecomposable generic matrix (§4.5).

• There exists a unique canonical block-triangular decomposition, called the

combinatorial canonical form (CCF for short), into irreducible components.

This is a generalization of the Dulmage–Mendelsohn decomposition. The

CCF can be computed by an eﬃcient algorithm (§4.4).

We now give the precise mathematical deﬁnitions of mixed matrices and

layered mixed matrices.

Let K be a subﬁeld of a ﬁeld F .Anm ×n matrix A =(A

)overF (i.e.,

∈ F ) is called a mixed matrix with respect to (K, F )if

A = Q + T, (4.1)

where

(M-Q) Q is an m × n matrix over K (i.e., Q

∈ K), and

(M-T) T is an m ×n matrix over F (i.e., T

∈ F ) such that the set

T of its nonzero entries is algebraically independent over K.

The class of m ×n mixed matrices is denoted as MM(K, F ; m, n) (or simply

as MM(K, F ) without reference to the size (m, n)) and the subﬁeld K will

be called the ground ﬁeld.

A mixed matrix A of (4.1) is called a layered mixed matrix (or an LM-

matrix) with respect to (K, F ) if the nonzero rows of Q and T are disjoint.

In other words, A is an LM-matrix if it can be put into the following form

with a permutation of rows:

A =













, (4.2)

where

(L-Q) Q is an m

× n matrix over K (i.e., Q

∈ K), and

(L-T) T is an m

× n matrix over F (i.e., T

∈ F ) such that the

set T of its nonzero entries is algebraically independent over K.

The class of such LM-matrices is denoted as LM(K, F ; m

,n) (or simply

as LM(K, F )). Obviously we have

LM(K, F ; m

,n) ⊆ MM(K, F ; m

+ m

,n).

Though an LM-matrix is a special case of mixed matrix, the following

argument would indicate that the class of LM-matrices is as general as the

class of mixed matrices both in theory and in application. Consider a system

of equations Ax = b in x ∈ F

described with an m × n mixed matrix

A = Q+T . By introducing an auxiliary variable w ∈ F

we can equivalently

rewrite the equation as

4.1 Mixed Matrix and Layered Mixed Matrix 133



−I









It may be assumed that F is so large that we can choose m numbers in F ,say

, ···,t

, which are algebraically independent over the ﬁeld K(T ), where

T denotes the set of the nonzero entries of T . Then, multiplying each of the

last m equations by t

, ···,t

, we obtain a system of equations



−diag [t

, ···,t

] T











, (4.3)

where diag [t

, ···,t

] is a diagonal matrix with “new” parameters t

, ···,t

and T



= t

. The coeﬃcient matrix of (4.3) is an LM-matrix with respect

to (K, F ) since the nonvanishing entries of [−diag [t

, ···,t

] | T



] are al-

gebraically independent over K. In this way any system of equations with

a mixed matrix as its coeﬃcient can be equivalently rewritten into an aug-

mented system using an LM-matrix. Hence we may restrict ourselves to LM-

matrices when we deal with the unique solvability of a system of equations

having a mixed matrix as its coeﬃcient matrix.

In general, with a mixed matrix A = Q + T ∈ MM(K, F ; m, n) we will

associate a (2m) × (m + n) LM-matrix

A ∈ LM(K, F ; m, m, m + n) deﬁned

A =







−diag [t

, ···,t

] T





. (4.4)

Note that the column set of

A has a natural one-to-one correspondence with

the union of the column set and the row set of A. Evidently, rank

A =rankA+

Example 4.1.1. Let {α, β, γ, t

} be algebraically independent over Q,

and put K = Q and F = Q(α, β, γ, t

). An equation



2+α 3

β 4+γ









described with a 2 ×2 mixed matrix with respect to (K, F ) can be rewritten

⎛

⎜

⎝

1023

0104

−t

0 t

α 0

0 −t

βt

⎞

⎟

⎠

⎛

⎜

⎝

⎞

⎟

⎠

⎛

⎜

⎝

⎞

⎟

⎠

by means of a 4 × 4 LM-matrix with respect to (K, F ). Note that

T =

{−t

, −t

α, t

β,t

γ} is algebraically independent over K. 2

A more size-eﬃcient transformation can be obtained following the same

principle as above but by distinguishing “mixed” rows from “pure” rows that

consist either solely of constants or solely of independent nonzero entries.

134 4. Theory and Application of Mixed Matrices

Suppose the coeﬃcient matrix A ∈ MM(K, F ; m, n)hasm

(≤ m) “mixed”

rows, say,

A = Q + T =

⎛

⎝

⎞

⎠

⎛

⎝

⎞

⎠

⎫

⎬

⎭

R, (4.5)

where R

, R

,andR

are disjoint row subsets of the row set R of A such that

∪R

= R and |R

| = m

(i =1, 2, 3), Q

and Q

are matrices over K,

and T

are matrices over F with independent nonzero entries. Then

by introducing an auxiliary m

-dimensional vector w, we obtain a similar

augmented system as (4.3) but now with an (m + m

) ×(n + m

) LM-matrix

A =





⎛

⎜

⎝

−diag[t

, ···,t

] T



⎞

⎟

⎠

, (4.6)

where diag [t

, ···,t

] is a diagonal matrix with “new” parameters t

, ···,t

∈ F and (T



)

= t

)

.Wehave

A ∈ LM(K, F ; m

+n)

and rank

A =rankA + m

When m

= m, this transformation is equivalent to the above transfor-

mation (4.4). In the other extreme case of m

= 0, i.e., when A is already

an LM-matrix, this transformation does not change A (i.e.,

A = A). The

transformation (4.6) will obviously be more attractive than transformation

(4.4) in practical situations.

Notes. The concept of mixed matrices was introduced in Murota–Iri [237,

238], whereas that of LM-matrices was subsequently introduced in Murota

[201] and Murota–Iri–Nakamura [239]. As survey papers on mixed matrices,

we may mention Murota [218] for mathematical properties and Murota [208,

214, 215] for applications to systems analysis.

4.2 Rank of Mixed Matrices

In this section we consider combinatorial characterizations of the rank of

a mixed matrix A with respect to (K, F ). The rank of A is deﬁned with

reference to the ﬁeld F , and not to the ground ﬁeld K. Hence the rank of A

is equal to (i) the maximum number of linearly independent column vectors

of A with coeﬃcients taken from F , (ii) the maximum number of linearly

independent row vectors of A with coeﬃcients taken from F , and (iii) the

maximum size of a submatrix of A for which the determinant does not vanish

in F .

4.2 Rank of Mixed Matrices 135

4.2.1 Rank Identities for LM-matrices

We will ﬁrst concentrate on an LM-matrix A =

∈ LM(K, F ; m

,n).

Then all the results for an LM-matrix will be translated to those for a general

mixed matrix through the trick of (4.4). We put C = Col(A), R =Row(A),

=Row(Q)andR

=Row(T ); then Col(Q) = Col(T )=C,andR =

∪ R

Before dealing with a general LM-matrix, let us review what is known for

the matrix T , all the nonzero entries of which are algebraically independent

over K. Note that a generic matrix T can be regarded as a special case of an

LM-matrix with m

=0.

The structure of T is represented by the functions τ, γ :2

→ Z and

Γ :2

→ 2

deﬁned by

τ(J) = term-rank T [R

,J],J⊆ C, (4.7)

Γ (J)={i ∈ R

|∃j ∈ J : T

=0},J⊆ C, (4.8)

γ(J)=|Γ (J)|,J⊆ C. (4.9)

It should be clear that Γ (J) stands for the set of nonzero rows of the sub-

matrix T [R

,J], and γ(J) for the number of nonzero rows of T [R

,J]. The

functions τ and γ both enjoy submodularity (cf. Propositions 2.1.9 and 2.1.12,

Lemma 2.2.16), that is,

τ(J

)+τ(J

) ≥ τ (J

∪ J

)+τ(J

∩ J

),J

⊆ C,

γ(J

)+γ(J

) ≥ γ(J

∪ J

)+γ(J

∩ J

),J

⊆ C.

These two functions are related by

τ(J) = min{γ(J



) −|J



||J



⊆ J} + |J|,J⊆ C. (4.10)

This is a version of the fundamental minimax relation (cf. Theorem 2.2.17)

concerning the maximum matchings and the minimum covers of a bipartite

graph, which is called the Hall–Ore theorem in §2.2.3. Recall also that the

function γ(J) −|J| is called the surplus function.

Combining Proposition 2.1.12 and (4.10) we obtain a rank formula for T:

rank T = term-rank T = min{γ(J) −|J||J ⊆ C}+ |C|. (4.11)

It is emphasized that the ﬁrst equality, connecting the algebraic quantity

(rank) to a combinatorial quantity (term-rank), is a consequence of the al-

gebraic independence of the set T of the nonzero entries of T , whereas the

second equality is due to a purely combinatorial min-max duality theorem.

We will use an argument of this type to derive a rank formula for a general

LM-matrix.

We are now in the position to consider a general LM-matrix A. Note that

a submatrix of T is nonsingular if and only if it is term-nonsingular.

136 4. Theory and Application of Mixed Matrices

Lemma 4.2.1. A square LM-matrix A =

∈ LM(K, F ) is nonsingular

if and only if both Q[R

,J] and T [R

,C\J] are nonsingular for some J ⊆ C.

Proof. Consider the generalized Laplace expansion (cf. Proposition 2.1.3):

det A =



J⊆C,|J|=m

±det Q[R

,J] · det T [R

,C \ J].

If det A = 0, the summation contains at least one nonvanishing term, namely,

det Q[R

,J] = 0 and det T [R

,C \ J] = 0 for some J. Conversely, sup-

pose that both Q[R

]andT [R

,C \ J

] are nonsingular for some J

Let t

···t

be a term contained in det T [R

,C\J

]. The algebraic inde-

pendence of T ensures that no similar terms arise from diﬀerent J’s. Hence

···t

appears in det A with a nonzero coeﬃcient, which is equal to

det Q[R

]. Hence det A =0.

The following fact is a basic rank identity for an LM-matrix.

Theorem 4.2.2. For an LM-matrix A =

∈ LM(K, F ),

rank A = max{rank Q[R

,J] + term-rank T [R

,C \ J] | J ⊆ C}. (4.12)

Proof. Lemma 4.2.1 applied to submatrices of A establishes the claim.

As the second step of the derivation of the rank formula for A, the right-

hand side of the basic identity (4.12) in Theorem 4.2.2 should be rewritten

using a combinatorial min-max duality result. To this end, we will ﬁrst trans-

late (4.12) into a matroid-theoretic expression.

Let M(A), M(Q)andM(T ) be the matroids deﬁned on C by matrices A,

Q and T , respectively, with respect to the linear independence among column

vectors. The rank function of M(Q) is given by

ρ(J)=rankQ[R

,J],J⊆ C, (4.13)

while that of M(T )isτ of (4.7). Then (4.12) in Theorem 4.2.2 is rewritten

rank A = max{ρ(J)+τ(C \ J) | J ⊆ C}, (4.14)

and Lemma 4.2.1 is rephrased as follows, where ∨ means the union of ma-

troids.

Theorem 4.2.3. For an LM-matrix A =

∈ LM(K, F ), it holds that

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

rank A = min{ρ(J)+τ (J) −|J||J ⊆ C} + |C|. (4.15)

Proof. It follows from Lemma 4.2.1, applied to submatrices of A, that

rank A[R, J]=|J| if and only if rank Q[R



]=|J



| and rank T [R

,J\J



|J \J



| for some J



⊆ J.Thatis,J is independent in M(A) if and only if it

4.2 Rank of Mixed Matrices 137

can be partitioned into two disjoint subsets that are independent in M(Q)

and M(T ), respectively. Namely, M(A)=M(Q) ∨ M(T ). Then we have

rank A =rankM(A) = rank (M(Q) ∨M(T )), in which rank (M(Q) ∨M(T ))

equals the right-hand side of (4.15) by the rank formula (2.80) for matroid

union.

Remark 4.2.4. A combination of (4.14) and (4.15) yields

ρ(J

)+τ(C \ J

) ≤ rank A ≤ ρ(J

)+τ(J

)+|C \ J

| (J

⊆ C).

This makes it possible to estimate rank A using any J

⊆ C. Further-

more, by Theorem 4.2.2 and Theorem 4.2.3, there exist J

, J

for which this

estimate is tight. In particular, Theorem 4.2.2 guarantees the existence of a

“certiﬁcate” (namely, J attaining the maximum) for the nonsingularity of A,

whereas Theorem 4.2.3 the existence of a “certiﬁcate” (namely, J attaining

the minimum) for the singularity of A. 2

The rank formula (4.15) is certainly a nontrivial and meaningful expres-

sion, giving a combinatorial characterization of rank A in terms of the min-

imum value of a submodular function. But it is not satisfactory enough in

that it does not extend the rank formula (4.11) for T . In fact, in this special

case (with A = T and ρ = 0) the expression (4.15) reduces to

rank T = min{τ(J) −|J||J ⊆ C}+ |C|,

which is almost a triviality, since the minimum on the right-hand side is

obviously attained by J = C and therefore the formula claims that rank T =

τ(C), i.e., rank T = term-rank T .

In order to obtain a more useful rank formula for A, we will introduce a

set function p :2

→ Z deﬁned by

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

as an extension of the surplus function γ(J) −|J| in the rank formula (4.11)

for T. We name p the LM-surplus function. This function p expresses a com-

bination of the combinatorial structures of the constituent matrices Q and T ,

with ρ standing for Q and γ for T . The LM-surplus function p is submodular,

namely,

p(J

)+p(J

) ≥ p(J

∪ J

)+p(J

∩ J

),J

⊆ C, (4.17)

since both ρ and γ are submodular. In the special case where A = T (i.e.,

=0andρ = 0), the LM-surplus function p(J) reduces indeed to γ(J) −

|J|, which is the surplus function appearing in (4.11).

The following theorem gives another minimax expression for the rank of

an LM-matrix, due to Murota [201, 204] and Murota–Iri–Nakamura [239].

138 4. Theory and Application of Mixed Matrices

Theorem 4.2.5. For an LM-matrix A =

∈ LM(K, F ), it holds that

rank A = min{ρ(J)+γ(J) −|J||J ⊆ C} + |C|. (4.18)

Using the notation p this formula can be written as

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

Proof. The right-hand sides of (4.15) and (4.18) are equal, since

min

{ρ(J)+τ(J) −|J||J ⊆ C}

= min

{ρ(J) + min



{γ(J



) −|J



||J



⊆ J}|J ⊆ C}

= min



{min

{ρ(J) | J ⊇ J



} + γ(J



) −|J



||J



⊆ C}

= min



{ρ(J



)+γ(J



) −|J



||J



⊆ C},

where the ﬁrst equality is by (4.10) and the last equality is due to the mono-

tonicity of ρ(J) with respect to J.

The two expressions, (4.15) in Theorem 4.2.3 and (4.18) in Theorem 4.2.5,

look very similar, with τ in (4.15) replaced by γ in (4.18). Moreover, in both

formulas, the functions to be minimized are submodular in J. However, the

second expression (4.18) is superior to the ﬁrst (4.15) for two reasons:

1. It contains the rank formula (4.11) for T (=the Hall–Ore theorem for

bipartite matchings) as a special case;

2. It leads to a canonical block-triangular decomposition, to be explained

at length in §4.4.

Example 4.2.6. Consider a 4 × 5 LM-matrix

A =





11110

02110

000t

0 t

00t

with T = {t

} being algebraically independent over Q. The columns

and the rows are indexed as Col(A)=C = {x

} and Row(T )=

= {f

}. It turns out that J = {x

} attains the maximum on the

right-hand side of (4.12) with rank Q[R

,J] = term-rank T [R

,C \ J]=2.

Hence rank A = 2 + 2 = 4. This can be obtained also from the rank formulas

(4.15) in Theorem 4.2.3 and (4.18) in Theorem 4.2.5. It can be veriﬁed that,

in either formula, J = {x

} attains the minimum value −1 with ρ(J)=1,

τ(J)=γ(J)=0and|J| =2. 2

4.2 Rank of Mixed Matrices 139

4.2.2 Rank Identities for Mixed Matrices

In this subsection we provide some results on the rank of a general mixed

matrix A. In principle, these results are straightforward translations of the

above results for an LM-matrix applied to the associated LM-matrix

A of

(4.4), for which we have rank

A =rankA + m. We use the notations R =

Row(A)andC = Col(A).

Lemma 4.2.1 yields the following counterpart. Note that a submatrix of

T is nonsingular if and only if it is term-nonsingular.

Lemma 4.2.7. A square mixed matrix A = Q+T is nonsingular if and only

if both Q[I,J] and T [R \I,C\J] are nonsingular for some I ⊆ R and J ⊆ C.

The following identity is obtained from Theorem 4.2.2.

Theorem 4.2.8. For a mixed matrix A = Q + T ,

rank A = max{rank Q[I,J] + term-rank T [R \ I,C \ J] | I ⊆ R, J ⊆ C}.

(4.20)

The content of Lemma 4.2.7 can be expressed in matroid-theoretic terms

as follows. We denote by L(

A), L(Q), and L(T ) the bimatroids (cf. §2.3.7)

deﬁned respectively by matrices A, Q,andT ; for example, (I,J) is a linked

pair in L(A) if and only if A[I,J] is nonsingular.

Theorem 4.2.9. For a mixed matrix A = Q + T , it holds that L(A)=

L(Q) ∨ L(T ),where∨ means the union of bimatroids. 2

Theorem 4.2.10. For a mixed matrix A = Q + T ∈ MM(K, F ; m, n),it

holds that

rank A =rank[M([I

| Q]) ∨ M([I

| T ]) ] − m

= maximum size of a common independent set

of M([I

| Q])

∗

and M([I

| T ]),

where M([I

| Q])

∗

( M([−Q

| I

])) is the dual of M([I

| Q]).

Proof. Apply Theorem 4.2.3 to the LM-matrix

A of (4.4) and use the relation

rank

A =rankA + |R|. The second equality is due to the general relation

(2.81) between union and intersection of two matroids.

Deﬁne ˆρ, ˆτ,ˆγ :2

× 2

→ Z and

Γ :2

× 2

→ 2

ˆρ(I,J)=rankQ[I,J],I⊆ R, J ⊆ C,

ˆτ(I,J) = term-rank T [I,J],I⊆ R, J ⊆ C,

Γ (I,J)={i ∈ I |∃j ∈ J : T

=0},I⊆ R, J ⊆ C,

ˆγ(I,J)=|

Γ (I,J)|,I⊆ R, J ⊆ C.

Note that

Γ (I,J)=I ∩

Γ (R, J).

140 4. Theory and Application of Mixed Matrices

Theorem 4.2.11. For a mixed matrix A = Q + T , it holds that

rank A = min

I⊆R,J⊆C

{ˆρ(I,J)+ˆτ (I,J) −|I|−|J|} + |R| + |C|, (4.21)

rank A = min

I⊆R,J⊆C

{ˆρ(I,J)+ˆγ(I,J) −|I|−|J|} + |R| + |C|. (4.22)

Proof. Consider the LM-matrix

A of (4.4) and let ˜ρ, ˜τ,˜γ :2

R∪C

→ Z and

Γ :2

R∪C

→ 2

be the functions associated with

A by (4.13), (4.7), (4.9) and

(4.8). For I ⊆ R and J ⊆ C we have

˜ρ(I ∪ J)=ˆρ(R \ I,J)+|I|,

˜τ(I ∪ J)=ˆτ (R \ I,J)+|I|,

Γ (I ∪ J)=

Γ (R, J) ∪ I =

Γ (R \ I,J) ∪ I,

˜γ(I ∪ J)=ˆγ(R \ I,J)+|I|.

Substituting these expressions into the rank formulas (4.15) and (4.18) for

and noting the relation rank

A =rankA + |R|, we obtain the claims.

From the second formula in Theorem 4.2.11 we can derive some variants.

Corollary 4.2.12. For a mixed matrix A = Q + T , it holds that

rank A = min

I⊆R,J⊆C

{rank Q[I,J] −|I|−|J||rank T [I,J]=0} + |R| + |C|,

(4.23)

rank A = min

J⊆C

{rank Q[R \

Γ (R, J),J]+|

Γ (R, J)|−|J|} + |C|. (4.24)

Proof. The second rank formula (4.22) in Theorem 4.2.11 can be rewritten as

rank A = min

I,J

{rank Q[I,J] −|I \

Γ (R, J)|−|J|} + |R| + |C|.

Since the function to be minimized does not increase when I is replaced by

I \

Γ (R, J), we may assume I ∩

Γ (R, J)=∅, i.e., rank T [I,J] = 0. Hence

follows the ﬁrst expression. Furthermore, we may choose I as large as possible

under this condition, i.e., I = R\

Γ (R, J), which results in the second formula.

If A is an LM-matrix, in particular, the expression (4.24) specializes di-

rectly to the rank formula (4.18) in Theorem 4.2.5, from which (4.24) itself

has been derived by way of (4.22) and (4.23). Note that

Γ (R, J)=Γ (J) ⊆ R

and rank Q[R \

Γ (R, J),J]=rankQ[R

,J] for an LM-matrix. This demon-

strates the equivalence of these formulas.

Just as the duality concerning bipartite matchings can be expressed equiv-

alently by the Hall–Ore theorem and by the K¨onig–Egerv´ary theorem, the

rank formula above, which is a generalization of the Hall–Ore theorem, ad-

mits a reformulation of the K¨onig–Egerv´ary type found by Bapat [9].