Murota K. Matrices and Matroids for Systems Analysis

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

1.3 Mathematics on Mixed Polynomial Matrices 29

det A

(1)

= det A

(2)

= −det

(3)

= R

+ sL · R

For the degree of det

(3)

, we may apply the method of §1.3.2 to each diagonal

block and sum up the degrees thus obtained. This will be more eﬃcient than

to apply the same method to the whole matrix.

Block-triangular decompositions of the above kind are one of the ma-

jor topics studied in this book; among which are the Dulmage–Mendelsohn

decomposition in Chap. 2 and the combinatorial canonical form (CCF) in

Chap. 4.

Notes. The concept of a mixed matrix was introduced in Murota–Iri [238]

with the observation on two kinds of numbers explained in §1.2.1, while the

dimensional analysis in §1.2.3 is due to Murota [200]. This chapter is an

improved version of a presentation (Murota [223]) at ICIAM 95.

2. Matrix, Graph, and Matroid

This chapter lays the mathematical foundation for combinatorial methods

of systems analysis. Combinatorial properties of numerical matrices can be

stated and analyzed with the aid of matroid theory, whereas those of polyno-

mial matrices are formulated in the language of valuated matroids in Chap. 5.

Emphasis is laid also on the general decomposition principle based on sub-

modularity, and accordingly the Dulmage–Mendelsohn decomposition, which

serves as a fundamental tool for the generic-case analysis of matrices, is pre-

sented in a systematic manner.

2.1 Matrix

2.1.1 Polynomial and Algebraic Independence

Let K be a ﬁeld (typically K = Q (rational numbers) or K = R (real

numbers)) and X be an indeterminate (independent variable). We denote by

K[X]thering of polynomials in X over K, i.e.,

K[X]={



k=0

| 0 ≤ N ∈ Z,α

∈ K (0 ≤ k ≤ N)}.

For p(X)=



k=0

with α

= 0, the highest index N is called the degree

of p(X), denoted deg p, whereas α

is the leading coeﬃcient. A polynomial

is called monic if the leading coeﬃcient is equal to one. We denote by K(X)

the ﬁeld of rational functions in X over K, i.e.,

K(X)={p(X)/q(X) | p(X),q(X) ∈ K[X],q(X) =0}.

For a rational function f(X) ∈ K(X), the degree of f(X), denoted deg f,

is deﬁned by deg f = deg p − deg q with reference to an expression f(X)=

p(X)/q(X) with p(X),q(X) ∈ K[X], where deg f is well-deﬁned, indepen-

dent of the expression. A rational function

f(X) ∈ K(X) is said to be

proper if deg f ≤ 0, and strictly proper if deg f<0. A rational function

f(X) ∈ K(X) is called a Laurent polynomial if X

f(X) ∈ K[X] for some

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

32 2. Matrix, Graph, and Matroid

integer N ∈ Z; in other words, f (X) is a Laurent polynomial if and only if

f(X) ∈ K[X, 1/X], where

K[X, 1/X]={



k=−N

| 0 ≤ N

∈ Z,α

∈ K (−N

≤ k ≤ N

)}.

For a Laurent polynomial f (X) we deﬁne

ordf = −min{N ∈ Z | X

f(X) ∈ K[X]}. (2.1)

Obviously, f (X) is a polynomial if and only if ordf ≥ 0.

Let F be an extension ﬁeld of K (i.e., F ⊇ K). For a subset Y of F ,

we denote by K(Y)andK[Y]theﬁeld adjunction and the ring adjunction,

respectively; that is, K(Y) is the extension ﬁeld of K generated by Y over

K while K[Y] the ring generated by Y over K.

An element y of F is called algebraic over K if there exists a nontrivial

polynomial p(X) in one indeterminate X over K such that p(y) = 0, where

p(X) is called nontrivial if some of its coeﬃcients are distinct from zero. An

element of F is called transcendental over K if it is not algebraic over K.A

subset (more precisely, multiset)

Y = {y

, ···,y

} of F is called algebraically

independent over K if either of the following equivalent conditions holds:

(i) For any i, y

is transcendental over K(Y\{y

}),

(ii) There exists no nontrivial polynomial p(X

, ···,X

)inq inde-

terminates over K such that p(y

, ···,y

)=0,

where p(X

, ···,X

) is called nontrivial if some of its coeﬃcients are distinct

from zero. We call Y algebraically dependent if it is not algebraically indepen-

dent. In this book we often use an informal expression like “y

, ···,y

are al-

gebraically independent over K” to mean the set {y

, ···,y

} is algebraically

independent over K, which is a stronger assertion than the elementwise tran-

scendency of each y

over K.

The degree of transcendency of F over K, denoted dim

F , means the

maximum cardinality of a subset of F that is algebraically independent over

K, where dim

F can be inﬁnite. For instance, dim

R =+∞.

Example 2.1.1. Let t

be independent parameters (indeterminates)

over Q.Forz

= t

+ t

, z

=(t

+ t

)

, z

= t

−t

we can ﬁnd a nontrivial

polynomial p(X

)=(X

−X

)

−X

for which p(z

) = 0. Hence

} is algebraically dependent over Q, whereas each z

is transcenden-

tal over Q. We see dim

Q(z

) = 2. On the other hand, for y

= t

+ t

, y

=2t

, there is no nontrivial polynomial q(X

)

over Q such that q(y

) = 0, and therefore, {y

} is algebraically

independent over Q. Accordingly, dim

Q(y

)=3. 2

We refer to Jacobson [149, 150] and van der Waerden [325] as general

references for algebraic concepts.

2.1 Matrix 33

2.1.2 Determinant

We consider matrices over a ﬁeld F . For a matrix A,therow set and the col-

umn set are denoted by Row(A) and Col(A), i.e., A =(A

| i ∈ Row(A),j ∈

Col(A)), where A

is the (i, j)-entry. For I ⊆ Row(A)andJ ⊆ Col(A),

A[I,J]=(A

| i ∈ I,j ∈ J) means the submatrix of A with row set I and

column set J.

For a square matrix A, its determinant is denoted by det A. Namely, for

an n × n matrix A, we deﬁne

det A =



π∈S

sgn π ·



i=1

iπ(i)

, (2.2)

where S

denotes the set of all the permutations of order n, and sgn π = ±1

is the signature of a permutation π. A matrix is nonsingular if it is square

and its determinant is distinct from zero. The set of nonsingular matrices of

order n over F will be denoted by GL(n, F ).

For I ⊆ R ≡ Row(A)andJ ⊆ C ≡ Col(A), we denote by det A[I,J]

the determinant of the submatrix A[I,J]. Since the sign of a determinant

depends on the orderings of rows and columns, we always assume that the

orderings of the elements of I and J are compatible with those of R and

C, unless otherwise stated. The determinant of a submatrix is sometimes

referred to as a minor or as a subdeterminant.

Proposition 2.1.2 (Laplace expansion). For a square matrix A and i ∈

R, it holds that

det A =



j∈C

(−1)

i+j

· A

· det A[R \{i},C \{j}]. (2.3)

Proof. In the summation of (2.2) classify π according to the value of π(i)to

obtain

det A =



j=1

⎡

⎣



π:π(i)=j

sgn π ·



k=i

kπ(k)

⎤

⎦

The expression in [ ] is equal to (−1)

i+j

det A[R \{i},C \{j}].

The formula (2.3) is called the Laplace expansion with respect to row

i. A more general form of this formula is an expansion with respect to a

subset I ⊆ R. The following expression (2.4) is called the generalized Laplace

expansion with respect to row set I ⊆ R.

Proposition 2.1.3 (Generalized Laplace expansion). For a square ma-

trix A and I ⊆ R, it holds that

det A =



J⊆C,|J|=|I|

sgn (I,J) · det A[I,J] · det A[R \ I,C \ J]. (2.4)

34 2. Matrix, Graph, and Matroid

Here, sgn (I,J)=±1 denotes the signature of the permutation



, ···,i

; i

k+1

, ···,i

, ···,j

; j

k+1

, ···,j



where I = {i

, ···,i

}, R \ I = {i

k+1

, ···,i

} with i

< ··· <i

; i

k+1

··· <i

,andJ = {j

, ···,j

}, C \ J = {j

k+1

, ···,j

} with j

< ··· <j

;

k+1

< ···<j

Proof. The proof is similar to the one for Proposition 2.1.2.

We now derive the Grassmann–Pl¨ucker identity, which would be the most

important identity for determinants in the context of the combinatorial study

of matrices, to be explained in Remark 2.1.8.

Proposition 2.1.4 (Grassmann–Pl¨ucker identity). Let A be a matrix

with |R|≤|C|,whereR =Row(A) and C = Col(A).ForJ, J



⊆ C with

|J| = |J



| = |R| and i ∈ J \ J



, it holds that

det A[R, J]·det A[R, J





j∈J



det A[R, J −i+j]·det A[R, J



+i−j], (2.5)

where J−i+j is a short-hand notation for (J \{i})∪{j} in which the column j

is put at the position of column i in J; similarly for J



+i−j =(J



∪{i})\{j}.

Proof. To avoid complication in notation, we present the idea for a 4 × 6

matrix A =





with J = {1, 2, 3, 4}, J



= {3, 4, 5, 6} and

i = 1, where a

(j =1, ···, 6) are 4-dimensional column vectors. Consider a

8 × 8 matrix

A =



000a



which is singular. The generalized Laplace expansion (2.4) applied to

A yields

(2.5).

Example 2.1.5. The Grassmann–Pl¨ucker identity is illustrated here. For

A =

100a

010a

001a

with C = {1, 2, 3, 4, 5, 6}, J = {1, 2, 3}, J



= {4, 5, 6}, i =1,wehavethe

following identity:

100 a

010 a

001 a

00 1 a

10 0 a

01 0 a

00 a

1 a

10 a

0 a

01 a

0 a

00 a

10 a

01 a

where |·|means a determinant. Note how the columns are ordered. 2

2.1 Matrix 35

The determinant of a matrix product AB admits an expansion in terms

of the minors of A and B, called the Cauchy–Binet formula.

Proposition 2.1.6 (Cauchy–Binet formula). For an m × n matrix A

and an n × m matrix B,wherem ≤ n, it holds that

det(AB)=



|J|=m

det A[R, J] · det B[J, C],

where R =Row(A), C = Col(B),andJ runs over all subsets of size m of

Col(A)=Row(B).

Proof. This formula can be derived from the generalized Laplace expansion

(2.4) applied to the (m + n) × (m + n) matrix

M =



B −I



In fact, the expansion (2.4) with respect to the row set I = R yields

det M =



|J|=m

(−1)

det A[R, J] · det B[J, C],

a summation over J ⊆ Col(A) with |J| = m, whereas







B −I





AB O

B −I



implies det M =(−1)

det(AB).

Proposition 2.1.7 (Schur complement). If A is square and D is non-

singular, then

det





= det D · det



A − BD

−1



Proof. This follows from



I −B





−1









A − BD

−1



The submatrix A − BD

−1

C is often called the Schur complement.

Remark 2.1.8. The Grassmann–Pl¨ucker identity has important combina-

torial implications, which play signiﬁcant roles in this book.

In the Grassmann–Pl¨ucker identity, if the left-hand side of (2.5) is distinct

from zero, then there exists at least one nonzero term in the summation on

the right-hand side. This means that B = {J ⊆ C | det A[R, J] =0} (= the

family of column bases of A) has the following property:

36 2. Matrix, Graph, and Matroid

(BM

)ForJ, J



∈Band for i ∈ J \ J



, there exists j ∈ J



\ J such

that J −i + j ∈Band J



+ i − j ∈B.

This property is formulated in §2.3.4 as the simultaneous exchange property

for matroids.

In case the entries of the matrix A are rational functions (more generally,

when F is a non-Archimedean valuated ﬁeld), we can talk of the consistency

of (2.5) with respect to degree (additive valuation). Let ω : B→Z denote

the degree of det A[R, J]forJ ∈B, i.e., ω(J) = deg det A[R, J]. The degree

of the left-hand side of (2.5) is equal to ω(J)+ω(J



), and there exists, in

the summation on the right-hand side, at least one term of degree greater

than or equal to this. This means the function ω : B→Z has the following

property:

(VM) For J, J



∈Band for i ∈ J \ J



, there exists j ∈ J



\ J such

that J −i + j ∈Band J



+ i − j ∈B,and

ω(J)+ω(J



) ≤ ω(J − i + j)+ω(J



+ i − j).

This property is formulated in §5.2 as an axiom of valuated matroids.

In case the entries of the matrix are real numbers (more generally, when

F is an ordered ﬁeld), we can talk of the consistency of (2.5) with respect

to sign (±1). Let σ : B→{1, −1} denote the sign of det A[R, J]forJ ∈B,

i.e., σ(J) = sgn det A[R, J], where J is considered an ordered set and assume

σ(πJ)=sgnπ ·σ(J) for a permutation π of J. If the left-hand side of (2.5) is

positive, then there exists at least one positive term in the summation on the

right-hand side. This means the function σ : B→{1, −1} has the following

property:

(OM) For J, J



∈Band for i ∈ J \ J



, there exists j ∈ J



\ J such

that J −i + j ∈Band J



+ i − j ∈B,and

σ(J) · σ(J



)=σ(J −i + j) · σ(J



+ i − j),

where we still assume the convention in Proposition 2.1.4 that J −i+j denotes

the ordered set in which the column j is put at the position of column i in

J. This property is formulated as an axiom of oriented matroids, though

nottreatedinthisbook(seeBj¨orner–Las Vergnas–Sturmfels–White–Ziegler

[14]). 2

2.1.3 Rank, Term-rank and Generic-rank

The rank of A, as deﬁned in linear algebra, is equal to (i) the maximum num-

ber of linearly independent column vectors of A, (ii) the maximum number of

linearly independent row vectors of A, and (iii) the maximum size of a nonsin-

gular submatrix of A. We denote the rank of A by rank A. A maximum-sized

set of linearly independent column vectors is called a column basis of A.A

row basis is deﬁned in a similar manner.

Let A be a matrix with R =Row(A)andC = Col(A), and deﬁne ρ :

→ Z and λ :2

× 2

→ Z by

2.1 Matrix 37

ρ(J)=rankA[R, J],J⊆ C, (2.6)

λ(I,J)=rankA[I,J],I⊆ R, J ⊆ C. (2.7)

These functions satisfy the following inequalities, of which the ﬁrst is called

the submodular inequality. These inequalities are most fundamental in the

combinatorial study of matrices, as will be explained later.

Proposition 2.1.9.

(1) ρ(J

)+ρ(J

) ≥ ρ(J

∩ J

)+ρ(J

∪ J

),J

⊆ C.

(2) λ(I

)+λ(I

) ≥ λ(I

∪ I

∩ J

)+λ(I

∩ I

∪ J

⊆ R; J

⊆ C.

Proof. (1) We denote by a

the column vector of A at column j ∈ C.For

the submatrix A[R, J

∩ J

], take a column basis, say {a

| j ∈ B

}, where

⊆ J

∩J

and |B

| = ρ(J

∩J

). It is possible to make a column basis of

A[R, J

] by adding some vectors from among {a

| j ∈ J

} to the already

chosen set {a

| j ∈ B

}.Let{a

| j ∈ B

} be the added vectors, where

⊆ J

and |B

|+ |B

| = ρ(J

). Similarly, we can make a column basis

of A[R, J

∪ J

] by augmenting {a

| j ∈ B

∪ B

} with some vectors of

| j ∈ J

}.Let{a

| j ∈ B

} be the added vectors, where B

⊆ J

and |B

| + |B

| = ρ(J

∪ J

). Since {a

| j ∈ B

∪ B

} is a set of

linearly independent vectors and B

∪B

⊆ J

,wehave|B

|+|B

|≤ρ(J

This establishes the desired inequality.

(2) Consider

A =(I

| A), where I

is the identity matrix of order

m = |R|. We have Col(

A)=R∪C. Putting ˜ρ(I ∪J)=rank

A[Row(

A),I∪J],

we see from

A =(I

| A)=



-

JR \ I

 -

that λ(I,J)=˜ρ((R\I)∪J)+|I|−m. Then the submodularity of ˜ρ established

in (1) is equivalent to the claimed inequality for λ.

The concept of the term-rank of a matrix, introduced by Ore [256], is a

combinatorial version of the rank and plays a signiﬁcant role in the combi-

natorial analysis of matrices. As already mentioned, the rank of a matrix is

equal to the maximum size of a nonsingular submatrix, i.e.,

rank A = max{|I||A[I,J] is nonsingular,I⊆ R, J ⊆ C}.

38 2. Matrix, Graph, and Matroid

As a combinatorial version of nonsingularity, let us say that a matrix A is

term-nonsingular if the deﬁning expansion (2.2) of the determinant contains

at least one nonvanishing term, that is, if A

iπ(i)

=0(∀ i ∈ R) for some

bijection π : R → C. Obviously, nonsingularity implies term-nonsingularity,

since (2.2) is distinct from zero only if the summation contains a nonzero

term. The term-rank of A is then deﬁned by

term-rank A = max{|I||A[I,J] is term-nonsingular,I⊆ R, J ⊆ C}.

In other words, the term-rank of A is deﬁned as the maximum of k such

that A

=0,A

=0,···, A

= 0 for some suitably chosen dis-

tinct rows i

, ···,i

and distinct columns j

, ···,j

. A set of pairs

{(i

), (i

), ···, (i

)} with the property that A

=0,A

=0,

···, A

= 0 is sometimes called a partial transversal. It holds that

rank A ≤ term-rank A, (2.8)

since nonsingularity implies term-nonsingularity.

Another related concept, called the generic-rank, is deﬁned for a ma-

trix containing parameters, as follows. Let the entries A

of A be rational

functions over a ﬁeld K in q independent parameters, or indeterminates,

, ···,X

; i.e., A

∈ K(X

, ···,X

) (= the ﬁeld of rational functions in

, ···,X

)overK). Then any subdeterminant is a rational function in

, ···,X

over K. The rank of A viewed as a matrix over K(X

, ···,X

)

is deﬁned to be the maximum size of a submatrix whose determinant is a

nonzero rational function. We call this rank the generic rank of A, and de-

note it by generic-rank A. The generic-rank of A is equal to the rank of A

with parameters X =(X

, ···,X

) ﬁxed to a set of numbers t =(t

, ···,t

)

(in some extension ﬁeld of K) which is algebraically independent over K:

generic-rank A =rankA(t). (2.9)

This means, in the case of K = Q, that (2.9) holds true for “almost all”

choices of real numbers t =(t

, ···,t

) ∈ R

Let F be an extension ﬁeld of K containing an inﬁnite number of elements

(typically, K = Q and F = R). If a set of numerical values a ∈ F

are

substituted for the parameters X =(X

, ···,X

), each entry of A(a) belongs

to F , and therefore the rank of A(a) as a matrix over F can be deﬁned.

This rank is uniquely determined for those parameter values a ∈ F

which

lie outside some proper algebraic variety

(⊂ F

). The uniquely determined

rank is equal to the maximum of rank A(a)overa ∈ F

,andalsotothe

generic-rank of A:

generic-rank A = max

a∈F

rank A(a).

By a proper algebraic variety is meant a proper subset of F

that can be

represented as {(x

, ···,x

) ∈ F

| p(x

, ···,x

)=0} for some p(X) ∈

K[X

, ···,X

2.1 Matrix 39

Example 2.1.10. For a matrix A =



X 1



, we have generic-rank A =1

and term-rank A =2. 2

Example 2.1.11. For a matrix A =



1 X



over K = GF(2) (= the ﬁeld

consisting of 0 and 1), we have generic-rank A = term-rank A = 2, whereas

max

a∈K

rank A(a)=1. 2

We are often interested in the cases where the generic-rank and the term-

rank coincide. A matrix A is called a generic matrix if the set of its nonva-

nishing entries is algebraically independent over some ﬁeld. This means that

each of the nonvanishing entries of A can be regarded as an independent

parameter by itself. For example, among three matrices







+ X





+ X

)

− X



where X

are algebraically independent numbers (or independent pa-

rameters), A

and A

are generic matrices and A

is not. Note that, in A

there is no algebraic relation among Y

= X

, Y

= X

, Y

=2X

whereas, in A

, we have a relation (Z

− Z

)

= Z

for Z

= X

+ X

=(X

+ X

)

, Z

= X

− X

(cf. Example 2.1.1).

The following fact is obvious, but fundamental (Edmonds [67]).

Proposition 2.1.12. For a generic matrix A, it holds that

generic-rank A = term-rank A. (2.10)

Proof. Consider a k × k term-nonsingular submatrix of A, where k =

term-rank A. The deﬁning expansion of its determinant contains a term, say,

···A

, which cannot be cancelled out. Hence generic-rank A ≥

term-rank A. The reverse inequality is true in general by (2.8), in which

rank A = generic-rank A.

Remark 2.1.13. The term-rank of A is in fact a graph-theoretic concept

(see §2.2.3 for terminology). Consider a bipartite graph G =(V

−

;

A) that

has the vertex bipartition (V

−

)=(C, R) corresponding to the column

set C and the row set R, and the arc set

A deﬁned by

A = {(j, i) | i ∈ R, j ∈ C, A

=0}.

That is, an arc represents a nonvanishing entry of A. Then term-rank of A

is equal to the maximum size of a matching in G, which can be computed

eﬃciently in polynomial time (cf. §2.2.3). 2