4.2 Rank of Mixed Matrices 141
Theorem 4.2.13 (K¨onig–Egerv´ary theorem for mixed matrix). Let
A = Q + T be a mixed matrix. Then there exist I ⊆ R and J ⊆ C such that
(i) |I|+ |J|−rank Q[I,J]=|R| + |C|−rank A,
(ii) rank T [I,J]=0.
Proof.Take(I,J) that attains the minimum on the right-hand side of (4.23).
Remark 4.2.14. Theorem 4.2.13 is a refinement of the previous result of
Hartfiel–Loewy [102] for a square mixed matrix, named the “determinan-
tal version of the Frobenius–K¨onig theorem,” and its extension to a general
rectangular mixed matrix by Murota [218]. The original proof of Hartfiel–
Loewy (for the square case) was quite involved, based on factorizations of
determinants. 2
Remark 4.2.15. As is naturally expected, the K¨onig–Egerv´ary-type result
(Theorem 4.2.13) is equivalent to the rank formula (4.23), under an obvious
inequality
rank A ≤ rank A[R, J]+rankA[R, C \ J]
≤ rank A[I,J]+rankA[R \ I,J]+rankA[R, C \J]
≤ rank Q[I,J]+|R \ I|+ |C \ J|
valid for (I,J) with T [I,J]=O (i.e., with I ∩
ˆ
Γ (R, J)=∅).
Furthermore, it is pointed out by Bapat [9] that Theorem 4.2.13 can be
proved independently of the rank formula using a fundamental property of a
general bimatroid. By Theorem 2.3.47 (applied to the bimatroid associated
with A), there exist I ⊆ R and J ⊆ C such that
(i) |I| + |J
|−rank A[I,J]=|R| + |C|−rank A,
(ii) rank A[I \{i},J \{j}]=rankA[I,J], ∀i ∈ I, ∀j ∈ J.
We claim that (ii) implies T [I,J]=O. Suppose, to the contrary, that T
ij
=0
for some i ∈ I and j ∈ J. Since rank A[I \{i},J \{j}]=rankA[I,J](=:r),
there exist I
⊆ I \{i} and J
⊆ J \{j} such that rank A[I
,J
]=|I
| =
|J
| = r. Consider the Laplace expansion of det A[I
∪{i},J
∪{j}]. It contains
a nonvanishing term T
ij
· det A[I
,J
], which is not cancelled out by virtue
of the algebraic independence of the nonzero entries of T . This implies a
contradiction that r =rankA[I,J] ≥ rank A[I
∪{i},J
∪{j}]=|I
| +1=
r +1. 2
Remark 4.2.16. When numerical values are substituted into the nonzero
entries of the T -part of a mixed matrix, the rank of the resulting numerical
matrix can possibly decrease. On the basis of Theorem 4.2.13 a systematic
procedure has been given by Geelen [92] that assigns numerical values so that
the rank remains the same. 2
Finally we mention the following fact in connection with the basic rank
identity (4.20).