混合行列束のKronecker標準形の組合せ論的解析

全文

(1)Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. ical form plays an important role in many applications such as control theory2),20) and differential-algebraic equations10),19) . Several numerical algorithms for computing it are. 混合行列束の Kronecker 標準形の組合せ論的解析. available1),3),4),9),21) . Matrix pencils arising in practice are often very sparse, and it is tempting to exploit. 岩田. 覚†1. 高松瑞代†2. the combinatorial structures. The Kronecker canonical form is a block diagonal matrix which consists of nilpotent blocks, rectangular blocks, and a residual square block. Among them, nilpotent blocks admit two combinatorial characterizations. The first one. 各成分の次数が高々1 の多項式行列を行列束という. 行列束は Kronecker 標準形という正準形を持つ. 本研究では, 正確な数値と独立パラメータを区別する混合行列束の Kronecker 標準形の構造指数を組合せ的に解析する. さらに, 同様の手法を用いることで, 正方な混合行列のべき乗の階数計算が可能であることを示す.. utilizes the highest degree of subdeterminants, which can be computed by combinatorial relaxation algorithms7),13) . The second characterization is based on the ranks of larger constant matrices, called expanded matrices. Under the genericity assumption that the set of nonzero coefficients is algebraically independent, it is shown that the. Combinatorial Analysis of Kronecker Canonical Forms of Mixed Matrix Pencils. rank of the expanded matrix coincides with the maximum weight of a matching in a bipartite graph8) , which can be computed efficiently by combinatorial algorithms. The genericity assumption is justified by the fact that physical characteristics in en-. Satoru Iwata†1 and Mizuyo Takamatsu†2. gineering systems are not precise in values because of noises. However, the genericity assumption is not always valid in practical situations. In fact, exact numbers do arise. A mixed matrix pencil is a matrix pencil which has two kinds of nonzero coefficients: fixed constants that account for conservation laws and independent parameters that represent physical characteristics. In this paper, we characterize the indices of nilpotency of the Kronecker canonical form for a mixed matrix pencil in terms of matroids. As a byproduct, we provide an algorithm for computing the rank of a power product of a square mixed matrix.. in dynamical systems such as in Kirchhoff’s conservation laws in electric circuits, or in the law of conservation of mass, energy, or momentum and the principle of action and reaction in mechanical systems. This observation led Murota and Iri18) to introduce the notion of a mixed matrix. A mixed matrix is a constant matrix that consists of two kinds of numbers as follows. Accurate Numbers (Fixed Constants) Numbers that account for conservation. 1. Introduction. laws are precise in values. These numbers should be treated numerically.. A matrix pencil is a polynomial matrix in which the degree of each entry is at most. Inaccurate Numbers (Independent Parameters) Numbers that represent phys-. one. We express a matrix pencil as D(s) = sX + Y by a pair of constant matrices X. ical characteristics are not precise in values. These numbers should be treated. and Y . A matrix pencil D(s) can be brought into the Kronecker canonical form by. combinatorially as nonzero parameters without reference to their nominal values.. equivalent transformations with constant nonsingular matrices. The Kronecker canon-. Since each such nonzero entry often comes from a single physical device, the parameters are assumed to be independent.. †1 京都大学 Kyoto University †2 東京大学 University of Tokyo. In order to deal with dynamical systems, it is natural to consider the polynomial matrix version, which is called a mixed polynomial matrix17) . In particular, the matrix pencil version is called a mixed matrix pencil.. 1. c 2009 Information Processing Society of Japan °.

(2) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. For a positive integer µ, we consider a µ × µ matrix pencil  Nµ defined by  1 s 0 ··· 0  . .. 0 1 . ..  s    . . . .  . . . . Nµ =  . . . . 0 .  . ..  . . . 1 s. For mixed polynomial matrices, Murota16) showed that the computation of the highest degree of subdeterminants reduces to solving a valuated independent assignment problem14),15) . This enables us to determine nilpotent blocks for a mixed matrix pencil. Murota also investigated the Smith normal form11),12) and the Smith-McMillan form at infinity16) of a mixed polynomial matrix in terms of the degree of subdeterminants. In this paper, we analyze the Kronecker canonical form of a mixed matrix pencil by. 0 ··· ··· 0 1 For a positive integer ², we further  denote by L² an ² × (² + 1) matrix pencil s 1 0 ··· 0  . .. 0 s . ..  1   L² =  .  .. . . . . . . . . .  0 .. using the ranks of expanded matrices. Extending the previous results8) , we prove that the computation of the ranks of expanded matrices for mixed matrix pencils reduces to solving valuated independent assignment problems. This leads to an algorithm for determining nilpotent blocks of a mixed matrix pencil. As a byproduct, we provide an algorithm for computing the rank of a power product k. A of a square mixed matrix A. In general, the matrix Ak is not a mixed matrix,. 0 ··· 0 s We also denote by L> η the transpose matrix of Lη .. because Ak has an independent parameter appearing multiple times. Therefore, we can. 1. not apply directly an algorithm for the rank of a mixed matrix18) . By making use of an. Let us denote by bdiag(D1 , . . . , Db ) the block-diagonal matrix pencil with diagonal. expanded matrix, we reduce the computation of the rank of Ak to solving a valuated. blocks D1 , . . . , Db . A matrix pencil is known to be strictly equivalent to its Kronecker. independent assignment problem.. canonical form as follows.. The preceding paper8) provided combinatorial characterizations on the sizes of rect-. Theorem 2.1. By a strict equivalence transformation, a matrix pencil D(s) can be ¯ brought into its Kronecker canonical form D(s) with > ¯ D(s) = bdiag(sIν + Jν , Nµ1 , . . . , Nµd , L²1 , . . . , L²p , L> η1 , . . . , Lηq , O),. angular blocks under the genericity assumption. It remains open to extend this result to mixed matrix pencils.. where. 2. Kronecker Canonical Form of Matrix Pencils. µ1 ≥ · · · ≥ µd > 0,. Let D(s) = sX + Y be an m × n matrix pencil with row set R and column set C. A. ²1 ≥ · · · ≥ ²p > 0,. η1 ≥ · · · ≥ ηq > 0,. Iν is a ν × ν identity matrix, and Jν is a ν × ν constant matrix. The numbers ν, d, p,. matrix pencil D(s) is said to be regular if D(s) is square and det D(s) 6= 0 as a poly-. q, µ1 , . . . , µd , ²1 , . . . , ²p , η1 , . . . , ηq are uniquely determined.. nomial in s. The rank of D(s) is the maximum size of its submatrix that is a regular ¯ matrix pencil. A matrix pencil D(s) is said to be strictly equivalent to D(s) if there ¯ exists a pair of nonsingular constant matrices F and H such that D(s) = F D(s)H.. are called the indices of nilpotency.. The matrices Nµ1 , . . . , Nµd are called the nilpotent blocks, and the numbers µ1 , . . . , µd The numbers ²1 , . . . , ²p and η1 , . . . , ηq are. the minimal column indices and minimal row indices, respectively.. The numbers. (ν, µ1 , . . . , µd , ²1 , . . . , ²p , η1 , . . . , ηq ) are called the structural indices of D(s). For an m × n matrix pencil D(s) = sX + Y , we consider a km × kn matrix Θk (D). 2. c 2009 Information Processing Society of Japan °.

(3) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. . defined by. X.  Y   Θk (D) =  O  .  .  .. ··· .. . .. . .. .. O X Y ... .. ··· ... .. . 3. Mixed Matrix Pencil. O ..  .   ..   . .. In this section, we first describe the definition of mixed matrix pencils. Secondly, for a mixed matrix pencil DM (s), we reduce the computation of θk (DM ) to the computation.  . of θk (D) for an associated special mixed matrix pencil D(s).. O. X. A generic matrix is a matrix in which each nonzero entry is an independent param-. O ··· O Y X We also construct a (k + 1)m × kn matrix Ψk (D) and a km × (k + 1)n matrix Φk (D) defined by. . X.  Y   Ψk (D) =  O  .  .  .. O X Y ... .. . ··· .. . .. . .. .. O ..  .  .     X O. .  O  and Φk (D) =   ..  .. X .. .. Y .. .. ··· .. . .. .. O. ···. O. X. O ··· O Y The rank of each expanded matrix is denoted by θk (D) = rank Θk (D), The following theorem. 8). ψk (D) = rank Ψk (D),. X. Y. O. eter. A matrix D is called a mixed matrix if D is given by D = Q + T with a constant matrix Q and a generic matrix T . A layered mixed matrix (or an LM-matrix for short) is defined to be a mixed matrix such that Q and T have disjoint nonzero rows. An. . LM-matrix D is expressed by D =. O ..   . . (Q) T. .. A mixed matrix pencil is a matrix pencil version of mixed matrices. A matrix pencil. . . D(s) is called a mixed matrix pencil if D(s) is given by D(s) = Q(s) + T (s) with a pair. O. of matrix pencils Q(s) = sXQ + YQ and T (s) = sXT + YT that satisfy the following two. Y. conditions. (MP-Q) XQ and YQ are constant matrices. (MP-T) XT and YT are generic matrices.. φk (D) = rank Φk (D).. Note that each independent parameter in XT and YT appears only once. A layered. shows a close relationship between the ranks of the expanded. matrices and the structural indices.. mixed matrix pencil (or an LM-matrix pencil for short) is defined to be a mixed matrix. Theorem 2.2. Let D(s) be a matrix pencil of rank r with the structural indices. pencil such that Q(s) and T (s) satisfying (MP-Q) and (MP-T) have disjoint nonzero. (ν, µ1 , . . . , µd , ²1 , . . . , ²p , η1 , . . . , ηq ). Then we have. rows. An LM-matrix pencil D(s) is expressed by D(s) =. ∑ d. θk (D) = rk −. ∑. φk (D) = rk +. . The polynomial ma-. mixed polynomial matrix (or an LM-polynomial matrix for short) in a similar way. Let DM (s) = s(XQ +XT )+(YQ +YT ) be an m×n mixed matrix pencil. We construct. min{k, ²i },. ). (. an LM-matrix pencil. i=1. q ∑. T (s). trix version of a mixed matrix is called a mixed polynomial matrix. We define a layered. min{k, µi },. i=1 p. ψk (D) = rk +. (Q(s)). I. XQ. ). ( O. YQ. , (1) + O YT −DT XT where DT is a diagonal matrix with the (i, i) entry being a new independent parameter D(s) = s. min{k, ηi }.. i=1. ti . We transform ) its strictly ( equivalent matrix ) ( ) ( D(s) into I XQ O YQ I O D(s) = s + . −I DT−1 XT O DT−1 YT O DT−1 Since DT is a diagonal generic matrix, we can regard DT−1 XT and DT−1 YT as new generic. By Theorem 2.2, the ranks of the expanded matrices determine the indices. In this paper, we analyze θk (D) for a mixed matrix pencil D(s) in order to obtain the indices of nilpotency µ1 , . . . , µd .. 3. c 2009 Information Processing Society of Japan °.

(4) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. ( ˜ T and Y˜T , respectively. Hence, D(s) and s matrices X. (. ). (. ). ) I. XQ ˜T X. −I. ( +. ) O. YQ Y˜T. O.        permutations  −−−−−−−−→        . , as. I XQ O YQ + , have the same Kronecker canonical form. −I XT O YT This observation leads to the following lemma concerning the relation between DM (s) ¯ well as D(s) =s. and D(s). Lemma 3.1. Let DM (s) = s(XQ + XT ) + (YQ + YT ) be an m × n mixed matrix pencil, and D(s) be its associated LM-matrix pencil defined by (1). Then we have θk (DM ) + km = θk (D).. (2) =. Im. O. O. O. XQ. O. O. O. O. Im. O. YQ. O. O. O. XQ .. .. O .. .. O. O. O .. .. O. O. O. O. Im. O. O. YQ. XQ. O. O. O. O. XQ + XT. O. O. O. O. O. O. O. YQ + YT. O. O. O. O. O .. .. O. O. XQ + XT .. .. O. ( O. O. O. )O. O. O. YQ + YT. XQ + XT. Ikm. O Hence it holds that. ∗ Θk (DM ).                . .. ¯ M ) = θk (DM ) + km. θk (D Thus we obtain (2) by (3). Proof. As noted above, D(s) has( the same Kronecker ) form as ) ( canonical O Y I X Q Q ¯ . + D(s) =s O YT −I XT ¯ Moreover, since D(s) ( is strictly ) equivalent ( to ) ( ) I O I X O Y Q Q ¯ M (s) = ¯ D D(s) =s + , I I O X Q + XT O YQ + YT we have ¯ = θk (D ¯ M ). θk (D) = θk (D) ¯ M ) as follows: Now we can transform Θk (D  Im XQ O O.         ¯ Θk (DM ) =        . O. O. O. O. XQ + XT. O. O. O. O. O. O. O. YQ. Im. XQ. O. O. O. O. O. YQ + YT. XQ + XT. O. O. O. O .. .. O. O. O .. .. O. O. ... ... .. O. O. O. O. O. O. O. O. O. its associated LM-matrix pencil defined by (1). Then we can not reduce the computation of ψk (DM ) to ψk (D) and φk (DM ) to φk (D) in a similar way to the proof of Lemma 3.1. This is one of major differences between θk (DM ) and ψk (DM ), φk (DM ). (3). 4. Valuated Independent Assignment Problem. . O. O. By Lemma 3.1, we hereafter focus on an LM-matrix pencil. Remark 3.2. Let DM (s) = s(XQ +XT )+(YQ +YT ) be a mixed matrix pencil, and D(s). .. O. O. O. YQ. Im. XQ. O. YQ + YT. O. XQ + XT. This section is devoted to preliminaries on matroids and valuated matroids, which.                . are combinatorial abstractions of matrices and polynomial matrices. After recapitulating matroids and valuated matroids, we explain the valuated independent assignment problem. A matroid is a pair M = (V, I) of finite set V and a collection I of subsets of V such that (I-1) ∅ ∈ I, (I-2) I ⊆ J ∈ I ⇒ I ∈ I, (I-3) I, J ∈ I, |I| < |J| ⇒ I ∪ {v} ∈ I for some v ∈ J \ I.. 4. c 2009 Information Processing Society of Japan °.

(5) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. The set V is called the ground set, I ∈ I is an independent set, and I is the family. matching and ∂ + M ⊆ B + ∈ B+ ,. of independent sets. Let B be the family of inclusion-wise maximal members of I. A. −. ∂ M ⊆B. member of B is called a base, and B is the base family.. matroids, which originate from a combinatorial structure of polynomial matrices with A valuated matroid is a triple M = (V, B, ω) of a ground set V , a base family B ⊆ 2V ,. Let D(s) =. (VM) For any B, B 0 ∈ B and u ∈ B \ B 0 , there exists v ∈ B 0 \ B such that B \ {u} ∪ The function ω is called a valuation. Note that a valuated matroid M = (V, B, ω) such that ω(B) = 0 for all B ∈ B coincides with a matroid. For a polynomial b(s), we denote the degree of b(s) by deg b, where D(s) with row set I and column set J. A typical example of a valuated matroid is as follows. Example 4.1. For an m × n matrix pencil D(s) of rank m with row set R and column set C, let us define ω(B) = deg det D[R, B].. Murota14),15) introduced the valuated independent assignment problem as a generalization of the independent matching problem6) . [Valuated Independent Assignment Problem (VIAP)] and edge set. ··· .. .. O ..  .  .   O. XQ. O. YQ. O   XQ .  XT    YT    O. O .. . .. .. O O XT.    . O  .     O . O . independent parameters in XT and Y(T appear ) multiple times. Q(s) , we introduce a VIAP. For a polynomial For an LM-matrix pencil D(s) = T (s) matrix Z(s), let us define. a weight function w : E → R, and subsets V0+ ⊆ V + and V0− ⊆ V − , find a −. triple (M, B , B ) that maximizes Ω(M, B + , B − ) := w(M ) + ω + (B + ) + ω − (B − ), where w(M ) =. The expanded matrix Θk (D) is expressed as  XQ O  .. Y .  Q  .  ..  O. O O YT XT by permutations. Although Θk (D) looks like an LM-matrix, it is not. This is because. E, a pair of valuated matroids M+ = (V + , B+ , ω + ) and M− = (V − , B− , ω − ), +. (5). Q(s). Θk (D) =  . Then (C, B, ω) is a valuated matroid.. Given a bipartite graph G = (V , V ; E) with vertex sets V , V. (4). its copy by C Q = {j Q | j ∈ C}.. deg 0 = −∞ by convention. For a matrix pencil D(s), D[I, J] denotes the submatrix of. −. =B ∩. V0− .. valuated independent assignment problem. ( ) Q(s) For an LM-matrix pencil D(s) = , we denote the row sets of Q(s) and T (s) T (s) by RQ and RT , respectively. Moreover, we denote the column set of D(s) by C, and. {v} ∈ B, B 0 ∪{u}\{v} ∈ B, and ω(B)+ω(B 0 ) ≤ ω(B \{u}∪{v})+ω(B 0 ∪{u}\{v}).. +. ∂ M∩. −. be an LM-matrix pencil with Q(s) = sXQ + YQ and T (s) = T (s) sXT + YT . In this section, we prove that θk (D) coincides with the optimal value of a. and a function ω : B → R that satisfy the following axiom (VM).. −. ∈B ,. V0−. 5. Analysis of θk (D) ( ). respect to the degree of determinants.. +. −. V0+ = V + and V0− = V − .. pendence. As a generalization of matroids, Dress and Wenzel5) introduced valuated. and. −. This problem is an extension of the problems introduced by Murota14),15) , where. Matroids are a combinatorial abstraction of matrices with respect to linear inde-. B = {B ⊆ C | det D[R, B] 6= 0}. −. ∂ + M ∩ V0+ = B + ∩ V0+ ,. ∑. {w(a) | a ∈ M }, subject to the constraint that M ⊆ E is a. δ(Z) = max{deg det Z[I, J] | |I| = |J|},. 5. c 2009 Information Processing Society of Japan °.

(6) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. Thus we obtain. which is the highest degree of subdeterminants of Z(s). First, we prove the following. max{deg det sk−1 Nµi [I, J]} = kµi − min{µi , k}.. key lemma. k. k−1. Lemma 5.1. Let D(s) = sX + Y be a matrix pencil, and Z(s) = s X + s. Y be a. (. It follows from (7) and (8) that. polynomial matrix. Then we have θk (D) = δ(Z).. δ(Z) =. d ∑. (kµi − min{µi , k}) + k. i=1. Proof. Since θk (D) and δ(Z) are invariant under strictly equivalent transformations,. = rk −. we may assume that D(s) = sX + Y is a Kronecker canonical form with the structural. d ∑. r−. d ∑. ) µi. i=1. min{µi , k},. i=1. which coincides with θk (D) by Theorem 2.2.. indices (ν, µ1 , . . . , µd , ²1 , . . . , ²p , η1 , . . . , ηq ). We denote the rank of D(s) by r. Then we have r=ν+. d ∑ i=1. µi +. p ∑. ²i +. i=1. q ∑. ηi .. For an LM-matrix pencil, we ( obtain the following corollary. ) sXQ + YQ ˜ be an LM-matrix pencil, and Z(s) = Corollary 5.2. Let D(s) = sXT + YT. (. (6). i=1. Now Z(s) is expressed as k−1. Z(s) = s. bdiag(sIν +. > Jν , Nµ1 , . . . , Nµd , L²1 , . . . , L²p , L> η1 , . . . , Lηq , O).. I. sk XQ + sk−1 YQ. O. sk XT + sk−1 YT. ). ˜ be an LM-polynomial matrix. Then we have θk (D) = δ(Z).. (. Hence it holds that Proof. It follows from Lemma 5.1 that θk (D) = δ(Z) for Z(s) =. δ(Z) = max{deg det sk−1 bdiag(Nµ1 , . . . , Nµd )[I, J]} I,J. > + max{deg det sk−1 bdiag(sIν + Jν , L²1 , . . . , L²p , L> η1 , . . . , Lηq )}. (. I,J. = max{deg det s. k−1. I,J. = max{deg det s I,J. bdiag(Nµ1 , . . . , Nµd )[I, J]} + k. ν+. ( k−1. bdiag(Nµ1 , . . . , Nµd )[I, J]} + k. r−. p ∑. ²i +. ). i=1. d ∑. µi. q ∑. ). (7). Let us investigate a µi × µi polynomial matrix s. sk XT + sk−1 YT. .. est degree of a submatrix with row set containing RQ . For an LM-polynomial matrix, Murota16) showed that the computation of the highest degree of subdeterminants with ˜ in the same row set containing RQ reduces to a VIAP. We now derive a VIAP for δ(Z). where the last step is due to (6). k−1. ). ˜ instead of θk (D). The row set and the column By Corollary 5.2, we focus on δ(Z) Q T ˜ set of Z(s) are denoted by R ∪ R and R ∪ C, where we use the same notation RQ , ˜ has the highRT , and C as the corresponding row/column set of D(s). Note that δ(Z). ηi. i=1. ,. sk XQ + sk−1 YQ. ˜ by δ(Z) = δ(Z). ˜ Hence we obtain θk (D) = δ(Z). i=1. Nµi . The highest degree of sub-. determinants is. way as Reference 16). deg det sk−1 Nµi = (k − 1)µi. or. (8). I,J. . sk.   sk−1  deg det   . 0 sk .. .. ··· .. . .. . sk−1. ˜ ˜ We denote the upper half of Z(s) by Q(s), and the lower half by T˜(s). Consider. . a bipartite graph G = (V + , V − ; E) with V + = RQ ∪ C Q ∪ RT , V − = R ∪ C, and. 0 ..   . . E = E Q ∪ E X ∪ E Y , where E Q = {(j Q , j) | j ∈ R ∪ C},.  = k(µi − 1).  0 . E X = {(i, j) | i ∈ RT , j ∈ C, the (i, j)th entry of XT is nonzero}, E Y = {(i, j) | i ∈ RT , j ∈ C, the (i, j)th entry of YT is nonzero}.. sk. 6. c 2009 Information Processing Society of Japan °.

(7) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. defined by. RQ. ˜ B+ = {RT ∪ B | B ∈ B},. ω + (B + ) = ω ˜ (B + \ RT ). (B + ∈ B+ ),. and B− = {R ∪ C},. R. ω − (R ∪ C) = 0.. Let us summarize the VIAP.. CQ. [VIAP for D] ˜ = (RQ ∪ Given a bipartite graph G = (V + , V − ; E), a valuated matroid M ˜ ω C Q , B, ˜ ), and a weight function w : E → R, find (M, B) that maximizes. C. Ω(M, B) := w(M ) + ω ˜ (B), subject to the constraint that M ⊆ E is a matching and ˜ ∂ + M ∩ (RQ ∪ C Q ) = B ∈ B.. RT. V. +. V. The main theorem of this paper is as follows. ) ( sXQ + YQ be an LM-matrix pencil. Then θk (D) coinTheorem 5.4. Let D(s) = sXT + YT cides with the optimal value of VIAP for D.. −. Figure 1 A graph G = (V + , V − ; E Q ∪ E X ∪ E Y ) with E Q (solid line), E X (heavy line), and E Y (dotted line) of Example 5.3.. 6. Application to Power Product of Mixed Matrices The weight w(a) of an arc a ∈ E is given  by  0. . w(a) =.   . A and a positive integer k. An algorithm for computing the rank of mixed matrices was. (a ∈ E X ),. k. k − 1 (a ∈ E Y ). ˜ ˜ ω Let us define a valuated matroid M = (RQ ∪ C Q , B, ˜ ) by Q Q Q ˜ ˜ Q , B] B˜ = {B ⊆ R ∪ C | det Z[R , B] 6= 0} and ω ˜ (B) = deg det Z[R Example 5.3. Consider an LM-matrix  pencil s 0 0.   0  D(s) =   t1 s   t3. We now consider the problem of computing the rank of Ak for an n × n mixed matrix. (a ∈ E Q ),. 1. s. 0. 0. t4. 0. described by Murota and Iri18) . However, since Ak has an independent parameter appearing multiple times, Ak itself is not a mixed matrix. This prevents us from applying that algorithm directly to Ak .. ˜ (B ∈ B).. Instead, we compute rank Ak via the an expanded matrix  expanded matrix. For  A O ··· ··· O  ..   I A ... .     ..  .. ..  Θk (sA + I) =  . . . , O I .  ..  . ..  . . . A O.  1.   t2 s  ,  0  s . 0 0 t5 s t 6 where t1 , . . . , t6 are independent parameters. Figure 1 illustrates G.. O. ···. O. I. A. We define the following VIAP on G, where V0+ = RQ ∪C Q and V0− = ∅. The valuated matroids M+ = (V + , B+ , ω + ) and M− = (V − , B− , ω − ) attached to V + and V − are. 7. c 2009 Information Processing Society of Japan °.

(8) Vol.2009-AL-126 No.4 2009/9/15. 情報処理学会研究報告 IPSJ SIG Technical Report. we can transform Θk (sA + I) into O O.  I    O . . .. O I .. .. O ··· by row operations. Hence we obtain. ··· .. . .. . .. .. O. −A2. O. I. A. O .. . O. (−1)k+1 Ak. reducing subspaces of singular A−λB pencils, SIAM J. Sci. Statist. Comput., vol.7, pp.185–211 (1986). 10) Kunkel, P. and Mehrmann, V.: Differential-Algebraic Equations: Analysis and Numerical Solutions, European Mathematical Society (2006). 11) Murota, K.: On the Smith normal form of structured polynomial matrices, SIAM J. Matrix Anal. Appl., vol.12, pp.747–765 (1991). 12) Murota, K.: On the Smith normal form of structured polynomial matrices, II, SIAM J. Matrix Anal. Appl., vol.14, pp.1103–1111 (1993). 13) Murota, K.: Combinatorial relaxation algorithm for the maximum degree of subdeterminants: Computing Smith-McMillan form at infinity and structural indices in Kronecker form, Applicable Algebra in Engineering, Communication and Computing, vol.6, pp.251–273 (1995). 14) Murota, K.: Valuated matroid intersection, I: optimality criteria, SIAM J. Discrete Math., vol.9, pp.545–561 (1996). 15) Murota, K.: Valuated matroid intersection, II: algorithms, SIAM J. Discrete Math., vol.9, pp.562–576 (1996). 16) Murota, K.: On the degree of mixed polynomial matrices, SIAM J. Matrix Anal. Appl.,vol.20, pp.196–227 (1999). 17) Murota, K.: Matrices and Matroids for Systems Analysis, Springer-Verlag, Berlin (2000). 18) Murota, K. and Iri, M.: Structural solvability of systems of equations — A mathematical formulation for distinguishing accurate and inaccurate numbers in structural analysis of systems, Japan J. Appl. Math., vol.2, pp.247–271 (1985). 19) Riaza, R.: Differential-Algebraic Systems: Analytical Aspects and Circuit Applications, World Scientific Publishing Company (2008). 20) Thorp, J. S.: The singular pencil of a linear dynamical system, Int. J. Control , vol.18, pp.577–596 (1973). 21) Van Dooren, P.: The computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl., vol.27, pp.103–140 (1979)..  . (−1)k Ak−1    ..  . .   . rank Ak = θk (sA + I) − (k − 1)n. k. Therefore, rank A is determined by θk (sA + I), which can be computed by solving a valuated independent assignment problem.. References 1) Beelen, T. and Van Dooren, P. : An improved algorithm for the computation of Kronecker’s canonical form of a singular pencil, Linear Algebra Appl., vol.105, pp. 9–65 (1988). 2) Demmel, J. and K˚ agstr¨ om, B.: Accurate solutions of ill-posed problems in control theory, SIAM J. Matrix Anal. Appl., vol.9, pp.126–145 (1988). 3) Demmel, J. and K˚ agstr¨ om, B.: The generalized Schur decomposition of an arbitrary pencil A-λB: Robust software with error bounds and applications. Part I: Theory and algorithms, ACM Transactions on Mathematical Software, vol.19, pp. 160–174 (1993). 4) Demmel, J. and K˚ agstr¨ om, B.: The generalized Schur decomposition of an arbitrary pencil A-λB: Robust software with error bounds and applications. Part II: Software and applications, ACM Transactions on Mathematical Software, vol.19, pp.175–201 (1993). 5) Dress, A. W. M. and Wenzel, W.: Valuated matroids, Adv. Math., vol. 93, pp. 214–250 (1992). 6) Iri, M. and Tomizawa, N.: An algorithm for finding an optimal “independent assignment”, J. Oper. Res. Soc. Japan, vol.19, pp.32–57 (1976). 7) Iwata, S.: Computing the maximum degree of minors in matrix pencils via combinatorial relaxation, Algorithmica, vol.36, pp.331–341 (2003). 8) Iwata, S. and Shimizu, R.: Combinatorial analysis of singular matrix pencils, SIAM J. Matrix Anal. Appl., vol.29, pp.245–259 (2007). 9) K˚ agstr¨ om, B.: RGSVD—an algorithm for computing the Kronecker structure and. 8. c 2009 Information Processing Society of Japan °.

(9)