会議マトリックス

数学において、会議行列（C行列とも呼ばれる）は、対角線上に0、対角線外に+1と-1を持つ正方行列 Cであり、 C T Cは単位行列 Iの倍数となる。したがって、行列の次数がnである場合、C T C  = ( n -1) Iとなる。一部の著者は、より一般的な定義を用いており、各行と各列に1つの0が存在する必要があるが、対角線上には必ずしも0が存在する必要はないとしている。[1] [2]

会議行列は、電話通信における問題に関連して初めて登場しました。[3]ヴィトルド・ベレヴィッチ によって初めて記述され、その名前も付けられました。ベレヴィッチは理想的な変成器から理想的な電話会議ネットワークを構築することに関心を持ち、そのようなネットワークが会議行列で表されることを発見したため、会議行列という名前が付けられました。[4] その他の応用としては、統計学、[5] 、楕円幾何学などがあります。[6]

n > 1の場合 、2 種類の会議行列が存在します。まず (より一般的な定義を使用する場合)、すべての 0 が対角線上にあるように行を並べ替え、次に最初のエントリが負である行または列を否定することで、 C を正規化します (これらの操作では、行列が会議行列であるかどうかは変わりません)。したがって、正規化された会議行列では、左上隅の 0 を除き、最初の行と最初の列はすべて 1 になり、対角線上では 0 になります。Cの最初の行と最初の列を削除したときに残る行列をSとします。すると、 nが偶数(4 の倍数) かつSが歪対称(最初の行が否定された場合の正規化Cと同様に) であるか、またはnが奇数( 4 を法として 2 と合同) かつSが対称(正規化Cと同様に) になります。

対称的な会議マトリックス

Cがn  > 1の次数の対称会議行列である場合、 nは2 mod 4に合同であるだけでなく、n − 1は2つの平方の和でなければなりません。[7] van LintとSeidelによる初等行列論による巧妙な証明があります。 [6] n − 1が素数ベキであれば、 nは常に2つの平方の和になります。[8]

対称会議行列が与えられたとき、行列Sはグラフのザイデル隣接行列とみなすことができます。グラフはn − 1 個の頂点を持ち、それぞれSの行と列に対応します。S の対応する要素が負の値である場合、2つの頂点は隣接しています。このグラフは強正則であり、（行列にちなんで）会議グラフと呼ばれます。

上記の制約によって許されるn次会議行列の存在は、nのある値についてのみ知られています。たとえば、n = q  + 1 でq が1 mod 4 と合同な素数べきである場合、Paley グラフは、 S をPaley グラフの Seidel 行列とすることで、n次対称会議行列の例を提供します。対称会議行列の最初のいくつかの可能な次数は、 n = 2、6、10、14、18、（21 は 2 つの平方の和ではないので 22 ではない）、26、30、（33 は 2 つの平方の和ではないので 34 ではない）、38、42、46、50、54、（58 ではない）、62（OEISのシーケンスA000952）です。これらのそれぞれについて、その次数の対称会議行列が存在することがわかっています。命令66は未解決の問題のようです。

例

本質的に唯一の6次の会議行列は次のように与えられる。

。

6 次その他の会議行列は、行や列の符号を反転することによって (また、使用されている定義に従って行や列の順列を並べ替えることによって)、この行列から取得されます。

10次​​の会議行列は

。

歪対称会議マトリックス

歪対称行列は、ペイリー構成によっても生成できます。qを剰余 3 mod 4 を持つ素数冪とします。すると、q次数のペイリー有向グラフが存在し、これはn = q + 1次数の歪対称会議行列につながります。 この行列は、 i から j への有向グラフの弧がある場合、位置 ( i , j ) に +1、位置 ( j , i ) に -1 を持ち、対角線が0であるq × q行列 をSに 取る ことで得られます。すると、 Sから上記のように構築されますが、最初の行がすべて負であるC は、歪対称会議行列です。

この構成は、偶数nに対してn次の歪対称会議行列が存在するかどうかを決定する問題のほんの一部しか解決しません。

一般化

n次の会議行列は、単にW ( n, n −1 )の形の重み行列として定義されることもあります。ここで、 W ( n,w )は、{−1, 0, +1}の要素を持ち、W W T = w Iを満たすサイズnの正方行列である場合 、重みw > 0でn次の正方行列と呼ばれます。[2]この定義を用いると、零要素が対角上にある必要はなくなりますが、それでも各行と各列に零要素が1つずつ存在する必要があることは容易にわかります。例えば、行列

この緩い定義は満たしますが、ゼロ要素が対角線上にあることを要求するより厳密な定義は満たしません。

会議デザインは、会議行列を非直角行列に一般化したものである。会議デザインCは、{−1, 0, +1}の要素を持ち、を満たす行列である。ここで、 は単位行列であり、各行には最大1つの零点が含まれる。会議デザインの折り返しデザインは、決定的スクリーニングデザインとして用いることができる。[9] [10]

電話会議回線

単純な2ポート会議ネットワーク

ベレヴィッチは、 nが38までのすべての値に対して会議マトリックスの完全な解を得、さらにいくつかのより小さなマトリックスの回路も提供した。理想的な会議ネットワークとは、信号損失が複数の会議加入者ポート間で信号が分割されることのみに起因するネットワークである。つまり、ネットワーク内に損失がない。ネットワークは理想的な変圧器のみで構成され、抵抗は含まれてはならない。nポートの理想的な会議ネットワークは、 n次の会議マトリックスが存在する場合にのみ存在する。例えば、電話機や回線中継器で2線式から4線式への変換に用いられる、よく知られたハイブリッド変圧器回路を用いて3ポートの会議ネットワークを構築できる。しかし、3次の会議マトリックスは存在せず、この回路は理想的な会議ネットワークを構成しない。信号を損失させる整合のために抵抗が必要であり、そうでなければ不整合によって信号が失われる。[11]

  • ベレヴィッチによる6ポートの理想的な会議ネットワークの実装
    ベレヴィッチによる6ポートの理想的な会議ネットワークの実装
  • ベレヴィッチによる10ポートの理想的な会議ネットワークの実装
    ベレヴィッチによる10ポートの理想的な会議ネットワークの実装

前述のように、会議行列が存在するための必要条件は、n −1 が2つの平方の和であることである。n −1 に対して2つの平方の和が複数存在する場合、対応する会議ネットワークには本質的に異なる複数の解が存在する。この状況はnが26および66のときに発生する。n −1 が完全な平方（n = 2, 10, 26, ...）の場合、ネットワークは特に単純になる。 [12]

注記

  1. ^ Greig Malcolm (2006). 「コンファレンス行列と近似分解可能な2-(2k+1,k,k-1)設計の共存について」. Journal of Combinatorial Theory, Series A. 113 ( 4): 703– 711. doi : 10.1016/j.jcta.2005.05.005 .
  2. ^ ab Gropp Harald (2004). 「軌道行列についてさらに詳しく」.離散数学電子ノート. 17 : 179–183 . doi :10.1016/j.endm.2004.03.036.
  3. ^ ベレヴィッチ 1950、231–244 ページ
  4. ^ コルボーンとディニッツ、2007、p. 19
    ヴァン・リント＆ウィルソン、2001、p. 98
    スティンソン、2004 年、p. 200
  5. ^ Raghavarao, D. (1959). 「いくつかの最適な計量設計」. Annals of Mathematical Statistics . 30 (2): 295– 303. doi : 10.1214/aoms/1177706253 . MR  0104322.
  6. ^ ab van Lint JH、ザイデル JJ (1966)。 「楕円幾何学における等辺点集合」。Indagationes Mathematicae。28 : 335–348 .
  7. ^ ベレヴィッチ 1950、240ページ
  8. ^ スティンソン 2004、78ページ
  9. ^ シャオ、リン、バ​​イ 2012
  10. ^ シェーン、エエンデバック＆グース 2018
  11. ^ ベレヴィッチ 1950、240～242ページ
  12. ^ ベレヴィッチ 1950、242ページ

参考文献

  • ベレヴィッチ, V (1950). 「2 n端末ネットワークの理論と会議電話への応用」.電気通信技術ジャーナル. 27.国際電話電信会社: 231–244 . ISSN  0013-4252. OCLC  989599917.
  • Goethals, JM; Seidel, JJ (1967). 「対角成分がゼロの直交行列」. Canadian Journal of Mathematics . 19 : 1001–10 . doi : 10.4153/cjm-1967-091-8 . S2CID  197456608.
  • Xiao, Lili; Lin, Dennis KJ; Bai, Fengshan (2012). 「カンファレンスマトリックスを用いた決定的スクリーニングデザインの構築」. Journal of Quality Technology . 44 (1): 2– 8. doi :10.1080/00224065.2012.11917877. S2CID  116145147.
  • Goethals, JM; Seidel, JJ (1991). 「対角線が零の直交行列」Corneil, DG ; Mathon, R. (編). 『幾何学と組合せ論：JJ Seidel 選集』 Academic Press. pp.  257– 266. doi :10.1016/B978-0-12-189420-7.50024-4. ISBN 978-0-12-189420-7. OCLC  680171333。いくつかの記事は、会議マトリックスとそのグラフに関連しています。
  • Colbourn, Charles J.; Dinitz, Jeffrey H. (2007). Handbook of Combinatorial Designs (第2版). CRC Press. ISBN 978-1-58488-506-1. OCLC  666979105。
  • ヴァン・リント、ヤコブス・ヘンドリクス著、ウィルソン、リチャード・マイケル著 (2001). 『組合せ論講座』（第2版）ケンブリッジ大学出版局. ISBN 0-521-00601-5. OCLC  667085103。
  • スティンソン、ダグラス・ロバート (2004).組み合わせデザイン：構築と分析. シュプリンガー. ISBN 0-387-95487-2. OCLC  757107627。
  • Schoen, Eric D.; Eendebak, Pieter T.; Goos, Peter (2018). 「決定的スクリーニングデザインのための分類基準」Annals of Statistics . 47 (2): 1179– 1202. JSTOR  26581895.

さらに読む

  • Balonin, NA; Seberry, J. (2014). 「レビューと新しい対称会議マトリックス」(PDF) .情報科学. 71 (4): 2– 7. RIS 91975 – ウーロンゴン大学Research Online経由.付録には、1002 までのすべての既知および可能性のある会議マトリックスがリストされています。
Retrieved from "https://en.wikipedia.org/w/index.php?title=Conference_matrix&oldid=1296011845"