مجموعة ريوردان

مصفوفة ريوردان هي مصفوفة مثلثية سفلية لانهائية ،${\displaystyle D}$، مُكوَّنة من سلسلتين رسميتين للقوى ،${\displaystyle d(t)}$من الرتبة 0 و${\displaystyle h(t)}$من الرتبة 1، بحيث${\displaystyle d_{n,k}=[t^{n}]d(t)h(t)^{k}}$.

مصفوفة ريوردان هي عنصر من عناصر زمرة ريوردان. ^{[ 1 ]} وقد عرّفها عالم الرياضيات لويس دبليو شابيرو، وسُميت نسبةً إلى جون ريوردان . ^{[ 1 ]} يُعدّ مجال دراسة مصفوفات ريوردان مجالًا متأثرًا بمجالات أخرى ، ومساهمًا فيها، مثل التوافقية ، ونظرية الزمر ، ونظرية المصفوفات ، ونظرية الأعداد ، والاحتمالات ، والمتتاليات والمتسلسلات ، وزمر لي وجبر لي ، ومتعددات الحدود المتعامدة ، ونظرية المخططات ، والشبكات ، والمتتاليات أحادية النمط ، والمتطابقات التوافقية، والمنحنيات الإهليلجية ، والتقريب العددي ، والتحليل التقاربي ، وتحليل البيانات . كما تُوحّد مصفوفات ريوردان أدواتٍ مثل الدوال المولدة ، وأنظمة الجبر الحاسوبي ، واللغات الرسمية ، ونماذج المسار . ^{[ 2 ]} وقد نُشرت كتبٌ حول هذا الموضوع، مثل كتاب "مصفوفة ريوردان" ^{[ 1 ]} (شابيرو، جيتو، ووان، وودسون، 1991).

سلسلة القوى الرسمية${\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)}$تكون متسلسلة قوى إذا وفقط إذا كانت من الرتبة 0، أي إذا وفقط إذا كانت تقع في${\displaystyle {\mathcal {F}}_{0}}$؛ ولها معكوس تركيبي ، أي أنه توجد متسلسلة قوى${\displaystyle {\bar {a}}}$بحيث${\displaystyle {\bar {a}}(a(x))=x}$إذا وفقط إذا كان ترتيبها 1، أي إذا وفقط إذا كانت تقع في${\displaystyle {\mathcal {F}}_{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};}$وبشكل خاص، يحدد العمود 0 متسلسلة القوى ويتم تحديده من خلالها${\displaystyle d(t).}$لأن${\displaystyle d(t)}$هي من الرتبة 0، ولها معكوس ضربي، وبالتالي يمكننا استعادة العمود 1 من المصفوفة${\displaystyle h(t)}$مثل${\displaystyle h(t)=d(t)^{-1}d(t)h(t)}$. منذ${\displaystyle h(t)}$الطلب رقم 1،${\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}}$إن تحويلها إلى مصفوفة مثلثية يكون أحاديًا .

فيما يلي بعض الحقائق الشائعة حول مصفوفات ريوردان. تجدر الإشارة إلى أن قواعد ضرب المصفوفات المطبقة على المصفوفات المثلثية السفلية اللانهائية تؤدي إلى مجاميع منتهية فقط، وأن حاصل ضرب مصفوفتين مثلثيتين سفليتين لانهائيتين ينتج عنه مصفوفة مثلثية سفلية لانهائية. وقد صاغ شابيرو وآخرون ^{[ 1 ]} النظريتين التاليتين وأثبتوهما لأول مرة، حيث وصفوهما بأنهما مستمدتان من نتائج في أوراق بحثية لجيان كارلو روتا وكتاب رومان ^{[ 3 ] .}

النظرية: أ. ليكن${\displaystyle (a(x),b(x))}$و${\displaystyle (c(x),d(x))}$لنفترض أن لدينا مصفوفات ريوردان، تُعتبر مصفوفات مثلثية سفلية لانهائية. عندئذٍ، يكون حاصل ضرب هذه المصفوفات هو المصفوفة المرتبطة بالزوج${\displaystyle (a(x)c(b(x)),d(b(x)))}$من سلسلة القوى الرسمية، والتي هي في حد ذاتها مصفوفة ريوردان.

ب. هذه الحقيقة تبرر تعريف عملية الضرب.${\displaystyle *}$تُعتبر مصفوفات ريوردان أزواجًا من متسلسلات القوى بواسطة

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

الدليل: بما أن${\displaystyle a(x)}$و${\displaystyle c(x)}$إذا كان الترتيب صفرًا، فمن الواضح أن${\displaystyle a(x)c(b(x))}$ترتيبه 0. وبالمثل،${\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 }$

نظرية: عائلة مصفوفات ريوردان المزودة بالناتج '${\displaystyle *}$يشكل التعريف المذكور أعلاه مجموعة: مجموعة ريوردان. ^{[ 1 ]}

البرهان: خاصية التجميع في عملية الضرب${\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 ]}${\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)}$إذا كان ترتيبها 1، فإن ذلك يترتب عليه أن${\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$ لنفترض الآن أنه بالنسبة لمصفوفة مثلثية، لدينا المعادلات التالية${\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)}$له رتبة 1. ليكن${\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 }$

من الواضح أن${\displaystyle A}$لا تحتوي التسلسلات وحدها على جميع المعلومات المتعلقة بمصفوفة ريوردان. في الواقع، إنها تحدد فقط${\displaystyle h(t)}$ولا يفرض أي قيود على${\displaystyle d(t)}$لتحديد${\displaystyle d(t)}$"أفقيًا"، وهو تعريف مماثل${\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 }$