Murota K. Matrices and Matroids for Systems Analysis
Подождите немного. Документ загружается.
4.8 Partitioned Matrix 241
the ground field K. We call such a transformation a GP-transformation.
It is emphasized that a GP-transformation preserves not only the partition
structure but the genericity in the above sense, and therefore the resulting
matrix remains a generic partitioned matrix.
A generic partitioned matrix A admitting a proper block-triangularization
under GP-transformations is called GP-reducible if it can be transformed
into a proper block-triangular form with two or more nonempty blocks by
a GP-transformation; otherwise it is called GP-irreducible. Note that GP-
reducibility or GP-irreducibility is defined only if A possesses a proper block-
triangular form.
The main objective of this section is to show that the proper block-
triangularization is possible for GP(2)-matrices, whereas this is not the case
with generic partitioned matrices of general type.
Example 4.8.15. The basic concepts introduced above are illustrated here.
Consider a 6 × 6 matrix
A =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
2t
11
t
11
t
12
t
12
t
13
t
13
t
13
t
21
t
21
t
22
t
23
t
23
t
31
t
31
t
32
−t
32
t
32
t
33
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
which is a GP(2)-matrix of type (2, 2, 2; 2, 2, 2) with K = Q. Using admissible
transformation matrices:
S
r
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
10
01
10
01
1 −1
01
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,S
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
10
−11
10
01
10
01
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
we obtain
˜
A = S
r
−1
AS
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
11
t
12
t
12
t
13
t
13
t
13
t
21
t
22
t
23
t
23
t
31
t
32
t
33
t
32
t
33
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,
which can be put into an explicit upper block-triangular form:
242 4. Theory and Application of Mixed Matrices
¯
A = P
r
˜
AP
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
13
t
11
t
11
t
12
t
12
t
13
t
21
t
22
t
23
t
31
t
32
t
33
t
32
t
33
t
13
t
23
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
with permutation matrices
P
r
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
100000
001000
000010
000001
010000
000100
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,P
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
010000
001000
000100
000010
000001
100000
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
The matrix
¯
A is a proper block-triangular matrix (in an explicit block-
triangular form), giving a GP-irreducible decomposition with the horizon-
tal tail
¯
A[R
0
,C
0
]=[
t
13
t
11
], the vertical tail
¯
A[R
∞
,C
∞
]=
t
13
t
23
, and two
square diagonal blocks
¯
A[R
1
,C
1
]=
t
21
t
22
t
31
t
32
and
¯
A[R
2
,C
2
]=[t
32
]. 2
Compatibly with the restriction of PE-transformations to GP-transforma-
tions, namely, the restriction to transformations over K, we introduce a vari-
ant of the PE-surplus function p
PE
as follows. Let U
◦
∼
=
K
m
and V
◦
∼
=
K
n
be K-linear spaces which are, respectively, expressed as direct sums of lower
dimensional component spaces:
U
◦
=
μ
1
α=1
U
◦
α
, dim
K
U
◦
α
= m
α
(α =1, ···,μ),
V
◦
=
ν
1
β=1
V
◦
β
, dim
K
V
◦
β
= n
β
(β =1, ···,ν).
Then we have the relations (4.117) and (4.118) for U = U
◦
⊗
K
F , V =
V
◦
⊗
K
F , U
α
= U
◦
α
⊗
K
F and V
β
= V
◦
β
⊗
K
F , where it should be clear that
U
◦
⊗
K
F , for example, denotes the linear space obtained from U
◦
(
∼
=
K
m
)
by extending the base field to F , and hence U
◦
⊗
K
F
∼
=
F
m
. We denote by
W
◦
the family of all the subspaces of V that can be generated by a direct
sum of subspaces of V
◦
β
’s, i.e.,
W
◦
= {W
◦
⊗
K
F | W
◦
: subspace of V
◦
,Γ
β
W
◦
⊆ W
◦
(β =1, ···,ν)}.
(4.128)
Similarly, we denote by Y
◦
the family of all the subspaces of U that can be
generated by a direct sum of subspaces of U
◦
α
’s. Then both W
◦
and Y
◦
form
a modular lattice. We define p
GP
: W
◦
→ Z and λ : Y
◦
×W
◦
→ Z by
4.8 Partitioned Matrix 243
p
GP
(W )=
μ
α=1
dim(A
α
W ) − dim W, W ∈W
◦
, (4.129)
λ(Y,W)=dim(AW/Y )=dim(AW ) − dim(AW ∩ Y ),
Y ∈Y
◦
,W ∈W
◦
, (4.130)
and call them the GP-surplus function and the GP-birank function, respec-
tively. Note that p
GP
is the restriction of p
PE
: W→Z to W
◦
, and hence,
by Lemma 4.8.2, p
GP
is submodular on W
◦
.
A combination of Proposition 4.8.3 and Theorem 4.8.6 can be adapted as
follows.
Proposition 4.8.16. For an m × n generic partitioned matrix A,
rank A ≤ min{p
GP
(W ) | W ∈W
◦
} + n ≤ term-rank A,
and a proper block-triangular matrix can be obtained by a GP-transformation
if and only if
rank A = min{p
GP
(W ) | W ∈W
◦
} + n. (4.131)
Proof. The proof is similar to those of Proposition 4.8.3 and Theorem 4.8.6.
Next, we have the following lemmas, the latter of which should be com-
pared with Theorem 2.3.47.
Lemma 4.8.17. For a generic partitioned matrix A the function λ : Y
◦
×
W
◦
→ Z is submodular, i.e.,
λ(Y
1
,W
1
)+λ(Y
2
,W
2
) ≥ λ(Y
1
+ Y
2
,W
1
+ W
2
)+λ(Y
1
∩ Y
2
,W
1
∩ W
2
)
for Y
i
∈Y
◦
, W
i
∈W
◦
(i =1, 2).
Proof. It is clear from the following calculation:
λ(Y
1
,W
1
)+λ(Y
2
,W
2
)
=dim(AW
1
)+dim(AW
2
) − dim(AW
1
∩ Y
1
) − dim(AW
2
∩ Y
2
)
=dim(A(W
1
+ W
2
)) + dim((AW
1
∩ AW
2
)/(Y
1
∩ Y
2
))
−dim((AW
1
∩ Y
1
)+(AW
2
∩ Y
2
))
≥ dim(A(W
1
+ W
2
)) + dim(A(W
1
∩ W
2
)/(Y
1
∩ Y
2
))
−dim(A(W
1
+ W
2
) ∩ (Y
1
+ Y
2
))
= λ(Y
1
+ Y
2
,W
1
+ W
2
)+λ(Y
1
∩ Y
2
,W
1
∩ W
2
).
Lemma 4.8.18. For an m × n generic partitioned matrix A, there exists a
pair Y
∗
∈Y
◦
and W
∗
∈W
◦
such that
(i) dim W
∗
− dim Y
∗
− λ(Y
∗
,W
∗
)=n − rank A,and
(ii) λ(Y
,W
)=λ(Y
∗
,W
∗
) for any Y
⊃ Y
∗
and W
⊂ W
∗
such that
dim Y
=dimY
∗
+1 and dim W
=dimW
∗
− 1.
244 4. Theory and Application of Mixed Matrices
Proof. Consider a pair (Y
∗
,W
∗
) which minimizes dim W
∗
− dim Y
∗
subject
to (i). Such (Y
∗
,W
∗
) certainly exists since (i) is satisfied by ({0},V). Then
for any Y
⊃ Y
∗
and W
⊂ W
∗
such that dim Y
=dimY
∗
+1 and dim W
=
dim W
∗
− 1, it follows from Lemma 4.8.17 that
λ(Y
∗
,W
∗
)+λ(Y
,W
) ≥ λ(Y
,W
∗
)+λ(Y
∗
,W
).
Because of the minimality of dim W
∗
− dim Y
∗
we have λ(Y
,W
∗
)=
λ(Y
∗
,W
∗
) since otherwise (Y
,W
∗
) would satisfy (i) with dim W
∗
−dim Y
<
dim W
∗
− dim Y
∗
. Likewise we have λ(Y
∗
,W
)=λ(Y
∗
,W
∗
). Therefore
λ(Y
,W
) ≥ λ(Y
∗
,W
∗
). On the other hand, it is clear that λ(Y
,W
) ≤
λ(Y
∗
,W
∗
) since Y
⊃ Y
∗
and W
⊂ W
∗
. Hence (Y
∗
,W
∗
) satisfies (ii).
Whereas the above two lemmas are valid for generic partitioned matrices
in general (even the genericity is irrelevant), the following theorem states a
key property valid for GP(2)-matrices (and not for generic partitioned ma-
trices of general type). We call this the K¨onig–Egerv´ary theorem for GP(2)-
matrices, since for a generic matrix it reduces to the K¨onig–Egerv´ary theorem
for bipartite graphs.
Theorem 4.8.19. For an m×n GP(2)-matrix A, there exists a pair Y
∗
∈Y
◦
and W
∗
∈W
◦
such that
(i) dim W
∗
− dim Y
∗
= n − rank A,and
(ii) λ(Y
∗
,W
∗
)=0.
In other words, there exists a GP-transformation
˜
A = S
r
−1
AS
c
and subsets
R
∗
⊆ Row(
˜
A) and C
∗
⊆ Col(
˜
A) such that
(i
) |R
∗
| + |C
∗
| = m + n − rank A,and
(ii
)rank
˜
A[R
∗
,C
∗
]=0.
Proof. Given a pair (Y
∗
,W
∗
) of Lemma 4.8.18, consider a GP-transformation
˜
A = S
r
−1
AS
c
such that a subset of the column vectors of S
r
spans Y
∗
and
a subset of the column vectors of S
c
spans W
∗
. We denote by R
∗
the com-
plement of the subset of Row(
˜
A) corresponding to Y
∗
and by C
∗
the subset
of Col(
˜
A) corresponding to W
∗
. Note that Row(
˜
A) and Col(
˜
A) have natural
one-to-one correspondences with Col(S
r
) and Col(S
c
), respectively, and that
|R
∗
| = m − dim Y
∗
, |C
∗
| =dimW
∗
and λ(Y
∗
,W
∗
)=rank
˜
A[R
∗
,C
∗
].
We claim that rank
˜
A
αβ
[R
∗
,C
∗
] =1foreach(α, β), where
˜
A
αβ
[R
∗
,C
∗
]is
a short-hand notation for
˜
A
αβ
[R
∗
∩ Row(
˜
A
αβ
),C
∗
∩ Col(
˜
A
αβ
)]. Assume, to
the contrary, that
˜
A
αβ
[R
∗
,C
∗
] has rank 1 for some (α, β). We may further
assume that
˜
A
αβ
[R
∗
,C
∗
] is in the rank normal form, i.e.,
t
αβ
0
00
,
t
αβ
0
,
.
t
αβ
0
/
, or
.
t
αβ
/
,
and that
˜
A
αβ
[R
∗
,C
∗
] has the only nonzero element at (i, j)-entry of
˜
A.Let
˜
A[I
∗
,J
∗
] be a maximum-sized nonsingular submatrix of
˜
A[R
∗
\{i},C
∗
\{j}],
4.8 Partitioned Matrix 245
and then
˜
A[I
∗
∪{i},J
∗
∪{j}] is nonsingular since the nonzero terms aris-
ing from t
αβ
det
˜
A[I
∗
,J
∗
] would not vanish in the determinant expansion of
˜
A[I
∗
∪{i},J
∗
∪{j}] because of the genericity. Therefore we have
rank
˜
A[R
∗
,C
∗
] > rank
˜
A[R
∗
\{i},C
∗
\{j}],
which contradicts the condition (ii) of Lemma 4.8.18. Hence rank
˜
A
αβ
[R
∗
,C
∗
]
is 0 or 2.
Consider a generic matrix B =(b
αβ
) with Row(B)={1, ···,μ} and
Col(B)={1, ···,ν} defined by
b
αβ
=
t
αβ
if rank
˜
A
αβ
[R
∗
,C
∗
]=2,
0ifrank
˜
A
αβ
[R
∗
,C
∗
]=0.
Note the correspondence between the entry b
αβ
of B and the submatrix
A
αβ
of A. The DM-decomposition of B splits R =Row(B)andC =
Col(B) into blocks (
R
0
; R
1
, ···, R
b
; R
∞
) and (C
0
; C
1
, ···, C
b
; C
∞
), respec-
tively. Accordingly, R
∗
and C
∗
are split into blocks (R
∗
0
; R
∗
1
, ···,R
∗
b
; R
∗
∞
)
and (C
∗
0
; C
∗
1
, ···,C
∗
b
; C
∗
∞
), respectively. Since rank
˜
A
αβ
[R
∗
,C
∗
]iseither2or
0, it follows from the genericity that
rank
˜
A[R
∗
,C
∗
]=2rankB.
Moreover,
˜
A[R
∗
,C
∗
] is in a proper block-triangular form with respect to the
blocks (R
∗
0
; R
∗
1
, ···,R
∗
b
; R
∗
∞
) and (C
∗
0
; C
∗
1
, ···,C
∗
b
; C
∗
∞
). For any i ∈ R
∗
\R
∗
∞
,
we would have
rank
˜
A[R
∗
\{i},C
∗
] < rank
˜
A[R
∗
,C
∗
],
which contradicts the condition (ii) in Lemma 4.8.18. Similarly, for any j ∈
C
∗
\ C
∗
0
, we would have
rank
˜
A[R
∗
,C
∗
\{j}] < rank
˜
A[R
∗
,C
∗
],
which also contradicts the condition (ii) in Lemma 4.8.18. Therefore R
∗
= R
∗
∞
and C
∗
= C
∗
0
.Thatistosay,
˜
A[R
∗
,C
∗
]=O, i.e., rank
˜
A[R
∗
,C
∗
]=0.
We now state the main result of this section, namely the rank identity
for GP(2)-matrices, due to Iwata–Murota [144]. This is an extension of the
Hall–Ore theorem for generic matrices.
Theorem 4.8.20. For an m × n GP(2)-matrix A,
rank A = min{p
GP
(W ) | W ∈W
◦
} + n. (4.132)
Hence a proper block-triangular form can be obtained by a GP-transformation.
246 4. Theory and Application of Mixed Matrices
Proof. Let (Y
∗
,W
∗
) be the pair of Theorem 4.8.19. From (ii) it follows that
A
α
W
∗
⊆ Y
∗
∩ U
α
. Using this and (i) we obtain
rank A =dimY
∗
− dim W
∗
+ n
≥
μ
α=1
dim(A
α
W
∗
) − dim W
∗
+ n = p
GP
(W
∗
)+n.
The other direction of the inequality follows from Proposition 4.8.16.
Remark 4.8.21. A compilation of Theorem 4.8.20 and the previous results
show that the rank identity (4.132) holds for the following types of generic
partitioned matrices:
• Generic matrix: m
α
=1forα =1, ···,μ and n
β
=1forβ =1, ···,ν.
• Multilayered matrix: n
β
=1forβ =1, ···,ν.
• Transposed multilayered matrix: m
α
=1forα =1, ···,μ.
• GP(2)-matrix: m
α
≤ 2forα =1, ···,μ and n
β
≤ 2forβ =1, ···,ν.
The second case above is easily seen from Theorem 4.7.6, whereas the third
follows from this with Theorem 4.8.6 and an observation that A has a proper
block-triangular form if and only if the transpose of A does also. The identity
(4.132) is not valid for generic partitioned matrices in general, as illustrated
in the following example. 2
Example 4.8.22. The identity (4.132) is not valid for generic partitioned
matrices in general. Consider a 6 × 6 generic partitioned matrix of type
(3, 3; 2, 2, 2):
A =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
12
t
11
t
13
t
12
t
13
t
22
t
23
t
21
t
23
t
21
t
22
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
It can be easily verified that rank A =5< min p
GP
+ n =6. 2
Example 4.8.23. The block-triangular decomposition of a GP(2)-matrix
depends on the ground field K. Consider, for example, a 4 ×4 GP(2)-matrix
A =
⎡
⎢
⎢
⎣
t
11
t
12
2 t
11
t
12
t
21
t
22
t
21
t
22
⎤
⎥
⎥
⎦
.
If regarded as a GP(2)-matrix with the ground field K = Q, A is GP-
irreducible. If R is the ground field K, on the other hand, the following
block-triangularization of A is obtained:
4.8 Partitioned Matrix 247
˜
A = S
r
−1
AS
c
=
⎡
⎢
⎢
⎣
t
11
−t
12
t
11
t
12
t
21
√
2 t
22
t
21
√
2 t
22
⎤
⎥
⎥
⎦
with
S
r
=
⎡
⎢
⎢
⎣
√
2
√
2
−22
−11
√
2
√
2
⎤
⎥
⎥
⎦
,S
c
=
⎡
⎢
⎢
⎣
√
2
√
2
−11
22
−
√
2
√
2
⎤
⎥
⎥
⎦
.
By using permutation matrices
P
r
=
⎡
⎢
⎢
⎣
1000
0010
0100
0001
⎤
⎥
⎥
⎦
,P
c
=
⎡
⎢
⎢
⎣
1000
0010
0100
0001
⎤
⎥
⎥
⎦
,
we obtain an explicit upper block-triangular (block-diagonal) matrix
¯
A = P
r
˜
AP
c
=
⎡
⎢
⎢
⎣
t
11
−t
12
t
21
√
2 t
22
t
11
t
12
t
21
√
2 t
22
⎤
⎥
⎥
⎦
.
Thus, when K = R, the matrix A is decomposed into a block-triangular
(block-diagonal) form with two square blocks and empty tails. 2
Example 4.8.24. Unlike the CCF of LM-matrices, the partial order among
the blocks is not uniquely determined in the block-triangularization of GP(2)-
matrices. The analysis in §4.8.3 for partitioned matrices carries over, mutatis
mutandis, to generic partitioned matrices. Here is an illustration by means
of an 8 × 8 GP(2)-matrix
A =
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
22
t
23
−2t
23
t
22
t
23
t
32
t
33
−2t
33
t
32
t
33
t
41
t
42
2t
42
t
43
t
44
t
41
2t
42
4t
42
t
43
t
44
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
with the ground field Q. For nonsingular matrices
248 4. Theory and Application of Mixed Matrices
S
r
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
10
01
10
01
10
01
01
10
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,S
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
10
01
10
01
12
01
01
10
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
we have
˜
A = S
r
−1
AS
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
22
t
23
t
22
t
23
t
32
t
33
t
32
t
33
t
41
2t
42
4t
42
t
43
2t
43
t
44
t
41
t
42
2t
42
t
43
2t
43
t
44
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
With suitable permutation matrices P
r
and P
c
, we obtain an explicit upper
block-triangular form
¯
A = P
r
˜
AP
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
41
t
44
2t
42
t
43
4t
42
2t
43
t
41
t
44
t
42
t
43
2t
42
2t
43
t
22
t
23
t
32
t
33
t
22
t
23
t
32
t
33
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Thus
¯
A is a GP-irreducible decomposition of A with empty tails and square
diagonal blocks
¯
A[R
1
,C
1
]=
⎡
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
41
t
44
t
41
t
44
⎤
⎥
⎥
⎦
,
¯
A[R
2
,C
2
]=
t
22
t
23
t
32
t
33
,and
¯
A[R
3
,C
3
]=
t
22
t
23
t
32
t
33
. For another pair of transformation matrices
S
r
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
10
01
1 −2
01
1 −2
01
10
01
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
,S
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
10
01
1 −2
01
10
01
10
01
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
4.8 Partitioned Matrix 249
we have
˜
A
= S
r
−1
AS
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
22
t
23
t
22
t
23
t
32
t
33
t
32
t
33
t
41
t
42
t
43
t
44
t
41
2t
42
t
43
t
44
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
With suitable permutation matrices P
r
and P
c
, we obtain another explicit
upper block-triangular form
¯
A
= P
r
˜
A
P
c
=
⎡
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
41
t
44
t
42
t
43
t
41
t
44
2t
42
t
43
t
22
t
23
t
32
t
33
t
22
t
23
t
32
t
33
⎤
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎥
⎦
.
Thus
¯
A
is another GP-irreducible decomposition of A, which has empty tails
and square diagonal blocks
¯
A
[R
1
,C
1
]=
⎡
⎢
⎢
⎣
t
11
t
14
2t
11
t
14
t
41
t
44
t
41
t
44
⎤
⎥
⎥
⎦
,
¯
A
[R
2
,C
2
]=
t
22
t
23
t
32
t
33
,and
¯
A
[R
3
,C
3
]=
t
22
t
23
t
32
t
33
. The partial orders among the block
in the two block-triangular forms are given by
¯
A :
C
2
C
3
\/
C
1
¯
A
:
C
2
| C
3
C
1
.
2
Notes. This section is a reorganization of the results from Ito–Iwata–Murota
[138] and Iwata–Murota [144]. In particular, Theorems 4.8.6, 4.8.7, 4.8.11,
and 4.8.13, are from Ito–Iwata–Murota [138], and Theorems 4.8.19 and 4.8.20
are from Iwata–Murota [144]. Ito–Iwata–Murota [138] deals also with the
block-triangularization under partition-respecting similarity transformations
with a motivation from the hidden Markov information sources investigated in
Ito [136] and Ito–Amari–Kobayashi [137]. Partition matrices are investigated
also in the context of “Matrix Problem,” though from a different viewpoint
(Gabriel–Roiter [85] and Simson [301]).
250 4. Theory and Application of Mixed Matrices
4.9 Principal Structures of LM-matrices
4.9.1 Motivations
Suppose an engineering system is described by a system of nonlinear equa-
tions
f
i
(x)=0,i∈ R, (4.133)
in a set of variables x =(x
j
| j ∈ C). Then a physical state of the engineering
system is specified by a point x of the manifold (in a loose sense) described
by (4.133). Let A = A(x) denote the Jacobian matrix of f(x) and assume
that rank A = |R| < |C| (for all x in an open set).
If |C|−|R| variables {x
j
| j ∈ C \ J}, where J ⊆ C and |J| = |R|,are
chosen in such a way that the submatrix A[R, J] is nonsingular, the remaining
variables {x
j
| j ∈ J} can be determined uniquely in general by (4.133).
Such variables {x
j
| j ∈ C \ J} are sometimes called design variables in the
engineering literature. Design variables can be regarded as local coordinates of
the manifold described by (4.133) (see Takamatsu–Hashimoto–Tomita [308]).
The choice of design variables is, to some extent, at our disposal. From
a computational point of view, it is advantageous to select a set of design
variables so that the system (4.133) of equations in the remaining dependent
variables may be hierarchically decomposable as fine as possible. Even though
we may not expect an optimal one in this respect, we would like to ask: “How
fine can we decompose the system with a clever choice of design variables?”
Assuming that the Jacobian matrix is an LM-matrix, we shall give a combi-
natorial answer to this question in terms of the horizontal principal structure
of LM-matrices in §4.9.5.
As a second motivation for the same question, suppose we are given a
linear program:
Maximize c
T
x subject to Ax = b, x ≥ 0
with an m × n LM-matrix of rank m as the coefficient matrix A. A basic
solution, corresponding to an m ×m nonsingular submatrix A[R, J] for some
J ⊆ C, is computed by solving A[R, J]x[J]=b and putting x[C \ J]=0.
The submatrix A[R, J] is again an LM-matrix, for which a canonical decom-
position is obtained by the CCF. Furthermore we may be interested in the
family of the decompositions of the submatrices A[R, J] for all possible basic
solutions. Mathematically this leads to the same question as the above on de-
sign variable selection, and a combinatorial answer is given as the horizontal
principal structure of LM-matrices in §4.9.5.
Next, consider a pair of primal and dual linear programs:
(P) Maximize c
T
x subject to Ax ≤ b,
(D) Minimize y
T
b subject to y
T
A = c
T
, y ≥ 0,