We introduce a class of groups named for H. S. M. Coxeter which generalize involutions in \(\mathbb R^n\). The actions of Coxeter groups arise in the study of networked-numbers games, the first of which appeared in the International Mathematical Olympiad in 1986:
To each vertex of a regular pentagon an integer is assigned, so that the sum of all five numbers is positive. If three consecutive vertices are assigned the numbers \(x\), \(y\), \(z\) respectively, and \(y\) < 0, then the following operation is allowed: \(x, y, z\) are replaced by \(x + y, -y, z + y\) respectively. Such an operation is performed repeatedly as long as at least one of the five numbers is negative. Determine whether this procedure necessarily comes to an end after a finite number of steps.
This game is implemented below. (Refresh the page for a new set of numbers.)
Observe that the operation described in the problem statement, which we shall call firing a vertex, leaves the sum of all vertex labels unchanged. Therefore, if this sum is initially negative, the procedure never terminates.
If we disregard the legality of firings (firing a vertex is legal if its label is negative,) we may observe the following.
Proposition 1.
- Firing the same vertex twice leaves the vertex labels unchanged.
- If \(x\) and \(y\) are adjacent vertices, firing \(x\), \(y\), \(x\) gives the same result as firing \(y, x, y\).
- If \(x\) and \(z\) are nonadjacent vertices, firing \(x, z\) gives the same result as firing \(z, x\).
Proof. Exercise 1.
It turns out that we may encode these properties nicely into presentations by generators and relations of certain groups – examples of the /Coxeter groups./[fn:act] Coxeter groups classify, among other things, all regular polygons, polyhedra, and higher-dimensional polyhedra.[fn:tope]
[fn:act] The game is then described by the action of this group on the set \(\mathbb Z^n.\) [fn:tope] Known as polytopes.
In this section, we formally define the game presented above.
Definition. Let \(G = (V, E)\) be a finite simple graph, and let \(\mathbf A ∈ M|V|(\mathbb Z)\) be a matrix indexed on \(V\) such that \(\mathbf Axy = 2\) if \(x = y\); \(\mathbf Axy ¬= 0\) if \(x ¬= y\) and \((x, y) ∈ E\); and \(\mathbf Axy = 0\) otherwise. Then \(\mathbf A\) is called an amplitude matrix for \(G.\)
Example. For any finite simple graph \(G\) on \(n\) vertices, let \(\mathbf A = 2\mathbf I_n - \mathbf M_G,\) where \(\mathbf I_n\) is the identity matrix and \(\mathbf M_G\) is the adjacency matrix of \(G\). Then \(\mathbf A\) is an amplitude matrix for \(G\), which we shall call the unweighted amplitude matrix.
For the 5-cycle given in the introduction, this matrix is
\[\begin{bmatrix}
2 & -1 & 0 & 0 & -1
-1 & 2 & -1 & 0 & 0 \
0 & -1 & 2 & -1 & 0 \
0 & 0 & -1 & 2 & -1 \
-1 & 0 & 0 & -1 & 2
\end{bmatrix}.\]
Definition. Let \(\mathbf A\) be an amplitude matrix for a finite graph \(G\) on \(n\) vertices. The integral networked-numbers game on \((G, \mathbf A)\) is described as follows:
- The initial game state is a function \(p_0 : V → \mathbb Z\) that assigns an integer, called a population, to each vertex of \(G.\)
- If \(v\) is a vertex of \(G\) with \(p_t(v) < 0,\) the player may legally fire \(v\), producing a new game state \(pt + 1\) with \[pt + 1(w) \coloneqq p_t(w) - \mathbf Avw p_t(v).\] You might think of firing \(v\) as sending \(p_t(v)\) pulses down its incident edges, which are amplified by those edges’ respective amplitudes.
- The objective of the game is to obtain a state with every vertex population nonnegative. If such a state is obtained, there are no legal moves, so the game stops.
We wish to characterize the conditions under which integral networked-numbers games stop. For instance:
Proposition 2. If \(G\) is the 5-cycle and \(\mathbf A\) its unweighted amplitude matrix, the integral networked-numbers game on \((G, \mathbf A)\) stops if the sum of the initial vertex populations is positive.
Proof. Exercise 2.
As we will see, there are several classes of integral networked-numbers games which always stop. In the next sections, we will formally prove this assertion.
If \(G\) is a path on \(n\) vertices, then its unweighted amplitude matrix \(\mathbf A\) is the tridiagonal matrix
\[A_n \coloneqq \begin{bmatrix}
2 & -1 & & & &
-1 & 2 & -1 & & & \
& -1 & \ddots & \ddots & & \
& & \ddots & 2 & -1 & \
& & & -1 & 2 & -1 \
& & & & -1 & 2
\end{bmatrix}.\]
An ING on a path of length 3 is playable below.
Observe that only the left and center vertices are ever fireable. In fact, all possible states are mapped below:
Here is another ING on a path of length 3.
Its possible states are mapped below.
Call a diagram like this, whose vertices are possible states and whose edges represent legal firings, a game graph. The previous two game graphs take the shapes of a hexagon and a rhombus, respectively. Here is another ING whose game graph is comprised of two hexagons adjoined to six rhombuses, in the shape of a hexagonal prism.[fn:2]
[fn:2] The reader is invited to verify this fact.
We shall see that any unweighted amplitude matrix, regardless of initial state, gives rise to game graphs that are comprised of hexagons and rhombuses.
Definition. A finite directed acyclic graph is hexarhombic if whenever \(u, v, w\) are vertices with \(u → v\), \(u → w\), one of the following two cases holds:
- There is a vertex \(x\), such that \(v → x\) and \(y → x\).
- There are vertices \(x, y, z\) such that \(v → x → z\) and \(w → y → z.\)
The reader should observe that in each of the INGs presented in the previous section, the final state and the number of steps taken to reach it are the same regardless of the player’s choice of firings. In game theory, this property is called strong convergence; we formally define it now.
Definition. An ING is said to be strongly convergent if for any initial state \(p_0\), exactly one of the following holds:
- there is a nonnegative integer \(n\) such that the game stops after any sequence of exactly \(n\) legal firings, and the final state \(p_n\) is independent of the sequence of firings; or
- no sequence of legal firings causes the game to stop.
From the game graph of a given ING, it is easy to determine whether condition 1 holds;[fn:fora] every path from the initial state to the final state will have length \(n\).[fn:edges] If condition 2 holds, the game graph is infinite or cyclic.
[fn:fora] For a given initial state. [fn:edges] In the sense that it has \(n\) edges.
Proposition 3. If the game graph of an ING with a given initial state is hexarhombic, then the ING is strongly convergent from that state.
Proof. It suffices to show that hexarhombic graphs have the property remarked on above. Let \(G\) be a hexarhombic graph. Since \(G\) is finite and acyclic, it has a vertex with no successors. Call this vertex \(z.\) We claim that for any other vertex \(v ∈ G\) from which \(z\) is reachable, there is a positive integer \(d(v)\) such that every path of length \(d(v)\) beginning at \(v\) ends at \(c.\)
Suppose \(y → z.\) If \(y\) has another successor \(y’\), then by the hexarhombicity of \(G\) there must be a vertex \(z’\) with \(y’ → z’\), \(z → z’\), but by assumption \(z\) has no successors. Therefore every path of length \(1\) beginning at \(y\) ends at \(z\), so \(d(y) = 1.\)
Suppose \(x → y → z\). We claim \(d(x) = 2\). It suffices to show that if \(x → y’,\) then \(d(y’) = 1;\) i.e., \(y’ → z.\) Suppose otherwise. Then clearly \(y’ ¬ = y,\) so there is a vertex \(z’ ¬= z\) with \(y’ → z’\) and \(y → z’.\) But \(y → z\) and \(y → z’\), which contradicts the terminality of \(z.\)
Now let \(k \geq 2\) be a positive integer, and assume inductively that whenever \(d(v) = k’ < k\) and \(u → v\) we have \(d(u) = k’ + 1.\)
Now suppose inductively that \(u → v\) and \(d(v) = k.\) We claim that \(d(u) = k + 1.\) Let \(v’\) be a successor of \(u\) with \(v’ ¬ = v\); it suffices to show that \(d(v’) = k.\) There are now two cases.
- There is a vertex \(x\) with \(v’ → x, v → x.\) Suppose \(d(x) ¬ = k - 1\); then there is a path from \(x\) to \(z\) not of length \(k - 1\), which can be extended to give a path from \(v\) to \(z\) not of length \(k\). This violates our assumption that \(d(v) = k,\) so we must have \(d(x) = k - 1,\) and by the inductive hypothesis, \(d(v’) = k.\)
- There are vertices \(w, x, y\) with \(v’ → w → y\) and \(v → x → y.\) As before, we must have \(d(x) = k - 1\) and \(d(y) = k - 2.\) Then by the inductive hypothesis \(d(w) = k - 1\) and \(d(v’) = k.\)
This completes the induction. Translating the result we have just shown into the language of INGs, it is apparent that for any starting position \(v\) that gives rise to a hexarhombic game graph, the terminal position and the number of steps required to reach it is unique.[fn:although]
[fn:although] Although it may depend on \(v.\)
We now formalize the increasingly apparent group structure of an ING.
Definition. A Coxeter group is a group \(G\) with presentation by generators and relations \[G = \left\{\{x_i\}i ∈ I \mid (x_ix_j)n(i, j) = e\right\},\] where \(I\) is an index set and \(n : I × I → \mathbb N ∪ \{∞\}\) is such that \(n(i, i) = 1\) and \(n(i, j) \geq 2\) if \(i ¬ = j.\)
Example. Some familiar examples of Coxeter groups:
- The group \(\mathbb Z_2^k\) is a Coxeter group, with \(k\) generators \(x1, …, k.\) For any \(1 \leq i < j \leq k,\) \(n(i, j) = 2.\)
- The dihedral group \(D2k\) is a Coxeter group whose generating set is comprised of \(k\) reflections \(\{L_1, …, L_k\}\).
- Let \(G = (V, E)\) be a finite simple graph, and let \(\mathbf A\) be its unweighted amplitude matrix. Let \(x_v\) represent the action of firing node \(v\), irrespective of whether doing so is legal. Then, by Proposition 1, the \(x_v\) generate a Coxeter group with \[n(v, w) = \begin{cases}2, &(v, w) ∈ E, \3, & (v, w) ¬ ∈ E.\end{cases}\]
The natural intuition for a generic Coxeter group is the transformations of space effected by a generating set of reflections (which are all involutions.) In example 1, the reflections invert one axis and fix all the others. In example 2, the reflections fix a given vertex and/or the midpoint of a given side (depending on the parity of \(k\)).
Example 3, which is of course the most pertinent to us, can also be thought of as a reflection group. Consider the ING on the length-3 chain, as above.[fn:general] Let \(p_0 = \begin{bmatrix} a & b & c \end{bmatrix}^\top\) be completely arbitrary. Firing the node whose population is \(a\) gives \(p_1 = \begin{bmatrix}-a & a + b & c\end{bmatrix}^\top.\) We can write this as a linear transformation:
\[ p_1 = \begin{bmatrix} -a \ a + b \ c \end{bmatrix} = \begin{bmatrix} -1 & 0 & 0 \ 1 & 1 & 0 \ 0 & 0 & 1 \end{bmatrix} \begin{bmatrix} a \ b \ c \end{bmatrix} = X_ap_0. \]
Note that the matrix \[ X_a = \begin{bmatrix} -1 & 0 & 0 \ 1 & 1 & 0 \ 0 & 0 & 1 \end{bmatrix}\] is independent of \(p.\) Similar calculations for the other two nodes give the matrices \[X_b = \begin{bmatrix} 1 & 1 & 0 \ 0 & -1 & 0 \ 0 & 1 & 1\end{bmatrix}, \quad X_c = \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & 1 \ 0 & 0 & -1 \end{bmatrix}. \]
At this point the reader is urged to verify the relations
\[\begin{aligned}
X_a^2 = X_b^2 = X_c^2 &= I_3,
(X_aX_b)^3 = (X_bX_c)^3 = (X_aX_c)^2 &= I_3,
\end{aligned}\]
and to calculate the equations of the planes in \(\mathbb R^3\) fixed by each of \(X_a, X_b, X_c.\)
[fn:general] Exercise 7 asks you to do this for a generic ING.
The following proposition, which Exercise 8 asks you to show, generalizes hexarhombicity to “polygonality.”
Proposition 4. Consider the ING on \((G, \mathbf A)\). Suppose the set \(\{x_v\}v ∈ G,\) as defined above, generates a Coxeter group defined by \(n : V × V → \mathbb N ∪ \{∞\}.\) Suppose also that from any position \(p\) with \(p(v), p(w) < 0\) for some vertices \(v, w,\) the firing sequences \[ \underbrace{v, w, v, w…}n(v, w); \quad \underbrace{w, v, w, v…}n(v, w) \] are both legal. Then the ING is strongly convergent from \(p.\)
The following characterization of strongly convergent INGs is due to Eriksson.[fn:real]
Theorem. [Eriksson 1996] The ING on \((G, \mathbf A)\) is strongly convergent if \(\mathbf Avw, \mathbf Awv < 0 \) for any edge \((v, w).\)
[fn:real] The converse of this theorem also holds, but is beyond our scope. In fact, Eriksson showed a stronger result which holds for networked-numbers games whose amplitudes and populations may be real numbers.
Proof. It will suffice to show that the set \(\{x_v\}v ∈ G\) generates a Coxeter group. The behavior of this group turns out to depend on the product \(α(v, w) \coloneqq \mathbf Avw\mathbf Awv,\) which is a positive integer by assumption. We shall treat only the case \(α(v, w) = 1;\) the other cases are left as exercises.
If \(α(v, w) = 1\), we must have \(\mathbf Avw = \mathbf Awv = -1.\) Let \(x ∈ G\) be adjacent to exactly one of \(v, w\) — assume \(v\) without loss of generality — and consider the actions of firing \(v\) and \(w\) as \(3 × 3\) matrices, indexed in the order \(x, v, w\): \[X_v = \begin{bmatrix} 1 & -Avx & 0 \ 0 & -1 & 0 \ 0 & -Avw & 1\end{bmatrix}, \quad X_w = \begin{bmatrix} 1 & 0 & 0 \ 0 & 1 & -Awv \ 0 & 0 & -1 \end{bmatrix}. \]
Note that \(X_v^2 = X_w^2 = \mathbf I_3.\) Now consider the products
\(\begin{aligned}
X_wX_v &= \begin{bmatrix} 1 & -\mathbf Avx & 0 \ 0 & α(v, w) - 1 & -\mathbf Awv \ 0 & \mathbf Avw & -1 \end{bmatrix}
= \begin{bmatrix} 1 & -\mathbf Avx & 0 \ 0 & 0 & 1 \ 0 & -1 & -1 \end{bmatrix};
X_vX_w &= \begin{bmatrix} 1 & -\mathbf Avx & \mathbf Avx\mathbf Awv \ 0 & - 1 & \mathbf Awv \ 0 & -\mathbf Avw & α(v, w) - 1 \end{bmatrix}
= \begin{bmatrix} 1 & -\mathbf Avx & -\mathbf Avx \ 0 & -1 & -1 \ 0 & 1 & 0 \end{bmatrix}; \
X_wX_vX_w &= \begin{bmatrix} 1 & -\mathbf Avx & \mathbf Avx\mathbf Awv \ 0 & α(v, w) - 1 & \mathbf Awv(2 - α(v, w)) \ 0 & \mathbf Avw & 1 - α(v, w) \end{bmatrix}; \
X_vX_wX_v &= \begin{bmatrix} 1 & -\mathbf Avx(α(v, w)) & \mathbf Avx\mathbf Awv \ 0 & 1 - α(v, w) & \mathbf Awv \ 0 & \mathbf Avw(2 - α(v, w)) & α(v, w) - 1 \end{bmatrix}.
\end{aligned}\)
Observe that \[ X_vX_wX_v = \begin{bmatrix} 1 & -\mathbf Avx & -\mathbf Avx \ 0 & 0 & -1 \ 0 & -1 & 0\end{bmatrix} = X_wX_vX_w, \] from which we have \((X_vX_w)^3 = (X_wX_v)^3 = \mathbf I_3.\)
Furthermore, observe that the \(v\)-rows of \(X_w\) and \(X_wX_v\), as well as the \(w\)-rows of \(X_v\) and \(X_vX_w\), are nonpositive and not the zero vector. Therefore, if we begin from a position in which \(v\) and \(w\) are both fireable, the firing sequences \(v, w, v\) and \(w, v, w\) are legal and form a hexagon in the game graph. Similarly, simultaneously fireable nonadjacent vertices form rhombuses. So the game graph arising from an unweighted amplitude matrix is hexarhombic, and its associated ING strongly converges by Proposition 3.
Similar arguments go through for the cases \(α(v, w) ∈ \{2, 3\}\) (Exercise 9) and \(α(v, w) \geq 4\) (Exercise 10.) Thus, the set \(\{X_v\}v ∈ G\) generates a Coxeter group. By the result of Exercise 7, the group generated by \(\{x_v\}v ∈ G\) is also Coxeter. So by Proposition 4, the ING is strongly convergent.
- Prove Proposition 1.
- Let \(G = (V, E)\) be the 5-cycle, and let \(\mathbf A\) be its unweighted amplitude matrix. Use the symmetry of \(G\) to show that any valid firing decreases the function \[I(t) \coloneqq ∑\substack{v ¬ = w \ (v, w) ¬ ∈ E} (p_t(v) - p_t(w))^2.\] Conclude that the integral networked-numbers game on \((G, \mathbf A)\) stops if \(∑v ∈ G p_0(v) > 0.\)
- What can be said about the converse of Exercise 2?
- Investigate whether Exercise 2 generalizes to cycles of different length.
- Verify that \(D2k\) is a Coxeter group with generating set given by its reflections. For reflections \(L_i, L_j\), what is \(n(i, j)\)?
- Show that the set of rigid motions of any Platonic solid forms a Coxeter group.
- Consider the integral networked-numbers game on \((G, \mathbf A_G).\) Write the action of firing an arbitrary vertex \(v ∈ V\) as a linear transformation \(X_v : \mathbb Z|V| → \mathbb Z|V|.\) Show by direct calculation that the function \(φ\) that maps \(x_v \mapsto X_v\) is an injective homomorphism from the Coxeter group generated by \(x_v\) onto the subgroup of \(GL(|V|, \mathbb Z)\) generated by \(X_v.\)[fn:rep]
- Generalize the proof of Proposition 3 from rhombuses and hexagons to arbitrary \(2k\)-gons. Use this result to prove Proposition 4. Make sure to cover the case \(n(v, w) = ∞.\)
- Why does it suffice to consider only \(v, w,\) and \(x\) in the proof of the theorem?
- Using the setup from the theorem, show that if \(α(v, w) = 2\), \((X_vX_w)^2 = (X_wX_v)^2 = \mathbf I_3\), and if \(α(v, w) = 3,\) \((X_vX_w)^3 = (X_wX_v)^3 = \mathbf I_3.\) Show that the corresponding firing sequences are legal in positions where \(v, w\) are both fireable.
- Using the setup from the theorem, show that if \(α(v, w) \geq 4,\) then \(X_vX_w\) and \(X_wX_v\) have infinite order in \(GL(|V|, \mathbb Z),\) and in positions where \(v, w\) are both fireable, any sequence \(v, w, v, …\) or \(w, v, w, …\) is legal. Conclude that such positions diverge.
- Show that each of the game graphs on length-3 paths given in this chapter can be realized as minors of the Cayley graph of the Coxeter group generated by \(\{X_a, X_b, X_c\},\) which corresponds to the truncated octahedron. To which polytopes do the other INGs correspond?
[fn:rep] Such a homomorphism is called a faithful representation.
- Kimmo Eriksson, ”Strong Convergence and a Game of Numbers,” European Journal of Combinatorics 17 (1996): 379-390.
- Eriksson, ”The Numbers Game and Coxeter Groups,” Discrete Mathematics 139 (1995): 155-166.
- Eriksson, ”Convergence of Mozes’s Game of Numbers,” Linear Algebra and its Applications 166 (1992): 151-165.
Humphreys, Coxeter groups and reflection groups.
Coxeter, Regular polytopes and Regular complex polytopes.
McMullen & Schulte, Regular polytopes in ordinary space.