Finite dimensional evolution algebras and (pseudo)digraphs

Received: 16 July 2019 DOI: 10.1002/mma.6632 Finite dimensional evolution algebras and (pseudo)digraphs M. Ceballos1J. Núñez2Á. F. Tenorio3 1Dpto. de Ingeniería, Universidad Loyola Andalucía, Campus Palmas Altas, C/ Energía Solar 1, Ed. E, Seville, 41014, Spain 2Dpto. de Geometría y Topología, Universidad de Sevilla, Calle Tarfia, s/n, Seville, 41012, Spain 3Dpto. de Economía, Métodos Cuantitativos e Historia Económica Escuela Politécnica Superior, Universidad Pablo de Olavide, Ctra. Utrera km. 1, Seville, 41013, Spain Correspondence M. Ceballos, Dpto. de Ingeniería, Universidad Loyola Andalucía, Campus Palmas Altas, C/ Energía Solar 1, Ed. E, 41014 Seville, Spain. Email: [email protected] Communicated by: J. Vigo-Aguiar Funding information Ministerio de Ciencia e Innovación, Grant/Award Number: MTM2016-75024-P; MTM2016-75024-P; FEDER In this paper, we focus on the link between evolution algebras and (pseudo)digraphs. We study some theoretical properties about this association and determine the properties of the (pseudo)digraphs associated with each type of evolution algebras. We also analyze the isomorphism classes for each configuration associated with these algebras providing a new method to classify them, and we compare our results with the current classifications of twoand three-dimensional evolution algebras. In order to complement the theoretical study, we have designed and performed the implementation of an algorithm, which constructs and draws the (pseudo)digraph associated with a given evolution algebra and another procedure to study the solvability of a given evolution algebra. KEYWORDS algorithm, digraph, evolution algebra, isomorphism MSC CLASSIFICATION 17D92; 05C25; 05C20; 05C85; 05C90; 68W30; 68R10 1INTRODUCTION Evolution algebras were introduced in 2006 by Tian and Vojtechovsky in their study.1Later, Tian established the foundations of evolution algebras in his study.2The notion of these algebras lies between nonassociative algebras and dynamical systems. Algebraically, evolution algebras are nonassociative Banach algebras; dynamically, they represent discrete dynamical systems. The systematic study of evolution algebras of arbitrary dimension and of their algebraic properties was started in Cabrera et al.,3where the authors analyze evolution subalgebras, ideals, nondegeneracy, simple evolution algebras, and irreducible evolution algebras. These algebras have many connections with other mathematical fields including graph theory, group theory, stochastic processes, and mathematical physics, (see Rozikov and Tian4for example). Another important application is the formulation of Mendel's laws. However, many general questions about these algebras are still unsolved, such as the classification of evolution algebras, because they only have been classified up to dimension three (see Cabrera et al.5and Casas et al.6). There exists also a recent partial classification of nilpotent evolution algebras up to dimension five (see Hegazi and Abdelwahab7,8). Currently, graph theory has become an essential tool to solve a wide range of problems in different research fields. In this way, we think that this theory may be used as a tool to study nonassociative algebras in general and evolution algebras in particular in order to solve open problems like the above-mentioned classification problem previously commented. For example, graphs have been used to study semisimple algebras because trees perform an important role to determine Math Meth Appl Sci. 2022;45:2424–2442.wileyonlinelibrary.com/journal/mma© 2020 John Wiley & Sons, Ltd.2424 RESEARCH ARTICLE the Dynkin diagrams associated to such algebras.9Moreover, graph theory is also applied to study the representation of finite-dimensional algebras.10 The main goal of this paper is to start studying the link between weighted (pseudo)digraphs and evolution algebras. More concretely, we pursue the generalization of the research line started in Carriazo et al.11 and developed in other studies12-15 to the case of evolution algebras instead of considering Lie or Leibniz algebras. This paper is structured as follows: After reviewing some well-known results on graph theory and evolution algebras in Section 2, Section 3 is devoted to design and define the algorithmic procedure to associate weighted (pseudo)digraph with an evolution algebra. This method is similar to the one introduced in Elduque and Labra.16 Next,inSection4,westudythe structure and properties of (pseudo)digraphs associated with evolution algebras. We analyze the type of evolution algebra according to its solvability and nilpotency, and we determine properties of the (pseudo)digraphs associated with solvable and nilpotent evolution algebras. Next, we also determine the isomorphism classes for each configuration providing a new method to classify these algebras, and we compare our results with the current classification of low dimensional evolution algebras. After that, Section 5 shows the implementation of the two algorithmic procedures used in the previous sections. The first one computes the (pseudo)digraph associated with a given finite-dimensional evolution algebra starting from its law, and the second one studies the solvability of a given evolution algebra. In addition, we give a brief computational study, showing the complexity order and computing time of the procedures here presented. In our opinion, the tools and results shown in this paper may be useful and helpful for understanding the relation between evolution algebras and (pseudo)digraphs. Moreover, the classification of (pseudo)digraphs may involve an easier method to classify evolution algebras by means of the classification of their associated structures. In this way, the procedures given in this paper would provide us with the resources to make improvements in the characterization of isomorphism classes for evolution algebras. 2PRELIMINARIES For a general overview on evolution algebras, the reader can consult Tian.2We only consider finite-dimensional evolution algebras over the complex field C. Definition 1. An evolution algebra 𝔤is a vector space equipped with a bilinear form, its law, which satisfies 1. ei·ei=∑n k=1ci,kek,∀1≤i≤n;and 2. ei·ej=0, ∀1≤i≠j≤n. for certain basis {ei}n i=1of 𝔤, which is called natural basis and ci,jare the structure (or Maurer–Cartan) constants. Note that, by definition, evolution algebras are commutative. Definition 2. The evolution algebra 𝔤verifying ei·ej=0, for any pair of generators ei,ejis called the trivial evolution algebra. Definition 3. Let 𝔤be an evolution algebra. The annihilator of 𝔤is given by Ann(𝔤)={X∈𝔤|X·Y=0,∀Y∈𝔤}. Definition 4. Given a finite-dimensional evolution algebra 𝔤,itsderived series is 1(𝔤)=𝔤,2(𝔤)=𝔤·𝔤,…,k(𝔤)=k−1(𝔤)·k−1(𝔤),… Thus, 𝔤is called solvable if there exists m∈Nsuch that m(𝔤)={0}. In addition, if m−1(𝔤)≠{0}also holds, then 𝔤 is (m−1)-step solvable. Definition 5. Given a finite-dimensional evolution algebra 𝔤,itscentral series is 1(𝔤)=𝔤,2(𝔤)=𝔤·𝔤,…,k(𝔤)=k−1(𝔤)·𝔤,… Thus, 𝔤is called nilpotent if there exists m∈Nsuch that m(𝔤)={0}. In addition, if m−1(𝔤)≠{0}also holds, then 𝔤 is (m−1)-step nilpotent. CEBALLOS ET AL.2425 FIGURE 1 Example of sink and source, respectively FIGURE 2 Loop over vertex i Remark 1. Every nilpotent algebra is trivially solvable because i(𝔤)⊆i(𝔤), for all i∈N. Definition 6. An evolution algebra 𝔤is perfect if 𝔤and 2(𝔤)=2(𝔤)are isomorphic. Definition 7. Let 𝔤be an evolution algebra. Given an element xof the algebra, the adjoint action of xon 𝔤is defined as adx∶𝔤→𝔤,where adx(𝑦)=x·𝑦. By composition, one may consider ad2 x(𝑦)=x·(x·𝑦),…,adr x(𝑦)=x·(x·…·(x·𝑦)). Although the reader can consult Harary17 as an introductory reference to graph theory, some notions are recalled next in this section. Definition 8. Adigraph consists in an ordered pair G=(V,E), where Vis a nonempty set called vertex set, and Eis a set of ordered pairs (edges) of two vertices, called edge set. Definition 9. Aloop in the digraph Gis an edge that connects a vertex with itself. If the digraph Gcontains loops, then Gis called a pseudodigraph. Throughout the paper, we consider (pseudo)digraphs admitting double edges. Definition 10. Given a digraph G=(V,E),avertexv∈Vis called simple if there is no loop on this vertex. Definition 11. Given a digraph G=(V,E),avertexv∈Vis a sink (resp. a source) if each edge incident with vis oriented towards v(resp. from v). See Figure 1. 3ASSOCIATING (PSEUDO)DIGRAPHS WITH EVOLUTION ALGEBRAS Let 𝔤be an n-dimensional evolution algebra with natural basis ={ei}n i=1. The structure constants are given by ei·ei=∑n h=1ci,heh, and hence, the pair (𝔤,)is associated with a (pseudo)digraph by using the following procedure: a) For each ei∈,wedrawvertexi. b) For every vertex iverifying ci,i≠0, we draw a loop whose weight is given by ci,i. See Figure 2. c) For each vertex iverifying ci,j≠0, we draw a directed edge from vertex ito jwhose weight is given by ci,j.Ifcj,i≠0, we draw another directed edge, but now from jto iand with weight cj,i. See Figure 3. Consequently, every evolution algebra with a natural basis can be associated with a (pseudo)digraph as described in this section. Notice that isolated vertices without loops correspond to basis vectors in the annihilator of the algebra. Let us note that this association is compatible with the one considered in Elduque and Labra.16 CEBALLOS ET AL. 2426 FIGURE 3 Directed edge FIGURE 4 (Pseudo)digraph associated with a four-dimensional evolution algebra FIGURE 5 (Pseudo)digraphs with two vertices Example 1. The four-dimensional evolution algebra with nonzero products e1·e1=e2−e3,e2·e2=−e2+e3, e3·e3=e1−e4,e4·e4=e1+e4is associated with the (pseudo)digraph shown in Figure 4. 4EVOLUTION ALGEBRAS AND (PSEUDO)DIGRAPHS In this section, we study the structure and properties of (pseudo)digraphs associated with evolution algebras. We analyze the type of evolution algebra according to its solvability and nilpotency. Next, we also determine the isomorphism classes for each configuration providing a new method to classify these algebras, and we compare our results with the current classifications of twoand three-dimensional evolution algebras. Proposition 1. Let 𝔤be a one-dimensional evolution algebra. Then 𝔤is associated with an isolated vertex with a possible loop. Proposition 2. Let 𝔤be a two-dimensional evolution algebra. Then 𝔤is associated with one of the (pseudo)digraphs of Figure 5. Moreover, it is verified that •Configuration (a)is associated with the two-dimensional trivial evolution algebra. •Configuration (d)is associated with a two-step nilpotent evolution algebra. •Configuration (j)is associated with a two-step solvable and nonnilpotent evolution algebra if c2 1,2c2,1+c3 1,1=c2,2c1,2+ c2 1,1=0. •The remaining configurations of Figure 5 are not solvable. Proof. Figure5 contains all the possible (pseudo)digraphs of two vertices. Clearly, the evolution algebra associated with Configuration (a)is trivial. Let 𝔤2 dbe the evolution algebra associated with Configuration (d).Then,𝔤2 d= span(e1,e2)with law e1·e1=c1,2 e2. Clearly, 2(𝔤2 d)=span(e2)is an abelian ideal, and hence, 𝔤2 dis a two-step nilpotent. CEBALLOS ET AL.2427 Now, we denote by 𝔤2 𝑗the evolution algebra associated with Configuration (j)from Figure5. The law of this algebra is e1·e1=c1,1e1+c1,2e2,e2·e2=c2,1e1+c2,2e2. We assume that c2 1,2c2,1+c3 1,1=c2,2c1,2+c2 1,1=0, then c2,1=− c3 1,1 c2 1,2 ,c2,2=− c2 1,1 c1,2 .and e2·e2=− c3 1,1 c2 1,2 e1−c2 1,1 c1,2 e2=− c2 1,1 c2 1,2 (c1,1e1+c2 1,2e2)=− c2 1,1 c2 1,2 e1·e1. Consequently, 2(𝔤2 𝑗)=span(e1·e1)and 3(𝔤2 𝑗)={0}because (e1·e1)·(e1·e1)=(c3 1,1+c2 1,2c2,1)e1+c1,2(c2 1,1+c1,2c2,2)e2=0. Notice that if c2 1,2c2,1+c3 1,1≠0orc2,2c1,2+c2 1,1≠0, then 𝔤2 𝑗is not solvable because 2(𝔤2 𝑗)=3(𝔤2 𝑗)≠{0}.Next,it is easy to prove that the evolution algebras associated with Configurations (c),(e),(h),and(i)are perfect. Finally, the evolution algebras, 𝔤, associated with Configurations (b),(f),or(g)are not solvable because i(𝔤)=span(e1), for all i≥2. Concerning the solvability and nilpotency, we can establish the following results. Proposition 3. If a (pseudo)digraph G contains a cycle, then the evolution algebra 𝔤associated with G is not nilpotent. Proof. Let ={e1,…,en}be a natural basis associated with 𝔤. We assume that vertices {1,…k}constitute a cycle in G. Then, we have the products ei·ei=ci,i+1ei+1+ n ∑ h=k+1 ci,heh,for 1 ≤i≤k−1;ek·ek=ck,1e1+ n ∑ h=k+1 ck,heh. Now, we define u=∑k i=1eiand 𝔥=span(ek+1,…,en). Then, it is verified that u·u=ck,1e1+ k−1 ∑ 𝑗=1 c𝑗,𝑗+1e𝑗+1, u·(u·u)=ck−1,kck,1e1+ck,1c1,2e2+ k−2 ∑ 𝑗=1 c𝑗,𝑗+1c𝑗+1,𝑗+2e𝑗+2+v, adr u(u)=u·(u,…,(u·u)…)= k−1 ∏ i=1 ci,i+1ck,1u+v. where v∈𝔥. Because adr u(u)∈r+1(𝔤), we can conclude that 𝔤is not nilpotent. Remark 2. Notice that, in particular, if Gcontains a double edge, then the associated evolution algebra 𝔤is not nilpotent. Notice also that if Gcontains a loop (one-dimensional cycle), then 𝔤is neither nilpotent. Proposition 4. If a (pseudo)digraph G contains a subgraph isomorphic to Configuration (f)or (g), then the associated evolution algebra, 𝔤, is not solvable. Proof. We prove this result for the case of Configuration (f), and the proof is similar for Configuration (g).Letus assume that 𝔤is the evolution algebra associated with a (pseudo)digraph G, which contains a subgraph isomorphic to Configuration (f)from Figure 5. We denote by ={ei}n i=1the natural basis associated with 𝔤assuming that iand j are the vertices, which constitute Configuration (f),andicontains a loop. Then, ei·ei=ci,iei+ci,𝑗 e𝑗+ n ∑ k=1,k≠i,𝑗 ek, CEBALLOS ET AL. 2428 and (ei·ei)·(ei·ei)=c2 i,i(ei·ei)+c2 i,𝑗 (e𝑗·e𝑗)+ n ∑ k=1,k≠i,𝑗 c2 i,k(ek·ek)= c2 i,i(ci,iei+ci,𝑗 e𝑗+ n ∑ k=1,k≠i,𝑗 ci,kek)+c2 i,𝑗 (e𝑗·e𝑗)+ n ∑ k=1,k≠i,𝑗 c2 i,k(ek·ek)= c3 i,iei+c2 i,ici,𝑗 e𝑗+c2 i,i n ∑ k=1,k≠i,𝑗 ci,kek+c2 i,𝑗 (e𝑗·e𝑗)+ n ∑ k=1,k≠i,𝑗 c2 i,k(ek·ek)= c3 i,iei+c2 i,ici,𝑗 e𝑗+c2 i,𝑗 (e𝑗·e𝑗)+ n ∑ k=1,k≠i,𝑗 ci,k(c2 i,iek+ci,k(ek·ek)). Notice that ei∈k(𝔤),fork≥1 because c𝓁,i=0, ∀1≤𝓁≠i≤n. Therefore, 𝔤is not solvable. Proposition 5. Consider a (pseudo)digraph G containing a sink vertex with a loop, then the associated evolution algebra 𝔤is not solvable. Proof. Let ibe the sink vertex with a loop. Then, we have the following law in the evolution algebra 𝔤associated with G ei·ei=ci,iei,e𝑗k·e𝑗k=c𝑗k,iei+ n ∑ m=1,m≠i c𝑗k,mem. This is due to the fact that there is no directed edge leaving from vertex i. Consequently, ei·ei=span(ei)∈p(𝔤), ∀p≥1and𝔤is not solvable. Proposition 6. Let G be a (pseudo)digraph with less than four vertices containing a double edge with, at least, a simple vertex. Then the evolution algebra 𝔤associated with G is not solvable. Proof. In case that Gcontains two vertices, we obtain Configuration (i)from Figure5, which is associated with a perfect evolution algebra. If Ghas three vertices {i,j,k}being ja simple vertex, the evolution algebra associated with Ghas the following law: ei·ei=ci,iei+ci,𝑗 e𝑗+ci,kek,e𝑗·e𝑗=c𝑗,iei+c𝑗,kek,ek·ek=ck,iei+ck,𝑗 e𝑗+ck,kek Notice that 2(𝔤)=span(ei·ei,e𝑗·e𝑗,ek·ek). By using elementary row transformations, we obtain (ci,ici,𝑗 ci,k c𝑗,i0c𝑗,k ck,ick,𝑗 ck,k)→⎛⎜⎜⎝ ci,ici,𝑗 ci,k 0−ci,𝑗 c𝑗,i ci,i c𝑗,k−ci,kc𝑗,i ci,i 0ck,𝑗 ck,k⎞⎟⎟⎠ → ⎛⎜⎜⎜⎝ ci,ici,𝑗 ci,k 0−ci,𝑗 c𝑗,i ci,i c𝑗,k−ci,kc𝑗,i ci,i 00ci,𝑗 c𝑗,i(ci,i(ck,k−c𝑗,k)+ci,k(c𝑗,i−ck,i))+ci,ick,𝑗 (ci,ic𝑗,k−ck,𝑗 c𝑗,i) ci,ici,𝑗 c𝑗,i ⎞⎟⎟⎟⎠ . If the rank of the previous matrix is 3, then 𝔤is a perfect evolution algebra. Now, we assume that ck,k=c𝑗,k−ci,k(c𝑗,i−ck,i) ci,i −ck,𝑗 (ci,ic𝑗,k−ck,𝑗 c𝑗,i) ci,𝑗 c𝑗,i .(1) Then dim(2(𝔤)) ≤2. Moreover, 2(𝔤)=span (ci,iei+ci,𝑗 e𝑗+ci,kek,−ci,𝑗 c𝑗,i ci,i e𝑗+(c𝑗,k−ci,kc𝑗,i ci,i)ek)=span(u,v), where u=ci,iei+ci,𝑗 e𝑗+ci,kek,v=e𝑗+Φek,with Φ=ci,kc𝑗,i−ci,ic𝑗,k ci,𝑗 c𝑗,i . CEBALLOS ET AL.2429 FIGURE 6 Counterexample with four vertices Next, we compute 3(𝔤) u·u=(c3 i,i+c2 i,𝑗 c𝑗,i+c2 i,kck,i)ei+(c2 i,ici,𝑗 +c2 i,kck,𝑗 )e𝑗+(c2 i,ici,k+c2 i,𝑗 c𝑗,k+c2 i,kck,k)ek v·v=(c2 i,𝑗 c3 𝑗,i+ck,iΦ2)ei+ck,𝑗 Φ2e𝑗+(c2 i,𝑗 c2 𝑗,ic𝑗,k+ck,kΦ2)ek u·v=(−c2 i,𝑗 c2 𝑗,i+ci,kck,iΦ) ei+ci,kck,𝑗 Φe𝑗+(−c2 i,𝑗 c𝑗,ic𝑗,k+ci,kck,kΦ) ek, where ck,kwas given in expression (1). If 𝛷=0, then c𝑗,iei+c𝑗,kek∈3(𝔤), and therefore, (c𝑗,iei+c𝑗,kek)·(c𝑗,iei+c𝑗,kek)=c𝑗,ici,𝑗 e𝑗+w∈4(𝔤),where w∈span(ei,ek). Consequently, 𝔤cannot be solvable. In case that 𝛷≠0, Φ(u·u)−ci,k(u·v)=(Φc3 i,i+c2 i,𝑗 c𝑗,iΦ−ci,kci,𝑗 c𝑗,i)ei+Φc2 i,ici,𝑗 e𝑗+ (Φ c2 i,ici,k+Φc2 i,𝑗 c𝑗,k−ci,kci,𝑗 c𝑗,k)ek=Φc2 i,ici,𝑗 e𝑗+w′∈4(𝔤),where w′∈span(ei,ek). Therefore, 𝔤cannot be solvable. Remark 3. Let us note that the previous result is not true for (pseudo)graphs having more than three vertices. Here, we show a counterexample. Consider the four-dimensional evolution algebra e1·e1=−(e3·e3)=e1−e2−e3+e4,e2·e2=−(e4·e4)=−e1−e3, which is associated with the pseudodigraph of Figure 6. The Vertices 2 and 4 are simple and are the only pair of vertices that does not form a double edge. However, this evolution algebra is three-step solvable because 2(𝔤)=⟨e1−e2−e3+e4,e1+e3⟩,3(𝔤)=⟨e1−e2−e3+e4⟩,4(𝔤)={0} and (e1−e2−e3+e4)·(e1−e2−e3+e4)=(e1+e3)·(e1+e3)=0, (e1−e2−e3+e4)·(e1+e3)=2(e1−e2−e3+e4). Proposition 7. Let G be a nonconnected (pseudo)digraph with three vertices associated with an evolution algebra. Then G is one of the configurations of Figure 7. Moreover, it is verified that •Configuration (v)is associated with a two-step nilpotent evolution algebra. •Configuration (vi)is associated with a two-step solvable and nonnilpotent evolution algebra. CEBALLOS ET AL. 2430 FIGURE 7 Disconnected (pseudo)digraphs with 3 vertices •Configurations (xvii)and (xviii)are associated with a two-step solvable and nonnilpotent evolution algebras if c3,2=− c3 2,2 c2 2,3 and c3,3=− c2 2,2 c2,3 •The remaining configurations of Figure 7 are not solvable. Proof. First, Configuration (i)is associated with the three-dimensional trivial evolution algebra. The proof that the evolution algebras associated with configurations (ii),(iii),and(iv)are not solvable is similar to the one done for Configurations (b)and (c)in Proposition 2. Next, by using Proposition 4, it is easy to prove that Configurations (vii)–(x) are associated with nonsolvable evolution algebras. According to Proposition 5, the same happens for Configurations (xi)and (xii). Moreover, Configurations (xiii)–(xvi)are not associated with solvable evolution algebras due to Proposition 6. Let 𝔤3 v)be the evolution algebra associated with Configuration (v)of Figure 7. Then, 𝔤3 v)=span(e1,e2,e3)with e2·e2=c2,3 e3verifies 2(𝔤)=span(e3)and 3(𝔤)={0}.Wedenoteby𝔤3 vi)the evolution algebra associated with Configuration (vi)of Figure 7. Then, 𝔤3 vi)=span(e1,e2,e3)with e1·e1=c1,1 e1,e2·e2=c2,3 e3verifies 2(𝔤)=span(e1,e3) and 3(𝔤)={0}. However, 𝔤3 vi)is not nilpotent according to Remark 2. Now, let 𝔤3 xvii)be the evolution algebra associated with Configuration (xvii)from Figure 7. Then, 𝔤3 xvii)=span(e1,e2,e3)with law e2·e2=c2,2e2+c2,3e3,e3·e3=c3,2e2+c3,3e3. Consequently, (e2·e2)·(e2·e2)=(c3 2,2+c2 2,3c3,2)e2+c2,3(c2 2,2+c2,3c3,3)e3 (e3·e3)·(e3·e3)=c3,2(c3,2c2,2+c2 3,3)e2+(c2 3,2c2,3+c3 3,3)e3 (e2·e2)·(e3·e3)=c3,2(c2 2,2+c2,3c3,3)e2+c2,3(c2,2c3,2+c2 3,3)e3. If c3,2=− c3 2,2 c2 2,3 and c3,3=− c2 2,2 c2,3 ,then3(𝔤3 xvii))={0}.Otherwise,𝔤3 xvii)is not solvable. Moreover, 𝔤3 xvii)is not nilpotent according to Proposition 3. Analogously, it is possible to prove the same conditions for the evolution algebra associated with Configuration (xviii)from Figure 7. Proposition 8. Let G be a connected digraph with three vertices associated with an evolution algebra. Then G is one of the configurations of Figure 8. Moreover, it is verified that •Configurations (1)and (3)are associated with a two-step nilpotent evolution algebra. •Configurations (2)and (8)are associated with a three-step nilpotent evolution algebra. •The remaining configurations of Figure 8 are not solvable. CEBALLOS ET AL.2431 FIGURE 8 Connected digraphs with 3 vertices Proof. Let 𝔤3 1)be the evolution algebra associated with Configuration (1)from Figure 8. Then 𝔤3 1)=span(e1,e2,e3) with nonzero products e1·e1=c1,2 e2,e3·e3=c3,2 e2. Notice that 2 is a sink vertex and span(e2)is an abelian ideal. Therefore, 𝔤3 1)is a two-step nilpotent. The proof is similar for the evolution algebra 𝔤3 3)associated with Configuration (3)from Figure 8, but this time, 1 and 3 are sink vertices and span(e1,e3)is a two-dimensional abelian ideal. We denote by 𝔤3 2)the evolution algebra associated with Configuration (2). It is verified that 𝔤3 2)=span(e1,e2,e3)with law e1·e1=c1,2 e2,e2·e2=c2,3 e3.Then,2(𝔤3 2))=span(e2,e3)and k(𝔤3 2))=span(e3)for k≥3. Therefore, 𝔤3 2)is not solvable. Let 𝔤3 7)be the evolution algebra associated with Configuration (7). Then, we have 𝔤3 7)=span(e1,e2,e3)with law e1·e1=c1,3 e3,e2·e2=c2,1 e1,e3·e3=c3,2 e2. Clearly 𝔤3 7)is a perfect evolution algebra. Now, we denote by 𝔤3 8)the evolution algebra associated with Configuration (8).Then𝔤3 8)=span(e1,e2,e3)with law e1·e1=c1,2 e2+c1,3 e3and e3·e3=c3,2 e2.Wehave2(𝔤3 8))=span(e2,e3),3(𝔤3 8))=span(e2)and 4(𝔤3 8))={0}. Finally, and according to Proposition 6, the evolution algebras associated with Configurations (4)–(6)and (9)–(13) are associated with nonsolvable evolution algebras. Proposition 9. Let G be a connected pseudodigraph with three vertices associated with an evolution algebra. Then G is one of the configurations of Figure 9. Moreover, it is verified that •Configuration (37)is associated with a three-step solvable and nonnilpotent evolution algebra if c2,1=− c3 1,1 c2 1,2 and c2,2=− c2 1,1 c1,2 . •Configuration (56)is associated with a two-step solvable and nonnilpotent evolution algebra if c2,1=− c2 3,3c3,1 c2 3,2 , c2,2=− c2 3,3 c3,2 ,c 2,3=− c3 3,3 c2 3,2 . •Configuration (61)is associated with a two-step solvable and nonnilpotent evolution algebra if c1,2=c1,3c3,2 c3,3 , c2,2=− c2 3,3 c3,2 ,c 2,3=− c3 3,3 c2 3,2 . •Configuration (79)is associated with a two-step solvable and nonnilpotent evolution algebra if c1,1=− d c3,1c3,3 , c1,2=− dc3,2 c2 3,1c3,3 ,c 1,3=−d c2 3,1 ,c 2,1=c2,3c3,1 c3,3 ,c 2,2=c3,2c2,3 c3,3 , where d =c2,3c2 3,2+c3 3,3. •The remaining configurations of Figure 9 are not solvable. Proof. First, the evolution algebras associated with Configurations (14)–(16),(18)–(22),(24)–(26),(46),(47),and(49) cannot be solvable according to Proposition4. Analogously and, according to Proposition 5, the same happens for Configurations (17),(23),(27),(36),(38)–(40),(50)–(53),(55),and(57). Next, by using Proposition 6, Configurations (28)–(30),(32),(34),(35),(38),(39),(41)–(44),(53)–(55),(58)–(60),(63)–(67),(70)–(75),(77),and(78)are associated with nonsolvable evolution algebras. Concerning Configurations (31),(45),(48),(62),(68),(69)and (76),theyare CEBALLOS ET AL. 2432 After that, we must run for loop and the subprocedure product. Finally, we evaluate the procedure drawing, obtaining Figure10, which corresponds to Configuration (xvii)from Figure 7. >draw(dim); 5.2 Studying the solvability of a given evolution algebra In this subsection, we implement an algorithmic procedure devoted to studying the solvability of a given evolution algebra. In order to do so, we need to load the libraries linalg,ListTools and Combinat to activate commands related to linear and combinatorial algebra and to use a collection of tools for manipulating lists. Once again, we follow the notation used in the previous sections, considering an n-dimensional evolution algebra 𝔤with natural basis and law given in Definition 1. We have designed the following algorithm to study the solvability of an evolution algebra 𝔤, structured in three steps. 1. Defining the value of the structure constants and the product between two arbitrary basis vectors in . 2. Evaluating the product between two vectors expressed as a linear combination of vectors from basis . 3. Studying the solvability of the evolution algebra 𝔤. Let us note that the first two steps were already implemented in the previous subsection. Therefore, we only need to show the implementation of the third step, which constitutes the main routine of this algorithm, called solvability. It receives as input a natural number, n, corresponding to the dimension of the evolution algebra 𝔤. In order to carry out the implementation, we have introduced four local variables: L,M,P,T.First,Lis a list devoted to saving the subindexes of the basis vectors of the evolution algebra 𝔤.Next,listMis used to save the generators of the derived algebra of the one introduced in the first step. List Pwill save the coefficients of each term of list Mwith respect to the basis vectors of the algebra. Finally, we will use the set Tin order to display a message concerning the solvability index of the evolution algebra. The procedure is implemented by using several loops concerning the solvability of the evolution algebra. The output is the solution of the equation system obtained when imposing a decrement on the dimension between 2(𝔤)and 3(𝔤)and a message related to the solvability index. In case that the previous system has no solution, the output will be a message saying that the algebra is not solvable. Notice that the first possible case is that there is a solution for which the derived algebra is trivial and, therefore, 𝔤is two-step solvable. In case that the derived algebra is not trivial, but it is possible to reduce the dimension between 2(𝔤) and 3(𝔤),wemayhaveak-step solvable evolution algebra with k>2. In order to carry out this study, we can reprogram the whole algorithm introducing the structure constants of the derived algebra of 𝔤and increasing in one unit the step messages of procedure solvability. >solvability:=proc(n) >local L,M,P,T; >L:=choose(n,2);M:=[];P:=[];T:={}; >for i from 1 to n do >L:=[op(L),[i,i]]; >end do; >for j from 1 to nops(L) do >eq[j]:=product(product(e[L[j][1]],e[L[j][1]],n),product(e[L[j][2]],e[L[j][2]],n),n); >end do; >M:=[seq(eq[k],k=1..nops(L))]; >for h from 1 to n do >P:=[op(P),[seq(coeff(M[k],e[h]),k=1..nops(M))]]; >end do; >if {solve(Flatten(P))}={} then >T:={op(T),“g is not 2-step solvable”}; >else return solve(Flatten(P)),“g is 2-step solvable”; >end if; >for i from 1 to n do >if {solve(Flatten(P[i]))}={} then T:=T; >else T:={op(T),“g is at least 3-step solvable”}; >return solve(Flatten(P[i])),T; CEBALLOS ET AL.2439 >end if; >end do; >return “g is not solvable”; >end proc: Example 3. Now, we show an example with Configuration (37)from Figure 9 associated with the three-dimensional evolution algebra, 𝔤, with nonzero products e1·e1=c1,1e1+c1,2e2;e2·e2=c2,1e1+c2,2e2+c2,3e3. First, we fill the assign sentences as follows: >assign(dim,3) >assign(c[1,3],0):assign(c[3,1],0):assign(c[3,2],0):assign(c[3,3],0): After that, we must run for loop, the subprocedure product, and the procedure solvability.Now,if we evaluate the main procedure over the variable dim, we obtain the output {c11 =c11, c12 =c12, c21 =-c113/c122, c22 =-c112/c12, c23 =c23}, {“g can be 3-step solvable”, “g is not 2-step solvable”} Under these conditions, the derived algebra is given by (𝔤)=span(u,v)with law u·u=c2 1,1u+c2 1,2v, where u=c1,1e1+c1,2e2,v=c2,1e1+c2,2e2+c2,3e3. Therefore, 𝔤is three-step solvable because (u·u)·(u·u)=0. 5.3 Computational and complexity study Next, we show a computational study of the algorithmic procedure shown in Section 5.2, which has been implemented with MAPLE 18, in an Intel(R) Core(TM) i7-4510U CPU with a 2.60 GHz processor and 12.00GB of RAM. Table 2 shows some computational data about both the computing time and the memory used to return the output of the whole procedure according to the value of the dimension nof the algebra. To do the computational study, we have considered the family of solvable evolution algebras associated with the generalization of Configuration (xvii)from Figure 7. This family has been chosen because it constitutes a special subclass of two-step nilpotent evolution algebras, which allow us to check empirically the computational data given for both the computing time and the used memory. Next we show some brief statistics about the relation between the computing time and the memory used by the implementation of the previous procedure. In this sense, Figure11 shows the behavior of the computing time with respect to the dimension n. In turn, Figure12 graphically represents the behavior of the used memory with respect to the dimension Input Computing time (s) Used memory (MB) n=3 0.13 4.67 n=40.25 4.81 n=5 0.39 5.01 n=60.52 5.19 n=7 1.01 6.38 n=81.49 7.54 n=9 2.59 9.89 n=10 3.89 12.47 n=11 6.32 13.96 n=12 9.81 19.65 n=13 14.29 24.31 TABLE 2 Computing time and used memory CEBALLOS ET AL. 2440 FIGURE 11 Graph for the computing time with respect to dimension [Colour figure can be viewed at wileyonlinelibrary.com] FIGURE 12 Graph for the used memory with respect to dimension [Colour figure can be viewed at wileyonlinelibrary.com] FIGURE 13 Graph for quotients used memory/computing time with respect to dimension [Colour figure can be viewed at wileyonlinelibrary.com] TABLE 3 Complexity and number of operations Step Routine Complexity Operations 1assign commands O(n)N1(n)=1+n(n+1) 2product O(n)N2(n)=1+ n ∑ i=1 1 3draw O(n2)N4(n)=O(n)+O(n2)+2 n2 ∑ i=1 1 4solvability O(n3)N3(n)=O(n)+O(n2)+2 n2 ∑ i=1 N2(n) n. Note that the computing time increases more quickly than the used memory, and both of them fit a positive exponential model. Next, we have studied the quotients between used memory and computing time, obtaining the frequency diagram shown in Figure13. In this case, the behavior also fits an exponential model, but being negative this time. Finally, we compute the complexity of the algorithm taking into account the number of operations carried out in the worst case. We have used the big Onotation to express the complexity. To recall the big Onotation, the reader can consult Wilf18: Given two functions 𝑓,g∶R→R, we could say that f(x)=O(g(x)) if and only if there exist M∈R+and x0∈R such that |f(x)|<M·g(x), for all x>x0. We denote by Ni(n)the number of operations when considering the Step i. This function depends on the dimension n of the evolution algebra. Table 3 shows the number of computations and the complexity of each step, as well as indicating the name of the procedure corresponding to each step. CEBALLOS ET AL.2441 ACKNOWLEDGEMENT It has been partially supported by MTM2016-75024-P and FEDER. CONFLICT OF INTEREST This work does not have any conflicts of interest. ORCID M. Ceballos https://orcid.org/0000-0003-0913-6417 J. Núñez https://orcid.org/0000-0002-8413-6735 REFERENCES 1. Tian JP, Vojtechovsky P. Mathematical concepts of evolution algebras in non-Mendelian genetics. Quasigroups Related Syst. 2006;14(1):111-122. 2. Tian JP. Evolution algebras and their applications; 1921:2008. 3. Cabrera Y, Siles M, Velasco MV. Evolution algebras of arbitrary dimension and their decompositions. Linear Algebra Appl. 2016;495:122-162. 4. Rozikov UA, Tian JP. Evolution algebras generated by Gibbs measures. Lobachevskii J Math. 2011;32(4):270-277. 5. Cabrera Y, Siles M, Velasco MV. Classification of three-dimensional evolution algebras. Linear Algebra Appl. 2017:524. https://doi.org/10. 1016/j.laa.2017.02.015 6. Casas JM, Ladra M, Omirov BA, Rozikov UA. On evolution algebras. Algebra Colloq. 2014;21:331-342. 7. Hegazi AS, Abdelwahab H. Nilpotent evolution algebras over arbitrary fields. Linear Algebra Appl. 2015;486:345-360. 8. Hegazi AS, Abdelwahab H. Five-dimensional nilpotent evolution algebras. arXiv:1508.07442v1. 9. Serre JP. Algèbres de Lie semi-simples complexes. New York: Benjamin Inc.; 1996. 10. Primc M. Basic representations for classical affine Lie algebras. JofAlgebra. 2000;228:1-50. 11. Carriazo A, Fernández LM, Núñez J. Combinatorial structures associated with Lie algebras of finite dimension. Linear Algebra Appl. 2004;389:43-61. 12. Cáceres J, Ceballos M, Núñez J, Puertas ML, Tenorio AF. Combinatorial structures of three vertices and Lie algebras. Int J Comput Math. 2012;89:1879-1900. 13. Ceballos M, Núñez J, Tenorio AF. Study of Lie algebras by using combinatorial structures. Linear Algebra Appl. 2011;436(2):349-363. 14. Ceballos M, Núñez J, Tenorio AF. Finite-dimensional Leibniz algebras and combinatorial structures. Commun Contemp Math. 2018;20(1):34. 15. Ceballos M author=Núñez, J. Malcev algebras and combinatorial structures. Appl Math Info Sci. 2015;9(2L):297-304. 16. Elduque A, Labra A. Evolution algebras and graphs. J Algebra Its Appl. 2015;14(7):1550103. 17. Harary F. Graph Theory. Reading: Addison-Wesley; 1969. 18. Wilf HS. Algorithms and Complexity. 2nd ed. Natick: A K Peters; 2002. https://doi.org/10.1201/b10621 How to cite this article: Ceballos M, Núñez J, Tenorio ÁF. Finite dimensional evolution algebras and (pseudo)digraphs. Math Meth Appl Sci. 2022;45:2424–2442. https://doi.org/10.1002/mma.6632 CEBALLOS ET AL. 2442