Acta Polytechnica https://doi.org/10.14311/AP.2023.63.0188 Acta Polytechnica 63(3):188–198, 2023 © 2023 The Author(s). Licensed under a CC-BY 4.0 licence Published by the Czech Technical University in Prague FROM POSITIONAL REPRESENTATION OF NUMBERS TO POSITIONAL REPRESENTATION OF VECTORS Izabella Ingrid Farkasa, Edita Pelantováb, ∗, Milena Svobodováb a Eötvös Loránd University, Doctoral School of Informatics, Pázmány P. sétány 1/C, 1117 Budapest, Hungary b Czech Technical University in Prague, Faculty of Nuclear Sciences and Physical Engineering, Department of Mathematics, Trojanova 13, 120 00 Prague, Czech Republic ∗ corresponding author: Edita.Pelantova@fjfi.cvut.cz Abstract. To represent real m-dimensional vectors, a positional vector system given by a non-singular matrix M ∈ Zm×m and a digit set D ⊂ Zm is used. If m = 1, the system coincides with the well known numeration system used to represent real numbers. We study some properties of the vector systems which are transformable from the case m = 1 to higher dimensions. We focus on an algorithm for parallel addition and on systems allowing an eventually periodic representation of vectors with rational coordinates. Keywords: Number system, positional representation, local function, parallel addition, eventually periodic representation. 1. Introduction Expression of a number as a linear combination of elements of the sequence (βj )j∈Z with coefficients from a finite set D is nowadays the most used way to represent numbers. Such a system is called a posi- tional number system with the base β and the digit set D. The decimal number system with the base ten and digits 0, 1, . . . , 9 prevails in Europe for several centuries. In the age of computers, the binary and hexadecimal number systems broke the domination of the decimal number system. But advantages of working with another number system were observed before computers came on the scene: A. Cauchy [1] checked correctness of his computations using simul- taneously the classical decimal number system and decimal number system with the symmetric set of digits {−5, −4, . . . , 0, 1, . . . , 5}. V. Grünwald [2] con- sidered a number system with base β = −2 and digits {0, 1}. An important moment for the number systems, making them a source of interest for many areas of mathematics, came in 1957, when A. Rényi [3] intro- duced number systems with an arbitrary real base β > 1. Algebraic, dynamical, topological, geometric and algorithmic properties of the Rényi number sys- tems have been very intensively studied since then, from both theoretical and practical points of view. For example, a suitable choice of a base in an algebraic extension of rational numbers enables to represent all elements of the algebraic field by a finite or even- tually periodic string of digits, see [4] and [5]. Fur- ther generalisations of numeration systems emerged in the following years. Knuth [6] and Penney [7] came with positional representations of complex numbers, wherein, instead of two strings of digits representing the real and the imaginary part of complex numbers separately, they suggested to use a complex base β, in order to represent the complex number by a single string of digits. This type of representation was then further developed in the concept of canonical num- ber systems [8] and (even more general) shift radix systems, see [9] for a survey on the topic. In most of the above mentioned generalisations of numeration systems, every number has a unique rep- resentation, whose digits are determined by iterations of some transformation function. One exception is the decimal system with a symmetric digit set used by Cauchy. It has eleven digits – more than necessary for representing all positive integers. Such a system is called redundant. Already Cauchy noticed that, with this redundant system, the addition of two numbers is easier than in the classical system, as the carry propa- gation is limited. This property was further exploited by A. Avizienis, aiming to speed up addition. In the classical b-ary numeration system, where the base is an integer β = b ≥ 2, addition has a linear time com- plexity with respect to the length of representations of the summands. Avizienis [10] designed an algorithm with a constant time complexity for addition in re- dundant number systems using base β = b ≥ 3 and a symmetric integer digit set. In this paper, we consider representations of m- dimensional vectors. The numeration system is given by a square matrix base M ∈ Zm×m and by a finite set of digits D ⊂ Zm. An origin of such numeration sys- tems can be found in works [11] and [12] of A. Vince, showing that for any expansive matrix M ∈ Zm×m, there exists a digit set D ⊂ Zm such that any ele- ment x of the lattice Zm can be written in the form x = ∑n j=0 M j dj , where dj ∈ D. In other words, the whole lattice Zm is representable in the matrix nu- meration system (M, D). However, if a matrix M has an eigenvalue inside the unit circle, then no choice of the digit set D ⊂ Zm allows to represent all in- 188 https://doi.org/10.14311/AP.2023.63.0188 https://creativecommons.org/licenses/by/4.0/ https://www.cvut.cz/en vol. 63 no. 3/2023 Positional representation of vectors teger vectors as a combination of only non-negative powers of M . The matrix formalism for numeration systems (under the name numeration systems in lat- tices) was systematically used by A. Kovács in [13]. Of course, Kovács, just like Vince, considers integer matrices, as they map a lattice into itself. In fact, al- ready positional representations of Gaussian integers or algebraic integers from an algebraic extension of rational numbers can be interpreted as special cases of the matrix numeration systems. J. Jankauskas and J. Thuswaldner [14] generalised the Vince’s results to matrix bases M ∈ Qm×m with rational entries and without eigenvalues in modulus strictly smaller than 1. Another generalisation introduced recently allows to use both positive and negative powers of the matrix base for representation of vectors. In [15], it is shown that for M ∈ Zm×m with det M = ∆ ̸= 0, there ex- ists a finite digit set D ⊂ Zm such that every integer vector from Zm has a finite (M, D)-representation, i.e., Zm ⊂ FinD (M ), where (1) FinD (M ) = {∑ j∈I M j dj : I ⊂ Z, I finite, dj ∈ D } . We show (in Theorem 9) that if, moreover, no eigen- value of M lies on the unit circle, then for a suitable finite digit set D ⊂ Zm, addition and subtraction on FinD(M ) can be performed by a parallel algorithm, i.e., in a constant number of steps independent of the length of (M, D)-representation of summands. Ac- cording to Proposition 15, the required assumption on eigenvalues of M is in fact necessary for the ex- istence of a parallel addition algorithm on (M, D). Then, we restrict our study to expansive matrices – i.e., matrices with all eigenvalues strictly outside the unit circle. In Theorem 21, we show that the digit set D ⊂ Zm allowing a parallel addition enables (for an expansive matrix base M ) an eventually periodic (M, D)-representation of every element of Qm, i.e. Qm = PerD (M ), where PerD (M ) = { N∑ j=−∞ M j dj : dj ∈ D, (dj )N−∞ eventually periodic } . Consequently, every element of Rm has an (M, D)- representation (Corollary 22). The methods we use in our proofs are based on proofs of analogous results for a positional representa- tion of real and complex numbers, modified accord- ingly to the formalism of matrices and vectors. 2. Preliminaries A numeration system used for a positional represen- tation of complex numbers is given by a base β ∈ C with |β| > 1 and a finite digit set A ⊂ C. If x ∈ C can be written in the form x = ∑n j=−∞ aj β j , where aj ∈ A for each j ∈ Z, j ≤ n, we say that x has a (β, A)-representation. The assumption |β| > 1 guar- antees that the series ∑n j=−∞ aj β j is convergent for any choice of digits aj ∈ A. W. Penney in [7] intro- duced the following numeration system, which we use to demonstrate our approach. Example 1. Let us consider β = i − 1. Penney in [7] showed that (1.) each x ∈ Z[i] = {a + ıb : a, b ∈ Z}, x ̸= 0 can be expressed uniquely as x = ∑n j=0 aj β j , where a0, a1, . . . , an ∈ {0, 1} and an ̸= 0; (2.) each x ∈ C can be expressed as x = ∑n j=−∞ aj β j , where aj ∈ {0, 1} for every j ∈ Z, j ≤ n. Our aim is to study selected properties of matrix numeration systems used to represent m-dimensional vectors. Any matrix numeration system used in this paper is given by a non-singular matrix base M ∈ Zm×m and a finite (vector) digit set D ⊂ Zm. Thanks to the result of [15] mentioned earlier, we always assume that Zm is a subset of FinD (M) and, (2) moreover, D contains the zero vector. (3) In the first part of this paper, we work only with vectors from FinD(M ). Therefore, we do not yet im- pose additional assumptions on the matrix base M , analogous to the assumption |β| > 1 required for number bases (which is important to ensure the con- vergence of the infinite series ∑n j=−∞ aj β j ). Only in the second part of the paper, we revisit the question of the infinite representations convergence for matrix numeration systems as well. Let us list some obvious properties of the set FinD (M ): • M pFinD (M ) = FinD (M ) for every p ∈ Z. • FinD (M ) ⊂ Qm, more precisely, FinD (M ) ⊂ ⋃ k∈N 1 ∆k Z m, where ∆ = det M . • If x = ∑n j=0 M j dj for some n ∈ N, then x ∈ Zm. • FinD (M ) is closed under addition and subtraction: Indeed, if x, y ∈ FinD(M ), then there exists p ∈ N such that M px ∈ Zm and M py ∈ Zm, and hence M p(x ± y) ∈ Zm. By assumption (2), M p(x ± y) ∈ FinD(M ) = M pFinD(M ), and thus x ± y ∈ FinD (M ). If a vector x ∈ Qm is expressed as x = ∑ j∈I M j dj for a finite I ⊂ Z and dj ∈ D, we can, for some integer numbers s ≤ 0 ≤ n, write x = ∑n j=s M j dj , because the zero vector belongs to D. Hence x can be identified with a bi-infinite string (dj )j∈Z ∈ DZ usually referred to as (M, D)-representation of x: (x)M,D = ω 0dndn−1 · · · d1d0 • d−1d−2 · · · ds0ω , where the zero index in the bi-infinite string is indicated by •. 189 I. Farkas, E. Pelantová, M. Svobodová Acta Polytechnica As mentioned in the introduction, some numeration systems used for representation of numbers can also be interpreted as matrix numeration systems. Let us illustrate this concept on the Penney numeration system introduced in Example 1 . Example 2. Let us transform the number numeration system from Example 1 into a matrix numeration system on Z2. In place of the number base β = ı − 1, we use the matrix base M = ( −1 −1 +1 −1 ) ∈ Z2×2. It is easily seen that multiplication of a Gaussian integer – complex number x = b + ıc ∈ Z[ı], with b, c ∈ Z, by the number base β corresponds to multiplication of an integer vector v = (b, c)⊤ ∈ Z2 by the matrix base M , as follows: βx = (ı − 1) · (b + ıc) = (−b − c) + ı(b − c) , M v = ( −1 −1 +1 −1 ) · ( b c ) = ( −b − c b − c ) . Let us define a mapping ξ : Z[ı] 7→ Z2 by the formula ξ(b + ıc) := (b, c)⊤ for any b, c ∈ Z . (4) Obviously, ξ(x + y) = ξ(x) + ξ(y) for every x, y ∈ Z[ı]. Thus, the mapping ξ is an isomorphism between the lattices Z[ı] and Z2. Moreover, it fulfils the equality ξ(β · x) = M · ξ(x) for every x ∈ Z[ı]. (5) Hence, if b + ıc ∈ Z[ı] is written in the form b + ıc =∑n j=0 aj β j with aj ∈ {0, 1}, then( b c ) = ξ(b+ıc) = ξ ( n∑ j=0 βj aj ) = n∑ j=0 M j dj , where dj = ξ(aj ) ∈ {( 0 0 ) , ( 1 0 )} = {ξ(0), ξ(1)} . Using the properties of the Penney numeration sys- tem from Example 1, we conclude that the matrix nu- meration system given by the base M = ( −1 −1 +1 −1 ) and the digit set D = {(0, 0)⊤, (1, 0)⊤} provides for any vector v ∈ Z2 a unique (M, D)-representation in the form v = ∑n j=0 M j dj , dj ∈ D and dn ̸= 0 (if v ̸= 0). 3. Parallel addition in matrix numeration systems Let us consider the operations of addition and sub- traction on the set of m-dimensional vectors from an algorithmic point of view. Similarly to the classical algorithms for arithmetic operations, we work only with finite representations – i.e., on the set FinD (M ). Let x, y ∈ FinD (M ), with (x)M,D = ω 0xnxn−1 · · · x1x0 •x−1x−2 · · · xs0ω and (y)M,D = ω 0ynyn−1 · · · y1y0 • y−1y−2 · · · ys0ω . Adding x and y means to rewrite the (M, D + D)- representation ω 0(xn + yn) · · · (x0 + y0) • (x−1 + y−1) · · · (xs + ys)0ω of the number x + y into an (M, D)-representation of x + y. As already announced, we are interested in parallel algorithms for addition. Let us mathematically for- malise the parallelism. Firstly, we recall the notion of a local function, which comes from symbolic dynamics, see [16]. Definition 3. Let A and B be finite sets. A function φ : AZ → BZ is said to be p-local if there exist non- negative integers r and t satisfying p = r + t + 1, and a function Φ : Ap → B such that, for any u = (uj )j∈Z ∈ AZ and its image v = φ(u) = (vj )j∈Z ∈ BZ, we have vj = Φ(uj+t · · · uj−r ) for every j ∈ Z. This means that the image of u by φ is obtained through a window of limited length p. The parame- ter r is called memory and the parameter t is called anticipation of the function φ. Such functions, re- stricted to finite sequences, are computable by a par- allel algorithm in constant time, irrespective of the length of the operands’ representations. Definition 4. Given a (matrix) base M ∈ Zm×m with det M ̸= 0 and (vector) digit sets A, B ⊂ Zm containing 0, a digit set conversion in base M from A to B is a function φ : AZ → BZ such that (1.) for any u = (uj )j∈Z ∈ AZ with a finite number of non-zero digits, v = (vj )j∈Z = φ(u) ∈ BZ has only a finite number of non-zero digits, and (2.) ∑ j∈Z M j vj = ∑ j∈Z M j uj . Such a conversion is said to be computable in parallel if it is a p-local function for some p ∈ N. Thus, the operation of addition on FinD (M ) is com- putable in parallel if there exists a digit set conversion in base M from D + D to D which is computable in parallel. Two useful lemmas precede the statement about the parallel addition on matrix numeration systems: Lemma 5. Let M ∈ Zm×m be a non-singular matrix and D ⊂ Zm be a finite digit set such that every x ∈ Zm is representable in the numeration system (M, D). If addition is computable in parallel in (M, D), then it is computable in parallel also in (M, D′) for each finite digit set D′ ⊂ Zm containing D. Proof. Each digit d′ ∈ D′ can be written in the form d′ = ∑ j∈I(d′) M j dj , where I(d′) is a finite subset of Z and dj ∈ D for each j ∈ I(d′). Denote q = max{|x| : d′ ∈ D′, x ∈ I(d′)} . 190 vol. 63 no. 3/2023 Positional representation of vectors The string 0ω d′nd′n−1 · · · d′0 • d′−1d′−2 · · · d′−N 0 ω can be transformed by a (2q + 1)-local function into a string having the form 0ω en+q en+q−1 · · · e0 • e−1e−2 · · · e−N −q 0ω , where ed ∈ D + D + · · · + D︸ ︷︷ ︸ (2q+1)−times . In other words, a sum of two finite (M, D′)- representations can be rewritten as sum of 2(2q + 1) finite (M, D)-representations. Since addition of two strings is doable in parallel in (M, D), addi- tion of 2(2q + 1) strings with fixed q is possible in parallel (M, D) as well, and the resulting (M, D)- representation is also an (M, D′)-representation, due to D ⊂ D′. The following lemma is stated without a proof here, as the course of the proof would be identical to that of Proposition 5.1 in [17]. Although that proposition works with roots of the minimal polynomial of an alge- braic number, the minimality of the polynomial is not used for the proof itself. In fact, the idea of the proof comes from [18], where expansive polynomials are con- sidered. In our case, we extend the considerations to polynomials with no roots on the unit circle. Lemma 6. Let α1, . . . , αn ∈ C be the roots of a polynomial f ∈ Z[X] satisfying |αk| ̸= 1 for all k = 1, . . . , n. Then, for any t ≥ 1, there exists a non-zero polynomial g ∈ Z[X], g(X) = ∑p−1 l=0 clX l such that g is divisible by f and for one coefficient cL we have 1 t cL > p−1∑ l=0,l ̸=L |cl| . (6) In particular, if |αk| > 1 for all k = 1, . . . , n, then L = 0. Corollary 7. Let M ∈ Zm×m, with det M ̸= 0 and no eigenvalue of M equals 1 in modulus. Then, there exists a polynomial g ∈ Z[X], g(X) = ∑p−1 l=0 clX l such that g(M ) = Θ and for one coefficient cL we have cL ≥ 4 · ( C + p−1∑ l=0,l ̸=L |cl| ) , (7) where C = cL − 4 ⌊ cL 4 ⌋ ∈ {0, 1, 2, 3}. Proof. Let f be the characteristic polynomial of the matrix M . The Hamilton–Cayley theorem says that f (M ) = Θ. By Lemma 6 applied on f with t = 16, we find a polynomial g(X) = ∑p−1 l=0 clX l ∈ Z[X] such that cL > 16 · p−1∑ l=0,l ̸=L |cl| , for some L ∈ {0, . . . , p − 1} . Using the fact that ∑p−1 l=0,l ̸=L |cl| ≥ 1 and denoting C := cL − 4 ⌊ cL 4 ⌋ ∈ {0, 1, 2, 3} , we obtain the following estimate: cL > 16 p−1∑ l=0,l ̸=L |cl| = 4 ( 3 p−1∑ l=0,l ̸=L |cl| + p−1∑ l=0,l ̸=L |cl| ) ≥ ≥ 4 ( 3 + p−1∑ l=0,l ̸=L |cl| ) ≥ 4 ( C + p−1∑ l=0,j ̸=L |cl| ) . Since the characteristic polynomial f divides g, we have g(M ) = Θ. Example 8. The minimal polynomial of the complex number β = ı − 1 and the characteristic polynomial of the matrix M defined in Example 2 are both equal to f (X) = X 2 + 2X + 2. The polynomial g(X) = X 4 + 4 = (X 2 + 2X + 2)(X 2 − 2X + 2) satisfies g(M ) = Θ and (7) with L = 0. Theorem 9. Let M ∈ Zm×m, with det M ≠ 0 and no eigenvalue of M equals 1 in modulus. Then there exists a finite (vector) digit set D ⊂ Zm such that Zm ⊂ FinD(M ) and both addition and subtraction on FinD (M ) are computable in parallel. Proof. Let g(X) = ∑p−1 l=0 clX l be the polynomial from Corollary 7. Denote K = ⌊ cL 4 ⌋ ≥ 1 and define D = [−3K, 3K)m ∩ Zm. In order to show that the digit set D enables parallel addition, we introduce two auxiliary sets D′ = [−2K, 2K)m ∩ Zm and Q = [−1, 1]m ∩ Zm , and then exploit the obvious fact that D + D ⊂ D′ + 4KQ . (8) Let x = ∑ j∈Z M j aj and y = ∑ j∈Z M j bj , where aj , bj ∈ D. Moreover, we assume that aj , bj ̸= 0 for just a finite number of indices j ∈ Z. Clearly, aj + bj ∈ D + D. Due to (8), we find for each j a vector qj ∈ Q such that aj + bj − 4Kqj ∈ D′. Then x + y = ∑ j∈Z M j (aj + bj ) = = ∑ j∈Z ( M j (aj + bj ) − M j−Lg(M )︸ ︷︷ ︸ =Θ qj ) . We express g(M ) in the explicit polynomial form g(M ) = ∑p−1 l=0 clM l in the rightmost sum: ∑ j∈Z M j−Lg(M )qj = ∑ j∈Z p−1∑ l=0 M j−L+lclqj = = ∑ j∈Z M j (p−1∑ l=0 clqj+L−l ) . Therefore, x + y = ∑ j∈Z M j zj , with zj = aj + bj − (p−1∑ l=0 clqj+L−l ) . (9) Using cL = 4K + C, we get zj = aj + bj − 4Kqj︸ ︷︷ ︸ ∈D′ − ( Cqj + p−1∑ l=0,l ̸=L clqj+L−l ︸ ︷︷ ︸ =:u ) . 191 I. Farkas, E. Pelantová, M. Svobodová Acta Polytechnica All entries of all vectors qj belong to {0, 1, −1}, and thus any component of the vector u in modulus is at most C + ∑ l=0,l ̸=L |cl|. Equation (7) guarantees that the components of u are not greater than cL4 . Since the components are integer, they are at most K = ⌊ cL 4 ⌋ . As D′ + [−K, K]m ⊂ [−3K, 3K)m, so we can conclude that zj ∈ D. In order to compute zj , we needed to know, besides aj and bj , also qj+L, qj+L−1, . . ., qj+L−p+1. Let us stress that qj depends only on aj + bj . Hence, zj is determined by digits on p positions, i.e., the addition is performed by a p-local function. To demonstrate the point (1) of Definition 4, we have to show that zj ̸= 0 for only finitely many indices j ∈ Z. The form of D, D′ and Q guarantees that there exists a unique qj satisfying aj + bj − 4Kqj ∈ D′. In particular, if aj = bj = 0, then qj = 0. The formula (9) implies that zj is non-zero for only finitely many indices j ∈ Z. Let us note that the digit set D is not closed under multiplication by −1. But for each b ∈ D, we can find c, d ∈ D such that −b = c + d. Hence, a subtraction of two vectors x = ∑ Z M j aj and y = ∑ Z M j bj can be viewed as addition of three vectors, and therefore it is computable in parallel as well. It remains to prove that Zm ⊂ FinD (M ). But this is clear, since D ⊂ FinD (M ), FinD (M ) is closed under addition and each x ∈ Zm can be expressed as a finite sum of digits from D. Remark 10. The vectors we add by the parallel algorithm as described in the previous proof are repre- sented by both-sided infinite strings. But only finitely many entries of the strings are occupied by non-zero digits. Assume that x + y = ∑N j=n M j (aj + bj ), for some integers n ≤ N . As stated in the previous proof, if both digits aj and bj are zero, then the algorithm puts qj = 0. The formula (9) for zj implies that zj is zero for all j ≤ n − L − 1 and for all j ≥ N + p − L. Hence, ∑N j=n M j (aj + bj ) = ∑N ′ j=n′ M j zj , where n′ = n − L and N ′ = N + p − L − 1. Example 11. Consider the matrix numeration sys- tem with base matrix M = ( −1 −1 +1 −1 ) ∈ Z2×2. By Example 8, the polynomial g(X) = X 4 + 4 with cL = c0 = 4 is suitable for the parallel addition algo- rithm as described in the proof of Theorem 9. Fol- lowing the proof, we put K = ⌊ cL 4 ⌋ = 1 and define D = [−3, 3)2 ∩ Z2, i.e., the digit set has 36 elements. With such a choice of the digit set D, the addition in (M, D) is computable in parallel. The algorithm for parallel addition constructed in the proof of Theorem 9 is very simple, as the value qj depends only on the digits aj and bj having the same index j. An algorithm with such a property is usually called neighbour free. However, we pay a large price for the simplicity of the algorithm – the digit set is huge. With another choice of the algorithm, the digit set could be substantially smaller, and still sufficient to perform the addition in parallel by means of a p-local function (with a larger parameter p, though). Example 12. Consider the numeration system in C with base β = ı − 1. In [19], a 7-local function of parallel addition in system (β, A) is found for the digit set A = {0, ±1, ±ı}. Let us denote the 7-local function as φ : (A + A)7 7→ A, acting on a 7-tuple (wj , . . . , wj−6) ∈ (A + A)7 by means of an auxiliary quotient function Q : (A + A)6 7→ Q ⊂ Z[ı] as follows: qj := Q(wj , . . . , wj−5) ∈ Q and, consequently, zj := wj + qj−1 − βqj = φ(wj , . . . , wj−6) ∈ A . The local functions φ and Q acting on numbers can be transformed to local functions φ′ : (D + D)7 7→ D = ξ(A) and Q′ : (D + D)6 7→ Q′ = ξ(Q) acting on vectors, by means of the isomorphism ξ : Z[ı] 7→ Z2 defined in Example 2. Thereby, we can define Q′ = ξ ◦ Q ◦ ξ−1 and φ′ = ξ ◦ φ ◦ ξ−1. In other words, with the help of the formulas from 7-local parallel addition on the number system (β, A), we obtain a 7-local parallel addition on the matrix sys- tem (M, D) with digit set size #D = #(ξ(A)) = #A = 5. The vector digit set of size 5 has elements {(0, 0)⊤, (1, 0)⊤, (−1, 0)⊤, (0, 1)⊤, (0, −1)⊤} = D. As proved in [20], the size of 5 is minimal for a digit set allowing parallel addition on the number sys- tem with base β = ı − 1. Consequently, the digit set size #D = 5 must be minimal for parallel addi- tion on the matrix system (M, D) as well, due to the isomorphism ξ. The algorithm for parallel addition of vectors in Z2 presented in Example 12 uses, for the given matrix base M , a digit set of the minimal possible size for parallel addition. However, the way to determine the coefficients qj = Q(wj , . . . , wj−5) is very laborious, as the formula for Q is in fact a look up table with 136 rows. With the digit set size increased from 5 to 9 elements, a lot simpler algorithm for parallel addition can be obtained, as presented in the following example. Example 13. Let us consider M = ( −1 −1 +1 −1 ) and the digit set of size 9 D̃ = {( bc ) : b, c ∈ {0, ±1}} ⊂ Z 2. Again, we construct an auxiliary coefficient function Q̃ : (D̃ + D̃)2 7→ Q̃ ⊂ Z2. The coefficients q̃j ∈ Q̃ produced by Q̃ then provide the result sum digits z̃j ∈ D̃ via local function φ̃ : (D̃ + D̃)3 7→ D̃, as follows: q̃j := Q̃(w̃j , w̃j−2) ∈ Q̃ and, consequently z̃j := w̃j + q̃j−2 − M 2q̃j = φ̃(w̃j , w̃j−2, w̃j−4) ∈ D̃ . 192 vol. 63 no. 3/2023 Positional representation of vectors The coefficient set Q̃ is, just by coincidence, equal to the digit set D̃: Q̃ = {( 00 ) , ± ( 10 ) , ± ( 01 ) , ± ( 11 ) , ± ( 1 −1 ) } . The interim sum digit set W̃ = D̃ + D̃ = {( bc ) : b, c ∈ {0, ±1, ±2}} has 25 elements and can be rewritten using the rota- tion symmetry by the angle π2 as follows W̃ = W̃0 ∪ W̃1 ∪ W̃2 ∪ W̃3 , where W̃0 = {( 00 ) , ( 10 ) , ( 20 ) , ( 11 ) , ( 21 ) , ( 12 ) , ( 22 )} and W̃k = Rk W̃0 for k = 1, 2, 3, with R = ( 0 −1 +1 0 ) . Thanks to the π2 -rotation symmetry of all the sets in question, i.e., D̃, Q̃, and W̃ = D̃ + D̃, it is enough to specify the coefficient function by listing its values Q̃(w̃j , w̃j−2) just for w̃j ∈ W̃0. All the rest can then be obtained by rotation: Q̃ ( Rkw̃j , R kw̃j−2 ) = Rk · Q̃(w̃j , w̃j−2) . For all w̃j ∈ W̃0 and w̃j−2 = ( bc ) ∈ W̃, the coeffi- cients q̃j assigned by Q̃ are listed below • Q̃ ( ( 00 ) , ( bc ) ) := ( 00 ); • Q̃ ( ( 20 ) , ( bc ) ) := ( 01 ); • Q̃ ( ( 22 ) , ( bc ) ) := ( −1 1 ) ; • Q̃ ( ( 10 ) , ( bc ) ) := ( 00 ), if c ≥ 0; • Q̃ ( ( 10 ) , ( bc ) ) := ( 01 ), if c < 0; • Q̃ ( ( 12 ) , ( bc ) ) := ( −1 0 ) , if c ≥ 0; • Q̃ ( ( 12 ) , ( bc ) ) := ( −1 1 ) , if c < 0; • Q̃ ( ( 21 ) , ( bc ) ) := ( 01 ), if b ≤ 0; • Q̃ ( ( 21 ) , ( bc ) ) := ( −1 1 ) , if b > 0; • Q̃ ( ( 11 ) , ( bc ) ) := ( 00 ), if b ≤ 0 ≤ c; • Q̃ ( ( 11 ) , ( bc ) ) := ( −1 0 ) , if b > 0 and c > 0; • Q̃ ( ( 11 ) , ( bc ) ) := ( 01 ), if b < 0 and c < 0; • Q̃ ( ( 11 ) , ( bc ) ) := ( −1 1 ) , if c ≤ 0 ≤ b and ( bc ) ̸= ( 00 ). By checking all the possible variants (w̃j , w̃j−2, w̃j−4) ∈ W̃ 3, it can be verified that the final digit z̃j calculated by z̃j := w̃j + q̃j−2 − M 2q̃j is always an element of the desired digit set D̃. Correct value of the final sum z̃ = ∑ j∈Z M j z̃j is guaranteed by z̃ = ∑ j∈Z M j z̃j = ∑ j∈Z M j (w̃j + q̃j−2 − M 2q̃j ) = ∑ j∈Z M j w̃j + ∑ j∈Z M j q̃j−2 − ∑ j∈Z M j+2q̃j = = w̃ + ∑ j∈Z M j q̃j−2 − ∑ l∈Z M lq̃l−2 = w̃ + 0 = w̃ . Remark 14. Consider M ∈ Zm×m with no eigen- value on the unit circle. Then, at least one eigen- value λ of M satisfies |λ| > 1. The eigenvalue λ is an algebraic integer, as it is a root of the characteristic polynomial f ∈ Z[X] of the matrix M , and, obviously, f is monic. If, moreover, f is irreducible over Q, then Z[λ] = {a0+a1λ+· · ·+am−1λm−1 : a0, . . . , am−1 ∈ Z} and ξ : Z[λ] 7→ Zm defined by ξ(a0 + a1λ + · · · + am−1) = (a0, a1, . . . , am−1)⊤ is an isomorphism. Consequently, any algorithm for parallel addition in the number system (λ, A) with A ⊂ Z[λ] can be transformed by the isomorphism ξ to the matrix nu- meration system (M, ξ(A)). In particular, if A ⊂ Z, then the digit set ξ(A) ⊂ {ce1 : c ∈ Z}, where e1 = (1, 0, . . . , 0)⊤. Any known result on the min- imal size of the digit set allowing parallel addition in the number system with base λ can be applied to the matrix numeration system with base M , thanks to irreducibility of f over Q. Some results on the mini- mal size of digit sets for parallel addition in number systems with base β ∈ C can be found e.g. in [21]. Theorem 9 states that each non-singular matrix M ∈ Zm×m with no eigenvalue on the unit circle can be equipped with a suitable finite digit set D ⊂ Zm such that any integer vector x ∈ Zm is representable in the system (M, D). As shown in [15], the assumption |λ| ≠ 1 for each eigenvalue λ of M is not necessary for the representability of Zm in (M, D). Nevertheless, this assumption is necessary for parallel addition in (M, D), as shown below. Proposition 15. If addition in a matrix numeration system (M, D) with base M ∈ Zm×m and a finite digit set D ⊂ Zm is doable in parallel, then no eigenvalue of M lies on the unit circle. Proof. By Lemma 5, we consider, without a loss of generality, that the digit set D generates Rm – i.e., that Rm is the linear hull of D. Assume, for a contradiction, that M has an eigen- value λ ∈ C on the unit circle, |λ| = 1. Let u ∈ Cm be an eigenvector of the matrix M ⊤ to the eigenvalue λ – i.e., M ⊤u = λu. As D generates Rm, the vector u cannot be orthogonal to all digits, hence there exists a digit d ∈ D such that αu⊤d = 1 for some α ∈ C. Let v be the eigenvector v = αu, so that v⊤d = 1 and v⊤M = λv⊤. Let parallel addition be performed by a p-local function. Denote S = max { ∣∣p−1∑ j=0 λj v⊤dj ∣∣ : dj ∈ D} . As |λ| = 1, there exist infinitely many j ∈ N such that ℜ(λj ) > 12 . Hence one can find N ∈ N and coefficients ε0, ε1, . . . , εN −1 ∈ {0, 1} such that ℜ ( ∑N −1 j=0 εj λ j ) > 193 I. Farkas, E. Pelantová, M. Svobodová Acta Polytechnica 2S. Let x = ∑N −1 j=0 M j xj with xj ∈ D such that |ℜ(v⊤x)| = max {∣∣ℜ(v⊤( N −1∑ j=0 M j dj ))∣∣ : dj ∈ D} = max {∣∣ℜ(N −1∑ j=0 λj v⊤dj )∣∣ : dj ∈ D} . Since 1 and 0 belong to {v⊤d : d ∈ D}, we have |ℜ(v⊤x)| ≥ ℜ ( N −1∑ j=0 εj λ j ) > 2S. (10) The p-local function used to add x + x produces digits zj ∈ D such that x + x = N +p−2∑ j=N M j zj + N −1∑ j=0 M j zj + −1∑ j=−p+1 M j zj . After multiplication of x + x by the vector v⊤ from the left, we have v⊤(x + x) = λN p−2∑ j=0 λj v⊤zN +j +v⊤ N −1∑ j=0 M j zj +λ−p p−1∑ j=1 λj v⊤zj−p . (11) The definitions of S and x guarantee that ∣∣p−2∑ j=0 λj v⊤zN +j ∣∣ ≤ S, ∣∣p−1∑ j=1 λj v⊤zj−p ∣∣ ≤ S, and ∣∣ℜ(v⊤(N −1∑ j=0 M j zj ))∣∣ ≤ |ℜ(v⊤x)| . Using these inequalities and the triangle inequality, together with (11) and the fact that |ℜ(y)| ≤ |y| for every y ∈ C, and with |λ| = 1, we get 2|ℜ(v⊤x)| ≤ |2v⊤x| ≤ 2S + |ℜ(v⊤x)| which contradicts (10). 4. Eventually periodic representations with expansive matrix base T. Vávra in [22] shows, for any algebraic complex base β with |β| > 1, that there exists a suitable (finite) digit set A ⊂ Z such that any x ∈ Q(β) has an eventually periodic expansion in this base, i.e., x = ∑N j=−∞ aj β j , where the sequence (aj )j≤N of digits from A is eventually periodic. Looking for an analogy to this result in the matrix systems, we first have to give a meaning of the previous sum in the case when the number base β is replaced with a matrix base M and (integer) number digits aj by (integer) vector digits dj . If a matrix M ∈ Zm×m is expansive, then M −1 is contractive and there exists a vector norm ∥·∥c in R m such that ∥∥M −1∥∥ < 1, where ∥·∥ is the matrix norm induced by the vector norm ∥·∥c, see [23]. Let us recall that for these two norms, the following inequalities hold: ∥Ax∥c ≤ ∥A∥ . ∥x∥c and ∥AB∥ ≤ ∥A∥ . ∥B∥ for every x ∈ Rm and A, B ∈ Rm×m. If (dj )N−∞ is a sequence of (vector) digits from a finite set D ⊂ Rm, then the vector ∑N j=−∞ M j dj is well defined, as the sequence ( N∑ j=−n M j dj )+∞ n=0 is a Cauchy sequence. Indeed, let us denote r :=∥∥M −1∥∥ < 1 and D := max{∥d∥c : d ∈ D}. The triangle inequality implies for every n, q ∈ N that∥∥∥∥∥∥ N∑ j=−n M j dj − N∑ j=−n−q M j dj ∥∥∥∥∥∥ c = ∥∥∥∥∥∥ −n−1∑ j=−n−q M j dj ∥∥∥∥∥∥ c = ∥∥∥∥∥∥ n+q∑ j=n+1 ( M −1 )j d−j ∥∥∥∥∥∥ c ≤ n+q∑ j=n+1 rj D ≤ Drn+1 1 − r , so the value Dr n+1 1−r can be made arbitrarily small for all n > n0, with sufficiently large n0 ∈ N. Consequently, if M is expansive, then there exists lim n→+∞ ∑N j=−n M j dj , which may be denoted as∑N j=−∞ M j dj . In the remaining part of this chapter, we focus on matrix numeration systems with M being an expansive matrix. Matrix numeration systems with base M being an expansive matrix have been intensively studied since the work of Vince. The main focus of the research in this area is on the systems where each lattice point has a unique representation. Recall that a lattice in Rm is the set of all integer combinations of m linearly independent vectors. A lattice numeration system can be formalised as follows (see [24]): Definition 16. Let Λ be a lattice, M : Λ → Λ be a linear operator (also called the base or radix) and let D be a finite subset of Λ containing 0 (called the digit set). The triplet (Λ, M, D) is called a generalised number system (GNS) if every element x ∈ Λ has a unique finite representation of the form x = N∑ j=0 M j dj , where N ∈ N, dj ∈ D for every j = 0, 1, . . . , N and dN is a non-zero digit (if x ̸= 0). Characterisation of triplets (Λ, M, D) forming GNS seems to be a difficult task. To quote a necessary 194 vol. 63 no. 3/2023 Positional representation of vectors condition, we recall that two elements (lattice points) x, y ∈ Λ are congruent modulo M if they belong to the same residue class, i. e., if (x − y) ∈ M Λ. We denote this fact by x ≡Λ y (mod M ). Theorem 17. [13] If (Λ, M, D) is a GNS, then the following holds: (1.) The operator M is expansive. (2.) The digit set D is a complete residue system modulo M. (3.) det(M − I) ̸= ±1. Note that the number of residue classes modulo M equals | det(M )|, hence the GNS has exactly #D = | det(M )| digits. A sufficient condition for GNS was provided by L. Germán and A. Kovács in [24]. Theorem 18. [24] Let M : Λ 7→ Λ be a non-singular linear operator. If the spectral radius of the inverse operator M −1 is less than 12 , then there exists a digit set D ⊂ Λ such that (Λ, M, D) is a GNS. Any lattice Λ ⊂ Rm is just an image of Zm under a non-singular linear map. Since a linear map does not change the GNS property, we can consider, without a loss of generality, that Λ = Zm. A linear operator mapping Zm to Zm corresponds to multiplication of integer vectors by a matrix M ∈ Zm×m. Further results are known regarding the existence of GNS with special types of the digits sets: • If D = {k(1, 0, . . . , 0)⊤) : k ∈ Z, 0 ≤ k < | det(M )|}, we speak about canonical systems. • If D = {k(1, 0, . . . , 0)⊤) : k ∈ Z, − 12 | det(M )| < k ≤ 12 | det(M )|}, the digit set is called symmetric. • If D contains the lattice point of the smallest norm from each residue class (modulo M ), then the digits set D is said to be dense. The choice of the smallest lattice point is not necessarily unique. • The adjoint digit set consists of those lattice points which belong to | det(M )| · [− 12 , 1 2 ) m. The results on GNS with the special digits sets can be consulted in [25]. If we abandon the requirement of uniqueness for the representation of vectors from Zm, then the question on existence of a suitable digit set for a given expan- sive base M is much more simpler. In fact, using a sufficiently redundant digit set D allows to represent all vectors in Rm. First, we focus on vectors from Rm which have eventually periodic representation in the numeration system (M, D), i.e., we focus on the set PerD (M ) = { N∑ j=−∞ M j dj : dj ∈ D, (dj )N−∞ eventually periodic } . To work with eventually periodic representations, we exploit a well known fact about contractive ma- trices, namely that (I − A)−1 = ∑+∞ j=0 A j for any contractive matrix A ∈ Cm×m. Lemma 19. Let M ∈ Zm×m be an expansive matrix and D ⊂ Zm. If x ∈ PerD (M ), then x ∈ Qm. Proof. First, assume that an (M, D)-representation of x has the form 0 • (d−1d−2 · · · d−p)ω . It means that x = M −1d−1 + M −2d−2 + · · · + M −pd−p + M −px, which implies that x = (I−M −p)−1(M −1d−1+M −2d−2+· · ·+M −pd−p) . Since all elements of M are integer, it follows that all the matrix powers M −j with j ∈ N and (Im −M −p)−1 belong to Qm×m. Therefore, x ∈ Qm. Now, let us assume that a representation of x is eventually periodic and the preperiodic part ends at an index −k ∈ Z, −k ≤ 0. Then M kx equals z + y, where z = ∑N j=0 M j dj and y has the purely periodic form y = 0 • (d−1d−2 · · · d−p)ω . Obviously, z ∈ Zm and, by the previous argumentation, y ∈ Qm. Hence x = M −k(z + y) belongs to Qm as well. To study the implication opposite to the previous Lemma 19, we use the concept of parallel addition. Lemma 20. If the digit set D allows parallel addition on FinD(M ), then it allows parallel addition also on PerD (M ), and the result of addition is again eventu- ally periodic. It means that, for such a digit set D, the set PerD (M ) is closed under addition. Proof. Let us explain this statement, assuming the parallel addition on FinD(M ) is a p-local function, with p = r + 1 + t, memory r and anticipation t. Let ℓx, ℓy be the lengths of the periods of (M, D)- representations of the summands x, y, and denote ℓxy := ℓxℓy . Clearly, both x and y have (M, D)- representations with the same period ℓxy , and the same holds for the (M, D + D)-representation of their (eventually periodic) sum w = x + y calculated by a pure summation of digits on each position separately. It is clear that, by applying the p-local function φ : (D + D)p 7→ D onto the (M, D + D)-representation of the interim sum w, we obtain an eventually periodic string over the alphabet D. In other words, x + y has an eventualy periodic (M, D)-representation. Theorem 21. Let M ∈ Zm×m be an expansive ma- trix. Then there exists a finite digit set D ⊂ Zm such that PerD (M ) = Qm. Proof. By Theorem 9 and Lemma 5, there exists a finite digit set D such that addition in (M, D) can be performed in parallel. Due to Lemma 19, it remains to prove only the inclusion Qm ⊂ PerD(M ). We denote by es the vector from Zm whose sth coordinate equals 1 and all other coordinates are zero. In the 195 I. Farkas, E. Pelantová, M. Svobodová Acta Polytechnica first step, we show that for each q ∈ N and each s = 1, 2, . . . , m, the vector 1 q es has an eventually periodic (M, D)-representation. For this purpose, we define a congruence relation on the matrices from Zm×m. We say that A ∈ Zm×m is congruent modulo q to B ∈ Zm×m, if (A − B) ∈ q Zm×m. As the number of congruence classes is finite (for a fixed q ∈ N), we find in the list I, M, M 2, M 3, . . . two matrices from the same congruence class. In other words, there exist k, ℓ ∈ N, ℓ > 0 such that M k+ℓ − M k = qC for some C ∈ Zm×m, or, equivalently 1 q I = M −ℓ−k (I − M −ℓ)−1 C = M −ℓ−k ( +∞∑ j=0 M −ℓj ) C . (12) Let c1 denote the first column of the matrix C. As Zm ⊂ FinD(M ), we can write c1 = ∑n t=0 M tft with ft ∈ D. It is due to Lemma 6 and Remark 10 that the bottom index of the sum equals zero, as M is expansive, so all of its eigenvalues are > 1 in modulus. The first column of the matrix equality (12) then equals 1 q e1 = M −ℓ−k +∞∑ j=0 M −ℓj c1 = n∑ t=0 +∞∑ j=0 M −ℓj−ℓ−k+tft . Thus, we have expressed 1 q e1 as a sum of n + 1 vectors with eventually periodic (M, D)-representation. Since PerD (M ) is closed under addition, due to Lemma 20, the vector 1 q e1 belongs to PerD(M ) as well. Anal- ogously, the same holds for 1 q e2, . . . , 1 q em and for − 1 q e1, . . . , − 1q em, therefore, they are also elements of PerD (M ). In the second step, we consider an arbitrary vector x ∈ Qm. We find q ∈ N and integer nubers p1, . . . , pm such that x = p1 ( 1 q e1 ) + · · · + pm ( 1 q em ) . It means that x is a sum of (|p1| + · · · + |pm|) vectors from the set PerD(M ), which is closed under addition. Hence x ∈ PerD (M ). Corollary 22. Let M ∈ Zm×m be an expansive matrix. Then there exists a finite digit set D ⊂ Z such that every x ∈ Rm has an (M, D)-representation. Proof. Let ∥·∥c be the vector norm of R m, for which the induced matrix norm of the contractive ma- trix M −1 is ∥∥M −1∥∥ = r < 1. Since M is expansive, any vector y ∈ Zm has an (M, D)-representation in the form y = ∑N j=0 M j dj for some N ∈ N and dj ∈ D. In general, the repre- sentation is not unique. We denote by height(y) the minimal N ∈ N among all the (M, D)-representations of y. Let x ∈ Rm and ( x(n) ) n∈N be a sequence of vec- tors from Qm such that lim n→∞ xn = x. By the previous theorem, we have x(n) = ∑Nn j=−∞ M j d (n) j . Denote the integer and fractional parts of x(n) by y(n) := ∑Nn j=0 M j d (n) j and z (n) := ∑−1 j=−∞ M j d (n) j , respectively. Obviously, y(n) ∈ Zm. Assume that (M, D)-representations of the integer parts y(n) sat- isfy Nn = height(y(n)) for every n ∈ N. The size of the fractional parts z(n) is bounded. Indeed,∥∥z(n)∥∥ c = ∥∥∥∑−1j=−∞ M j d(n)j ∥∥∥ c ≤ ∑−1 j=−∞ r −j D = rD 1−r . Since any convergent sequence is bounded, the integer parts y(n) ∈ Zm are bounded as well, as∥∥y(n)∥∥ c ≤ ∥∥x(n) − z(n)∥∥ c ≤ ∥∥z(n)∥∥ c + ∥∥x(n)∥∥ c . It means that y(n) can take only finitely many values in Zm, and thus their heights Nn are bounded as well, say by N . Hence, we can rewrite the representation of x(n) for each n ∈ N into the form x(n) = ∑N j=−∞ M j d (n) j with the uniform upper index N of the sums (if necessary, we add leading zero coefficients to sums). Now, we are ready to find an (M, D)-representation of x = lim n→∞ x(n). We construct the sequence dN dN −1 · · · d0 • d−1d−2 · · · of digits from D. A digit which appears infinitely times among x(n)N will be chosen as dN . Then, we chose dN −1 as such a digit that the pair of digits dN dN −1 appears infinitely many times among x (n) N x (n) N −1. Similarly, dN −2 is chosen as such a digit that the triplet dN dN −1dN −2 appears infinitely many times among x(n)N x (n) N −1x (n) N −2, and so on. By this con- struction, for every step l ∈ N, l ≥ 1, there exists kl ∈ Z such that the strings dN dN −1 · · · d0•d−1d−2 · · · and x(kl)N x (kl) N −1 · · · x (kl) 0 • x (kl) −1 x (kl) −2 · · · have a common prefix of length at least l. Therefore,∥∥∥∥∥∥ N∑ j=−∞ M j dj − N∑ j=−∞ M j x (kl) j ∥∥∥∥∥∥ c = ∥∥∥∥∥∥ N −l∑ j=−∞ M j ( dj − x (kl) j )∥∥∥∥∥∥ c ≤ 2D +∞∑ j=l−N rj = 2D 1 − r rl−N , where D denotes max{||d||c : d ∈ D}. Since 2D1−r r l−N tends to 0 with l → +∞, we obtain N∑ j=−∞ M j dj = lim l→+∞ x(kl) = lim n→+∞ x(n) = x , and thus ∑N j=−∞ M j dj is an (M, D)-representation of x. 5. Open questions We have focused only on two questions connected with (M, D)-representation of vectors: computability of addition in parallel and eventually periodic represen- tations. Many open problems still remain unresolved. Let us list some of them: (1.) What is the minimal size of a digit set D ⊂ Zm with the property Zm ⊂ FinD(M )? This question 196 vol. 63 no. 3/2023 Positional representation of vectors was already tackled in [26] for very special matrices, namely for Jordan blocks Jm(1) corresponding to the eigenvalue 1. (2.) Is it possible for a given non-singular matrix M ∈ Zm×m to find a (finite) digit set D ⊂ Zm such that every element in FinD(M ) has a unique representation in this numeration system? If M is expansive, then the size of the suitable digit set (if it exists) is | det(M )|, see [13]. What is an analogy of this result for a non-expansive matrix? (3.) Does there exist any (finite) digit set such that multiplication of vectors from Rm by a scalar x ∈ R can be performed by an on-line algorithm? Note that K. Trivedi and M. Ercegovac in [27] designed on-line algorithms for the multiplication and divi- sion of two numbers represented in a numeration system (β, A) with β ∈ N. Their algorithms were later generalised to numeration systems (β, A) with base β being a (real or complex) Pisot number [28]. Acknowledgements Edita Pelantová acknowledges financial support by The Ministry of Education, Youth and Sports of the Czech Re- public, project no. CZ.02.1.01/0.0/0.0/16_019/0000778. References [1] A. Cauchy. Sur les moyens d’éviter les erreurs dans les calculs numériques. No. 11 in série I. C.R. Acad. Sc. Paris, France, 1840. [2] V. Grünwald. Intorno all’aritmetica dei sistemi numerici a base negativa con particolare riguardo al sistema numerico a base negativo-decimale per lo studio delle sue analogie coll’aritmetica ordinaria (decimale). 23. Giornale di matematiche di Battaglini, Italy, 1885. [3] A. Rényi. Representations for real numbers and their ergodic properties. Acta Mathematica Academiae Scientiarum Hungaricae 8:477–493, 1957. https://doi.org/10.1007/BF02020331 [4] K. Schmidt. On periodic expansions of Pisot numbers and Salem numbers. Bulletin of the London Mathematical Society 12(4):269–278, 1980. https://doi.org/10.1112/blms/12.4.269 [5] T. Vávra, F. Veneziano. Pisot unit generators in number fields. Journal of Symbolic Computation 89:94–108, 2018. https://doi.org/10.1016/j.jsc.2017.11.005 [6] D. E. Knuth. A imaginary number system. Communications of the ACM 3(4):245–247, 1960. https://doi.org/10.1145/367177.367233 [7] W. Penney. A “binary” system for complex numbers. Journal of the ACM 12(2):247–248, 1965. https://doi.org/10.1145/321264.321274 [8] B. Kovács, A. Pethö. Number systems in integral domains, especially in orders of algebraic number fields. Acta Scientiarum Mathematicarum 55:287–299, 1991. http://acta.bibl.u-szeged.hu/15313/1/math_055_ fasc_003_004_287-299.pdf. [9] P. Kirschenhofer, J. Thuswaldner. Shift radix systems: A survey. Numeration and Substitution B46:1–59, 2014. http://hdl.handle.net/2433/226207. [10] A. Avizienis. Signed-digit numbe representations for fast parallel arithmetic. IRE Transactions on Electronic Computers EC-10(3):389–400, 1961. https://doi.org/10.1109/TEC.1961.5219227 [11] A. Vince. Radix representation and rep-tiling. In Proceedings of the 24-th Southeastern International Conference on Combinatorics, Graph Theory, and Computing, vol. 98, pp. 199–212. 1993. [12] A. Vince. Replicating tessellations. SIAM Journal on Discrete Mathematics 6(3):501–521, 1993. https://doi.org/10.1137/0406040 [13] A. Kovács. Number expansions in lattices. Mathematical and Computer Modelling 38(7):909–915, 2003. https://doi.org/10.1016/S0895-7177(03)90076-8 [14] J. Jankauskas, J. Thuswaldner. Characterization of rational matrices that admit finite digit representations. Linear Algebra and its Applications 557:350–358, 2018. https://doi.org/10.1016/j.laa.2018.08.006 [15] E. Pelantová, T. Vávra. On positional representation of integer vectors. Linear Algebra and its Applications 633:316–331, 2022. https://doi.org/10.1016/j.laa.2021.10.018 [16] D. Lind, B. Marcus. An Introduction to Symbolic Dynamics and Coding. Cambridge University Press, Cambridge, 1995. https://doi.org/10.1017/CBO9780511626302 [17] C. Frougny, E. Pelantová, M. Svobodová. Parallel addition in non-standard numeration systems. Theoretical Computer Science 412(41):5714–5727, 2011. https://doi.org/10.1016/j.tcs.2011.06.028 [18] S. Akiyama, P. Drungilas, J. Jankauskas. Height reducing problem on algebraic integers. Functiones et Approximatio Commentarii Mathematici 47(1):105–119, 2012. https://doi.org/10.7169/facm/2012.47.1.9 [19] J. Legerský, M. Svobodová. Construction of algorithms for parallel addition in expanding bases via Extending Window Method. Theoretical Computer Science 795:547–569, 2019. https://doi.org/10.1016/j.tcs.2019.08.010 [20] J. Legerský. Minimal non-integer alphabets allowing parallel addition. Acta Polytechnica 58(5):285–291, 2018. https://doi.org/10.14311/AP.2018.58.0285 [21] C. Frougny, E. Pelantová, M. Svobodová. Minimal digit sets for parallel addition in non-standard numeration systems. Journal of Integer Sequencers 16(2):1–36, 2013. https://cs.uwaterloo.ca/ journals/JIS/VOL16/Frougny/frougny3.pdf. [22] T. Vávra. Periodic representations in Salem bases. Israel Journal of Mathematics 242:83–95, 2021. https://doi.org/10.1007/s11856-021-2123-3 [23] E. Isaacson, H. Keller. Analysis of numerical methods. John Wiley & Sons, New York, 1966. [24] L. Germán, A. Kovács. On number system constructions. Acta Mathematica Hungarica 115:155–167, 2007. https://doi.org/10.1007/s10474-007-5224-5 197 https://doi.org/10.1007/BF02020331 https://doi.org/10.1112/blms/12.4.269 https://doi.org/10.1016/j.jsc.2017.11.005 https://doi.org/10.1145/367177.367233 https://doi.org/10.1145/321264.321274 http://acta.bibl.u-szeged.hu/15313/1/math_055_fasc_003_004_287-299.pdf http://acta.bibl.u-szeged.hu/15313/1/math_055_fasc_003_004_287-299.pdf http://hdl.handle.net/2433/226207 https://doi.org/10.1109/TEC.1961.5219227 https://doi.org/10.1137/0406040 https://doi.org/10.1016/S0895-7177(03)90076-8 https://doi.org/10.1016/j.laa.2018.08.006 https://doi.org/10.1016/j.laa.2021.10.018 https://doi.org/10.1017/CBO9780511626302 https://doi.org/10.1016/j.tcs.2011.06.028 https://doi.org/10.7169/facm/2012.47.1.9 https://doi.org/10.1016/j.tcs.2019.08.010 https://doi.org/10.14311/AP.2018.58.0285 https://cs.uwaterloo.ca/journals/JIS/VOL16/Frougny/frougny3.pdf https://cs.uwaterloo.ca/journals/JIS/VOL16/Frougny/frougny3.pdf https://doi.org/10.1007/s11856-021-2123-3 https://doi.org/10.1007/s10474-007-5224-5 I. Farkas, E. Pelantová, M. Svobodová Acta Polytechnica [25] P. Hudoba, A. Kovács. Toolset for supporting the research of lattice based number expansions. Acta Cybernetica 25(2):271–284, 2021. https://doi.org/10.14232/actacyb.289524 [26] J. Caldwell, K. Hare, T. Vávra. Non-expansive matrix number systems with bases similar to jn(1). [2022-02-01]. arXiv:2110.11937 [27] K. Trivedi, M. Ercegovac. On-line algorithms for division and multiplication. IEEE Transactions on Computers C-26(7):681–687, 1977. https://doi.org/10.1109/TC.1977.1674901 [28] C. Frougny, M. Pavelka, E. Pelantová, M. Svobodová. On-line algorithms for multiplication and division in real and complex numeration systems. Discrete Mathematics & Theoretical Computer Science 21(3), 2019. https://doi.org/10.23638/DMTCS-21-3-14 198 https://doi.org/10.14232/actacyb.289524 https://arxiv.org/pdf/2110.11937.pdf https://doi.org/10.1109/TC.1977.1674901 https://doi.org/10.23638/DMTCS-21-3-14 Acta Polytechnica 63(3):188–198, 2023 1 Introduction 2 Preliminaries 3 Parallel addition in matrix numeration systems 4 Eventually periodic representations with expansive matrix base 5 Open questions Acknowledgements References