Murota K. Matrices and Matroids for Systems Analysis
Подождите немного. Документ загружается.
422 7. Further Topics
Theorem 7.2.4. Let τ be the transition index of a bimatroid A with Row(A)
= Col(A).Then
RM(A
0
)
→
=
RM(A
1
)
→
=
···
→
=
RM(A
τ−1
)
→
=
RM(A
τ
)=RM(A
k
),k≥ τ +1,
CM(A
0
)
→
=
CM(A
1
)
→
=
···
→
=
CM(A
τ−1
)
→
=
CM(A
τ
)=CM(A
k
),k≥ τ +1,
where M
1
→
=
M
2
means that M
2
is a strong quotient of, and not isomorphic
to, M
1
.
Proof. It follows from Theorem 2.3.59 that RM(A
k
) → RM(A
k+1
)and
CM(A
k
) → CM(A
k+1
). Combining these with Theorem 7.2.3(2) and
Lemma 2.3.1, we establish the theorem.
Based on Theorem 7.2.3 we can define a set of characteristic indices
(ω
0
; ω
1
,ω
2
, ···)ofA by
ω
0
= r(A
∞
),
ω
k
= r(A
k+1
)+r(A
k−1
) − 2r(A
k
),k=1, 2, ···,
where ω
k
≥ 0(k =0, 1, ···). Note that ω
k
=0fork>τ and that
ω
0
+
τ
k=1
kω
k
= |S|.
In the particular case where A = L(A) with a square generic matrix A
having independent nonzero entries, this set of indices (ω
0
; ω
1
,ω
2
, ···) deter-
mines the Jordan canonical form of the matrix A. Motivated by this we call
(ω
0
; ω
1
,ω
2
, ···)theJordan type of a bimatroid A.
Remark 7.2.5. Theorems 7.2.3 and 7.2.4 are motivated by similar phenom-
ena for matrix products A
k
, k =0, 1, 2, ···. The same inequalities as in The-
orem 7.2.3 hold true for the sequence rank A
k
, k =0, 1, 2, ···, with τ being
the maximum size of a Jordan block for a zero eigenvalue. The strong map
sequence of Theorem 7.2.4 corresponds to the nesting structure of subspaces:
Im(A
0
)
⊃
=
Im(A
1
)
⊃
=
···
⊃
=
Im(A
τ−1
)
⊃
=
Im(A
τ
)=Im(A
k
),k≥ τ +1.
Recall from Example 2.3.8 that the strong map relation may be interpreted
as a combinatorial abstraction of the nesting of linear subspaces. 2
7.2.3 Eigensets and Recurrent Sets
In this section we study eigensets and recurrent sets of a bimatroid, intro-
duced by Murota [202, 211]. A subset X ⊆ S is said to be an eigenset of a
bimatroid A =(S, S, Λ(A)) if (X, X) ∈ Λ(A), and a recurrent set of A if
(X, X) ∈ Λ(A
k
) for some k ≥ 1. By definition, an eigenset is a recurrent set,
but the converse is not true in general.
7.2 Combinatorial System Theory 423
Eigensets of a bimatroid may be regarded as a combinatorial analogue of
eigenvectors of a matrix as follows. Let A be a matrix and A the correspond-
ing bimatroid, both having S as the row set and the column set. Just as we
think of A as a mapping in R
S
we may regard A as a (multivalued) mapping
in 2
S
, where it is kept in mind that X ∈ 2
S
can be expressed alternatively
by its characteristic vector χ
X
∈ R
S
. A vector x ∈ R
S
is an eigenvector of
A if it is invariant in direction when transformed by A. In parallel, a subset
X ∈ 2
S
or its characteristic vector χ
X
is an eigenset of A if it can be kept
invariant when transformed by A.
We denote by EIG(A) the family of eigensets of A, and by max-EIG(A)
that of maximum-sized eigensets of A. Similarly, we denote by REC(A)the
family of recurrent sets of A, and by max-REC(A) that of maximum-sized
recurrent sets of A.
Example 7.2.6. For illustration, let us consider the bimatroid A defined by
a matrix
x
1
x
2
x
3
x
1
111
x
2
112
x
3
111
.
Writing X → Y instead of (X, Y ) ∈ Λ(A), we have {x
1
,x
2
}→{x
1
,x
3
},
{x
1
,x
2
}→{x
2
,x
3
}, {x
2
,x
3
}→{x
1
,x
3
}, {x
2
,x
3
}→{x
2
,x
3
}; {x
i
}→{x
j
}
for i, j =1, 2, 3, and ∅→∅. Hence,
EIG(A)=REC(A)={{x
2
,x
3
}, {x
1
}, {x
2
}, {x
3
}, ∅},
max-EIG(A) = max-REC(A)={{x
2
,x
3
}}.
This example shows that a maximal recurrent set is not necessarily a
maximum-sized recurrent set, nor is a maximal eigenset a maximum eigenset.
In fact, the singleton set {x
1
} is maximal and not maximum. 2
We first consider recurrent sets of maximum size.
Theorem 7.2.7. Let A be a bimatroid with Row(A) = Col(A) and k ≥
τ(A) (=the transition index). Then
max-REC(A) = max-EIG(A
k
) = max RM(A
∞
) ∩ max CM(A
∞
),
where max RM(A
∞
) denotes the family of bases (=maximum-sized inde-
pendent sets) of RM(A
∞
), and similarly for max CM(A
∞
); accordingly,
the right-most term means the family of common bases of RM(A
∞
) and
CM(A
∞
).
Proof. Suppose X ∈ REC(A). Then (X, X) ∈ Λ(A
k
) for some k ≥ 1. This
implies that (X, X) ∈ Λ(A
km
) for any m. Choosing m so that km ≥ τ,we
see X is independent both in RM(A
∞
)andCM(A
∞
), cf. Theorem 7.2.4.
424 7. Further Topics
If X is a common base of RM(A
∞
)andCM(A
∞
)andk ≥ τ, then
(X, Y ) ∈ Λ(A
k
) and (Z, X) ∈ Λ(A
k
) for some Y and Z. It then follows from
the property (L-3) of a bimatroid that (X
,X
) ∈ Λ(A
k
) for some X
⊇ X
and X
⊇ X.WemusthaveX
= X
= X since |X| =rank(A
k
). Hence
X ∈ EIG(A
k
) ⊆ REC(A).
The claim of the theorem follows from the above argument.
Theorem 7.2.8. REC(A) is a hereditary family. That is, if Y ⊆ X ∈
REC(A), then Y ∈ REC(A).
Proof. The proof consists of three steps (i)–(iii). The assertion of the theorem
follows from the claim in (iii) by induction.
(i) First we claim: x ∈ X ∈ EIG(A) ⇒{x}∈REC(A). By Theo-
rem 2.3.44(1), there is a permutation σ of X such that ({x}, {σ(x)}) ∈ Λ(A).
For each x ∈ X there exists k ≥ 1 such that σ
k
(x)=x. This implies that
({x}, {x}) ∈ Λ(A
k
). Hence {x}∈REC(A).
(ii) Next we claim: x ∈ X ∈ EIG(A) ⇒ X \{x}∈REC(A). Since
(X, X) ∈ Λ(A), A[X, X] is a nonsingular bimatroid. Put A
= A[X, X]
−1
(the inverse bimatroid; see §2.3). Then X ∈ EIG(A
). The first claim implies
that, for each x ∈ X there exists a sequence x
0
(= x),x
1
, ···,x
k
(= x)
in X such that ({x
i
}, {x
i−1
}) ∈ Λ(A
)fori =1, ···,k. This is equivalent
to (X
i−1
,X
i
) ∈ Λ(A[X, X]), with X
i
= X \{x
i
} for i =1, ···,k. Hence
(X \{x},X \{x}) ∈ Λ(A
k
), establishing the claim.
(iii) We finally claim: x ∈ X ∈ REC(A) ⇒ X \{x}∈REC(A). Since
X ∈ EIG(A
k
) for some k ≥ 1, we see X \{x}∈REC(A
k
) by the second
claim above. This implies X \{x}∈REC(A).
Remark 7.2.9. By the proof of Theorem 7.2.7, a recurrent set of A is a
common independent set of RM(A
∞
)andCM(A
∞
). The converse, however,
is not true in general, since an arbitrary common independent set cannot
always be augmented to a common base. For a concrete instance, consider
the bimatroid A defined by a matrix
x
1
x
2
x
3
x
1
110
x
2
001
x
3
001
and the singleton set {x
2
}. This is not a recurrent set, though it is indepen-
dent both in RM(A
∞
)andCM(A
∞
). 2
Remark 7.2.10. The family of eigensets is not necessarily hereditary. For
the bimatroid A defined by a matrix
x
1
x
2
x
1
01
x
2
10
7.2 Combinatorial System Theory 425
we have EIG(A)={{x
1
,x
2
}, ∅}. 2
Our next result shows that the maximum size of a recurrent set coincides
with that of an eigenset. Since an eigenset is a “static” concept that does
not involve dynamics, we may say that the formula below gives a “static”
characterization of the limit of the dynamics, lim
k→∞
r(A
k
).
Theorem 7.2.11. For a bimatroid A with Row(A) = Col(A),
max{|X||X ∈ EIG(A)} = max{|X||X ∈ REC(A)} = r(A
∞
).
Proof. By Theorem 7.2.7 as well as the obvious inclusion EIG(A) ⊆ REC(A),
we see
max{|X||X ∈ EIG(A)}≤max{|X||X ∈ REC(A)} = r(A
∞
).
The inequality here is an equality by the following lemma.
Lemma 7.2.12. If X is a recurrent set of maximum size and x ∈ X, then
there exists an eigenset Y such that x ∈ Y and |X| = |Y |.
Proof. We denote by S
−
and S
+
two disjoint copies of S =Row(A) = Col(A).
For X ⊆ S we compatibly denote by X
−
and X
+
the copies of X in S
−
and
S
+
, respectively.
Consider two matroids M
A
=(S
−
∪ S
+
, B
A
)andM
0
=(S
−
∪ S
+
, B
0
)
with the base families
B
A
= {(S
−
\X
−
)∪Y
+
| (X, Y ) ∈ Λ(A)}, B
0
= {(S
−
\X
−
)∪Y
+
| X = Y },
where M
A
is the matroid associated with A by (2.86). It is easy to see that
X ∈ EIG(A) ⇐⇒ (S
−
\ X
−
) ∪ X
+
∈B
A
⇐⇒ ∃H ∈B
A
∩B
0
: X
+
= H ∩S
+
.
Let B
A
⊆ R
S
−
∪S
+
denote the convex hull of the characteristic vectors χ
H
of H ∈B
A
, and define B
0
⊆ R
S
−
∪S
+
similarly from B
0
.
For X ∈ max-REC(A), there exist X
i
(i =0, 1, ···,k) with X
0
= X
k
= X
such that (X
i−1
,X
i
) ∈ Λ(A)fori =1, ···,k. This means that
[(χ
S
)
−
− (χ
X
i−1
)
−
] ⊕ (χ
X
i
)
+
∈ B
A
,i=1, 2, ···,k,
where for a vector ξ ∈ R
S
in general we write ξ
−
and ξ
+
for the corresponding
vectors in R
S
−
and R
S
+
, respectively. Taking the average of these expressions
and putting μ =
k
i=1
χ
X
i
/k, we obtain
¯
h =[(χ
S
)
−
− μ
−
] ⊕ μ
+
∈ B
A
∩ B
0
.
We also have
¯
h(S
+
)=|X| = r(A
∞
). This shows that max{h(S
+
) | h ∈
B
A
∩ B
0
} = r(A
∞
) and that
¯
h attains the maximum.
426 7. Further Topics
By the integrality of matroid intersection, B
A
∩ B
0
is the convex hull of
the characteristic vectors of common bases of M
A
and M
0
. In particular, we
can express
¯
h as a convex combination
¯
h =
m
j=1
c
j
h
j
,
m
j=1
c
j
=1,c
j
> 0(j =1, ···,m)
of such incidence vectors h
j
= χ
H
j
(j =1, ···,m) with h
j
(S
+
)=r(A
∞
).
Note that H
j
∈B
A
∩B
0
is equivalent to H
j
=(S
−
\ Z
j
−
) ∪ Z
j
+
for some
Z
j
∈ EIG(A), and that h
j
(S
+
)=|Z
j
| = r(A
∞
). Since x ∈ X,wehave
¯
h(x
+
) > 0. This implies that h
j
(x
+
) > 0 for some j, i.e., x ∈ Z
j
for some j.
This Z
j
gives the desired Y .
Remark 7.2.13. A recurrent set of maximum size is not necessarily an
eigenset, i.e., max-REC(A) = max-EIG(A). For the bimatroid A defined
by a matrix
x
1
x
2
x
3
x
4
x
5
x
1
00100
x
2
00010
x
3
01001
x
4
00100
x
5
10000
it can be verified that max-EIG(A)={{x
1
,x
3
,x
5
}, {x
2
,x
3
,x
4
}} and
max-REC(A) = max-EIG(A) ∪{{x
1
,x
2
,x
3
}, {x
3
,x
4
,x
5
}}. 2
Remark 7.2.14. Theorem 7.2.11 does not imply
max{|X||rank A[X, X]=|X|,X ⊆ S} = lim
k→∞
rank (A
k
) (7.39)
for a numerical matrix A with Row(A) = Col(A)=S because of the possi-
ble discrepancy between matrix multiplication and bimatroid multiplication
(cf. Remark 2.3.54). In fact, A =
11
−1 −1
serves as a counterexample to
(7.39). The equality (7.39) is true, however, if the nonzero entries of A are al-
gebraically independent, which fact follows from the combination of Theorem
7.2.11 with Theorem 7.2.2. 2
7.2.4 Controllability of Combinatorial Dynamical Systems
This section gives a number of controllability criteria for a CDS (A, B).
Before stating the general results, it is worth while explaining the relation
between the structural controllability and the controllability of a CDS in a
typical situation.
Consider a conventional dynamical system (7.34) described by matrices A
and B, with which we can associate a CDS (A, B) under the correspondence:
7.2 Combinatorial System Theory 427
A = L(A), B = L(B). In the special case where the matrices A and B
are generic (“structured” in the sense of §6.4.2), the associated bimatroids
A and B can be represented by matchings in bipartite graphs. In this case
the associated CDS (A, B) is controllable if and only if there exists in the
dynamic graph G
n
0
of the system (7.34) a Menger-type vertex-disjoint linking
of size n from U
n−1
0
to X
n
(see §2.2.1 or §6.4.2 for the definitions of G
n
0
, U
n−1
0
,
and X
n
). Theorem 6.4.3 then reveals that a “structured” system (A, B)is
controllable in the ordinary sense if and only if the associated CDS (A, B)
is controllable. It is noted at the same time that the controllability of the
associated CDS (A, B) is only necessary for general numerical matrices A
and B.
For the controllability criteria we shall investigate the structure of the
sequence {RS
k
(∅)}
k
, i.e., the sequence of those sets which are reachable at
time k from the empty set (cf. (7.36)). As the following theorem claims,
RS
k
(∅) forms the family of independent sets of a matroid, denoted by R
k
,
and the sequence {R
k
}
k
is determined by a recurrence relation. The matroid
R
k
will be referred to as the reachability matroid.
Theorem 7.2.15. For each k (≥ 0), RS
k
(∅) of (7.36) forms the family of
independent sets of a matroid R
k
. The matroids are determined by
R
k
=(A ∗ R
k−1
) ∨ RM(B),k=1, 2, ···,
where R
0
is a trivial matroid (of rank zero), A ∗R
k−1
is the matroid induced
from R
k−1
by A,and∨ means the matroid union.
Proof. We prove the claims by induction on k. Assume that RS
k−1
(∅) defines
a matroid R
k−1
. It follows from the state-space equation (7.35) that X
k
∈
RS
k
(∅) if and only if X
k
= X
k
∪ X
k
, X
k
∩ X
k
= ∅,(X
k
,X
k−1
) ∈ Λ(A),
(X
k
,U
k−1
) ∈ Λ(B), and X
k−1
∈ RS
k−1
(∅) for some X
k
, X
k
, X
k−1
,and
U
k−1
. The latter condition can be rephrased that X
k
= X
k
∪X
k
, X
k
∩X
k
= ∅
for some independent set X
k
of A ∗ R
k−1
and some independent set X
k
of
RM(B). Note that, by the induction assumption, the notation A ∗ R
k−1
makes sense to mean the matroid induced from R
k−1
by A. Hence RS
k
(∅)
forms the family of independent sets of the union of A ∗ R
k−1
and RM(B).
Theorem 7.2.15 motivates us to investigate a sequence of matroids subject
to a recurrence relation. The following general theorem proven in Murota
[206] reveals some fundamental properties of the reachability matroids, where
we choose N = RM(B).
Theorem 7.2.16. Let A =(S, S, α) be a bimatroid with birank function α,
and N =(S, ν) be a matroid with rank function ν. Define a sequence of
matroids R
k
by the recurrence relation
R
k
=(A ∗ R
k−1
) ∨ N,k=1, 2, ···, (7.40)
428 7. Further Topics
starting with a trivial matroid R
0
on S.
(1) r(R
k
) − r(R
k−1
) ≥ r(R
k+1
) − r(R
k
),k=1, 2, ···.
(2) There exists κ = κ(A, N)(≥ 0) such that
r(R
0
) <r(R
1
) < ···<r(R
κ−1
) <r(R
κ
)=r(R
k
),k= κ +1,κ+2, ···.
(3) R
0
←
=
R
1
←
=
···
←
=
R
κ−1
←
=
R
κ
= R
k
,k= κ +1,κ+2, ···,
where R
k
←
=
R
k+1
means that R
k
is a strong quotient of, and not isomorphic
to, R
k+1
.
Proof.LetS
(i)
(i =0, 1, 2, ···) be disjoint copies of S, and denote by A
(i)
=
(S
(i)
,S
(i−1)
,α
(i)
)andN
(i)
=(S
(i)
,ν
(i)
)(i =0, 1, 2, ···) the bimatroids and
matroids that are isomorphic to A and N, respectively. Denote by M
(i)
the
dual of the matroid associated with A
(i)
by (2.86); S
(i)
∪S
(i−1)
is the ground
set of M
(i)
, and (X, Y ) ∈ Λ(A
(i)
) if and only if X ∪ (S
(i−1)
\Y )isabaseof
M
(i)
. Furthermore, define a matroid
G
j,k
=
⎛
⎝
k
"
i=j+1
M
(i)
⎞
⎠
∨
⎛
⎝
k
"
i=j
N
(i)
⎞
⎠
,
the ground set of which is
k
i=j
S
(i)
. It is straightforward to verify that R
k
(G
1,k
)
S
(k)
(=the contraction of G
1,k
to S
(k)
) and that
r(R
k
)=r(G
1,k
) − (k − 1)|S|, (7.41)
since
k−1
i=1
S
(i)
, being a base of
!
k
i=2
M
(i)
, is independent in G
1,k
.
Proposition 2.3.40 applied to a triple (M
(2)
∨N
(1)
, G
2,k
, M
(k+1)
∨N
(k+1)
)
yields
r(G
1,k+1
)+r(G
2,k
) ≤ r(G
1,k
)+r(G
2,k+1
).
Noting G
2,k
G
1,k−1
and G
2,k+1
G
1,k
and using (7.41), we obtain the
desired inequality in (1).
The strong map relation R
k
← R
k+1
follows from the expressions
R
k
(G
2,k+1
)
S
(k+1)
, R
k+1
([M
(2)
∨ N
(1)
] ∨ G
2,k+1
)
S
(k+1)
,
and Theorem 2.3.41. Hence, r(R
k
) ≤ r(R
k+1
), k =0, 1, 2, ···.Letκ be the
smallest k (> 0) such that the equality holds. Then (1) implies that the
equality must hold for all k ≥ κ, establishing (2). Finally recall Lemma 2.3.1
to obtain the assertion of (3).
The strong map relation for R
k
shows that the reachable part grows
with time to a matroid R
κ
, denoted also as R
∞
. Compare this with the
similar phenomenon for the conventional system (7.34) that the controllable
subspaces R
k
=Im[B | AB | A
2
B |···|A
k−1
B] increase with k, where A and
B are numerical matrices. In this connection recall from Example 2.3.8 that
7.2 Combinatorial System Theory 429
the strong map relation may be interpreted as a combinatorial abstraction of
the nesting of linear subspaces.
The ultimate rank r(R
κ
), i.e., r(R
∞
), of the sequence {R
k
}
k
defined by
the recurrence relation (7.40) admits a “static” characterization, as follows.
Recall that A[X, X] denotes the restriction of A to (X, X), and N[X]the
restriction of N to X.
Theorem 7.2.17. Let A =(S, S, α), N =(S, ν),and{R
k
}
k
be as in The-
orem 7.2.16. If
α(X, S \ X)+ν(X) ≥ 1, ∅ = ∀X ⊆ S,
it holds that
rank (R
∞
) = max{|X||rank
.
A[X, X] ∨ N[X]
/
= |X|,X⊆ S}.
Proof. See Murota [206].
By specializing the above theorem to the case of N = RM(B), we obtain
a formula for the ultimate rank of the reachability matroid of a CDS (A, B),
which is called the controllable dimension. This result is a generalization of
Theorem 6.4.5.
Corollary 7.2.18. If a CDS (A, B) is reachable (i.e., {x}∈RS(∅) for all
x ∈ S), the controllable dimension is given by
rank (R
∞
) = max{|X||rank
.
A[X, X] ∨ B[X, P ]
/
= |X|,X⊆ S}. (7.42)
Proof. With Theorem 7.2.17 it suffices to show that the reachability of (A, B)
is equivalent to
α(X, S \ X)+β(X, P) ≥ 1, ∅ = ∀X ⊆ S,
where α and β are the birank functions of A and B.
The formula (7.42) yields the following controllability criteria shown in
Murota [206].
Theorem 7.2.19. ForaCDS(A, B), the following three conditions are
equivalent:
(i) (A, B) is controllable;
(ii) (A, B) is reachable, and RM(A) ∨ RM(B) is the free matroid;
(iii) (A, B) is reachable, and there exists a state feedback F such that
A ∨ (B ∗ F) is a nonsingular bimatroid.
Proof. First note that reachability is necessary for controllability; so we as-
sume reachability. By definition, controllability is equivalent to rank (R
∞
)=
|S|. On the other hand, the expression of rank (R
∞
) in Corollary 7.2.18 shows
that rank (R
∞
)=|S| if and only if rank (A ∨ B)=|S|. Hence follows the
430 7. Further Topics
equivalence of (i) and (ii), since rank (A ∨ B) = rank (RM(A) ∨ RM(B)).
The equivalence of (ii) and (iii) is easy to show. Assume (iii), i.e., that
(S, S) ∈ Λ(A ∨ (B ∗ F)) for some F. This is equivalent to saying that there
exist X, X
⊆ S,andU ⊆ P such that (X
,X) ∈ Λ(A), (S \ X
,U) ∈ Λ(B),
and (U, S \ X) ∈ Λ(F). Hence S = X
∪ (S \ X
) is independent in
RM(A) ∨RM(B), showing (ii). Similarly we can show that (ii) implies (iii),
by choosing F to be the “free” bimatroid, in which every pair is a linked pair.
Remark 7.2.20. Compare the second criterion (ii) in Theorem 7.2.19 with
the structural controllability theorem (Theorem 6.4.2). Note that, in case of
A = L(A), B = L(B) with generic matrices A and B, RM(A) ∨ RM(B)is
the free matroid if and only if term-rank [A | B]=n. 2
The integer κ = κ(A, B)(0≤ κ ≤ n = |S|) in Theorem 7.2.16 for N =
RM(B) is called the controllability index of the CDS (A, B). The inequalities
in (1) and (2) show that Δr
k
= r(R
k
) − r(R
k−1
),k=1, 2, ···,forma
nonnegative and nonincreasing sequence that vanishes for k>κ. This enables
us to define a set of nonnegative indices {κ
i
} by
κ
i
= |{k | Δr
k
≥ i}|,i=1, 2, ···,
just as in the conventional dynamical system theory. Note that κ
1
= κ(A, B).
The indices {κ
i
} are called the controllability indices of (A, B).
For a controllable system we can find a nicely nested input sequence with
reference to the controllability indices as follows.
Theorem 7.2.21. Suppose (A, B) is controllable. There exists an input
(U
k
| k =0, 1, ···,K − 1) with K ≤|S| admissible for (∅,S) such that
U
0
⊆ U
1
⊆···⊆U
K−1
and that
{˜κ
u
| u ∈ P } = {κ
i
| i =1, ···, |P |},
where ˜κ
u
= |{k | U
k
u, 0 ≤ k ≤ K − 1}| indicates how many times u ∈ P
is used.
Proof. See Murota [206].
Notes. Sections 7.2.2 and 7.2.3 are based on Murota [211], whereas §7.2.4 is
on Murota [206].
7.3 Mixed Skew-symmetric Matrix 431
7.3 Mixed Skew-symmetric Matrix
7.3.1 Introduction
A square matrix A =(A
ij
) over a field is said to be skew-symmetric if A
T
=
−A and all the diagonal entries are equal to zero, where the second condition
is implied by the first if the characteristic of the underlying field is distinct
from two. The definition of skew-symmetry presupposes that the row set and
the column set of A are indexed by a common finite set, say V = {1, ···,n}.
Skew-symmetric matrices enjoy rich combinatorial structures. Among oth-
ers, the rank of a skew-symmetric matrix A is equal to the maximum size
of a matching in the associated undirected graph G =(V,E) with vertex
set V and arc set E = {(i, j) | A
ij
=0}, provided that the nonzero entries
of the matrix are independent parameters except for the obvious constraint
A
ij
+A
ji
= 0 due to skew-symmetry. This fact was exploited by Tutte [322] in
deriving a fundamental duality result for maximum matchings (cf. Theorem
7.3.9). Combinatorial properties of a skew-symmetric matrix with numerical
data are abstracted as delta-matroids by Bouchet [15]. A delta-matroid is
an abstract discrete structure defined in terms of an exchange axiom (to be
explained in §7.3.3).
Skew-symmetric matrices are also important in applications. Electrical
network theory, in particular, employs an ideal element called a gyrator,
which is described by a skew-symmetric matrix of order two. The solvability
of RCG networks (electrical networks involving gyrators as well as resistors
and capacitors) has been analyzed successfully with the aid of the results on
the matroid parity problem (Recski [276, 277], Ueno–Kajitani [323]).
In this section we introduce the skew-symmetric version of a mixed matrix
as a further mathematical tool for systems analysis by means of matroid-
theoretic combinatorial methods. A mixed skew-symmetric matrix is a matrix
A expressed as A = Q + T , where Q is a “constant” skew-symmetric matrix
and T is a “generic” skew-symmetric matrix in the sense that the nonzero
entries of T are independent parameters except for the obvious constraint
due to skew-symmetry.
A formal definition of mixed skew-symmetric matrix reads as follows. Let
F be a field, and K be a subfield of F . A skew-symmetric matrix A over
F (i.e., A
ij
= −A
ji
∈ F , A
ii
= 0) is called a mixed skew-symmetric matrix
with respect to (K, F )if
A = Q + T, (7.43)
where
(MS-Q) Q is a skew-symmetric matrix over K (i.e., Q
ij
∈ K), and
(MS-T) T is a skew-symmetric matrix over F (i.e., T
ij
∈ F ) such
that the set T = {T
ij
| T
ij
=0,i < j} of its nonzero entries in
the upper-triangular part is algebraically independent over K.