リオーダン配列

リオーダン配列は、次数0 と次数 1 の2 つの形式的な冪級数から構成される無限下三角行列です。 ${\displaystyle D}$${\displaystyle d(t)}$${\displaystyle h(t)}$${\displaystyle d_{n,k}=[t^{n}]d(t)h(t)^{k}}$

リオーダン配列はリオーダン群の要素である。^[1]数学者ルイス・W・シャピロによって定義され、ジョン・リオーダンにちなんで名付けられた。^[1] リオーダン配列の研究は、組合せ論、群論、行列理論、数論、確率、数列と級数、リー群とリー代数、直交多項式、グラフ理論、ネットワーク、単峰性数列、組合せ恒等式、楕円曲線、数値近似、漸近解析、データ解析などの他の分野から影響を受け、また貢献している分野である。リオーダン配列は、生成関数、コンピュータ代数システム、形式言語、パスモデルなどのツールも統合する。^[2]この主題に関する書籍、例えば『リオーダン配列』^[1] (Shapiro et al., 1991) が出版されている。

形式的冪級数(ここで は複素係数を持つ形式的冪級数の環)は、 のとき、位数を持つと言われます。位数 の形式的冪級数の集合について と書きます。冪級数が乗法逆数(つまり は冪級数である) を持つのは、位数 0 を持つ場合、つまり に属する場合のみです。また、 の合成逆数を持つため、 となる冪級数が存在するのは、位数 1 を持つ場合、つまり に属する場合のみです。 ${\displaystyle a(x)=a_{0}+a_{1}x+a_{2}x^{2}+\cdots =\sum _{j\geq 0}a_{j}x^{j}\in \mathbb {C} [[x]]}$${\displaystyle \mathbb {C} [[x]]}$ ${\displaystyle r}$${\displaystyle a_{0}=\cdots =a_{r-1}=0\neq a_{r}}$${\displaystyle {\mathcal {F}}_{r}}$${\displaystyle r}$${\displaystyle a(x)}$${\displaystyle 1/a(x)}$${\displaystyle {\mathcal {F}}_{0}}$${\displaystyle {\bar {a}}}$${\displaystyle {\bar {a}}(a(x))=x}$${\displaystyle {\mathcal {F}}_{1}}$

前述のように、リオーダン配列は通常、一対のべき級数 によって定義されます。名前の「配列」という部分は、を によって定義される複素数の配列に関連付けることに由来しています(ここで「」は「のの係数」を意味します)。したがって、配列の列は、べき級数の係数のシーケンスで構成されます。特に、列 0 は を決定し、 はべき級数 によって決定されます。 は次数 0 であるため、乗法逆元があり、配列の列 1 から を復元できます。は次数 1 であるため、 は次数であり、 も同様です。したがって、配列は下三角であり、主対角線上で等比数列を示します。また、一対のべき級数をその三角配列に送るマップは単射 であることもわかります。 ${\displaystyle (d(t),h(t))\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}}$${\displaystyle (d(t),h(t))}$${\displaystyle d_{n,k}:=[t^{n}]d(t)h(t)^{k},}$ ${\displaystyle n,k\in \mathbb {N} }$${\displaystyle [t^{n}]\cdots }$${\displaystyle t^{n}}$${\displaystyle \cdots }$${\displaystyle k}$${\displaystyle d(t)h(t)^{k};}$${\displaystyle d(t).}$${\displaystyle d(t)}$${\displaystyle h(t)}$${\displaystyle h(t)=d(t)^{-1}d(t)h(t)}$${\displaystyle h(t)}$${\displaystyle h(t)^{k}}$${\displaystyle k}$${\displaystyle d(t)h(t)^{k}.}$${\displaystyle d_{n,k}}$${\displaystyle (d_{k,k})_{k\geq 0}=(d_{0}h_{1}^{k})_{k\geq 0}}$${\displaystyle (d(t),h(t))\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}}$

リオルダン配列の例は、次の冪級数のペアで示される。

${\displaystyle \left({\frac {1}{1-x}},{\frac {x}{1-x}}\right)=\left(\sum _{j\geq 0}x^{j},\sum _{j\geq 0}x^{j+1}\right)\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}}$。

このペアがパスカル行列とも呼ばれる 二項係数の無限三角配列を生成することを示すのは難しくありません。${\displaystyle d_{n,k}={\binom {n}{k}}}$

${\displaystyle P=\left({\begin{array}{ccccccc}1&&&&&&\\1&1&&&&&\\1&2&1&&&&\cdots \\1&3&3&1&&&\\1&4&6&4&1&&\\&&\vdots &&&&\ddots \end{array}}\right)}$。

証明:が 係数列 を伴うべき級数である 場合、べき級数のコーシー乗法により、 となる 。 したがって後者の級数は係数列 を伴うため 、 となる 。任意 の を固定し、 がパスカル配列の列を表す 場合、 となる 。この議論により、 が係数列としてパスカル配列の列を持つ を帰納的に確認することができる。 ${\displaystyle q(x)=\sum _{j\geq 0}q_{j}x^{j}}$${\displaystyle (q_{0},q_{1},q_{2},...)}$${\displaystyle q(x){\frac {x}{1-x}}=\sum _{j\geq 0}(0+q_{0}+q_{1}+\cdots +q_{j-1})x^{j}.}$${\displaystyle (0,q_{0},q_{0}+q_{1},q_{0}+q_{1}+q_{2},....)}$${\displaystyle [t^{n}]q(x){\frac {x}{1-x}}=q_{0}+\cdots +q_{n-1}}$${\displaystyle k\in \mathbb {Z} _{\geq 0}.}$${\displaystyle q_{n}={\binom {n}{k}}}$${\displaystyle (q_{n})_{n\geq 0}}$${\displaystyle k}$${\displaystyle \sum _{j=0}^{n-1}q_{j}=\sum _{j=0}^{n-1}{\binom {j}{k}}={\binom {n}{k+1}}}$${\displaystyle k}$${\displaystyle {\frac {1}{1-x}}\left({\frac {x}{1-x}}\right)^{k}}$${\displaystyle k}$

以下は、リオーダン配列についてよく使われる事実です。無限下三角行列に適用される行列乗算規則は有限和のみを導き、2 つの無限下三角行列の積は無限下三角行列になることに注意してください。次の 2 つの定理は、シャピロら^{[1]によって最初に述べられ、証明されました。彼らは、}ジャンカルロ ロータの論文とローマ書^[3]で見つけた研究を修正したと述べています。

定理: a. およびを、無限下三角行列として見たリオルダン配列とします。すると、これらの行列の積は、 形式的な冪級数のペアに関連付けられた配列となり、それ自体がリオルダン配列となります。 ${\displaystyle (a(x),b(x))}$${\displaystyle (c(x),d(x))}$${\displaystyle (a(x)c(b(x)),d(b(x)))}$

b. この事実は、Riordan配列の乗算「」の定義を、冪級数のペアとして見た場合の ${\displaystyle *}$

${\displaystyle (a(x),b(x))*(c(x),d(x))=(a(x)c(b(x)),d(b(x))}$

証明:は次数が 0なので、は次数が 0 である ことは明らかです。同様に、 が成り立つこと も意味します 。したがって、はリオーダン配列です。 行列をリオーダン配列として定義します。定義により、その- 番目の列は、べき級数 の係数のシーケンスです 。 この行列を右からシーケンスで乗算すると、 結果として列の線形結合が得られ、これはべき級数の線形結合、つまり として読み取ることができます。 したがって 、 シーケンスをべき級数でコード化されたものとして見ると、 であることが示されました。 ここで、 は、べき級数レベルでの行列乗算との対応を示す記号です。 リオーダン配列に単一のべき級数を乗じました。 ここで、を行列として見た別のリオーダン配列とします。 の積を作成できます。この積の - 番目の列は 、の - 番目の列と乗算されます。後者はべき級数 に対応するので 、上記から、 の- 番目の列は に対応すること がわかります。 これはに出現するすべての列インデックスに当てはまるので 、パート a を示しました。これでパート b が明らかになりました。 ${\displaystyle a(x),c(x)}$${\displaystyle a(x)c(b(x))}$${\displaystyle b(x),d(x)\in {\mathcal {F}}_{1}}$${\displaystyle d(b(x))\in {\mathcal {F}}_{1}.}$${\displaystyle (a(x)c(b(x)),d(b(x)))}$${\displaystyle M}$${\displaystyle (a(x),b(x)).}$${\displaystyle j}$${\displaystyle M_{*,j}}$${\displaystyle a(x)b(x)^{j}}$${\displaystyle (r_{0},r_{1},r_{2},...)^{T}}$${\displaystyle M}$${\displaystyle \sum _{\nu \geq 0}r_{\nu }M_{*,\nu }=\sum _{\nu \geq 0}r_{\nu }a(x)b(x)^{\nu }=a(x)\sum _{\nu \geq 0}r_{\nu }b(x)^{\nu }.}$${\displaystyle (r_{0},r_{1},r_{2},...)^{T}}$${\displaystyle r(x),}$${\displaystyle (a(x),b(x))*r(x)=a(x)r(b(x)).}$${\displaystyle *}$${\displaystyle (a(x),b(x))}$${\displaystyle (c(x),d(x))}$${\displaystyle (a(x),b(x))(c(x),d(x))}$${\displaystyle j}$${\displaystyle (a(x),b(x))}$${\displaystyle j}$${\displaystyle (c(x),d(x)).}$${\displaystyle c(x)d(x)^{j}}$${\displaystyle j}$${\displaystyle (a(x),b(x))(c(x),d(x))}$${\displaystyle a(x)c(b(x))d(b(x))^{j}}$${\displaystyle j}$${\displaystyle (c(x),d(x))}$${\displaystyle \Box }$

定理:上記で定義した積 ' ' を持つリオルダン配列の族は、リオルダン群と呼ばれる群を形成します。^[1]${\displaystyle *}$

証明:乗算 ' ' の結合法則は、行列の乗算の結合法則から導かれます。次に、 に注意してください。 は左中立元です。最後に、 は べき級数 の左逆である と主張します。このためには、計算 を確認してください。よく知られているように、左中立元を持ち、各要素に左逆がある結合構造はグループです。 ${\displaystyle *}$${\displaystyle (1,x)*(c(x),d(x))=(1\cdot c(x),d(x))=(c(x),d(x))}$${\displaystyle (1,x)}$${\displaystyle (c({\bar {d}}(x))^{-1},{\bar {d}}(x))}$${\displaystyle (c(x),d(x))}$${\displaystyle (c({\bar {d}}(x))^{-1},{\bar {d}}(x))*(c(x),d(x))}$ ${\displaystyle =((c({\bar {d}}(x))^{-1}c(d(x)),d({\bar {d}}(x)))=(1,x)}$${\displaystyle \Box }$

もちろん、すべての可逆無限下三角配列がリオーダン配列であるわけではありません。ここではリオーダン配列の便利な特徴付けを示します。次の結果は明らかにロジャーズによるものです。 ^[4]

定理：無限下三角配列がリオルダン配列である場合、それ は伝統的に-シーケンスと呼ばれるシーケンスが存在し、${\displaystyle D=(d_{n,k})_{n,k\geq 0}}$${\displaystyle A}$${\displaystyle A=(a_{0}\neq 0,a_{1},...)}$

${\displaystyle *_{1}:d_{n+1,k+1}=a_{0}d_{n,k}+a_{1}d_{n,k+1}+a_{2}d_{n,k+2}+\cdots =\sum _{j\geq 0}a_{j}d_{n,k+j}}$

証明。^[5] を から生じるリオーダン配列とします。 は位数が1なので、 はリオーダン配列であり、群の性質により、 となるリオーダン配列が存在することになります。左辺を計算 すると となり 、比較すると となります。もちろん はこの方程式の解です。 は合成が可逆であるため、一意です。 したがって、方程式を次のように書き直すことができます。${\displaystyle \Rightarrow :}$${\displaystyle D}$${\displaystyle (d(t),h(t)).}$${\displaystyle d(t)\in {\mathcal {F}}_{0},}$ ${\displaystyle d_{0,0}\neq 0.}$${\displaystyle h(t)}$${\displaystyle (d(t)h(t)/t,h(t))}$${\displaystyle (A(t),B(t))}$${\displaystyle (d(t),h(t))*(A(t),B(t))=(d(t)h(t)/t,h(t)).}$${\displaystyle (d(t)A(h(t)),B(h(t))}$${\displaystyle B(h(t))=h(t).}$${\displaystyle B(t)=t}$${\displaystyle B}$${\displaystyle (d(t),h(t))*(A(t),t)=(d(t)h(t)/t,h(t)).}$

さて、行列の乗法則から、この後者の式の左辺の項は ${\displaystyle n,k}$

${\displaystyle \sum _{j\geq 0}d_{n,j}(A(t),t)_{j,k}=\sum \limits _{j\geq 0}d_{n,j}[t^{j}]A(t)t^{k}=\sum \limits _{j\geq 0}d_{n,j}[t^{j-k}]A(t)=\sum \limits _{j\geq 0}d_{n,j}a_{j-k}=\sum \limits _{j\geq 0}a_{j}d_{n,k+j}.}$

一方、上の式の右辺の項は ${\displaystyle n,k}$

${\displaystyle t^{[n]}{\frac {1}{t}}d(t)h(t)h(t)^{k}=t^{[n+1]}d(t)h(t)^{k+1}=d_{n+1,k+1},}$

となる。 から、 すべての要素に対してとなり 、対角要素がゼロでないことが分かっているので、 となる。 式を使うと 、要素が分かっているすべての要素を計算できる 点に注意する。${\displaystyle *_{1}}$${\displaystyle d_{n+1,n+1}=a_{0}d_{n,n}}$${\displaystyle n\geq 0}$${\displaystyle a_{0}\neq 0.}$${\displaystyle *_{1}}$${\displaystyle (d_{n,0})_{n\geq 0}.}$

${\displaystyle \Leftarrow :}$ ここで、三角形配列があり、ある数列の方程式があることを前提と します。 をその数列の生成関数とし、方程式から を定義します。 の次数が 1 であることがわかる ので、 との係数について結果として得られる方程式を解くことができることを確認します。を数列の生成関数とします。すると、ペアについて次 が見つかります。 これは、証明の最初の部分で見つけた方程式とまったく同じであり、その理由付けを行っていくと、 のような方程式が見つかります。(またはその係数のシーケンス) によって他のエントリが決まることから、開始時の配列が推定した配列であることがわかります。したがって、 の配列はRiordan 配列です。 ${\displaystyle *_{1}}$${\displaystyle (a_{j})_{j\geq 0}.}$${\displaystyle A(t)}$${\displaystyle h(t)}$${\displaystyle tA(h(t))=h(t).}$${\displaystyle h;}$${\displaystyle a_{0}\neq 0}$${\displaystyle h(t)}$${\displaystyle d(t)}$${\displaystyle (d_{0,0},d_{1,0},d_{2,0},...).}$${\displaystyle (d(t),h(t))}$${\displaystyle (d(t),h(t))*(A(t),t)=(d(t)A(h(t)),h(t))=(d(t)h(t)/t,h(t)).}$${\displaystyle *_{1}}$${\displaystyle d(t)}$${\displaystyle *_{1}}$${\displaystyle \Box }$

明らかに、 -シーケンスだけでは、Riordan 配列に関するすべての情報が得られるわけではありません。 -シーケンスの他に、以下の -シーケンスも研究されており、有用であることが示されています。 ${\displaystyle A}$${\displaystyle A}$${\displaystyle Z}$

定理。対角列に ゼロを含まない無限下三角配列を と する。すると、 次のような 一意の列が存在する。${\displaystyle (d_{n,k})_{n,k\geq 0}}$${\displaystyle (d_{n,n})_{n\geq 0}}$${\displaystyle Z=(z_{0},z_{1},z_{2},...)}$

${\displaystyle d_{n+1,0}=z_{0}d_{n,0}+z_{1}d_{n,1}+z_{2}d_{n,2}+\cdots =\sum \limits _{j\geq 0}z_{j}d_{n,j},\quad n=0,1,2,3,...}$

証明:配列の三角形性により、主張されている方程式は と同等です 。 この方程式は であり、一意に 計算できるためです。一般に、 が既知であれば、 を 一意に計算できます。${\displaystyle d_{n+1,0}=\sum _{j=0}^{n}z_{j}d_{n,j}.}$${\displaystyle n=0,}$${\displaystyle d_{1,0}=z_{0}d_{0,0}}$${\displaystyle d_{0,0}\neq 0,}$${\displaystyle z_{0}}$${\displaystyle z_{0},z_{1},...,z_{n-1}}$${\displaystyle d_{n+1,0}-\sum _{j=0}^{n-1}z_{j}d_{n,j}=z_{n}d_{n,n}}$${\displaystyle z_{n}}$${\displaystyle \Box }$