Games in the matrix
Ilijas Farah · 2025
Read Games in the matrix by Ilijas Farah (2025) in the Tower of Babel, a free online library of public-domain works preserved in clean, searchable text. No sign-up. The full text is served as a plain-text file at a predictable URL, where text is present: https://antarctic-labs.com/tower-of-babel/arxiv-2511-07456.txt.
Introduction
Ilijas Farah poses a playful but deep question about matrices: as square complex matrices grow without bound, do their algebras start to look alike? The short abstract admits nobody knows the answer yet. Farah frames the problem as a game, inviting readers to play along and see how far the play leads. As a brief, openly exploratory piece on a hard open question in operator algebras, it offers an entry point and a challenge rather than a settled theorem.
Catalog record
| CREATOR | Ilijas Farah |
|---|---|
| YEAR | 2025 |
| COLLECTION | PAPERS |
| FORMAT | TXT |
| FILE SIZE | 35 KB |
| VERSION | 1.0 |
| LICENSE | http://creativecommons.org/licenses/by/4.0/ |
| RIGHTS | CC BY |
| SOURCE | arXiv |
Source: https://arxiv.org/abs/2511-07456
Browse the full library · About the Tower of Babel
Full text
The opening of the work, from the library's hosted text:
Games in the matrix Thanks: Partially supported by NSERC Ilijas Farah Abstract 1. Games Let’s start with the simplest interesting mathematical structures. A simple graph is a set of vertices some of which are connected by an ‘edge’ (the technical term is ‘adjacent’). What makes a graph simple is that only distinct nodes can be adjacent and that we do not allow multiple edges between any two vertices. We write G=(V,E) , where V is the set of vertices and E is the set of connections, called edges. If V has m elements, then there are exactly m\choose 2 ways to choose the edges, because for every pair of distinct vertices we have two choices, whether to connect them with an edge or not. To compare two graphs, we will play a game. Given graphs G_{1}=(V_{1},E_{1}) and G_{2}=(V_{2},E_{2}) and n\geq 1 , the game \Gamma(G_{1},G_{2},n) between two players, Challenger and Duplicator is played in n innings and has the following rules. In each inning Challenger chooses a vertex in either one of the graphs. Duplicator responds by choosing a vertex the other graph. Thus in the j -th inning a vertex a_{j} in V_{1} and a vertex b_{j} in V_{2} are chosen. We add the (unnecessary) requirement that vertices cannot be repeated; the first player who repeats a vertex loses the game. After n innings, Duplicator wins if all i and j satisfy a_{i}\E_{1}a_{j} if and only if b_{i}\E_{2}b_{j} (another way to say this is that the map a_{i}\mapsto b_{i} , for i\leq n , is an isomorphism between the induced subgraphs ); otherwise Challenger wins. Let’s get some easy observations out of the way. If there is an isomorphism \Phi between the graphs, then Duplicator can win the game by applying \Phi or its inverse to the vertices provided by the Challenger. If both graphs have n vertices, then a game in which Duplicator wins produces an isomorphism between the two graphs. Each game considered in this note is a finite game of perfect information, meaning that each player has complete knowledge of the history of the game up to their current turn. For example, both chess and go are finite games of perfect information, but in each of these games draw is a possible outcome. Since draw is not a possible outcome in any of the games considered in this note, being a finite game of perfect information implies that one of the players has a winning strategy. 1 1 1 The question of the existence of a strategy for one of the players (a property called determinacy) for infinite games is the first in a long list of fascinating topics related to our subject that we regrettably do not have time to discuss. A winning strategy in \Gamma(G_{1},G_{2},n) for Duplicator is a function from positions in the game in which it is Duplicator’s turn whose values are valid moves in the game, and such that by following this strategy Duplicator wins the game regardless of how Challenger plays. A winning strategy for Challenger is defined analogously. If each of the players had a winning strategy, then pitting these strategies against each other would result in a game in which both players win; contradiction. An example of a winning strategy is provided in the proof of Theorem 1.1 below. In chess and go there are three possible outcomes: (i–ii) One of the players has a winning strategy, or (iii) each of the players has a strategy that assures that they do not lose the game. We move on to a (somewhat) nontrivial example of a winning strategy for Duplicator. For m\geq 3 let C_{m} be the cycle graph , whose vertices are \{1,\dots,m\} and two vertices i,j are adjacent if and only if |i-j|=1 or \{i,j\}=\{1,m\} . Theorem 1.1 . If \min(m,k)>2^{n+1} , then Duplicator wins \Gamma(C_{m},C_{k},n) . Proof. The distance , d(x,y) between two vertices x,y in a graph is the smallest l such that there is a path from x to y of length l in which each step consists of moving to an adjacent vertex. 2 2 2 If there is no such l then we set d(x,y)=\infty . For j\geq 1 we say that two vertices x,y in C_{m} are j -far if d(x,y)>2^{j} , and that a path is j -long if its length is >2^{j} . Note that vertices are 0-near if and only if they are adjacent. We can now describe the strategy for the Duplicator. The positions in this game are so similar that there is no harm in pretending that the Challenger always chooses vertices from the first graph. To increase the stakes, we switch to the first-person narrative. In the first inning, we can play any vertex b_{1} . In the second move, we have vertices a_{1} and a_{2} in one of the graphs and b_{1} in the second. If one of the paths is n -short (meaning, not n -long), then choose b_{2} so that d(b_{1},b_{2})=d(a_{1},a_{2}) . The salient point is that, because a 1 a 3 a 2 a 5 a 4 b 1 b 3 b 2 b 5 b 4 Figure 1. The position after five innings. Since m and l are very large, we zoomed out so much that the vertices blended into two continuous circles. The corresponding short (red) arcs are of the same length, while the long (blue) arcs are simply sufficiently long. No matter what vertex the Challenger plays, we can respond by choosing a vertex in the corresponding arc that is either at the right distance or sufficiently far from the corresponding ends. \min(m,k)>2^{n+1} , the longer path between a_{1} and a_{2} is n -long, and so is the longer path between b_{1} and b_{2} . If a_{1} and a_{2} are n -far, then take b_{2} to be any vertex n -far from b_{1} ; this is possible because \min(m,k)>2^{n} . At this stage we have vertices a_{1} and a_{2} ‘splitting’ one cycle into two arcs and b_{1} and b_{2} ‘splitting’ the other cycle into two arcs. Either all of the arcs are sufficiently long, or the short arcs are of the same length. Our strategy in the k+1 -st inning for k\geq 2 hinges on the following inductive hypothesis holding after the k -th inning. (IH k ) The vertices a_{1},\dots,a_{k} and b_{1},\dots,b_{k} are arranged on their cycles so that for all i and j either d(a_{i},a_{j})=d(b_{i},b_{j}) or a_{i} and a_{j} are k+1 -far and b_{i} and b_{j} are k+1 -far. After the k -th inning for k\geq 2 , Challenger adds a vertex a_{k+1} to one of the arcs, between vertices a_{i} and a_{j} for some i,j . If it is added to a short arc, then we can choose b_{3} so that sides of the ‘triangle’ 3 3 3 These triangles are rather flat, but no worries. b_{i},b_{j},b_{k} are equal to the corresponding sides of the ‘triangle’ with the vertices a_{i},a_{j},a_{k} . If a_{k} is added to a long arc, but it is n-1 -near a_{i} , then we play b_{k} on the arc b_{i},b_{j} so that d(b_{k},b_{i})=d(a_{k},a_{i}) . Otherwise, play b_{k} that is k -far from both b_{i} and b_{j} . After this move, the