Riordan array

En (riktig) Riordan-matris är en oändlig nedre triangulär matris , $D$ , konstruerad av två formella potensserier , $d(t)$ av ordningen 0 och ${\ displaystyle h(t)}$ av ordning 1, på ett sådant sätt att $d_{n,k}=[t^{n}] d(t)h(t)^{k}$ .

En Riordan-array är en del av Riordan-gruppen. Den skapades av matematikern Louis W. Shapiro och uppkallades efter matematikern John Riordan .

Studiet av Riordan-matriser är ett växande område som både påverkas av, och fortsätter sina bidrag till, andra områden som kombinatorik , gruppteori, matristeori, talteori, sannolikhet, sekvenser och serier, Lie-grupper och Lie-algebror, ortogonala polynom , grafteori , nätverk , Beal-förmodan , Riemann-hypotes, unimodala sekvenser, kombinatoriska identiteter, elliptiska kurvor , numerisk approximation, asymptotik och dataanalys. Riordan-arrayer är också ett kraftfullt förenande koncept, som binder samman viktiga verktyg: genererande funktioner , datoralgebrasystem, formella språk, vägmodell och så vidare.

Detaljer följer.

En formell potensserie $a(x)=a_{0}+a_ {1}x+a_{2}x^{2}+\cdots =\sum _{j\geq 0}a_{j}x^{j}\in \mathbb {C} [[x]]$ är sägs ha ordningen $r$ om $a_{0}=...=a_{r-1}=0\neq a_{r}.$ Skriv ${\mathcal {F}}_{r}$ för den formella potensen ordningsföljd $r.$ En potensserie $a(x)$ av ordningen 0 har en multiplikativ invers (dvs $1/a(x)$ är en potensserie ) om den har ordning 0, dvs. om den ligger i ${\mathcal {F}}_{0}$ ; den har en sammansättningsinvers som är att det finns en potensserie ${\bar {a}}$ så att ${\bar {a}}(a( x))=x$ om den har ordning 1, dvs om den ligger i ${\mathcal {F}}_{1}.$

Som nämnts definieras en Riordan-matris vanligtvis som ett par potensserier ${\displaystyle (a(t),b(t))\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}.} 'Array'-delen i sitt$ namn härrör från det faktum att man associerar till $(a(t),b(t))$ matrisen av komplexa tal definierade av $d_{n,k}:=[t^{n}]a(t)b(t)^{k},$$n,k\in \mathbb {N} =\mathbb {Z} _{\geq 0}.$ (Här $[t^{n}]...$ betyder koefficient för $t^{n}$ i ${\displaystyle \cdots } )$ . Så kolumn $k$ i arrayen består helt enkelt av sekvensen av koefficienter för potensserien $a(t)b(t)^{k};$ i synnerhet kolumn 0 bestämmer och bestäms av potensserien $a(t).$ Eftersom $a(t)$ är av ordningen 0, har den en multiplikativ invers och det följer att från arrayens kolumn 1 kan vi återställa ${\ displaystyle b(t)}$ som $b(t)=a(t)^{-1}a(t)b(t).$ Eftersom $b(t) =b_{1}t+b_{2}t^{2}+\cdots$ har ordning 1, $b(t)^{k}$ har ordningen $k$ och så har $a(t)b(t)^{k}.$ Det följer att arrayen $d_{n,k}$ är oändlig triangulär och uppvisar en geometrisk progression $(d_{k,k})_{k\geq 0}=(a_{0}b_{1}^{k})_{k\geq 0}$ på sin huvuddiagonal. Det följer också att kartan som associeras med ett par potensserier $(a(t),b(t))\in {\mathcal {F }}_{0}\times {\mathcal {F}}_{1}$ dess triangulära array är injektiv.

Ett exempel på en Riordan-matris ges av potensserieparet ${\displaystyle ({\frac {1}{1-x}},{\frac {x}{1-x}})=(\summa _{j\geq 0}x^{j},\summa _ {j\geq 0}x^{j+1})\in {\mathcal {F}}_{0}\times {\mathcal {F}}_{1}.} Det är inte svårt att visa att$ detta paret genererar den oändliga triangulära matrisen av binomialkoefficienter $d_{n,k}={n \choose k},$ även kallad Pascal-matris

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

Bevis. Om $q(x)=\sum _{j\geq 0}q_{j}x^{j}$ är en potensserie med tillhörande koefficientsekvens $(q_{0},q_{1},q_{2},...),$ sedan, med Cauchy multiplikation av potensserier, $q(x){\frac {x}{1-x}}=\sum _{j\geq 0}(0+q_{0}+q_{1}+\cdots +q_{j-1 })x^{j}.$ Så den senare serien har som koefficientsekvens $(0,q_{0}, q_{0}+q_{1},q_{0}+q_{1}+q_{2},...)$ och därav ${\displaystyle [t^{n}]q(x){\frac {x}{1-x}}=q_{0}+\cdots +q_{n-1}.} Fixa$ valfri $k\in \mathbb {Z} _{\geq 0}.$ Om $q_{n}={n \choose k},$ så att $(q_{n})_{n\geq 0}$ representerar kolumn $k$ i Pascal-matrisen, sedan $\sum _{j=0}^{n-1}q_{j}=\sum _{j=0}^{n-1}{j \choose k}={n \choose k+1 }.$ Detta argument gör det möjligt att se genom induktion på $k$ att ${\frac {1}{1-x}}({\frac {x }{1-x}})^{k}$ har kolumn $k$ i Pascal-matrisen som koefficientsekvens. $\Box$

Vi kommer att bevisa några mycket använda fakta om Riordan-arrayer. Observera att matrismultiplikationsreglerna som tillämpas på oändliga triangulära matriser endast leder till ändliga summor och produkten av två oändliga triangulära matriser är oändligt triangulär. De följande två satserna upptäcktes huvudsakligen av Shapiro och medarbetare, som säger att de modifierade arbete som de hittade i tidningar av Gian-Carlo Rota och boken Roman

Sats. a. Låt $(a(x),b(x))$ och $(c(x),d( x))$ vara Riordan-matriser, ses som oändliga lägre triangulära matriser. Då är produkten av dessa matriser den matris som är associerad med paret $(a(x)c(b(x)), d(b(x)))$ av formell potensserie som i sig är en Riordan-matris.

b. Detta faktum motiverar att definiera en multiplikation ` $*$ ' av Riordan-matriser sett som par av potensserier med

$(a( x),b(x))*(c(x),d(x))=(a(x)c(b(x)),d(b(x))$

Bevis. Eftersom $a(x),c(x)$ har ordning 0 är det tydligt att $a(x)c( b(x))$ har ordningen 0. På samma sätt innebär $b(x),d(x)\in {\mathcal {F}}_{1}$$d(b(x))\in {\mathcal {F}}_{1}.$ Så $(a(x)c(b(x)),d(b(x)))$ är en Riordan-array. Definiera en matris $M$ som Riordan-matrisen $(a(x),b(x)).$ Enligt definitioner är dess $j$ -th kolumn $M_{*,j}$ sekvensen av koefficienter för potensen serie $a(x)b(x)^{j}.$ Om vi ​​multiplicerar denna matris från höger med sekvensen $(r_{0} ,r_{1},r_{2},...)^{T}$ får vi som ett resultat en linjär kombination av kolumner av $M$ som vi kan läsa som en linjär kombination av potensserier, nämligen ${\displaystyle \sum _{\nu \geq 0}r_{\nu }M_{*,\nu }=\sum _{\nu \geq 0}r_{\nu }a(x)b(x)^ {\nu }=a(x)\summa _{\nu \geq 0}r_{\nu }b(x)^{\nu }.} Alltså,$ visningssekvens $(r_{0},r_{1},r_{2},...)^{T}$ som kodifierats av potensserien $r(x),$ vi visade ${\displaystyle (a(x),b(x))*r(x)=a(x)r(b(x)).} Här är ∗ {\displaystyle *} symbolen för att$ indikera $på$ potensen serienivå med matrismultiplikation. Vi multiplicerade en Riordan-matris $(a(x),b(x))$ med en enda potensserie. Låt nu $(c(x),d(x))$ vara en annan Riordan-array sedd som en matris. Man kan bilda produkten $),b(x))(c(x),d(x)).}$$j$ J -e kolumnen i denna produkt är bara $(a(x),b(x))$ multiplicerat med $j$ -te kolumnen av $(c(x),d(x)).$ Eftersom den senare motsvarar potensserien $c(x)d(x)^{j},$ det följer av ovan, att $j$ -:te kolumnen av $(a(x),b (x))(c(x),d(x))$ motsvarar $a(x)c(b(x))d(b(x))^{j}.$ Eftersom detta gäller för alla kolumnindex $j$ som förekommer i $(c(x),d(x))$ vi har visat del a. Del b är nu klar. $\Box$

Sats. Familjen av Riordan-arrayer utrustade med produkten ' $*$ ' definierad ovan bildar en grupp: Riordan-gruppen.

Bevis. Associativiteten för multiplikationen ` $*$ ' följer av associativiteten för matrismultiplikationen. Nästa not $(1,x)*(c(x),d(x))=(1\cdot c(x),d(x))=(c(x),d(x)).$ Så $(1,x)$ är ett vänsterneutralt element. Slutligen hävdar vi att $(c({\bar {d}}(x))^{-1},{\bar {d }}(x))$ är den vänstra inversen till potensserien $(c(x),d(x)).$ För detta kontrollera beräkningen $(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).} Som bekant är en associativ struktur där$ en vänster neutralt element finns och för varje element är en vänster invers en grupp. $\Box$

Naturligtvis är inte alla inverterbara oändliga nedre triangulära arrayer Riordan-arrayer. Här är en användbar karaktärisering för arrayerna som är Riordan. Följande resultat verkar bero på Rogers

Sats. En oändlig lägre triangulär array $D=(d_{n,k})_{n,k\geq 0}$ är en Riordan-array om och bara om det finns en sekvens som traditionellt kallas $A$ -sekvensen, $A=(a_{0}\neq 0,a_{1},...)$ sådant

${ \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}}$

Bevis. $\Rightarrow :$ Låt $D$ vara Riordan-matrisen som härrör från $(d(t),h(t)).$ Eftersom $d(t)\in {\mathcal {F}}_{0},$$d_{0,0}\neq 0.$ Eftersom $h(t)$ har ordning 1, följer det att $(d(t)h(t)/t,h(t))$ är en Riordan-array och av gruppegenskapen finns det en Riordan-array ${\ visningsstil (A(t),B(t))}$ så att ${\displaystyle (d(t),h(t))*(A(t),B(t))=(d(t)h(t)/t,h(t)).} Beräknar vänster$ hand sidavkastning $(d(t)A(h(t)),B(h(t))$ och så jämförelseavkastning $B(h(t))=h(t).$ Naturligtvis är ${\displaystyle B(t)=t} en$ lösningen till denna ekvation; den är unik eftersom $B$ är komposition inverterbar. Så vi kan skriva om ekvationen som $(d(t),h(t))*(A(t),t)=(d(t)h(t)/t ,h(t)).$

Nu från matrismultiplikationslagen är $n,k$ -posten på vänster sida av denna senare ekvation

$\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}=\summa \limits _{j\geq 0}d_{n,j}[t^{jk}]A(t)=\summa \limits _{j\geq 0}d_{n,j}a_{jk}=\sum \limits _{j\geq 0}a_{j}d_{n,k+j}.$

Å andra sidan är $n,k$ -posten för rhs i ekvationen ovan

$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},$

så att jag blir resultat. Från $*_{1}$ får vi även $d_{n+1,n+1}=a_{0}d_{n ,n}$ för alla $n\geq 0$ och eftersom vi vet att de diagonala elementen inte är noll, har vi $a_{0}\neq 0.$ Observera att med ekvation $*_{1}$ kan man beräkna alla poster genom att känna till posterna $(d_{n,0})_{n\geq 0}.$

$\Leftarrow :$ Antag nu att vi känner till en triangulär matris ekvationerna $*_{1}$ för någon sekvens $(a_{j})_{j\geq 0}.$ Låt $A(t)$ vara den genererande funktionen för den sekvensen och definiera $h(t ) )$ från ekvationen $tA(h(t))=h(t).$ Kontrollera att det är möjligt att lösa de resulterande ekvationerna för koefficienterna för $h;$ och eftersom $a_{0}\neq 0$ får man att $h(t)$ har ordning 1. Låt $d( t)$ vara den genererande funktionen för sekvensen $(d_{0,0},d_{1,0},d_{2,0},...).$ Sedan för paret $( d(t),h(t))$ finner vi $(d(t),h(t))*(A(t),t)=(d(t)A(h(t)),h(t))=(d(t)h( t)/t,h(t)).$ Detta är exakt samma ekvationer som vi har hittat i den första delen av beviset och genom att gå igenom dess resonemang hittar vi ekvationer som i $*_{1}$ . Eftersom $d(t)$ (eller sekvensen av dess koefficienter) bestämmer de andra posterna finner vi att den matris vi började med är den matris vi härledde. Så matrisen i $*_{1}$ är en Riordan-matris. $\Box$

Det är klart att $A$ -sekvensen ensam inte levererar all information om en Riordan-array. Förutom $A$ -sekvensen är det $Z$ -sekvensen som har visat sig vara förvånansvärt användbar.

Sats. Låt $(d_{n,k})_{n,k\geq 0}$ vara en oändlig nedre triangulär array vars diagonalsekvens ${ \displaystyle (d_{n,n})_{n\geq 0}}$ innehåller inte nollor. Sedan finns det en unik sekvens $Z=(z_{0},z_{1},z_{2},...)$ så att

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

Bevis. Beviset är enkelt: Genom triangulariteten hos arrayen är ekvationen som hävdas ekvivalent med ${\displaystyle d_{n+1,0}=\sum _{j=0}^{n}z_{j}d_{n,j}.} För n =, {\displaystyle n$ = $n=0,$ this equation is $d_{1,0}=z_{0}d_{0,0}$ and, as $d_{0,0}\neq 0,$ it allows computing $z_{0}$ uniquely. In general if $z_{0},z_{1},...,z_{n-1}$ are known already then $d_{n+1,0}-\sum _{j=0}^{n-1}z_{j}d_{n,j}=z_{n}d_{n,n}$ allows to compute $z_{n}$ uniquely. $\Box$

Helt nyligen dök boken upp som borde vara en värdefull källa för ytterligare information.