Paper deep dive
Grokking Finite-Dimensional Algebra
Pascal Jr Tikeng Notsawo, Guillaume Dumas, Guillaume Rabusseau
Intelligence
Status: succeeded | Model: Gemma-4-26B-A4B | Prompt: intel-v1 | Confidence: 92%
Last extracted: 7/20/2026, 4:09:09 PM
Summary
This paper investigates the 'grokking' phenomenon in neural networks by extending the analysis from group operations to finite-dimensional algebras (FDA). It establishes that learning FDA multiplication is equivalent to learning a bilinear product defined by a structure tensor. The study demonstrates that for algebras over reals, this relates to matrix factorization, while for finite fields, it involves learning discrete representations. The authors experimentally analyze how algebraic properties (commutativity, associativity, unitality) and tensor structural features (sparsity, rank) influence the emergence and timing of grokking, providing a unified framework for understanding generalization dynamics in neural networks.
Entities (9)
Relation Signals (7)
Grokking → occursin → Finite-Dimensional Algebra
confidence 95% · This paper investigates the grokking phenomenon... in the context of learning multiplication in finite-dimensional algebras (FDA).
Finite-Dimensional Algebra → representedby → Structure Tensor
confidence 95% · learning multiplication in FDA amounts to learning a bilinear product specified by the algebra's structure tensor.
Complex Numbers → isinstanceof → Finite-Dimensional Algebra
confidence 92% · Grokking... on a 2-layer MLP... trained to learn multiplication in the algebra of complex numbers
Finite-Dimensional Algebra → connectedto → Matrix Factorization
confidence 90% · For algebras over the reals, we connect the learning problem to matrix factorization with an implicit low-rank bias
Associativity → influences → Grokking
confidence 90% · how do algebraic properties such as commutativity, associativity, and unitality influence both the emergence and timing of grokking
Commutativity → influences → Grokking
confidence 90% · how do algebraic properties such as commutativity, associativity, and unitality influence both the emergence and timing of grokking
Unitality → influences → Grokking
confidence 90% · how do algebraic properties such as commutativity, associativity, and unitality influence both the emergence and timing of grokking
Cypher Suggestions (0)
No Cypher suggestions yet.
Abstract
Abstract:This paper investigates the grokking phenomenon, which refers to the sudden transition from a long memorization to generalization observed during neural networks training, in the context of learning multiplication in finite-dimensional algebras (FDA). While prior work on grokking has focused mainly on group operations, we extend the analysis to more general algebraic structures, including non-associative, non-commutative, and non-unital algebras. We show that learning group operations is a special case of learning FDA, and that learning multiplication in FDA amounts to learning a bilinear product specified by the algebra's structure tensor. For algebras over the reals, we connect the learning problem to matrix factorization with an implicit low-rank bias, and for algebras over finite fields, we show that grokking emerges naturally as models must learn discrete representations of algebraic elements. This leads us to experimentally investigate the following core questions: (i) how do algebraic properties such as commutativity, associativity, and unitality influence both the emergence and timing of grokking, (ii) how structural properties of the structure tensor of the FDA, such as sparsity and rank, influence generalization, and (iii) to what extent generalization correlates with the model learning latent embeddings aligned with the algebra's representation. Our work provides a unified framework for grokking across algebraic structures and new insights into how mathematical structure governs neural network generalization dynamics.
Tags
Links
- Source: https://arxiv.org/abs/2602.19533v2
- Canonical: https://arxiv.org/abs/2602.19533v2
Trouble viewing inline? Open PDF directly →
Full Text
235,686 characters extracted from source content.
Expand or collapse full text
Grokking Finite-Dimensional Algebra Pascal Jr Tikeng Notsawo Guillaume Dumas Guillaume Rabusseau Abstract This paper investigates the grokking phenomenon, which refers to the sudden transition from a long memorization to generalization observed during neural networks training, in the context of learning multiplication in finite-dimensional algebras (FDA). While prior work on grokking has focused mainly on group operations, we extend the analysis to more general algebraic structures, including non-associative, non-commutative, and non-unital algebras. We show that learning group operations is a special case of learning FDA, and that learning multiplication in FDA amounts to learning a bilinear product specified by the algebra’s structure tensor. For algebras over the reals, we connect the learning problem to matrix factorization with an implicit low-rank bias, and for algebras over finite fields, we show that grokking emerges naturally as models must learn discrete representations of algebraic elements. This leads us to experimentally investigate the following core questions: (i) how do algebraic properties such as commutativity, associativity, and unitality influence both the emergence and timing of grokking, (i) how structural properties of the structure tensor of the FDA, such as sparsity and rank, influence generalization, and (i) to what extent generalization correlates with the model learning latent embeddings aligned with the algebra’s representation. Our work provides a unified framework for grokking across algebraic structures and new insights into how mathematical structure governs neural network generalization dynamics. Machine Learning, ICML 1 Introduction Figure 1: (a) Grokking (non-trivial Δtgen=t4−t2 t_gen=t_4-t_2) on a 2-layer MLP with ReLUReLU activation trained to learn multiplication in the algebra of complex numbers over the field 7=ℤ/7ℤF_7=Z/7Z, where (a+b)(c+d)=ac+bd2+(ad+bc)(a+bi)(c+di)=ac+bdi^2+(ad+bc)i and 2=−1≡6 mod 7i^2=-1≡ 6 mod 7. (b) Histogram of grokking delay Δtgen t_gen under single modifications of the multiplication rules of complex numbers in 7F_7, where each perturbation consists in changing the outcome of one multiplication relation (e.g., replacing 2=−1i^2=-1 with 2=1i^2=1). One of the primary objectives of machine learning is generalization, which refers to the ability of models to perform well on data they have not encountered during training. Even if these models perform exceptionally well in different domains today, the underlying reason for their good generalization ability remains an open question. By introducing the grokking phenomenon, Power et al. (2022) recently provides a new lens to view the generalization capabilities of overparametrized neural networks, challenging previous notions that such networks merely memorize training data. The grokking phenomenon has been studied mainly on algorithmic tasks, which consist of predicting z=x∘yz=x y given (x,y)∈2(x,y) ^2, with ∘ a binary mathematical operator and S a finite set of discrete symbols with no internal structure; for instance, finite cyclic groups of order 11 with its binary operation ∘ (such as addition in =ℤ/pℤS=Z/pZ for some prime integer p). In such settings, it is now established that models like Transformers generalize by recovering the representation of the group itself (Gromov, 2023; Nanda et al., 2023; Chughtai et al., 2023; Stander et al., 2024). In this work, we investigate how grokking extends beyond these well-understood settings in terms of algebraic complexity, i.e, moving from groups to more general algebras. Our goal is to understand how specific algebraic or structural properties of the task influence the emergence and timing of the grokking phenomenon. Motivations While group operations provide a basic structure, algebras encompass a richer and more complex set of operations, including non-unital, non-commutative, and non-associative behaviors. For example, many systems (in physics, robotics, control, etc) evolve according to infinitesimal transformations whose interaction is governed by a Lie bracket [⋅,⋅][·,·], a bilinear, non-commutative, non-associative, and non-unital operation. Predicting such infinitesimal updates corresponds to learning a FDA. In drug discovery, predicting how molecules interact with biological targets is crucial for identifying potential drug candidates. This involves understanding the complex relationships and transformations between different molecular structures. An example of a task is chemical reaction prediction (Fooshee et al., 2018), where given two molecules x and y, the task is to predict the product xyxy when these molecules undergo a chemical reaction (and the reaction pathway). If a third molecule z is involved, the reaction sequence (xy)z(xy)z might yield a different product than x(yz)x(yz). Also, chemical reactions often involve complex mechanisms that cannot be simply reversed or do not have a natural identity element (a molecule that would leave another unchanged in a reaction). In natural language processing, understanding how the meanings of smaller units (words or phrases) combine to form the meanings of larger units (sentences or documents) is a fundamental challenge. This process is inherently compositional, similar to operations in an algebraic structure where the operation combines elements to produce another element within the same set, and for which the order in which the elements are taken is very important. Consider the semantic composition and decomposition tasks (Turney, 2014) as a concrete example. The first task involves understanding the meaning of a text by composing the meanings of the individual words in this text, and the second involves understanding the meaning of an individual word by decomposing it into various aspects that are latent in the word’s meaning. For example, given a noun-modifier bigram ‘x y’, with ‘x’ the head noun and ‘y’ the noun or adjective, the semantic composition task can be to find a noun unigram ‘z’ in the vocabulary which is a synonym of ‘x y’. Conversely, the semantic decomposition can be to find a bigram ‘x y’ synonym to a given ‘z’ from the vocabulary. Examples of (x y, z) are (presidential term, presidency), (electrical power, wattage), (milk sugar, lactose), (bass fiddle, contrabass), etc. This kind of problem is often solved by optimizing argmaxg(f(,),) *arg\,max_zg(f(x,y),z), where x, y and z are vectors representing the words ‘x’, ‘y’ and ‘z’; f a function representing ‘x y’ from x and y; and g a measure of similarity. Using a symmetric f is common, such as f(,)=+f(x,y)=x+y, but they are order independent and gives the same representation to ‘x y’ and ‘y x’, so that, for example, “good morning” == “morning good” under f. Landauer (2002) estimates that 80%80\% of the meaning of English text comes from word choice, and the remaining 20%20\% comes from word order. Therefore, methods like vector addition, which do not account for word order, potentially overlook at least 20%20\% of the meaning in a bigram (Turney, 2014). So, the order of words affects the meaning; “good morning” conveys a different sentiment and usage than “morning good”. For associativity, when combining more than two words, the order in which they are combined can affect the resulting meaning. For example, combining words in the phrase “old country house” can yield different interpretations based on which words are combined first. Contributions Our contributions are fourfold: • Leveraging the fact that any tensor ∈n×n×n C ^n× n× n defines an n-dimensional algebra over a field F (nnF-FDA), with associativity, commutativity, and unitality encoded as tensor identities, and matrix representations characterized by explicit tensor constraints; we establishe the equivalence between n×n×nF^n× n× n and all nnF-FDA, allowing us to focus on structure tensors rather than abstract algebras. • We show that prior work on grokking in groups (e.g., (Nanda et al., 2023), (Chughtai et al., 2023)) is a special case of our tensorial framework, which naturally extends to non-associative, non-commutative, and non-unital algebras. • We connect FDA learning over ℝR to matrix factorization, while over finite fields grokking emerges when models learn explicit embeddings of FDA elements. • We provide the first systematic study of grokking beyond groups, showing that algebraic constraints (associativity, commutativity, unitality) and structural features of the structure tensor (sparsity, rank) significantly affect grokking delay and sample complexity, and that generalization coincides with the emergence of algebra-consistent representations in model layers111The code to reproduce all figures is available at https://github.com/Tikquuss/grokking_fda.. Related Work On finite groups like ℤ/pℤZ/pZ and SnS_n, it has been shown that models like Transformers grok by recovering the representation of the group itself (Gromov, 2023; Nanda et al., 2023; Chughtai et al., 2023; Stander et al., 2024). On the algorithmic task (Power et al., 2022), Liu et al. (2022) shows representation learning to be the main underlying factor of the existence of generalizing solutions for modular arithmetic, supporting Power et al. (2022)’s preliminary observations. Gromov (2023) write out the exact-form expression of the weights of a 2-layer MLP (with activation function x↦x2x x^2) that yield 100%100\% accuracy on modular addition. Nanda et al. (2023) write out the closed-form solution of final trained weights in the case of a one-layer transformer trained on the same task, which is also made of sinusoids as in (Gromov, 2023). Chughtai et al. (2023) reverse engineer (small) neural networks learning finite group composition via mathematical representation theory. Stander et al. (2024) do the same, with the focus on composition in the symmetric group S5S_5. To the best of our knowledge, we are the first to study grokking in the general setting of FDAs. Prior work on grokking studies algorithmic tasks almost exclusively through group operations. These structures enforce a rigid bundle of properties (associativity, unitality, etc), making it impossible to isolate which algebraic traits influence grokking and whether these properties generalize beyond groups. Our FDA framework provides the first setting in which all previously studied group tasks embed naturally, and non-unital and non-associative operations become accessible. Our experiments show, for instance, that associativity, commutativity, and unitality each induce distinct grokking delays and generalization patterns, and that these patterns persist across all the algebras sampled from each regime. Structure of the document Section 2 introduces the structure-tensor view of FDA, characterizes algebraic properties as tensor identities, and provides a criterion for matrix representations. Section 3 shows how the framework subsumes groups, and Section 4 presents the learning formulation together with its theoretical motivation. Experimental results and discussion are given in Section 5 and Section 6, respectively, before concluding in Section 7. Notations For n∈ℕ∗n ^*, [n]:=1,…,n[n]:=\1,…,n\. For ∈ℝm×nA ^m× n, vec()∈ℝmnvec(A) ^mn denotes the vector obtained by stacking the columns of A. The iith row and column of A are denoted by i,:A_i,: (or iA_i) and :,iA_:,i, respectively. This notation extends naturally to tensor slices. We denote by ⊙ the Hadamard product, ⊗ the Kronecker product, ⋆ the Khatri–Rao product, ∙ the face-splitting product, and ×n×_n the mode-n tensor–vector product (Kolda & Bader, 2009). 2 Finite Dimensional Algebra In this section, we work with standard notions from FDA and adopt a concrete tensorial viewpoint. Fixing a basis, any n-dimensional algebra is identified with a structure tensor ∈n×n×n C ^n× n× n. This formulation provides a unified and operational description of algebraic structure that is directly compatible with our setting. In particular, it allows us to treat C as a concrete object that can be compared with learned representations, forming the basis for the alignment perspective developed later in the paper. 2.1 Definitions An algebra A over a field (,+,∗)(F,+,*) is a vector space equipped with a F-bilinear product ⋅:×→·: A× A→ A such that (+)⋅=⋅+⋅(u+v)·w=u·w+v·w (right distributivity), ⋅(+)=⋅+⋅w·(u+v)=w·u+w·v (left distributivity) and (α)⋅(β)=(α∗β)(⋅)( )·( )=(α*β)(u·v) (compatibility with scalars) for all ,,∈u,v,w∈ A and α,β∈α,β . When ⋅· is associative (resp. commutative), A is said to be associative (resp. commutative). When there exists an element 1∈1_ A∈ A such that 1⋅=⋅1=∀∈1_ A·u=u· 1_ A=u\ ∈ A, A is said to be unital. The dimension of A is its dimension as a F-vector space, denoted by dimdim_F A. We say that A is finite-dimensional if n=dimn=dim_F A is finite. This means that there exists a finite basis (i)i∈[n]\a^(i)\_i∈[n] of A (as a vector space over F) such that for every ∈u∈ A, =∑i=1nαi(i)u= _i=1^n _ia^(i) with αi∈ _i . Let (,⋅)( A,·) and (,×)( B,×) be two F-algebras. A homomorphism of F-algebras ϕ:→φ: A→ B is a F-linear map satisfying ϕ(⋅)=ϕ()×ϕ()φ(u·v)=φ(u)×φ(v) for all ,∈u,v∈ A; and ϕ(1)=1φ(1_ A)=1_ B when A and B are unitals. This homomorphism ϕφ is called an isomorphism if it is bijective. Two F-algebras A and B are isomorphic if there exists an algebra isomorphism ϕ:→φ: A→ B between them. In other words, A and B may look different at the level of their elements or chosen bases, but they share exactly the same algebraic structure. In the following, F-FDA means FDA over the field F, and nnF-FDA means F-FDA of dimension n. 2.2 Structure Constants of FDA Let (,⋅)( A,·) be an nnF-FDA and B=(i)i∈[n]B=\a^(i)\_i∈[n] a basis of A. The structure of A in B is entirely captured by the tensor (B)∈n×n×n C^(B) ^n× n× n defined by (i)⋅(j)=∑k=1nijk(B)(k)a^(i)·a^(j)= _k=1^n C_ijk^(B)a^(k). The entries of (B) C^(B) are called structure coefficients/constants of A in B. We will call the tensor (B) C^(B) the structure tensor of A in the basis B, and when the context is clear, we will omit B from the notation. That said, we have for all =∑i=1ni(i)u= _i=1^nu_ia^(i) and =∑i=1ni(i)v= _i=1^nv_ia^(i) in A, ⋅=∑k=1n(×1×2)k(k)u·v= _k=1^n ( C×_1u×_2v )_ka^(k) with ×1×2:=[⊤:,:,k]k∈[n]⊤=(3)(⊗) C×_1u×_2v:= [u C_:,:,kv ]_k∈[n] = C_(3) (v ) (1) In this equation, (3)∈n×n2 C_(3) ^n× n^2 is the mode-3 unfolding of C: ((3))k,:=vec(:,:,k)∈n2∀k∈[n] ( C_(3) )_k,:=vec( C_:,:,k) ^n^2\ ∀ k∈[n]. Example 2.1. The complex numbers ℂ=(ℝ2,⋅)C= (R^2,· ) can be seen as a 2ℝ2R-FDA, with the product ⋅· defined as (a+b)⋅(c+d)=(ac−bd)+(ad+bc)(a+bi)·(c+di)=(ac-bd)+(ad+bc)i, where 2=−1i^2=-1. The structure tensor of ℂC in ((1),(2))≡(1,)(a^(1),a^(2))≡(1,i) is [111112121122],[211212221222]=[1001],[01−10] bmatrix C_111& C_112\\ C_121& C_122\\ bmatrix, bmatrix C_211& C_212\\ C_221& C_222\\ bmatrix= bmatrix1&0\\ 0&1\\ bmatrix, bmatrix0&1\\ -1&0\\ bmatrix (2) In the field =p:=ℤ/pℤF=F_p:=Z/pZ for p prime (or power of prime), we have 2=(−1)modp=p−1i^2=(-1) p=p-1 instead, so 221=p−1 C_221=p-1 (the other coefficients remain unchanged). One may ask whether every tensor ∈n×n×n C ^n× n× n defines an nnF-FDA. If this holds, then one could in principle sample the entries of C over F and study the resulting algebra through the properties of its structure tensor. The following proposition shows that analyzing the space n×n×nF^n× n× n is equivalent to studying all nnF-FDA. What remains open, however, is how to sample C in a principled way so as to obtain meaningful and general insights about the phenomena of interest. We return to this issue in Section 4. Proposition 2.1. For all ∈n×n×n C ^n× n× n, there exists an nnF-FDA whose structure tensor is C in some basis. Moreover, all algebras that have C as a structure tensor in one of their bases are isomorphic to each other. The proof of this proposition is constructive. We define on the vector space nF^n the bilinear map ×=×1×2u×v= C×_1u×_2v, and show that (n,×)(F^n,×) is an nnF-FDA with structure tensor C in the canonical basis (i)i∈[n]\e^(i)\_i∈[n], j(i)=δije^(i)_j= _ij (Lemma B.1). We call this algebra the algebra generated by C, and denote it []F[ C]. We then show that []F[ C] is isomorphic to any nnF-FDA whose structure tensor is C in some basis (Lemma B.2). Although any ∈n×n×n C ^n× n× n defines an nnF-FDA, a key question is how the algebraic properties of (,⋅)( A,·) are reflected in C. The following proposition makes this connection explicit by characterizing associativity, commutativity, and unitality in terms of tensor equations. Proposition 2.2. An nnF-FDA (,⋅)( A,·) with structure tensor ∈n×n×n C ^n× n× n in the basis B=(i)i∈[n]B=\a^(i)\_i∈[n] is (i) associative if and only if ∑k=1nijkklm=∑k=1nikmjlk∀i,j,l,m∈[n] _k=1^n C_ijk C_klm= _k=1^n C_ikm C_jlk\ ∀ i,j,l,m∈[n]; (i) commutative if and only if C is symmetric in its first two modes, i.e. ijk=jik∀i,j,k∈[n] C_ijk= C_jik\ ∀ i,j,k∈[n]; (i) unital if and only if there exists λ∈nλ ^n such that ∑i=1nλii,:,:=∑i=1nλi:,i,:=n _i=1^n _i C_i,:,:= _i=1^n _i C_:,i,:=I_n. In that case, λ is unique and 1=∑i=1nλi(i)1_ A= _i=1^n _ia^(i). Proof. See Proposition B.5.∎ 2.3 Representations of FDA For m∈ℕ∗m ^*, let ℳm()M_m(F) denote the set of all m×m× m matrices over F, which is an m2m^2F-FDA under standard matrix multiplication. A representation of dimension m of a F-algebra (,⋅)( A,·) involves a homomorphism ρ:→ℳm()ρ: A _m(F) such that ρ(α+β)=αρ()+βρ()ρ( + )=αρ(u)+βρ(v) and ρ(⋅)=ρ()ρ()ρ(u·v)=ρ(u)ρ(v) for all ,∈u,v∈ A and α,β∈α,β . If A is unital, it is further required that ρ(1)=mρ(1_ A)=I_m. The following proposition characterizes when such a representation exists in terms of the structure tensor. Proposition 2.3. Let (,⋅)( A,·) be an nnF-FDA with structure tensor ∈n×n×n C ^n× n× n in B=(i)i∈[n]B=\a^(i)\_i∈[n]. Fix m∈ℕ∗m ^* and ∈n×m×m R ^n× m× m. Set k=k,:,:∈m×m R_k= R_k,:,: ^m× m for all k∈[n]k∈[n]. The linear map ρ:→ℳm()ρ: A _m(F) defined by ρ(∑k=1nαk(k)):=∑k=1nαkk∀α∈nρ ( _k=1^n _ka^(k) ):= _k=1^n _k R_k\ ∀α ^n is a representation of A if and only if ij=∑kijkk∀i,j∈[n] array[]l R_i R_j= _k C_ijk R_k ∀ i,j∈[n] array (3) and, if A is unital with 1=∑iλi(i)1_ A= _i _ia^(i), ∑iλii=m _i _i R_i=I_m. Proof. See Proposition B.16. ∎ Example 2.2. With the algebra of complex numbers in =ℝF=R, the defining relations for ((1),(2))=(1,)(a^(1),a^(2))=(1,i) are 12=1,12=21=2,22=−1 R_1^2= R_1,\ R_1 R_2= R_2 R_1= R_2,\ R_2^2=- R_1; together with 1=m since 1=(1) R_1=I_m since 1_ A=a^(1). Hence 22=−m R_2^2=-I_m, which forces m to be even. Writing m=2km=2k, the general solution is 2=(k⊗2⊤)−1∀∈GLm(ℝ) R_2=S(I_k C_2 )S^-1\ _m(R), with GLm(ℝ)GL_m(R) the general linear group, and 2⊤=[[0−1],[10]] C_2 = bmatrix bmatrix0&-1 bmatrix, bmatrix1&0 bmatrix bmatrix (the standard real representation of multiplication by i). In pF_p, 22=−m R_2^2=-I_m becomes 22=(p−1)m R_2^2=(p-1)I_m. There is no parity restriction on m, and a convenient normal form is 2=(p−1)1/2diag(ϵ)−1∀∈GLm(ℝ),ϵ∈±1m R_2=(p-1)^1/2Sdiag ( ε )S^-1\ _m(R), ε∈\± 1\^m. It is worth asking, for a given ∈n×n×n C ^n× n× n, what is the smallest m (or the values of m) for which the system of equations (3) admits a non-trivial solution. This question amounts to determining the minimal dimension of a faithful representation of A, which is a classical but non-trivial problem in representation theory. For associatives nnF-FDA, this smallest m is less than or equal to n (Proposition B.18). Since our goal in Section 5 is to investigate whether neural networks trained on data from =[] A=F[ C] implicitly learn such representations, we do not attempt to solve the minimality problem here. Instead, we will assume a sufficiently large m so that the system can be solvable and concentrate on analyzing how the learned embedding dimension relates to the properties of A and its structure tensor. 3 From Groups to FDA We show in this section that group learning is a special case of FDA learning. In fact, the study of grokking in groups naturally extends to algebras through their structure tensors. To see this, consider a finite group (G,∘)(G, ) with n elements gii∈[n]\g_i\_i∈[n]. One can construct the Cayley table of the group as a matrix ∈Gn×nA∈ G^n× n, where each entry is given by ij=gi∘gj,∀i,j∈[n]A_ij=g_i g_j,\ ∀ i,j∈[n]. This table contains n2n^2 operations, which are then randomly partitioned into two disjoint non-empty subsets, a training set and a test set (Power et al., 2022). More precisely, the model is trained to predict Ψ(gi∘gj) (g_i g_j) given Ψ(gi) (g_i) and Ψ(gj) (g_j), with Ψ:G→0,1n :G→\0,1\^n the one-hot encoding defined on G, Ψ(gi):=[(gk=gi)]k∈[n]∈0,1n∀i∈[n] (g_i):= [1(g_k=g_i) ]_k∈[n]∈\0,1\^n\ ∀ i∈[n], 1 the indicator function. Now, for a field F, define the set [G]:=∑i=1nαi(i)∣α∈nF[G]:= \ _i=1^n _ia^(i)\ \ α ^n \, where (i)=Ψ(gi)∈0,1n∀i∈[n]a^(i)= (g_i)∈\0_F,1_F\^n\ ∀ i∈[n]. For all =∑i(i)u= _iu_ia^(i) and =∑j(j)v= _jv_ja^(j) in [G]F[G], let ⋅:=∑i,jijΨ(gi∘gj)=∑k(∑i,jij(gi∘gj=gk))(k)u·v:= _i,ju_iv_j (g_i g_j )= _k ( _i,ju_iv_j1(g_i g_j=g_k) )a^(k). The following proposition shows that ([G],⋅)(F[G],·) is an nnF-FDA, and that training a model on the group (G,∘)(G, ) is equivalent to training it on the multiplication in ([G],⋅)(F[G],·). In fact, applying the encoding Ψ to each entry of the Cayley table A of G directly yields the structure tensor C of ([G],⋅)(F[G],·) in B=(i)i∈[n]B=\a^(i)\_i∈[n]. Therefore, any framework developed for algebras already subsumes the case of groups. In particular, by investigating grokking in algebras, we not only extend the scope of previous studies but also recover them as a special case. Proposition 3.1. For a finite group (G,∘)(G, ) with n elements gii∈[n]\g_i\_i∈[n] and identity e, ([G],⋅)(F[G],·) is an n-dimensional associative and unital F-FDA with 1[G]=Ψ(e)1_F[G]= (e). Also, ([G],⋅)(F[G],·) is commutative if and only if G is commutative. Moreover, the structure tensor of [G]F[G] in B=Ψ(gi)i∈[n]B=\ (g_i)\_i∈[n] is given by ijk=(gi∘gj=gk)∀i,j,k∈[n] C_ijk=1_F(g_i g_j=g_k)\ ∀ i,j,k∈[n]; and we have Ψ(gi∘gj)=×1Ψ(gi)×2Ψ(gj)∀i,j∈[n] (g_i g_j)= C×_1 (g_i)×_2 (g_j)\ ∀ i,j∈[n]. Proof. See Proposition B.10. ∎ 4 Learning Finite Dimensional Algebra In this section, we study supervised learning of multiplication in a finite-dimensional algebra (FDA). We show in the previous section that any n-dimensional FDA A over a field F with structure tensor ∗∈n×n×n C^* ^n× n× n is isomorphic to nF^n endowed with the bilinear product (,)↦∗×1×2∈n(u,v) C^*×_1u×_2v ^n (Proposition 2.1). Given inputs =(,)∈n×nx=(u,v) ^n×F^n, the supervised target is ∗()=∗×1×2y^*(x)= C^*×_1u×_2v. The structure of ∗ C^* (e.g., rank, sparsity pattern) is inherited from A and can shape both sample complexity and the dynamics of generalization. We propose to investigate how these properties impact generalization and the underlying mechanism by which they do so. 4.1 Grokking Regimes in FDAs Liu et al. (2023) argue that grokking arises when task performance hinges on learning a useful representation. For algorithmic data (Power et al., 2022), representation quality typically determines all-or-nothing accuracy (random guess vs. 100%100\%), while on natural data (e.g., MNIST) representation quality may separate 95%95\% from 100%100\% accuracy. In our setting, this viewpoint yields a concrete mechanism: for a finite-field FDA (=p=ℤ/pℤF=F_p=Z/pZ, p prime), treat A as a vocabulary, index each element ∈u∈ A by ⟨⟩∈[q] ∈[q] with q=||q=| A|, and learn an embedding matrix ∈ℝq×dE ^q× d so that ⟨⟩E_ is the trainable vector attached to u. Grokking corresponds to the point at which E and the downstream layers collectively represent the algebra, so a simple linear readout recovers the correct output token. By contrast, for =ℝF=R, a model that operates directly on (,)∈n×n(u,v) ^n×F^n and parameterizes a (bi)linear map can often fit without a prolonged representation-formation phase; grokking (in the strict “delayed generalization after memorization” sense) typically requires being induced via, e.g., large-scale initialization with small weight decay (Liu et al., 2023; Lyu et al., 2024) or by strongly misaligning the Neural Tangent Kernel with the target (Kumar et al., 2024). Moreover, Levi et al. (2024) and Notsawo et al. (2025) document cases of “grokking without understanding”: a sharp decrease in the test error during training, driven by changes in the ℓ2 _2-norm of the model parameters, but that does not result in convergence to an optimal solution. From this analysis, we distinguish ℝR from pF_p. The present paper focuses on the finite-field setting, where representation learning is intrinsic and grokking phenomena are most salient (Figure 1). We include a concise treatment of the real case below, where learning reduces to a linear inverse problem where explicit or implicit low-rank bias governs recovery, and defer rank/coherence details to the supplement. 4.2 A Linear Inverse View for =ℝF=R Let ,,∈N×nU,V,Y ^N× n be such that for each s∈[N]s∈[N], s=∗×1s×2s=(3)∗(s⊗s)Y_s= C^*×_1U_s×_2V_s= C^*_(3)\! (V_s _s ). Stacking gives =(3)∗⊤Y=X C^* _(3) with design :=∙∈ℝN×n2X:=V ^N× n^2, where ∙ is the face-splitting product (s=s⊗sX_s=V_s _s). We recall that sY_s is the ssth row of Y treated as a column vector, same thing for sU_s and sV_s. Finding another structure tensor ∈n×n×n C ^n× n× n such that s=×1s×2s∀s∈[N]Y_s= C×_1U_s×_2V_s\ ∀ s∈[N] is equivalent to solving the following linear equation in C; (3)⊤==(3)∗⊤⟺=vec()=∗X C _(3)=Y=X C^* _(3) =vec(Y)=Mb^* (4) with :=n⊗∈Nn×n3M:=I_n ^Nn× n^3 and :=vec((3)⊤)∈n3b:=vec( C _(3)) ^n^3, similarly for ∗b^*. This problem can be viewed as a matrix factorization problem with matrix (3)∗⊤∈n2×n C^* _(3) ^n^2× n and measurement (,)(U,V), or a compressed sensing problem with signal ∗b^* and measurement M. Thus, learning ∗ C^* from (,,)(U,V,Y) is a linear inverse problem whose identifiability and sample complexity are governed by the conditioning of =∙X=V vis-à-vis the signal (3)∗ C^*_(3), and the effective low-rank structure of (3)∗ C^*_(3). A convenient parameterization is a linear network (3)⊤=(L)⋯(1) C _(3)=W^(L)·sW^(1) with (L)∈ℝn2×dW^(L) ^n^2× d, (i)∈ℝd×dW^(i) ^d× d (1<i<L1<i<L), and (1)∈ℝd×nW^(1) ^d× n. For L=1L=1, explicit low-rank regularization (e.g., nuclear norm) or appropriate sparsity penalties may be necessary when N is sufficiently large (Candès & Tao, 2010; Notsawo et al., 2025). For L≥2L≥ 2, gradient descent exhibits an implicit bias toward low-rank solutions, enabling accurate recovery without explicit regularization in many regimes (Gunasekar et al., 2017; Arora et al., 2018, 2019; Gidel et al., 2019; Gissin et al., 2019; Razin & Cohen, 2020; Li et al., 2020). Beyond rank, recovery depends on coherence of the left/right singular subspaces of (3)∗⊤ C^* _(3) with the measurement matrix X (Candès & Tao, 2010; Candes & Recht, 2012; Chen et al., 2014). We summarize these implications for Equation (4) in Section C.1. While Equation (4) makes it straightforward to study recovery as a function of properties of ∗ C^*, the same is not true for the induced algebra ℝ[∗]=(ℝn,×)R[ C^*]=(R^n,×). Associativity, commutativity, and unitality correspond to polynomial constraints of measure zero in ℝn3R^n^3 (Proposition 2.2). Thus, a randomly sampled ∗ C^* almost surely defines a degenerate non-associative, non-commutative, non-unital product. This makes principled empirical study over ℝR difficult222This limitation is a property of the algebraic landscape over ℝR, not our tensorial framework, which simply makes it explicit. Structured (e.g., unital) nℝnR-FDA form a measure-zero subset among the set of all possible nℝnR-FDA. Thus, random sampling yields almost always degenerate algebras. and motivates our focus on finite fields, where structured algebras occur with non-negligible probability. 4.3 Finite Fields =ℤ/pℤF=Z/pZ Over =pF=F_p, algebraic properties have positive density. For moderate (n,p)(n,p), the space of possibilities (pn3p^n^3 tensors) is finite and can be systematically explored and stratified by properties such as associativity, commutativity, and unitality. Our experimental program is thus: (i) vary algebraic properties of p[∗]F_p[ C^*] and measure their effect on grokking delay and generalization; (i) study how structural features of ∗ C^* shape learning dynamics; and (i) probe whether models learn algebraic representations during training. 5 Experiments and Results 5.1 Experiment Setup From now on, we work over the finite field =pF=F_p (prime p). Identify ≡n A ^n and set q:=||=pnq:=| A|=p^n. Each element ∈u∈ A is treated as a vocabulary symbol with index ⟨⟩∈[q] ∈[q]. The models we use will associate to each of these symbols a trainable vector ⟨⟩∈ℝdE_ ^d, with ∈ℝV×dE ^V× d, V=q+2V=q+2 the vocabulary size, 22 for the special tokens =×,=S= \×, = \. We train the model using a classification approach. The logits for =(,×,,=)x=(u,×,v, =) with (,)∈2(u,v)∈ A^2 are given by yθ()=φ(ϕ(⟨⟩⊕⟨×⟩⊕⟨⟩⊕⟨=⟩))∈ℝqy_θ(x)= (φ (E_ _ × _ _ = ) ) ^q, where ⊕ is the vector concatenation, ϕφ the encoder and φ the classifier333The tokens × and = are not strictly necessary. Training the classifier on the simpler input pair (,)(u,v) yields qualitatively identical conclusions. We included for consistency with the formulation in (Power et al., 2022), but the results do not rely on them.. The dataset =((,×,,=),∗(,)∣(,)∈2D=\((u,×,v, =),y^*(u,v) (u,v)∈ A^2\ is randomly partitioned into two disjoint and non-empty sets trainD_train and testD_test, the training and the validation dataset respectively, following a ratio r:=|train|/||∈(0,1]r:=|D_train|/|D|∈(0,1], which allows us to interpolate between different data-availability regimes. The models are trained to minimize the average cross-entropy loss ℒtrain(θ)=∑(,∗)∈trainℓ(yθ(),⟨∗⟩)L_train(θ)= _(x,y^*) _train (y_θ(x), ^* ), with ℓ(,i)=−i+log(∑jexp(j))∀∈ℝq,i∈[q] (y,i )=-y_i+ ( _j (y_j ) )\ ^q,i∈[q]. We denoted by trainA_train the corresponding accuracy (ℒtestL_test and testA_test on testD_test). We use a linear classifier φ()=+∈ℝq (z)=b+Wz ^q. The learnable parameters θ consist of ,,E,W,b together with those of the encoder ϕφ. We consider three architectures for ϕφ: an MLP, an LSTM, and a Transformer (full details are provided in Appendix D). For clarity, we present mainly the MLP results and some Transformer results in the following section. Additional results, along with experimental details, are deferred to Appendix E. 5.2 Representation Learning Over a finite alphabet, the model must construct a representation in which all q2q^2 algebra products are linearly separable by the classifier head, q:=||q:=| A|. Early training can memorize subsets of products via brittle lookup-like features; only after the embedding geometry aligns with the algebraic structure does linear decoding succeed on the full combinatorial support, producing the characteristic delayed generalization of grokking (Liu et al., 2023). To see this, assume that (,×)( A,×) has a group structure and let ρ:→ℝm×mρ: A ^m× m be a faithful representation of A. If the model →ϕ()x φ(x) encodes a pair =(,)x=(u,v) as ϕ()=ρ(×)φ(x)=ρ(u×v) and the linear classifier head stores the inverses ρ()−1∀∈ρ(w)^-1\ ∈ A in its weights, then the decoding rule recovers the correct product ×u×v. In other words, under these assumptions, the model is able to generalize to all inputs. Proposition 5.1. Assume that (,×)( A,×) has a group structure, and let ρ:→ℝm×mρ: A ^m× m be a faithful matrix representation of A. Suppose a model yθ()=ϕ()∈ℝqy_θ(x)=Wφ(x) ^q encodes pairs =(,)∈2x=(u,v)∈ A^2 as ϕ(,)=ρ(×)φ(u,v)=ρ(u×v) and decodes with a linear classifier parameterized by weights ∈ℝq×m2W ^q× m^2 containing ρ()−1ρ(w)^-1 for each ∈w∈ A. Then the predicted label satisfies argmaxi∈[q]yθ()[i]=× *arg\,max_i∈[q]y_θ(x)[i]=u×v. As a consequence, the classifier linearly separates all q outputs. Proof. See Proposition D.1. ∎ Thus, the classifier achieves exact decoding of the group product for all pairs (,)∈2(u,v)∈ A^2 once the embedding geometry aligns with the group structure. Unfortunately, algebras do not have a group structure. However, in Proposition 2.3 we established a necessary and sufficient condition for verifying that a set of matrices represents an algebra, namely ij=∑kijk∗k∀i,j∈[n] R_i R_j= _k C^*_ijk R_k\ ∀ i,j∈[n]. By setting (i)=vec(i)∈m2∀i∈[n]r^(i)=vec( R_i) ^m^2\ ∀ i∈[n] and defining (i)⋅(j):=vec(ij)=∑kijk∗(k)∀i,j∈[n]r^(i)·r^(j):=vec( R_i R_j)= _k C^*_ijkr^(k)\ ∀ i,j∈[n] in :=∑i=1nαi(i)∣α∈n B:= \ _i=1^n _ir^(i) α ^n \, we obtain ⋅=∗×1×2∀,∈u·v=_ B C^*×_1u×_2v\ ,v∈ B, where ==_ B is the equality when expressed in basis. We performed linear probing to check whether such a structure emerges in the features learned by the models. (a) MLP (b) Transformer Figure 2: Representation quality and generalization performances as a function of training steps. Before grokking repA_rep remains relatively low and then sharply increases as the model groks. (a) MLP (b) Transformer Figure 3: Generalization accuracy as a function of representation quality for different training data size (r) and model layers (0 for first layer, 11 for the second, etc.) for a MLP and a Transformer Encoder: testA_test increases with repA_rep in a low-data regime. More precisely, let (ℓ)()∈ℝm2f^( )(u) ^m^2 and (r)()∈ℝm2f^(r)(u) ^m^2 denote the feature vectors produced by the model for ∈u∈ A when u appears on the left and on the right of an equation (i.e. when appearing as the left/right operand), respectively; and let ()∈ℝm2f(u) ^m^2 denote the feature vector of u produced by the unembedding layer (the classifier). We want to determine whether there exists ∈ℝm2×m2×m2 W ^m^2× m^2× m^2 such that (×)=^(,)f(u×v)= f_ W(u,v) for all ,∈u,v∈ A, where ^(,):=×1(ℓ)()×2(r)() f_ W(u,v):= W×_1f^( )(u)×_2f^(r)(v) is a bilinear model parameterized by W. We use the cosine similarity rep=1|2|∑(,)⟨(×),^(,)⟩/‖(×)‖‖^(,)‖A_rep= 1| A^2| _(u,v) (u×v), f_ W(u,v) /\|f(u×v)\|\,\| f_ W(u,v)\| associated with solving this problem (i.e., finding W) as a measure of how algebra-like structure emerges in the model’s feature space. The tensor W is obtained by minimizing a squared reconstruction error ∑(,)‖(×)−^(,)‖22 _(u,v) \|f(u×v)- f_ W(u,v) \|_2^2. This is solved using ordinary least squares with ℓ2 _2 regularization (more details in Sections D.2.2 and E of the Appendix). As shown in Figure 2, before grokking repA_rep remains relatively low and then sharply increases as the model groks. Figure 3 plots testA_test as a function of repA_rep across different model layers, training steps, and training dataset sizes. Each point is (rep(ℓ),test)(A_rep^( ),A_test) for a certain layer ℓ . We observe that testA_test increases with rep(ℓ)A_rep^( ) in a low-data regime, showing that the emergence of algebra-consistent features directly facilitates generalization when data are scarce. For Figures 2 and 3, the algebra being learned is the algebra of complex numbers over 7F_7. 5.3 The Properties of the FDA on Generalization We demonstrate in this section how algebraic structure (e.g., associativity) influences sample complexity, memorization time, and learning dynamics. For now on, we denote by t2t_2 (resp. t4t_4) the step at which the training (resp. test) accuracy first reaches ≈99%≈ 99\%. With the structure tensor ∗ C^* of complex numbers in =ℤ/7ℤF=Z/7Z (Example 2.1), we observed that the model exhibits grokking (Figure 1), but in a manner highly sensitive to the specific entries of ∗ C^*. A single random perturbation of one entry in ∗ C^* can dramatically reduce/increase the grokking delay (Figure 1). These observations suggest that the internal algebraic structure encoded by ∗ C^* exerts a direct influence on generalization. Using (n,p)=(2,7)(n,p)=(2,7), we generate ∗ C^* in pn×n×nF_p^n× n× n. We have pn3=78=5764801p^n^3=7^8=5764801 possibilities for such ∗ C^*. Let a=associativeassociative, c=commutativecommutative, u=unitalunital. We have the following 232^3 possible categories : acuacu, acu¯ac u, ac¯ua cu, a¯cu acu, ac¯u¯a c u, a¯cu¯ ac u, a¯c¯u a cu and a¯c¯u¯ a c u. The bar on top of the symbols¯ symbols represents negation, and the concatenation is the Boolean conjunction. For example, acu¯ac u represents the tensor algebras that are associative and commutative but non-unital. We obtain 996(0.017%)acu996\ (0.017\%)\ acu, 1741(0.03%)acu¯1741(0.03\%)\ ac u, 0(0.0%)ac¯u0\ (0.0\%)\ a cu, 0(0.0%)a¯cu0\ (0.0\%)\ acu, 96(0.002%)ac¯u¯96\ (0.002\%)\ a c u, 114912(1.99%)a¯cu¯114912\ (1.99\%)\ ac u, 0(0.0%)a¯c¯u0\ (0.0\%)\ a cu and 5647056(97.958%)a¯c¯u¯5647056\ (97.958\%)\ a c u. We sampled 1010 tensors in each case (category). We varied r=|train|/||r=|D_train|/|D| in 0.2,0.3,…,0.9\0.2,0.3,…,0.9\. For each triplet (category,∗,r)( category, C^*,r), we repeated the experiment twice. Figure 4: Evolution of the test accuracy testA_test during training for different training data fraction r∈0.2,0.3r∈\0.2,0.3\. Figure 5: Test loss ℒtestL_test and grokking step t4t_4 as a function of training data fraction r. Our results are summarized in Figures 4 (for the other values of r, see Figure 14) and 5. We varied r to show that algebra-dependent effects persist across regimes. Small r leads to memorization; intermediate r yields delayed generalization; and this delay decreases as r→1r→ 1. This matches known behavior on algorithmic tasks (Power et al., 2022; Notsawo Jr et al., 2023). We can observe that acu¯ac u algebras are consistently the easiest to learn (in terms of shorter grokking time and stronger generalization after grokking, measured in terms of test loss), followed by ac¯u¯a c u, with the remaining categories showing almost indistinguishable behavior. This shows that the combination of non-unitality and associativity most strongly facilitates generalization. This finding is consistent with the previous discussion on representation learning. When the algebra is associative but non-unital (ac¯u¯a c u and acu¯ac u), it admits two trivial representations444The probing from Section 5.2 on representation learning does not target any specific example of representation. It tests whether the model learns a representation that satisfies the constraints similar to those of Proposition 2.3, up to a linear transformation., the zero representation and left regular representation given by the tensor ∗ C^* itself, i=i∗⊤∀i∈[n] R_i= C^* _i∀ i∈[n] (Proposition B.18). Moreover, the representations constraints admit many solutions: if (i)i∈[n]( R_i)_i∈[n] is a representation of dimension m, then for any p≥mp≥ m and ∈p×mA ^p× m, ∈m×pB ^m× p with =mBA=I_m, (i)i∈[n](A R_iB)_i∈[n] is also a representation (Proposition B.19). These provide simpler and more accessible solutions for the learning process, effectively lowering the complexity of the optimization landscape. In other words, removing the unit constraint allows the model to exploit “shortcuts” in the representation space, which explains why non-unital associative algebras generalize more quickly and grok earlier. When the algebra is unital, the additional constraint ∑iλii=m _i _i R_i=I_m must be satisfied by its representations (Proposition 2.3). This requirement adds equations without adding degrees of freedom, drastically shrinking the feasible set and eliminating many representations, and this typically delays convergence. In fact, it significantly restricts the solution space, since it forces the representation to encode an identity element across all transformations, thereby reducing the flexibility of optimization and leading to slower convergence. In representation theory, such unit constraints are well known to eliminate many otherwise valid low-dimensional representations, leaving only more rigid (and more complex to approximate) ones. Among the two non-unital regimes (acu¯ac u and ac¯u¯a c u), commutativity makes acu¯ac u even easier from representation learning perspective because it reduces the number of equations in (3) from n2n^2 to n(n+1)/2n(n+1)/2, because ij=∑kijkk R_i R_j= _k C_ijk R_k and ji=∑kijkk R_j R_i= _k C_ijk R_k represent the same equation under commutativity, for all i,ji,j. Another way to see this is to observe that the models have the form y(,)=φ(ϕ(,))y(u,v)= (φ(u,v)), so that when ϕφ learns a representation ρ of the FDA, i.e. ϕ(,)=ρ(×)∀(,)φ(u,v)=ρ(u×v)\ ∀(u,v), then whenever ×=′×′u×v=u ×v we have identical predictions y(,)=y(′,′)y(u,v)=y(u ,v ). In a commutative FDA, ×=×u×v=v×u, so each product has two presentations (,)(u,v) and (,)(v,u). Once the classifier predicts one ordering correctly, it also predicts the swapped one, effectively reducing the number of distinct outputs it must separate. This symmetry makes acu¯ac u easier than ac¯u¯a c u and yields earlier transitions. 5.4 The Properties of the Structure Tensor on Generalization We focused in this section on the direct properties of ∗ C^* that influence generalization. Indeed, while the algebraic constraints on the entries of ∗ C^* required to ensure properties such as associativity are well understood, there are other structural characteristics of ∗ C^* whose connection to the underlying algebra remains unclear, especially over finite fields. Here, we examined two such properties: the sparsity s of ∗ C^* and the rank r(3)r^(3) of the mode-3 unfolding (3)∗ C^*_(3), motivated by our earlier discussion in the real-valued setting. Figure 6: Test loss and grokking step as a function of training data fraction r for different r(3)=rank((3)∗)r^(3)= *rank( C^*_(3)) and sparsity level s. Our experiments show that both the test loss and the time to generalize increase with r(3)r^(3) and s (Figure 6), indicating that higher complexity in these dimensions hinders efficient generalization. This is also true for other mode-unfolding (Figure 13). Note that the rank is basis-invariant (Corollary B.4) and reflects the intrinsic multilinear complexity of the operation, which we claim is why increasing rank leads to longer grokking delays. Sparsity, on the other hand, is not basis-invariant. It reflects a genuine “privileged basis” problem familiar in mechanistic interpretability (Olsson et al., 2022), as the neural network sees raw coordinates, and these coordinates implicitly privilege certain representations. Our experiments, therefore, treat sparsity as a task-dependent difficulty parameter, naturally associated with each algebraic example, in the canonical basis. Our empirical claim is therefore conditional on the canonical basis used. 6 Discussion and Limitations In the case of the Transformer Encoder (Figure 2), rep(ℓ)A_rep^( ) does not change with testA_test for layer ℓ=0 =0, the embedding layer. At first glance, this result contradicts previous work on group operations (Power et al., 2022; Liu et al., 2022), for which an emergence of structure is observed in the model’s embedding layer as it groks. We believe this difference is due to the embedding and unembedding layers being shared. More specifically, for layer 0, we seek W such that (×)=×1()×2()=(3)(()⊗())f(u×v)= W×_1f(u)×_2f(v)= W_(3) (f(v) (u) ) for all ,∈u,v∈ A, where f:→ℝm2f: A ^m^2 is the embedding layer. The fact that rep(0)A_rep^(0) remains almost constant simply shows that such a structure does not emerge in our case, without ruling out the possibility that another structure might emerge, such as the emergence of low-rank embeddings. We leave further investigation for future works. Figure 7: Generalization delay Δtgen t_gen as a function of training data fraction r∈(0,1)r∈(0,1) for ℳ2(3)M_2(F_3) and UT2(5)UT_2(F_5), the algebra of 2×22× 2 matrices (n=4n=4) over 3F_3 and th 2×22× 2 upper triangular matrices (n=3n=3) over 5F_5, respectively. Also, restricting most experiments to n=2n=2 over 7F_7 limits the scope of the empirical evaluation. The space of possible structure tensors grows rapidly, with |pn×n×n|=pn3|F_p^n× n× n|=p^n^3. As a result, exploring this space becomes computationally challenging even for moderate values of n and p. We therefore chose a reasonable (n,p)(n,p) to enable a controlled and systematic study of how algebraic properties affect generalization and grokking behavior. Figure 7 shows additional experiments with a non-trivial generalization delay on two associative, noncommutative, and unital (ac¯ua cu) algebras: the matrix algebras (which arise when n is a perfect square) and the upper triangular matrix algebra, which are not captured in the n=2n=2 setup. In fact, the minimum dimension n to get an ac¯ua cu algebra over any field F is 33 (Proposition B.7). Several directions remain open. Theoretically, a tighter link between tensor properties (e.g., rank, coherence) and sample complexity is needed over finite fields. Empirically, scaling to larger algebras and probing real-world tasks with latent algebraic structure could further clarify when and why grokking occurs. 7 Conclusion We introduced a tensorial framework for studying grokking in finite-dimensional algebras, showing that learning multiplication reduces to analyzing properties of structure tensors. This formulation recovers groups as a special case and extends grokking analysis to non-associative, non-commutative, and non-unital algebras. Our experiments demonstrate that algebraic constraints, such as unitality, do not always simplify learning and may even lengthen grokking delays, while structural properties, like sparsity or low rank, often accelerate generalization. We observe that test performance improves only once model layers align with the algebraic multiplication, reinforcing the view of grokking as a representational phase transition. These findings bridge classical algebra with modern learning theory: over real fields, FDA learning connects to low-rank matrix recovery, while over finite fields, grokking arises from the need to form internal representations. Acknowledgements We are grateful to David Kanaa for helpful conversations in the early stages of this work, and to Jonas Ngnawé for his feedback on the first draft of this paper. Pascal Tikeng sincerely acknowledges the support from the Canada Excellence Research Chairs (CERC) program, without which this work would not have been possible. Guillaume Rabusseau acknowledges the support of the CIFAR AI Chair program. Guillaume Dumas was supported by the Institute for Data Valorization, Montreal and the Canada First Research Excellence Fund (IVADO; CF00137433), the Fonds de Recherche du Quebec (FRQ; 285289), the Natural Sciences and Engineering Research Council of Canada (NSERC; DGECR-2023-00089), and the Canadian Institute for Health Research (CIHR 192031; SCALE). Impact Statement This paper aims to advance the field of Machine Learning by improving the understanding of grokking in neural networks. While the focus is on finite-dimensional algebra, our work has practical implications for optimizing model training. We acknowledge the potential ethical considerations of AI technologies, but do not feel any specific issues need to be highlighted here at this time. References Arora et al. (2018) Arora, S., Cohen, N., and Hazan, E. On the optimization of deep networks: Implicit acceleration by overparameterization, 2018. URL https://arxiv.org/abs/1802.06509. Arora et al. (2019) Arora, S., Cohen, N., Hu, W., and Luo, Y. Implicit regularization in deep matrix factorization. CoRR, abs/1905.13655, 2019. URL http://arxiv.org/abs/1905.13655. Candes & Recht (2012) Candes, E. and Recht, B. Exact matrix completion via convex optimization. Communications of the ACM, 55(6):111–119, 2012. Candès & Tao (2010) Candès, E. J. and Tao, T. The power of convex relaxation: Near-optimal matrix completion. IEEE transactions on information theory, 56(5):2053–2080, 2010. Chen et al. (2014) Chen, Y., Bhojanapalli, S., Sanghavi, S., and Ward, R. Coherent matrix completion. In Xing, E. P. and Jebara, T. (eds.), Proceedings of the 31st International Conference on Machine Learning, volume 32 of Proceedings of Machine Learning Research, p. 674–682, Bejing, China, 22–24 Jun 2014. PMLR. URL https://proceedings.mlr.press/v32/chenc14.html. Chughtai et al. (2023) Chughtai, B., Chan, L., and Nanda, N. A toy model of universality: Reverse engineering how networks learn group operations. In International Conference on Machine Learning, p. 6243–6267. PMLR, 2023. Fooshee et al. (2018) Fooshee, D., Mood, A., Gutman, E., Tavakoli, M., Urban, G., Liu, F., Huynh, N., Van Vranken, D., and Baldi, P. Deep learning for chemical reaction prediction. Mol. Syst. Des. Eng., 3:442–452, 2018. doi: 10.1039/C7ME00107J. URL http://dx.doi.org/10.1039/C7ME00107J. Gidel et al. (2019) Gidel, G., Bach, F. R., and Lacoste-Julien, S. Implicit regularization of discrete gradient dynamics in deep linear neural networks. CoRR, abs/1904.13262, 2019. URL http://arxiv.org/abs/1904.13262. Gissin et al. (2019) Gissin, D., Shalev-Shwartz, S., and Daniely, A. The implicit bias of depth: How incremental learning drives generalization. CoRR, abs/1909.12051, 2019. URL http://arxiv.org/abs/1909.12051. Gromov (2023) Gromov, A. Grokking modular arithmetic. arXiv preprint arXiv:2301.02679, 2023. Gunasekar et al. (2017) Gunasekar, S., Woodworth, B. E., Bhojanapalli, S., Neyshabur, B., and Srebro, N. Implicit regularization in matrix factorization. Advances in neural information processing systems, 30, 2017. Johnson & Lindenstrauss (1984) Johnson, W. B. and Lindenstrauss, J. Extensions of lipschitz mappings into hilbert space. Contemporary mathematics, 26:189–206, 1984. URL https://api.semanticscholar.org/CorpusID:117819162. Kolda & Bader (2009) Kolda, T. G. and Bader, B. W. Tensor decompositions and applications. SIAM review, 51(3):455–500, 2009. Kumar et al. (2024) Kumar, T., Bordelon, B., Gershman, S. J., and Pehlevan, C. Grokking as the transition from lazy to rich training dynamics. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=vt5mnLVIVo. Landauer (2002) Landauer, T. K. On the computational basis of learning and cognition: Arguments from lsa. In On the computational basis of learning and cognition: Arguments from LSA, volume 41 of Psychology of Learning and Motivation, p. 43–84. Academic Press, 2002. doi: https://doi.org/10.1016/S0079-7421(02)80004-4. URL https://w.sciencedirect.com/science/article/pii/S0079742102800044. Levi et al. (2024) Levi, N. I., Beck, A., and Bar-Sinai, Y. Grokking in linear estimators – a solvable model that groks without understanding. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=GH2LYb9XV0. Li et al. (2020) Li, Z., Luo, Y., and Lyu, K. Towards resolving the implicit bias of gradient descent for matrix factorization: Greedy low-rank learning. CoRR, abs/2012.09839, 2020. URL https://arxiv.org/abs/2012.09839. Liu et al. (2022) Liu, Z., Kitouni, O., Nolte, N., Michaud, E. J., Tegmark, M., and Williams, M. Towards understanding grokking: An effective theory of representation learning. In Oh, A. H., Agarwal, A., Belgrave, D., and Cho, K. (eds.), Advances in Neural Information Processing Systems, 2022. URL https://openreview.net/forum?id=6at6rB3IZm. Liu et al. (2023) Liu, Z., Michaud, E. J., and Tegmark, M. Omnigrok: Grokking beyond algorithmic data. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=zDiHoIWa0q1. Lyu et al. (2024) Lyu, K., Jin, J., Li, Z., Du, S. S., Lee, J. D., and Hu, W. Dichotomy of early and late phase implicit biases can provably induce grokking. In The Twelfth International Conference on Learning Representations, 2024. URL https://openreview.net/forum?id=XsHqr9dEGH. Nanda et al. (2023) Nanda, N., Chan, L., Lieberum, T., Smith, J., and Steinhardt, J. Progress measures for grokking via mechanistic interpretability. In The Eleventh International Conference on Learning Representations, 2023. URL https://openreview.net/forum?id=9XFSbDPmdW. Notsawo et al. (2025) Notsawo, P. J. T., Dumas, G., and Rabusseau, G. Grokking beyond the euclidean norm of model parameters. arXiv preprint arXiv:2506.05718, 2025. Notsawo Jr et al. (2023) Notsawo Jr, P., Zhou, H., Pezeshki, M., Rish, I., Dumas, G., et al. Predicting grokking long before it happens: A look into the loss landscape of models which grok. arXiv preprint arXiv:2306.13253, 2023. Olsson et al. (2022) Olsson, C., Elhage, N., Nanda, N., Joseph, N., DasSarma, N., Henighan, T., Mann, B., Askell, A., Bai, Y., Chen, A., Conerly, T., Drain, D., Ganguli, D., Hatfield-Dodds, Z., Hernandez, D., Johnston, S., Jones, A., Kernion, J., Lovitt, L., Ndousse, K., Amodei, D., Brown, T., Clark, J., Kaplan, J., McCandlish, S., and Olah, C. In-context learning and induction heads, 2022. URL https://arxiv.org/abs/2209.11895. Power et al. (2022) Power, A., Burda, Y., Edwards, H., Babuschkin, I., and Misra, V. Grokking: Generalization beyond overfitting on small algorithmic datasets. arXiv preprint arXiv:2201.02177, 2022. Razin & Cohen (2020) Razin, N. and Cohen, N. Implicit regularization in deep learning may not be explainable by norms. CoRR, abs/2005.06398, 2020. URL https://arxiv.org/abs/2005.06398. Stander et al. (2024) Stander, D., Yu, Q., Fan, H., and Biderman, S. Grokking group multiplication with cosets. In Forty-first International Conference on Machine Learning, 2024. URL https://openreview.net/forum?id=hcQfTsVnBo. Turney (2014) Turney, P. D. Semantic composition and decomposition: From recognition to generation. arXiv preprint arXiv:1405.7908, 2014. Abstract 1 Introduction 1 2 Finite Dimensional Algebra 2 2.1 Definitions 2.1 2.2 Structure Constants of FDA 2.2 2.3 Representations of FDA 2.3 3 From Groups to FDA 3 4 Learning Finite Dimensional Algebra 4 4.1 Grokking Regimes in FDAs 4.1 4.2 A Linear Inverse View for =ℝF=R 4.2 4.3 Finite Fields =ℤ/pℤF=Z/pZ 4.3 5 Experiments and Results 5 5.1 Experiment Setup 5.1 5.2 Representation Learning 5.2 5.3 The Properties of the FDA on Generalization 5.3 5.4 The Properties of the Structure Tensor on Generalization 5.4 6 Discussion and Limitations 6 7 Conclusion 7 A Notations and Useful Identities A B Finite-Dimensional Algebra (FDA) B B.1 Definitions B.1 B.2 Structure Constants of FDA B.2 B.3 Examples of FDA B.3 B.4 From Groups to FDA: A Unified View B.4 B.5 Representation of FDA B.5 C Learning Finite-Dimensional Algebra C C.1 A Linear Inverse View for =ℝF=R C.1 C.2 Finite Fields =ℤ/pℤF=Z/pZ and Representation-Centric Modeling C.2 D Experiment Setup D D.1 Task Description and Model Architecture D.1 D.2 Representation Learning D.2 E Experimentation Details and Additional Experiments E Appendix A Notations and Useful Identities We used the following standard notations. • For n∈ℕ∗n ^*, [n]:=1,…,n[n]:=\1,…,n\. For m,n∈ℕm,n with m≥nm≥ n, ⟦n,m⟧:=n,n+1,⋯,m n,m :=\n,n+1,·s,m\. • Scalars are denoted by lowercase letters, e.g., a; vectors are denoted by boldface lowercase letters, e.g., =[i]ia=[a_i]_i; matrices are denoted by boldface capital letters, e.g., =[i,j]i,jA=[A_i,j]_i,j; higher-order tensors (order three or higher) are denoted by boldface Euler script letters, e.g., =[i1,i2,i3,…]i1,i2,i3,… A=[ A_i_1,i_2,i_3,…]_i_1,i_2,i_3,…. • The ithi^th row (resp. column) of a matrix A will be denoted by i,:A_i,: or simply iA_i (resp. :,iA_:,i). This notation is extended to slices of a tensor straightforwardly. Commas in subscripts may occasionally be omitted whenever no ambiguity arises, e.g., =[ij]ijA=[A_ij]_ij and i:A_i:. Unless otherwise stated, indices of vectors, matrices, and tensors will start at 11. When 0-based indexing is used, it will be explicitly mentioned. • For a given dimension n∈ℕ∗n ^*, (k)∈ℝne^(k) ^n is the kthk^th vector of the canonical basis of ℝnR^n, l(k)=δkl∀l∈[n]e^(k)_l= _kl∀ l∈[n]. Here, δ is the Kronecker delta function. • For a vector ∈ℝnx ^n, ‖0=|i∈[n],i≠0|\|x\|_0=|\i∈[n],x_i≠ 0\|, ‖p=(∑i=1n|i|p)1p∀p∈(0,∞)\|x\|_p= ( _i=1^n|x_i|^p ) 1p∀ p∈(0,∞) and ‖∞=maxi∈[n]|i|\|x\|_∞= _i∈[n]|x_i|. • For a matrix ∈ℝm×nA ^m× n, the operator vec()∈ℝmnvec(A) ^mn stacks the column of A in a vector, i.e. (vec())(j−1)m+i=ij(vec(A))_(j-1)m+i=A_ij for all (i,j)∈[m]×[n](i,j)∈[m]×[n]. We have ‖F:=‖vec()‖2\|A\|_F:=\|vec(A)\|_2. • For the operations on vectors and matrices, we denote by ⊙ the Hadamard product, ⊗ the Kronecker product, ⋆ the Khatri-Rao product, ∙ the face-splitting product, and ∘ the outer product. For n vectors (i)∈ℝmi∀i∈[n]a^(i) ^m_i\ ∀ i∈[n], ((1)∘⋯∘(n))i1,⋯,in=i1(1)⋯in(n)∀(i1,⋯,in)∈[m1]×⋯×[mn] (a^(1) ·s ^(n) )_i_1,·s,i_n=a^(1)_i_1·sa^(n)_i_n\ ∀(i_1,·s,i_n)∈[m_1]×·s×[m_n]. Let ∈ℝd1×d2×d3 T ^d_1× d_2× d_3. • For a vector ∈ℝd1a ^d_1, the matrix =×1∈ℝd2×d3A= T×_1a ^d_2× d_3 is such that jk=∑i=1d1ijki=:,j,k⊤∀(j,k)∈[d2]×[d3]A_jk= _i=1^d_1 T_ijka_i= T_:,j,k a\ ∀(j,k)∈[d_2]×[d_3], that is =∑i=1d1ii,:,:A= _i=1^d_1a_i T_i,:,:. The matrices ×2∈ℝd1×d3 T×_2a ^d_1× d_3 and ×3∈ℝd1×d2 T×_3a ^d_1× d_2 are define similarly, for ∈ℝd2a ^d_2 and ∈ℝd3a ^d_3 respectively: ×2=∑j=1d2:,j,:j T×_2a= _j=1^d_2 T_:,j,:a_j and ×3=∑k=1d3:,:,kk T×_3a= _k=1^d_3 T_:,:,ka_k. So, for ∈ℝd1a ^d_1 and ∈ℝd2b ^d_2, the vector =×1×2=×2=⊤∈ℝd3c= T×_1a×_2b=A×_2b=A b ^d_3, with =×1∈ℝd2×d3A= T×_1a ^d_2× d_3, is such that k=⊤:,:,k=:,k⊤∀k∈[d3]c_k=a T_:,:,kb=A_:,k b\ ∀ k∈[d_3], i.e. =∑i=1d1∑j=1d2iji,j,:=∑j=1d2jj,:c= _i=1^d_1 _j=1^d_2a_ib_j T_i,j,:= _j=1^d_2b_jA_j,:. As a special case, identifying matrices with tensors in ℝd1×d2×1R^d_1× d_2× 1 gives ×1=⊤∈ℝd2×2=∈ℝd1∀∈ℝd1×d2,∈ℝd1,∈ℝd2 split \ array[]lA×_1a=A a ^d_2\\ A×_2b=Ab ^d_1 array . ^d_1× d_2,a ^d_1,b ^d_2 split (5) • For a matrix ∈ℝm×d1A ^m× d_1, the tensor =×1∈ℝm×d2×d3 A= T×_1A ^m× d_2× d_3 is such that ijk=∑l=1d1illjk∀(i,j,k)∈[m]×[d2]×[d3] A_ijk= _l=1^d_1A_il T_ljk\ ∀(i,j,k)∈[m]×[d_2]×[d_3]; or equivalently, i,:,:=∑l=1d1ill,:,:∈ℝd2×d3∀i∈[m] A_i,:,:= _l=1^d_1A_il T_l,:,: ^d_2× d_3\ ∀ i∈[m]. Similarly, for ∈ℝm×d2A ^m× d_2, =×2∈ℝd1×m×d3 A= T×_2A ^d_1× m× d_3 is such that ijk=∑l=1d2jlilk∀(i,j,k)∈[d1]×[m]×[d3] A_ijk= _l=1^d_2A_jl T_ilk\ ∀(i,j,k)∈[d_1]×[m]×[d_3]; or equivalently, :j:=∑l=1d2jl:,l,:∈ℝd1×d3∀j∈[m] A_:j:= _l=1^d_2A_jl T_:,l,: ^d_1× d_3\ ∀ j∈[m]; In the same way, for ∈ℝm×d3A ^m× d_3, the tensor =×3∈ℝd1×d2×m A= T×_3A ^d_1× d_2× m is such that ijk=∑l=1d3klijl∀(i,j,k)∈[d1]×[d2]×[m] A_ijk= _l=1^d_3A_kl T_ijl\ ∀(i,j,k)∈[d_1]×[d_2]×[m]; or equivalently, :,:,k=∑l=1d3kl:,:,l∈ℝd1×d2∀k∈[m] A_:,:,k= _l=1^d_3A_kl T_:,:,l ^d_1× d_2\ ∀ k∈[m]. So, for (ℓ)∈ℝmℓ×dℓ∀ℓ∈[3]A^( ) ^m_ × d_ \ ∀ ∈[3], the tensor =×1(1)×2(2)×3(3)∈ℝm1×m2×m3 A= T×_1A^(1)×_2A^(2)×_3A^(3) ^m_1× m_2× m_3 is such that ijk=∑l=1d1∑r=1d2∑s=1d3lrsil(1)jr(2)ks(3)∀i,j,k⟺=∑l=1d1∑r=1d2∑s=1d3lrs:,l(1)∘:,r(2)∘:s(3) A_ijk= _l=1^d_1 _r=1^d_2 _s=1^d_3 T_lrsA^(1)_ilA^(2)_jrA^(3)_ks∀ i,j,k A= _l=1^d_1 _r=1^d_2 _s=1^d_3 T_lrsA^(1)_:,l ^(2)_:,r ^(3)_:s (6) • We denoted by (1)∈ℝd1×d2d3 T_(1) ^d_1× d_2d_3, (2)∈ℝd2×d1d3 T_(2) ^d_2× d_1d_3 and (3)∈ℝd3×d1d2 T_(3) ^d_3× d_1d_2 the mode-1,2,3 unfolding of T, respectively. They are defined by ((1))i,(j−1)d3+k=((2))j,(k−1)d1+i=((3))k,(j−1)d1+i=ijk∀(i,j,k)∈[d1]×[d2]×[d3] ( T_(1) )_i,(j-1)d_3+k= ( T_(2) )_j,(k-1)d_1+i= ( T_(3) )_k,(j-1)d_1+i= T_ijk\ ∀(i,j,k)∈[d_1]×[d_2]×[d_3], or equivalently: (1)=[−vec(1,:,:⊤)−vec(2,:,:⊤)−⋯−vec(d1,:,:⊤)−](2)=[−vec(:,1,:)−vec(:,2,:)−⋯−vec(:,d2,:)−](3)=[−vec(:,:,1)−vec(:,:,2)−⋯−vec(:,:,d3)−] T_(1)= bmatrix-\ vec( T_1,:,: )\ -\\ -\ vec( T_2,:,: )\ -\\ -\ \ ·s -\\ -vec( T_d_1,:,: )- bmatrix T_(2)= bmatrix-\ vec( T_:,1,:)\ -\\ -\ vec( T_:,2,:)\ -\\ -\ \ ·s -\\ -vec( T_:,d_2,:)- bmatrix T_(3)= bmatrix-\ vec( T_:,:,1)\ -\\ -\ vec( T_:,:,2)\ -\\ -\ \ ·s -\\ -vec( T_:,:,d_3)- bmatrix (7) The following identities follow from these definitions using standard tensor and Kronecker-product manipulations. – For all ℓ∈[3] ∈[3], we have (ℓ)=(×ℓ)(ℓ)∀∈ℝm×dℓA T_( )=( T×_ A)_( )\ ^m× d_ (8) – We have (×2×3)(1)=(1)(⊗)⊤∈ℝd1×m2m3∀∈ℝm2×d2,∈ℝm3×d3(×1×3)(2)=(2)(⊗)⊤∈ℝd2×m1m3∀∈ℝm1×d1,∈ℝm3×d3(×1×2)(3)=(3)(⊗)⊤∈ℝd3×m1m2∀∈ℝm1×d1,∈ℝm2×d2 split&( T×_2A×_3B)_(1)= T_(1) (A ) ^d_1× m_2m_3\ ^m_2× d_2,B ^m_3× d_3\\ &( T×_1A×_3B)_(2)= T_(2) (B ) ^d_2× m_1m_3\ ^m_1× d_1,B ^m_3× d_3\\ &( T×_1A×_2B)_(3)= T_(3) (B ) ^d_3× m_1m_2\ ^m_1× d_1,B ^m_2× d_2 split (9) – For all ℓ∈[3] ∈[3], we have ×ℓ×ℓ= T×_ A×_ B= T for all ,∈ℝdℓ×dℓA,B ^d_ × d_ such that =dℓBA=I_d_ . – We have vec((×1)⊤)=(1)⊤∀∈ℝd1,vec(×2)=(2)⊤∀∈ℝd2vec(×3)=(3)⊤∀∈ℝd3 split&vec (( T×_1a) )= T_(1) a\ ^d_1,\\ &vec( T×_2a)= T_(2) a\ ^d_2\\ &vec( T×_3a)= T_(3) a\ ^d_3 split (10) – For ∈ℝd1a ^d_1 and ∈ℝd2b ^d_2, we have ×1×2=[⊤::k]k∈[n]⊤=[vec(⊤::k)]k∈[n]⊤=[(⊗)⊤vec(::k)]k∈[n]⊤=(3)(⊗) T×_1a×_2b= [a T_::kb ]_k∈[n] = [vec(a T_::kb) ]_k∈[n] = [ (b ) vec( T_::k) ]_k∈[n] = T_(3) (b ) (11) – If we CP-decompose T as =⟦,,⟧:=∑ℓ=1R:,ℓ∘:,ℓ∘:,ℓ T= ,B,C := _ =1^RA_:, _:, _:, with ∈ℝd1×RA ^d_1× R, ∈ℝd2×RB ^d_2× R and ∈ℝd3×RC ^d_3× R the three mode loading matrices, then (1)=(⋆)⊤ T_(1)=A(B ) , (2)=(⋆)⊤ T_(2)=B(C ) , and (3)=(⋆)⊤ T_(3)=C(B ) . We recall that ∘ is the outer product, so that ijk=∑ℓ=1R(:,ℓ∘:,ℓ∘:,ℓ)ijk=∑ℓ=1Riℓjℓkℓ∀(i,j,k)∈[d1]×[d2]×[d3] T_ijk= _ =1^R(A_:, _:, _:, )_ijk= _ =1^RA_i B_j C_k \ ∀(i,j,k)∈[d_1]×[d_2]×[d_3]. – The CP-rank of T, denoted rankCP() *rank_CP( T), is the smallest R for which there exist ∈ℝd1×RA ^d_1× R, ∈ℝd2×RB ^d_2× R and ∈ℝd3×RC ^d_3× R such that =⟦,,⟧ T= ,B,C . We always have rankCP()≤mind1d2,d1d3,d2d3 *rank_CP( T)≤ \d_1d_2,d_1d_3,d_2d_3\, and when one of the tensor dimensions equals 11, the CP-rank reduces to the usual matrix rank under the natural identification between matrices and third-order tensors with a singleton mode. For instance, if d3=1d_3=1, ∈ℝd1×d2×1 T ^d_1× d_2× 1 can be identified with a matrix :,:,1=∑ℓ=1R1,ℓ:,ℓ:,ℓ⊤∈ℝd1×d2 T_:,:,1= _ =1^RC_1, A_:, B_:, ^d_1× d_2, which is precisely a rank-R matrix factorization of :,:,1 T_:,:,1. Consequently, rankCP()=rank(:,:,1) *rank_CP( T)= *rank( T_:,:,1). The same argument applies whenever d1=1d_1=1 or d2=1d_2=1. Appendix B Finite-Dimensional Algebra (FDA) We intentionally adopt a relatively broad and self-contained exposition in this section in order to make the paper accessible to a wider audience. Readers already familiar with the underlying algebraic background may safely skip most of the introductory material and proceed directly to the proofs of the propositions (many of which rely on standard or straightforward arguments), or move directly to the next section. B.1 Definitions A monoid is a set equipped with a binary operation that combines any two elements to form a third element of that set. Specifically, a monoid (M,⋅)(M,·) must satisfy a⋅b∈M∀a,b∈Ma· b∈ M\ ∀ a,b∈ M (closure), (a⋅b)⋅c=a⋅(b⋅c)∀a,b,c∈M(a· b)· c=a·(b· c)\ ∀ a,b,c∈ M (associativity), and ∃e∈M,e⋅a=a⋅e=a∀a∈M∃ e∈ M,\ e· a=a· e=a\ ∀ a∈ M (identity element). A group is a monoid in which every element admits an inverse. More precisely, a group (G,⋅)(G,·) is a monoid such that ∀a∈G,∃b∈G,a⋅b=b⋅a=e∀ a∈ G,∃ b∈ G,\ a· b=b· a=e, where e denotes the identity element of G. The element b is called the inverse of a and is usually denoted by a−1a^-1. A group G is said to be abelian or commutative if a⋅b=b⋅a∀a,b∈Ga· b=b· a\ ∀ a,b∈ G. An additive group is a group where the group operation is typically thought of as addition. This terminology is most commonly used when the group elements are intuitively additive in nature, such as numbers or functions. The group operation is denoted by ++, the identity element by 0, and the inverse of an element a is denoted by −a-a. A multiplicative group is a group in which the group operation is typically understood as multiplication. This terminology is used especially when dealing with elements that naturally support a multiplicative structure, such as non-zero numbers, invertible matrices, and permutations. The group operation is denoted by ∗* or simply by juxtaposition (abab), the identity element by 11, and the inverse of an element a by a−1a^-1. A ring (R,+,∗)(R,+,*) is a structure consisting of a set equipped with two binary operations: addition (++) and multiplication (∗*), such that (R,+)(R,+) is an abelian (additive) group, (R,∗)(R,*) is a (multiplicative) monoid, and multiplication is distributive over addition (a∗(b+c)=a∗b+a∗ca*(b+c)=a*b+a*c and (a+b)∗c=a∗c+b∗c(a+b)*c=a*c+b*c, corresponding to the left and right distributivity respectively). A ring is commutative if (R,∗)(R,*) is a commutative monoid: a∗b=b∗a*b=b*a for all a,b∈Ra,b∈ R. Example B.1. For m∈ℕ∗m ^*, let ℳm()M_m(F) denote the set of m×m× m matrices with entries in F. Equipped with matrix multiplication, ℳm()M_m(F) forms a monoid. The subset GLm()⊂ℳm()GL_m(F) _m(F) of invertible matrices forms a group under matrix multiplication, the general linear group of degree m over F. Moreover, endowed with the usual matrix addition and multiplication, ℳm()M_m(F) forms a non-commutative ring. A field (,+,∗)(F,+,*) is a commutative ring in which every non-zero element has a multiplicative inverse, making (∖0,∗)(F \0\,*) an abelian group as well. Example B.2. For a prime integer p, p=ℤ/pℤF_p=Z/pZ endowed with modular arithmetic forms a finite field, the prime field of order p (also known as the Galois field of order p). In general, for any integer q, a finite field of order q exists if and only if q is a prime power (i.e., q=pkq=p^k where p is a prime number and k is a positive integer). In this case, all fields of order q are isomorphic to each other. In pF_p, the multiplicative inverse of an element α is the element β (denoted α−1α^-1) such that (αβ)%p=1(αβ)\%p=1, and can be computed using the extended Euclidean Algorithm. The result of α/βα/β is (αβ−1)%p(αβ^-1)\%p. A vector space over a field (,+,∗)(F,+,*) is a set V equipped with two operations, vector addition (V×V→V× V→ V) and scalar multiplication (×V→VF× V→ V), such that V with vector addition forms an abelian group (with identity 0 and inverses −-v) and scalar multiplication is associative and distributive over vector addition, i.e. for all a,b∈a,b and ,∈Vu,v∈ V: a(+)=a+a,(a+b)=a+b,(ab)=a(b), 1=a(u+v)=au+av,\ (a+b)u=au+bu,\ (ab)u=a(bu),\ 1_Fu=u. A module over a ring R generalizes vector spaces by allowing the scalars to come from a ring, not necessarily a field. The key differences are the absence of scalar inverses generally and the fact that the ring does not need to be commutative. An algebra A over a field (resp. ring) (,+,∗)(F,+,*) is a vector space (resp. module) equipped with a F-bilinear product555i.e. a map that is linear in each argument separately: (α+β)⋅=α(⋅)+β(⋅)( + )·w=α(u·v)+β(u·w) and ⋅(α+β)=α(⋅)+β(⋅)w·( + )=α(w·u)+β(w·v) for all ,,∈u,v,w∈ A, α,β∈α,β . ⋅:×→·: A× A→ A such that (+)⋅=⋅+⋅(u+v)·w=u·w+v·w (right distributivity), ⋅(+)=⋅+⋅w·(u+v)=w·u+w·v (left distributivity) and (α)⋅(β)=(α∗β)(⋅)( )·( )=(α*β)(u·v) (compatibility with scalars) for all ,,∈u,v,w∈ A and α,β∈α,β . When ⋅· is associative (resp. commutative), the algebra is said to be associative (resp. commutative). When the multiplicative identity exists, i.e., there exists an element 1∈1_ A∈ A such that 1⋅=⋅1=∀∈1_ A·u=u· 1_ A=u\ ∈ A, the algebra is said to be unital. The dimension of A is its dimension as a F-vector space, denoted by dimdim_F A. We say that A is finite-dimensional if n=dimn=dim_F A is finite. This means that a finite number of elements in the set can be combined linearly to express any element in the algebra, i.e., there exists a finite basis (i)i∈[n]\a^(i)\_i∈[n] of A (as a vector space over F) such that for every ∈u∈ A, =∑i=1nαi(i)u= _i=1^n _ia^(i) with αi∈∀i∈[n] _i \ ∀ i∈[n]. Let (,⋅)( A,·) and (,×)( B,×) be two F-algebras. A homomorphism of F-algebras ϕ:→φ: A→ B is a F-linear map satisfying ϕ(⋅)=ϕ()×ϕ()φ(u·v)=φ(u)×φ(v) for all ,∈u,v∈ A; and ϕ(1)=1φ(1_ A)=1_ B when A and B are unitals. The algebra homomorphism ϕφ is called an isomorphism if it is bijective, or equivalently, if there exists an algebra homomorphism φ:→ : B→ A, often denoted ϕ−1φ^-1, such that φ(ϕ())=∀∈ (φ(u))=u\ ∈ A and ϕ(φ())=∀∈φ( (v))=v\ ∈ B. If further = B= A, the isomorphism ϕφ is called an automorphism of A. Two F-algebras A and B are isomorphic (or, informally, similar) if there exists an algebra isomorphism ϕ:→φ: A→ B between them. In other words, A and B may look different at the level of their elements or chosen bases, but they share exactly the same algebraic structure: the operations in one correspond perfectly to the operations in the other under ϕφ. B.2 Structure Constants of FDA Let (,⋅)( A,·) be an nnF-FDA and B=(i)i∈[n]B=\a^(i)\_i∈[n] a basis of A (as a vector space over F). Then the structure of A in B is entirely captured by the tensor (B)∈n×n×n C^(B) ^n× n× n defined by (i)⋅(j)=∑k=1nijk(B)(k)a^(i)·a^(j)= _k=1^n C_ijk^(B)a^(k) (12) The elements of (B) C^(B) are called structure coefficients/constants of A in B. We will call the tensor (B) C^(B) the structure tensor of A in the basis B, and when the context is clear, we will omit B from the notation. That said, we have for all =∑i=1ni(i)u= _i=1^nu_ia^(i) and =∑i=1ni(i)v= _i=1^nv_ia^(i) in A, ⋅=∑i=1n∑j=1nij((i)⋅(j))=∑k=1n(∑i=1n∑j=1nijkij)(k)=∑k=1n(×1×2)k(k) splitu·v&= _i=1^n _j=1^nu_iv_j(a^(i)·a^(j))= _k=1^n ( _i=1^n _j=1^n C_ijku_iv_j )a^(k)= _k=1^n ( C×_1u×_2v )_ka^(k) split (13) Using (,)=((i),(j))(u,v)=(a^(i),a^(j)), we obtain ijk=(i)⊤::k(j) C_ijk=a^(i) C_::ka^(j) for all i,j,k∈[n]i,j,k∈[n]. Note that (see Equation (11)) ×1×2=(3)(⊗) C×_1u×_2v= C_(3) (v ) (14) with (Equation (7)) (3)⊤:=[|||vec(::1)vec(::2)⋯vec(::n)|||]∈n2×n C_(3) := bmatrix|&|&&|\\ vec( C_::1)&vec( C_::2)&·s&vec( C_::n)\\ |&|&&|\\ bmatrix ^n^2× n (15) The Proposition 2.1 states that for all ∈n×n×n C ^n× n× n, there exists an nnF-FDA whose structure tensor is C is some basis B; and that all nnF-FDA that have C as a structure tensor in one of their bases are isomorphic to each other. The proof of the first part is given by Lemma B.1 and the proof of the second part is given by Lemma B.2. Lemma B.1. For a ring F (which can be a field), let ∈n×n×n C ^n× n× n, and ×:n×n→n×:F^n×F^n ^n defined by ×=×1×2u×v= C×_1u×_2v. Then (n,×)(F^n,×) is an nnF-FDA, and C its structure tensor in its canonical basis (i)i∈[n]\e^(i)\_i∈[n]. Proof. It is easy to check that this structure forms an algebra over F. For the structure tensor, observe that (×)k=(×1×2)k=∑=1n∑j=1nijkij(u×v)_k=( C×_1u×_2v)_k= _=1^n _j=1^n C_ijku_iv_j for all ,∈nu,v ^n. So ((i)×(j))k=ijk∀i,j,k∈[n](e^(i)×e^(j))_k= C_ijk\ ∀ i,j,k∈[n]. ∎ Lemma B.2. Let (,⋅)( A,·) be an nnF-FDA with structure tensor ∈n×n×n C ^n× n× n in a basis B=(i)i∈[n]B=\a^(i)\_i∈[n], and (i)i∈[n]\e^(i)\_i∈[n] be the canonical basis of nF^n. The linear map ϕ:n→φ:F^n→ A defined by ϕ((i))=(i)∀i∈[n]φ(e^(i))=a^(i)\ ∀ i∈[n] is an isomorphism (of vector spaces), and we have the relation ϕ(×)=ϕ()⋅ϕ()∀,∈nφ(u×v)=φ(u)·φ(v)\ ,v ^n. As a consequence, by defining the product ×=×1×2u×v= C×_1u×_2v on nF^n, ϕφ becomes an algebra isomorphism between (n,×)(F^n,×) and (,⋅)( A,·). Proof. It is easy to see that ϕφ is an isomorphism of vector spaces. We also have for all ,∈nu,v ^n: ϕ(×)=∑k=1n(×1×2)kϕ((k))=∑k=1n(∑i=1n∑j=1nijkij)(k)=∑i=1n∑j=1nij∑k=1nijk(k)=∑i=1n∑j=1nij((i)⋅(j))=(∑i=1ni(i))⋅(∑j=1nj(j))=(∑i=1niϕ((i)))⋅(∑j=1njϕ((j)))=ϕ(∑i=1ni(i))⋅ϕ(∑j=1nj(j))=ϕ()⋅ϕ() splitφ (u×v )&= _k=1^n ( C×_1u×_2v )_kφ(e^(k))= _k=1^n ( _i=1^n _j=1^n C_ijku_iv_j )a^(k)\\ &= _i=1^n _j=1^nu_iv_j _k=1^n C_ijka^(k)\\ &= _i=1^n _j=1^nu_iv_j(a^(i)·a^(j))= ( _i=1^nu_ia^(i) )· ( _j=1^nv_ja^(j) )\\ &= ( _i=1^nu_iφ(e^(i)) )· ( _j=1^nv_jφ(e^(j)) )\\ &=φ ( _i=1^nu_ie^(i) )·φ ( _j=1^nv_je^(j) )=φ (u )·φ (v ) split (16) ∎ This shows that learning multiplication ⋅· in (,⋅)( A,·) is equivalent to learning × in []:=(n,×)F[ C]:=(F^n,×). If we are working in an arbitrary basis (i)i∈[n]\a^(i)\_i∈[n] of nF^n such that (i)=∑k=1nki(k)∀i∈[n]a^(i)= _k=1^nP_kie^(k)∀ i∈[n], we need to rescale C accordingly. Proposition B.3. Let C and ~ C be the structure tensors of an nnF-FDA A with respect to two bases B=(i))i∈[n]B=\a^(i))\_i∈[n] and B~=~(i)i∈[n] B=\ a^(i)\_i∈[n] respectively. If ∈n×nP ^n× n is the basis change matrix from B to B~ B, i.e. ~(i)=∑k=1nki(k)∀i∈[n] a^(i)= _k=1^nP_kia^(k)\ ∀ i∈[n], then we have ~=×1⊤×2⊤×3−1 C= C×_1P ×_2P ×_3P^-1, or equivalently, ~×3=×1⊤×2⊤ C×_3P= C×_1P ×_2P . If further B and B~ B are orthogonal basis, then ~=×1⊤×2⊤×3⊤ C= C×_1P ×_2P ×_3P . Proof. For all i,j∈[n]i,j∈[n], we have ~(i)⋅~(j)=(∑ℓ=1nℓi(ℓ))⋅(∑r=1nrj(r))=∑ℓ=1n∑r=1nℓirj((ℓ)⋅(r))=∑ℓ=1n∑r=1nℓirj∑s=1nℓrs(s)=∑ℓ=1n∑r=1nℓirj∑s=1nℓrs∑k=1n(−1)ks~(k)=∑k=1n(∑ℓ,r,s=1nℓrs(⊤)iℓ(⊤)jr(−1)ks)~(k)=∑k=1n(×1⊤×2⊤×3−1)ijk~(k) (Equation (6)) split a^(i)· a^(j)&= ( _ =1^nP_ ia^( ) )· ( _r=1^nP_rja^(r) )\\ &= _ =1^n _r=1^nP_ iP_rj (a^( )·a^(r) )\\ &= _ =1^n _r=1^nP_ iP_rj _s=1^n C_ rsa^(s)\\ &= _ =1^n _r=1^nP_ iP_rj _s=1^n C_ rs _k=1^n(P^-1)_ks a^(k)\\ &= _k=1^n ( _ ,r,s=1^n C_ rs(P )_i (P )_jr(P^-1)_ks ) a^(k)\\ &= _k=1^n ( C×_1P ×_2P ×_3P^-1 )_ijk a^(k) (Equation~ eq:T_A_A_A) split (17) So ~=×1⊤×2⊤×3−1 C= C×_1P ×_2P ×_3P^-1. We have (see Equation (8)) (~×3)(3)=~(3)=(×1⊤×2⊤×3−1)(3)=−1(×1⊤×2⊤)(3)=(×1⊤×2⊤)(3)( C×_3P)_(3)=P C_(3)=P( C×_1P ×_2P ×_3P^-1)_(3)=PP^-1( C×_1P ×_2P )_(3)=( C×_1P ×_2P )_(3). So ~×3=×1⊤×2⊤ C×_3P= C×_1P ×_2P . If further B and B~ B are orthogonal basis, then −1=⊤P^-1=P . In fact, let =[−(i)−]i∈[n]⊤∈n×nB=[-a^(i)-]_i∈[n] ^n× n (ia_i is the ithi^th column of B) and ~=[−~(i)−]i∈[n]⊤∈n×n B=[- a^(i)-]_i∈[n] ^n× n. We have ~= B=BP. Assuming ⊤=nB B=I_n, this give =⊤~P=B B, so that ⊤=nP P=I_n if ⊤=~⊤~=nBB = B B=I_n and ⊤=nPP =I_n if ~~⊤=⊤=n B B =B B=I_n. ∎ As a consequence of this proposition, we get that the rank of the structure tensor of a FDA is basis-invariant: it is an intrinsic invariant of the algebra. Corollary B.4. For all i∈[3]i∈[3], the rank of (i)(B)∈n×n2 C^(B)_(i) ^n× n^2 is independant from the basis B. Proof. If P is the basis change matrix from an arbitrary basis B to another basis B~ B, then (B~)=(B)×1⊤×2⊤×3−1 C^( B)= C^(B)×_1P ×_2P ×_3P^-1 by Proposition B.3. This implies (see Equations (8) and (9)): • (1)(B~)=((B)×1⊤×2⊤×3−1)(1)=⊤((B)×2⊤×3−1)(1)=⊤(1)(B)(⊤⊗−1)⊤ C^( B)_(1)= ( C^(B)×_1P ×_2P ×_3P^-1 )_(1)=P ( C^(B)×_2P ×_3P^-1 )_(1)=P C^(B)_(1)(P ^-1) • (2)(B~)=((B)×1⊤×2⊤×3−1)(2)=⊤((B)×1⊤×3−1)(2)=⊤(2)(B)(−1⊗⊤)⊤ C^( B)_(2)= ( C^(B)×_1P ×_2P ×_3P^-1 )_(2)=P ( C^(B)×_1P ×_3P^-1 )_(2)=P C^(B)_(2)(P^-1 ) • (3)(B~)=((B)×1⊤×2⊤×3−1)(3)=−1((B)×1⊤×2⊤)(3)=−1(3)(B)(⊗) C^( B)_(3)= ( C^(B)×_1P ×_2P ×_3P^-1 )_(3)=P^-1 ( C^(B)×_1P ×_2P )_(3)=P^-1 C^(B)_(3)(P ) In each case, (i)(B~) C^( B)_(i) is obtained from (i)(B) C^(B)_(i) by left- and right-multiplication with invertible matrices. Such operations preserve matrix rank, hence rank((i)(B~))=rank((i)(B))∀i∈[3] *rank ( C^( B)_(i) )= *rank ( C^(B)_(i) )\ ∀ i∈[3]. ∎ Sparsity, on the other hand, is not basis-invariant. But it may be possible to find a basis of A in which C is as sparse as possible, making the problem of learning A simpler to study; ~∈argmin≠n,rank()=n‖×1⊤×2⊤×3−1‖0 C∈ _P _n, *rank(P)=n \| C×_1P ×_2P ×_3P^-1 \|_0. For example, if we go from a basis B=(i)i∈[n]B=\a^(i)\_i∈[n] to its orthonormal equivalent Q=(i)i∈[n]Q=\q^(i)\_i∈[n], then we have =B=QP under the QR decomposition, with =[−(i)−]i∈[n]⊤∈n×nB=[-a^(i)-]_i∈[n] ^n× n (ia_i is the ithi^th column of B), =[−(i)−]i∈[n]⊤∈n×nQ=[-q^(i)-]_i∈[n] ^n× n orthogonal, and ∈n×nP ^n× n upper triangular. Note that ijk(Q)=∑ℓ,r,sℓrs(B)ℓirj(−1)ks C_ijk^(Q)= _ ,r,s C_ rs^(B)P_ iP_rj(P^-1)_ks, with −1P^-1 also upper triangular. Although any tensor ∈n×n×n C ^n× n× n defines an nnF-FDA, a key question is how the algebraic properties of (,⋅)( A,·) are reflected in its structure of C. The following proposition makes this connection explicit by characterizing associativity, commutativity, and the existence of a unit directly in terms of tensor equations. Proposition B.5. Let (,⋅)( A,·) be an nnF-FDA with structure tensor ∈n×n×n C ^n× n× n in B=(i)i∈[n]B=\a^(i)\_i∈[n]. A is (i) associative if and only if ∑k=1nijkklm=∑k=1nikmjlk∀i,j,l,m∈[n] _k=1^n C_ijk C_klm= _k=1^n C_ikm C_jlk\ ∀ i,j,l,m∈[n]; (i) commutative if and only if C is symmetric is its first two modes, i.e. ij:=ji:∀i,j∈[n] C_ij:= C_ji:\ ∀ i,j∈[n], or equivalently, ::k⊤=::k∀k∈[n] C_::k = C_::k∀ k∈[n]; (i) unital if and only if there exist λ∈nλ ^n such that ×1λ=n=×2λ C×_1λ=I_n= C×_2λ, that is ∑i=1nλii,:,:=n=∑i=1nλi:,i,: _i=1^n _i C_i,:,:=I_n= _i=1^n _i C_:,i,:, or equivalently, (1)⊤λ=vec(n)=(2)⊤λ C_(1) λ=vec(I_n)= C_(2) λ. In this case, 1=∑i=1nλi(i)1_ A= _i=1^n _ia^(i), with λ∈nλ ^n the unique solution of the system of equations (1)⊤λ=vec(n)=(2)⊤λ C_(1) λ=vec(I_n)= C_(2) λ. Proof. (i) For associative FDA, the multiplication must satisfy ((i)⋅(j))⋅(l)=(i)⋅((j)⋅(l))∀i,j,l(a^(i)·a^(j))·a^(l)=a^(i)·(a^(j)·a^(l))\ ∀ i,j,l. Expanding this using the structure constants (Equation (12)), we require ∑m=1n(∑k=1nijkklm)(m)=∑m=1n(∑k=1nikmjlk)(m)∀i,j,l∈[n] _m=1^n ( _k=1^n C_ijk C_klm )a^(m)= _m=1^n ( _k=1^n C_ikm C_jlk )a^(m)\ ∀ i,j,l∈[n]. (i) For commutative FDA, the multiplication must satisfy (i)⋅(j)=(j)⋅(i)∀i,j∈[n]⟺∑k=1nijk(k)=∑k=1njik(k)∀i,j∈[n]⟺ij:=ji:∀i,j∈[n]a^(i)·a^(j)=a^(j)·a^(i)\ ∀ i,j∈[n] _k=1^n C_ijka^(k)= _k=1^n C_jika^(k)\ ∀ i,j∈[n] C_ij:= C_ji:\ ∀ i,j∈[n]. (i) First, consider the algebra ([],×)(F[ C],×) generated by C. Suppose ([],×)(F[ C],×) is unital, i.e. there exists λ∈nλ ^n such that ×λ==λ×u×λ=u=λ×u for all ∈nu ^n. Then, expanding using Equation (13), wet get ×1×2λ==×1λ×2∀∈n C×_1u×_2λ=u= C×_1λ×_2u\ ^n, which is equivalent to ×2λ=n=×1λ C×_2λ=I_n= C×_1λ. The direction ⟸ of this equivalence is obvious, considering the fact that n×1=n⊤=I_n×_1u=I_n u=u and n×2=n=I_n×_2u=I_nu=u for all ∈nu ^n (Equation (5)). The direction ⟹ follows by taking u as a kthk^th canonical vector of nF^n, for all k∈[n]k∈[n]. We also have ×1λ=n=×2λ⟺(×1λ)⊤=n=×2λ⟺vec((×1λ)⊤)=vec(n)=vec(×2λ)⟺(1)⊤λ=vec(n)=(2)⊤λ (Equation (10)) split C×_1λ=I_n= C×_2λ& ( C×_1λ) =I_n= C×_2λ\\ & (( C×_1λ) )=vec(I_n)=vec( C×_2λ)\\ & C_(1) λ=vec(I_n)= C_(2) λ (Equation~ eq:vect_Ta) split (18) Now, suppose there exist λ,λ~∈nλ, λ ^n such that ×1λ=n=×2λ C×_1λ=I_n= C×_2λ and ×1λ~=n=×2λ~ C×_1 λ=I_n= C×_2 λ. From ×1λ=n C×_1λ=I_n, we get ×1λ×2λ~=n×2λ~=λ~ C×_1λ×_2 λ=I_n×_2 λ= λ; and from n=×2λ~I_n= C×_2 λ, we get λ=n×1λ=×2λ~×1λ=I_n×_1λ= C×_2 λ×_1λ. So λ=×1λ×2λ~=λ~λ= C×_1λ×_2 λ= λ. Therefore, when a solution λ to (1)⊤λ=vec(n)=(2)⊤λ C_(1) λ=vec(I_n)= C_(2) λ exists, it is unique, and thus equals 1[]1_F[ C]. Finally, since ([],×)(F[ C],×) and (,⋅)( A,·) are isomorphic by the linear map ϕ:n→φ:F^n→ A defined by ϕ((i))=(i)∀i∈[n]φ(e^(i))=a^(i)\ ∀ i∈[n] (Lemma B.2), if ([],×)(F[ C],×) is unital with 1[]=∑i=1nλi(i)1_F[ C]= _i=1^n _ie^(i), then (,⋅)( A,·) is also unital with 1=ϕ(1[])=∑i=1nλiϕ((i))=∑i=1nλi(i)1_ A=φ(1_F[ C])= _i=1^n _iφ(e^(i))= _i=1^n _ia^(i). ∎ The corollary of (i) in this proposition tells us how we can get the unit element of ([],×)(F[ C],×) in B=(i)i∈[n]B=\e^(i)\_i∈[n] when we only have access to C and the condition of its existence. Corollary B.6. Let (,⋅)( A,·) be an nnF-FDA with structure tensor ∈n×n×n C ^n× n× n in B=(i)i∈[n]B=\a^(i)\_i∈[n]. Let :=[(1),(2)]⊤∈2n2×nA:= [ C_(1), C_(2) ] ^2n^2× n and :=[vec(n),vec(n)]⊤∈2n2b:= [vec(I_n),vec(I_n) ] ^2n^2. A is unital if and only if rank()=rank([|]) *rank_F(A)= *rank_F ( [A|b ] ), where [|]∈2n2×(n+1) [A|b ] ^2n^2×(n+1) is the augmented matrix of A with b added as a column. In this case, 1=∑i=1nλi(i)1_ A= _i=1^n _ia^(i), with λ the unique solution to λ=Aλ=b. Proof. We need to check that there exists a joint solution to the two λ linear equations (k)⊤λ=vec(n) C_(k) λ=vec(I_n), k∈1,2k∈\1,2\, that is λ=Aλ=b. The system has 2n22n^2 equations for n variables, and solutions are cosets of ker() (A). We just need to check the system’s consistency (in F, this precision is important). ∎ We can also solve the system λ=Aλ=b to find the coordinates of the unit element of A in B=(i)i∈[n]B=\a^(i)\_i∈[n]. It all depends on the field we are in. This can be done quite easily in ℝR or ℂC. The system λ=Aλ=b has solutions if and only if †=AA b=b, and the solutions are the vectors λ=†+(−†)λ=A b+ (I-A A )u for an arbitrary conformable vector u. Here, †A is the pseudo-inverse of A : †=AA A=A and ††=†A AA =A . In a field like pF_p, a given solution of the system is not guaranteed to be in F, and solving the system is not easy. In fact, in this field, everything is modulo p, for example, Equation (13) should be read (∑i(i))⋅(∑i(i))=∑k((∑i,jijkij)%p)(k) ( _iu_ia^(i) )· ( _iv_ia^(i) )= _k ( ( _i,j C_ijku_iv_j )\%p )a^(k), and the system, (λ)%p= (Aλ )\%p=b. The multiplicative inverse of an element α is the element β (denoted α−1α^-1) such that (αβ)%p=1(αβ)\%p=1, and can be computed using the extended Euclidean Algorithm. The result of α/βα/β is (αβ−1)%p(αβ^-1)\%p. So, these details must be considered if we opt for Gaussian Elimination to solve the system. It should be noted that associative, unital, noncommutative algebras only exist for n≥3n≥ 3 over any field F. Proposition B.7. For any field F, the smallest integer n∈ℕ∗n ^* for which there exists an associative, unital, noncommutative nnF-FDA is n=3n=3. Equivalently, (i) every associative and unital nnF-FDA with n≤2n≤ 2 is commutative; (i) and there exists an associative, unital, noncommutative 33F-FDA. Proof. We split the proof into two parts. (i) Nonexistence for n≤2n≤ 2. For n=1n=1, let (,⋅)( A,·) be a unital 11F-FDA. Since dim()=1 _F( A)=1, the unit element 11_ A forms a basis of A. Therefore =λ1,λ∈ A=\λ 1_ A,λ \. Hence, for all =λ1u=λ 1_ A and =μ1v=μ 1_ A in A, we have ⋅=(λ1)⋅(μ1)=λμ(1⋅1)=λμ1=μλ1=⋅u·v=(λ 1_ A)·(μ 1_ A)=λμ(1_ A· 1_ A)=λμ 1_ A=μλ 1_ A=v·u (19) So A is commutative. Now let n=2n=2, and let (,⋅)( A,·) be an associative and unital 22F-FDA. Since dim()=2 _F( A)=2 and 1≠01_ A≠ 0, there exists ∈e∈ A such that B=1,B=\1_ A,e\ is a basis of A. Since A is closed under multiplication, there exist α,β∈α,β such that 2=α1+βe^2=α 1_ A+ . Let =a1+bu=a1_ A+be and =c1+dv=c1_ A+de be two arbitrary elements of A, with a,b,c,d∈a,b,c,d . Then ⋅=(a1+b)⋅(c1+d)=ac1⋅1+ad1⋅+bc⋅1+bd2=ac 1+ad+bc+bd(α1+β)=(ac+αbd)1+(ad+bc+βbd) splitu·v&=(a1_ A+be)·(c1_ A+de)\\ &=ac1_ A· 1_ A+ad1_ A·e+bce· 1_ A+bde^2\\ &=ac\,1_ A+ade+bce+bd(α 1_ A+ )\\ &=(ac+α bd)1_ A+(ad+bc+β bd)e split (20) The right-hand side is symmetric in (a,b)(a,b) and (c,d)(c,d), since ac+αbd=ca+αdbac+α bd=ca+α db and ad+bc+βbd=cb+da+βdbad+bc+β bd=cb+da+β db. Therefore ⋅=⋅∀,∈u·v=v·u\ ,v∈ A. So every associative and unital 22F-FDA is commutative. (i) Existence for n=3n=3. Consider =UT2():=(ab0c):a,b,c∈, A= UT_2(F):= \ pmatrixa&b\\ 0&c pmatrix\ :\ a,b,c \, equipped with the usual matrix multiplication. This is the algebra of upper triangular 2×22× 2 matrices over F. We have =span(1),(2),(3) A=span_F \a^(1),a^(2),a^(3) \ where (1)=(1000),(2)=(0100),(3)=(0001)a^(1)= pmatrix1&0\\ 0&0 pmatrix, ^(2)= pmatrix0&1\\ 0&0 pmatrix, ^(3)= pmatrix0&0\\ 0&1 pmatrix (21) These three matrices are linearly independent, so dim()=3 _F( A)=3. Since matrix multiplication is bilinear and associative, (,⋅)( A,·) is an associative 33F-FDA. It is also unital, with unit 1=(1)+(3)1_ A=a^(1)+a^(3). Finally, A is not commutative, because (1)(2)=(2)≠0=(2)(1)a^(1)a^(2)=a^(2)≠ 0=a^(2)a^(1). ∎ B.3 Examples of FDA Examples B.3, B.4 and B.5 are associative, commutative and unital. Example B.6 is associative and unital but not commutative. The algebra of quaternions is associative and unitary but non-commutative. The algebra of octonions is unitary but neither associative nor commutative. Lie algebras (Example B.8) are not associative, not commutative, nor unital. Example B.3 (Complex Numbers). =ℝF=R, n=2n=2 and =ℂ=(2,⋅) A=C= (F^2,· ). The product ⋅· is defined as (a+b)⋅(c+d):=(ac−bd)+(ad+bc)(a+bi)·(c+di):=(ac-bd)+(ad+bc)i with 2=−1i^2=-1. The structure tensor of A in its canonical basis ((1),(2))≡(1,)(a^(1),a^(2))≡(1,i) is [111112121122],[211212221222]=[1001],[01−10] bmatrix C_111& C_112\\ C_121& C_122\\ bmatrix, bmatrix C_211& C_212\\ C_221& C_222\\ bmatrix= bmatrix1&0\\ 0&1\\ bmatrix, bmatrix0&1\\ -1&0\\ bmatrix (22) since (1)⋅(1)=(1)⟹11:=[1,0]a^(1)·a^(1)=a^(1) C_11:=[1,0], (1)⋅(2)=(2)⋅(1)=(2)⟹12:=21:=[0,1]a^(1)·a^(2)=a^(2)·a^(1)=a^(2) C_12:= C_21:=[0,1], and (2)⋅(2)=−(1)⟹22:=[−1,0]a^(2)·a^(2)=-a^(1) C_22:=[-1,0]. In the field =ℤ/pℤF=Z/pZ for p prime, we have =(−1)%p=p−1i=(-1)\%p=p-1, so 221=p−1 C_221=p-1. In the same way, we can also calculate the structure constants of quaternions (n=4n=4) and octonions (n=8n=8). Example B.4 (Dual Numbers). =(2,⋅) A= (F^2,· ) with product ⋅· is defined as (a+bε)⋅(c+dε):=ac+(ad+bc)ε(a+b )·(c+d ):=ac+(ad+bc) , where ε2=0 ^2=0. The structure tensor of A in its canonical basis ((1),(2))≡(1,ε)(a^(1),a^(2))≡(1, ) is [111112121122],[211212221222]=[1001],[0100] bmatrix C_111& C_112\\ C_121& C_122\\ bmatrix, bmatrix C_211& C_212\\ C_221& C_222\\ bmatrix= bmatrix1&0\\ 0&1\\ bmatrix, bmatrix0&1\\ 0&0\\ bmatrix (23) Example B.5 (Polynomials modulo xn−1x^n-1). =(n−1[x],⋅) A= (F_n-1[x],· ), with n−1[x]F_n-1[x] the set of polynomial of degree at most n−1n-1 on F. The product ⋅· is defined as (∑i=0n−1aixi)⋅(∑i=0n−1bixi):=∑i,j=0n−1aibix(i+j)%n=∑k=0n−1(∑i,j=0n−1aibiδk,(i+j)%n)xk ( _i=0^n-1a_ix^i )· ( _i=0^n-1b_ix^i ):= _i,j=0^n-1a_ib_ix^(i+j)\%n= _k=0^n-1 ( _i,j=0^n-1a_ib_i _k,(i+j)\%n )x^k. Equivalently, ≃[x]/(xn−1) A [x]/(x^n-1), with [x]F[x] the polynomial ring in one indeterminate x over the field F. The structure tensor of A in its canonical basis ((0),…,(n−1))≡(x0,⋯,xn−1)(a^(0),…,a^(n-1))≡(x^0,·s,x^n-1) is ijk=δk,(i+j)%n∀i,j,k∈⟦0,n−1⟧ C_ijk= _k,(i+j)\%n\ ∀ i,j,k∈ 0,n-1 since xi⋅xj=x(i+j)modnx^i· x^j=x^(i+j) n. Here we adopt 0-based indexing, i.e., indices range from 0 to n−1n-1, for the convenience of notation. Example B.6 (Square matrices of size n). =(ℳn(),⋅) A= (M_n(F),· ), with ℳn()M_n(F) the set of square matrices of size n with entries in F. The product ⋅· is defined as (⋅)ij:=∑k=1nikkj (A·B )_ij:= _k=1^nA_ikB_kj. Let’s consider the canonical basis B=(i)i∈[n2]=((q−1)n+r)(q,r)∈[n]2B=\a^(i)\_i∈[n^2]=\a^((q-1)n+r)\_(q,r)∈[n]^2 of ℳn()M_n(F), where each ((q−1)n+r)a^((q-1)n+r) has 11_F at position (q,r)∈[n]2(q,r)∈[n]^2 and 00_F everywhere. Since ((q1−1)n+r1)⋅((q2−1)n+r2)=δq2r1((q1−1)n+r2)a^((q_1-1)n+r_1)·a^((q_2-1)n+r_2)= _q_2r_1a^((q_1-1)n+r_2), the structure tensor of A in B is (q1−1)n+r1,(q2−1)n+r2,(q3−1)n+r3=δq2r1δq1q3δr2r3 C_(q_1-1)n+r_1,(q_2-1)n+r_2,(q_3-1)n+r_3= _q_2r_1 _q_1q_3 _r_2r_3. Example B.7 (Upper triangular matrices of size t). =(UTt(),⋅) A= ( UT_t(F),· ), with UTt():=∈ℳt():ij=0∀i>j UT_t(F):= \A _t(F):A_ij=0_F∀ i>j \ the set of upper triangular square matrices of size m with entries in F. The product ⋅· is defined as the usual matrix multiplication. The dimension of UTt() UT_t(F) is n=t(t+1)2n= t(t+1)2, since the free entries are exactly those on and above the diagonal. Example B.8. A Lie algebra (,⋅)( A,·) is an algebra whose binary operation ⋅· (generally denoted by [⋅,⋅][·,·] and called the Lie bracket) satisfies the alternating property (or antisymmetry) ⋅=0∀∈u·u=0\ ∈ A, and the Jacobi identity (⋅)⋅+(⋅)⋅+(⋅)⋅=0∀,,∈(u·v)·w+(v·w)·u+(w·u)·v=0\ ,v,w∈ A. For any associative algebra (,⋅)( A,·), one can define a Lie algebra using [,]=⋅−⋅∀,∈[u,v]=u·v-v·u\ ,v∈ A. For example, if we replace matrix multiplication AB with the matrix commutator ⋅:=−A·B:=AB-BA, then =(ℳn(),⋅) A= (M_n(F),· ) becomes a Lie algebra, with (q1−1)n+r1,(q2−1)n+r2,(q3−1)n+r3=δq2r1δq1q3δr2r3−δq1r2δq2q3δr1r3 C_(q_1-1)n+r_1,(q_2-1)n+r_2,(q_3-1)n+r_3= _q_2r_1 _q_1q_3 _r_2r_3- _q_1r_2 _q_2q_3 _r_1r_3. In general, we have the following result about the structure tensor of Lie Algebra. Proposition B.8. An nnF-FDA (,⋅)( A,·) with structure tensor ∈n×n×n C ^n× n× n in the basis B=(i)i∈[n]B=\a^(i)\_i∈[n] is a Lie algebra if and only if (i) skew-symmetric: ijk=−jik∀i,j,k∈[n]; C_ijk=- C_jik ∀ i,j,k∈[n]; (24) (i) Jacobi identity: ∑k=1nijkkℓm+∑k=1njℓkkim+∑k=1nℓikkjm=0∀i,j,ℓ,m∈[n] _k=1^n C_ijk C_k m+ _k=1^n C_j k C_kim+ _k=1^n C_ ik C_kjm=0 ∀ i,j, ,m∈[n] (25) Proof. Recall that (,⋅)( A,·) is a Lie algebra if and only if its product is bilinear, skew-symmetric, and satisfies the Jacobi identity. Since (,⋅)( A,·) is already an nnF-FDA, bilinearity is part of the definition. It therefore remains to characterize skew-symmetry and the Jacobi identity in terms of C. (i) We first characterize skew-symmetry. For all i,j∈[n]i,j∈[n], we have (i)⋅(j)=∑k=1nijk(k)a^(i)·a^(j)= _k=1^n C_ijka^(k) and (j)⋅(i)=∑k=1njik(k)a^(j)·a^(i)= _k=1^n C_jika^(k). Thus, (i)⋅(j)=−(j)⋅(i)∀i,j∈[n]⟺∑k=1nijk(k)=∑k=1n(−jik)(k)∀i,j∈[n]a^(i)·a^(j)=-a^(j)·a^(i)\ ∀ i,j∈[n] _k=1^n C_ijka^(k)= _k=1^n(- C_jik)a^(k) ∀ i,j∈[n] (26) Since B=(k)k∈[n]B=\a^(k)\_k∈[n] is a basis, this holds if and only if Equation (24) holds. (i) We now characterize the Jacobi identity. For all i,j,ℓ∈[n]i,j, ∈[n], we have ((i)⋅(j))⋅(ℓ)=∑k=1nijk((k)⋅(ℓ))=∑k=1nijk∑m=1nkℓm(m)=∑m=1n(∑k=1nijkkℓm)(m)(a^(i)·a^(j))·a^( )= _k=1^n C_ijk (a^(k)·a^( ) )= _k=1^n C_ijk _m=1^n C_k ma^(m)= _m=1^n ( _k=1^n C_ijk C_k m )a^(m) (27) Similarly, ((j)⋅(ℓ))⋅(i)=∑m=1n(∑k=1njℓkkim)(m) and ((ℓ)⋅(i))⋅(j)=∑m=1n(∑k=1nℓikkjm)(m)(a^(j)·a^( ))·a^(i)= _m=1^n ( _k=1^n C_j k C_kim )a^(m) and (a^( )·a^(i))·a^(j)= _m=1^n ( _k=1^n C_ ik C_kjm )a^(m) (28) Thus, the Jacobi identity ((i)⋅(j))⋅(ℓ)+((j)⋅(ℓ))⋅(i)+((ℓ)⋅(i))⋅(j)=0∀i,j,ℓ∈[n](a^(i)·a^(j))·a^( )+(a^(j)·a^( ))·a^(i)+(a^( )·a^(i))·a^(j)=0 ∀ i,j, ∈[n] (29) is equivalent to ∑m=1n[∑k=1nijkkℓm+∑k=1njℓkkim+∑k=1nℓikkjm](m)=0∀i,j,ℓ∈[n] _m=1^n [ _k=1^n C_ijk C_k m+ _k=1^n C_j k C_kim+ _k=1^n C_ ik C_kjm ]a^(m)=0 ∀ i,j, ∈[n] (30) Since B is a basis, this holds if and only if Equation (25) holds. ∎ B.4 From Groups to FDA: A Unified View Definition B.9. For a group (G,∘)(G, ) and a field F, the group algebra of G over F, denoted ([G],⋅)(F[G],·), is the set of all linear combinations of elements of G with coefficients in F. If G has n elements gii∈[n]\g_i\_i∈[n], then [G]=∑i=1nαigi∣α1,…,αn∈F[G]= \ _i=1^n _ig_i\ \ _1,…, _n \ and (∑i=1nαigi)⋅(∑j=1nβjgj)=∑i,j=1nαiβi(gi∘gj)=∑k=1n(∑i,j=1nαiβj(gi∘gj=gk))gk ( _i=1^n _ig_i )· ( _j=1^n _jg_j )= _i,j=1^n _i _i (g_i g_j )= _k=1^n ( _i,j=1^n _i _j1(g_i g_j=g_k) )g_k, with 1 the indicator function. We have 1[G]=e1_F[G]=e, with e is the identity of G. The structure tensor of [G]F[G] in gii=1n\g_i\_i=1^n is ijk=(gk=gi∘gj)∈0,1∀i,j,k∈[n] C_ijk=1(g_k=g_i g_j)∈\0,1\\ ∀ i,j,k∈[n]. Note that the formal expression ∑i=1nαigi _i=1^n _ig_i should not be interpreted as a genuine linear combination inside G, since a group has no intrinsic compatibility between its operation ∘ and the scalar or additive structure of F. As explained in Section 3, this expression acquires meaning once we pass to one-hot encoding. Redefine [G]:=∑i=1nαi(i)|α∈nF[G]:= \ _i=1^n _ia^(i)\; |\;α ^n \ where (i)=Ψ(gi)a^(i)= (g_i) and Ψ:G→0,1n :G→\0_F,1_F\^n is the one-hot encoding of G over F, given by Ψ(gi):=[(gk=gi)]k∈[n] (g_i):= [1(g_k=g_i) ]_k∈[n]. Multiplication in [G]F[G], which is a free vector space over G with multiplication given by linearly extending the group law, is then defined by ⋅:=∑i,jijΨ(gi∘gj)=∑k=1n(∑i,j=1nij(gi∘gj=gk))(k)u·v:= _i,ju_iv_j (g_i g_j)= _k=1^n ( _i,j=1^nu_iv_j1(g_i g_j=g_k) )a^(k) for all =∑i(i)u= _iu_ia^(i) and =∑j(j)v= _jv_ja^(j). In this way, linear combinations of group elements become well-defined elements of the vector space [G]F[G], and the group multiplication naturally extends to an algebra product on [G]F[G]. With this construction, we can show that ([G],⋅)(F[G],·) is an nnF-FDA, and that training a model on the group (G,∘)(G, ) is equivalent to training it on the multiplication in ([G],⋅)(F[G],·). Proposition B.10. For a finite group (G,∘)(G, ) with n elements gii∈[n]\g_i\_i∈[n] and identity e, ([G],⋅)(F[G],·) is an n-dimensional associative and unital F-FDA with 1[G]=Ψ(e)1_F[G]= (e). Also, ([G],⋅)(F[G],·) is commutative if and only if G is commutative. Moreover, the structure tensor of [G]F[G] in B=Ψ(gi)i∈[n]B=\ (g_i)\_i∈[n] is given by ijk=(gi∘gj=gk)∀i,j,k∈[n] C_ijk=1_F(g_i g_j=g_k)\ ∀ i,j,k∈[n]; and we have Ψ(gi∘gj)=×1Ψ(gi)×2Ψ(gj)∀i,j∈[n] (g_i g_j)= C×_1 (g_i)×_2 (g_j)\ ∀ i,j∈[n]. Proof. It is easy to check that [G]F[G] is a vector space over F, and that ⋅· verifies the axioms of an algebra operation (bilinearity, right and left distributivity, compatibility with scalars). The associativity and unitality conditions follow from the fact that G is by definition associative and unital. Now, let i,j∈[n]i,j∈[n]. We have Ψ(gi)⋅Ψ(gj)=Ψ(gi∘gj) (g_i)· (g_j)= (g_i g_j), so ijk=(gk=gi∘gj)=(Ψ(gi∘gj))k∀k∈[n] C_ijk=1(g_k=g_i g_j)=( (g_i g_j))_k\ ∀ k∈[n]. If G is commutative, then [G]F[G] is commutative by Proposition B.5 since ijk=(gi∘gj=gk)=(gj∘gi=gk)=jik∀i,j,k∈[n] C_ijk=1(g_i g_j=g_k)=1(g_j g_i=g_k)= C_jik\ ∀ i,j,k∈[n]. The converse is also true by the same proposition. Finally, we have Ψ(gi∘gj)=×1Ψ(gi)×2Ψ(gj) (g_i g_j)= C×_1 (g_i)×_2 (g_j) for all i,j∈[n]i,j∈[n] since (×1Ψ(gi)×2Ψ(gj))k=∑l,r=1nlrk(Ψ(gi))l(Ψ(gj))r=∑l,r=1nlrkδliδrj=ijk=(Ψ(gi∘gj))k∀k∈[n] split ( C×_1 (g_i)×_2 (g_j) )_k= _l,r=1^n C_lrk( (g_i))_l( (g_j))_r= _l,r=1^n C_lrk _li _rj= C_ijk=( (g_i g_j))_k\ ∀ k∈[n] split (31) ∎ Remark B.11. Given a group G=gii∈[n]G=\g_i\_i∈[n], the structure tensor of [G]F[G] in B=Ψ(gi)i∈[n]B=\ (g_i)\_i∈[n] is the same for all =ℤ/pℤF=Z/pZ, p>1p>1. For all i,j,k∈[n]i,j,k∈[n], we have ijk=1 C_ijk=1 if gi∘gj=gkg_i g_j=g_k and 0 otherwise. So for groups and finite fields, we can always choose p=2p=2 without loss of generality. Remark B.12. The assignment sending a group G to its group algebra [G]F[G] is a functor from the category of groups to the category of F-algebras. Indeed, to every group homomorphism ϕ:G→Hφ:G→ H one can associate the algebra homomorphism [ϕ]:[G]→[H]F[φ]:F[G] [H] defined by [ϕ](∑g∈Gαgg):=∑g∈Gαgϕ(g)=∑h∈H(∑g∈G,ϕ(g)=hαg)hF[φ] ( _g∈ G _gg ):= _g∈ G _gφ(g)= _h∈ H ( _ subarraycg∈ G,\ φ(g)=h subarray _g )h. This construction preserves identities ([idG]=id[G]F[id_G]=id_F[G] with idGid_G the identity map on the group G, and id[G]id_F[G] the identity map on the algebra [G]F[G]) and composition ([ψ∘ϕ]=[ψ]∘[ϕ]F[ψ φ]=F[ψ] [φ] for all ϕ:G→Hφ:G→ H and ψ:H→Kψ:H→ K). Hence, it defines a functor. As a consequence, [Ψ]F[ ] is an isomorphism between ([G],⋅)(F[G],·) and ([],×)(F[ C],×) in Proposition B.10. GGHH[G]F[G][H]F[H]ϕ φ[ϕ] F[φ] (32) Example B.9 (Group algebra of the additive group ℤ/nℤZ/nZ over F). =([ℤ/nℤ],⋅) A= (F[Z/nZ],· ), with ℤ/nℤ=gii∈⟦0,n−1⟧≡⟦0,n−1⟧Z/nZ= \g_i \_i∈ 0,n-1 ≡ 0,n-1 and gi∘gj=(i+j)modn=g(i+j)modn∀i,j∈⟦0,n−1⟧g_i g_j=(i+j) n=g_(i+j) n\ ∀ i,j∈ 0,n-1 . So ijk=(gk=gi∘gj)=δk,(i+j)%n∀i,j,k∈⟦0,n−1⟧ C_ijk=1(g_k=g_i g_j)= _k,(i+j)\%n\ ∀ i,j,k∈ 0,n-1 . This is the structure tensor of n−1[x]=[x]/(xn−1)F_n-1[x]=F[x]/(x^n-1) in its canonical basis (Example B.5), so [ℤ/nℤ]≅n−1[x]F[Z/nZ] _n-1[x]. Here we adopt 0-based indexing for the convenience of notation. Example B.10 (Group algebra of the Dihedral group DtD_t over F). =([Dt],⋅) A= (F[D_t],· ), with Dt=(r0,…,rt−1,s0,…,st−1)D_t=(r_0,…,r_t-1,s_0,…,s_t-1) the group of symmetries of a regular t-gon, where each rir_i denotes the rotation of angle 2πi/t2π i/t and each sis_i the reflection across the axis passing through vertex i (the axis at angle πi/tπ i/t). The group composition is given by ri∘rj=r(i+j)%t,ri∘sj=s(i+j)%t,si∘rj=s(i−j)%t,si∘sj=r(i−j)%t∀i,j∈⟦0,t−1⟧r_i r_j=r_(i+j)\%t, r_i s_j=s_(i+j)\%t, s_i r_j=s_(i-j)\%t, s_i s_j=r_(i-j)\%t ∀ i,j∈ 0,t-1 (33) We have n=dim=|Dt|=2tn=dim_F A=|D_t|=2t. Let us index the elements of Dt=gii∈⟦0,n−1⟧D_t=\g_i\_i∈ 0,n-1 by gi=rig_i=r_i for i∈⟦0,t−1⟧i∈ 0,t-1 and gi=si−tg_i=s_i-t for i∈⟦t,n−1⟧i∈ t,n-1 . Then, for all i,j,k∈⟦0,n−1⟧i,j,k∈ 0,n-1 , the structure tensor of A in its canonical basis gii∈⟦0,n−1⟧\g_i\_i∈ 0,n-1 is given by ijk=δk,(i+j)%tif 0≤i,j<tsince gi∘gj=rj∘ri=r(i+j)%t=g(i+j)%tδk,t+(i+j−t)%tif 0≤i<t,t≤j<2tsince gi∘gj=ri∘sj−t=s(i+j−t)%t=gt+(i+j−t)%tδk,t+(i−t−j)%tif t≤i<2t,0≤j<tsince gi∘gj=si−t∘rj=s(i−t−j)%t=gt+(i−t−j)%tδk,((i−t)−(j−t))%tif t≤i,j<2tsince gi∘gj=si−t∘sj−t=r(i−t−j+t)%t=g(i−t−j+t)%t split C_ijk&= \ array[]l _k,(i+j)\%t& if 0≤ i,j<t& since g_i g_j=r_j r_i=r_(i+j)\%t=g_(i+j)\%t\\[5.69054pt] _k,t+(i+j-t)\%t& if 0≤ i<t,\ t≤ j<2t& since g_i g_j=r_i s_j-t=s_(i+j-t)\%t=g_t+(i+j-t)\%t\\[5.69054pt] _k,t+(i-t-j)\%t& if t≤ i<2t,0≤ j<t& since g_i g_j=s_i-t r_j=s_(i-t-j)\%t=g_t+(i-t-j)\%t\\[5.69054pt] _k,((i-t)-(j-t))\%t& if t≤ i,j<2t& since g_i g_j=s_i-t s_j-t=r_(i-t-j+t)\%t=g_(i-t-j+t)\%t array . split Example B.11 (Group algebra of the symmetric group StS_t over F). =([St],⋅) A= (F[S_t],· ). The elements of [St]F[S_t] can be seen as endomorphisms of tF^t and can be written =∑σ∈Stσσu= _σ∈ S_tu_σ, i.e. u takes an element of tF^t, applies all the permutations of StS_t to it, then makes a linear combination of these permutations with coefficients (σ)σ∈St(u_σ)_σ∈ S_t in F. The product ⋅· is define as (∑σ∈Stσσ)⋅(∑π∈Stππ)=∑σ,π∈Stσπ(σ∘π)=∑γ∈St(∑σ∘π=γσπ)γ ( _σ∈ S_tu_σ )· ( _π∈ S_tv_π )= _σ,π∈ S_tu_σv_π (σ π )= _γ∈ S_t ( _σ π=γu_σv_π )γ, where ∘ is the composition of permutations. We have n=dim=|St|=t!n=dim_F A=|S_t|=t!. B.5 Representation of FDA Structure-like groups have representations with respect to their elements and the operators acting on them. Definition B.13. A representation of a group (G,∘)(G, ) over a field F is a group homomorphism ρ:G→GLm()ρ:G _m(F) such that ρ(g∘h)=ρ(g)ρ(h)∀g,h∈Gρ(g h)=ρ(g)ρ(h)\ ∀ g,h∈ G and ρ(e)=mρ(e)=I_m, where e is the identity of G. For example, any cyclic group of order p generated by g has the following 2-dimensional irreducible representation: ρ(gk)=(cos(2πkp)−sin(2πkp)sin(2πkp)cos(2πkp))∀k∈⟦0,p⟧ρ(g^k)= pmatrix ( 2π kp )&- ( 2π kp )\\ ( 2π kp )& ( 2π kp ) pmatrix\ ∀ k∈ 0,p (34) Each element gkg^k is represented by the angle rotation 2πk/p2π k/p. An example of a finite cyclic group of order p is the additive group (p,+)(F_p,+) for p a prime integer. Definition B.14. The representation of an F-algebra (,⋅)( A,·) involves a homomorphism ρ from A to the algebra of matrices (Example B.6), preserving both the linear and the multiplicative structures, i.e. ρ(α+β)=αρ()+βρ()ρ( + )=αρ(u)+βρ(v) and ρ(⋅)=ρ()ρ()ρ(u·v)=ρ(u)ρ(v) for all ,∈u,v∈ A and α,β∈α,β . When A is unital, it is also required that ρ(1)=ρ(1_ A)=I, the identity matrix. This notion of algebra representation is central to the interpretation of the results of this paper. However, the theory of algebra representations is somewhat more abstract than that of groups, involving concepts such as (right or left) modules of algebra, semi-simplicity, and others. Nevertheless, the picture becomes less abstract (though still difficult) if we work directly with the structure tensor of the algebra. Let us consider the representations of an nnF-FDA (,⋅)( A,·) over F itself, of dimension m∈ℕ∗m ^*. From the Definition B.14, we see that it is necessary and sufficient (Proposition B.15) to find a representation i:=ρ((i))∈m×m R_i:=ρ(a^(i)) ^m× m of the elements of a basis B=(i)i∈[n]B=\a^(i)\_i∈[n] of A in order to represent all other elements using ρ(∑k=1nαk(k))=∑k=1nαkk∀(α1,⋯,αn)∈nρ ( _k=1^n _ka^(k) )= _k=1^n _k R_k\ ∀( _1,·s, _n) ^n (35) In this way, we always have ρ(α+β)=αρ()+βρ()ρ( + )=αρ(u)+βρ(v) for all ,∈u,v∈ A and α,β∈α,β . To also ensure that ρ(⋅)=ρ()ρ()∀,∈ρ(u·v)=ρ(u)ρ(v)\ ,v∈ A, it is necessary and sufficient (Propositon B.16) that Pi,j():=ij−∑k=1nijk(B)k=0∀i,j∈[n]P_i,j( R):= R_i R_j- _k=1^n C^(B)_ijk R_k=0\ ∀ i,j∈[n] (36) That is, Pi,jl,r():=∑s=1milsjsr−∑k=1nijk(B)klr=0∀i,j∈[n];l,r∈[m]P_i,j^l,r( R):= _s=1^m R_ils R_jsr- _k=1^n C^(B)_ijk R_klr=0\ ∀ i,j∈[n];\;l,r∈[m] (37) Proposition B.15. Let (,⋅)( A,·) be an nnF-FDA. For all representation ρ and all basis B=(i)i∈[n]B=\a^(i)\_i∈[n] of A, we have ρ(∑k=1nαk(k))=∑k=1nαkρ((k))∀(α1,⋯,αn)∈nρ ( _k=1^n _ka^(k) )= _k=1^n _kρ (a^(k) )\ ∀( _1,·s, _n) ^n and ρ((i))ρ((j))=∑k=1nijk(B)ρ((k))∀i,j∈[n]ρ (a^(i) )ρ (a^(j) )= _k=1^n C^(B)_ijkρ (a^(k) )\ ∀ i,j∈[n]. Proof. ρ(∑k=1nαk(k))=∑k=1nαkρ((k))∀α∈nρ ( _k=1^n _ka^(k) )= _k=1^n _kρ (a^(k) )\ ∀α ^n since ρ is an algebra homomorphism. For all i,j∈[n]i,j∈[n] : ρ((i))ρ((j))=ρ((i)⋅(j)) since ρ is an algebra homomorphism=ρ(∑k=1nijk(B)(k)) by the definition of (B)=∑k=1nijk(B)ρ((k)) splitρ (a^(i) )ρ (a^(j) )&=ρ (a^(i)·a^(j) ) since $ρ$ is an algebra homomorphism\\ &=ρ ( _k=1^n C^(B)_ijka^(k) ) by the definition of $ C^(B)$\\ &= _k=1^n C^(B)_ijkρ (a^(k) ) split (38) ∎ Proposition B.16. Let (,⋅)( A,·) be an nnF-FDA with structure tensor ∈n×n×n C ^n× n× n in B=(i)i∈[n]B=\a^(i)\_i∈[n]. Fix m∈ℕ∗m ^* and ∈n×m×m R ^n× m× m. Set k=k,:,:∈m×m∀k∈[n] R_k= R_k,:,: ^m× m\ ∀ k∈[n], and define the linear map ρ:→ℳm()ρ: A _m(F) by ρ(∑k=1nαk(k)):=∑k=1nαkk∀(α1,⋯,αn)∈nρ ( _k=1^n _ka^(k) ):= _k=1^n _k R_k\ ∀( _1,·s, _n) ^n (39) Then ρ is an algebra homomorphism if and only if ij=∑k=1nijkk∀i,j∈[n] R_i R_j= _k=1^n C_ijk R_k ∀ i,j∈[n] (40) If A is unital with 1=∑i=1nλi(i)1_ A= _i=1^n _ia^(i), then the additional condition ρ(1)=mρ(1_ A)=I_m is equivalent to ∑i=1nλii=m _i=1^n _i R_i=I_m (41) Proof. (⟹ ) Suppose ρ is an algebra homomorphism. Then, we have for all i,j∈[n]i,j∈[n] : ij=ρ((i))ρ((j)) by the definition of ρ=ρ((i)⋅(j)) since ρ is an algebra homomorphism=ρ(∑k=1nijk(k)) by the definition of (Equation (12))=∑k=1nijkk by the definition of ρ split R_i R_j&=ρ(a^(i))ρ(a^(j)) by the definition of $ρ$\\ &=ρ (a^(i)·a^(j) ) since $ρ$ is an algebra homomorphism\\ &=ρ ( _k=1^n C_ijka^(k) ) by the definition of $ C$ (Equation~ eq:structure_tensor)\\ &= _k=1^n C_ijk R_k by the definition of $ρ$ split (42) (⟸ ) Assume (40) holds. For all =∑i=1ni(i)u= _i=1^nu_ia^(i) and =∑i=1ni(i)v= _i=1^nv_ia^(i), we have ρ()ρ()=(∑i=1nii)(∑i=1nii) by the definition of ρ=∑i,j=1nijij=∑i,j=1nij∑k=1nijkk (Equation (40))=∑k=1n(∑i,j=1nijijk)k=ρ(∑k=1n(∑i,j=1nijijk)(k)) by the definition of ρ=ρ(⋅) (Equation (13)) splitρ(u)ρ(v)&= ( _i=1^nu_i R_i ) ( _i=1^nv_i R_i ) by the definition of $ρ$\\ &= _i,j=1^nu_iv_j R_i R_j\\ &= _i,j=1^nu_iv_j _k=1^n C_ijk R_k (Equation~ eq:R_iR_j=C_kR_k)\\ &= _k=1^n ( _i,j=1^nu_iv_j C_ijk ) R_k\\ &=ρ ( _k=1^n ( _i,j=1^nu_iv_j C_ijk )a^(k) ) by the definition of $ρ$\\ &=ρ (u·v ) (Equation~ eq:uv=Cuv) split (43) Therefore, ρ is multiplicative. Since it is a F-linear map, this proves that it is a homomorphism of F-algebras. ∎ From this proposition, it follows that we can find a solution ∈n×m×m R ^n× m× m to Pi,j():=ij−∑k=1nijk(B)k=0∀i,j∈[n]∑i=1nλi(B)i=m if is unital with 1=∑i=1nλi(B)(i) split&P_i,j( R):= R_i R_j- _k=1^n C^(B)_ijk R_k=0\ ∀ i,j∈[n]\\ & _i=1^nλ^(B)_i R_i=I_m if $ A$ is unital with $1_ A= _i=1^nλ^(B)_ia^(i)$ split (44) in order to obtain a representation of size m of A over F, or more generally over any field into which F embeds. In particular, even if =ℤ/pℤF=Z/pZ, one may regard its elements as integer representatives and solve the same equations over ℝR or ℂC, so that real (or complex) matrix representations remain valid. It should be noted that if we switch from the basis B to another basis B~ B, then a solution R in B to the above system of equations becomes ×1⊤ R×_1P in B~ B, with ∈n×nP ^n× n the basis change matrix from B to B~ B. Proposition B.17. Let C and ~ C be the structure tensors of an nnF-FDA A with respect to two bases B=(i))i∈[n]B=\a^(i))\_i∈[n] and B~=~(i)i∈[n] B=\ a^(i)\_i∈[n] respectively. Let ∈n×nP ^n× n be the basis change matrix from B to B~ B, i.e. ~(i)=∑k=1nki(k)∀i∈[n] a^(i)= _k=1^nP_kia^(k)\ ∀ i∈[n]. For all ∈n×m×m R ^n× m× m, by defining ~:=×1⊤ R:= R×_1P , which is equivalent to =~×1−1⊤ R= R×_1P^-1 , we have: • ij=∑k=1nijkk∀i,j∈[n]⇔~i~j=∑k=1n~ijk~k∀i,j∈[n] R_i R_j= _k=1^n C_ijk R_k\ ∀ i,j∈[n] R_i R_j= _k=1^n C_ijk R_k\ ∀ i,j∈[n]; • ∑i=1nλii=m⇔∑i=1nλ~i~i=m _i=1^n _i R_i=I_m _i=1^n λ_i R_i=I_m if further A is unital with 1=∑i=1nλi(i)=∑i=1nλ~i~(i)1_ A= _i=1^n _ia^(i)= _i=1^n λ_i a^(i). Proof. Let ∈n×m×m R ^n× m× m. Set ~=×1⊤ R= R×_1P . First, note that this is equivalent to =~×1−1⊤ R= R×_1P^-1 since (×1⊤×1−1⊤)(1)=−1⊤(×1⊤)(1)=−1⊤⊤(1)=(1)( R×_1P ×_1P^-1 )_(1)=P^-1 ( R×_1P )_(1)=P^-1 P R_(1)= R_(1) and (~×1−1⊤×1⊤)(1)=⊤−1⊤~(1)=~(1)( R×_1P^-1 ×_1P )_(1)=P P^-1 R_(1)= R_(1) (Equation (8)). Assume ij=∑k=1nijkk∀i,j∈[n] R_i R_j= _k=1^n C_ijk R_k\ ∀ i,j∈[n]. Then, for all i,j∈[n]i,j∈[n], we have: ~i~j=(∑l=1nlil)(∑r=1nrjr)=∑l=1n∑r=1nlirjlr=∑l=1n∑r=1nlirj∑s=1nlrss=∑s=1n∑l=1n∑r=1nlrslirjs=∑s=1n∑l=1n∑r=1nlrslirj∑k=1n(−1)ks~k=∑k=1n(∑ℓ=1n∑r=1n∑s=1nlrs(⊤)il(⊤)jr(−1)ks)~k=∑k=1n(×1⊤×2⊤×3−1)ijk~k=∑k=1n~ijk~k (Proposition B.3) split R_i R_j&= ( _l=1^nP_li R_l ) ( _r=1^nP_rj R_r )= _l=1^n _r=1^nP_liP_rj R_l R_r\\ &= _l=1^n _r=1^nP_liP_rj _s=1^n C_lrs R_s= _s=1^n _l=1^n _r=1^n C_lrsP_liP_rj R_s\\ &= _s=1^n _l=1^n _r=1^n C_lrsP_liP_rj _k=1^n(P^-1)_ks R_k\\ &= _k=1^n ( _ =1^n _r=1^n _s=1^n C_lrs(P )_il(P )_jr(P^-1)_ks ) R_k\\ &= _k=1^n ( C×_1P ×_2P ×_3P^-1 )_ijk R_k\\ &= _k=1^n C_ijk R_k (Proposition~ proposition:algebra_generate_by_C_change_of_basis) split (45) Further, assume that A is unital with 1=∑i=1nλi(i)=∑i=1nλ~i~(i)1_ A= _i=1^n _ia^(i)= _i=1^n λ_i a^(i). We have λ~=−1λ λ=P^-1λ. So ∑i=1nλii=m⟺∑i=1nλi∑k=1n(−1)ki~i=m⟺∑k=1n(∑i=1n(−1)kiλi)~k=m⟺∑k=1n(−1λ)k~k=m⟺∑k=1nλ~k~k=m split _i=1^n _i R_i=I_m _i=1^n _i _k=1^n(P^-1)_ki R_i=I_m& _k=1^n ( _i=1^n(P^-1)_ki _i ) R_k=I_m\\ & _k=1^n (P^-1λ )_k R_k=I_m\\ & _k=1^n λ_k R_k=I_m split (46) Similarly, assume ~i~j=∑k=1n~ijk~k∀i,j∈[n] R_i R_j= _k=1^n C_ijk R_k\ ∀ i,j∈[n]. Then, for all i,j∈[n]i,j∈[n], we have (the derivation steps are similar to those above) ij=∑k=1n(~×1−1⊤×2−1⊤×3)ijkk=∑k=1nijkk R_i R_j= _k=1^n ( C×_1P^-1 ×_2P^-1 ×_3P )_ijk R_k= _k=1^n C_ijk R_k. ∎ We have a system of n2m2n^2m^2 (for a non-unital A) or (n2+1)m2(n^2+1)m^2 (for a unital A) non-linear equations in nm2nm^2 variables, so in general, overdetermined. Solutions form an algebraic variety. For a non-unital A, the trivial solution is =0n×m×m R=0_n× m× m, the zero tensor. For a unital A, there is no trivial solution. It is worth asking what is the smallest m (or the values of m) for which this system admits a non-trivial solution., i.e., a solution to P()=∑i,j‖Pi,j()‖F2=∑i,j∑l,r(Pi,jl,r())2=0subject to∑i=1n‖i‖F2≠0∑i=1nλi(B)i=m if is unital with 1=∑i=1nλi(B)(i) split&P( R)= _i,j\|P_i,j( R)\|_F^2= _i,j _l,r (P_i,j^l,r( R) )^2=0 to _i=1^n\| R_i\|_F^2≠ 0\\ & _i=1^nλ^(B)_i R_i=I_m if $ A$ is unital with $1_ A= _i=1^nλ^(B)_ia^(i)$ split (47) For associatives nnF-FDA, the smallest m is less than or equal to n, since the tensor ∈n×n×n R ^n× n× n defined by i=i⊤∀i∈[n] R_i= C_i ∀ i∈[n] is solution to (44) (Proposition B.18). For non-unital FDA, if there is a solution for a certain m, then there is one for all p≥mp≥ m. In fact, if ∈n×m×m R ^n× m× m is solution to Equation (44), then for all ∈p×mA ^p× m and ∈m×pB ^m× p such that =mBA=I_m, ~=[i]i∈[n]∈n×p×p R= [A R_iB ]_i∈[n] ^n× p× p is also solution to Equation (44) (Proposition B.19). But this is false for unital FDA in general. If ∑i=1nλii=m _i=1^n _i R_i=I_m, then we have ∑i=1nλii=(∑i=1nλii)= _i=1^n _iA R_iB=A ( _i=1^n _i R_i )B=AB. For this to equals pI_p, we need p=mp=m. Describing the solution set of (44) in full generality is challenging. A basic invariance is simultaneous conjugation: if =[1,…,n] R=[ R_1,…, R_n] solves (44) for all i,ji,j, then so does [1−1,…,n−1][S R_1S^-1,…,S R_nS^-1] for any ∈GLm()S _m(F) (Corollary B.20). Proposition B.18 (Left-regular representation). If (,⋅)( A,·) is an associative nnF-FDA with structure tensor ∈n×n×n C ^n× n× n in B=(i)i∈[n]B=\a^(i)\_i∈[n], then the tensor ∈n×n×n R ^n× n× n defined by i:=i⊤∀i∈[n] R_i:= C_i ∀ i∈[n] satisfies ij=∑k=1nijkk=0∀i,j∈[n], and ∑i=1nλii=n if is unital with 1=∑i=1nλi(i) split& R_i R_j= _k=1^n C_ijk R_k=0\ ∀ i,j∈[n], and _i=1^n _i R_i=I_n if $ A$ is unital with $1_ A= _i=1^n _ia^(i)$ split (48) Proof. Assume (,⋅)( A,·) is an associative nnF-FDA. That is (Proposition B.5) ∑k=1nijkklm=∑k=1nikmjlk∀i,j,l,m∈[n]⟺∑k=1nijk(k⊤)ml=(i⊤j⊤)ml∀i,j,l,m∈[n]⟺∑k=1nijkk⊤=i⊤j⊤∀i,j∈[n]⟺∑k=1nijkk=ij∀i,j∈[n] split _k=1^n C_ijk C_klm= _k=1^n C_ikm C_jlk\ ∀ i,j,l,m∈[n]& _k=1^n C_ijk( C_k )_ml=( C_i C_j )_ml\ ∀ i,j,l,m∈[n]\\ & _k=1^n C_ijk C_k = C_i C_j \ ∀ i,j∈[n]\\ & _k=1^n C_ijk R_k= R_i R_j\ ∀ i,j∈[n] split (49) If further A is unital, then ×1λ=∑i=1nλii=n C×_1λ= _i=1^n _i C_i=I_n (Proposition B.5), which is equivalent to ∑i=1nλii=n _i=1^n _i R_i=I_n. ∎ Proposition B.19 (Invariance of the solution set). Let ∈n×n×n C ^n× n× n. For all ∈n×m×m R ^n× m× m, if ij=∑k=1nijkk∀i,j∈[n] R_i R_j= _k=1^n C_ijk R_k\ ∀ i,j∈[n], then (i)(j)=∑k=1nijk(k)∀i,j∈[n] (A R_iB ) (A R_jB )= _k=1^n C_ijk(A R_kB)\ ∀ i,j∈[n] for all for all ∈p×mA ^p× m and ∈m×pB ^m× p such that =mBA=I_m. Corollary B.20 (Conjugacy invariance of the solution set). Let ∈n×n×n C ^n× n× n. For all ∈n×m×m R ^n× m× m, if ij=∑k=1nijkk∀i,j∈[n] R_i R_j= _k=1^n C_ijk R_k\ ∀ i,j∈[n], then (i−1)(j−1)=∑k=1nijk(k−1)∀i,j∈[n] (S R_iS^-1 ) (S R_jS^-1 )= _k=1^n C_ijk(S R_kS^-1)\ ∀ i,j∈[n] for all ∈GLm()S _m(F). If further ∑i=1nλii=m _i=1^n _i R_i=I_m, then ∑i=1nλii−1=m _i=1^n _iS R_iS^-1=I_m. It is therefore natural to work up to the equivalence relation defined on n×m×mF^n× m× m by the following equation, i.e., to consider orbits under simultaneous conjugation. ∼~⟺∃∈GLm()such that~i=i−1∀i∈[n] R R _m(F)\ such that\ R_i=S R_iS^-1\ \ ∀ i∈[n] (50) One might hope this allows choosing a diagonal normal form. However, this would require a single change of basis that diagonalizes all i R_i at once. In general the i R_i need not commute or be simultaneously diagonalizable, so this reduction is not available without additional assumptions. Nevertheless, let us imagine we restrict ourselves to diagonal solutions. In that case, writing i=diag(i(1),…,i(m)) R_i=diag(r_i^(1),…,r_i^(m)) for all i∈[n]i∈[n], the defining system (Equation (44)) decouples coordinate-wise. For each t∈[m]t∈[m], the scalars (1(t),…,n(t))(r_1^(t),…,r_n^(t)) must satisfy i(t)j(t)=∑k=1nijkk(t)∀i,j∈[n],∑i=1nλii(t)=1 if is unital split&r_i^(t)r_j^(t)= _k=1^n C_ijkr_k^(t) ∀ i,j∈[n], _i=1^n _ir_i^(t)=1 if A is unital split (51) Thus, the diagonal ansatz reduces the matrix problem to a family of scalar problems, one for each diagonal entry. A diagonal solution of size m is obtained by picking m points in ():=∈n:ij=∑kijkk∀(i,j)∈[n]2and∑iλii=1if unitality holdsS( C):= \r ^n:r_ir_j= _k C_ijkr_k\ ∀(i,j)∈[n]^2\ and\ _i _ir_i=1\ if unitality holds \ (52) and placing them on the diagonal (conjugation by permutation matrices only reorders the diagonal). Thus, diagonal solutions correspond to ()m/SmS( C)^m/S_m666The quotient /Sm/S_m indicates that two m-tuples which differ only by a permutation of their coordinates correspond to the same diagonal solution.. In particular, a nontrivial diagonal solution exists if and only if ()∖0≠∅S( C) \0\≠ . Hence, the minimal matrix size for a diagonal solution is m=1m=1 whenever ()S( C) contains a nonzero point; otherwise, no diagonal solution exists for any m. While the defining equations for representations are explicit (see (44) and the diagonal reduction (51)), a general description of their solution set (e.g., orbit structure, invariances, dimensions, and stratification) would require tools from algebraic geometry, invariant theory, or representation theory. For this reason, we now provide a few examples of representation for the algebras of Section B.3 and proceed to the next section, which addresses the problem of learning algebras using deep learning models. Example B.12 (Complex Numbers). For the algebra of complex numbers (Example B.3) with =ℝF=R and (1),(2)=1,\a^(1),a^(2)\=\1,i\, the relations are 12=1,12=21=2,22=−1,1=m since 1=(1) split& R_1^2= R_1,\ R_1 R_2= R_2 R_1= R_2,\ R_2^2=- R_1, R_1=I_m since 1_ A=a^(1) split (53) Therefore 1=m R_1=I_m (representation of multiplication by 11 in ℂC for m=2m=2) and 22=−m R_2^2=-I_m. This requires m to be even, because over ℝR there is no odd-dimensional m×m× m real matrix squaring to −m-I_m. The minimal case is m=2m=2 with 2=2⊤=[[0−1],[10]]=−2 R_2= C_2 = bmatrix bmatrix0&-1 bmatrix, bmatrix1&0 bmatrix bmatrix=- C_2 (Equation (2)), which is the standard real representation of multiplication by i. Writing m=2km=2k, the general solution is 2=(k⊗2⊤)−1 R_2=S(I_k C_2 )S^-1 for an arbitrary invertible real matrix ∈GLm(ℝ)S _m(R). Equivalently, 2 R_2 is any real matrix with minimal polynomial x2+1x^2+1. If one requires 2 R_2 to be orthogonal, then 2=(k⊗2⊤)⊤ R_2=Q(I_k C_2 )Q for any ∈O(m)Q∈ O(m), with O(m)O(m) the general orthogonal group. With =ℤ/pℤF=Z/pZ for p prime, we have 221=(−1)%p=p−1 C_221=(-1)\%p=p-1, so the relation 22=−1=−m R_2^2=- R_1=-I_m over ℝR becomes 22=(p−1)m R_2^2=(p-1)\,I_m. Since p−1>0p-1>0, the polynomial x2−(p−1)=(x−p−1)(x+p−1)x^2-(p-1)=(x- p-1)(x+ p-1) has distinct real roots, hence any real solution 2 R_2 is diagonalizable over ℝR with eigenvalues in ±p−1\± p-1\. Equivalently, 2=(p−1)1/2 R_2=(p-1)^1/2J with 2=mJ^2=I_m i.e., 2 R_2 is p−1 p-1 times an involution. There is no parity restriction on m (unlike the =ℝF=R case). A convenient normal form is 2=(p−1)1/2diag(ϵ)−1 R_2=(p-1)^1/2Sdiag ( ε )S^-1 for any ∈GLm(ℝ)S _m(R) and signs ϵ∈±1m ε∈\± 1\^m. If one also requires 2 R_2 to be symmetric (hence orthogonally diagonalizable), then 2=(p−1)1/2diag(ϵ)⊤ R_2=(p-1)^1/2Qdiag ( ε )Q for any ∈O(m)Q∈ O(m). Example B.13 (Dual Numbers). For the algebra of dual numbers (Example B.4) with (1),(2)=1,ε\a^(1),a^(2)\=\1, \, 1=m R_1=I_m and 22=0 R_2^2=0 (corresponding to the dual number ε ). This yields nontrivial solutions whenever m≥2m≥ 2, since square-zero (nilpotent) matrices exist, e.g. 2=⊤∈m×m R_2=uv ^m× m for any ,∈mu,v ^m such that ⊤=0u v=0. Example B.14 (Polynomials modulo xnx^n). =(n−1[x],⋅) A= (F_n-1[x],· ) with basis (i)=xi∀i∈⟦0,n−1⟧a^(i)=x^i\ ∀ i∈ 0,n-1 and product xi⋅xj=x(i+j)modnx^i· x^j=x^(i+j) n (Example B.5). The structure constants are ijk=δk,(i+j)%n∀i,j,k∈⟦0,n−1⟧ C_ijk= _k,(i+j)\%n\ ∀ i,j,k∈ 0,n-1 , so we have the relations ij=(i+j)%n∀i,j∈⟦0,n−1⟧,0=m since 1=(0) split& R_i R_j= R_(i+j)\%n\ ∀ i,j∈ 0,n-1 , R_0=I_m since 1_ A=a^(0) split (54) Setting :=1A:= R_1, (54) yields i+1=i R_i+1=A R_i and hence i=i R_i=A^i for all i. In particular, n=n=0=mA^n= R_n= R_0=I_m. Conversely, for any ∈ℳm()A _m(F) with n=mA^n=I_m, the assignment i:=i∀i∈⟦0,n−1⟧ R_i:=A^i\ ∀ i∈ 0,n-1 solves (54). In fact, since n=mA^n=I_m, we have for all k=qn+rk=qn+r with q≥0q≥ 0 and r=k%n∈⟦0,n−1⟧r=k\%n∈ 0,n-1 (Euclidean division), k=qn+r=(n)qr=(m)qr=r=k%nA^k=A^qn+r=(A^n)^qA^r=(I_m)^qA^r=A^r=A^k\%n. Therefore, size-m solutions are in bijection with matrices A satisfying n=mA^n=I_m, via ↦(i=i)i=0n−1A ( R_i=A^i)_i=0^n-1. Over ℝR, a faithful (i.e. injective) size-n representation is obtained by choosing A to be the n×n× n cyclic shift matrix =(00⋯0110⋯0001⋱⋮⋱000⋯010)A= pmatrix0&0&·s&0&1\\ 1&0&·s&0&0\\ 0&1& & & \\ & & &0&0\\ 0&·s&0&1&0 pmatrix (55) Since (k)=(k+1)∀k∈[n−1]Ae^(k)=e^(k+1)\ ∀ k∈[n-1] and (n)=(1)Ae^(n)=e^(1), we have n(k)=(k)∀k∈[n]A_n^ne^(k)=e^(k)\ ∀ k∈[n]. Therefore n=nA^n=I_n. Define ρ(xi)=i∀i∈⟦0,n−1⟧ρ(x^i)=A^i\ ∀ i∈ 0,n-1 . Then for all i,j∈⟦0,n−1⟧i,j∈ 0,n-1 , ρ(xi)ρ(xj)=ij=i+j=(i+j)%n=ρ(x(i+j)%n)ρ(x^i)ρ(x^j)=A^iA^j=A^i+j=A^(i+j)\%n=ρ (x^(i+j)\%n ). So ρ is an algebra homomorphism. This is the regular (cyclic) real representation. More generally, any real solution arises from some ∈m×mA ^m× m with n=mA^n=I_m by j=j R_j=A^j. Over ℝR such A is real-similar to a block diagonal matrix with 1×11× 1 blocks at ±1± 1 (when n is even) and 2×22× 2 rotation blocks corresponding to conjugate pairs e±2πk/ne^± 2 /n (Equation (34)). If fact, if ∈ℝm×mA ^m× m satisfies n=mA^n=I_m, then every eigenvalue λ of A solves λn=1λ^n=1, i.e. λ=e2πik/nλ=e^2 /n for some k∈⟦0,n−1⟧k∈ 0,n-1 . The real roots among these are λ=1λ=1 (always) and, when n is even, λ=−1λ=-1; these give 1×11× 1 Jordan blocks [1][1] and (if n is even) [−1][-1]. All remaining roots occur in complex-conjugate pairs e±iθe θ with θ=2πk/nθ=2π k/n. Over ℝR, each such conjugate pair corresponds to a 2×22× 2 real block that acts as a rotation by angle θ. Example B.15 (Square matrices of size n). =(ℳn(),⋅) A= (M_n(F),· ), with canonical matrix unit basis B=((q−1)n+r)(q,r)∈[n]2B=\a^((q-1)n+r)\_(q,r)∈[n]^2, where each ((q−1)n+r)a^((q-1)n+r) has 11_F at position (q,r)∈[n]2(q,r)∈[n]^2 and 00_F everywhere (Example B.6). Since ((q1−1)n+r1)⋅((q2−1)n+r2)=δq2r1((q1−1)n+r2)a^((q_1-1)n+r_1)·a^((q_2-1)n+r_2)= _q_2r_1a^((q_1-1)n+r_2), the structure constants of A in B are (q1−1)n+r1,(q2−1)n+r2,(q3−1)n+r3=δq2r1δq1q3δr2r3 C_(q_1-1)n+r_1,(q_2-1)n+r_2,(q_3-1)n+r_3= _q_2r_1 _q_1q_3 _r_2r_3. The representation equations, therefore, read (q1−1)n+r1(q2−1)n+r2=∑q,r=1nδq2r1δq1qδr2r(q−1)n+r=δq2r1(q1−1)n+r2∀q1,r1,q2,r2∈[n]∑q,r=1nδqr(q−1)n+r=∑i=1n(i−1)n+i=m since 1=n=∑q,r=1nδqr((q−1)n+r) split& R_(q_1-1)n+r_1 R_(q_2-1)n+r_2= _q,r=1^n _q_2r_1 _q_1q _r_2r R_(q-1)n+r= _q_2r_1 R_(q_1-1)n+r_2 ∀ q_1,r_1,q_2,r_2∈[n]\\ & _q,r=1^n _qr R_(q-1)n+r= _i=1^n R_(i-1)n+i=I_m since 1_ A=I_n= _q,r=1^n _qra^((q-1)n+r) split (56) Define m=nm=n and set, for each (q,r)∈[n]2(q,r)∈[n]^2, (q−1)n+r=((q−1)n+r)∈ℝn×n R_(q-1)n+r=a^((q-1)n+r) ^n× n. Then (q1−1)n+r1(q2−1)n+r2=δq2r1((q1−1)n+r2)=δq2r1(q1−1)n+r2∀q1,r1,q2,r2∈[n]∑i=1n(i−1)n+i=∑i=1n((i−1)n+i)=n split& R_(q_1-1)n+r_1 R_(q_2-1)n+r_2= _q_2r_1a^((q_1-1)n+r_2)= _q_2r_1 R_(q_1-1)n+r_2\ ∀ q_1,r_1,q_2,r_2∈[n]\\ & _i=1^n R_(i-1)n+i= _i=1^na^((i-1)n+i)=I_n split (57) So (56) holds. This gives the standard left action ρ:ℳn()→ℳn()ρ:M_n(F) _n(F), ρ()=ρ(A)=A. For a general size m=κnm=κ n with κ∈ℕκ , set (q−1)n+r=((q−1)n+r)⊗κ∈κn×κn R_(q-1)n+r=a^((q-1)n+r) _κ ^κ n×κ n. We have (q1−1)n+r1(q2−1)n+r2=(((q1−1)n+r1)((q2−1)n+r2))⊗κ=δq2r1((q1−1)n+r2)⊗κ=δq2r1(q1−1)n+r2∑i=1n(i−1)n+i=∑i=1n((i−1)n+i)⊗κ=n⊗κ=κn split& R_(q_1-1)n+r_1 R_(q_2-1)n+r_2= (a^((q_1-1)n+r_1)a^((q_2-1)n+r_2) ) _κ= _q_2r_1a^((q_1-1)n+r_2) _κ= _q_2r_1 R_(q_1-1)n+r_2\\ & _i=1^n R_(i-1)n+i= _i=1^na^((i-1)n+i) _κ=I_n _κ=I_κ n split (58) Thus (56) holds with m=κnm=κ n. By conjugacy invariance (Corollary B.20), the family (q−1)n+r:=(((q−1)n+r)⊗κ)−1 R_(q-1)n+r:=S(a^((q-1)n+r) _κ)S^-1 is again a solution for any ∈GLκn()S _κ n(F). In this way, one obtains all size-m=κnm=κ n solutions up to simultaneous conjugation. Example B.16 (Square matrices of size n with the commutator). If we replace matrix multiplication AB in =(ℳn(),⋅) A= (M_n(F),· ) with the matrix commutator [,]=−[A,B]=AB-BA, then (q1−1)n+r1,(q2−1)n+r2,(q3−1)n+r3=δq2r1δq1q3δr2r3−δq1r2δq2q3δr1r3 C_(q_1-1)n+r_1,(q_2-1)n+r_2,(q_3-1)n+r_3= _q_2r_1 _q_1q_3 _r_2r_3- _q_1r_2 _q_2q_3 _r_1r_3 (Example B.8). The representation equations, therefore, read (q1−1)n+r1(q2−1)n+r2=δq2r1(q1−1)n+r2−δq1r2(q2−1)n+r1∀q1,r1,q2,r2∈[n] split& R_(q_1-1)n+r_1 R_(q_2-1)n+r_2= _q_2r_1 R_(q_1-1)n+r_2- _q_1r_2 R_(q_2-1)n+r_1\ ∀ q_1,r_1,q_2,r_2∈[n] split (59) Fix m≥2m≥ 2 and choose any nonzero matrix ∈m×mN ^m× m with 2=0N^2=0. Define (q−1)n+r=δqr∀(q,r)∈[n]2 R_(q-1)n+r= _qrN\ ∀(q,r)∈[n]^2. For all q1,r1,q2,r2∈[n]q_1,r_1,q_2,r_2∈[n], (q1−1)n+r1(q2−1)n+r2=(δq1r1)(δq2r2)=δq1r1δq2r22=0 R_(q_1-1)n+r_1 R_(q_2-1)n+r_2=( _q_1r_1N)( _q_2r_2N)= _q_1r_1 _q_2r_2N^2=0 (60) and δq2r1(q1−1)n+r2−δq1r2(q2−1)n+r1=δq2r1δq1r2−δq1r2δq2r1=0 _q_2r_1 R_(q_1-1)n+r_2- _q_1r_2 R_(q_2-1)n+r_1= _q_2r_1 _q_1r_2N- _q_1r_2 _q_2r_1N=0 (61) So R satisfies the system (59). This yields nontrivial solutions whenever m≥2m≥ 2, since square-zero (nilpotent) matrices exist, e.g. =⊤∈m×mN=uv ^m× m for any ,∈mu,v ^m such that ⊤=0u v=0. Any simultaneous conjugate (q−1)n+r−1S R_(q-1)n+rS^-1 for ∈GLm()S _m(F) is again a solution, so replacing N by any conjugate −1SNS^-1 with (−1)2=0(SNS^-1)^2=0 also works. Note that for all ∈GLm()S _m(F), we have 2=0⟺(−1)2=0N^2=0 (SNS^-1)^2=0. If m=1m=1 over a field of characteristic ≠2≠ 2 (e.g. ℝR), the only solution is trivial: the equations force all scalars to be 0. Hence, the minimal m for a nontrivial solution is m=2m=2. Proposition B.21. Let ρG:G→GLm() _G:G _m(F) be a representation of a goup (G,∘)(G, ). Define the linear map ρ:[G]→ℳm(),ρ(∑i=1nαigi):=∑i=1nαiρG(gi)ρ:F[G] _m(F),\ ρ ( _i=1^n _ig_i ):= _i=1^n _i\, _G(g_i) (62) Then ρ is an F-algebra homomorphism, and hence a representation of ([G],⋅)(F[G],·). Proof. ρ is linear by definition. For all =∑igiu= _iu_ig_i and =∑jgjv= _jv_jg_j, ρ(⋅)=ρ(∑i,jij(gi∘gj))=∑i,jijρG(gi∘gj)=∑i,jijρG(gi)ρG(gj)=ρ()ρ()ρ(u·v)=ρ ( _i,ju_iv_j(g_i g_j) )= _i,ju_iv_j _G(g_i g_j)= _i,ju_iv_j _G(g_i) _G(g_j)=ρ(u)ρ(v). Finaly, ρ(1[G])=ρ(e)=mρ(1_F[G])=ρ(e)=I_m since ρG(e)=m _G(e)=I_m. ∎ Example B.17 (Group algebra of the symmetric group StS_t over F). Write n=t!n=t!. The structure tensor of =([St],⋅) A= (F[S_t],· ) in its canonical basis ((1),…,(n))≡(σ)σ∈St(a^(1),…,a^(n))≡(σ)_σ∈ S_t is ijk=((k)=(i)∘(j))∀i,j,k∈[n] C_ijk=1(a^(k)=a^(i) ^(j))\ ∀ i,j,k∈[n] (Example B.11), so the representation equations read (by abuse of notations) σiσj=σi∘σj∀σi,σj∈St R_ _i R_ _j= R_ _i _j\ ∀ _i, _j∈ S_t (63) Take m=tm=t and define σ=σ∈m×m∀σ∈St R_σ=P_σ ^m× m\ ∀σ∈ S_t, where σP_σ is the permutation matrix associated to σ, i.e. (σ)ab=1(P_σ)_ab=1 if σ(b)=aσ(b)=a and 0 otherwise (under cycle notation for permutations). Then σiσj=σiσj=σi∘σj=σi∘σj R_ _i R_ _j=P_ _iP_ _j=P_ _i _j= R_ _i _j, so (63) is satisfied. This is the standard permutation representation of StS_t on tF^t. More generally, let m=nm=n and for each σ∈Stσ∈ S_t set σ:=matrix of left multiplication by σ on [St] R_σ:=matrix of left multiplication by $σ$ on $ F[S_t]$. Explicitly, (σ)π,γ=(γ=σ∘π)∀π,γ∈St( R_σ)_π,γ=1(γ=σ π)\ ∀π,γ∈ S_t. Then σiσj=σi∘σj R_ _i R_ _j= R_ _i _j, so (63) holds. This is the left regular representation (Proposition B.18). In general, for any m≥1m≥ 1, any group representation ρ:St→GLm()ρ:S_t _m(F) gives a solution of (63) by setting σ:=ρ(σ) R_σ:=ρ(σ) (Proposition B.21). Conversely, any solution of (63) defines a group representation of StS_t. Thus, the solutions of the FDA system for [St]F[S_t] are in bijection with group representations of StS_t. Appendix C Learning Finite-Dimensional Algebra C.1 A Linear Inverse View for =ℝF=R In =ℝF=R, the problem of learning a FDA with structure tensor ∗∈n×n×n C^* ^n× n× n is similar to a matrix factorization problem with matrix (3)∗⊤∈n2×n C^* _(3) ^n^2× n (Equation (4)). Giving the measures ,∈N×nU,V ^N× n, let :=∙=[−s⊗s−]s∈[N]∈N×n2X:=V = [-V_s _s- ]_s∈[N] ^N× n^2. The training loss is ℒ()=∑s∈[N]‖(−∗)×1s×2s‖22=∑s∈[N]‖((3)−(3)∗)s‖22=‖((3)−(3)∗)⊤‖F2 splitL( C)&= _s∈[N] \| ( C- C^* )×_1U_s×_2V_s \|_2^2= _s∈[N] \| ( C_(3)- C^*_(3) )X_s \|_2^2= \|X ( C_(3)- C^*_(3) ) \|_F^2 split (64) By writing ∗=⟦∗,∗,∗⟧:=∑ℓ=1R:,ℓ∗∘:,ℓ∗∘:,ℓ∗ C^*= ^*,B^*,C^* := _ =1^RA^*_:, ^*_:, ^*_:, as the CP decomposition of rank R of ∗ C^*, we can use a parametrization =⟦,,⟧ C= ,B,C , so that (3)=(⋆)⊤ C_(3)=C(B ) . In that case, if we are interested in the global structure of ∗ C^*, we can try to evaluate the effect of the properties of the algebra A generated by ∗ C^* on the CP rank R of ∗ C^*, and thus classify which properties of this algebra increase its CP rank (and therefore make it more difficult to learn). Note that =⟦,,⟧ C= ,B,C implies (3)=(⋆)⊤ C_(3)=C(B ) and ×1×2=((⊤)⊙(⊤))∀,∈n C×_1u×_2v=C ((A u) (B v) )\ ,v ^n, so that (3)⊤=(∙)(⋆)⊤=(()⊙())⊤X C_(3) = (V )(B )C = ((VB) (UA) )C . We recall that ⊙ is the Hadamard product, ⋆ the Khatri-Rao product, ∙ the face-splitting product, and ∘ the outer product. Another way to make things simple, is to just analyze the rank r of (3)∗⊤ C^* _(3) to characterize the solvability of the problem using a parameterization (3)⊤=(L)⋯(1) C _(3)=W^(L)·sW^(1), with (L)∈ℝn2×dW^(L) ^n^2× d, (i)∈ℝd×dW^(i) ^d× d for 1<i<L1<i<L, and (1)∈ℝd×nW^(1) ^d× n. This corresponds to a linear network with L layers. That said, if we are interested in the global structure of ∗ C^*, we can try to evaluate the effect of the properties of the algebra A generated by ∗ C^* on the rank r of (3)∗⊤ C^* _(3), and thus classify which properties of this algebra increase its rank (and therefore make it more difficult to learn). For example, if ∗=⟦∗,∗,∗⟧ C^*= ^*,B^*,C^* , then (3)∗⊤=(∗⋆∗)∗⊤ C^* _(3)=(B^* ^*)C^* , so that777rank()+rank()−d2≤rank()≤min(rank(),rank()) *rank(A)+ *rank(B)-d_2≤ *rank(AB)≤ ( *rank(A), *rank(B) ) for all ∈ℝd1×d2A ^d_1× d_2 and ∈ℝd2×d3B ^d_2× d_3. rank(∗⋆∗)+rank(∗)−R≤r≤min(rank(∗⋆∗),rank(∗)) *rank(B^* ^*)+ *rank(C^*)-R≤ r≤ ( *rank(B^* ^*), *rank(C^*) ). By “making things simple,” we mean that this is a well-studied problem in the matrix setting. With L=1L=1, there is a need for ℓ∗ _* (nuclear norm) regularization (or any other form of appropriate regularization888For example, if (3)∗⊤ C^* _(3) is extremely sparse so that the notion of sparsity prevails over the notion of rank, then ℓ1 _1 is needed for generalization under gradient descent optimization (Notsawo et al., 2025).) to recover (3)∗⊤ C^* _(3) when N is large enough (Candès & Tao, 2010; Candes & Recht, 2012; Notsawo et al., 2025). But when L≥2L≥ 2 (and the initialization scale is small), there is no need for ℓ∗ _* (or any other form of regularization) to recover (3)∗⊤ C^* _(3) (Gunasekar et al., 2017; Arora et al., 2018, 2019; Gidel et al., 2019; Gissin et al., 2019; Razin & Cohen, 2020; Li et al., 2020). Increasing L implicitly biases (3)⊤ C _(3) toward a low-rank solution, which oftentimes leads to more accurate recovery for sufficiently large N. The rank is not the only thing to take into account if we treat the problem as a matrix factorization problem. To see this, consider the matrix (k)(l)⊤e^(k)e^(l) for k,l∈[n]k,l∈[n]. Even if the rank of this matrix is 11, it has only zeros everywhere except 11 at position (k,l)(k,l), so we have very little chance of reconstructing it in high dimension by observing a portion of its inputs uniformly at random. The only way to guarantee observation of the input at position (k,l)(k,l) is to choose measurements coherently with its singular basis (k)⊗(l)e^(k) ^(l). This idea is formulated more generally below. Definition C.1. Let U be a subspace of ℝnR^n of dimension r and UP_U be the orthogonal projection onto U. Then, the coherence of U vis-a-vis a basis (i)i∈[n]\u^(i)\_i∈[n] is defined by μ(U)=nrmaxi‖U(i)‖2μ(U)= nr _i\|P_Uu^(i)\|^2. For a matrix =Σ⊤∈ℝn1×n2A=U ^n_1× n_2 under the compact SVD, the projection on the left singular value is →⊤x x, and ‖⊤‖22=‖⊤‖22\|UU x\|^2_2=\|U x\|^2_2 for all x (similarly for the right singular value). We have the following definition of coherence, which considers each matrix entry. Definition C.2 (Local coherence & Leverage score). Let =Σ⊤∈ℝn1×n2A=U ^n_1× n_2 be the compact SVD of a matrix A of rank r. The local coherences of A are defined by μi()=n1r‖⊤(i)‖2=n1r‖i,:‖2∀i∈[n1]νj()=n2r‖⊤(j)‖2=n2r‖j,:‖2∀j∈[n2] split& _i(A)= n_1r\|U e^(i)\|^2= n_1r\|U_i,:\|^2 ∀ i∈[n_1]\\ & _j(A)= n_2r\|V e^(j)\|^2= n_2r\|V_j,:\|^2 ∀ j∈[n_2] split (65) with μi _i for row i and νj _j for row j. In ⊤(i)U e^(i), (i)∈ℝn1e^(i) ^n_1, and in ⊤(j)V e^(j), (j)∈ℝn2e^(j) ^n_2. We did not distinguish them explicitly for simplicity’s sake. The analysis of recovery guarantees for matrix factorization hinges on local coherence of a target matrix ∗A^*. The local coherence measures (μi,νj)(i,j)∈[n1]×[n2]( _i, _j)_(i,j)∈[n_1]×[n_2] of ∗∈ℝn1×n2A^* ^n_1× n_2 quantify how strongly individual rows and columns align with the top singular vectors. These quantities, also known as leverage scores, indicate the “influence” of each row i or column j on the low-rank structure. A row/column with a high leverage score projects strongly onto the span of the singular vectors, meaning that a relatively small number of its entries capture much of the matrix’s structure. Uniformly low coherence (μi _i and νi _i close to 11) implies that the matrix’s information is well-distributed across rows and columns, thereby reducing the number of samples needed for exact recovery. For example, Chen et al. (2014) show in the context of matrix completion that sampling the training inputs at position (i,j)(i,j) with probability pijp_ij proportional to μi+νj _i+ _j allows for perfect recovery of ∗A^* with fewer samples than uniform sampling, and called such sampling strategies local coherence sampling (see Theorem 3.2 and Corollary 3.3 in (Chen et al., 2014)). The minimal number of observations required for perfect recovery also depends on the coherence measures (Candès & Tao, 2010; Candes & Recht, 2012). Let μ(0)μ^(0) and μ(1)μ^(1) be two constants such that μ(0)≥max(maxiμi,maxiνi)μ^(0)≥ ( _i _i, _i _i ) and maxi,j[∗⊤]ij≤μ(1)r/(n1n2) _i,j[U^*V^* ]_ij≤μ^(1) r/(n_1n_2)999Since |[∗∗⊤]ij|=|∑ki,k∗j,k∗|≤∑ki,k∗2∑kj,k∗2=‖i,:∗‖2‖j,:∗‖2=rn1n2μiνj≤rn1n2μ0 |[U^*V^* ]_ij |= | _kU^*_i,kV^*_j,k |≤ _kU^*2_i,k _kV^*2_j,k=\|U^*_i,:\|_2\|V^*_j,:\|_2= r n_1n_2 _i _j≤ r n_1n_2 _0 for all i,ji,j; we can take any μ(1)≥μ(0)rμ^(1)≥μ^(0) r.. Candes & Recht (2012) show that if μ0 _0 and μ1 _1 are low, few samples are required to recover ∗A^*. More precisely, put n=max(n1,n2)n= (n_1,n_2). Suppose we observe N entries of ∗A^* with locations sampled uniformly at random. There are numerical constants C and c such that if N≥Cmax(μ12,μ012μ1,μ0n14)nrβlog(n)N≥ C ( _1^2, _0 12 _1, _0n 14 )nrβ (n ) for some β>2β>2, then perfect recovery of ∗A^* is possible from this N observations with probability at least 1−c/n31-c/n^3. In addition, if r≤n1/5/μ0r≤ n^1/5/ _0, then the recovery is exact with probability at least 1−c/n31-c/n^3 provided that N≥Cμ0n6/5rβlog(n)N≥ C _0n^6/5rβ (n ) (see Theorem 1.3 in (Candes & Recht, 2012)) The research question here can be therefore to know which natural properties of A affects the rank and the local coherences of (3)∗⊤ C^* _(3); or more generally, how do the properties of A affect the rank and the local coherences of (3)∗⊤ C^* _(3). We leave these questions for future work. C.2 Finite Fields =ℤ/pℤF=Z/pZ and Representation-Centric Modeling For a finite-field FDA (=p=ℤ/pℤF=F_p=Z/pZ, p prime), we treat A as a vocabulary, index each element ∈u∈ A by ⟨⟩∈[q] ∈[q] with q=||=pnq=| A|=p^n, and learn an embedding matrix ∈ℝq×dE ^q× d so that ⟨⟩E_ is the trainable vector attached to u. We hypothesize that grokking corresponds to the point at which E and the downstream layers collectively represent the algebra, so a simple linear readout recovers the correct output token. To verify this hypothesis: (i) we vary algebraic properties of p[∗]F_p[ C^*] and measure their effect on grokking delay and generalization; (i) we study how structural features of ∗ C^* shape learning dynamics; and (i) we probe whether models learn algebraic representations during training. This finite-field setting provides the cleanest laboratory for observing how algebraic structure governs grokking. Appendix D Experiment Setup D.1 Task Description and Model Architecture From now on we work over the finite field =pF=F_p (prime p). Identify ≡pn A _p^n and set q:=||=pnq:=| A|=p^n. Each element ∈u∈ A is treated as a vocabulary symbol with index ⟨⟩∈[q] ∈[q]. The models we use will associate to each of these symbols a trainable vector ⟨⟩∈ℝdE_ ^d. ∈ℝV×dE ^V× d, with V≥qV≥ q the vocabulary size, which include the set special tokens S (see section below). Let Ψ:→0,1V : A→\0,1\^V be the one-hot encoding defined the vocabulary =∪V= A , Ψ():=[(=)]∈∀∈ (a):= [1(v=u) ]_v \ . We have ⟨⟩=⊤Ψ()E_ =E (u). D.1.1 Classification Here, V=q+2V=q+2, with 11 for the special tokens =×,=S= \×, = \. The logits for =(,×,,=)x=(u,×,v, =) with (,)∈2(u,v)∈ A^2 are given by yθ()=φ(ϕ(⟨⟩⊕⟨×⟩⊕⟨⟩⊕⟨=⟩))∈ℝqy_θ(x)= (φ (E_ _ × _ _ = ) ) ^q, where ⊕ is the vector concatenation, and φ the classifier. We use a linear classifier φ()=+ (z)=b+Wz. For ϕφ, we use MLP, LSTM and Transformer (encoder). The learnable parameters θ are the union of ,, \E,W,b \ and the parameters of ϕφ. For LSTM and Transformer, ϕφ takes the embeddings ∈ℝ4×dz ^4× d and returns a hidden representation of size m2m^2, for instance, the representation of the last token = of x. For a MLP φ∘ϕ φ of L>1L>1 layers with activation function g, we defined ϕφ by ϕ()=g((L−1)+(L−1)g(⋯g((2)+(2)g((1)+(1)vec()))⋯))φ(z)=g (b^(L-1)+W^(L-1)g (·s g (b^(2)+W^(2)g (b^(1)+W^(1)vec(z) ) )·s ) ) (66) with =vec(⟨⟩⊕⟨⟩)∈ℝ2dz=vec (E_ _ ) ^2d, where (i)∈ℝdi+1×diW^(i) ^d_i+1× d_i and (i)∈ℝdi+1b^(i) ^d_i+1 for all i∈[L−1]i∈[L-1], (d1,dL)=(2d,m2)(d_1,d_L)=(2d,m^2). The dataset =(,∗())∣=(,×,,=),(,)∈2D=\(x,y^*(x)) =(u,×,v, =),(u,v)∈ A^2\ has size N=q2N=q^2. D is randomly partitioned into two disjoint and non-empty sets trainD_train and testD_test, the training and the validation dataset respectively, following a ratio r:=|train|/||∈(0,1]r:=|D_train|/|D|∈(0,1]. The models are trained to minimize the average cross-entropy loss ℒtrain(θ)L_train(θ) given in Equation (67). We denoted by trainA_train the corresponding accuracy (ℒtestL_test and testA_test on testD_test). ℒtrain(θ)=∑(,∗)∈trainℓ(yθ(),⟨∗⟩) with ℓ(,i)=−log(exp(i)∑j∈[q]exp(j))∀∈ℝq,i∈[q]L_train(θ)= _(x,y^*) _train (y_θ(x), ^* )\ with (y,i )=- ( (y_i ) _j∈[q] (y_j ) )\ ^q,i∈[q] (67) D.1.2 Language Modeling Here, V=q+4V=q+4, with 44 for the special tokens =×,=,bos,eosS= \×, =, bos, eos \. We train the model on the algebra using an auto-regressive approach. For =(,)∈2x=(u,v)∈ A^2 with =∗×1×2y= C^*×_1u×_2v, let s=⟨bos⟩⟨⟩⟨×⟩⟨⟩⟨=⟩⟨⟩⟨eos⟩∈[V]7s= bos × = eos ∈[V]^7. The training is performed by maximizing the likelihood under the direct autoregressive factorization, and the loss (as well as the accuracy) is calculated only on the answer part s6s7=⟨⟩⟨eos⟩s_6s_7= eos of the equation. More precisely, let ϕφ be an encoder that takes a sequence of embedding vectors and returns a hidden representation of size m2m^2, and φ:ℝm2→ℝV :R^m^2 ^V be the classifier. For s∈[V]7s∈[V]^7 and k≥2k≥ 2, write s(k) s^(k) =s1⋯sk∈[V]k =s_1·s s_k∈[V]^k (68) (k) ^(k) =[s1,⋯,sk]⊤∈ℝk×d =[E_s_1,·s,E_s_k] ^k× d (69) (k) ^(k) =φ(ϕ((k))∈ℝV = (φ(E^(k)) ^V (70) ℙ(i∣s<k) (i s_<k) =exp(i(k))∑jexp(j(k))∈0,1V∀i∈[V] = (z^(k)_i) _j (z^(k)_j)∈\0,1\^V\ ∀ i∈[V] (71) The likelihood for s=s1⋯s6s7=⟨bos⟩⟨⟩⟨×⟩⟨⟩⟨=⟩⟨⟩⟨eos⟩∈[V]7s=s_1·s s_6s_7= bos × = eos ∈[V]^7 is pθ(s6s7∣s<6)=ℙ(s6∣s<6)ℙ(s7∣s<7)p_θ(s_6s_7 s_<6)=P(s_6 s_<6)P(s_7 s_<7) (72) The dataset D of all possible equations (which has size q2q^2) is randomly partitioned into two disjoint and non-empty sets trainD_train and testD_test, the training and the validation dataset respectively, following a ratio r:=|train|/||r:=|D_train|/|D|. The models are trained to minimize the average ℒtrain(θ)L_train(θ) of the negative loglikelihood −logpθ(s6s7∣s<6)- p_θ(s_6s_7 s_<6) over trainD_train (Equation (73)). We denoted by trainA_train the corresponding accuracy (ℒtestL_test and testA_test on testD_test). ℒtrain(θ)=−∑s∈trainlogpθ(s6s7∣s<6)L_train(θ)=- _s _train p_θ(s_6s_7 s_<6) (73) We use a linear classifier φ()=+∈ℝV (z)=b+Wz ^V. For ϕφ, we use MLP, LSTM, and Transformer (encoder). The learnable parameters θ are the union of ,, \E,W,b \ and the parameters of ϕφ. For LSTM and Transformer, ϕφ takes the embeddings ∈ℝT×dz ^T× d and returns a hidden representation of size m2m^2, for instance, the representation of the last element (last token). For MLP, we ignored the special tokens for simplicity, i.e ϕφ directly takes as input the embedding =vec(⟨⟩⊕⟨⟩)∈ℝ2dz=vec (E_ _ ) ^2d. For L>1L>1, we defined ϕφ by ϕ()=g((L−1)+(L−1)g(⋯g((2)+(2)g((1)+(1)))⋯))φ(z)=g (b^(L-1)+W^(L-1)g (·s g (b^(2)+W^(2)g (b^(1)+W^(1)z ) )·s ) ) (74) where (i)∈ℝdi+1×diW^(i) ^d_i+1× d_i and (i)∈ℝdi+1b^(i) ^d_i+1 for all i∈[L−1]i∈[L-1], (d1,dL)=(2d,m2)(d_1,d_L)=(2d,m^2). So φ∘ϕ φ is a MLP of L layers with g as activation function. D.2 Representation Learning D.2.1 Proof of Propositon 5.1 Proposition D.1. Assume that (,×)( A,×) has a group structure (of size q), and denote the inverse of an element ∈u∈ A by −1u^-1. Let ρ:→ℝm×mρ: A ^m× m be a faithful matrix representation of A. Suppose a model yθ()=ϕ()∈ℝqy_θ(x)=Wφ(x) ^q encodes pairs =(,)∈2x=(u,v)∈ A^2 as ϕ(,)=ρ(×)φ(u,v)=ρ(u×v) and decodes with a linear classifier parameterized by weights ∈ℝq×m2W ^q× m^2 containing ρ(−1)ρ(w^-1) for each ∈w∈ A. Then the predicted label satisfies argmaxi∈[q]yθ()[i]=× *arg\,max_i∈[q]y_θ(x)[i]=u×v. As a consequence, the classifier linearly separates all q outputs. Proof. Consider the linear classifier yθ()=ϕ(,)y_θ(x)=Wφ(u,v) acting on ϕ(,)∈ℝm2φ(u,v) ^m^2, that is yθ(,)[i]=⟨i,ϕ(,)⟩y_θ(u,v)[i]= _i,φ(u,v) where the inner product is the Frobenius product on ℝm×mR^m× m. Write i=ρ(−1)W_i=ρ(w^-1) for some ∈w∈ A, so that yθ(,)[i]=⟨ρ(×),ρ(−1)⟩=tr(ρ(×)ρ(−1)⊤)y_θ(u,v)[i]= ρ(u×v),ρ(w^-1) =tr (ρ(u×v)ρ(w^-1) ) (75) Since ρ(−1)⊤=ρ(−1)ρ(w^-1) =ρ(w^-1) for an orthogonal (unitary) representation, this reduces to yθ(,)[i]=tr(ρ(×)ρ(−1))=χρ((×)×−1)y_θ(u,v)[i]=tr (ρ(u×v)ρ(w^-1) )= _ρ ((u×v)×w^-1 ) (76) where χρ _ρ is the character of ρ. Now, recall that χρ _ρ uniquely distinguishes group elements whenever ρ is faithful. In particular, max∈χρ((×)−1) _w∈ A _ρ ((u×v)w^-1 ) is attained uniquely at =×w=u×v. Therefore, argmaxi∈[q]yθ(,)[i]=argmax∈χρ((×)×−1)=× *arg\,max_i∈[q]y_θ(u,v)[i]= *arg\,max_w∈ A _ρ ((u×v)×w^-1 )=u×v (77) ∎ D.2.2 Representation Quality Let (ℓ)()∈ℝm12f^( )(u) ^m_1^2 and (r)()∈ℝm12f^(r)(u) ^m_1^2 denote the feature vectors produced by the model for ∈u∈ A when u appears on the left or on the right of an equation, respectively; and let ()∈ℝm2f(u) ^m^2 denote the feature vector of u produced by the unembedding layer (the classifier). For the first layer of the model (the embedding), we have (ℓ)()=(r)()=⟨⟩f^( )(u)=f^(r)(u)=E_ and thus m12=dm_1^2=d. For Transformer, m12=dm_1^2=d for all layers, but for LSTM (resp. MLP), m12m_1^2 is the hidden dimension (resp. number of hidden units in the considered layer), which can differ from the embedding size d. We want to determine whether there exists ∈ℝm12×m12×m2 W ^m_1^2× m_1^2× m^2 such that (×)=^(×):=×1(ℓ)()×2(r)()=(3)((r)()⊗(ℓ)())∀(,)∈2f(u×v)= f(u×v):= W×_1f^( )(u)×_2f^(r)(v)= W_(3) (f^(r)(v) ^( )(u) ) ∀(u,v)∈ A^2 (78) with (3)∈ℝm2×m14 W_(3) ^m^2× m_1^4. Here, we are seeking a linear transformation from ℝm14R^m_1^4 to ℝm2R^m^2, with m14≈m4m_1^4≈ m^4 (since m and m1m_1 are of similar order). Because N=|2|=q2N=| A^2|=q^2 is not very large, the problem may become trivial if the dimension is too high101010In fact, if m14≫Nm_1^4 N, then the system is overparameterized and admits near-perfect solutions regardless of whether the features encode algebraic structure.. To avoid this, we first project (ℓ)()f^( )(u) and (r)()f^(r)(v) into a lower-dimensional space of size m22≤m_2^2≤ m. Formally, we want ∈ℝm22×m22×m2 W ^m_2^2× m_2^2× m^2, (ℓ)∈ℝm22×m12P^( ) ^m_2^2× m_1^2 and (r)∈ℝm22×m12P^(r) ^m_2^2× m_1^2 such that (×)=^(×):=(3)(((r)(r)())⊗((ℓ)(ℓ)()))=(3)((r)()⊗(ℓ)())∀(,)∈2f(u×v)= f(u×v):= W_(3) ( (P^(r)f^(r)(v) ) (P^( )f^( )(u) ) )= W_(3)\,P\, (f^(r)(v) ^( )(u) ) ∀(u,v)∈ A^2 (79) with (3)∈ℝm2×m24 W_(3) ^m^2× m_2^4 and =(r)⊗(ℓ)∈ℝm24×m14P=P^(r) ^( ) ^m_2^4× m_1^4. We do not learn (ℓ),(r)P^( ),P^(r) jointly with W, since this would give W too much flexibility and risk overfitting (the decomposition (79) could still hold trivially without revealing whether algebra-like structure emerges in the model’s features). Instead, we fix (ℓ),(r)P^( ),P^(r) in advance, either by drawing them at random or by using a PCA-based construction. We use the mean squared error ℒrepL_rep and the cosine similarity repA_rep associated with solving this problem (i.e. finding W) as measures of how algebra-like structure emerges in the model’s feature space. ℒrep _rep =1|2|1∑(,)∈2‖(×)‖22∑(,)∈2‖(×)−^(,)‖22 = 1| A^2| 1 _(u,v)∈ A^2 \|f(u×v) \|_2^2 _(u,v)∈ A^2 \|f(u×v)- f(u,v) \|_2^2 (80) rep _rep =1|2|∑(,)∈2⟨(×),^(,)⟩‖(×)‖2‖^(,)‖2 = 1| A^2| _(u,v)∈ A^2 (u×v), f(u,v) \|f(u×v)\|_2\,\| f(u,v)\|_2 (81) Random projections A natural choice is to draw (ℓ),(r)P^( ),P^(r) at random, for example with i.i.d. Gaussian entries followed by row-orthonormalization. Random projections preserve pairwise geometry up to small distortions (Johnson–Lindenstrauss lemma (Johnson & Lindenstrauss, 1984)) and avoid introducing systematic biases. They are also simple, fast to generate, and hard to overfit since they are fixed across training runs. To pick m2m_2, we balance two constraints: (i) avoid the trivial regime where m24≫Nm_2^4 N, and (i) retain enough information from the features. In practice we set m2≈min(⌊m1/2⌋,⌊(N/κ)1/4⌋)m_2≈ ( m^1/2 ,\ (N/κ)^1/4 ) with κ≥1κ≥ 1 a safety factor. This ensures m24≲Nm_2^4 N while keeping m22m_2^2 on the same scale as m. To ensure robustness, we repeat the probe with several independent draws of P and report mean ± standard deviation of (ℒrep,rep)(L_rep,A_rep). PCA projections When the feature distribution is highly anisotropic, random projections may discard important directions. In this case, we compute (ℓ)P^( ) and (r)P^(r) using PCA, fitted separately on (ℓ)()∈\f^( )(u)\_u∈ A and (r)()∈\f^(r)(u)\_u∈ A, respectively. We retain the top m22m_2^2 components and whiten them to equalize variances. This choice improves the signal-to-noise ratio by ensuring that the projection focuses on the most informative directions while still enforcing the same dimensionality constraint m24≤m2m_2^4≤ m^2. Thus, PCA projections can complement random projections: the former adapt to data anisotropy, while the latter serve as a neutral and robust baseline. Figure 8: Grokking on 2 layers Tansformer trained on the algebra of complex numbers in ℤ/7ℤZ/7Z using a training data fraction of r=0.5r=0.5. Appendix E Experimentation Details and Additional Experiments MLP For Figures 1, 2 (a), 3 (a), 4, 5, 6, 7, 11, 12, 14 and 13, φ∘ϕ φ is implemented as a three-layer MLP with ReLU activations and input, hidden, and output dimensions all set to m2=28m^2=2^8. More precisely, we define φ()=∈ℝq,∈ℝq×m2 (z)=Wz ^q, ^q× m^2 and ϕ()=g((2)+(2)g((1)+(1)vec()))φ(z)=g (b^(2)+W^(2)g\! (b^(1)+W^(1)vec(z) ) ) where (1)∈ℝm2×2dW^(1) ^m^2× 2d, (1)∈ℝ2db^(1) ^2d, (2)∈ℝm2×m2W^(2) ^m^2× m^2, (2)∈ℝm2b^(2) ^m^2, and g(z)=max(0,z)g(z)= (0,z). The embedding dimension is therefore d=m2/2d=m^2/2. All models are initialized using PyTorch’s default initialization scheme. Training was carried out with the AdamW optimizer, a learning rate of 10−210^-2, weight decay of 10−110^-1, and a minibatch size of 2102^10. Models were optimized on a NVIDIA Tesla T4 GPU. For Figure 1, the training data fraction is r=0.5r=0.5. Transformer For Figures 2 (b), 3 (b) and 8, ϕφ is implemented as a two-layer Transformer Encoder with 22 heads and a hidden/embedding dimension of d=m12=26d=m_1^2=2^6. The models are initialized using PyTorch’s default initialization scheme and trained with the AdamW optimizer, a learning rate of 10−310^-3, weight decay of 10−110^-1, and a minibatch size of 2102^10. LSTM For Figures 9 and 10, ϕφ is implemented as a three-layer LSTM with hidden dimension m12m_1^2 equal to the embedding dimension d=28d=2^8. The models are initialized using PyTorch’s default initialization scheme and trained with the AdamW optimizer, a learning rate of 10−210^-2, weight decay of 10−110^-1, and a minibatch size of 2102^10. Linear Probing For the probing experiments (Figures 2, 3 and 10), we apply PCA and retain the top m22=m_2^2=m components to construct the projection matrices (ℓ),(r)∈ℝm22×m12P^( ),P^(r) ^m_2^2× m_1^2 with m1=m_1=m. The problem (79) is then solved using ordinary least squares with ℓ2 _2 regularization (10−310^-3), implemented via sklearn’s Ridge regression. Figure 9: Grokking on 3 layers LSTM trained on the algebra of complex numbers in ℤ/7ℤZ/7Z using a training data fraction of r=0.3r=0.3. Figure 10: Generalization accuracy as a function of representation quality for different training data size (r) and model layers (0 for first layer, 11 for the second, etc.) for a LSTM: testA_test increases with repA_rep in a low-data regime. Figure 11: Training and test loss and accuracy as a function of the training data fraction. Figure 12: Phase transition times as a function of the fraction of data used to train the model: t1t_1 is the step a which the training accuracy trainA_train reaches a value strictly greater than 5%5\% for the first time, t2t_2 the step at which trainA_train reaches 99%99\% for the first time, t3t_3 the step at which the test accuracy testA_test reaches a value strictly greater than 5%5\% for the first time, and t2t_2 the step at which testA_test reaches ≈99%≈ 99\% for the first time. Figure 13: Test loss as a function of training data fraction r for rank((1)∗) *rank( C^*_(1)) (left) and rank((2)∗) *rank( C^*_(2)) (right). The sizes of the dots are proportional to t4t_4. Figure 14: Training and test loss and accuracy as a function of training steps for different values of the training data fraction r.