Compu a ional and Applied Ma hema ics (2022) 41:148
h ps://doi.o g/10.1007/s40314-022-01858-7
New ad ances on (pseudo)dig aphs and e olu ion algeb as
M. Ceballos1
Recei ed: 16 No embe 2021 / Re ised: 18 Ma ch 2022 / Accep ed: 28 Ma ch 2022
© The Au ho (s) unde exclusi e licence o Sociedade B asilei a de Ma emá ica Aplicada e Compu acional 2022
Abs ac
In his pape , new ad ances conce ning he link be ween e olu ion algeb as and (pseudo)dig aph
a e shown. Some impo an elemen s ha can be ead om he (pseudo)dig aph ha is asso-
cia ed wi h an e olu ion algeb a a e s udied. Mo eo e , se e al esul s conce ning sol abili y,
nilpo ency, and he p ese a ion o hem unde he g aph union ope a ion a e p o ed. To com-
plemen he heo e ical s udy, an algo i hmic me hod has been implemen ed. This is de o ed o
compu ing he nilpo ency index o a nilpo en e olu ion algeb a using i s associa ed dig aph.
Keywo ds (Pseudo)Dig aph ·E olu ion algeb a ·De i ed algeb a ·Algo i hm
Ma hema ics Subjec Classi ica ion 17D92 ·05C25 ·05C20 ·05C85 ·05C90 ·68W30 ·
68R10
1 In oduc ion
Nowadays, one o he mos impo an and ele an esea ch in Ma hema ics is inding and
s udying new links be ween di e en ields. Al e na i e echniques and p ocedu es allow
esea che s o sol e many open p oblems, imp o e well-known heo ies, and achie e new
esul s. This pape deals wi h he link be ween e olu ion algeb as and G aph Theo y. In
2006, Tian and Voj echo sky in oduced e olu ion algeb as (see Tian and Voj echo sky
2006). La e , Tian se he basic concep s o e olu ion algeb as in Tian (2008). These alge-
b as lie be ween dynamical sys ems and non-associa i e algeb as. F om an algeb aic poin
o iew, e olu ion algeb as a e Banach non-associa i e algeb as, and dynamically, hey a e
a disc e e dynamical sys em. In Cab e a e al. (2016), some gene al algeb aic p ope ies
o e olu ion algeb as we e s udied. The au ho s analyzed e olu ion ideals, e olu ion sub-
algeb as, non-degene acy, and simple and i educible e olu ion algeb as. The e exis many
connec ions be ween hese algeb as and o he ma hema ical ields such as g aph heo y,
Communica ed by Ca los Hoppen.
BM. Ceballos
[email p o ec ed]
1Depa amen o de Ingenie ía, Uni e sidad Loyola Andalucía, A . de las Uni e sidades, s/n, 41704 Dos
He manas, Se ille, Spain
0123456789().: V,- ol 123
148 Page 2 o 17 M. Ceballos
g oup heo y, s ochas ic p ocesses, physics, e c. (Roziko and Tian (2011) can be seen, o
example). Mo eo e , he e a e many algeb aic open p oblems abou hese algeb as such as
hei classi ica ion. E olu ion algeb as ha e only been classi ied up o dimension 3 (Casas
e al. 2014; Cab e a e al. 2017). The e is also a classi ica ion o some amilies o nilpo en
e olu ion algeb as wi h dimension less han six (Hegazi and Abdelwahab 2015).
The o mula ion o Mendel’s law is ano he impo an applica ion o e olu ion algeb as.
In ac , Tian showed in Tian (2008) he close connec ion be ween e olu ion algeb as, Ma ko
chains, and non-Mendelian gene ics. Mo e conc e ely, e olu ion algeb as can be applied o
he inhe i ance o o ganelle genes, o example, o es ima e all possible mechanisms o se
he homoplasmy o cell popula ions. In his pape , we will deal wi h some algeb aic no ions
such as sol abili y and nilpo ency o e olu ion algeb as. Those concep s can be in e p e ed
biologically as he ac ha some o he o iginal gene a o s become ex inc a e a ce ain
numbe o gene a ions.
Cu en ly, G aph Theo y is an essen ial ool o sol e a huge numbe o p oblems in di e en
ma hema ical esea ch ields. In his way, semisimple algeb as can be s udied using g aphs,
since ees allow o de e mine he Dynkin diag ams ha a e associa ed o such algeb as
(Se e 1996). Mo eo e , G aph Theo y can be also applied o ep esen ini e-dimensional
algeb as (P imc 2000). The e a e se e al pape s in he li e a u e conce ning he ela ion
be ween G aph Theo y and e olu ion algeb as. Fi s , in 2008, Tian (2008) desc ibed a way
o associa e g aphs and dig aphs wi h e olu ion algeb as. He also deal wi h he con e se
p oblem. Tian ema ked in Tian (2008) ha he “in insic ela ion o e olu ion algeb as wi h
g aph heo y allows o analyze g aphs algeb aically [...] and g aph heo y can be used o deal
wi h non-associa i e algeb as”. In 2011, Roziko and Tian (2011) de ined e olu ion algeb as
associa ed wi h unc ion spaces gi en by ini e and connec ed g aphs. In 2015, Elduque and
Lab a (2015) used dig aphs o s udy i a ini e-dimensional e olu ion algeb a is nil. In 2016,
Cab e a e al. (2016) desc ibed a dig aph ela ed o a non-degene a e e olu ion algeb a, so
ha he la e is i educible i and only i he o me is connec ed. Mo e ecen ly, in 2019,
Cada id e al. (2019) desc ibed he space o de i a ions o e olu ion algeb as associa ed wi h
g aphs, depending on a pa i ion o hei se s o e ices. One yea la e (see Cada id e al.
2020), hey deal wi h he ela ionship be ween he e olu ion algeb a induced by a andom
walk on a g aph and he e olu ion algeb a de e mined by he same g aph. Also, in 2020,
Ceballos e al. (2020) desc ibed new (pseudo)dig aphs associa ed wi h e olu ion algeb as,
using his associa ion o classi y low-dimensional e olu ion algeb as.
The main goal o his cu en pape is o con inue wi h he esea ch line s a ed in Ca iazo
e al. (2004); Ceballos e al. (2011,2018), whe e a link among combina o ial s uc u es
and Lie o Leibniz algeb as was es ablished and, hence, se e al p ope ies on hose non-
associa i e algeb as can be ansla ed in o he G aph Theo y ield and ice e sa. This pape
ex ends hese s udies o he case o e olu ion algeb as o con inue wi h he esea ch line s a ed
in Ceballos e al. (2020); Elduque and Lab a (2015) analyzing he link among weigh ed
(pseudo)dig aphs and e olu ion algeb as. In Ceballos e al. (2020), he au ho s con inued he
wo k s a ed in Ca iazo e al. (2004) and de eloped in Ceballos e al. (2011,2015,2018)and
Cáce es e al. (2012), bu his ime o e olu ion algeb as. The s uc u e o his pape is di ided
in o se e al sec ions as ollows: Sec . 2 e iews some concep s and no a ion on bo h, e olu ion
algeb as and G aph Theo y. Nex , Sec . 3 ecalls he p ocedu e de o ed o associa ing a
weigh ed (pseudo)dig aph wi h an e olu ion algeb a like he one de eloped in Ceballos
e al. (2020) and Elduque and Lab a (2015). Nex , in Sec . 4, se e al new esul s conce ning
(pseudo)dig aphs and e olu ion algeb as a e ob ained. Fi s , some p ope ies ha can be
ead om he associa ed (pseudo)dig aph a e analyzed. Nex , we s udy how he sol abili y
and nilpo ency can be ansla ed in o he p ope ies o he associa ed (pseudo)dig aph and
123
New ad ances on (pseudo)dig aphs and e olu ion algeb as Page 3 o 17 148
he union ope a ion. A e ha , Sec . 5deals wi h he implemen a ion o an algo i hm o
compu e he nilpo ency index o a gi en nilpo en e olu ion algeb a using i s associa ed
dig aph. Finally, a complexi y and compu a ional s udy is ca ied ou in Sec . 6gi ing also
he compu ing ime and numbe o ope a ions o each s ep o he algo i hm.
2 P elimina ies
This sec ion ecalls some p elimina y concep s, esul s, and no a ions abou e olu ion alge-
b as and g aphs. Conce ning he o me , he eade can consul (Tian 2008). Rega ding he
la e , Ha a y (1969) is an in oduc o y e e ence o G aph Theo y.
2.1 E olu ion algeb as
Le Kbe a ield and E≡(E,+,·)an algeb a o e K. We say ha Eis an n-dimensional
e olu ion algeb a i we can ind a basis B={ei}n
i=1o he e olu ion algeb a, such ha
1) e2
i=n
k=1ci,kek,∀1≤i≤n;and
2) ei·ej=0, ∀1≤i= j≤n.
The basis Bis called na u al basis o he e olu ion algeb a E,ci,ja e known as he s uc u e
cons an s and A=(ci,j)is called he s uc u e ma ix. F om now on, we will s udy n-
dimensional e olu ion algeb as Eo e he ield o complex numbe s wi h na u al basis B.
E olu ion algeb as a e commu a i e and lexible (Tian and Voj echo sky 2006), bu hey
a e no associa i e o powe -associa i e.
One can ind wo di e en ypes o i ial e olu ion algeb as: he ones called ze o e olu ion
algeb as, which a e hose e i ying ei·ej=0, ∀1≤i,j≤nand he ones called non-ze o
e olu ion algeb as,whe ee2
i=ci,iei,∀1≤i≤n.
An e olu ion algeb a is non-degene a e i e2
i= 0, ∀1≤i≤n. O he wise, hey a e called
degene a e. Gi en an e olu ion algeb a Eand a ixed na u al basis B,anelemen e∈Eis
said o be absolu e nilpo en wi h espec o Bi e2=0, while e∈Eis idempo en i e2=e.
The se o all he absolu e nilpo en elemen s o Ewill be deno ed by An(E).
The annihila o o an e olu ion algeb a Eis de ined by Ann(E)={X∈E|X·Y=
0,∀Y∈E}. Clea ly, Ann(E)⊂An(E).
The de i ed se ies o a gi en ini e-dimensional e olu ion algeb a Eis
E(1)=E,E(2)=E·E, ..., E(k)=E(k−1)·E(k−1), ...
We say ha Eis sol able i ∃m∈N,m>1, such ha E(m)={0}.I E(m−1)={0}also holds,
hen mis known as he sol abili y index o sol index o Eand i is said ha Eis (m−1)-s ep
sol able.
The cen al se ies o a gi en ini e-dimensional e olu ion algeb a Eis
E<1>=E,E<2>=E·E, ..., E<k>=E<k−1>·E, ...
We say ha Eis nilpo en i ∃m∈N,m>1, such ha E<m>={0}.I E<m−1>={0}
also holds, hen mis known as he nilpo ency index o nilindex o Eand i is said ha Eis
(m−1)-s ep nilpo en .
No ice ha , o a gene al algeb a, he p e ious de ini ion co esponds o igh nilpo ency,
bu in e olu ion algeb as, bo h classes nilpo en and igh nilpo en a e he same.
123
148 Page 4 o 17 M. Ceballos
Ob iously, e e y nilpo en e olu ion algeb a is sol able, since E(i)⊆E<i>,∀i∈N.
Nilpo en e olu ion algeb as ha ing maximal nilpo ency index (n-s ep) a e called ili o m.
The de i ed algeb a o an e olu ion algeb a Ewill be deno ed by DE=E(2)=E<2>.
An e olu ion algeb a Eis pe ec i Eand DEa e equal.
2.2 G aph heo y
Ag aph is a pai G=(V,E),whe eVis called he non-emp y e ex-se (o node-se ) and
Eis called edge-se , which is gi en by uno de ed pai s o a couple o nodes. I is possible o
associa e a weigh o each edge. In case ha Eis gi en by o de ed pai s o e ices, we will
say ha Gis a di ec ed g aph o a dig aph.
An edge o a dig aph connec ing a e ex wi h i sel is usually known as a loop. A dig aph
con aining loops will be called pseudodig aph.
Th oughou he pape , weigh ed (pseudo)dig aphs wi h possible double edges will be
conside ed.
A e ex ∈Vin a gi en dig aph Gwill be called simple i he e ex has no loop.
O he wise, i will be non-simple.A e ex ∈Vis called sou ce ( esp. sink)i e e yedge
which is inciden wi h e ex has an o ien a ion om ( esp. owa d ). An example o
his is ep esen ed in Fig. 1.
A e ex in a g aph Gis said o be a lea i i is only adjacen o ano he e ex. Fo
example, in Fig. 1, all he e ices di e en om a e lea es.
The adjacency ma ix o a weigh ed pseudodig aph G=(V,E)is gi en by A=(aij),
whe e ai,jis he weigh o he edge connec ing e ex iwi h j. Ob iously, in case ha
bo h e ices a e no adjacen , ha weigh would be ze o.
A sequence o consecu i e e ices and edges in a g aph is known as a walk.Ag aphis
connec ed i he e is a walk be ween any pai o e ices. An a c is a walk whe e all he edges
and e ices a e di e en . The leng h o a walk is de ined by he numbe o i s edges. The
leng h o he sho es walk (also called geodesic) connec ing wo e ices in a g aph Gis he
dis ance be ween hem. The diame e o a g aph G,d(G), is he g ea es dis ance be ween
e e y pai o e ices.
Acycle C in a dig aph Gis a non-emp y walk in which he only epea ed e ices a e he
i s and las one. An o ien ed cycle will be a cycle in he dig aph espec ing he di ec ion
among he di ec ed edges o G. O he wise, we will call i a non-o ien ed cycle. A cycle wi h
leng h kwill be e e ed as k-cycle.
Example 1 In Fig. 2,C:1,a,2,b,3,c,4,d,1 is a non-o ien ed cycle wi h leng h 4, since c
is no a di ec ed edge om e ex 3 o 4. Fo example, C:1,a,2,e,4,d,1isano ien ed
cycle wi h leng h 3.
A (di ec ed) ee Tis a (di ec ed) connec ed g aph wi hou cycles.
Fig. 1 Sink and sou ce on e ex
, espec i ely
123
New ad ances on (pseudo)dig aphs and e olu ion algeb as Page 5 o 17 148
Fig. 2 Dig aph con aining
o ien ed and non-o ien ed cycles
Gi en wo g aphs G1=(V1,E1)and G2=(V2,E2), he union o bo h g aphs is de ined
by G=G1∪G2=(V1∪V2,E1∪E2). I bo h g aphs ha e no common e ices, we ob ain
a disconnec ed g aph wi h componen s G1and G2. In case ha bo h g aphs a e joined by a
unique common e ex, we will w i e G1˙
∪G2. The de ini ion o his ope a ion is simila o
dig aphs o pseudodig aphs.
3 Me hod o associa e (pseudo)dig aphs and e olu ion algeb as
In his sec ion, we in oduce wo di e en me hods. The i s one is de o ed o ob aining he
(pseudo)dig aph associa ed wi h a gi en e olu ion algeb a. We also show a ew esul s om
pape Ceballos e al. (2020) ha will be used la e . Finally, we desc ibe he me hod de o ed
o de ining he e olu ion algeb a associa ed wi h a ixed (pseudo)dig aph.
3.1 Ob aining he (pseudo)dig aph associa ed wi h an e olu ion algeb a
Fi s , we show how o ob ain he (pseudo)dig aph associa ed wi h a ixed e olu ion algeb a.
Le us deno e by Ean e olu ion algeb a o dimension n, na u al basis B={ei}n
i=1and law
e2
i=n
h=1ci,heh. The pai (E,B)can be associa ed wi h a weigh ed (pseudo)dig aph, G,
ollowing he me hod in oduced in Ceballos e al. (2020, Sec ion 3), which is as ollows:
a) Fo each ei∈B,wed aw e exi.
b) Fo e e y ci,i= 0 in he p oduc e2
i(1 ≤i≤n), we d aw a loop on e ex iwhose
weigh is gi en by ci,i.SeeFig.3.
c) Fo e e y ci,j= 0(i= j) in he p oduc e2
i(1 ≤i≤n), we d aw a di ec ed edge om
e ex i o jwhose weigh is gi en by ci,j.I cj,i= 0ine2
j, we d aw ano he di ec ed
edge, bu now om j o iand wi h weigh cj,i.SeeFigs.4and 5.
Consequen ly, e e y e olu ion algeb a wi h a na u al basis can be associa ed wi h a
(pseudo)dig aph as desc ibed in his sec ion. No ice ha isola ed e ices wi hou loops
co espond o basis ec o s in he annihila o o he algeb a. Le us no e ha his associa ion
is compa ible wi h he one conside ed in Elduque and Lab a (2015) and i is equi alen o
conside ing he s uc u e ma ix o Eas he adjacency ma ix o G.
Example 2 The e olu ion algeb a o e he complex numbe ield ( om now on, complex
e olu ion algeb a) wi h dimension 4 and non-ze o p oduc s e1·e1=e2−e3,e2·e2=
−e2+e3,e3·e3=e1−e4,e4·e4=e1+e4is associa ed wi h he (pseudo)dig aph shown
in Fig. 6.
F om now on, we will e e o Ceballos e al. (2020, P oposi ions 1 and 3). Fo he
con enience o he eade , we include hose p oposi ions he e.
123
148 Page 6 o 17 M. Ceballos
Fig. 3 Loop on i
Fig. 4 Di ec ed edge
Fig. 5 Double edge
Fig. 6 (Pseudo)dig aph
associa ed wi h a 4-dimensional
e olu ion algeb a
P oposi ion 1 Le Ebe a 1-dimensional e olu ion algeb a. Then, Eis associa ed wi h an
isola ed e ex wi h a possible loop.
P oposi ion 2 I a (pseudo)dig aph G con ains a cycle, hen he e olu ion algeb a Eassoci-
a ed wi h G is no nilpo en .
I an e olu ion algeb a Eis associa ed wi h a non-connec ed (pseudo)dig aph G, henE
leads o he di ec sum o simple ideals ha can be associa ed wi h e e y connec ed componen
o G. Bea ing his in mind and also Ceballos e al. (2020, P oposi ion 1), unless i is said, only
non- i ial connec ed (pseudo)dig aphs will be conside ed. I is also necessa y o poin ou
he ac ha he au ho s in Ceballos e al. (2020, P oposi ion 3) should ha e w i en “o ien ed
cycle” ins ead o jus “cycle”.
123
New ad ances on (pseudo)dig aphs and e olu ion algeb as Page 7 o 17 148
Fig. 7 Pseudodig aph o be
associa ed wi h an e olu ion
algeb a
3.2 Ob aining he e olu ion algeb a associa ed wi h a (pseudo)dig aph
Now, we see how o de ine he e olu ion algeb a associa ed wi h a ixed (pseudo)dig aph.
Le G=(V,E)be a pseudodig aph wi h V={1,...,n}. Then, Gcan be associa ed wi h
an e olu ion algeb a Ewi h na u al basis Bas ollows:
a) De ine he ec o space W={e1,...,en} om he se o e ices V.
b) In case ha i(1 ≤i≤n)isasink e ex,wede inee2
i=0.
c) I iis no a sink, hen e2
i=n
j=1ci,jej,whe e ci,jis he weigh o he edge om e ex
i o e ex j. No ice ha , i iis a non-simple e ex, hen ci,iwill be he weigh o he
loop on he e ex i. I he e is no di ec ed edge om e ex i o e ex j, henci,j=0.
Example 3 Le us conside he pseudodig aph G=(V,E)wi h V={1,2,3} ep esen ed
in Fig. 7. Then, he 3-dimensional e olu ion algeb a Eassocia ed wi h Gis he one gi en by
he na u al basis B={e1,e2,e3}and p oduc s e2
1=e2+e3,e2
3=−2e1+2e2−e3.
4 New esul s on (pseudo)dig aphs and e olu ion algeb as
In his sec ion, new esul s conce ning (pseudo)dig aphs and e olu ion algeb as a e shown.
Fi s , we analyze some p ope ies ha can be ead om he (pseudo)dig aph: he annihila o ,
he de i ed algeb a, and idempo en and absolu e nilpo en elemen s o an e olu ion algeb a.
A e ha , we show se e al esul s conce ning sol abili y (o non-sol abili y), nilpo ency,
and he p ese a ion o hem unde he union ope a ion. F om he e on, Gwill deno e he
(pseudo)dig aph associa ed wi h an e olu ion algeb a Eand a ixed na u al basis B ollowing
he p ocedu e indica ed in Sec . 3.
4.1 Reading p ope ies om he (pseudo)dig aph
This subsec ion is de o ed o s udying which p ope ies o e olu ion algeb as can be ead
om hei associa ed (pseudo)dig aph.
Lemma 1 Le us deno e by G he (pseudo)dig aph associa ed wi h an e olu ion algeb a E.
Then
Ann(E)=span{ei|iis a sink e ex}.
P oo I ollows om he de ini ion o a sink e ex and he me hod used in Ceballos e al.
(2020, Sec ion 3).
Rema k 1 No ice ha i Gwe e a non-connec ed (pseudo)dig aph associa ed wi h E, henG
may con ain isola ed e ices and we would ha e o add hose co esponding ec o s o he
123
148 Page 8 o 17 M. Ceballos
Fig. 8 Absolu e nilpo en elemen
om non-adjacen e ices
basis o Ann(E). Mo eo e , we would also ha e o include he ec o s associa ed wi h sink
e ices o each one o i s componen s.
Co olla y 1 Le G be he (pseudo)dig aph associa ed wi h E. Then, e e y sink e ex and
each simple isola ed e ex co esponds o an absolu e nilpo en elemen o E.
P oo I ollows om he ac ha Ann(E)⊂An(E).
Rema k 2 Absolu e nilpo en elemen s do no need o be o med om adjacen e ices o G.
Fo example, he 3-dimensional e olu ion algeb a Egi en by e2
1=e2,e2
3=−e2is associa ed
wi h he dig aph o Fig. 8and (e1+e3)2=e2
1+e2
3=0, so e1+e3is absolu e nilpo en .
Lemma 2 Le G deno e he (pseudo)dig aph associa ed wi h an e olu ion algeb a E.I a
e ex i o G is non-simple o a sou ce, hen he co esponding ec o eiis no an absolu e
nilpo en elemen o E.
P oo I iis a sou ce e ex o G, hene2
i=n
j=1ci,jejand ∃1≤k≤n, such ha ci,k= 0.
The e o e, e2
i= 0. In case ha iis a non-simple e ex o G, henihas a loop wi h weigh
ci,i= 0. Consequen ly, e2
i= 0. In bo h cases, we ob ain ei/∈An(E).
Rema k 3 No ice ha Lemma 2can be gene alized conside ing a e ex inciden wi h an
edge ha ing o ien a ion om i .
Lemma 3 Le G be he non-connec ed (pseudo)dig aph associa ed wi h an e olu ion algeb a
E. Then, e e y non-simple isola ed e ex o G co esponds o an idempo en elemen o E.
P oo Le G=(V,E),whe eV={i1,i2,...,in}and ik(1≤k≤n)is an isola ed e ex
o Gha ing a loop o weigh cik,ik= 0. Conside ing φ:E→Ede ined as ik=φ(eik)=
1
cik,ik
eik; ij=φ(eij)=eij,∀1≤j= k≤n, we ob ain ha { i1,..., in}is a na u al
basis o Ewhose associa ed pseudodig aph has a loop o weigh 1 on e ex ikand ikis an
idempo en elemen o E.
Rema k 4 No ice ha in Lemma 3, we a e conside ing he same na u al basis o he pseu-
dodig aph and he idempo en elemen . Mo eo e , in he p oo o ha Lemma, he basis
{eih}n
h=1and { ih}n
h=1a e equi alen , since he la e is ob ained om he o me by mul i-
plying some e ms by a non-ze o scala (see Boudi e al. 2022 o mo e in o ma ion abou
equi alen na u al basis). Thei associa ed (pseudo)dig aphs only di e in he weigh o he
loops.
Lemma 4 Le T be a di ec ed ee. Then, T con ains, a leas , a sink and a sou ce.
123
New ad ances on (pseudo)dig aphs and e olu ion algeb as Page 9 o 17 148
Fig. 9 Compu ing he de i ed algeb a o hese (pseudo)dig aphs
P oo As i is well known, Thas, a leas , wo lea es. I one o hose lea es is a sink and
ano he one is a sou ce, hen we a e done. Now, we assume ha all he lea es a e sou ces ( he
case in which all he lea es a e sinks is analogous). Ob iously, a lea canno ha e an edge
wi h o ien a ion om i and ano he edge wi h o ien a ion owa d i due o he own de ini ion
o lea . Le V={ 1,...,
n}be he se o e ices o T,whe e{ 1,...,
i}a e he lea es.
Le Pbe he longes possible walk ollowing he di ec ion o he edges and s a ing on he
lea 1. We assume ha jis he end o he walk P.I 1<j≤i, hen he lea jis no a
sou ce and we ob ain a con adic ion. I j>i, hen he e is no edge wi h o ien a ion om
jdue o he maximali y o he walk Pand he ac ha Tcon ains no cycles. The e o e, j
is a sink e ex.
Lemma 5 Le G he connec ed (pseudo)dig aph associa ed wi h E. I is e i ied ha :
a) DE=span n
h=1ci,heh|iis no a simple sink e ex.
b) I G con ains no cycles, hen Eis no pe ec .
P oo Fi s , i is i ial ha DE=span({e2
i|1≤i≤n})=spann
h=1ci,heh.Le
us no e he e is no edge di ec ed om a simple sink e ex. The e o e, we conclude ha a)
holds. In case ha Gcon ains no cycle, hen Gis a ee. Acco ding o Lemma 4,Gcon ains
a leas a sou ce e ex j. Since he e is no edge di ec ed o j, we can a i m ha ej/∈DE
and, hence, Eis no pe ec .
Example 4 Le us conside he (pseudo)dig aphs Gand Ho Fig. 9.Wedeno ebyEand F he
complex e olu ion algeb as associa ed wi h Gand H, espec i ely. Then, Ehas a na u al basis
{ei}5
i=1wi h law e2
1=−e2,e2
2=e3+e5,e2
4=2e3.No ice ha Gcon ains no cycle, so,
acco ding o Lemma 5,Eis no pe ec . This is ue, since DE=span{−e2,2e3,e3+e5}=
span{e2,e3,e5}.
The e olu ion algeb a Fhas a na u al basis {ei}4
i=1, p oduc s e2
1=e2−e3,e2
2=
−e2−e3,e2
3=e1−e4,e2
4=e1+e4and de i ed algeb a DF=span{e2−e3,−e2−
e3,e1+e4,e1−e4}=span{e1,e2,e3,e4}. The pseudodig aph Hcon ains cycles and Fis
a pe ec e olu ion algeb a.
4.2 Sol abili y and nilpo ency
In his subsec ion, we use ees and non-o ien ed cycles o cha ac e ize nilpo en e olu ion
algeb as. Nex , he cases o sol able non-nilpo en and ili o m e olu ion algeb as a e shown
gi ing also a co ec ion o a con igu a ion in Ceballos e al. (2020, P oposi ion 8). Finally, we
deal wi h he union ope a ion s udying unde which condi ions sol abili y (o non-sol abili y)
and nilpo ency a e p ese ed.
123
148 Page 16 o 17 M. Ceballos
Fig. 16 Quo ien s be ween memo y and ime
Table 2 Numbe o ope a ions and complexi y o de o each s ep
S ep P ocedu e Complexi y N◦ope a ions
1p od O(n2)N1(n)=1+n(n−1)
2
2diag aph O(n4)N2(n)=n
j=1n
k=1N1(n)
3diame e O(n4)N3(n)=3+n
j=1n
k=1N1(n)
7 Conclusions
In his pape , new ad ances conce ning he link be ween e olu ion algeb as and g aphs ha e
been shown. Mo eo e , se e al elemen s ha can be ead om he (pseudo)dig aph associa ed
wi h an e olu ion algeb a ha e been s udied. We ha e also ob ained some esul s conce ning
sol abili y, nilpo ency, and hei p ese a ion unde he g aph union ope a ion. Finally, some
ou ines ha e been implemen ed o compu e he nilpo ency index o a nilpo en e olu ion
algeb a using i s associa ed dig aph.
F om he au ho ’s poin o iew, he ools and esul s shown in his pape may be use ul
and help ul o unde s anding he ela ion be ween e olu ion algeb as and (pseudo)dig aphs.
We ha e seen in he in oduc ion ha he e a e se e al pape s in he li e a u e dealing
wi h he link among e olu ion algeb as and G aph Theo y. Howe e , he e a e se e al open
p oblems o sol e. He e, we ha e a sho lis o he p oblems ound in hose e e ences and
o he s ha come up om his cu en pape :
1. S udy i i is possible o ansla e each p oblem in G aph heo y o he language o e olu ion
algeb as and he ecip ocal. This p oblem was s a ed by Tian (2008).
2. Find new aspec s and p ope ies o e olu ion algeb as ha can be ead om hei associa ed
(pseudo)dig aph.
3. De e mine which esul s o elemen s in g aphs a e independen o he chosen na u al basis
o he associa ed e olu ion algeb as.
The las wo open p oblems a ise om his cu en pape and o he s like Ceballos e al.
(2020). The au ho hopes o deal wi h hem in he nea u u e.
Acknowledgemen s The pape was pa ially suppo ed by US-1262169, P20_01056, MTM2016-75024-P
and FEDER.
123
New ad ances on (pseudo)dig aphs and e olu ion algeb as Page 17 o 17 148
Re e ences
Boudi N, Cab e a Y, Siles M (2022) Na u al amilies in e olu ion algeb as. Publ Ma 66(1):159–181
Cab e a Y, Siles M, Velasco MV (2016) E olu ion algeb as o a bi a y dimension and hei decomposi ions.
Linea Algeb a Appl 495:122–162
Cab e a Y, Siles M, Velasco MV (2017) Classi ica ion o h ee-dimensional e olu ion algeb as. Linea Algeb a
Appl. h ps://doi.o g/10.1016/j.laa.2017.02.015
Cada id P, Rodiño ML, Rod íguez PM (2019) Cha ac e iza ion heo ems o he spaces o de i a ions o
e olu ion algeb as associa ed o g aphs. Linea Mul ilinea Algeb a. h ps://doi.o g/10.1080/03081087.
2018.1541962 (In p ess)
Cada id P, Rodiño ML, Rod íguez PM (2020) The connec ion be ween e olu ion algeb as, andom walks and
g aphs. J Algeb a Appl 19(2):2050023
Ca iazo A, Fe nández LM, Núñez J (2004) Combina o ial s uc u es associa ed wi h Lie algeb as o ini e
dimension. Linea Algeb a Appl 389:43–61
Casas JM, Lad a M, Omi o BA, Roziko UA (2014) On e olu ion algeb as. Algeb a Colloquium 21:331–342
Cáce es J, Ceballos M, Núñez J, Pue as ML, Teno io AF (2012) Combina o ial s uc u es o h ee e ices
and Lie algeb as. In J Compu Ma h 89:1879–1900
Ceballos M, Núñez J, Teno io AF (2011) S udy o Lie algeb as by using combina o ial s uc u es. Linea
Algeb a Appl 436(2):349–363
Ceballos M, Núñez J, Teno io AF (2018) Fini e-dimensional Leibniz algeb as and combina o ial s uc u es.
Commun Con emp Ma h 20(1):34
Ceballos M, Núñez J, Teno io AF (2015) Malce algeb as and combina o ial s uc u es. Appl Ma h In Sci
9(2L):297–304
Ceballos M, Núñez J, Teno io AF (2020) Fini e dimensional e olu ion algeb as and (pseudo)dig aphs. Ma h
Me hods Appl Sci. h ps://doi.o g/10.1002/mma.6632
Elduque A, Lab a A (2015) E olu ion algeb as and g aphs. J Algeb a Appl 14(7):1550103
Ha a y F (1969) G aph heo y. Addison-Wesley, Reading
Hegazi AS, Abdelwahab H (2015) Nilpo en e olu ion algeb as o e a bi a y ields. Linea Algeb a Appl
486:345–360
Hegazi AS, Abdelwahab H (2015) Fi e-dimensional nilpo en e olu ion algeb as.a Xi :1508.07442 1
P imc M (2000) Basic ep esen a ions o classical a ine Lie algeb as. J Algeb a 228:1–50
Roziko UA, Tian JP (2011) E olu ion algeb as gene a ed by Gibbs measu es. Lobache skii J Ma h 32(4):270–
277
Se e JP (1996) Algèb es de lie semi-simples complexes. Benjamin Inc., New Yo k
Tian JP (2008) E olu ion algeb as and hei applica ions, lec u e no es in ma hema ics, ol 1921. Sp inge ,
Be lin
Tian JP, Voj echo sky P (2006) Ma hema ical concep s o e olu ion algeb as in non-Mendelian gene ics.
Quasig oups Rela Sys 14(1):111–122
Wil HS (2002) Algo i hms and complexi y, 2nd edn. AK Pe e s, Na ick. h ps://doi.o g/10.1201/b10621
Publishe ’s No e Sp inge Na u e emains neu al wi h ega d o ju isdic ional claims in published maps and
ins i u ional a ilia ions.
123
