Markov evolution algebras

ABSTRACT

We study Markov evolution algebras, that is, evolution algebras having Markov structure matrices. We first consider the discrete-time case, and delve into their algebraic structure for later application to continuous-time Markov evolution algebras that arise defined by standard stochastic semigroups. The study of embeddable Markov evolution algebras, that is, of Markov evolution algebras with structure matrices existing within standard stochastic semigroups is then equivalent to the embedding problem for Markov matrices.

Keywords:

• Markov evolution algebra
• stochastic semigroup
• continuous-time evolution algebra

1. Introduction

An evolution algebra $\mathcal{E}$ is an n-dimensional (real) algebra with basis $\mathcal{B}=\{e_1,\dots ,e_n\}$ and multiplication: $\left\{\begin{array}{ll}{e}_i^2=e_i{e}_i=\sum _{j=1}^n{a}_{ij}{e}_j,& i=1,\dots ,n;\\ e_i{e}_j=e_j{e}_i=0,& i\ne j.\end{array}\right.$ Such a basis $\mathcal{B}$ is called natural basis and the matrix $\mathbf{A}=(a_{ij}{)}_{i,j=1}^n\in M_n(\mathbb{R})$ the structure matrix of $\mathcal{E}$ [1,2] ( evolution matrix in [3]).

Evolution algebras were introduced in [1] (see also [2]) and have been exhaustively studied over the last years. See, for instance, [3–6] and references therein for a review of some of the main results achieved on this topic. These algebras are related to a wide variety of mathematical subjects, including Markov chains and dynamical systems. The relationship between evolution algebras and homogeneous discrete-time Markov chains was settled in [1, Theorem 16, p. 54]. Markov evolution algebras are real evolution algebras whose structure matrix A is nonnegative and has row sums equal to 1 (i.e. A is a Markov matrix).

In his seminal work [1], Tian posed as one of the most fruitful further topics of research the development of the theory of continuous evolution algebras and their connection to continuous-time Markov processes. Tian outlined continuous evolution algebras to be evolution algebras with multiplication, w.r.t. a natural basis $\mathcal{B}=\{e_1,\dots ,e_n\}$: $\left\{\begin{array}{ll}{e}_i^2=e_i{e}_i=\sum _{j=1}^n{a}_{ij}\left(t\right)e_j,& i=1,\dots ,n;\\ e_i{e}_j=e_j{e}_i=0,& i\ne j;\end{array}\right.$ for differentiable functions a_ij(t), i, j = 1, …, n [1, Section 6.2.4, p. 115].

Chains of evolution algebras (CEAs), introduced in [7], can be understood as the first approach to continuous-time evolution algebras, as they consist of families of evolution algebras whose structure matrices satisfy Chapman–Kolmogorov-type equations [7, Theorem 2.5]. Continuity or differentiability is, however, not required.

With the further aim of settling a theory of continuous evolution algebras, in this paper, we put the focus on Markov evolution algebras. First, we review the discrete-time case already considered in [1]. Here, taking advantage of recently obtained results on general evolution algebras, we improve our knowledge on these structures, for later application to the continuous-time case. In the second part of the paper, we introduce the notion of continuous-time Markov evolution algebra as the first step to a more general theory of continuous evolution algebras. Our study of continuous-time Markov evolution algebras connects these algebras to the embedding problem for Markov matrices [8].

This paper is organized as follows. After this introductory section, in Section 2, we revisit Tian's notion of Markov evolution algebra, characterized as those evolution algebras whose structure matrix is precisely a (real) Markov matrix (i.e. nonnegative and row stochastic), therefore defining a homogeneous discrete-time Markov chain. In this section, we address the elementary properties of this class of evolution algebras, such as the (non)existence of nilpotent or idempotent elements. We also study the behaviour of their evolution operator, and show that results in [9] can be seen as a generalization for the ergodic theorems for Markov evolution algebras having primitive structure matrices [10].

In the third section, we take advantage of the notion of basic ideal [11] to address a decomposition of Markov evolution algebras into simple basic ideals together to an additional component gathering the inessential behaviour within the Markov evolution algebra. This decomposition, similar to the semi-direct sum decomposition proposed in [1, 4.4, p. 76], stems quite straightforwardly when considering the notion of an essential class of states (and also that of incidence matrix) for nonnegative matrices. It also comes out the suitability of the notion of basic ideal to study Markov evolution algebras. Section 4 is devoted to examples. The different Markov evolution algebras considered in this section, stemming them all mainly from Biology, allow us to illustrate different algebraic properties of Markov evolution algebras.

In Section 5, we recall some basic facts on continuous-time Markov chains [12,13], prior to introducing in Section 6 continuous-time Markov evolution algebras $\mathcal{E}\left(t\right)=\{{\mathcal{E}}_t,t\ge 0\}$ to be families of (Markov) evolution algebras whose structure matrices {A(t)}_t≥0 form standard stochastic semigroups, and therefore are solutions of Kolmogorov differential equations. Being, for all t ≥ 0, the structure matrix of ${\mathcal{E}}_t$ of the form A(t) = e^tQ, it comes out that all such evolution algebras should be not only nondegenerate but also perfect, posing therefore the question of identifying those evolution algebras that can be realized this way. This leads us to consider the embedding problem.

The embedding problem copes with the problem of given a Markov matrix P to determine the existence of a rate matrix Q such that P = eQ and e^tQ is Markov for all t ≥ 0. The existence and uniqueness (i.e. the identifiability) of the Markov generator Q is related to the spectral properties of P and to the noninjectivity of the principal logarithm of matrices [8]. See [14,15] and references therein for recent results on the embedding problem in phylogenetics.

The study of CT-Markov evolution algebras leads naturally to consider when a Markov evolution algebra (its structure matrix) can exist within a standard stochastic semigroup. To do this, we consider the embeddability of discrete-time Markov evolution algebras, and although determining families of embeddable matrices it not a goal pursued here, some such characterizations will be applied in Section 7 to obtain Markov evolution matrices realizable within CT Markov processes.

2. Markov evolution algebras

Let $\mathbb{R}$ be the field of real numbers. In what follows, all algebraic objects will be defined over finite-dimensional real vector spaces. Matrices and vectors will be denoted boldface.

Evolution algebras are a class of commutative algebras, which are not necessarily associative nor power-associative [1, Corollary 1, p. 20]. Only nonzero trivial evolution algebras with structure matrix A = diag(λ₁, …, λ_n), (λ_i ≠ 0, for all i) are unital [1, Proposition 1, p. 22].

Definition 2.1

[[1, 4.1.2, p. 54]] Let $\mathcal{E}$ be a finite-dimensional real algebra (${\mathrm{d}\mathrm{i}\mathrm{m}}_{\mathbb{R}}\left(\mathcal{E}\right)=n$). We say that $\mathcal{E}$ is a Markov evolution algebra if it admits a basis $\mathcal{B}=\{e_1,\dots ,e_n\}$ and multiplication: $\left\{\begin{array}{ll}{e}_i^2=e_i{e}_i=\sum _{j=1}^n{a}_{ij}{e}_j,& i=1,\dots ,n;\\ e_i{e}_j=e_j{e}_i=0,& i\ne j\end{array}\right.$ (i.e. $\mathcal{E}$ is an evolution algebra), such that its structure matrix $\mathbf{A}=(a_{ij}{)}_{i,j=1}^n$ is a nonnegative row stochastic matrix, i.e. a (real) Markov matrix.

The structure matrix A of any Markov evolution algebra can be seen as the transition probability matrix of a homogeneous discrete-time (HDT) Markov chain on a finite set of states Λ = {1, …, n}, under the obvious identification $\mathcal{B}\cong \mathrm{\Lambda }$. Within the genetic non-Mendelian framework, where evolution algebras first arose, one can write $\mathbf{A}=\left(\begin{array}{cccc}P(e_1\mid e_1)& P(e_2\mid e_1)& \cdots & P(e_n\mid e_1)\\ P(e_1\mid e_2)& P(e_2\mid e_2)& \cdots & P(e_n\mid e_2)\\ ⋮& ⋮& \ddots & ⋮\\ P(e_1\mid e_n)& P(e_2\mid e_n)& \cdots & P(e_n\mid e_n)\end{array}\right),$ where a_ij = P(e_j| e_i) denotes the probability for a type j individual to arise from self-replication of a type i individual.

We refer the reader to [10,13] for basic results on HDT Markov processes.

Definition 2.2

A discrete-time stochastic process $X=\{X_k{\}}_{k=0}^{\mathrm{\infty }}$, where X_k is a discrete random variable defined on a (finite) state space Λ = {1, …, n}, is a Markov chain if the Markov property $P(X_k=i_k\mid X_0=i_0,\dots ,X_{k-1}=i_{k-1})=P(X_k=i_k\mid X_{k-1}=i_{k-1}),$ where i_k ∈ {1, …, n}, holds for all k = 0, 1, …. A discrete-time Markov chain is homogeneous (HDT) if the transition probabilities do not depend on (time) k, P(X_k = i_k| X_k−1 = i_k−1) = P(X_k+l = i_k| X_k+l−1 = i_k−1), for all l = 0, 1, …. We denote the transition probabilities of a HDT Markov chain by a_ij = P(X_k = j| X_k−1 = i), k = 0, 1, ….

The relation between Markov evolution algebras and HDT Markov chains was settled in [1, Theorem 16, p. 54].

Theorem 2.3

[1, Theorem 16, p. 54]

For each homogeneous Markov chain X there is an evolution algebra M_X whose structural constants are transition probabilities, and whose generator set is the state space of the Markov chain.

Examples 2.4

Let $\mathcal{E}$ be an evolution algebra with an natural basis $\mathcal{B}=\{e_1,\dots ,e_n\}$.

1. The only trivial Markov evolution algebra has A = I_n, that is, $e_i^2=e_i$, for all i = 1, …, n. In this particular case, $\mathcal{E}$ is unital with unit element $e=\sum _{i=1}^n{e}_i$.

2. An evolution algebra of permutations ${\mathcal{E}}_{n,\pi }(a_1,\dots ,a_n)$ is Markov if and only if a_i = 1, i = 1, …, n. Then A equals the permutation matrix of π ∈ S_n [16].

3. Let ${\mathcal{E}}_{\pi ,\tau }^n$ be the evolution algebra corresponding to permutations π, τ (π ≠ τ ∈ S_n), with multiplication [17]: $\left\{\begin{array}{ll}{e}_i^2=e_i{e}_i=a_{i\pi \left(i\right)}{e}_{\pi \left(i\right)}+a_{i\tau \left(i\right)}{e}_{\tau \left(i\right)},& i=1,\dots ,n;\\ e_i{e}_j=e_j{e}_i=0,& i\ne j.\end{array}\right.$ Then ${\mathcal{E}}_{\pi ,\tau }^n$ is Markov if and only if a_iπ(i), a_iτ(i) ≥ 0 and a_iπ(i) + a_iτ(i) = 1 for all i = 1, …, n.

4. Evolution algebras ${\mathcal{E}}_{1/2}$ and ${\mathcal{E}}_1$ [7] are Markov evolution algebras: ${\mathcal{E}}_{1/2}:\left\{\begin{array}{l}{e}_1^2=e_2^2=\frac{1}{2}(e_1+e_2),\\ e_1{e}_2=0,\end{array}\right.{\mathcal{E}}_1:\left\{\begin{array}{l}{e}_1^2=e_1,\\ e_2^2=e_2,\\ e_1{e}_2=0.\end{array}\right.$ Here, $rk\left({\mathcal{E}}_{1/2}\right)=1$ and $rk\left({\mathcal{E}}_1\right)=2$. Algebras ${\mathcal{E}}_2$, ${\mathcal{E}}_6(0,0)$ and ${\mathcal{E}}_7\left(0\right)$ in the classification of 2-dimensional real evolution algebras [18, Theorem 1] are also Markov evolution algebras, with structure matrices: ${\mathcal{E}}_2:\left(\begin{array}{cc}1& 0\\ 1& 0\end{array}\right),{\mathcal{E}}_6(0,0):\left(\begin{array}{cc}1& 0\\ 0& 1\end{array}\right),{\mathcal{E}}_7\left(0\right):\left(\begin{array}{cc}0& 1\\ 1& 0\end{array}\right).$ Notice now $rk\left({\mathcal{E}}_2\right)=1$, whereas $rk\left({\mathcal{E}}_6\right(0,0\left)\right)=rk\left({\mathcal{E}}_7\right(0\left)\right)=2$. We recall here that the rank $rk\left(\mathcal{E}\right)$ of an evolution algebra $\mathcal{E}$ equals $\mathrm{d}\mathrm{i}\mathrm{m}\left({\mathcal{E}}^2\right)$.

Remark 2.1

As many other properties of evolution algebras, being Markov may depend on the natural basis. Therefore, natural basis (as evolution algebras) of Markov evolution algebras need to be assumed to be Markov-natural (M-natural, for short), that is, to be bases giving rise to Markov structure matrices. To illustrate this, let us consider the 2-dimensional evolution algebra ${\mathcal{E}}_{1/2}$ (see Example 2.4(iv)) with natural basis $\mathcal{B}=\{e_1,e_2\}$ and multiplication $e_1^2=e_2^2=\frac{1}{2}(e_1+e_2)$. The structure matrix of ${\mathcal{E}}_{1/2}$ is then: $\mathbf{A}=\left(\begin{array}{cc}\frac{1}{2}& \frac{1}{2}\\ \frac{1}{2}& \frac{1}{2}\end{array}\right).$ Consider now a second (natural) basis ${\mathcal{B}}^{\prime }=\{f_1,f_2\}$, where f₁ = e₁ + e₂ and f₂ = e₁ − e₂. Then $f_1^2=f_1$ and $f_2^2=0$ giving rise to the structure matrix ${\mathbf{A}}^{\prime }=\left(\begin{array}{cc}1& 0\\ 0& 0\end{array}\right),$ which is clearly not row stochastic. Hence $\mathcal{B}$ is M-natural, but ${\mathcal{B}}^{\prime }$ is not.

Example 2.5

Consider the evolution algebras induced by the cycle graph with five vertices C₅ and by the random walk on C₅ [19, Example 2.5]: $\begin{array}{rl}& \mathcal{A}\left(C_5\right):\left\{\begin{array}{l}{e}_1^2=e_2+e_5,\\ e_i^2=e_{i-1}+e_{i+1},i=2,3,4,\\ e_5^2=e_1+e_4,\\ e_i{e}_j=0,i\ne j.\end{array}\right.\\ & {\mathcal{A}}_{RW}\left(C_5\right):\left\{\begin{array}{l}{e}_1^2=\frac{1}{2}{e}_2+\frac{1}{2}{e}_5\\ e_i^2=\frac{1}{2}{e}_{i-1}+\frac{1}{2}{e}_{i+1},i=2,3,4,\\ e_5^2=\frac{1}{2}{e}_1+\frac{1}{2}{e}_4,\\ e_i{e}_j=0,i\ne j.\end{array}\right.\end{array}$ Both $\mathcal{A}\left(C_5\right)$ and ${\mathcal{A}}_{RW}\left(C_5\right)$ are evolution algebras w.r.t. $\mathcal{B}=\{e_1,\dots ,e_5\}$, but only ${\mathcal{A}}_{RW}\left(C_5\right)$ is Markov. However, $\mathcal{A}\left(C_5\right)\cong {\mathcal{A}}_{RW}\left(C_5\right)$ by [20, Theorem 3.2(i)]. The case of the wheel graph W_n (n>4) is similar, with ${\mathcal{A}}_{RW}\left(W_n\right)$ being Markov, but $\mathcal{A}\left(W_n\right)$ not Markov. However, ${\mathcal{A}}_{RW}\left(W_n\right)≆\mathcal{A}\left(W_n\right)$ as evolution algebras [20, Proposition 3.5].

In what follows, natural bases of Markov evolution algebras will be assumed to be M-natural basis and to remain fixed throughout.

M-natural bases are normalized natural bases ($\parallel e_i^2{\parallel }_1=1$ for all i = 1, …, n w.r.t. the l₁-norm) and unital ($\parallel e_i{\parallel }_1=1$ ). Thus Markov evolution algebras are normed algebras w.r.t. $\parallel \cdot {\parallel }_1$ and therefore, by finite-dimensionality, Banach evolution algebras [9, Corollary 2.5] and [1, Chapter I.3.3, p. 36].

The notion of graph $\mathrm{\Gamma }(\mathcal{E},\mathcal{B})=(V,E)$ attached to an evolution algebra $\mathcal{E}$ relative to a natural basis $\mathcal{B}$ was introduced in [6, Definition 2.2]. Recall (i, j) ∈ E if and only if a_ij ≠ 0. This corresponds to the usual notion of (weighted) digraph G(A) associated to its structure matrix A and therefore implies having state i leading to state j (i → j) in the Markov chain, since i → j if and only if $a_{ij}^{\left(k\right)}>0$ for some integer k ≥ 1 [10, p. 12].

Remark 2.2

Baric evolution algebras were characterized in [7, Theorem 3.2] as follows: An n-dimensional real evolution algebra $\mathcal{E}$ is baric if and only if there is a column ${\mathbf{A}}_{:i_0}=(a_{1i_0},\dots ,a_{n{i}_0}{)}^{\mathrm{T}}$ of its structure matrix A with $a_{i_0{i}_0}\ne 0$ and $a_{i{i}_0}=0$ for all i ≠ i₀. The weight map is then defined by $\omega \left(x\right)=a_{i_0{i}_0}{x}_{i_0}$, for all $x\in \mathcal{E}$. Moreover, see [7, Corollary 3.3], $\mathcal{E}$ has exactly as many weight functions as columns ${\mathbf{A}}_{:i_j}=(a_{1i_j},\dots ,a_{n{i}_j}{)}^{\mathrm{T}}$ of the structure matrix A satisfy the given condition, j = i₁, …, i_m, m ≤ n.

Proposition 2.6

Let $\mathcal{E}$ be a Markov evolution algebra. If $\mathcal{E}$ is a baric algebra, then the underlying HDT Markov chain is reducible.

Proof.

If $\mathcal{E}$ is baric, by [7, Theorem 3.2], its structure matrix A contains a column ${\mathbf{A}}_{:i_0}=(a_{1i_0},\dots ,a_{n{i}_0}{)}^{\mathrm{T}}$ such that $a_{i{i}_0}={\delta }_{i{i}_0}{a}_{i_0{i}_0}$, which amounts to $i\nrightarrow i_0$ for any i ≠ i₀, meaning that i₀ cannot be reached from any other state i, and therefore implying that the underlying HDT Markov chain is reducible. This follows from the fact all entries in the i₀th column of ${\mathbf{A}}^k=(a_{ij}^{\left(k\right)}{)}_{i,j=1}^n$ vanishes, but $a_{i_0{i}_0}^{\left(k\right)}=(a_{i_0{i}_0}{)}^k$.

Remark 2.3

We note that reducibility is, however, not enough for ensuring the existence of characters. Indeed, consider the Markov evolution algebra $\mathcal{E}$ with structure matrix $\mathbf{A}=\left(\begin{array}{cccc}0& 1& 0& 0\\ 1& 0& 0& 0\\ 0& 0& 0& 1\\ 0& 0& 1& 0\end{array}\right),$ and reducible underlying Markov chain, having two (obviously disjoint) essential classes. Clearly, [7, Theorem 3.2] is not satisfied, and therefore $\mathcal{E}$ is not baric.

Graphically (also equivalently, in terms of the Markov chain states topology), a Markov evolution algebra is baric if and only if there exists a state i₀ ∈ {1, …, n} such that i₀ → i₀ ($\mathrm{\Gamma }(\mathcal{E},\mathcal{B})$ has a loop at i₀) and $i\nrightarrow i_0$, for any i ≠ i₀, that is i₀ is a source. The number of different weight maps is then given by the number of sources of $\mathrm{\Gamma }(\mathcal{E},\mathcal{B})$, with a loop at them. The existence of sources, being a requirement for that of characters, leads us to the following result.

Corollary 2.7

Let $\mathcal{E}$ be a Markov evolution algebra. If $\mathrm{\Gamma }(\mathcal{E},\mathcal{B})$ is strongly connected, then $\mathcal{E}$ has no nonzero character ($\mathcal{E}$ is not a baric algebra).

Proposition 2.8

Markov evolution algebras are not nil (nor nilpotent).

Proof.

Let $\mathcal{E}$ be a Markov evolution algebra with M-natural basis $\mathcal{B}$. Then no reordering of the elements of $\mathcal{B}$ can produce an strictly upper triangular matrix (as all row totals remain equal to 1). The result now follows from [5, Theorem 2.7].

Proposition 2.9

Markov evolution algebras have no nonzero absolute nilpotent elements (i.e. elements $x\in \mathcal{E}$ such that x² = 0).

Proof.

Let $x=\sum _{i=1}^n{x}_i{e}_i\in \mathcal{E}$ and write $x^2=\sum _{j=1}^n\left(\sum _{i=1}^n{x}_i^2{a}_{ij}\right)e_j$. Assume now x is a nonzero absolute nilpotent element and take i₀ ∈ {1, …, n} such that $x_{i_0}\ne 0$. Since A is nonnegative, it then follows that $a_{i_{0}j}=0$ for all j = 1, …, n, contradicting the row stochasticity of A.

Proposition 2.10

Let $\mathcal{E}$ be a Markov evolution algebra. Then the evolution element $e=\sum _{i=1}^n{e}_i$ is idempotent if and only if A is a doubly stochastic matrix.

Proof.

We note that $e^2=(e_1+\cdots +e_n{)}^2=\sum _{i=1}^n{e}_i^2=\sum _{i=1}^n(\sum _{j=1}^n{a}_{ij}{e}_j)=\sum _{j=1}^n(\sum _{i=1}^n{a}_{ij})e_j$. Thus, since A is nonnegative, e² = e amounts to have $\sum _{i=1}^n{a}_{ij}=1$ for all j = 1, …, n, that is, to A also have column sums equal to 1.

Spectral theory of nonnegative matrices, including Markov matrices, has been broadly studied [10,13]. A nonnegative n × n matrix A (A ≥ 0 i.e. a_ij ≥ 0 for all i, j = 1, …, n) is positive (A > 0) if a_ij > 0 for all i, j = 1, …, n; and primitive if A^k > 0 for some positive integer k. Irreducibility means that for every pair i, j ∈ {1, …, n} there exists a positive integer k such that $a_{ij}^{\left(k\right)}$, the (i, j)th entry of A^k, is (strictly) positive. Eigenvalues of primitive and irreducible Markov matrices follow from Perron–Frobenius Theorem [10, Theorem 1.1, Theorem 1.5]. If A is primitive and Markov, then A has eigenvalue λ = 1 with algebraic and geometric multiplicity 1, and |λ_i| < 1 for any other eigenvalue λ_i ≠ 1 of A. If A is irreducible, but not primitive, then |λ_i| ≤ 1, and, in general, algebraic and geometric multiplicities of λ = 1 are given by the number of communication classes of A [13, pp. 197–198]. Equivalent results can be found in [1, 4.3].

The analytic study of evolution algebras, carried on in [9] and focused on the ergodic behaviour of evolution operators of finite-dimensional evolution algebras, can be understood as a generalization of previously mentioned results in the case of primitive nonnegative matrices.

Definition 2.11

The evolution operator $L:\mathcal{E}\to \mathcal{E}$ of an evolution algebra (w.r.t. $\mathcal{B}$) is defined as the (left) multiplication L(x) = ex by the evolution element $e=\sum _{i=1}^n{e}_i$.

The evolution operator L of a Markov evolution algebra leaves invariant the (n − 1)-dimensional simplex Δ⁽ⁿ⁻¹⁾ that can be understood as the set of probability distributions of the underlying (genetic, dynamical,…) system.

Remark 2.4

Let a be an element of a finite-dimensional commutative real algebra $\mathcal{A}$, and let L_a(x) = ax, for all $x\in \mathcal{A}$, be the left multiplication by the element a. The m-spectrum of a is ${\sigma }_m\left(a\right)=\left\{\begin{array}{ll}\sigma \left(L_a\right),& \mathrm{i}\mathrm{f}\mathcal{A}\mathrm{i}\mathrm{s}\mathrm{u}\mathrm{n}\mathrm{i}\mathrm{t}\mathrm{a}\mathrm{l};\\ \sigma \left(L_a\right)\cup \left\{0\right\},& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e};\end{array}\right.$ where as usual, $\sigma \left(L_a\right)=\{\lambda \in \mathbb{C}\mid L_a-\lambda I\text{is not bijective}\}$ denotes the spectrum of L_a (as linear map). The m-spectral radius of a is $\rho \left(a\right)=\left\{\begin{array}{ll}sup\{|\lambda |\mid \lambda \in {\sigma }_m(a\left)\right\},& {\sigma }_m\left(a\right)\ne set;\\ 0,& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}\right.$ Given λ ∈ σ_m(a), the multiplicative a-index of λ, denoted ν(λ, a) = ν(λ, L_a), is the size of the largest Jordan block corresponding to λ in the canonical Jordan normal block matrix associated to L_a (with ν(λ, a) = 0 if $\lambda \notin \sigma \left(L_a\right)$). We refer the reader to [9, Definition 4.3, Definition 4.4, Theorem 4.13, Definition 4.14] for more accurate details on the m-spectrum, m-spectral radius and multiplicative index of the elements of evolution algebras. We only note here that, despite the differences with the notation used in [9], the eigenvalues of the evolution operator L = L_e are exactly those of the structure matrix A of $\mathcal{E}$ [9, Equation 4.1, p. 120].

Theorem 2.12

Let e be the evolution element of a Markov evolution algebra $\mathcal{E}$ (w.r.t. a M-natural basis $\mathcal{B}$) with primitive structure matrix A. Then:

1. ${\sigma }_m\left(e\right)=\sigma \left(\mathbf{A}\right)\cup \left\{0\right\}$ and ρ(e) = 1.

2. The multiplicative e-index of λ = 1 is ν(1, e) = 1.

3. e is an equilibrium generator of $\mathcal{E}$, equivalently $\mathcal{E}$ reaches $\mathcal{B}$-equilibrium, that is $\left(L_e^k\right(b){)}_{k\in \mathbb{N}}$ converges for all $b\in \mathcal{E}$. (See equivalent conditions in [9, Proposition 4.7].)

Proof.

(i) Follows from [9, Proposition 4.5] taking into account Perron–Frobenius Theorem for primitive Markov matrices. For (ii), it suffices to recall that the algebraic and geometric multiplicity of λ = 1 for A is one (see more details in [9, Proposition 4.13]). Finally, (iii) is [9, Corollary 4.17].

Remark 2.5

In this setting, we have dim(ker(A − I_n)) = m_a(1, A) = m_g(1, A) = 1 = rank(lim _k→∞A^k) [9, Proposition 4.10, Proposition 4.13]. Note the last equality also follows from the Ergodic Theorem for Primitive Markov Chains [10, Theorem 4.2], since then A^k → 1v^T, where v denotes the unique stationary distribution of the Markov chain, and convergence is elementwise. Therefore results in [9, Proposition 4.7] on the ergodicity of multiplication operators of the form $\left(L_a^k\right(b){)}_{k\in \mathbb{N}}$ can be understood as a generalization of the Ergodic Theorem for Primitive Markov Chains for arbitrary finite-dimensional evolution algebras.

Example 2.13

Consider a 2-dimensional Markov evolution algebra $\mathcal{E}$ with positive (hence primitive) structure matrix $\mathbf{A}=\left(\begin{array}{cc}1-a& a\\ b& 1-b\end{array}\right),$ for some a, b ∈ (0, 1). Then σ(A) = {1, 1 − a − b} and dim(ker(A − I_n)) = m_a(1, A) = m_g(1, A) = 1. A classical result states that 1 = (1, 1)^T is a right eigenvector of A of eigenvalue 1 with stationary probability distribution $\mathbf{v}=\frac{1}{a+b}(b,a{)}^{\mathrm{T}}$, and ${\mathbf{A}}^{\mathrm{\infty }}=\underset{k\to \mathrm{\infty }}{lim}{\mathbf{A}}^k=\mathbf{1}{\mathbf{v}}^T=\frac{1}{a+b}\left(\begin{array}{cc}b& a\\ b& a\end{array}\right)$ has rank one. Thus, given $x=x_1{e}_1+x_2{e}_2\in \mathcal{E}$, we have $L_e^k\left(x\right)\to {\mathbf{x}}^T\mathbf{1}{\mathbf{v}}^T$, with x = (x₁, x₂)^T.

3. The structure of Markov evolution algebras

In this section, we delve into the structure of Markov evolution algebras. To do this basic ideals are considered. A proper ideal I of an evolution algebra $\mathcal{E}$ is an i-basic ideal w.r.t. a natural basis $\mathcal{B}=\{e_1,\dots ,e_n\}$ if I is generated by i vectors of $\mathcal{B}$ [11, Definition 2.1]. We recall here, that for any finite-dimensional perfect evolution algebra ($\mathcal{E}={\mathcal{E}}^2$), simplicity and basic simplicity are equivalent [11, Proposition 2.7].

Definition 3.1

[3, Definition 2.16]

An evolution algebra $\mathcal{E}$ is nondegenerate if it has a natural basis $\mathcal{B}=\{e_1,\dots ,e_n\}$ such that $e_i^2\ne 0$ for all i = 1, …, n. Nondegeneracy is equivalent to $ann\left(\mathcal{E}\right)=\{x\in \mathcal{E}\mid x\mathcal{E}=0\}=0$ [3, Corollary 2.19].

Proposition 3.2

Markov evolution algebras are nondegenerate.

Proof.

Recall first $ann\left(\mathcal{E}\right)=\{x\in \mathcal{E}\mid x\mathcal{E}=0\}={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_i\mid e_i^2=0)$ [6, Lemma 2.7]. Hence to prove that a Markov evolution algebra is nondegenerate, it suffices to check $e_i^2\ne 0$, for all i = 1, …, n. But this follows from Proposition 2.9 on the existence of no nonzero absolute nilpotent elements in Markov evolution algebras. Indeed, note that $e_i^2=0$ would imply that the ith row A_i: = (a_i1, …, a_in)^T of the structure matrix A of $\mathcal{E}$ vanishes, contradicting the row stochasticity of A.

Proposition 3.3

Let $\mathcal{E}$ be a Markov evolution algebra. Then $\mathcal{E}$ is indecomposable (there exist no nonzero ideals I and J such that $\mathcal{E}=I\oplus J$) if and only if $\mathrm{\Gamma }(\mathcal{E},\mathcal{B})$ is strongly connected.

Proof.

It follows from [6, Proposition 2.8], as a result of Proposition 3.2.

Ideals considered in Proposition 3.3 have their usual meaning, despite the different notions of (evolution) ideals found in the literature (see , for instance, [1,3]). A similar result follows from [3, Lemma 5.2, Corollary 5.8], as a consequence of nondegenerancy of Markov evolution algebras (Proposition 3.2).

Remark 3.1

A Markov evolution algebra $\mathcal{E}$ is perfect if and only if its structure matrix A is nonsingular (det(A) ≠ 0) [6, Proposition 4.2]. This follows into natural bases to be unique up to permutation and scalar multiplication [6, Corollary 4.7]. A similar result holds for M-natural basis, since if $\mathcal{B}=\{e_1,\dots ,e_n\}$ is M-natural, so is ${\mathcal{B}}^{\prime }=\{\pm e_{\sigma \left(1\right)},\dots ,\pm e_{\sigma \left(n\right)}\}$ for all σ ∈ S_n.

Following the previous section, in what follows, we consider $\mathcal{E}$ to be a Markov evolution algebra with structure matrix A w.r.t. a M-natural basis $\mathcal{B}=\{e_1,\dots ,e_n\}$, and identify $\mathcal{B}\cong \mathrm{\Lambda }$ in the obvious way, where Λ = {1, …, n} is the state set of the underlying HDT Markov chain.

Remark 3.2

We refer to [10, p. 12] for the notion of essential and inessential classes of states of nonnegative matrices, and to [12, II.2.3] for the notion of communication class of states of Markov chains. We note that any essential class forms a communication class, but the converse is not true, as communication classes may not be closed [12, Definition 2.9]. Indeed, states in an essential class communicate to each other, but cannot lead to any other state outside their class. However, the equivalence relation defining communication classes [12, Definition 2.7] does not exclude the existence of states leading to states outside it.

Lemma 3.4

Let $\mathcal{E}$ be a Markov evolution algebra with M-natural basis $\mathcal{B}$. Then, under $\mathcal{B}\cong \mathrm{\Lambda },$ any closed subset of states of Λ generates a basic ideal of $\mathcal{E},$ and, conversely, any basic ideal defines a closed subset of Λ. This ideal is basic simple if and only if the closed subset forms an essential class.

Proof.

Assume, after relabelling if necessary, C = {1, …, r} ⊂ Λ is closed. Then $a_{ij}^{\left(k\right)}=0$ for all 1 ≤ i ≤ r < j ≤ n, and any positive integer $k\in \mathbb{N}$. This implies $e_i^2=\sum _{j=1}^n{a}_{ij}{e}_j=\sum _{s\in C}{a}_{is}{e}_s\in I={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_s\mid s\in C)$, for every i ∈ C. Hence I is a basic ideal of $\mathcal{E}$. Conversely, let I be a basic ideal of $\mathcal{E}$, and write $I={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_s\mid s\in C)$, with C ⊂ Λ. Then, for all i ∈ C, $e_i^2\in I$ implies a_ij = 0 for all $j\notin C$, and also $a_{ij}^{\left(k\right)}=0$ for all $k\in \mathbb{N}$. Hence C is closed.

The last statement is clear.

Theorem 3.5

Let $\mathcal{E}$ be a Markov evolution algebra with structure matrix A w.r.t. a M-natural basis $\mathcal{B}$. Then, suitably relabelling the elements of $\mathcal{B}$:

1. A has a block structure: $\mathbf{A}=\left(\begin{array}{cccccc}{\mathbf{A}}_1& 0& 0& \cdots & 0& 0\\ 0& {\mathbf{A}}_2& 0& \cdots & 0& 0\\ 0& 0& {\mathbf{A}}_3& \cdots & 0& 0\\ ⋮& ⋮& ⋮& \ddots & ⋮& ⋮\\ 0& 0& 0& \cdots & {\mathbf{A}}_r& 0\\ & & \mathbf{R}& & & \mathbf{Q}\end{array}\right),$ where A_k is a n_k × n_k matrix, for k = 1, …, r, and $\mathrm{\Lambda }=\{1,\dots ,n\}={\mathrm{\Lambda }}_1\bigsqcup \cdots \bigsqcup {\mathrm{\Lambda }}_r\bigsqcup {\mathrm{\Lambda }}_{r+1}$ (disjoint union), with Λ_k = {n₁ + · · · + n_k−1 + 1, …, n₁ + · · · + n_k} for k = 1, …, r + 1, and n = n₁ + · · · + n_r+1.

2. $I_k={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_s\mid s\in {\mathrm{\Lambda }}_k)$ is an n_k-basic ideal of $\mathcal{E}$ with M-natural basis ${\mathcal{B}}_k=\{e_{n_1+\cdots n_{k-1}+1},\dots ,e_{n_1+\cdots +n_k}\}$ and structure matrix A_k, for all 1 ≤ k ≤ r. Moreover, I_kI_s = 0 for all k ≠ s = 1, …, r.

3. Ideals I_k are basic simple, for all k = 1, …, r.

4. $\mathcal{E}=\bigcup _{s=1}^{r+1}{\mathcal{F}}_s,$ where ${\mathcal{F}}_s=\bigcup _{j=1}^s{I}_j$ is a proper (n₁ + · · · + n_s)-basic ideal of $\mathcal{E}$, for all s = 1, …, r, is a filtration of $\mathcal{E}$.

5. $\mathcal{E}$ admits a grading $\mathcal{E}=\underset{s=1}{\overset{r+1}{⨁}}{\mathcal{E}}_s,$ with ${\mathcal{F}}_1={\mathcal{E}}_1=I_1$ and ${\mathcal{E}}_s={\mathcal{F}}_s/{\mathcal{F}}_{s-1},$ for 2 ≤ s ≤ r + 1. Moreover, ${\mathcal{E}}_s\cong I_s$ for 1 ≤ s ≤ r.

Proof.

(i) The block structure of A, after a suitable index relabelling, arises from the classification into essential and inessential classes of the indices of any nonnegative matrix and it corresponds to the so-called canonical form of the nonnegative matrix [10, p. 14]. It is then straightforward to check (ii), i.e. that I_k is an n_k-basic ideal with M-natural basis ${\mathcal{B}}_k$ and structure matrix A_k, for all 1 ≤ k ≤ r. The orthogonality of these ideals is clear.

Next, (iii) follows from Lemma 3.4 and, finally, statements (iv)–(v) are standard.

The threefold identification between elements of M-natural bases of Markov evolution algebras, indices of their (nonnegative) structure matrices and states of the underlying HDT Markov chains, is the cornerstone of the above decomposition into minimal basic ideals, together to an additional term gathering the inessential (transient) behaviour within the Markov evolution algebras. We recall here that classification into (in)essential classes only depends on the vanishing or non-vanishing of the (nonnegative) entries a_ij. Thus any two Markov evolution algebras with the same incidence matrix (the matrix that arises when replacing all strictly positive matrix entries of the structure matrix by ones) have the same decomposition. This fact can also be seen as a result of both having the same (un-weighted) digraph.

4. Examples

Although evolution algebras were firstly introduced in connection to non-Mendelian genetics, some of their most recent examples arise from those areas they turned out to be related to [[20, 2.1], [1, 4.4.7]]. In this section, we exploit some well-known Markov processes modelling different stochastic processes to define the corresponding Markov evolution algebras.

4.1. Birth and death processes

Consider a birth and death process on {0, 1…, N} with absorbing states 0 and N. The (N + 1) × (N + 1) transition matrix is $\mathbf{A}=\left(\begin{array}{cccccccc}1& 0& 0& 0& \cdots & 0& 0& 0\\ q& 0& p& 0& \cdots & 0& 0& 0\\ 0& q& 0& p& \cdots & 0& 0& 0\\ ⋮& ⋮& ⋮& ⋮& \ddots & ⋮& ⋮& ⋮\\ 0& 0& 0& 0& \cdots & 0& p& 0\\ 0& 0& 0& 0& \cdots & q& 0& p\\ 0& 0& 0& 0& \cdots & 0& 0& 1\end{array}\right),$ where we have (p + q = 1, p, q ≥ 0): $a_{ij}=P(X_{k+1}=j\mid X_k=i)=\left\{\begin{array}{ll}p,& j=i+1;\\ q,& j=i-1;\\ 0,& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e};\end{array}\right.$ and, additionally, a₀₀ = 1 = a_NN [12, Example 2.3]. Let $\mathcal{E}$ be the (N + 1)-dimensional Markov evolution algebra with structure matrix A w.r.t. $\mathcal{B}=\{e_0,e_1,\dots ,e_N\}$. Clearly det(A) = 0 and, the decomposition of the state space Λ = {0, 1…, N} of the underlying HDT Markov chain into three (disjoint) communication classes $\mathrm{\Lambda }=\left\{0\right\}\bigsqcup \{1,2,\dots ,N-1\}\bigsqcup \left\{N\right\}$ (see Remark 3.2) proves that $\mathcal{E}$ is not simple as it contains two 1-dimensional (basic) ideals $I_0=\mathbb{R}{e}_0$ and $I_N=\mathbb{R}{e}_N$, both corresponding to absorbing states. Note, however, that ${\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_1,\dots ,e_{n-1})$ is not a (basic) ideal, since the communication class {1, 2, …, N − 1} is not closed. This fact is easily illustrated by the digraph $\mathrm{\Gamma }(\mathcal{E},\mathcal{B})$, that in case when N = 3 is given by

This Markov evolution algebra $\mathcal{E}$ provides an alternative example of non-perfect finite-dimensional evolution algebra with non-unique maximal basic ideals [11, Example 2.6]. It is also clear that $\mathcal{E}$ is not baric (see Remarks 2.2 and 2.3).

General birth and death processes [12, 3.6] do provide more general examples of Markov evolution algebras, with properties such as being perfect, simple or baric depending on birth and death probabilities.

4.2. Greenwood model

Greenwood model is a simplified version of a bivariate Markov chain for binomial epidemic models. Let $\left\{\right(S,I{)}_k{\}}_{k=0}^{\mathrm{\infty }}$, being S_k and I_k discrete random variables for, respectively, the number of susceptible and infected individuals at time k. In this model S_k = S_k+1 + I_k+1, that is, susceptible individuals at time k are either still susceptible or already infected at time k + 1, as no births nor deaths are assumed [21]. In Greenwood model $P\left(\right(s,i{)}_{k+1}\mid (s,i{)}_k)=\left(\genfrac{}{}{0em}{}{s_k}{s_{k+1}}\right)p^{s_{k+1}}(1-p{)}^{s_k-s_{k+1}},$ where 1−p is the probability of contact resulting in infection. Assuming I₀ > 0, the state space is Λ = {0, 1, …, s₀} with S₀ = s₀ > 0 being the maximal number of possible infected individuals [12, 3.10.1]. The transition matrix is $\mathbf{A}=\left(\begin{array}{ccccc}1& 0& 0& \cdots & 0\\ 1-p& p& 0& \cdots & 0\\ (1-p{)}^2& 2p(1-p)& p^2& \cdots & 0\\ ⋮& ⋮& ⋮& \ddots & ⋮\\ (1-p{)}^{s_0}& \left(\genfrac{}{}{0em}{}{s_0}{1}\right)p(1-p{)}^{s_0-1}& \left(\genfrac{}{}{0em}{}{s_0}{2}\right)p^2(1-p{)}^{s_0-2}& \cdots & p^{s_0}\end{array}\right),$ giving $e_i^2=\left(\genfrac{}{}{0em}{}{i}{0}\right)(1-p{)}^i{e}_0+\left(\genfrac{}{}{0em}{}{i}{1}\right)p(1-p{)}^{i-1}{e}_1+\cdots +\left(\genfrac{}{}{0em}{}{i}{i}\right)p^i{e}_i$, for all i = 0, 1, …, s₀.

The corresponding n = (s₀ + 1)-dimensional Markov evolution algebra $\mathcal{E}$ is perfect ($\mathrm{d}\mathrm{e}\mathrm{t}\left(\mathbf{A}\right)=p^{\frac{s_0(s_0+1)}{2}}\in (0,1)$ ), but not simple, since $J_i={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_1,\dots e_{i+1})$ is an (i + 1)-dimensional (basic) ideal of $\mathcal{E}$, for all i = 0, …, s₀ [11, Proposition 2.7]. Assuming s₀ = 3 and following the terminology introduced in [?], $\mathcal{E}$ provides an example of 4-dimensional perfect non-simple evolution algebra containing a 3-basic ideal which has a 2-basic ideal, not satisfying classification condition (3, 2, 3).

4.3. Jukes–Cantor model

The Jukes–Cantor model for molecular evolution has doubly stochastic transition matrix: $\mathbf{A}=\left(\begin{array}{cccc}1-3a& a& a& a\\ a& 1-3a& a& a\\ a& a& 1-3a& a\\ a& a& a& 1-3a\end{array}\right),$ where for i, j = A, G, C, T (DNA bases) a_ij = P(X_k+1 = j| X_k = i) = a, i ≠ j. Moreover, det(A) = (1 − 4a)³ and σ(A) = {1, 1 − 4a}. Thus A is a positive, hence irreducible, matrix if a ∈ (0, 1/3), and for a ∈ (0, 1/3) − {1/4}, the corresponding evolution algebra $\mathcal{E}$ with structure matrix A is a 4-dimensional simple (perfect) Markov algebra, and $\mathrm{\Gamma }(\mathcal{E},\mathcal{B})$ is strongly connected. We recall here that Jukes-Cantor model is a particular case of Kimura 3ST model with additional symmetries (see, for instance, [22, Definition 2.1]).

5. Continuous-time Markov chains

Let {X(t)| t ∈ [0, ∞)} be discrete random variables with values in a finite set Λ = {1, …, n}, and continuous index set t ∈ [0, ∞). We refer to [12,13] for background on these processes.

Definition 5.1

A continuous-time Markov chain (CTMC) is a stochastic process {X(t)}_t≥0 satisfying the Markov property, i.e. for any sequence 0 ≤ t₀ < t₁ < … < t_k < t_k+1, P(X(t_k+1) = i_k+1| X(t₀) = i₀, …, X(t_k) = i_k) = P(X(t_k+1) = i_k+1| X(t_k) = i_k).

Assuming transition probabilities p_ij(t, s) = P(X(t) = j| X(s) = i), for s<t, only depend on the time interval length t−s (homogeneity), we write p_ij(t) = P(X(t) = j| X(0) = i). Transition probability matrices $\mathbf{P}\left(t\right)=\left(p_{ij}\right(t){)}_{i,j=1}^n$ are nonnegative row stochastic for all t ≥ 0 (i.e. Markov matrices), and satisfy Chapman–Kolmogorov equation P(t + s) = P(t)P (s), for all s, t ≥ 0. Also P(0) = I_n, since p_ij(0) = P(X(0) = j| X(0) = i) = δ_ij, i, j = 1, …, n. Functions p_ij(t) = P(X(t) = j| X(0) = i), for all t ≥ 0, are the transition functions of the process, and the set {P(t)}_t≥0 is the transition or stochastic semigroup of the CTMC on Λ = {1, …, n}.

Definition 5.2

[13, Chapter 8, Section 2.2]

A family {P(t)}_t≥0 of (n × n) real matrices forms a (finite) stochastic semigroup on a finite Λ = {1, …, n}, if for each t, s ≥ 0:

1. P(t) is a Markov matrix.

2. P(0) = I_n.

3. P(t + s) = P(t)P(s) (Chapman–Kolmogorov equation or semigroup property).

A stochastic semigroup is called standard if:

1. $\underset{t\to 0^{+}}{lim}\mathbf{P}\left(t\right)=\mathbf{P}\left(0\right)={\mathbf{I}}_n$, componentwise.

Remark 5.1

As |Λ| = n is finite, continuity at origin (t = 0) of stochastic semigroups ensures continuity at any other time t ≥ 0, as well as differentiability at the origin. This implies the existence and finiteness of the defining limits of the infinitesimal generator or rate matrix [13, Chapter 8, Section 2.2]. Additional analytic properties of stochastic semigroups can be found at [23, Chapter V].

Definition 5.3

The infinitesimal generator or rate matrix of a CTMC is $\mathbf{Q}=(q_{ij}{)}_{i,j=1}^n$ with $q_{ij}=\underset{\mathrm{\Delta }t\to 0^{+}}{lim}\frac{p_{ij}\left(\mathrm{\Delta }t\right)-p_{ij}\left(0\right)}{\mathrm{\Delta }t},$ equivalently, in matrix notation, componentwise, $\mathbf{Q}=\underset{\mathrm{\Delta }t\to 0^{+}}{lim}\frac{\mathbf{P}\left(\mathrm{\Delta }t\right)-{\mathbf{I}}_n}{\mathrm{\Delta }t}.$

Remark 5.2

1. Constants q_ij are transition rates from state i to state j and satisfy: q_ij ≥ 0 if i ≠ j, and $q_{ii}=-\sum _{j=1,j\ne i}^n{q}_{ij}$; i.e. Q has nonnegative off-diagonal entries and zero row sums (Q1 = 0, where 1 = (1, …, 1)^T and 0 = (0, …, 0)^T ), i.e. Q is a Markov generator.

2. Standard (finite state) stochastic semigroups {P(t)}_t≥0 satisfy Backward and Forward Kolmogorov differential equations: $\left(\mathrm{B}\right):\frac{\mathrm{d}}{\mathrm{d}t}\mathbf{P}\left(t\right)=\mathbf{Q}\mathbf{P}\left(t\right)\left(\mathrm{F}\right):\frac{\mathrm{d}}{\mathrm{d}t}\mathbf{P}\left(t\right)=\mathbf{P}\left(t\right)\mathbf{Q}$ with initial condition P(0) = I_n, and unique solution $\mathbf{P}\left(t\right)=e^{t\mathbf{Q}}=\sum _{k=0}^{\mathrm{\infty }}{\mathbf{Q}}^k\frac{t^k}{k!}$. We refer to [24, Remark VII.2.3] for a digression about dynamics underlying above differential equations.

6. Continuous-time Markov evolution algebras

Let $\mathcal{E}$ be a finite-dimensional real vector space with basis $\mathcal{B}=\{e_1,\dots ,e_n\}$ and consider the continuous index set ${\mathbb{R}}_{\ge 0}=[0,\mathrm{\infty })$. We denote by $\mathcal{E}\left(t\right)=\{{\mathcal{E}}_t=(\mathcal{E},m\left(t\right)){\}}_{t\ge 0}$ the family of evolution algebras with multiplication: $m\left(t\right)(e_i\otimes e_j)=e_i{\cdot }_t{e}_j=\left\{\begin{array}{ll}\sum _{k=1}^n{a}_{ik}\left(t\right)e_k,& i=j=1,\dots ,n;\\ 0,& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e};\end{array}\right.$ and by $\mathbf{A}\left(t\right)=\left(a_{ij}\right(t){)}_{i,j=1}^n$ the structure matrix of ${\mathcal{E}}_t$, for all t ≥ 0. Multiplication will be denoted simply by juxtaposition when t-value (time) is clear.

Definition 6.1

1. A continuous time Markov evolution algebra (CT-Markov EA) is a family $\mathcal{E}\left(t\right)$ of evolution algebras whose structure matrices {A(t)}_t≥0 w.r.t. (the natural basis) $\mathcal{B}$ form a standard stochastic semigroup.

2. We call rate matrix of a CT-Markov EA $\mathcal{E}\left(t\right)$ to the matrix Q such that A(t) = e^tQ, t ≥ 0.

The existence of the rate matrix Q was discussed in the previous section. The following facts are stated as a lemma for further use. Proofs are straightforward.

Lemma 6.2

Let $\mathcal{E}\left(t\right)$ be a CT-Markov EA.

1. ${\mathcal{E}}_t$ is a Markov evolution algebra, for all t ≥ 0, with M-natural basis $\mathcal{B}$.

2. ${\mathcal{E}}_0$ is the (nonzero) trivial Markov evolution algebra with structure matrix A(0) = I_n.

3. Given a Markov generator Q, the CT-Markov EA $\mathcal{E}\left(t\right)$ (its structure matrices) is the unique solution of (backward and forward) Kolmogorov differential equations with initial condition A(0) = I_n. In fact, recall Q is the derivative of t → A(t) at origin.

In what follows, $\mathcal{E}\left(t\right)$ will denote a CT-Markov EA with standard stochastic semigroup {A(t)}_t≥0 w.r.t. (a M-natural basis) $\mathcal{B}=\{e_1,\dots ,e_n\}$. For convenience, elements of $\mathcal{B}$ will be identified to the finite set of states Λ = {1, …, n} of the underlying continuous-time Markov chain.

Definition 6.3

The embedded Markov evolution algebra ${\mathcal{E}}_e$ of a CT-Markov EA $\mathcal{E}\left(t\right)$ is the Markov evolution algebra with structure matrix (w.r.t. $\mathcal{B}$) the transition matrix ${\mathbf{A}}_e=(a_{ij}{)}_{i,j=1}^n$ of the corresponding HDT embedded Markov chain, that is, $a_{ii}=\left\{\begin{array}{ll}0,& q_{ii}\ne 0;\\ 1,& q_{ii}=0;\end{array}\right.\mathrm{a}\mathrm{n}\mathrm{d}\mathrm{i}\mathrm{f}i\ne j{a}_{ij}=\left\{\begin{array}{ll}-\frac{q_{ij}}{q_{ii}},& q_{ii}\ne 0;\\ 0,& q_{ii}=0,\end{array}\right.$ where $\mathbf{Q}=(q_{ij}{)}_{i,j=1}^n$ denotes the rate matrix of $\mathcal{E}\left(t\right)$.

Remark 6.1

${\mathcal{E}}_e$ is defined by the jump chain or embedded Markov chain $\{Y_k{\}}_{k=0}^{\mathrm{\infty }}$ associated to the corresponding CTMC, where Y_k = X(W_k), being $\{W_k{\}}_{k=0}^{\mathrm{\infty }}$ random variables defining the jump times or waiting times of the CTMC, that is, W_k is the time of the kth jump or time the CTMC remains in state X(W_k−1) before jumping into X(W_k) (and W₀ = 0). Thus, since a_ij = P(Y_k+1 = j| Y_k = i), it holds q_ii = 0 if and only if a_ii = 1, i.e. if state i is absorbing with null change rate. Note ${\mathbf{A}}_e^k=(a_{ij}^{\left(k\right)}{)}_{i,j=1}^n$ gathers probabilities $a_{ij}^{\left(k\right)}=P(Y_k=j\mid Y_0=i)$.

Example 6.4

Let us consider $\mathbf{Q}=\left(\begin{array}{cccc}-1& 1& 0& 0\\ 0& -1& 1& 0\\ 0& 0& -1& 1\\ 1& 0& 0& -1\end{array}\right)\mathrm{a}\mathrm{n}\mathrm{d}{\mathbf{A}}_e=\left(\begin{array}{cccc}0& 1& 0& 0\\ 0& 0& 1& 0\\ 0& 0& 0& 1\\ 1& 0& 0& 0\end{array}\right).$ Matrix A_e tells us that 1 → 2 → 3 → 4 → 1 [12, Examples 5.3 and 5.8]. The solution of Kolmogorov differential equations gives us the CT-Markov evolution algebra $\left\{\mathcal{E}\right(t){\}}_{t\ge 0}$ with multiplication defined by the standard stochastic semigroup: $\begin{array}{rl}\mathbf{A}\left(t\right)& =e^{t\mathbf{Q}}\\ & =\frac{1}{4}\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\\ 1& 1& 1& 1\end{array}\right)+\frac{1}{2}{e}^{-t}\left(\begin{array}{cccc}\cos \left(t\right)& \sin \left(t\right)& -\cos \left(t\right)& -\sin \left(t\right)\\ -\sin \left(t\right)& \cos \left(t\right)& \sin \left(t\right)& -\cos \left(t\right)\\ -\cos \left(t\right)& -\sin \left(t\right)& \cos \left(t\right)& \sin \left(t\right)\\ \sin \left(t\right)& -\cos \left(t\right)& -\sin \left(t\right)& \cos \left(t\right)\end{array}\right)\\ & +\frac{1}{4}{e}^{-2t}\left(\begin{array}{cccc}1& -1& 1& -1\\ -1& 1& -1& -1\\ 1& -1& 1& -1\\ -1& 1& -1& 1\end{array}\right).\end{array}$

Asymptotic behaviour of CT-Markov evolution algebras is given by their embedded Markov evolution algebras. Mimicking analogous notions for CT Markov chains, we introduce the following definitions.

Definition 6.5

Let $\mathcal{E}\left(t\right)$, {A(t)}_t≥0 and $\mathcal{B}$ as before, and consider $e_i,e_j\in \mathcal{B}$. Then e_i leads to e_j if a_ij(t) > 0 for some t ≥ 0 (we then write e_i → e_j), and elements e_i and e_j communicate (e_i ↔ e_j) if e_i → e_j and e_j → e_i.

We remark here that a_ij(t) > 0 for some t ≥ 0, implies a_ij(t) > 0 for all t > 0, and e_i → e_j in ${\mathcal{E}}_e$. Essential, inessential and communication classes of basic elements of CT-Markov evolution algebras are then defined similarly to the DT setting. This results into irreducibility of $\mathcal{E}\left(t\right)$ to be equivalent to that of ${\mathcal{E}}_e$.

Definition 6.6

A CT-Markov evolution algebra $\mathcal{E}\left(t\right)$ is basic simple if there exists no proper basic ideal common to ${\mathcal{E}}_t$, for all t ≥ 0.

Theorem 6.7

A CT-Markov evolution algebra $\mathcal{E}\left(t\right)$ is basic simple if and only if A_e is irreducible.

Proof.

Let $\mathcal{E}\left(t\right)$ be a basic simple CT-Markov evolution algebra. Assuming A_e is reducible, there exist i, j ∈ Λ such that $i\nrightarrow j$, implying that for all $k\in \mathbb{N}$, $a_{ij}^{\left(k\right)}=P(Y_k=j\mid Y_0=i)=0$ and therefore a_ij(t) = 0 for all t ≥ 0. Then $I={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_s\mid i\to s)={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_s\mid a_{is}^{\left(k\right)}>0\mathrm{f}\mathrm{o}\mathrm{r}\mathrm{s}\mathrm{o}\mathrm{m}\mathrm{e}k\in \mathbb{N}$) is a basic ideal of ${\mathcal{E}}_t$, for all t ≥ 0. Moreover, I is proper since $e_j\notin I$, contradicting the basic simplicity of $\mathcal{E}\left(t\right)$.

Assume now A_e is irreducible and (up to relabelling) $I={\mathrm{s}\mathrm{p}\mathrm{a}\mathrm{n}}_{\mathbb{R}}(e_1,\dots ,e_r)$ a proper r-basic ideal of ${\mathcal{E}}_t$ for all t ≥ 0. Take i, j such that 1 ≤ i ≤ r < j ≤ n. Irreducibility of A_e implies $a_{ij}^{\left(k\right)}=P(Y_k=j\mid Y_0=i)>0$ for some nonnegative integer k, and therefore a_ij(t) > 0 for some t ≥ 0, contradicting that I is a proper basic ideal of ${\mathcal{E}}_t$.

It is then easy to prove that the CT-Markov evolution algebra in Example 6.4 is basic simple, whereas that appearing in (forthcoming) Remark 6.2 is not.

Proposition 6.8

Let $\mathcal{E}\left(t\right)$ be a CT-Markov EA with embedded Markov EA ${\mathcal{E}}_e$.

1. ${\mathcal{E}}_t$ (for all t ≥ 0) and ${\mathcal{E}}_e$ are nondegenerate.

2. ${\mathcal{E}}_t$ is perfect for all t ≥ 0, but ${\mathcal{E}}_e$ is not necessarily perfect.

Proof.

(i) Follows from Proposition 3.2, and the first assertion of (ii) results then from det(A(t)) = det(e^tQ) = e^tr(tQ). Finally, we refer to [12, Example 5.9] (see Remark 6.2 below) for a rate matrix Q defining a standard stochastic semigroup, hence a CT-Markov EA, with non-perfect embedded Markov EA, which by (i) above amounts to have det(A_e) = 0 as noted in Remark 3.1.

Remark 6.2

[12, Example 5.9]

Consider the CT-Markov evolution algebra $\mathcal{E}\left(t\right)$ with structure matrix A(t) = e^tQ given by $\left(\begin{array}{cccc}1& 0& 0& 0\\ 1-e^{-t}& e^{-t}& 0& 0\\ 1-2e^{-t}+e^{-2t}& 2e^{-t}-2e^{-2t}& e^{-2t}& 0\\ 1-3e^{-t}+3e^{-2t}-e^{-3t}& 3e^{-t}-6e^{-2t}+3e^{-3t}& 3e^{-2t}-3e^{-3t}& e^{-3t}\end{array}\right),$ and with corresponding rate matrix Q and A_e: $\mathbf{Q}=\left(\begin{array}{cccc}0& 0& 0& 0\\ 1& -1& 0& 0\\ 0& 2& -2& 0\\ 0& 0& 3& -3\end{array}\right),{\mathbf{A}}_e=\left(\begin{array}{cccc}1& 0& 0& 0\\ 1& 0& 0& 0\\ 0& 1& 0& 0\\ 0& 0& 1& 0\end{array}\right).$ Clearly, state i = 4 is a source (with no loops at it) resulting in A_e containing a column of zeros. Therefore, det(A_e) = 0 implying that ${\mathcal{E}}_e$ is not perfect.

Proposition 6.8(ii) yields that properties of standard stochastic semigroups limit when a (discrete-time) Markov evolution algebra $\mathcal{E}$ could exist within a CT-Markov evolution algebra ($\mathcal{E}={\mathcal{E}}_t$, for some t ≥ 0), since any such Markov evolution algebra ${\mathcal{E}}_t$ needs to be perfect. This leads us to consider in the next section the embedding problem.

7. Embeddability of Markov evolution algebras

We will say that a Markov evolution algebra $\mathcal{E}$ is embeddable into a CT-Markov EA $\mathcal{E}\left(t\right)$ if its structure matrix A is embeddable, i.e. if there exists a rate matrix Q such that A = eQ.

If a Markov evolution algebra $\mathcal{E}$ is embeddable, then {A(t) = e^tQ, t ≥ 0} is a standard stochastic semigroup defining a CT-Markov EA $\mathcal{E}\left(t\right)$, such that $\mathcal{E}={\mathcal{E}}_1$, resulting from A = A(1). Uniqueness of the Markov generator Q is not, however, ensured, a question known as the identifiability problem (see [8,14,25] and references therein).

We recall here the following results for further use.

Proposition 7.1

[14, Proposition 2.1]

If a Markov matrix P is embeddable, P = eQ, with Markov generator Q, then:

1. σ(P) = e^σ(Q), where σ(A) denotes the spectrum of a matrix A.

2. 0 < det(P) ≤ 1, so $0\notin \sigma \left(\mathbf{P}\right),$ and det(P) = 1 only for P = I_n.

3. P is either reducible, or positive and hence primitive.

4. If p_ij > 0 and p_jk > 0, then p_ik > 0.

Proposition 7.1 gives a first criterion to discard Markov evolution algebras not realizable by standard stochastic semigroups (i.e. non-embeddable).

Example 7.2

1. Consider the Markov evolution algebras appearing in Example 2.4(iv). The structure matrices of ${\mathcal{E}}_{1/2}$ and ${\mathcal{E}}_2$ are singular and that of ${\mathcal{E}}_7\left(0\right)$ irreducible but not positive. Hence, none of these Markov evolution algebras is embeddable. Markov evolution algebra ${\mathcal{E}}_1$ (i.e. ${\mathcal{E}}_6(0,0)$) has structure matrix I₂, so it is trivially embeddable since I₂ = e^Q for $\mathbf{Q}=\left(\begin{array}{cc}0& 0\\ 0& 0\end{array}\right)$.

2. The Markov evolution algebra ${\mathcal{A}}_{RW}\left(C_5\right)$ given by the random walk on the cycle graph with five vertices C₅ (Example 2.5) is not embeddable, as Proposition 7.1(iv) is not satisfied. Indeed, notice ${\mathcal{A}}_{RW}\left(C_5\right)$ has structure matrix $\mathbf{A}=\left(\begin{array}{ccccc}0& 1/2& 0& 0& 1/2\\ 1/2& 0& 1/2& 0& 0\\ 0& 1/2& 0& 1/2& 0\\ 0& 0& 1/2& 0& 1/2\\ 1/2& 0& 0& 1/2& 0\end{array}\right),$ with a₁₂, a₂₃ > 0 but a₁₃ = 0.

3. Markov evolution algebras arising from birth and death processes on {0, 1…, N} with absorbing states 0 and N are not embeddable, as their structure matrices are singular (see Section 4.1).

4. Jukes–Cantor model (Section 4.3) is given by a 4 × 4 circulant matrix (a matrix is circulant when their rows arise from shifting them cyclically one position to the right). Embeddability of d × d circulant matrices (d ≥ 4) is characterized in [14, Theorem 5.6]. The stochastic semigroup and rate matrix for Jukes–Cantor model can be found in [24, 7.8.1]. The JC model is the simplest nucleotide model as it assumes all mutations occur with an equal rate. More complex models are also given in [24, 7.8.1].

Remark 7.1

Despite being closely related to Markov processes and satisfying Chapman–Kolmogorov type conditions, CEAS are not necessarily embeddable. Consider for instance ${\mathcal{M}}_{22}^{[s,t]}=\left(\begin{array}{cc}f\left(t\right)& 1-f\left(t\right)\\ f\left(t\right)& 1-f\left(t\right)\end{array}\right),$ and assume f(t) ∈ [0, 1] for all t ≥ 0 [26, p. 352]. Then ${\mathcal{M}}_{22}^{[s,t]}$ is Markov, but singular, hence not embeddable.

As noticed above, studying CT-Markov evolution algebras becomes to be related to the embedding problem of Markov matrices. Despite of partial results for small dimensions, some of the most recent and general results on this problem can be found in [25].

To conclude, and despite similar results on the embeddability of Markov evolution algebras that could be derived from characterizations given, for instance, in [14,25], we consider the case of 2-dimensional Markov evolution algebras. For this simple case, the embeddability of 2-dimensional Markov evolution algebras are fully determined by the following results on 2 × 2 Markov matrices, being moreover the Markov generator unique.

Proposition 7.3

[14, Theorem 3.1, Corollary 3.3]

Let $\mathbf{P}=\left(\begin{array}{cc}1-a& a\\ b& 1-b\end{array}\right)$ with a, b ∈ [0, 1]. Then, the following statements are equivalent:

1. P is embeddable.

2. 0 < det(P) = 1 − (a + b) ≤ 1.

3. 1 < tr(P) ≤ 2, i.e. 0 ≤ a + b < 1.

4. P has positive spectrum σ(P) = {1, 1 − (a + b)} (positive eigenvalues only).

Moreover, if the above equivalent conditions hold, there exists a unique rate matrix Q such that P = e^Q. More precisely, $\mathbf{Q}=\left\{\begin{array}{ll}{\mathbf{I}}_2,& \mathrm{i}\mathrm{f}a=b=0;\\ -\frac{\log (1-a-b)}{a+b}\left(\begin{array}{cc}-a& a\\ b& -b\end{array}\right),& \mathrm{o}\mathrm{t}\mathrm{h}\mathrm{e}\mathrm{r}\mathrm{w}\mathrm{i}\mathrm{s}\mathrm{e}.\end{array}\right.$

Corollary 7.4

If $\mathbf{P}=\left(\begin{array}{cc}1-a& a\\ b& 1-b\end{array}\right)$ is embeddable, then a, b ∈ [0, 1).

Proof.

It suffices to note that a = 1 would imply det(P) = −b < 0 contradicting Proposition 7.3(ii) (similarly det(P) = −a < 0 if b = 1).

Theorem 7.5

Let $\mathcal{E}$ be a 2-dimensional Markov evolution algebra. Then, $\mathcal{E}$ is embeddable into a CT-Markov evolution algebra $\mathcal{E}\left(t\right)$ if and only if:

1. $\mathcal{E}$ is perfect and has two 1-basic ideals. (More precisely, $\mathcal{E}$ is the trivial evolution algebra with structure matrix A = I₂.)

2. $\mathcal{E}$ is perfect and has a 1-basic ideal.

3. $\mathcal{E}$ is perfect and (basic) simple.

Then the rate matrix Q of $\mathcal{E}\left(t\right)$ is unique, and as described in Proposition 7.3.

Proof.

Let $\mathcal{E}$ be a 2-dimensional Markov evolution algebra with structure matrix $\mathbf{A}=\left(\begin{array}{cc}1-a& a\\ b& 1-b\end{array}\right)$. We first assume $\mathcal{E}$ is embeddable, so that by Corollary 7.4 we necessarily have a, b ∈ [0, 1). Then, by Proposition 7.3:

1. If a = b = 0, i.e. if A = I₂, then $\mathcal{E}$ is a non-simple trivial evolution algebra with 1-basic ideals $I_i=\mathbb{R}{e}_i$, i = 1, 2.

2. If a = 0 and b ≠ 0 (thus det(A) = 1 − b ≠ 0 ), then $I=\mathbb{R}{e}_1$, is a 1-basic ideal of $\mathcal{E}$. (Analogously if a ≠ 0 and b = 0, considering then $I=\mathbb{R}{e}_2$.)

3. If ab ≠ 0 (thus det(A) = 1 − a − b ≠ 0 ), then $\mathcal{E}$ is perfect and (basic) simple [11, Proposition 2.7].

Conversely, the structure matrix of any of the 2-dimensional Markov evolution algebras listed above is embeddable by Proposition 7.3.

7.1. Further comments

Tian's target of studying continuous evolution algebras, even under the additional assumptions considered here, has been proved to be connected to the classical problem on the embeddability of Markov matrices [8]. Current research on this topic, see for instance [25], would contribute to better understand continuous-time evolution algebras. Some more problems are still to be considered, as for instance, the representation of (Markov) evolution algebras as solutions of differential equations (see Lemma 6.2(iii)) or the case of evolution algebras with complex structure matrices with row sums equal to one.

Disclosure statement

No potential conflict of interest was reported by the author(s).

Additional information

Funding

Partially supported by Secretaría de Estado de Investigación, Desarrollo e Innovación grant MTM2017-83506-C2-1-P (AEI/FEDER, UE).