(ver. 4:. 2005-07-27) 1 1.1 (mixed matrix) (layered mixed matrix, LM-matrix) m n A = Q T (2m) (m n) ( ) ( ) Q I m Q à = = (1) T diag [t 1,, t m ] T rank à = m rank A (2) 1.2 [ ] B rank [B C] rank B rank C, rank rank B rank C. (3) C 2 2.1 1 A = ( ) Q T rank A = max{rank Q[R Q, J] t-rank T [R T, C \ J] J C}. (4) R Q Q R T T C A 1
T rank A max{rank Q[R Q, J] t-rank T [R T, C \ J] J C} 2 ([1, p.138, Theorem 4.2.5]) A = ( ) Q rank A = min{ρ(j) γ(j) J J C} C, (5) ρ(j) = rank Q[R Q, J], J C, Γ(J) = {i R T j J : T ij 0}, J C, γ(j) = Γ(J), J C. (5) min( ) J C rank A ρ(j) γ(j) J C. = J C rank A ρ(j) γ(j) J C. = J T 1 A = x 1 x 2 x 3 x 4 x 5 1 1 1 1 0 0 2 1 1 0 f 1 t 1 0 0 0 t 2 f 2 0 t 3 0 0 t 4 (6) C = {x 1, x 2, x 3, x 4, x 5 }, R T = {f 1, f 2 }. rank A = 4 J = {x 1, x 3 } (4) 2 2 = 4 J = {x 3, x 4 } (5) 1 0 2 5 = 4 2.2 1 Laplace 1 ([1, p.136, Lemma 4.2.1]) A = ( ) Q T J C Q[R Q, J], T [R T, C \ J] ( ) Laplace det A = J C, J = R Q ± det Q[R Q, J] det T [R T, C \ J] det A 0 J det Q[R Q, J] 0 det T [R T, C \ J] 0. 2
J 0 Q[R Q, J 0 ] T [R T, C \J 0 ] det T [R T, C \J 0 ] t 1 t 2 t k ( k = R T ) T J t 1 t 2 t k det Q[R Q, J 0 ] 0 det A 0. 1 1 A r = rank A r A R, C ( R = C = r) A A = ( ) Q T Q I Q T I T 1 J C Q[I Q, J], T [I T, C \ J] J = rank Q[I Q, J] rank Q[R Q, J], C \ J = t-rank T [I T, C \ J] t-rank T [R T, C \ J] rank A = r = C rank Q[R Q, J] t-rank T [R T, C \ J]. (4) rank A max{ }. (4) J Q[R Q, J], T [R T, C \ J] I Q R Q, J Q J, I T R T, J T C \ J I Q = J Q = rank Q[I Q, J Q ] = rank Q[R Q, J], I T = J T = t-rank T [I T, J T ] = t-rank T [R T, C \ J]. 1 A[I Q I T, J Q J T ] rank A[I Q I T, J Q J T ] = J Q J T. rank A rank A[I Q I T, J Q J T ] = J Q J T = rank Q[R Q, J] t-rank T [R T, C \ J] = max{ }. 2.3 2 rank A rank A[R, J] rank A[R, C \ J] rank A[R Q, J] rank A[R T, J] rank A[R, C \ J] = rank Q[R Q, J] rank T [R T, J] rank A[R, C \ J] ρ(j) γ(j) C \ J. rank Q[R Q, J] = ρ(j), rank T [R T, J] ( ) = γ(j), rank A[R, C \ J] ( ) = C \ J. 3
2.4 2 2.4.1 1. (a) (b) ( ) primal (c) dual 2. Q = Q = 3. (a) Q (b) primal = (c) rank A ρ(j) γ(j) J C J dual = 1 4. 2.4.2 G = (R T C Q, C; ). C Q = {j Q j C} C (j C j Q C Q ), = {(i, j) i R T, j C, T ij 0}, = {(j Q, j) j C}. M M M R T C Q C M M M = 2 M M Q C (M ) Q 1 rank A 1 Q M(Q) C Q C Q M M(Q) 4
R T C C Q x 1 f 1 x 2 x 1Q x 2Q x 3 x 3Q f 2 x 4 x 4Q x 5 x 5Q 1: Graph G ( : arc in a maximum independent matching M) 2 ([1, p.143, Theorem 4.2.18]) M rank A[R, C M] = M. rank A M. rank A = max{ M M }. ( ) J Q = C (M ), J T = C (M ) J Q J T = C M rank Q[R Q, J Q ] = J Q, t-rank T [R T, J T ] = J T. 1 rank A[R, J Q J T ] = J Q J T = M. M rank A 1 2 1 A = x 1 x 2 x 3 x 4 x 5 1 1 1 1 0 0 2 1 1 0 f 1 t 1 0 0 0 t 2 f 2 0 t 3 0 0 t 4 1 C = {x 1, x 2, x 3, x 4, x 5 }, C Q = {x 1Q, x 2Q, x 3Q, x 4Q, x 5Q }, R T = {f 1, f 2 }. M = {(f 1, x 5 ), (f 2, x 2 ), (x 1Q, x 1 ), (x 3Q, x 3 )}. rank A = M = 4 J = C (M ) = {x 1, x 3 } (4) 1 2 (7) (7) 2.4.3 M G = G M Ṽ = R T C Q C Ẽ = E M M M 5
M C R T C Q 3 2 E Q ( M(Q) ) I = C (M ), (8) J = {j C \ I rank Q[R Q, I {j}] = I } (9) rank Q[R Q, I] = I E i I, j J (i Q, j Q ) E I i j Q (10) E C Q S S S = (R T \ M) {j Q C Q j C \ (I J)}, S = C \ M S S 2.4.4 2.4.5 Q P I, J, S, E P I P Q C I Z J = {j C \ I P ij = 0 ( i Z)}, E = {(i Q, j Q ) i I, j J, P ij 0} (11) P = I J K i 1 i 2 i 3 i 4 i 5 i 6 j 1 j 2 j 3 j 4 k 1 k 2 k 3 i 1 1 0 0 0 0 0 e e e e i 2 0 1 0 0 0 0 e e e e I i 3 0 0 1 0 0 0 e e e e i 4 0 0 0 1 0 0 e e e e i 5 0 0 0 0 1 0 e e e e i 6 0 0 0 0 0 1 e e e e z 1 0 0 0 0 0 0 0 0 0 0 s s s Z z 2 0 0 0 0 0 0 0 0 0 0 s s s z 3 0 0 0 0 0 0 0 0 0 0 s s s z 4 0 0 0 0 0 0 0 0 0 0 s s s (12) e E K = C \ (I J) s C Q C Q S = {j Q C Q j K} 4 3 2 (7) M = {(f 2, x 2 ), (x 3Q, x 3 )} 2 P = x 1 x 2 x 3 x 4 x 5 1 1 1 1 0 1 1 0 0 0 6
f 1 R T C C Q f 2 x 1 x 2 x 3 x 4 x 5 x 1Q x 2Q x 3Q E x 4Q x 5Q 2: Graph G for an independent matching M ( : arc in M; : vertex in S ; : vertex in S ) S = {f 1, x 1Q, x 2Q }, S = {x 1, x 4, x 5 } (8) I = {x 3 }, (9) J = {x 4, x 5 }. 2 2 (7) M = {(f 1, x 1 ), (x 2Q, x 2 ), (x 4Q, x 4 )} 2.4.4 E (i Q, j Q ) E = I i j Q (10) I (8) E R T E (i 1Q, j 1Q ),..., (i kq, j kq ) I = (I \ {i 1,..., i k }) {j 1,..., j k } Q (i p, j q ) (p < q) (k = 4 ) e 0 s I Q ( no-short cut lemma [1, p.83, Lemma 2.3.22]). {i 1, i 2, i 3, i 4 }, {j 1, j 2, j 3, j 4 } 7
P = I i 1 i 2 i 3 i 4 j 1 j 2 j 3 j 4 i 1 1 0 0 0 0 0 e 0 s 0 s 0 s i 2 0 1 0 0 0 0 e 0 s 0 s i 3 0 0 1 0 0 0 e 0 s i 4 0 0 0 1 0 0 e 0 0 0 0 1 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 I (13) 2.4.5 S S S W J = W C 3 J 1. W S, W S =. 2. C C Q W (j W j Q W ) 3 J rank A ρ(j) γ(j) J C ( ). ( ) I T = W R T C J Q = J (M ) (Q J ) J T = J (M ) (T J ) K Q = (C \ J) (M ) (Q J ) K T = (C \ J) (M ) (T J ) Q J C \ J S C M S J Q J T K Q K T J Q I O 1 ρ(j) K Q O 2 O 1 O 2 I O 3 O 1 O 3 O 1 Q K I T T J γ(j) R T O 4 O 4 O 4 T K S R T O 4 O 4 O 4 (14) 1. T J, T K T 8
S R T C C Q I T J K T K Q J T J Q S W S 3: Graph G with no path from S to S ( : arc in M) 2. Q J Q K Q O 1. 3. C Q \ W C Q W C Q \ W {j Q C Q j K Q } (K Q C Q ) C Q W J C Q O 2. 4. W S = J C Q (, j J j Q S C Q ) O 3 2 5. R T \ W (= R T \ I T ) J O 4. 6. M 2 rank A[R, C M] = C M. 7. O 2, O 3 ρ(j) = J Q. 8. O 4 T J Γ(J) = I T γ(j) = I T = J T. rank A rank A[R, C M] = C M = J Q J T C \ J = ρ(j) γ(j) C \ J. 2 4 2 1 M = {(f 1, x 5 ), (f 2, x 2 ), (x 1Q, x 1 ), (x 3Q, x 3 )} 4 P = x 1 x 2 x 3 x 4 x 5 1 1 0 0 0 0 2 1 1 0 2 K T Q S C Q j K T j Q C Q Q K j 9
R T C C Q f 1 f 2 x 1 x 2 x 3 x 4 x 1Q x 2Q E x 3Q x 4Q x 5 x 5Q W 4: Graph G for a maximum independent matching M ( : arc in M; S =, : vertex in S, vertex in W is reachable to S ) S = {x 4 } W = {x 3, x 4, x 3Q, x 4Q }J = W C = {x 3, x 4 } J (5) 3 I T =, J T =, J Q = {x 3 }, K Q = {x 1 }, K T = {x 2, x 5 } 3 1 W 2.5 2 Edmonds Hall Ore (1985 4 ) τ : 2 C Z: τ(j) = t-rank T [R T, J], J C, γ : 2 C Z Hall Ore τ(j) = min{γ(k) K K J} J, J C. (15) (Hall Ore Edmonds 1 A, Q, T C M(A), M(Q), M(T ) 1. A M(A) rank A = rank M(A). 2. Q, T M(Q), M(T ), ρ, τ M(Q), M(T ) 10
3. 1 M(A) M(Q) M(T ) M(A) = M(Q) M(T ). 4. Edmonds rank (M(Q) M(T )) = min{ρ(j) τ(j) J J C} C. (16) 2 (5) rank A = rank M(A) = rank (M(Q) M(T )) = min{ρ(j) τ(j) J J C} C J = min{ρ(j) min{γ(k) K K J} J C} C J K = min {min {ρ(j) J K} γ(k) K K C} C K J = min{ρ(k) γ(k) K K C} C. K 4 rank A = min{ρ(j) τ(j) J J C} C (17) (5) 3 3.1 3 A = Q T rank A = max{rank Q[I, J] t-rank T [R \ I, C \ J] I R, J C}. (18) 4 ([1, p.141, Theorem 4.2.13]) A = QT I R, J C (i) I J rank Q[I, J] = R C rank A, (ii) rank T [I, J] = 0. rank T [I, J] = 0 I J rank Q[I, J] R C rank A. = I R, J C rank T [I, J] = 0 I J rank Q[I, J] R C rank A. = 2 11
3.2 3 1 4 ([1, p.139, Lemma 4.2.7]) A = Q T I R, J C Q[I, J], T [R \ I, C \ J] ( ) det A = det(q T ) = ± det Q[I, J] det T [R \ I, C \ J]. I R J C det A 0 I, J det Q[I, J] 0 det T [R \ I, C \ J] 0. I 0, J 0 Q[I 0, J 0 ] T [R \ I 0, C \ J 0 ] det T [R \ I 0, C \J 0 ] t 1 t 2 t k ( k = R\I 0 ) T (I, J) t 1 t 2 t k det Q[I 0, J 0 ] 0 det A 0. 3.3 4 T [I, J] = O rank A rank A[R, J] rank A[R, C \ J] rank A[I, J] rank A[R \ I, J] rank A[R, C \ J] rank Q[I, J] R \ I C \ J. 3.4 4 2 4 A = Q T Ã 2 J R C I = R \ J, J = C J (1) ρ( J) = rank Q[I, J] R \ I (2) I Γ(J) = (3) rank T [I, J] = 0 (4) I J rank Q[I, J] R C rank A 3.5 4 2 A = ( ) ( Q T A = Q ) ( O O ) T 4 (i), (ii) (I, J) 12
(1) I R Q (2) ρ(j) = rank Q[I, J] (3) γ(j) R \ I (4) rank A ρ(j) γ(j) J C 4 [1, 4.2.4]. Algorithm for computing the rank of an LM-matrix A Step 1: Step 2: Step 3: M := ; base[i] := 0 (i R Q ); P [i, j] := Q ij (i R Q, j C); S := unit matrix of order m Q. I := {i C i Q M C Q }; J := {j C \ I h : base[h] = 0 P [h, j] = 0}; S T := R T \ M ; S := S T S Q ; S := C \ M ; S Q := {j Q C Q j C \ (I J)}; E := {(i Q, j Q ) h R Q, j J, P [h, j] 0, i = base[h] 0}; [Ẽ is updated accordingly] If there exists in G = (Ṽ, Ẽ) a directed path from S to S then go to Step 3; otherwise (including the case where S = or S = ) stop with the conclusion that rank A = M. Let L ( Ẽ) be (the set of arcs on) a shortest path from S to S ( shortest in the number of arcs); M := (M \ L) {(j, i) (i, j) L } {(j, j Q ) (j Q, j) L }; If the initial vertex ( S ) of the path L belongs to S Q, then do the following: {Let j Q ( S Q C Q) be the initial vertex; Find h such that base[h] = 0 and P [h, j] 0; base[h] := j; w := 1/P [h, j]; P [k, l] := P [k, l] w P [k, j] P [h, l] [j C corresponds to j Q C Q ] (k R Q \ {h}, l C \ {j}); S[k, l] := S[k, l] w P [k, j] S[h, l] (k R Q \ {h}, l R Q ); P [k, j] := 0 (k R Q \ {h}) }; 13
f 1 f 2 R T C C Q x 1 x 2 x 3 x 4 x 5 x 1Q x 2Q x 3Q x 4Q x 5Q 5: Graph G (0) (: vertex in S ; : vertex in S ) For all (i Q, j Q ) L E (in the order from S to S along L) do the following: {Find h such that i = base[h]; [j C corresponds to j Q C Q ] base[h] := j; w := 1/P [h, j]; P [k, l] := P [k, l] w P [k, j] P [h, l] (k R Q \ {h}, l C \ {j}); S[k, l] := S[k, l] w P [k, j] S[h, l] (k R Q \ {h}, l R Q ); P [k, j] := 0 (k R Q \ {h}) }; Go to Step 2. 5 2 Step 1: M := ; base := r 1 0 r 2 0, P := x 1 x 2 x 3 x 4 x 5 r 1 1 1 1 1 0 r 2 0 2 1 1 0, S := 1 0 0 1. Step 2: I := ; J := {x 5 }; S T := {f 1, f 2 }; S Q := {x 1Q, x 2Q, x 3Q, x 4Q }; S := {f 1, f 2, x 1Q, x 2Q, x 3Q, x 4Q }; S := {x 1, x 2, x 3, x 4, x 5 }; E := ; There exists a path from S to S. [ = G (0), 5] Step 3: L := {(x 1Q, x 1 )}; M := {(x 1, x 1Q )}; 14
f 1 f 2 R T C C Q x 1 x 2 x 3 x 4 x 5 x 1Q x 2Q x 3Q x 4Q x 5Q 6: Graph G (1) ( : arc in M; : vertex in S ; : vertex in S ) The initial vertex x 1Q of L is in S Q, and the matrices are updated (with h = r 1) to base := r 1 x 1 r 2 0, P := x 1 x 2 x 3 x 4 x 5 r 1 1 1 1 1 0 r 2 0 2 1 1 0, S := 1 0 0 1. Noting L E = we return to Step 2. Step 2: I := {x 1 }; J := {x 5 }; S T := {f 1, f 2 }; S Q := {x 2Q, x 3Q, x 4Q }; S := {f 1, f 2, x 2Q, x 3Q, x 4Q }; S := {x 2, x 3, x 4, x 5 }; E := ; There exists a path from S to S. [ = G (1), 6] Step 3: L := {(x 2Q, x 2 )}; M := {(x 1, x 1Q ), (x 2, x 2Q )}; The initial vertex x 2Q of L is in S Q, and the matrices are updated (with h = r 2) to base := r 1 x 1 r 2 x 2, P := x 1 x 2 x 3 x 4 x 5 r 1 1 0 1/2 1/2 0 r 2 0 2 1 1 0, S := 1 1/2 0 1. Noting L E = we return to Step 2. Step 2: I := {x 1, x 2 }; J := {x 3, x 4, x 5 }; S T := {f 1, f 2 }; S Q := ; S := {f 1, f 2 }; S := {x 3, x 4, x 5 }; E := {(x 1Q, x 3Q ), (x 1Q, x 4Q ), (x 2Q, x 3Q ), (x 2Q, x 4Q )}; There exists a path from S to S. [ = G (2), 7] 15
f 1 f 2 R T C C Q x 1 x 2 x 3 x 4 x 5 x 1Q x 2Q x E 3Q x 4Q x 5Q 7: Graph G (2) ( : arc in M; : vertex in S ; : vertex in S ) R T C C Q f 1 x 2 f 2 x 1 x 3 x 4 x 5 x 1Q x 2Q x E 3Q x 4Q x 5Q 8: Graph G (3) ( : arc in M; : vertex in S ; : vertex in S ) Step 3: L := {(f 1, x 5 )}; M := {(x 1, x 1Q ), (x 2, x 2Q ), (x 5, f 1 )}; The initial vertex f 1 S Q and L E =, and therefore the matrices remain unchanged and we return to Step 2. Step 2: I := {x 1, x 2 }; J := {x 3, x 4, x 5 }; S T := {f 2}; S Q := ; S := {f 2 }; S := {x 3, x 4 }; E := {(x 1Q, x 3Q ), (x 1Q, x 4Q ), (x 2Q, x 3Q ), (x 2Q, x 4Q )}; There exists a path from S to S. [ = G (3), 8] Step 3: L := {(f 2, x 2 ), (x 2, x 2Q ), (x 2Q, x 3Q ), (x 3Q, x 3 )}; M := {(x 1, x 1Q ), (x 3, x 3Q ), (x 5, f 1 ), (x 2, f 2 )}; 16
R T C C Q f 1 f 2 x 1 x 2 x 3 x 4 x 1Q x 2Q x E 3Q x 4Q x 5 x 5Q 9: Graph G (4) ( : arc in M; S =, : vertex in S ) The initial vertex f 2 S Q and L E = {(x 2Q, x 3Q )}, and the matrices are updated (with h = r 2 ) to base := r 1 x 1 r 2 x 3, P := x 1 x 2 x 3 x 4 x 5 r 1 1 1 0 0 0 r 2 0 2 1 1 0, S := 1 1 0 1. Step 2: I := {x 1, x 3 }; J := {x 2, x 4, x 5 }; S T := ; S Q := ; S := ; S := {x 4 }; E := {(x 1Q, x 2Q ), (x 3Q, x 2Q ), (x 3Q, x 4Q )}; There exists no path from S (= ) to S ; We stop with the conclusion that rank A = M = 4. [ = G (4), 9] [1] K. Murota: Matrices and Matroids for Systems Analysis, Springer-Verlag, Berlin, 2000. 6 256 17