●学生論文賞受賞論文

CombinatorialMatrixAnalysISbySign Patterns
垣村 尚徳（東京大学大学院情報理工学系研究科数理情報学専攻 現所属・同大学院情報理工学系研究科数理情報学専攻）
指導教員 岩田 覚肋教授

長年未解決であったが，1999年にRobertson，1．はじめにSeymour，Thomasによって多項式時間解法が示され経済活動などの社会現象を線形方程式系で定式化す
る時，その係数の大小関係や正負は，選好順序や変化の方向性から容易に知ることができるが，係数の正確た［5］．

3．対称行列の符号指数な値を知ることが困難である場合が多い．本論文では，対称行列の符号指数とは，対称行列の正，負，零のこのような定性的情報のみが抜える状況の下で解析を固有値の数の組を指す．この値は合同変換において不行うために，その係数行列の要素の絶対値によらない変な値であり，符号指数によって二次形式を分類する性質を調べることを目的とする．

ことができる．非線形関数において，その二階微分で行列要素の符号情報のみから分かる性質を調べる研
究は，定性的行列理論とも呼ばれ，Samuelson［6］によって経済モデルを扱うために提唱された．その後，あるヘッセ行列の符号指数は，ある点の近傍における曲面の形状を表す．
この対称行列の符号指数を行列要素の符号情報を基Brualdi，Shader［1］などによる線形方程式系の符号情に計算することを議論する．すなわち，対称行列A報に基づく解析など様々な研究がなされてきた．と同じ符号パターンを持つ対称行列全体の集合を本論文では，このような定性的行列理論のさらなる0＊（A）：＝（AlÅ∈0（A），AT＝A）とした時，任意の発展として，特に最適化問題に関連する行列の定性的A∈0＊（A）が同じ符号指数を持つかどうかを判定し，解析を行う．主に二つの問題を扱う．まず，対称行列もし同じならばAの要素の正負を基に符号指数を計の符号指数を行列要素の正負から計算することを議論算する方法を考える．

する．さらに，線形計画問題に対して，その係数行列

Ha11，Li，Wang［2］は，対称行列の符号指数が行列の符号情報から最適解の符号情報が一意に定まるため要素の大きさによらず一意に定まるための必要十分条の条件とその解法について議論する．

件を与えている．対称行列Aにおいて，任意のA∈
Q＊（A）が正則であるとき，Aは符号正則であるとい

2．符号正則性判定問題

う．Hallらの結果より，符号正則な対称行列は符号定性的行列理論における重要な問題の一つとして，行列の符号情報から要素の大きさによらず正則（符号指数が一意に定まる．
本論文ではまず，符号正則な対称行列に対する符号正則性）かどうかを判定する問題がある．すなわち，指数の一意性をHa11らと別の方法によって示した．

行列Aと同じ符号パターンを持つ行列全体の集合をこれは，対称行列に対応する二部グラフの完全マッチ￠（A）としたとき，Q（A）内の行列全てが正則かどうングの性質を調べることで組合せ的に導かれる．さらかを判定する問題である．この符号正則性判定問題は，に，二部グラフの最大量み完全マッチングを求めるア

様々な組合せ的問題と等価であることが知られている

ルゴリズムを利用することで，符号正則な対称行列の［4］．1913年にP61yaによって提案された行列のパー符号指数を求めるための多項式時間解法を与えた．

マネントの計算を行列要素のいくつかを−1倍するこ定理1対称行列Aが符号正則ならば，要素の大きさとで行列式の計算に帰着できるか判定する問題，有向によらず符号指数が一意に定まる．

グラフに長さ偶数の初等的有向閉路が存在するか判定

定理2乃次対称行列Aが符号正則ならば，要素の符する問題，二部グラフがPfa侃an orientationを持つ号のみから符号指数を0（ノ盲γlog乃）時間で計算できか判定する問題などと等価である．その計算複雑度はる．ただしγとはAの非零要素の個数を指す．

2005年12月号© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.

（45）835

さらに，対称行列の符号指数の一意性の判定についA，∂，Cの要素の符号を基に単体法を動かすことがでて，以下の定理が成り立つ．これは，長方行列のランきる．単体表の符号パターンは，完全符号正則行列にクが行列要素の大きさによらずに一意に決まるか判定対応する二部グラフ上でパスを見つけることで，要素する問題がcoNP完全であるというKlee，Ladner，の符号のみから組合せ的に得られる．よって，一回のManber［3］の結果に基づいている．

ピボットに対する計算量は0（γ）となる．ただし，γ定理3対称行列Aに対して，Aと同じ符号指数を持はA，∂，Cの非零要素数の和である．完全符号正則行

たないA∈￠＊（A）が存在するか判定する問題はNP

列は疎であるので，数値計算を行うよりも効率的に計完全である．

算することができる．ピボットの更新規則としては，変数の添字と単体表の符号のみから更新していく規則，4．線形計画法の符号可解性

例えば最小添字規則や十文字法，が知られており，これらは有限回の反復で終了する．よって，符号情報の線形計画問題：

maXlmlZe CX

みを用いて，有限回の反復で最適解の符号パターンをSubjectto A．r＝b，得ることができる．
さらに，定理4の条件を満たすとき，線形計画問題∬≧0，に対して，与えられたA，∂，Cの要素の符号から，最を多項式時間で解くことができる．最適解の符号パタ適解の符号パターンを求めることを目的とする．線形ーンは，符号可解性から非零要素を全て＋1と一1に計画問題が符号可解であるとは，最適解のとり得る符置き換えた問題のものと等しい．この間題の入力の大号パターンの集合が，A，∂，Cの要素の大きさによらきさは定数なので，楕円体法や内点法を用いて最適解ずに一意に定まることを言う．本論文では，符号可解の符号パターンを多項式時間で計算できる．

な線形計画問題に対する特徴づけを行った．
参考文献

そのために完全符号正則という性質を導入する．研×乃次行列A（桝＞乃）が完全符号正則であるとは，A［1］R．A．Brualdiand B．L．Shader：Mahices qf Sなn−SOluableLinear＄ystems，CambridgeUniversityPress，の任意の弼次正方部分行列の正則性がAの要素の大きさによらず一意に決まることを言う．与えられた行列が完全符号正則であるかどうかは，Robertson，Seymour，Thomasの符号正則性判定方法を用いることで多項式時間で判定可能である．符号可解性に関して，以下の定理が成り立つ．

Cambridge，1995．
［2］F．J．Hall，Z．Liand D．Wang：Symmetric signpattern matrices that requlre unlqueinertia，Linear
却如飯川胱＝わ4妙払地肌，338，pp．153−169，2001．

［3］Ⅴ．Klee，R．LadnerandR．Manber：Sign−SOlvability
revisited，LinearAkebnlandIisApplications，59，pp．

定理4線形計画問題は，行列（A∂）とがともに（ニ）完全符号正則ならば，符号可解である．

13ト158，1984．

［4］W．McCuaig：P61ya，s permanent problem，771e
gJec〜和瑠fcノ0緑川αJ〆Co刑∂f乃αわわcs，11，＃R79，2004．

この十分条件は，任意の基底に村する基底解とその［5］N．Robertson，P．D．SeymourandR．Thomas：Per−

簡約費用が与えられた要素の大きさによらず一意に定

manents，Pfafhanorientations，andevendirected cir−

まるための必要十分条件であり，符号可解性を特徴付

Cuits，AnnaLs d Mathematics，150，No．3，pp．929−975，けるための最も自然な条件となっている．

1999．

線形計画問題を解くための方法の一つに単体法が知られている．定理4の条件を満たすならば，任意の基底に対する単体表の符号パターンが一［6］p．A．Samuelson：Fbundations q／EconomicsAnal−ysis，HarvardU．P．，1947；Atheneum，NewYork，1971．

意に定まるため，オペレーションズ・リサーチ

83一事（46）© 日本オペレーションズ・リサーチ学会. 無断複写・複製・転載を禁ず.