Mathematical Background
The mutation game is a combinatorial process on graphs that naturally produces the root systems of Lie algebras. It was introduced by N. J. Wildberger [Wild2003] and later published in a generalized form in [Wild2020]. This section describes the mathematical setting.
The mutation game
The game is set on a network of cities on Mars, as described by Wildberger [Wild2003]. Consider a simple undirected graph G with n nodes, described by its adjacency matrix A (where \(A_{ij} = 1\) if nodes i and j are connected, and 0 otherwise).
A state of the game is an integer vector \(v \in \mathbb{Z}^n\), where each component \(v_i\) represents the population at node i. Populations can be positive (“Martians”) or negative (“Anti-Martians”) – Wildberger’s original terminology.
A mutation at node k transforms the state according to the rule:
where the sum runs over all neighbors j of k. All other components remain unchanged: \(v_i' = v_i\) for \(i \neq k\).
Equivalently, the mutation at node k is the linear map \(v \mapsto M_k v\) where \(M_k\) is the identity matrix with row k replaced:
Each mutation is an involution: \(M_k^2 = I\). Applying the same mutation twice returns the state to its original value.
Root systems
The simple roots are the standard basis vectors \(e_1, \ldots, e_n\). Starting from these seeds, the root system \(\Phi\) is the set of all distinct vectors reachable by applying any sequence of mutations:
The root system decomposes into positive roots (all components \(\geq 0\)) and negative roots (all components \(\leq 0\)). Every root is either positive or negative, and \(v \in \Phi\) implies \(-v \in \Phi\).
Roots vs. bases
The simple roots \(e_1, \ldots, e_n\) form a basis of \(\mathbb{R}^n\) – they are linearly independent and span the space. The root system, however, is much larger than a basis. For example, the A3 root system lives in \(\mathbb{R}^3\) (which needs only 3 basis vectors) but contains 12 roots.
Every root can be written as an integer linear combination of simple roots: positive roots have all non-negative coefficients, negative roots all non-positive. But the roots are far from independent – the root system is a highly structured, symmetric set of vectors that the Weyl group permutes.
The Weyl group as a group of symmetries
The mutation matrices \(M_1, \ldots, M_n\) generate a group under matrix multiplication: the Weyl group \(W\). This group is finite for ADE-type graphs and acts on the root system.
The group axioms are satisfied as follows:
Closure: the product of any two mutation matrices (or compositions thereof) is another element of W. In particular, for any root \(v \in \Phi\) and any mutation \(M_k\), the image \(M_k v\) is again a root in \(\Phi\).
Identity: the identity matrix I is the “do nothing” mutation (apply zero mutations).
Inverses: each mutation is its own inverse (\(M_k^2 = I\)), so every generator is an involution. Arbitrary products are inverted by reversing the order: \((M_{k_1} M_{k_2} \cdots M_{k_m})^{-1} = M_{k_m} \cdots M_{k_2} M_{k_1}\).
Associativity: inherited from matrix multiplication.
The root system \(\Phi\) is then an orbit of the simple roots under this group action: \(\Phi = W \cdot \{e_1, \ldots, e_n\}\) (together with their negatives). The root system itself is not a group (it is not closed under addition), but it is the set on which the Weyl group acts faithfully.
Finite and infinite types
Whether the root system is finite depends on the graph:
Finite type – The graph is a simply-laced Dynkin diagram (types A, D, E). The mutation game terminates with a finite root system whose size is determined by the type:
Type
Graph structure
Positive roots
Total roots
\(A_n\)
Path on n nodes
\(\frac{n(n+1)}{2}\)
\(n(n+1)\)
\(D_n\) (\(n \geq 4\))
Path with a fork at one end
\(n(n-1)\)
\(2n(n-1)\)
\(E_6\)
See below
36
72
\(E_7\)
See below
63
126
\(E_8\)
See below
120
240
Infinite type – For any other connected graph (e.g. a cycle, or a tree not of ADE type), the mutation process generates infinitely many distinct roots.
A complete proof that the ADE diagrams are the only simply-laced finite-type graphs is given in Proof of the ADE Classification.
Where does the Cartan matrix come from?
The formula \(C = 2I - A^T\) can look like it was pulled out of a hat. Why \(2I - A^T\) and not, say, \(I + A\) or \(3I - 2A\)? The answer is that the Cartan matrix is not a choice — it is forced by a natural question about symmetry.
The question. Is there a quadratic form \(Q(v) = v^T B\, v\) (a way to measure “size”) that is preserved by every mutation? That is, a symmetric matrix \(B\) such that:
If such a \(B\) exists, then mutations are “rotations” with respect to \(B\) — they move vectors around without changing their \(B\)-length. This is exactly the condition for the Weyl group to be a group of symmetries of a geometric shape (the root polytope).
The answer for A2. Let’s solve this concretely. For \(A_2\) the mutation matrices are:
We seek a symmetric \(B = \bigl(\begin{smallmatrix} a & b \\ b & c \end{smallmatrix}\bigr)\) satisfying \(M_0^T B M_0 = B\) and \(M_1^T B M_1 = B\). This gives a system of equations whose solution (up to an overall scale) is:
for an arbitrary constant \(t > 0\). We can verify this with sympy:
>>> from sympy import symbols, Matrix, solve
>>> a, b, c = symbols('a b c')
>>> B = Matrix([[a, b], [b, c]])
>>> M0 = Matrix([[-1, 1], [0, 1]])
>>> M1 = Matrix([[1, 0], [1, -1]])
>>> # Solve M0^T B M0 = B and M1^T B M1 = B
>>> eqs = []
>>> for M in [M0, M1]:
... diff = M.T * B * M - B
... for i in range(2):
... for j in range(i, 2):
... eqs.append(diff[i, j])
>>> sol = solve(eqs, [a, b, c])
>>> print(sol)
{a: c, b: -c/2}
>>> # So B = c * [[1, -1/2], [-1/2, 1]] = (c/2) * [[2, -1], [-1, 2]]
>>> print(B.subs(sol).subs(c, 2))
Matrix([[2, -1], [-1, 2]])
The unique preserved quadratic form (up to scale) is the Cartan matrix \(C = 2I - A\):
This works for any simply-laced type. For \(A_3\):
>>> from mutation_game import MutationGame
>>> import numpy as np
>>> game = MutationGame.from_dynkin("A3")
>>> # Verify: M_k^T C M_k = C for all k
>>> C = game.cartan_matrix()
>>> for k in range(3):
... M = game.mutation_matrix(k)
... print(f" M_{k}^T C M_{k} == C? {np.allclose(M.T @ C @ M, C)}")
M_0^T C M_0 == C? True
M_1^T C M_1 == C? True
M_2^T C M_2 == C? True
For non-simply-laced types (B, C, F, G), the Cartan matrix \(C = 2I - A^T\) is not symmetric, so it cannot directly be a quadratic form. But there is still a unique (up to scale) symmetric preserved form \(B = D \cdot C\), where \(D\) is a diagonal matrix that accounts for the different root lengths:
>>> game = MutationGame.from_dynkin("B2")
>>> C = game.cartan_matrix()
>>> print("Cartan (non-symmetric):"); print(C)
Cartan (non-symmetric):
[[ 2 -1]
[-2 2]]
>>> # The preserved symmetric form is D @ C with D = diag(2, 1)
>>> D = np.diag([2, 1])
>>> B = D @ C
>>> print("Preserved form B = D C:"); print(B)
Preserved form B = D C:
[[ 4 -2]
[-2 2]]
>>> # Verify: M_k^T B M_k = B
>>> for k in range(2):
... M = game.mutation_matrix(k)
... print(f" M_{k}^T B M_{k} == B? {np.allclose(M.T @ B @ M, B)}")
M_0^T B M_0 == B? True
M_1^T B M_1 == B? True
The diagonal entries of \(D\) are proportional to the squared root lengths: \(d_0 = 2\) (long root) and \(d_1 = 1\) (short root), reflecting the fact that \(B_2\) has roots of two different lengths.
Summary. The Cartan matrix \(C = 2I - A^T\) is not an arbitrary definition. It is the unique inner product (for simply-laced types) or the generator of the unique symmetrized inner product (for non-simply-laced types) that makes every mutation a symmetry. It emerges inevitably from asking: what do the mutations preserve?
The Cartan matrix and finite-type classification
Having motivated the Cartan matrix, we can state its role in classification. For simply-laced types, the Cartan matrix is:
For directed multigraphs (non-simply-laced types), it is \(C = 2I - A^T\).
The type of the root system is determined entirely by the spectrum of the (symmetrized) Cartan form:
Positive definite (all eigenvalues \(> 0\)): the root system is finite. This happens exactly for the ADE Dynkin diagrams.
Positive semi-definite (smallest eigenvalue \(= 0\)): the root system is affine (infinite, but with controlled growth). Example: a cycle graph.
Indefinite (a negative eigenvalue): the root system is infinite with no finiteness structure.
The library uses this criterion directly: is_finite_type() checks whether
the Cartan matrix is positive definite. Methods that require the full root
system (calculate_roots, plot_root_orbits, etc.) raise a
RuntimeError early if the graph is not finite type, rather than running
an unbounded BFS.
>>> from mutation_game import MutationGame
>>> game = MutationGame.from_dynkin("D4")
>>> game.is_finite_type()
True
>>> print(game.cartan_eigenvalues())
[0.58578644 2. 2. 3.41421356]
>>> cycle = MutationGame([[0,1,1],[1,0,1],[1,1,0]])
>>> cycle.is_finite_type()
False
>>> print(cycle.cartan_eigenvalues())
[0. 3. 3.]
Eigenvectors of the Cartan matrix
Since \(C = 2I - A\), the eigenvectors of C are exactly the eigenvectors of the adjacency matrix A (only the eigenvalues shift: if \(A v = \lambda v\) then \(C v = (2 - \lambda) v\)).
The bilinear form \(\langle v, w \rangle = v^T C \, w\) is the natural inner product on the root lattice. The Weyl group preserves this form – every mutation matrix satisfies \(M_k^T C \, M_k = C\). For simple roots, \(\langle e_i, e_j \rangle = C_{ij}\), so the Cartan matrix is literally the Gram matrix of the simple roots under this inner product.
The Perron–Frobenius eigenvector (the eigenvector of A with the largest eigenvalue, equivalently the eigenvector of C with the smallest eigenvalue) has all positive entries and is closely related to the highest root – the positive root with the largest height in the system.
>>> game = MutationGame.from_dynkin("A3")
>>> vals, vecs = game.cartan_eigenvectors()
>>> print("Eigenvalues:", vals)
Eigenvalues: [0.58578644 2. 3.41421356]
>>> print("Perron-Frobenius eigenvector:", vecs[:, 0])
Perron-Frobenius eigenvector: [ 0.5 0.70710678 0.5 ]
Connection to Lie theory
The mutation game is a combinatorial realization of the Weyl group action on a root system [Wild2003] [Wild2020]. The mutation matrices \(M_k\) are the simple reflections \(s_k\) of the Weyl group W(G), and the root system \(\Phi\) produced by the game coincides with the root system of the corresponding simply-laced Lie algebra. Wildberger showed that the graphs for which the mutation game produces a finite root system are precisely the Dynkin diagrams of finite-dimensional complex simple Lie algebras. A related purely combinatorial construction of the Lie algebras themselves for simply-laced diagrams is given in [Wild2003b].
The simple reflection at node k acts on the weight lattice as:
which is precisely the mutation rule: \(v_k \mapsto -v_k + \sum_{j \sim k} v_j\).
Why not embed first?
A natural question arises: if the roots ultimately live in \(\mathbb{R}^{n+1}\) (for \(A_n\)) or some other Euclidean space, why not start there? Why compute in the abstract simple root basis and embed later?
The traditional approach in Lie theory does exactly that:
Start with the Cartan matrix \(C\)
Find vectors \(\alpha_1, \ldots, \alpha_n\) in \(\mathbb{R}^m\) whose dot products match \(C\) (the embedding)
Define reflections \(s_k(v) = v - \frac{2\, v \cdot \alpha_k}{\alpha_k \cdot \alpha_k}\, \alpha_k\) acting on \(\mathbb{R}^m\)
Generate the root system by applying reflections to the simple roots
This works, and the geometry is visible from the start. But Wildberger’s mutation game takes the opposite path:
Start with the adjacency matrix \(A\) (a graph — just 0s and 1s)
Define mutation matrices \(M_k\) (integer entries, no square roots)
BFS in \(\mathbb{R}^n\) to enumerate all roots as integer vectors
Embed into Euclidean space later, if you want to see the geometry
The mutation game approach has several advantages:
Minimal dimension. The computation happens in \(\mathbb{R}^n\) (one coordinate per node), not \(\mathbb{R}^{n+1}\) or higher. For \(A_2\) we work in \(\mathbb{R}^2\), not \(\mathbb{R}^3\).
Pure integer arithmetic. The mutation matrices have integer entries, so all roots have integer coordinates in the simple root basis. No irrational numbers, no floating point, no rounding errors.
No embedding needed. To compute the root system, its size, the mutation paths, or to check finiteness (via the Cartan eigenvalues), you never need to choose an embedding. The combinatorics are self-contained.
Works for any graph. For the ADE types, the classical \(e_i - e_j\) embedding is well-known. But for an arbitrary graph (or directed multigraph), finding an embedding means solving for vectors with prescribed dot products — a harder problem. The mutation game just runs the BFS regardless.
The price is that the geometry is hidden: the roots \((1, 0)\), \((0, 1)\), \((1, 1)\) don’t look like a hexagon until you embed them (as explained in From Platonic Solids to Dynkin Diagrams). But the combinatorial content — how many roots, which mutations connect them, the Weyl group structure — is all there in the integer vectors.
Both approaches produce the same root system. The mutation game is the computational workhorse; the Euclidean embedding is for geometric visualization. This library uses the mutation game for computation and provides the embedding tools when you want to see the shapes.
The mutation graph
The mutation graph has the roots as vertices and an edge between two roots whenever one can be obtained from the other by a single mutation. Each edge is labeled with the index of the mutated node.
For finite-type graphs, the mutation graph is a finite connected graph whose structure encodes the combinatorics of the Weyl group. The shortest path between two roots in this graph gives the minimal sequence of mutations (simple reflections) needed to transform one into the other.
References
N. J. Wildberger, “The Mutation Game, Coxeter Graphs, and Partially Ordered Multisets,” preprint, UNSW, 2003. https://web.maths.unsw.edu.au/~norman/papers/MutationGameCoxeterGraphs.pdf
N. J. Wildberger, “The Mutation Game, Coxeter–Dynkin Graphs, and Generalized Root Systems,” Algebra Colloquium, vol. 27, no. 1, pp. 55–78, 2020.
N. J. Wildberger, “A Combinatorial Construction for Simply-Laced Lie Algebras,” Advances in Applied Mathematics, vol. 30, no. 1–2, pp. 385–396, 2003. doi:10.1016/S0196-8858(02)00541-9