Murota K. Matrices and Matroids for Systems Analysis
Подождите немного. Документ загружается.
4.6 Decomposition of Mixed Matrices 211
ˆ
J
∗
k
=(C
Qk
\
ˆ
J
−
k
) ∪
ˆ
J
+
k
=
ˆ
J
Q
k
∪
ˆ
J
+
k
(k =1, 2).
To be specific, ϕ
∗
: R
T
→ C defined by (ϕ
∗
(i),i) ∈ E
∗
M
gives a one-to-one
correspondence between R
T
and C \ (
ˆ
J
∗
1
∪
ˆ
J
∗
2
) such that ϕ
∗
(R
Tk
)=C
k
\
ˆ
J
∗
k
(k =1, 2), and that
τ
k
≡
i∈R
Tk
T
i,ϕ
∗
(i)
=0 (k =1, 2).
We consider the term τ
1
· τ
2
in det A. By the Laplace expansion of det A
with A of (4.84) we see that the coefficient c
∗
∈ K of τ
1
·τ
2
in det A is given
by
c
∗
= det Q[R
Q
,
ˆ
J
∗
1
∪
ˆ
J
∗
2
].
For the determinant on the right-hand side we have
det Q[R
Q
,
ˆ
J
∗
1
∪
ˆ
J
∗
2
] = det Q[
ˆ
I
−
,
ˆ
J
+
] = det Q[
ˆ
I
−
1
,
ˆ
J
+
1
] · det Q[
ˆ
I
−
2
,
ˆ
J
+
2
]+α,
where the first equality follows from
Q[R
Q
,
ˆ
J
∗
1
∪
ˆ
J
∗
2
]=
ˆ
J
Q
1
ˆ
J
+
1
ˆ
J
Q
2
ˆ
J
+
2
ˆ
I
Q
1
IQ[∗] OQ[∗]
ˆ
I
−
1
OQ[1, 1] OQ[1, 2]
ˆ
I
Q
2
OQ[∗] IQ[∗]
ˆ
I
−
2
OQ[2, 1] OQ[2, 2]
and (4.85), and the second equality from (4.83). Therefore,
c
∗
= det Q[
ˆ
I
−
1
,
ˆ
J
+
1
] · det Q[
ˆ
I
−
2
,
ˆ
J
+
2
]+α. (4.86)
On the other hand, since τ
k
is contained in det A[R
k
,C
k
] with the coeffi-
cient equal to Q[
ˆ
I
−
k
,
ˆ
J
+
k
]fork =1, 2, the expression (4.76) requires that
c
∗
= det Q[
ˆ
I
−
1
,
ˆ
J
+
1
] · det Q[
ˆ
I
−
2
,
ˆ
J
+
2
]. (4.87)
Thus we are led to two contradictory expressions, (4.86) and (4.87), for c
∗
.
This completes the proof of Theorem 4.5.6.
Notes. This section is based on Murota [207] and Murota [218].
4.6 Decomposition of Mixed Matrices
The decomposition of LM-matrices has been established by the CCF in §4.4.
The decomposition of general mixed matrices is considered in this section.
212 4. Theory and Application of Mixed Matrices
4.6.1 LU-decomposition of Invertible Mixed Matrices
We investigate here the invertibility of a mixed matrix A = Q + T in K[T ]
(=the ring of polynomials in the nonvanishing entries T of T over K). More
specifically, we are interested in whether we can compute A
−1
by means of
pivot operations in K[T ] and also in how simple we can make the LU-factors
of A by applying suitable permutations to the rows and columns.
Let A = Q + T be a square mixed matrix, A ∈ MM(K, F ; n, n), which we
regard as a matrix over K[T ]. Recall a well-known fact that A is invertible
in K[T ], i.e., A
−1
∈ K[T ], if and only if det A ∈ K
∗
(= K \{0}). By way of
illustration of our problem we start with an example.
Example 4.6.1. A matrix
A =
12345
1 −11101
2 10x 10
3 01101
4 y −110−1
5 110z 0
is a mixed matrix, A = Q + T ∈ MM(K, F ;5, 5) for K = Q and F =
Q(x, y, z) with
Q =
12345
1 −11101
2 10010
3 01101
4 0 −110−1
5 11000
,T=
12345
1 00000
2 00x 00
3 00000
4 y 0000
5 000z 0
,
if T = {x, y, z} is algebraically independent over Q. Note that det A =2
and hence A is invertible in Q[x, y, z]. The matrix A is decomposed into
LU-factors in Q(x, y, z)asA = LU with
L =
⎡
⎢
⎢
⎢
⎢
⎣
10 0 0 0
−11 0 0 0
01 1 0 0
−yy− 1 y − 1 − 2/x 10
−12 2+1/x −(xz +1)/21
⎤
⎥
⎥
⎥
⎥
⎦
,U=
⎡
⎢
⎢
⎢
⎢
⎣
−11 1 0 1
01x +1 1 1
00−x −10
00 0 −2/x 0
00 0 0 −1
⎤
⎥
⎥
⎥
⎥
⎦
.
Observe that some of the entries of L and U do not belong to Q[x, y, z
].
However, after rearranging the rows and the columns of A as
P
r
AP
c
=
52431
1 1101−1
5 01z 01
2 001x 1
4 −1 −101y
3 11010
,
4.6 Decomposition of Mixed Matrices 213
we have the LU-decomposition P
r
AP
c
= LU with
L =
⎡
⎢
⎢
⎢
⎢
⎣
10000
01000
00100
−10010
10001
⎤
⎥
⎥
⎥
⎥
⎦
,U=
⎡
⎢
⎢
⎢
⎢
⎣
1101−1
01z 01
001x 1
0002y − 1
00001
⎤
⎥
⎥
⎥
⎥
⎦
.
These LU-factors are much simpler in the sense that all the entries of L are
numbers in Q and consequently the entries of U are polynomials in x, y,and
z over Q of degree at most one. 2
In the following, we establish a theorem (Theorem 4.6.4) stating that it is
always possible to find permutations of rows and columns through which an
invertible matrix A can be brought to a form decomposable into LU-factors
with the L-factor being a matrix over K. Furthermore, we show how to find
suitable permutations.
First, a necessary and sufficient condition for the invertibility of a mixed
matrix is given. A matrix is said to be strictly upper triangular if it is an
upper triangular matrix with zero diagonals.
Theorem 4.6.2. A square mixed matrix A = Q + T ∈ MM(K, F ; n, n) is
invertible in K[T ],ifandonlyifdet Q =0and P
c
T
(Q
−1
T )P
c
is strictly
upper triangular for some permutation matrix P
c
.
Proof. Firstly suppose that P
c
T
(Q
−1
T )P
c
is strictly upper triangular for some
permutation matrix P
c
. Then, since det Q =0andA = Q + T ,wehave
det A = det[Q(I + Q
−1
T )] = det Q · det[I + P
c
T
(Q
−1
T )P
c
] = det Q ∈ K
∗
.
Conversely, if det A ∈ K
∗
, then det Q = det A =0.PutS = Q
−1
. Suppose
that P
c
T
(Q
−1
T )P
c
= P
c
T
(ST)P
c
is not strictly upper triangular for any
permutation matrix P
c
. Then ST has a cycle of nonzero entries, that is,
there exist an integer M ≥ 1 and a sequence of indices i(m)andj(m)(m =
1, ···,M) such that S
j(m),i(m)
=0andT
i(m),j(m+1)
=0form =1, ···,M,
where j(M +1)=j(1). Choose M to be the minimum of such integers. We
write S
j(m),i(m)
= s
m
and T
i(m),j(m+1)
= t
m
.
For k =0, 1, ···, consider the expression of the (j(1),i(1)) entry of
(ST)
kM
S in the form of the sum of products of S
ji
’s and T
ij
’s. Corresponding
to the above cycle, it contains a term
s
1
(s
1
s
2
···s
M
)
k
· (t
1
t
2
···t
M
)
k
,
since no other similar terms of (t
1
t
2
···t
M
)
k
exist due to the minimality of
M and since it cannot be canceled out by nonsimilar terms by virtue of the
algebraic independence of T .
214 4. Theory and Application of Mixed Matrices
Next we formally expand A
−1
as
1
A
−1
=[Q(I + Q
−1
T )]
−1
= S − STS + STSTS −··· .
Each entry of A
−1
on the left-hand side is a polynomial in T over K since A
is invertible. On the right-hand side, the (j(1),i(1)) entry contains a term of
arbitrarily high degree, since the nonzero term (t
1
t
2
···t
M
)
k
of degree kM,
stemming from (ST)
kM
S, as above, cannot be canceled out for k =0, 1, ···.
This is a contradiction.
Example 4.6.3. For the matrix A = Q + T in Example 4.6.1, we have
det Q =2and
P
c
T
(Q
−1
T )P
c
=
5243 1
5 00−z 0 −y/2
2 00z 00
4 000x 0
3 0000y/2
1 0000 0
,
which is strictly upper triangular. 2
We now state the theorem of LU-decomposition of mixed matrices due to
Murota [198].
Theorem 4.6.4. A square mixed matrix A = Q + T ∈ MM(K, F ; n, n) is
invertible in K[T ], if and only if there exist permutation matrices P
r
and P
c
,
an n×n matrix L =(L
ij
) over K and an n×n matrix U =(U
ij
) over F such
that (i) P
r
AP
c
= LU, (ii) L
ij
=0for i<j and L
ii
=1for i =1, ···,n,
and (iii) U
ij
=0for i>j, U
ii
∈ K
∗
,andU
ij
is a polynomial of degree at
most one in T over K.
Proof. It suffices to prove the “only if” part. Let P
c
be the permutation
matrix in Theorem 4.6.2 for which P
c
T
(Q
−1
T )P
c
is strictly upper triangular.
Since det Q = 0, a standard result on the LU-decomposition or the Gaussian
elimination (cf., e.g., Gantmacher [87], Golub–Van Loan [97]) shows that
there exist a permutation matrix P
r
, a lower triangular matrix with unit
diagonals L ∈ GL(n, K), and a nonsingular upper triangular matrix V ∈
GL(n, K) such that P
r
QP
c
= LV. Then we obtain
P
r
AP
c
= P
r
(Q + T )P
c
=(P
r
QP
c
)[I + P
c
T
(Q
−1
T )P
c
]
=(LV)[I + P
c
T
(Q
−1
T )P
c
]=LU
with U = V [I + P
c
T
(Q
−1
T )P
c
], which is an upper triangular matrix. Obvi-
ously L is a matrix over K, and consequently the entries of U = L
−1
P
r
AP
c
are polynomials in T of degree at most one.
1
This expansion converges for sufficiently small absolute values of T .
4.6 Decomposition of Mixed Matrices 215
Remark 4.6.5. In Theorem 4.6.4 the assumption of algebraic independence
of T as a whole cannot be weakened to element-wise transcendency of the
members of T . Consider, e.g., A =
1+xx
−x 1 − x
, which can be expressed
as A = Q + T with Q =
10
01
and T =
xx
−x −x
. Although det A =1and
each entry of T is transcendental over Q, there exists no LU-decomposition
with the L-factor over Q. 2
Given a mixed matrix A ∈ MM(K, F ; n, n), we can test for its invertibil-
ity with O(n
3
) arithmetic operations in K on the basis of Theorem 4.6.2:
first compute Q
−1
by elimination operations in K, then determine the
zero/nonzero pattern of Q
−1
T by boolean operations and finally check for the
acyclicity of the graph associated with Q
−1
T as defined in §2.2.1. This proce-
dure simultaneously provides the permutation matrix P
c
. In this connection
we may recall Theorem 4.2.17, which shows how an invertible submatrix can
be extracted.
Theorem 4.6.4 reads that if A ∈ MM(K, F ; n, n) is invertible, it can
be brought to an upper triangular form U over F by a transformation
(L
−1
P
r
) AP
c
= U with L ∈ GL(n, K) and permutation matrices P
r
and
P
c
. In the next subsection we will consider the problem of reducing a general
mixed matrix A ∈ MM(K, F ; m, n) to an upper block-triangular form by a
transformation SAP with S ∈ GL(m, K) and a permutation matrix P .
4.6.2 Block-triangularization of General Mixed Matrices
We consider a block-triangularization of a mixed matrix A = Q + T ∈
MM(K, F ; m, n) under a transformation of the form
ˆ
A = SAP, (4.88)
where S ∈ GL(m, K)andP is a permutation matrix. For a proper block-
triangularization (in the sense of §2.1.4) the following conditions are re-
quired of
ˆ
A and of partitions (
ˆ
R
0
;
ˆ
R
1
, ···,
ˆ
R
ˆ
b
;
ˆ
R
∞
) and (
ˆ
C
0
;
ˆ
C
1
, ···,
ˆ
C
ˆ
b
;
ˆ
C
∞
)
of Row(
ˆ
A) and Col(
ˆ
A):
ˆ
R
k
= ∅,
ˆ
C
k
= ∅ (k =1, ···,
ˆ
b);
ˆ
R
0
,
ˆ
R
∞
,
ˆ
C
0
,
ˆ
C
∞
canbeempty,
ˆ
A[
ˆ
R
k
,
ˆ
C
l
]=O if 0 ≤ l<k≤∞,
rank
ˆ
A[
ˆ
R
0
,
ˆ
C
0
]=|
ˆ
R
0
| (< |
ˆ
C
0
| if
ˆ
R
0
= ∅),
rank
ˆ
A[
ˆ
R
k
,
ˆ
C
k
]=|
ˆ
R
k
| = |
ˆ
C
k
| > 0fork =1, ···,
ˆ
b,
rank
ˆ
A[
ˆ
R
∞
,
ˆ
C
∞
]=|
ˆ
C
∞
| (< |
ˆ
R
∞
| if
ˆ
C
∞
= ∅).
Note that the existence of such
ˆ
A is by no means obvious and that the trans-
formed matrix
ˆ
A =(SQP)+(STP) no longer belongs to MM(K, F ; m, n)
216 4. Theory and Application of Mixed Matrices
in general. Roughly speaking, such
ˆ
A can be constructed as an aggregation
of the CCF of the associated LM-matrix.
Let
˜
A ∈ LM(K, F ; m, m, m + n) be the LM-matrix associated with A
in the sense of (4.4). Putting R =Row(A)andC = Col(A), we identify
˜
C = Col(
˜
A) with R ∪C through a one-to-one correspondence ψ : R ∪C →
˜
C.
Let ˜ρ, ˜γ, ˜p :2
˜
C
→ Z be the functions associated with
˜
A by (4.13), (4.9), and
(4.16).
Recalling that the CCF of
˜
A is obtained (cf. §4.4.3) from the lattice
L
min
(˜p)(⊆ 2
˜
C
) of the minimizers of the LM-surplus function ˜p, we consider
here a subfamily of L
min
(˜p) defined by
ˆ
L = {X ∈L
min
(˜p) | I ⊇
ˆ
Γ (R, J)forI = ψ
−1
(X) ∩ R, J = ψ
−1
(X) ∩ C},
(4.89)
where
ˆ
Γ (R, J)={i ∈ R |∃j ∈ J : T
ij
=0},J⊆ C.
Lemma 4.6.6.
ˆ
L = ∅ and
ˆ
L is a sublattice of L
min
(˜p).
Proof.ForX ∈L
min
(˜p), put I = ψ
−1
(X) ∩ R and J = ψ
−1
(X) ∩ C,and
define I
= I ∪
ˆ
Γ (R, J)andX
= ψ(I
∪ J) ⊇ X. Since ˜γ(X
)=˜γ(X),
˜ρ(X
) ≤ ˜ρ(X)+|I
\ I|,and|X
| = |X| + |I
\ I|,wehave˜p(X
) ≤ ˜p(X),
which shows X
∈L
min
(˜p). If X is the maximum element of L
min
(˜p), we must
have X
= X, i.e., I ⊇
ˆ
Γ (R, J), which means X ∈
ˆ
L, and therefore
ˆ
L = ∅.
It follows from Lemma 2.2.16 that L
0
= {X ⊆
˜
C | I ⊇
ˆ
Γ (R, J)forI =
ψ
−1
(X) ∩ R, J = ψ
−1
(X) ∩ C} forms a sublattice of 2
˜
C
. Hence
ˆ
L = L
0
∩
L
min
(˜p) is a sublattice of L
min
(˜p).
By Lemma 4.6.6 above and Birkhoff’s representation theorem (Theo-
rem 2.2.10),
ˆ
L determines a partition of
˜
C which is an aggregation of
the one induced by L
min
(˜p). Accordingly (cf. §4.4.3),
ˆ
L induces a block-
triangularization, coarser than the CCF, of the LM-matrix
˜
A under a trans-
formation (4.35) with S ∈ GL(m, K) and permutation matrices P
r
and P
c
.
We shall see that this matrix S gives the desired transformation in
ˆ
A = SAP.
Let
¯
A = P
r
S
I
m
I
m
Q
−I
m
T
P
c
be the block-triangular matrix induced by
ˆ
L,andlet(
¯
R
0
;
¯
R
1
, ···,
¯
R
b
;
¯
R
∞
)
and (
¯
C
0
;
¯
C
1
, ···,
¯
C
b
;
¯
C
∞
) be the associated partitions of Row(
¯
A) and Col(
¯
A).
Then we have
¯
A[
¯
R
k
,
¯
C
l
]=O for l<k. (4.90)
Define
¯
Q = S[ I
m
| Q ],
¯
T =[−I
m
| T ]
so that
¯
A = P
r
¯
Q
¯
T
P
c
.
4.6 Decomposition of Mixed Matrices 217
Note that
S =
¯
Q[Row(
¯
Q),ψ(R)], (4.91)
where ψ is regarded as ψ : R∪C → Col(
¯
Q) through the natural identification
of Col(
¯
Q) with
˜
C; similarly for Col(
¯
T ). From the identity
OSA
−I
m
T
=
I
m
S
OI
m
S
I
m
I
m
Q
−I
m
T
=
¯
Q + S
¯
T
¯
T
we see that
SA =(
¯
Q + S
¯
T )[Row(
¯
Q),ψ(C)]. (4.92)
For k =0, 1, ···,b,∞, put
¯
R
Qk
=Row(
¯
Q) ∩
¯
R
k
and
¯
R
Tk
=Row(
¯
T ) ∩
¯
R
k
,
where Row(
¯
A) is identified with Row(
¯
Q) ∪Row(
¯
T ) through the permutation
P
r
. Similarly, Col(
¯
A) is identified with Col(
¯
Q) (= Col(
¯
T )) through the per-
mutation P
c
. By the condition I ⊇
ˆ
Γ (R, J) in the definition of
ˆ
L and the
construction of the CCF (cf. (4.54) in particular), it holds that
ψ(
¯
R
Tk
)=
¯
C
k
∩ ψ(R). (4.93)
Hence the diagonal submatrix
¯
A[
¯
R
k
,
¯
C
k
] is of the following form:
¯
A[
¯
R
k
,
¯
C
k
]=
¯
C
k
∩ ψ(R)
¯
C
k
∩ ψ(C)
¯
R
Qk
Q
1k
Q
2k
¯
R
Tk
−IT
k
,
that is, the submatrix
¯
A[
¯
R
Tk
,
¯
C
k
∩ ψ(R)] is equal to −I (the negative of an
identity matrix).
We now claim
(
¯
Q + S
¯
T )[
¯
R
Qk
,
¯
C
l
∩ ψ(C)] = O for l<k. (4.94)
To show this, first note from (4.90) that
¯
Q[
¯
R
Qk
,
¯
C
l
∩ ψ(C)] = O,
¯
T [
¯
R
Tk
,
¯
C
l
∩ ψ(C)] = O for l<k.
Then we have
(S
¯
T )[
¯
R
Qk
,
¯
C
l
∩ ψ(C)] =
j
S[
¯
R
Qk
,
¯
R
Tj
] ·
¯
T [
¯
R
Tj
,
¯
C
l
∩ ψ(C)]
=
j
¯
Q[
¯
R
Qk
,
¯
C
j
∩ ψ(R)] ·
¯
T [
¯
R
Tj
,
¯
C
l
∩ ψ(C)] = O
with the aid of (4.91) and (4.93). Thus the claim (4.94) is proven.
Noting that |
¯
R
Qk
| = |
¯
C
k
∩ψ(C)| for k =1, ···,b, define {
ˆ
R
l
| l =1, ···,
ˆ
b}
to be the family of nonempty blocks among {
¯
R
Qk
| k =1, ···,b} and likewise
218 4. Theory and Application of Mixed Matrices
{
ˆ
C
l
| l =1, ···,
ˆ
b} to be the family of nonempty blocks among {
¯
C
k
∩ ψ(C) |
k =1, ···,b}. Also define
ˆ
R
0
=
¯
R
Q0
,
ˆ
R
∞
=
¯
R
Q∞
,
ˆ
C
0
=
¯
C
0
∩ ψ(C),
ˆ
C
∞
=
¯
C
∞
∩ ψ(C).
The expressions (4.92) and (4.94) show that
(SA)[
ˆ
R
k
,
ˆ
C
l
]=O if 0 ≤ l<k≤∞, (4.95)
namely, the matrix SA is block-triangularized with respect to the partitions
(
ˆ
R
0
;
ˆ
R
1
, ···,
ˆ
R
ˆ
b
;
ˆ
R
∞
) and (
ˆ
C
0
;
ˆ
C
1
, ···,
ˆ
C
ˆ
b
;
ˆ
C
∞
). Hence,
ˆ
A = SAP with some
permutation matrix P is explicitly block-triangularized. Denote by the
partial order on {
ˆ
C
0
;
ˆ
C
1
, ···,
ˆ
C
ˆ
b
;
ˆ
C
∞
} that is induced from the partial order
defined by
ˆ
L on {
¯
C
0
;
¯
C
1
, ···,
¯
C
b
;
¯
C
∞
}.
Example 4.6.7. The construction explained above is illustrated for a mixed
matrix A ∈ MM(Q, F ;5, 5):
A =
x
1
x
2
x
3
x
4
x
5
w
1
11t
1
1 t
2
w
2
−1 −11t
3
0
w
3
00t
4
t
5
t
6
w
4
00001
w
5
t
7
t
8
000
,
where t
i
(i =1, ···, 8) are indeterminates over Q and F = Q(t
1
, ···,t
8
). By
the CCF of the associated LM-matrix
˜
A ∈ LM(Q, F ;5, 5, 10) we see that
¯
A = P
r
SO
OI
5
I
5
Q
−I
5
T
P
c
=
←−
¯
C
1
−→ ←−
¯
C
2
−→
¯
C
3
¯
C
4
← C
1
→ C
2
←− C
3
−→ C
4
C
5
C
6
x
1
x
2
w
5
w
1
w
2
x
3
x
4
w
3
x
5
w
4
r
1
11 11
w
5
t
7
t
8
−1
r
2
1
r
3
1111
w
1
−10t
1
0 t
2
w
2
0 −10 t
3
w
3
00t
4
t
5
−1 t
6
r
4
1
r
5
1 1
w
4
−1
,
where
4.6 Decomposition of Mixed Matrices 219
S =
⎡
⎢
⎢
⎢
⎢
⎣
10000
00001
11000
00100
00010
⎤
⎥
⎥
⎥
⎥
⎦
.
In the CCF of
˜
A, the column set Col(
˜
A), identified with {w
1
, ···,w
5
}∪
{x
1
, ···,x
5
}, is divided into six (nonempty) blocks:
C
1
= {x
1
,x
2
},C
2
= {w
5
},C
3
= {w
1
,w
2
,x
3
,x
4
},C
4
= {w
3
},
C
5
= {x
5
},C
6
= {w
4
} (C
0
= C
∞
= ∅)
with the partial order being the transitive closure of the relations:
C
1
C
2
; C
3
C
4
; C
1
C
3
C
5
C
6
.
This corresponds to the lattice L
min
(˜p).
The sublattice
ˆ
L of (4.89), on the other hand, yields a coarser partition
consisting of four blocks:
¯
C
1
= {x
1
,x
2
,w
5
},
¯
C
2
= {x
3
,x
4
,w
1
,w
2
,w
3
},
¯
C
3
= {x
5
},
¯
C
4
= {w
4
}
with
¯
C
1
¯
C
2
¯
C
3
¯
C
4
, where
¯
C
0
=
¯
C
∞
= ∅. Namely,
ˆ
L = {∅,
¯
C
1
,
¯
C
1
∪
¯
C
2
,
¯
C
1
∪
¯
C
2
∪
¯
C
3
,
¯
C
1
∪
¯
C
2
∪
¯
C
3
∪
¯
C
4
}. Note, for example, that
¯
C
1
= C
1
∪C
2
∈
L
min
(˜p), and I = ψ
−1
(
¯
C
1
) ∩ R = {w
5
},andJ = ψ
−1
(
¯
C
1
) ∩ C = {x
1
,x
2
}
satisfy the condition I ⊇
ˆ
Γ (R, J).
Finally, for the partition of Col(A), we obtain
ˆ
C
1
= {x
1
,x
2
},
ˆ
C
2
= {x
3
,x
4
},
ˆ
C
3
= {x
5
}
with the partial order
ˆ
C
1
ˆ
C
2
ˆ
C
3
, where
ˆ
C
0
=
ˆ
C
∞
= ∅. Accordingly, the
following block-triangular form is obtained:
SAP =
ˆ
C
1
ˆ
C
2
ˆ
C
3
x
1
x
2
x
3
x
4
x
5
r
1
11 t
1
1 t
2
r
2
t
7
t
8
r
3
t
1
+1t
3
+1 t
2
r
4
t
4
t
5
t
6
r
5
1
,
where P = I
5
. 2
The theorem on the block-triangularization of a general mixed matrix is
now stated.
Theorem 4.6.8. The matrix
ˆ
A as well as partitions (
ˆ
R
0
;
ˆ
R
1
, ···,
ˆ
R
ˆ
b
;
ˆ
R
∞
)
and (
ˆ
C
0
;
ˆ
C
1
, ···,
ˆ
C
ˆ
b
;
ˆ
C
∞
) constructed above gives a proper block-triangular
form, having the following properties.
220 4. Theory and Application of Mixed Matrices
(1)
ˆ
A is block-triangularized, i.e.,
ˆ
A[
ˆ
R
k
,
ˆ
C
l
]=O if 0 ≤ l<k≤∞. (4.96)
Moreover, the partial order on {
ˆ
C
1
, ···,
ˆ
C
ˆ
b
} induced by the zero/nonzero
structure of
ˆ
A agrees with the partial order defined from
ˆ
L; i.e.,
ˆ
A[
ˆ
R
k
,
ˆ
C
l
]=O unless
ˆ
C
k
ˆ
C
l
(1 ≤ k, l ≤
ˆ
b);
ˆ
A[
ˆ
R
k
,
ˆ
C
l
] = O if
ˆ
C
k
≺·
ˆ
C
l
(1 ≤ k, l ≤
ˆ
b).
(2)
rank
ˆ
A[
ˆ
R
0
,
ˆ
C
0
]=|
ˆ
R
0
| (< |
ˆ
C
0
| if
ˆ
R
0
= ∅),
rank
ˆ
A[
ˆ
R
k
,
ˆ
C
k
]=|
ˆ
R
k
| = |
ˆ
C
k
| > 0fork =1, ···,
ˆ
b,
rank
ˆ
A[
ˆ
R
∞
,
ˆ
C
∞
]=|
ˆ
C
∞
| (< |
ˆ
R
∞
| if
ˆ
C
∞
= ∅).
(3)
ˆ
A is the finest proper block-triangular matrix (“proper” in the sense
of §2.1.4) among those obtained by a transformation of the form (4.88).
Proof. (1)–(2) The claim (4.96) has been shown in (4.95). The other claims in
(1) and (2) can be proven similarly to the corresponding claims in Theorem
4.4.4.
(3) Suppose that there exist S ∈ GL(m, K), W ⊆ R
S
≡ Row(S), and
J ⊆ C such that
(SA)[R
S
\ W, J ]=O, (4.97)
rank (SA)[W, J ]=|W |,
rank (SA)[R
S
\ W, C \ J]=|C \ J|.
This means
rank A =rankSA = n −|J| + |W |,
which implies by Theorem 4.2.5 that
min ˜p =rank
˜
A − (m + n)=rankA − n = |W |−|J|. (4.98)
To show that
ˆ
A is the finest proper block-triangularization, it suffices to
prove that X = ψ(I ∪ J) ∈L
min
(˜p)forI =
ˆ
Γ (R, J), which implies X ∈
ˆ
L.
By the algebraic independence of T , (4.97) is equivalent to
(SQ)[R
S
\ W, J ]=O, (ST)[R
S
\ W, J ]=O. (4.99)
Moreover, the latter condition is further equivalent, again by the algebraic
independence of T ,to
S[R
S
\ W, I]=O. (4.100)
From the first of (4.99) and (4.100), we see that
˜ρ(X) = rank (I
m
| Q)[R, X] = rank (S(I
m
| Q))[R
S
,X] ≤|W |. (4.101)