On Word Representations and Embeddings in Complex Matrices

arXiv:2604.15386 · cs.FL, cs.DM, math.GR, math.RT · Submitted 2026-04-16 · Read on arXiv

Listen

Radio episode about this paper

Transcript

Introduction to the show: ident: Computer Science. The day in computer science: software, systems and theory on arXiv.

Tom: We're looking at the paper: "On Word Representations and Embeddings in Complex Matrices".

Paper summary: Tom: So to get into what this paper is doing, they are developing new techniques for constructing word representations of the Euclidean Bianchi groups. They claim these new representations provide a symbolic framework and a natural first step towards analyzing fundamental decision problems in those two by two matrix semigroups.

Jane: The authors are aiming to characterize which word structures admit faithful low-dimensional matrix representations over the complex numbers, and they develop these techniques specifically for the Euclidean Bianchi groups. That's Theorem three they developed <ref:2604.15386#pg1>.

Lu: This is essentially an essential first step to study fundamental decision problems in two by two matrix semigroups through their symbolic representations like membership, freeness, and vector reachability in those matrix domains.

Meng: I'm curious about the methodology here. They develop a procedure to construct word representations for elements of Euclidean Bianchi groups. How do they actually do that?

Tom: The procedure involves two main steps first constructing an element H in PSL2 of Od such that M times H is upper triangular and then representing an upper triangular element M as a specific sequence of matrix products.

Jane: This construction step relies on the ring of integers Od equipped with the field norm N being a Euclidean domain. They loop this process until a matrix M times H satisfies gamma k equals zero.

Lalam: And then they represent that upper triangular element M as L epsilon T p0 U q0 times AT pk Uqk times AT pk minus one U qk minus one and so on, which is the word representation itself. The polynomial runtime is established by bounding the number of iterations and the sizes of the integer exponents in that word representation.

Tom: It sounds like they're setting up a clear symbolic framework for these groups using words and then showing how to compute things within those words, which is pretty cool for connecting it all together.

Conclusion: Jane: Looking at the "On Word Representations and Embeddings in Complex Matrices", the authors are essentially mapping out the landscape of possible embeddings between word structures and matrix semigroups. They summarize non-existence results for embeddings into O2 times 2d and SL2 of Od based on a parameter d <ref:2604.15386#pg1>.

Tom: They also list existing embeddings, like Proposition five for free groups over unary alphabets into Z two by two and Proposition six for free groups over binary alphabets into C two by two. There are also non-existence proofs that often rely on analyzing the Jordan normal forms of the resulting matrices to derive contradictions based on group relations.

Lu: The paper relies on techniques similar to those found in previous work, specifically looking at how generators map and deriving contradictions based on matrix relations when proving non-existence statements for embeddings into O3 times 3d <ref:2604.15386#pg1>.

Meng: I want to ask about the limitations they mention. Since they're doing this in complex matrices, what is the actual constraint that limits their results?

Lalam: One limitation mentioned is that the proof of Theorem three for d equals two, three, seven and eleven splits into two parts: construction and runtime <ref:2604.15386#pg1>. The construction involves a sequence of matrices H l such that N gamma l is strictly decreasing until it reaches zero.

Tom: And the runtime analysis is tied to bounding the matrix norms and the sizes of those integer exponents in the word representation. So they establish a polynomial runtime for these constructions, which is good because it gives us some kind of complexity measure.

Jane: Overall, this paper helps determine which techniques from linear algebra can be applied to word problems versus those that require different approaches. It's about figuring out the limits of what you can represent symbolically in low-dimensional matrix semigroups.

Lu: It provides a clear path forward for analyzing fundamental decision problems in two by two matrix semigroups using these symbolic representations, which is where the real potential for applying this research lies.

Meng: So it's less about finding one big answer and more about building a toolkit for figuring out what's possible and what isn't in these matrix settings.

Lalam: It gives us a symbolic framework that lets us test membership and freeness questions inside these two by two matrix semigroups directly, which is a solid starting point for future work.

Paul C. Bell, George Kenison, Reino Niskanen, Igor Potapov, Pavel Semukhin

Liverpool John Moores University · KU Leuven

cs.FL, cs.DM, math.GR, math.RT

Submitted: 2026-04-16

Updated: 2026-11-18

Comments: 23 pages. Full version of conference paper accepted to DLT 2026

License: http://creativecommons.org/licenses/by-nc-sa/4.0/

Importance score: 80/100

The gist: Embeddings of word structures into matrix semigroups provide a natural bridge between combinatorics on words and linear algebra However…

Key concepts

Word Representations
This involves representing sequences of generators (words) from a group or semigroup as specific matrices. This allows questions about combining words (concatenation) and computational models to be translated into standard matrix multiplication, providing an algebraic framework for studying word structures.
Euclidean Bianchi Groups
These are specific groups studied in the paper whose elements can be represented by matrices. The authors develop a procedure to construct explicit word representations for these groups, which is a key contribution to understanding their structure through symbolic matrix forms.
Matrix Semigroups
A semigroup is a set with an associative binary operation, and this study focuses on semigroups whose elements are matrices. Analyzing these structures helps in understanding the structural restrictions imposed by low-dimensional matrix constraints on word embeddings.
Boundary Characterization
This refers to investigating the limits of embedding word structures into different matrix semigroups. The paper summarizes results showing when certain pairs of words cannot be embedded into specific matrix groups, helping to define the boundary between possible and impossible embeddings.

Terminology

Summary

Embeddings of word structures into matrix semigroups provide a natural bridge between combinatorics on words and linear algebra However, low-dimensional matrix semigroups impose strong structural restrictions on possible embeddings This paper explores the boundary between combinatorics on words and matrix semigroups, aiming to characterise which word structures admit faithful low-dimensional matrix representations over complex numbers and develops new techniques to find word representations for the Euclidean Bianchi groups (Theorem 3)

Foundational Concepts

The study connects combinatorial group theory with linear algebra by representing words or generators as matrices By representing words or generators as matrices, questions about concatenation of words and computational models operating on words can be translated into questions about matrix multiplication Embeddings into integer or complex matrices provide a concrete and well-understood algebraic framework in which structural properties of (semi)groups can be analysed, while also enabling the transfer of results between the theory of words and the theory of matrix semigroups The origins of this connection go back to Nielsen's work on free groups in the 1920s Magnus showed that free groups admit faithful representations into groups of matrices over certain rings of formal power series Recent work has highlighted the importance of decision problems for matrix semigroups over complex numbers, particularly concerning embeddings into the 2 × 2 complex matrices

Word Representation Procedure

The paper develops a procedure to construct word representations for elements of Euclidean Bianchi groups (Theorem 3) The procedure involves two main steps:

  1. Constructing an element H in PSL(2, Od) such that MH is upper-triangular This step relies on using the fact that the ring of integers Od equipped with the field norm N is a Euclidean domain The construction involves looping a process until a matrix MH satisfies γk = 0

  2. Representing an upper-triangular element M = αβ/γδ as LϵT p0U q0 · AT pk Uqk · AT pk−1U qk−1 · · · AT p1U q1 The polynomial runtime is established by bounding the number of iterations and the sizes of the integer exponents in the word representation

Boundary Characterization

The paper investigates the border between existence and non-existence of injective morphisms from pairs of word (semi)groups to various matrix semigroups It summarizes results concerning embeddings, such as non-existence results for pairs of words into different matrix semigroups Proposition 9 lists several non-existence results for embeddings into O2×2d and SL(2, Od) based on the value of d For instance, there is no embedding from S(Σ2) × F(Σ1) into O2×2d

Decidability and Complexity

The work touches upon the decidability of fundamental decision problems for matrix semigroups over complex numbers The construction of word representations for PSL(2, Od) is related to the decidability of the identity problem for matrices over SL(2, Od) The polynomial runtime analysis provides a framework for analyzing fundamental decision problems in 2×2 matrix semigroups within their symbolic representations like membership and freeness The paper also discusses the complexity of word structures one can embed into restricted groups and semigroups of low-dimensional matrices

Summary of Embeddings

The paper presents several known group embeddings, such as Proposition 5 for F(Σ2) → Z2×2 and Proposition 6 for F(Σ2) → C2×2 It also lists existence results, including the embedding from F(Σ1) × F(Σ1) into U(2, N) The non-existence proofs often rely on analyzing the Jordan normal forms of the resulting matrices to derive contradictions based on group relations The final section confirms that Claims 1 and 2 hold for each d in the specified set by performing exhaustive searches using SageMath

Committed Embeddings Proofs

The proof of Claim 2 involves an exhaustive search for pairs (M, M') of matrices in PSL(2, Od) that falsify the claim The search procedure utilizes a function Quotient to find the nearest integer in Od to determine if M < M' holds The proof confirms that Claims 1 and 2 hold for each d in the set by confirming the results of Claim 1 and Claim 2 using computer assistance

The final case in Proposition 9, concerning the non-existence of an embedding from F(Σ2)×S(Σ2) into O3×3d, is proven by analyzing the Jordan normal forms of the resulting matrices The proof rules out each potential Jordan normal form based on relations derived from the generators This leads to a contradiction regarding the embedding being injective

The construction of word representations for PSL(2, Od) is analogous to that employed in the proof for the Picard group PSL(2, Z) The proof of Theorem 3 for d = 2, 3, 7, 11 splits into two parts: construction and runtime The construction involves a sequence of matrices Hl such that N(γl) is strictly decreasing until it reaches zero The polynomial runtime is established by bounding the matrix norms and the sizes of the integer exponents in the word representation

The proof of Claim 2 for d = 2, 3, 7, 11 involves an exhaustive search for pairs (Ml−1, Ml) of matrices that falsify the claim The proof confirms that Claims 1 and 2 hold for each d in the set by confirming the results of Claim 1 and Claim 2 using computer assistance

The proof of Proposition 9 relies on techniques akin to those found in [7,19] The non-existence statements are proven by considering the mapping of generators and deriving contradictions based on matrix relations This leads to a contradiction regarding the embedding being injective

The proof of Proposition 8 involves defining four specific mappings φ1, φ2, φ3, and φ4 that demonstrate injectivity for the respective embeddings These mappings use well-known embeddings from the literature for the first component The determinant is additionally used to count the number of unary letters in some mappings

Green — the paper says it, and the page is printed. Red — no passage carries it, so treat that sentence as unverified. The same check runs on your own text: check a summary against its source, $5.

Improvements for AI systems

  1. Better word representation construction for Euclidean Bianchi groups: The system can now output a word representation for any element M in a Euclidean Bianchi group PSL(2, Od) using Theorem 3, providing a symbolic framework for analyzing fundamental decision problems like membership and freeness.

  2. Enhanced analysis of embedding boundaries: The system can determine which word structures admit faithful low-dimensional matrix representations over complex numbers by systematically checking the non-existence results summarized in Table 1 and Table 2.

  3. Automated verification of embedding existence: The system can test for the existence of injective morphisms from pairs of word (semi)groups to various matrix semigroups by utilizing the established necessary conditions derived in Proposition 9.

  4. Polynomial time complexity analysis for word representations: The system can guarantee a polynomial runtime for generating word representations, leveraging the bounds derived from Lemma 11 and Claim 2 regarding Euclidean minima kappa(d).

  5. Decision problem solving within matrix semigroups: By providing a symbolic framework via word representations, the system can serve as a natural first step towards analyzing fundamental decision problems in 2x2 matrix semigroups, such as membership and vector reachability.

Abstract

Embeddings of word structures into matrix semigroups provide a natural bridge between combinatorics on words and linear algebra. However, low-dimensional matrix semigroups impose strong structural restrictions on possible embeddings. Certain finitely generated groups admit faithful representations in SL(2, C) and other similar matrix groups. On the other hand, it is known that the product of two free semigroups on two generators cannot be embedded into the 2x2 complex matrices. In this paper we study embeddings of word structures into low-dimensional matrix semigroups over the complex numbers and develop new techniques for constructing word representations of the Euclidean Bianchi groups. These representations provide a symbolic framework and a natural first step towards analysing fundamental decision problems in 2x2 matrix semigroups.

Related papers