{'fraction_non_alphanumeric': 0.05985320151970242, 'fraction_numerical': 0.02122411632486623, 'mean_word_length': 3.7693767194763304, 'pattern_counts': {'":': 0, '<': 20, '<?xml version=': 0, '>': 23, 'https://': 0, 'lorem ipsum': 0, 'www.': 0, 'xml': 0}, 'pii_count': 0, 'substrings_counts': 0, 'word_list_counts': {'cursed_substrings.json': 18, 'profanity_word_list.json': 0, 'sexual_word_list.json': 0, 'zh_pornsignals.json': 0}}
Notes on Markov embedding

The representation problem of finite-dimensional Markov matrices in Markov semigroups is revisited, with emphasis on concrete criteria for matrix subclasses of theoretical or practical relevance, such as equal-input, circulant, symmetric or doubly stochastic matrices. Here, we pay special attention to various algebraic properties of the embedding problem, and discuss the connection with the centraliser of a Markov matrix.


Introduction
A stochastic or Markov matrix M is a matrix with non-negative entries and row sums 1, which is the convention we use here. We call M strictly positive when all its entries are positive. A Markov generator Q, also known as a rate matrix, has non-negative entries off the diagonal and row sums 0, and {e tQ : t 0} is the homogeneous Markov semigroup (or monoid, to be more precise) generated by Q; see [6] for general background. It is an old and still only partially resolved question which Markov matrices M are embeddable, meaning that they appear in a Markov semigroup. For a given M , this is clearly equivalent to the existence of a rate matrix Q such that M = e Q .
While the traditional focus was on irreducible Markov matrices, recent progress on various models of biological evolution has put new emphasis also on reducible and even on absorbing Markov chains, and on submodels with additional algebraic structure; see [1,27,14,33] for some examples. Moreover, an answer to the embedding problem also gives insight into the structure of Markov semigroups that are being used in many places; see [2] and references therein for some recent examples. This motivates us to revisit the embedding problem with an eye on more specific classes of Markov matrices, where we will only consider the finite-dimensional case here. This, inevitably, brings one in contact with the topologically complicated structure of the boundary of the set of embeddable matrices, as detailed in Kingman's influential paper [25] on the subject, which can be seen as one of the reasons why the problem has not yet received a complete solution.
An efficient starting point to the embedding problem is the paper by Davies [9], who collected a good number of known results and examples in one place, with a useful list of references. We will refer to it frequently. Also, [20] gives an insightful overview of many of the early results. Some care has to be exercised as to the precise conditions in informal statements, for instance on whether irreducibility or positive determinant is (implicitly) assumed. One should note that many of the early results give abstract characterisations that are of limited use in practice. Our goal here is to revisit the embedding problem from a slightly different perspective, where we treat it, in a more concrete fashion, for various classes of matrices that are natural from an algebraic point of view or frequently show up in applications.
The paper is organised as follows. In Section 2, we set the scene, recall some of the known results, and formulate various algebraic and asymptotic properties for later use. The classic case of two-dimensional (d = 2) Markov matrices is reviewed in Section 3, where we select calculations and proofs with an eye to our later needs in higher dimensions. One generalisation, the class of equal-input matrices, is then treated in Section 4, where an interesting dichotomy between even and odd dimensions shows up. Section 5 presents results for the class of circulant matrices, which have a rich theory of their own. Finally, we discuss various more specialised classes of Markov matrices for d = 3 in Section 6, once again aiming at more concrete criteria, and close with a brief outlook in Section 7.

General setting and results
Let us begin by recalling some necessary (but generally far from sufficient) conditions for embeddability. For convenience, we give brief hints on the proofs or references. We use σ(A) to denote the spectrum of a matrix A, usually including multiplicities. When the latter are not important, we simply consider σ(A) as a set. Let us also recall that the d-dimensional Markov matrices form a closed, convex subset M d ⊂ Mat(d, R), which has locally constant, topological dimension d(d−1), where we generally assume d 2 to avoid trivialities. Clearly, M d is a monoid with respect to matrix multiplication, where the extremal elements are the stochastic {0, 1}-matrices [22]. Also, if M is Markov, one has det(M ) 1, with equality if and only if M is a permutation matrix for an even permutation. The last property follows from general Perron-Frobenius theory applied to M and the fact that Markov matrices with determinant 1 are diagonalisable; see [15,Sec. 13.6].
Proposition 2.1. If a Markov matrix M is embeddable, so M = e Q with Q a Markov generator, M satisfies the following properties.
(5) M is either reducible, or strictly positive and thus also primitive.

.2.1].
Let us note in passing that the difficulty of solving M = e Q for Q consists in the existence of a logarithm of M that has the positivity properties required for a generator, where the latter is the harder constraint by far.
Example 2.2. While 1 = e 0 is trivially embeddable, any irreducible Markov matrix that is embeddable must actually be primitive and strictly positive. For instance, ( 0 1 1 0 ) is irreducible, but not primitive, while 1−a a 1 0 with a ∈ (0, 1) is primitive, but not strictly positive, so neither of these matrices is embeddable; compare Example 3.8 below.
Also, M = 1−a a a 1−a , which has spectrum σ(M ) = {1, 1 − 2a}, cannot be embeddable for a ∈ 1 2 , 1 , as this violates Property (2), as well as (4) when a > 1 2 . ♦ Homogeneous Markov semigroups possess a well-known asymptotic property, which we recall here for convenience and later use; compare [23,Thms. 12.25 and 12.26] for closely related results. Also, some aspects of Proposition 2.1 may become more transparent this way. Proposition 2.3. Every finite-dimensional Markov generator Q has the following properties.
(2) The minimal polynomial of Q is of the form z q(z) with q(0) = 0, which is to say that the algebraic and the geometric multiplicity of λ = 0 coincide.
(3) If M (t) := e tQ , the limit M ∞ = lim t→∞ M (t) exists and is a Markov matrix with Proof. While claim (1) follows from Proposition 2.1(2) via the spectral mapping theorem, we prefer to give an independent argument with some additional insight. Define the number µ = min{z 0 : Q + z1 is a non-negative matrix} and set R = Q + µ1, with matrix elements r ij 0 for all 1 i, j d and j r ij = µ for all i by construction. The Gershgorin circles of R are G i = B µ−r ii (r ii ), one of which must be B µ (0), where B ρ (x) denotes the closed disk of radius ρ around x. Clearly, we then have i G i = B µ (0), and σ(R) ⊂ B µ (0) by Gershgorin's theorem [15,Thm. 14.6]. Consequently, we get σ(Q) ⊂ B µ (−µ). Since Q is a real matrix, this gives the first claim. We know that 0 ∈ σ(Q), as Q has zero row sums. To show claim (2), assume to the contrary that the geometric multiplicity is smaller than the algebraic one. Consequently, there are linearly independent row vectors 1 u, v = 0 such that vQ = 0 and uQ = v. For M := e Q , which is Markov, this implies vM = v and uM = u + v by a simple calculation, hence also uM n = u + nv for n ∈ N. If . 1 denotes the 1-norm for row vectors, the matching matrix norm is the row sum norm, with M 1 = 1. Here, we get uM n 1 u 1 M n 1 = u 1 , which is bounded. In contrast, we have u + nv 1 n v 1 − u 1 , which is unbounded due to v 1 > 0 and thus gives a contradiction, so the principal vector u cannot exist. 1 Though an equivalent argument can be given with column instead of row vectors, this version has the slight advantage that we can directly use the row sum normalisation of M . (1) and (2) in conjunction with the observation that the Markov property is preserved under taking limits, because M d is closed in Mat(d, R). The projector property follows from

Claim (3) is a simple consequence of properties
which also implies the claim on the eigenvalues.
One immediate consequence is the following. If 1 = M = e Q is embeddable, the Markov semigroup {e tQ : t 0} defines a path (in M d ) of embeddable matrices from 1 (included) via M to M ∞ (not included). Here, since Q = 0 and thus tr(Q) < 0, one has det(M ∞ ) = 0, and M ∞ itself is not embeddable. In this way, no embeddable Markov matrix is isolated, and any two embeddable matrices of the same dimension are pathwise connected.
When M is a general Markov matrix (hence not necessarily embeddable), it is also true that 1 is an eigenvalue with equal algebraic and geometric multiplicity [15,Thm. 13.10], which can be seen as a consequence of the normal form of non-negative matrices in [15,Eq. (13.70)]. However, M n need not converge as n → ∞, because M can be irreducible without being primitive; compare [23,Thms. 8.18 and 8.22]. This cannot occur for embeddable matrices, in line with Elving's theorem, which is Proposition 2.1(3) above.
Proof. Though the claims for embeddable matrices follow from the more general ones via Elving's theorem, we give a simple independent argument. When M = e Q , one has M n = e nQ , and the first claim follows from Proposition 2.3 (3). The generator property of R is clear, while M 2 ∞ = M ∞ implies the relation for R as well as the property of the spectrum. For the general claim, observe that our previous comment implies that M has minimal polynomial zp(z) with p(0) = 0. Since all roots of p have modulus < 1, convergence now follows from a standard Jordan normal form argument.
Let E d denote the set of d-dimensional Markov matrices that are embeddable, and let E d := E d be the (multiplicative) semigroup generated by it. In view of the dichotomy in Proposition 2.1(5), we also introduce E + d := {M ∈ E d : M is strictly positive}.
Fact 2.5. E d is a monoid, while E + d is a semigroup and a two-sided ideal in E d .
Proof. Since 1 is embeddable, E d is a semigroup with unit, and the first claim is clear. For the second, observe that the product of strictly positive Markov matrices is strictly positive, which implies the semigroup property, and that the product of a strictly positive Markov matrix with any Markov matrix, in either order, is again a strictly positive Markov matrix, which implies E + d to be a two-sided ideal in E d .
The set E d is relatively closed [25,Prop. 3] within M > d := {M ∈ M d : det(M ) > 0}, with the same topological dimension. In particular, one has the interior-closure inclusions (2) the embeddable matrices with distinct eigenvalues; (3) the embeddable matrices with Abelian centraliser in Mat(d, R), as characterised in more detail below in Fact 2.10.
Moreover, each of these subsets has full measure in E d .
Let us take a different perspective on the general embedding problem, which will provide a slightly simpler setting where some concrete answers are possible. Assume that we consider a (finite or infinite) set of rate matrices which generate a closed matrix algebra G over R with respect to matrix addition and multiplication. For G ∈ G and arbitrary t ∈ R, the series converges absolutely, where G m ∈ G for all m ∈ N, thus A := e G − 1 ∈ G as well. Moreover, in conjunction with Proposition 2.3(1) and its proof, one has the following connection. When d 2, it is worth mentioning that, due to the Cayley-Hamilton theorem and the structure of the exponential series, one also has a representation (2) e tQ = 1 + where each F ℓ is a power series with infinite convergence radius and F ℓ (0) = 0. When Q is a rate matrix, this structure suggests to consider the matrix algebra (3) alg(Q) := Q, Q 2 , . . . , Q d−1 R , which will become relevant shortly. Note that alg(Q) is a subalgebra of the matrix algebra A 0 of all real matrices with vanishing row sums, (4) A 0 := A ∈ Mat(d, R) : d j=1 A ij = 0 for all 1 i d , which does not contain 1. Clearly, alg(Q) has dimension d−1 or smaller, where the latter case occurs if Q has a minimal polynomial of degree less than d. Also, since both A 0 and alg(Q) are closed subspaces of Mat(d, R) when viewed as real vector spaces, they are complete with respect to any chosen matrix norm on Mat(d, R), which is another way to see that e tQ − 1, for any t 0, lies in alg(Q). Proof. Clearly, both A and R are generators themselves. Since e tQ − 1 ∈ alg(Q) for any t 0, its limit as t → ∞, which is R, lies in alg(Q) as well, because the latter is closed.
where (A + 1) n − 1 = n m=1 n m (−1) n−m A m ∈ alg(A). Since alg(A) is closed, we also have R ∈ alg(A), and our claim follows.
Next, we state a simple special case of alg(Q) for later use, which harvests the fact that the only nilpotent Markov generator is Q = 0. (1) The minimal polynomial of Q is z(z + c) with c > 0.
Let us return to Fact 2.7. Viewed differently, the generator of an embedding has to satisfy a commutativity condition. Generically, this will mean that Q is of the same 'type' as A, and it is thus an interesting subproblem of the general embedding question to look at embeddability under a natural constraint on Q; compare [31,33,14]. This can be of practical relevance, for instance in biological applications; see [30,Ch. 7] and references therein.
Since commutativity of matrices will be important in what follows, let us recall a classic result from algebra [17, Chs. III. [15][16][17][18], specialised to the case of real matrices. For its formulation, we employ the eigenspace notation V λ := {x ∈ C d : Bx = λx} for λ ∈ C and a given matrix B ∈ Mat(d, R) ⊂ Mat(d, C). (1) The characteristic polynomial of B is also its minimal polynomial.
(3) B is cyclic: {u, Bu, . . . , B d−1 u} is a basis of R d for some u ∈ R d .  Below, we will call matrices of this kind cyclic. In particular, Fact 2.10 applies to all matrices with simple spectrum, which means distinct eigenvalues. In the case of degeneracies, the existence of additional elements in cent(B), which is known as the centraliser (or the commutant) of B, can be seen from a repetition in its Jordan blocks. In this context, the last claim of Fact 2.7 means that A = M − 1 with M = e Q implies A ∈ cent(Q) as well as Q ∈ cent(A). This has the following consequence.
Lemma 2.11. If M = e Q is an embeddable Markov matrix that is cyclic, one has Q ∈ alg(A) with A = M − 1.
Proof. For the matrix A, we are in the situation of Fact 2.10. Then, by Fact 2.7, the rate matrix Q must be an element of R[A] ∩ A 0 , which means Q ∈ alg(A).
The significance of this result emerges from the following concept. (1) Property S is well defined for generators, and inherited by all elements of alg(A); (2) Property S is preserved under taking limits within Mat(d, R); (3) M can arbitrarily well be approximated, in the row sum norm say, by other Markov matrices with Property S that are also generic in the sense of Fact 2.10.
When only (1) and (2) are satisfied, we call the property semi-stable.
As an example, the reader may think of a symmetric Markov matrix, so M T = M , where A = M − 1 and every element of alg(A) is then symmetric as well. Clearly, the limit of a convergent sequence of symmetric matrices is again symmetric. Finally, any symmetric matrix is the limit of sufficiently many convergent sequences of symmetric matrices, in the sense that every neighbourhood of a symmetric Markov matrix also contains further symmetric ones. This can be shown by a deformation argument, and it is still true within the set E d ; see Remark 4.11 below. In contrast, the property of having simple spectrum already fails to be semi-stable, as does the property of having geometric multiplicity 1 for all eigenvalues.
Let us briefly comment on an algebraic consequence of Definition 2.12. When Property S is a linear property, such as being symmetric, semi-stability means that the S-generators form a Jordan algebra. This follows from the simple observation that A 2 , B 2 and (A + B) 2 having Property S then implies that (AB + BA) has Property S as well.
Proposition 2.13. Let M be an embeddable Markov matrix. If M has a stable property, S say, M can be embedded as M = e Q with a generator Q having Property S. If, in addition, cent(M ) is Abelian, every generator Q with e Q = M must be an S-generator.
Proof. If M has an Abelian centraliser, we are in the situation of Lemma 2.11 and the claim is clear. Otherwise, we infer from [25,Prop. 4] that the relative interior of E d as a subset of M > d is non-empty, which means that the topological dimension of E d is the maximal one, namely d(d− 1). Combining Fact 2.6 with Condition (3) of Definition 2.12, we may conclude that there is a sequence of embeddable Markov matrices with Abelian centraliser and Property S, Then, for all j ∈ N, we have M j = e Q j with a generator Q j ∈ alg(M j − 1), so all Q j have Property S by Lemma 2.11 in conjunction with Condition (1) of Definition 2.12. Now, the set of solutions of M j = e Q ′ with Q ′ a Markov generator is discrete and finite, see Fact 2.14 below, and the exponential map is locally a homeomorphism. Consequently, there is a subsequence (j m ) m∈N of indices such that (Q j m ) m∈N converges, where Q = lim m→∞ Q j m is a generator with property S. By construction and Condition (2) of Definition 2.12, we get M = e Q as claimed.
The second claim is now another consequence of Lemma 2.11 and Fact 2.10.
Let us also note the following variant of [9, Cor. 10]. The proof is essentially the same, with the only difference coming from the more general commutativity result in Fact 2.10, that is, using cyclic rather than simple matrices. The latter case is also considered in [22, Thm. 1.1].
Fact 2.14. Let M be a Markov matrix that is cyclic. Then, the solutions of M = e Q form a discrete set in A 0 , and these solutions commute with one another and with M . Moreover, only a finite number of the solutions can be Markov generators.
Finally, let us recall a diagonalisability result that will come in handy later.
Proof. Via the Jordan-Chevalley decomposition, B can be written as B = D + N with D diagonalisable, N nilpotent, and [D, N ] = 0. In particular, the minimal polynomial of N is z k , for some 1 k d.
1 m! N m again being nilpotent. Since M is diagonalisable, and e N = e −D M with [D, M ] = 0, the matrix e N is diagonalisable as well, and we must have N ′ = 0, as this is the only diagonalisable nilpotent matrix. But this implies k = 1, as any larger k would give a contradiction to z k being the minimal polynomial of N . This means N = 0 together with B diagonalisable.
We are now set to embark on the Markov embedding problem.

Two-dimensional Markov matrices
The situation for d = 2 is particularly simple, because both eigenvalues are real and the determinant condition from Proposition 2.1(2) is sufficient to give a complete characterisation We recall this well-known result and give a short explicit proof, both for the convenience of the reader and for later use; for background on the underlying calculations around matrix functions, we refer to [16].
, the following statements are equivalent.
Proof. All Markov matrices for d = 2 are covered by the parametrisation chosen. The equivalence of (2) and (3) is elementary, where (2) is a necessary condition for embeddability by which is a Markov generator because the scalar prefactor of A is always a positive number in our case. Since M = e Q by construction, any such M is embeddable, and we see that the necessary determinant condition is also sufficient.
It is instructive, and will be useful later on, to also consider the complementary point of view, where one starts from a general rate matrix Q = −α α β −β with α, β 0 and calculates e tQ . We may assume α + β > 0 to avoid the trivial case e 0 = 1. Now, with Q 2 = −(α + β)Q, one explicitly calculates the exponential series as which also covers the limit α+ β ց 0 via l'Hôpital's rule. Since the sum of the two off-diagonal elements of e tQ satisfies 0 1 − e −(α+β)t < 1 for all t 0, the spectral radius of e tQ − 1 is less than 1, and it is clear that all Markov matrices M from Theorem 3.1 are covered precisely once, which gives the following result that is specific to d = 2; see [7,8] for some results with d 3, and [9, Cor. 10(3) and Thm. 11] for a summary.
The diagonal line is the 1-simplex of symmetric Markov matrices, which agree with the doubly stochastic and with the circulant Markov matrices for d = 2. Note that E 2 is star-shaped with respect to the boundary point 1 2 , 1 2 , as is the entire set M 2 .
Remark 3.3. Note that Theorem 3.1 is not restricted to irreducible Markov matrices. It is worth noting that the irreducible cases are also reversible, and that the embeddable ones among them are also reversibly embeddable, as discussed in more generality in [4]. Reversible Markov matrices form another interesting class, though we do not consider them here. Let us note that the property of reversibility fails to be semi-stable, as can be seen from 1−ε ε 1−2ε 2ε for small ε > 0, which is both embeddable and reversible, while the limit εց0 gives the matrix ( 1 0 1 0 ), which is neither. However, if (M n ) n∈N is a converging sequence of reversible, irreducible Markov matrices such that the limit is still irreducible, reversibility is preserved as well. ♦ Although d = 2 is not really representative for the general case, it is nevertheless instructive to illustrate the situation from the viewpoint of convex sets; see Figure 1. The algebraic situation for d = 2 is as follows.
To get a better understanding in the matrix setting, we take a look at commutativity.
as before, and setting A = M − 1 and A ′ = M ′ − 1, a simple calculation gives the following result.
Otherwise, the new rate matrix Q ′′ can be calculated by the Baker-Campbell-Hausdorff (BCH) formula, 2 at least in principle. We shall give a simple, closed formula for this case below in Eq. (15). One consequence is that Q ′′ belongs to the Lie algebra generated by Q and Q ′ , which motivated the investigation of Lie-Markov models [31,33]. While the row sums of Q ′′ all vanish, it remains a difficult problem (when d 3) to decide when Q ′′ is a Markov generator.
In general, when M and M ′ are embeddable but do not commute, the embedding semigroups have no simple relation to one another. The situation, neither restricted to d = 2 nor to Markov generators, reads as follows; see [12] for background and various extensions.  (2) One has e tA e tB = e tC for all t ∈ R.
(3) One has e tA e tB = e tC for all t 0.
(4) One has e tA e tB = e tC for some ε > 0 and all 0 t < ε.
Proof. Condition (2) follows from (1), as can be checked by a simple calculation with the exponential series, and (2) obviously implies (3), (4) and (5), where (3) ⇒ (4) is also clear. Now, assume e tA e tB = e tC for small t 0. Evaluating the time derivative of both sides at t = 0 gives A + B = C. With this, by evaluating the second time derivative of both sides at t = 0, one sees that A and B must commute, so (4) ⇒ (1) ⇒ (2).
Finally, assume (5). As t 0 = 0 is covered by (4), we may take t 0 = 1 without loss of generality, by rescaling all three matrices if necessary. This time, evaluating the derivative at t = 1 gives Ae C + e C B = e C C = C e C and thus the double identity because e C is invertible. The analogous exercise with the second derivative leads to where the second equality emerges from Eq. (7)   When this is to remain true for some small intervals around t and s, which may be viewed as some kind of stability requirement, arguments as in the previous proof force the three generators to be equal. There are several variants of this situation, the details of which are left to the interested reader. Particular aspects, such as the inconsistency of some time-reversible models and consequences thereof, are addressed and discussed in [32]. ♦ Let us next look at an interesting example where a power of a non-embeddable matrix is embeddable, and how this emerges. , where M ′ is another matrix root of M 2 , but a strictly positive and embeddable one.
The analogous phenomenon must happen whenever a Markov matrix fails to be embeddable, though a power of it is. This is connected with the characterisation of embeddable matrices as the ones that possess a Markov n-th root for every n ∈ N; see [25,22]. ♦ Figure 1 also illustrates M 2 and its subset of symmetric Markov matrices, some aspects of which will later be extended in Remark 4.11. With hindsight, the set M 2 can be related to a number of different matrix algebras, including Mat(2, R). While the latter viewpoint becomes highly complex for d > 2, the situation is different for another choice of matrix algebra, which we shall discuss next.

Equal-input matrices
Following [30, Sec. 7.3.1], let us consider a special, but practically important, class of Markov matrices, known as equal-input (or Felsenstein [13]) matrices. For its formulation, let C be a d×d-matrix with equal rows, each being (c 1 , . . . , c d ), and define c = c 1 + · · · + c d as its summatory parameter.
Fact 4.1. Any square matrix C with equal rows and summatory parameter c satisfies the relation C 2 = cC. When c = 0, it is always diagonalisable, while it is nilpotent for c = 0. In the latter case, it is diagonalisable if and only if C = 0.
which is a matrix with row sums 1. It is Markov if c i 0 and c 1 + c i for all i. We denote the set of all equal-input Markov matrices with fixed d by which, for embeddability, has to lie in (0, 1] by Proposition 2.1 (2). When d 2 is even, Eq. For general d, whenever 0 < c < 1, the spectral radius of A = M C − 1 is less than 1 and we can use the relation A 2 = −cA to obtain (10) log in complete analogy to Eq. (5), where A = C − c1 is a generator of equal-input type, called an equal-input generator from now on. Note that c = 0 means A = 0, so that the formula in Eq. (10) also covers this limiting case via l'Hospital's rule.
Observe that M ∈ M d being of equal-input type is a semi-stable, but not a stable property in the sense of Definition 2.12, so we should expect some subtleties. Thus, consider a general matrix B with equal rows (α 1 , . . . , α d ). Then, Q B := B − α1 with α = α 1 + · · · + α d is an equal-input generator whenever all this time in complete analogy to the formula in Eq. (6). In particular, all equal-input Markov matrices M C = (1 − c)1 + C ∈ C d with 0 c < 1 are embeddable in this way. Also, observing that in obvious notation, we know that the product of equal-input matrices is an equal-input matrix [30,Lemma 7.2(iv)]. Also, 0 c, c ′ < 1 implies c ′′ ∈ [0, 1), in line with the fact that the equal-input Markov matrices form the (closed) positive cone of a matrix algebra.
Putting these pieces together, we have the following result for even dimensions.
The matrix ring R[J 3 ] = {a1 + bJ 3 : a, b ∈ R} is two-dimensional (viewed as a vector space over R). Now, J 3 fails to have simple spectrum, but is diagonalisable, so cent(J 3 ) is larger than R[J 3 ] by Fact 2.10. For Q ′ a Markov generator, a simple computation shows that [Q ′ , J 3 ] = 0 is equivalent to Q ′ being doubly stochastic, where the latter means that also all column sums of Q ′ are zero. Via an explicit calculation, one finds the embeddable matrix with τ, x, y, z, w ∈ R. In particular, a Markov matrix or a Markov generator commutes with J 3 if and only if it is doubly stochastic.
Proof. The first claim follows from a simple calculation around [B, J 3 ] = 0, which also gives the parametrisation chosen. The last claim is obvious via restricting cent(J 3 ) to the set of Markov matrices or generators, respectively.
Clearly, the matrix M from Example 4.3 cannot be written as e Q with Q an equal-input generator, as any e Q has parameter sum c < 1, while we had c M > 1. Also, due to Eqs. (10) and (11), equal-input embeddable Markov matrices are closed under multiplication, and we have the following counterpart of Proposition 4.2. The difference to d even is that there are other embeddable cases, but not with a generator of equal-input type. This matches with the fact that being equal-input is only a semi-stable property in the sense of Definition 2.12. We thus have the following general statement. Moreover, when d is even, irrespectively of the type of generator, no further equal-input Markov matrices are embeddable, while additional cases do exist for d odd.
When M is equal-input embeddable, this does not exclude further embeddings of a different nature, as we shall see in Remark 6.7. However, more can be said about the equal-input solutions. If Q is an equal-input generator, one has Q = C − c1 and thus (14) e which means that the summatory parameterc of e Q isc = 1 − e −c . Now, let Q and Q ′ be equal-input generators, with parameters c and c ′ . When e Q = e Q ′ , it is immediate that c = c ′ , and Eq. (14) then implies Q = Q ′ . This gives us the following uniqueness result, which is a generalisation of Corollary 3.2.
Corollary 4.7. If an equal-input Markov matrix M is embeddable as M = e Q with a generator Q of equal-input type, which is possible if and only ifc = c M ∈ [0, 1), the generator Q is unique. Forc ∈ (0, 1), it is given by Eq. (10), and by Q = 0 forc = 0.
One can further exploit the monoid property of equal-input embeddable Markov matrices. If Q and Q ′ are equal-input generators, one finds e Q e Q ′ = e Q ′′ with the new generator (15) Q When [Q, Q ′ ] = 0, this simplifies to Q ′′ = Q + Q ′ , in line with Lemma 3.6. In any case, the summatory parameters of the exponentials are related bỹ in accordance with Eq. (11).
Remark 4.8. The class of equal-input matrices M C contains a subclass, defined by the condition c 1 = c 2 = . . . = c d , called constant-input matrices. For d = 4, they in particular cover the Jukes-Cantor mutation matrices [19]. Constant-input matrices are closed under multiplication, so the previous analysis can be restricted to this subclass. Since the matrix M from Example 4.3 is a constant-input matrix, we get the result of Theorem 4.6 also for this subclass, with the same distinction between d even and d odd. We shall meet this class again in Section 6.2. ♦ Let C be as above, with summatory parameter c together with c i 0 for all 1 i d, and consider the equal-input generator Q C = C − c1. Since Q C = 0 when c = 0, let us assume c > 0. Then, we have C = 0 and Q C C = 0, so Q C has minimal polynomial z (z + c). In particular, Q C is diagonalisable, with eigenvalues 0 and −c, the latter with multiplicity d − 1.
In this context, one has the following extension of Fact 2.9. Proof. Under the assumptions, we have Q(Q + c1) = 0. When 0 ∈ σ(Q) is simple, with eigenvector u = (1, 1, . . . , 1) T , we see that each column of Q + c1 must be a scalar multiple of u. If the ith column is c i u with c i ∈ R, we have Q = C − c1, which is a generator if and only if all c i 0 together with c = c 1 + · · · + c d . Since 0 is simple, we must have c > 0.
The converse direction was shown above.
For d 3, an equal-input generator inevitably has multiple eigenvalues such that minimal and characteristic polynomial differ. Consequently, by Fact 2.10, the centraliser is non-Abelian. Interestingly, on the level of generators, one has the following elementary result, which can be seen as a generalisation of Fact 4.4. Proof. When c = 0, which means Q = 0 and c 1 = · · · = c d = 0, every generator X commutes with Q and the statement is trivial. Next, assume c > 0 and Q = C − c1. A matrix commutes with Q if and only if it commutes with C. When X is a generator, one has XC = 0 because C has constant columns. Then, [X, C] = 0 means CX = 0, each line of which is the condition stated. Since 1 c (c 1 , . . . , c d ) is a probability vector for c > 0, the last claim is clear.
Let us note that a generator X as it appears in the last proof may have several equilibrium states, which form a convex set. In such a case, when c > 0, the characterisation from Lemma 4.10 specifies only one of them.
Remark 4.11. It is worth mentioning that there is a special constant-input Markov matrix, , with a number of interesting properties. Clearly, it has det(I d ) = 0 and thus cannot be embeddable, but lies on the boundary of E d . This is also clear from the relation I d = lim t→∞ e tQ with Q being any irreducible, doubly stochastic generator in d dimensions. More importantly, as shown in [21, Thm. 2.7], E d is star-shaped with respect to I d ; see Figure 1 for d = 2. Since I d is also circulant, symmetric and doubly stochastic, this will be useful for various deformation arguments later on. ♦

Circulant matrices
A d × d-matrix is called circulant if each of its rows emerges from the previous one by cyclically shifting it one position to the right (see below for more). Such matrices have a rich theory of their own; see [10] for a detailed exposition. Here, we are interested in circulant matrices that are also Markov matrices or generators, respectively. The interested reader may consult [30, Ch. 7.3.2] for how these matrices fit into the setting of 'group-based models', and [34] for an extension to 'semigroup-based models'. The latter in particular include the equal-input models discussed in the Section 4.
For d = 2, a Markov matrix is circulant if it is constant-input, so M = 1−a a a 1−a . By Theorem 3.1, it is embeddable if and only if 0 a < 1 2 . In fact, with Q = α −1 1 1 −1 , one can rewrite our earlier formula as (16) e tQ = e −αt cosh(αt)1 + e −αt sinh(αt) 0 In particular, whenever a circulant M with d = 2 is embeddable, Corollary 3.2 together with Eq. (5) implies that this is only possible with a circulant generator, which also fits Proposition 2.13. The explicit computations rely on the formula e x = cosh(x) + sinh(x), which can be seen as a decomposition of the exponential function over the cyclic group C 2 .
which is the standard d-dimensional representation of the cyclic permutation (12 . . . d). Since P has simple spectrum, namely σ(P ) = {e 2πim/d : 0 m d − 1}, and since P is also a doubly stochastic matrix, as is any power of it, one finds the following consequence. It is an easy consequence of this characterisation that the exponential of a circulant matrix is again circulant, and that being circulant is a stable property. This can be seen by a deformation argument on the basis of Remark 4.11, where one uses a circulant matrix near I d with simple spectrum from Remark 4.11, in conjunction with [9,Cor. 6]. By Proposition 2.13, we thus get the following consequence. With this, some elementary calculations establish the following result.
satisfy the following properties.
(1) For any r ∈ C d , one has the decomposition e ω r t = d−1 m=0 χ m (r)f (d) m (t). In particular, this gives e t = f (2) For any m ∈ C d , the function f Due to the first property, this can be considered as a decomposition of the exponential function over the cyclic group C d , thus generalising the earlier case, d = 2. If d|D, so D = kd with k ∈ N, one also has the summatory identity for r ∈ C d . We shall return to these functions after an explicit treatment of d = 3 and d = 4. 2 a primitive third root of unity, so ω 2 = ω and P 3 = 1. Also, by Fact 2.10, one has cent(P ) = R[P ] = 1, P, P 2 R . Now, P is diagonalisable as U −1 P U = diag(1, ω, ω ) with the unitary Fourier matrix Next, define two Markov generators as K 1 = P − 1, which equals Q from Eq. (12), and K 2 = P 2 − 1. They satisfy and thus generate a two-dimensional matrix algebra over R, which is an Abelian subalgebra of A 0 from Eq. (4). This subalgebra contains the matrices with α, β ∈ R, which are all circulant. Since the rate matrices K 1 and K 2 commute, one has e αK 1 +βK 2 = e αK 1 e βK 2 , wherefore it is natural to set Now, with α, β ∈ R and η := e αω+β ω−(α+β) , we get with x(α, β) = 1 3 1 + 2e −γ cos δ − 2π 3 and y(α, β) = x(β, α), where γ = 3 2 (α + β) and δ = The necessary determinant condition det(M (a, b)) = 1 − 3(a + b) + 3(a 2 + ab + b 2 ) ∈ (0, 1] from Proposition 2.1(2) implies the inequality which is satisfied, but not sufficient in this case. Figure 2 illustrates the region that is covered. It is bounded by the two curves (20) {z(α, 0) : α 0} and {z(0, β) : β 0}, which both start at (0, 0) and approach the limit point 1 3 , 1 3 without reaching it. The entire region is filled with straight lines from the boundary points towards this special point, as parametrised by {z(α + t, t) : t 0} with α 0 (lower half) and {z(t, β + t) : t 0} with β 0 (upper half). The special role of the limit point also emerges from which shows that the limit point is the (somewhat degenerate) evolute of our family of curves.
We can summarise our derivation as follows.
Its exponential is e Q = 1 + xK 1 + yK 2 + zK 3 =: M (x, y, z) with K m = P m − 1, where P is the permutation matrix of (1234) in analogy to the previous section, and 3 x = 1 2 e −(α+γ) sinh(α + γ) + e −2β sin(α − γ) , 3 The validity of Eq. (21) can easily be verified by means of a standard computer algebra program, the details of which are left to the interested reader.
(3) The parameters x, y, z lie in the closed region defined by the three surface sheets with the parameter regions from Eq. (22), without the points on the evolute.
In general, consider C d and let n r be the order of the cyclic subgroup that is multiplicatively generated by r, where r ∈ C d and n r |d. Now, it is not hard to compute where the second representation is a consequence of Eq. (18).
Consequently, the algebra generated by the K j is Abelian and of dimension d−1. Now, with α 0 := − α 1 + · · · + α d−1 , one obtains a r P r with the coefficients (24) a r = a r α 1 , . . . , With Fact 5.3(1), one finds the relation which leads to the alternative expression This can be seen as the natural generalisation of our previous calculations, in particular Eq. (16) and the formulas for d = 3 and d = 4. From here, one obtains general criteria for circulant Markov matrices and their embeddability as follows.
One can analyse the situation further from here in various ways. For instance, one finds det ∂x i ∂α j = e −d(α 1 +···+α d−1 ) , and one can determine bounding surface sheets for the parameter region as before. We leave details to the interested reader.
Remark 5.8. The above analysis can also be carried out for general (Abelian) group-based models in the sense of [30,Sec. 7.3.2]. In particular, the embedding problem for the C 2 ×C 2 case, otherwise known as the Kimura 3ST model [24], has recently been treated in [29]. The authors demonstrate in Example 3.1 of their work that there exist Kimura 3ST Markov matrices that are not embeddable via a generator of this type. However, their example is embeddable with a C 4 circulant generator Q. Hence, this situation is in perfect analogy with our Example 4.3 above, and the explanation for the phenomenon is the same. ♦

6.
Other classes for d = 3 While we know from Proposition 2.1 that any irreducible M ∈ E 3 must be strictly positive, this is no longer the case within E 3 , as can be seen from When a, b, c, d ∈ (0, 1), the two block matrices on the left are reducible, but embeddable, while the matrix on the right is primitive, because its square is strictly positive. However, the matrix itself still contains a zero element, so cannot be embeddable due to Proposition 2.1(5).
In particular, even if the right-hand side can be written as e B , with B determined via the BCH formula say, B has vanishing row sums, but at least one off-diagonal element will be negative. Consequently, E 3 E 3 , and the same phenomenon occurs for all d 3. Using other canonical ways to embed E 2 into E 3 , one sees that E 3 contains non-embeddable primitive matrices with a single 0 in one off-diagonal entry, for any of the six possible choices. Moreover, as can be seen from [9,Ex. 14], there are strictly positive Markov matrices that satisfy the determinant condition, but are not embeddable, which shows the higher complexity for d 3. Let us thus look at some subclasses that are related to various matrix subalgebras of Mat(3, R). Our results can alternatively be derived via a normal form for Markov matrices, which also underlies some of the analysis in [22,3,5]. A spectral characterisation of embeddable matrices with simple spectrum is given in [22,Cor. 1.3], while those with spectrum {1, λ, λ} and 0 < λ < 1 are covered by [22,Prop. 1.4]. The case with λ < 0 was later solved in [3,5]. Our approach is based on the algebraic structure of stable properties, which gives alternative insight.
Before we embark on the special cases, let us take a closer look at the underlying structure for d = 3. When the minimal polynomial of a Markov matrix M has degree 3, we know that M is cyclic, and we can investigate M = e Q under the condition that the generator satisfies Q ∈ alg(A) with A = M − 1, by Lemma 2.11. When the degree is 1, the polynomial must be z − 1, which is the trivial case M = 1 = e 0 . So, we only have to worry about the case where the minimal polynomial of M is (z − 1)(z − λ) for some λ ∈ (−1, 1). (1) dim(alg(Q)) = 1, so Q 2 = −qQ for some q > 0, and alg(Q) = alg(A) = alg(R). If 1 is a simple eigenvalue of M , the generator Q must be of equal-input type.
(2) dim(alg(Q)) = 2 and 1 is a simple eigenvalue of M , which implies that Q is simple, In particular, M is of equal-input type whenever 1 is a simple eigenvalue of M .
Proof. Assume M as stated, with eigenvalues 1 and λ. This means that A = M − 1 has minimal polynomial z(z + c) with c = 1 − λ > 0, hence eigenvalues 0 and −c, one of them with multiplicity 2. In either case, both A and M are diagonalisable. Clearly, A satisfies A 2 = −cA, and dim(alg(A)) = 1 by Fact 2.9. Now assume that M = e Q , with Q a generator, and define R = lim t→∞ e tQ − 1 as before, where R 2 = −R from Corollary 2.4. By Lemma 2.8, we have R ∈ alg(Q) ∩ alg(A), which implies R = c −1 A. In particular, alg(A) = alg(R) is one-dimensional, while diagonalisability of Q follows from that of M in conjunction with Fact 2.15.
As Q = 0, we have dim(alg(Q)) ∈ {1, 2}. But Q diagonalisable means it is either simple or satisfies Q 2 = −qQ for some q > 0. In the latter case, since A ∈ alg(Q), the generators A and Q both are non-trivial multiples of R, which gives the equalities of the one-dimensional algebras. If 1 ∈ σ(M ) is simple, the equal-input property of Q, which has 0 as a simple eigenvalue, follows from Corollary 4.9. The equal-input property is then inherited by M .
As 0 ∈ σ(A) must be simple in the last case, A is an equal-input generator by Corollary 4.9 again, which also completes the argument for the final claim.
The rather simple structure of the eigenvalues follows easily from the observation that Q + (α + β + γ)1 is an anti-circulant matrix; compare [10, p. 156]. Also, eigenvectors can be computed in closed form and read which are mutually orthogonal. In Dirac notation, let |u 0 and |u ± be the normalised eigenvectors derived from this, which give the three projectors (27) |u 0 u 0 | = I 3 = 1 + J 3 and |u ± u ± | = − 1 2 with I 3 as in Remark 4.11, as can be checked by an explicit computation.
Lemma 6.2. If Q is the generator from Eq. (25), its exponential is given by which correctly covers the limiting case s ց 0, where e Q = 1 + 1 − e −∆ J 3 .
Proof. Given Q, which is diagonalisable, the spectrum of e Q is 1, e −∆+s , e −∆−s . Employing the projectors from Eq. Let us now consider symmetric Markov matrices, written as with a, b, c ∈ [0, 1] as well as a + b, a + c, b + c ∈ [0, 1]. Note that any such matrix is also doubly stochastic, and that M + (a + b + c − 1)1 is again anti-circulant. Clearly, we can have a = b = c = 0, which is 1 = e 0 . More generally, let us assume that M is embeddable. If a = 0, Proposition 2.1(5) implies that bc = 0, and likewise for b = 0 or c = 0. So, we either have abc > 0 or ab + bc + ca = 0. If a = 1, we must have b = 0 and hence also c = 0, which fails to be an embeddable case by Theorem 3.1, and analogously for b = 1 or c = 1. In fact, whenever two of the numbers are zero, Theorem 3.1 implies that the third lies in the interval 0, 1 2 , which gives us the following result, where the second claim can be seen constructively from another application of Eq. (5). The general case can be stated as follows.
Theorem 6.5. Let M be the general symmetric Markov matrix from (28), with parameters a, b, c 0 and max(a + b, a + c, b + c) 1. Then, the following statements are equivalent.
(2) M is embeddable with a symmetric generator.
Proof. The equivalence of (1) and (2)  with ∆ and s as in Eq. (26). We can now compare the coefficients of the characteristic polynomial of M with the corresponding expressions from Vieta's formula. This gives three necessary conditions for embeddability a follows. First, in line with Proposition 2.1(2), one has det(M ) ∈ (0, 1], which means 3(ab + ac + bc) 2(a + b + c) < 1 + 3(ab + ac + bc).
All three conditions are sharp in the sense that each possible value can be realised. Note that these conditions, even when taken together, are not sufficient for the embeddability of M . Two other properties follow from Eq. (29), namely that M is positive definite and that M −1 has spectral radius less than 1. The former, via Sylvester's criterion, means det(M ) > 0 together with max(a + b, a + c, b + c) < 1, which also follows from the trace condition, and 1 + (ab + bc + ca) > (a + b + c) + max(a, b, c), which, in this case, is not an independent condition either. With A := M − 1, the other property implies that the symmetric matrix is well defined, has vanishing row sums because A is a generator, and satisfies M = e Q ′ . The difficult step, when starting from this formula, consists in formulating a condition on a, b, c that ensures the off-diagonal elements of Q ′ to be non-negative. No criterion in polynomial form, say, exists for this. So, assume M = e Q is constant-input with c > 1 and Q being doubly stochastic, the most general form of which is with α, β, γ, ǫ 0 and |ǫ| min(α, β, γ). One finds σ(Q) = {0, −∆ + s ǫ , −∆ − s ǫ } with A matching set of eigenvectors can be given as where v 0 is perpendicular to v ± .
Remark 6.7. We have used the choice k = 0 to get the maximal range. Alternatively, when using k ∈ N, so ǫ k = (2k+1)π/ √ 3 and α ǫ k , one obtains the range 1 < c M 1+ e −(2k+1)π √ 3 with another embedding solution. So, for smaller and smaller regions, one gets an increasing number of solutions to the embedding problem; see [26] for a related discussion. In fact, due to (1 + 2J) 2 = 1, one has e nT = 1 + (−1) n+1 + 1 J, and this gives extra embedding solutions also for c < 1. Indeed, when n = 2m 0 is even, Q α,m = 3αJ + 2mT is a generator when α 2mπ/ c M < 1. When m ∈ N, these extra solutions are doubly stochastic generators that are not of equal-input type. ♦ 6.3. Doubly stochastic matrices. A natural extension of symmetric Markov matrices is provided by the family of doubly stochastic ones. The latter form a closed convex set that is again a monoid. The extremal elements are the d! permutation matrices, compare [22], which are linearly dependent for d 3.
There are 6 extremal matrices for d = 3, but the corresponding monoid is four-dimensional. Indeed, a simple calculation, compare Fact 4.4, shows that any doubly stochastic matrix can be parametrised as 3 is doubly stochastic and shows that some subtle phenomena can occur. However, being doubly stochastic is a stable property, where the approximation property once again follows from a deformation argument on the basis of Fact 2.6 and Remark 4.11. So, we can apply Proposition 2.13 to get the following result. Note that the generator Q of Eq. (30) is of equal-input type if and only if ǫ = 0 together with α = β = γ, which means that it is then a constant-input generator. Theorem 6.9. Let M be the general doubly stochastic Markov matrix from (33), with parameters a, b, c 0 and e ∈ R subject to max(a + b, a + c, b + c) 1 and |e| min(a, b, c). Let p denote the minimal polynomial of M . Then, M is embeddable if and only if one of the following situations applies.
Proof. Case (1) is trivial, while the case distinction in (2) follows from a simple calculation with the eigenvalues of M and its consequences for ∆ and s ǫ . When ∆ = s ǫ , we are back to Fact 6.4, while s ǫ = 0 implies M to be equal-input and doubly stochastic, hence constant-input, and the condition stated here follows from Theorem 4.6 in conjunction with Corollary 6.6. For Case (3), M is either simple or has a real eigenvalue λ, −1 < λ < 1, with algebraic multiplicity 2, but geometric multiplicity 1, and hence a non-trivial Jordan block attached to it in the Jordan normal form. When M is simple, hence cyclic, we are in Case (2) of Lemma 6.1, so Q is diagonalisable as well and A = M − 1 ∈ alg(Q) = Q, J R with J = J 3 as before. Here, A, Q and J are simultaneously diagonalisable, with a matrix that derives from the eigenvectors of Q as given in (32). Now, we can use A = uQ + vJ and compare eigenvalues, which results in the equation as stated. The further constraints guarantee the generator property of Q.
Finally, the remaining Jordan case is obtained as a limit of such simple matrices, which still gives the same equation for the parameters.

Outlook
There are many aspects of the embedding problem that we have not treated or addressed here, though some were briefly mentioned in our remarks. Among them are more general results on uniqueness or multiple solutions, the classification of matrix classes that are connected with Jordan or Lie algebras, the relation to inhomogeneous Markov chains, or the extension to countable state chains, to mention but a few.
From the viewpoint of biological application, it seems desirable to concretely consider matrix classes for d = 4 that cover the standard mutation schemes of molecular evolution, which are commonly used in bioinformatics and in population genetics. Since the number of relevant matrix classes is much larger than for d = 3, this needs a separate treatment.
Another direction is the extension of the analysis to sub-stochastic matrices and their generators, which show up increasingly in theoretic and applied probability. Here, the nonnegativity conditions remain the same, but the row sums for sub-stochastic matrices or generators are either 1 or 0, respectively.