THE UNIVERSITY OF MICHIGAN COLLEGE OF ENGINEERING Department of Electrical Engineering Information Systems Laboratory Interim Engineering Report ON THE TRIANGULARITY OF THE CARRY PROPAGATION MATRIX OF NON-REDUNDANT WEIGHTED SYSTEMS T.R.N. Rao ORA Project 04879 under contract with: UNITED STATES AIR FORCE AERONAUTICAL SYSTEMS DIVISION CONTRACT NO. AF 33(657)-7811 WRIGHT-PATTERSON AIR FORCE BASE, OHIO administered through: OFFICE OF RESEARCH ADMINISTRATION ANN ARBOR March 1963

TABLE OF CONTENTS Page NOTATION v SUMMARY vii I. INTRODUCTION 1 II. SOME USEFUL THEOREMS IN DETERMINANTS 4 III. MODULE THEORY AND TRIANGULAR FORMS OF SUBMODULES FOR NONREDUNDANT NUMBER SYSTEMS 17 VI. CONCLUSION 25 REFERENCES 26 iii

NOTATION Z ring of integers ZM integers modulo M IxIM residue of x modulo M such that 0 < IXMI < M n.. matrix ckl * Ckn__ C11 ~ Cln determinant Cnl. cnn I|x absolute value of x ae a is an element of 6 such that C c K C is a subset of K S/C if C is a subgroup of I, ~/C is a quotient group V

SUMMARY It is shown in this report that in a non-redundant weighted system with moduli ml,m2,..., mn, representing integers modulo M = ml m2... nn, the carry propagation must take place in only one direction. This is shown by the existence of a matrix C (called carry matrix) obeying the relation below: ml 0 0 0 Pi -c21 m2 0 0 P2 O(mod M) -cnl mn n where 0 > cij > mj, p1,..., Pn are the digit weights of the system. This is proved in two parts. The first part gives a theorem relating to a (n x n) matrix C, which has off-diagonal elements < 0, and, at most, one of the diagonal elements non-positive and the rest positive, where the determinant of C is equal to the product of diagonals if and only if the matrix is triangularable. The second part introduces the theory of modules and a nonredundant number system as a quotient module. We also discuss the mappings of an n-dimensional Z-module into the integers modulo M. The kernel of sucha mapping is the carry propagation matrix which should be triangularable in order that the system be non-redundant and complete. vii

I. INTRODUCTION It is well known that carry propagation in some weighted number systems, such as decimal and binary systems, takes place from one digit to the next higher ordered digit. In other weighted systems such as residue systems,l no carries are produced. However, it is well established in all known systems to date that if the system is non-redundant and complete, the carry propagation must take place in only one direction. In other words, the carries cannot flow back and forth. This can also be explained by a representation of a carry propagation matrix which has a great significance in the theory of modules applied to linear number systems. 6 D. P. Rozenberg3 has shown that a number system related to a residue system can be complete if it has a basis of elements that is triangular, with the diagonal elements relatively prime to the moduli. Every residue related system has to deal with moduli that are relatively prime. However, the necessity of a triangular basis had not been established. H. L. Garner worked out the necessary and sufficient conditions on the digit weights of a non-redundant system, and found also that if the moduli are relatively prime, a triangular weight matrix can be constructed. R. F. Arnold has used LeVeque's theorem on the existence of a modulus, whose elements from a subgroup of the number system to show the triangular nature of the submodule. This report gives an entirely different and simple solution to the problem. As a preliminary step, let us examine the triangular representation of a few familiar examples of number systems. 1

(1) Conventional decimal systems representing integers modulo 1000 can have a carry matrix C as below: 10 0 0 C = -1 10 0 0 -1 10 Since the digit weights pi = 100, P2 = 10, p3 = 1, we have 10 0 0 100 -1 100 0 -1 10 1 Also, the system can be represented as a quotient module //C. /10 0 O0 S/C = z + Z + z/ -1 10 0 /,0 -1 10 (2) For a four-bit binary system to represent Z16, we can write //C as 2 0 0 0 -1 2 0 0 Z z+ Z + Z 0 -1 2 0 0 0 -1 2 since p1 = 8, P2 = 4, p3 = 2, p4 = 1 2

2 0 0 0 8 -1 2 0 0 4 - O(mod 16) 0 -1 2 0 2 0 0 -1 2 1 (3) For a residue system with moduli 2, 3, 5, 7 to represent Z210, the quotient module 5/C is 2 0 0 0 0 5 0 0 z + + z+ Z 0 0 5 0 0 0 0 7 The carry matrix is diagonal indicating there are no carry flows at all. The weights are pi = 105, = 70, p3 126, 120 2 0 0 0 105 0 3 0 0 70 = O(mod 210) 0 0 5 0 126 0 0 0 7 120 These examples are provided to show the triangular nature of the carry matrix of non-redundant weighted number systems. For the definitions of Z-modules and quotient modules look into pages 17-20 of this report. 5

II. SOME USEFUL THEOREMS IN DETERMINANTS Let C be a k x k matrix of the form shown below: ml C12. Cln c21 m2. Cn * c Cnl.. mn mi m2... mn are used for the principal diagonal to be easily distinguished from the rest. A diagonal permutation on C is a column and row permutation as defined below. Definition 1. If ith and jth rows are exchanged, followed by an ith and jth column exchange, then the matrix is said to be diagonally permuted. Such row and column permutations are said to be diagonal permutations. Diagonal permutations satisfy the following: (1) The set of elements mi m2 o. mn of the matrix C remains on the principal diagonal after a diagonal permutation, and also after any number of repeated diagonal permutations. (2) The determinant of C is unaltered in sign and magnitude by diagonal permutation because row and column shifts are done an even number of times and the sign change takes place an even number of times. Definition 2. If a (k x k) matrix C can be made (lower or upper) triangular by a necessary number of repeated diagonal permutations, then C is said to be triangularable. 4

Lemma I. If a (k x k) matrix C is triangularable, then there exists a j < k such that cji = 0 for j + i. Proof. The lemma in essence means that there must exist a row in C in which off-diagonal elements are zero. ml c12. ~ Clk c21 m2.. c2k Now let C = Ckl Ck2 * * m Let C' be the (lower) triangularised matrix of C. Then ml 0.. 0 c~z m2 ~. ~ C.l mI2 0. 0 0 ckl mk C' can also be diagonally permuted to obtain C (as the diagonal permutations have inverses). The first row of C' has at most one non-zero element. Column permutations of C' do not change the number of non-zero elements of any row. A row permutation involving the first row (which has at most one non-zero element) and jth row would leave the jth row with one non-zero element. Hence, there will always be a row having ml on the diagonal with that row satisfying 5

the required condition. Since C is obtained by repeated diagonal permutation of C', C satisfies the conditions; hence, the lemma is proved. From now on, all the matrices and determinants are over integers. Theorem lo Let C be a matrix as shown below: ml -C12 -Cln -c21 m2 -C2n C =.. -Cnl mn where cij is any non-negative integer, and mi > 0 for i = 2, 3,..., n mi can be any integer. n Then determinant C < T mi i=l Proof. For n = 1, 2 the theorem is true. Assume the theorem is true for n = 1, 2,..., k-1. Claim. The theorem is true for n = k. mi -C12 -clk -c21 m2 -C2k Determinant C = -Ckl -Ck2 mk k i-1 Determinant C = mlAll - cilAi(-l) i =2 /Ajl is minor of, min \for j = 2,...,n mlAli + ( 1) ciiAi 6

A11 is a k-l by k-l determinant satisfying the conditions of the theorem so by induction hypothesis All < m2,..., mk so mlAll < ml, m2,..., mk If we can show that each of the terms in the summation is < 0, the proof will be complete. Consider (-1) cilAi -c12 -c13 -clk m2 -C23 -cak Ail = -ci-l2 ~ -ci_-,k -ci+1,2 ~ -ci+, k -ck,2 mk For shifting the first row of Ail to the place shown by dots, i-2 displacements are necessary. Hence (-1) Ail would be a new determinant. This shifting is done to leave all off-diagonal elements < 0 so that the induction hypothesis is satisfied. (This step is done several times in the proofs of other lemmas and theorems in this report.) 7

m2 ~ -C2k -Cii,2 mii -ci - i,k = (-1) -C12.* -Cli -clk -ci+i, 2 * -i+i -Ci+ik -Ckl. mk Let the new determinant be Ail Ail = (-1) Ahi Ail is a k-l by k-l determinant and by repeated diagonal permutation (the principal diagonal permuted) we can obtain the negative element to the top of the principal diagonal. -cii -C12 -cik -cmi m2 -c2k Ail = -ci-li * mi-i. -Ci-i,k -ci+li' ~ mi+i -ci+ik -ck,i -ck2 mk From the Induction Hypothesis we have Ail < -cli, m2,..., mi-i, mi+l,..* mk < 0 as cli, mj are all non-negative for j = 2, 5,..., n 8

the summation term 2i-(2)i(l) i-2 ci^- - Ail = i(-l)i2 Ail has the same sign as Ail < 0 determinant C < ml m2... mk Hence, the theorem is proved. If mi > 0 for all i $ j and mj is any integer, the theorem still holds good. This is because by diagonal permutation we can obtain the jth row to the first, and diagonal permutation does not change the determinant of the matrix. The diagonally permuted matrix has the first element on the diagonal any integer while the rest on the diagonal are > O. All off-diagonal elements are < O. Hence, we have ml -C12 ~ -Cn -c21 m2 -C2n < ml m2..* mn -cnl - n2 ~ -mn provided cij > 0 for all i + j; and mi > 0 for i = 1,2,...,j-l,j+l,...,n and mj is any integer. Lemma 2. If there are two determinants ck-1, Dk such that 9

ml -C12 C * -C, k-l -C21 m2 -C2, k-i Ck1 = -Ck-, 1 mk- 1 cij > 0 mi > 0 for i = 1,2,...,j-l,j+l,...,n mj is any integer 0 > j > k-1 ml 0 0 0 -d21 m2 -d23 -d2k Dk -d3 -d32 m3 -d3k -dk, mk dij > O mi > 0 for i = 1,2,...,-1l,+1,...,n mi any integer 0 < < k and if k-1 Ck.l =;l mi-r- ck_.l is triangularable i=l then k Dk = m i D is triangularable. i=l 10

Proof. Dk = m1A11 m2 -d23 -d2k -d32 m3 -dsk where Al = -dk, mk Dk = mAjl = mi m2... mk A11 = m2... mk All is a k-1 by k-l determinant whose determinant is equal to the product of the principal diagonal elements. Thus A11 is triangularable. Diagonal permutation of Dk so that All is triangularised would leave the first row of Dk intact (only zeros are permuted). Hence, we will have Dk triangular. The proof is then complete. Theorem 2. Let mi -C12 -cin -c21 m2 -C2n Dn n -cnI -cn2 in such that c ik > 0 mk > 0 for k + ~ for some a, 1 < < n. m~ any integer n then Dn = yi mi is and only if Dn is triangularable. i=l 11

Proof. Let Dn be triangularable. Then let Dn be triangularised to D'. As triangularisation does not change the determinant in magnitude and sign, we have D; = Dn. Since DA is triangular and the diagonal is only permuted by triangularising, we have Dn = Dn = mi m2.*. mn. Dn is triangularable -- Dn = ml m2... mn Yet to be proved is Dn = ml m2... mn -Dn is triangularable. Proof by induction Induction Step: For n = 1, it is trivial. For n = 2, ml -C12 = mi, mi2 -c21 m2 _-r c21 C12 = 0 -= C12 or c21 = 0 Hence, D2 is already triangular. Induction Hypothesis: The theorem is true for n = 1,2,..., k-l. Claim. The theorem is true for n = k. mi -C12 ~* -clk Dk = -C21 m2. -c2k -ckl.. mk 12

Let m2,..., mk be > O. ml may be. any integer. If that is not the case, we can always diagonally permute and reorder the moduli to obtain the condition m2,..., mk all > 0 = mlAll + (-1) iAi = m m2... mk m2 -C23 -C2k -c32 m3 -c3k All = mk2 mk From Theorem 1 we have A11 < m2 m3... mk and as all the terms in this sulnmation are negative n miAni + (-1) cilAil = ml m2... mk i=2 = Ail = 0 i = 2,.,k. A11 = m2... mk. From the Induction Hypothesis, A1l is triangularable. Hence, let Dk be diagonally permuted so that A1l is lower triangular. Now reordering the subscripts (as m2, mk are all arbitrary) we have ml -C12 -C13 -clk- 1 clk -c21 m2 0 0 0 0 -C31 -C32 m3 0 0 0 D = mkl 0 -Ckl mk Figure 1 13

If there exists a row that has all zero terms (except probably the diagonal element), then by so triangularising we can bring that row to the top by diagonal permutation. The resulting determinant would look like mi 0 0 -cji m -Cjk -Cki mk All off-diagonal elements will be < 0 since the determinant = ml m2... mk and the All is a k-l by k-l1 determinant such that Anl = product of diagonals, and hence, by the Induction Hypothesis is triangularable. By triangularising All, the result will be a k x k determinant that is also triangular because of the off-diagonal zeros in the first row. Thus, the theorem will be true. Let us assume that there is no row among Dk having the off-diagonal elements all zero. lml -c 2 -c13 -cik -c21 m2 0 0 Let Dk = -c31 -C32 m3 0 0 -Cki -Ck2 mk k D = "iMiA + (-1) Cii -=i mi m2... mk i =2 All = m2... mk Each of the terms in summation is < 0. cliAli = O; for i =2,..., ko 14

Case 1. Let C12 / 0. Then A12 = 0 A12 = -21 m3... mn = 0. C21 = 0. The second row then has all off-diagonal elements equal to zero which is a contradiction. c12 = 0. Case 2. c21# 0; let 013 + 0 A13 = 0 by shifting the first column of the minor to the second place of the minor, we alter only the sign, not the magnitude. m2 -C21 0 0 -C32 -C31 0 0 -C42 -c41 m4 0 0 = 0 0 -Ck2 -Ckl -Ck4 mk m4... mk(-m2 c31 - c21 C32) = 0 C31 = 0 C21 $ ~ c32 = 0 m2 m4... mk + 0 which makes the third row having off-diagonal elements all zero thereby giving a contradiction. Also c21 cannot be zero. C13 = 0. 15

Case 3. Now let clj + 0 for smallest j. Then Aij = 0. Now by shifting the first column to jth position ml 0 0 0 -clj -clj+i -Clk m2 0 0. -c21 0 0 -C32 m3 0.. -C31 0 0 -42 -C43 m4 0. -C41 0 0;-Cjo1,2 -1 -cj,2 * * * -Cj,1 O0 mj+1, o 0 0 mk Aij = mj+l... mkA' = 0 A' = 0 where A' is top left square of j-1 by j-1 At < m2 m3 m4... mjl(-j, 1) since A' = 0,. cj, = 0. A' is j-1 by j-1 matrix whose determinant is equal to the product of diagonals with off-diagonal terms non-positive. It is triangularable, and so from Lemma 1 has a row with off-diagonal elements zero. This implies in Figure 1 that there is a row with off-diagonal elements zero, which is contradictory. Hence, clj = O. So for j = 2,..., k Clj = 0 we have a triangular form. Hence, the theorem is proved. 16

III MODULE THEORY AND TRIANGULAR FORMS OF SUBM3DULES FOR NON-REDUNDANT NUMBER SYSTEMS Definitions of the module, submodule and quotient module are included. The reader is assumed to be familiar with the notions of groups, rings, group homomorphisms, fields and vector spaces. Definition 3. Module If R is a commutative ring with identity, a set of elements g with an operation addition satisfying the axioms (i) to (v) of an abelian group (i) x + y e (ii) x + (y+z) = y+y+z (iii) x + y = y + x for all x, y, z E (iv) 3o0 e, ax +o = x (v) 3 c E ~x+x' = o and closure and distributive laws with respect to the elements of ring R (vi) a x C E for all a E R; x E (vii) (a + b)x = ax + bx for all a, b e R; x c (viii) a(x + y) = ax + ay for all a E R; x, y C Then E is said to be a module over R. As an example, if e is an n-dimensional module over the ring of integers Z - IZez... ezi n terms and if x, y e Z, x, y are of the form 17

x = (xl, x2,..., Xn), Xi E Z Y = (Yi, Y2, *., Yn), Yi C Z then x + y = (xl + yl,..., Xn + Yn) E C ax = (axi, ax2,..., axn) e t for a e R Definition 4. Submodule If C is a subgroup of 5 and is closed under the multiplication by the elements of R, then C is a submodule of 5. That is x c C; a c R ax c C. Definition 5. Quotient Module If t is a module over R, and C is a submodule of i, then quotient group./C is a quotient module over R This is clearly so because if x + C Ce /C, a C R a(x + C) = ax + Ce S/C Note: The reader who is interested in other ideas applicable to number systems will be well advised to go through the algebraic parts of Refs. 2 and 5. Let ~ be an n-dimensional Z-module where Z is the ring of integers. Let el, e2,..., en be the set of generators of 5 where ei = (0, 0 O 0, 1, 0,..., O) ith place Every element of x e 5 is uniquely expressible as n x = xi ei xi C Z i=l Consider a set of cl, c2,..., ck, ci C S 18

and n Ci = > cij ej i = 1, 2,..., k j=l cl, c2,..., ck can be expressed as an n x n matrix C as below: nCl.. Cln C21. C2n C = Ckt Ckn Let C also denote the set of elements generated by the set (cl, c2,..., cn) such that k x cC x = ai Ci; ai E Z i=l C is the submodule commonly denoted by C = ~ C1, C2..., Ck >> We can also have a quotient module 5/C / ll * Cln Z Z... Z/ c21 * c2n C/kl ~ Ckn Theorem 3. If ~ is a Z-module of dim = n, and C a submodule of 5 with n generators, then S/C is a group of order equal to the absolute value of the determinant of C. A rigorous mathematical discussion will be found in Chapter 3 of Jacobson's Volume 2, so that it will be unnecessary to reproduce that part. How19

ever, an outline of the proof will be provided. If C and C' are two n x n matrices and an equivalence relation - defined C - C' > C1 = u C v where u and v are two non-singular matrices (non-singular matrices over integers have a determinant equal to ~1). The absolute values of two determinants will be the same if they are equivalent. It can be shown that for every matrix C there exists an equivalent diagonal matrix C' of the form i a2 C' = \- ~ an where ai divides ai+i determinant c = Ideterminant C'I = lal, a2,..., anl //C has the same abstract structure as the //C'. It can easily be seen that //C' is a group of lai, a2,..., an| elements, and so it is of order equal to the determinant C. So //C is a group of Ideterminant Ci number of elements. Thus, the theorem is proved. Let us define a mapping of $ on the set 5 onto ZM, the integers modulo M as below: i: e XZM such that $(ei) = Pi i = 1, 2,..., n 20

where (el, e2,..., en) are the set of generators for. Now if x = (xl, x2,..., xn) y = (Y1, Y2, *, Yn) with respect to the generator set (el, e2,..., en) n ~(x) = Pixi M i=l M ((x + y) = (xl + Yl, X2 + Y2, *.., Xn + Yn) n - j Pi(xi + yi) i =1 n n Aii M Mi =M - (x) + (y) So i is a group homomorphism of 5 onto ZM. Let C be a submodule of ~ with generators cl, c2,..., cn where ci = (-cil, -ci2, *.*, -cii-_, Mi,..,-Cin) i = 1, 2,..., n and C as a matrix representation will be ml -C12. -Cn -c21 m2. -C2n C =. -CnI -Cn2 m 21

The rows of C are the generators of C and n x e C X = ) ai i ai E Z i =1 C = < Cl, C2,... Cn >> Consider a non-redundant number system with moduli ml, m2,..., mn with digit weights pl, P2, *.., Pn to represent integers modulo M, where M = mi, m2,..., mn. In a non-redundant system the digit flows can be expressed by linear relations as below: ml d1 P + d13 P+ d2 p + dd Pn m2 P2 d21 P1 d23 + + d2n Pn (mod M) mn Pn dnl dn P + d n2 Pp + dn Pn-i + for some dij where mj > dij > O. Since cij may be any integer > 0, we may use as well cij instead of dij and we can write the n congruences above as m -C12 -Cln P1 -c21 m2 -c2n P - O(mod M) -Cnl -Cn2 mn Pn These equations are also the same as ~(ci) = 0 i = 1, 2,..., n 22

and Ci = (-cil, -ci2,..., mi,.., -cin) ith term i: C -+ 0. If kernel / = (x eC 3 0 (x) = 0) C Ci kernel Since': + ZM is a homomorphism, a/kernel 0 is isomorphic to ZM. (First theorem on homomorphism.) /kernel must be of order M. Since C Z kernel i //C must be of order > M. However, from Theorem 3, S/C is of order equal to the absolute value of the determinant C. From Theorem 1, we have determinant C < ml m2... mn = M.. /C must be of order M. C = kernel i. determinant C = M = ml m2... mn. From Theorem 2, we see that C is triangularable. By triangularising C and reordering the subscripts of the moduli, we can obtain a submodule C' of the form 23

mil 0 0 0 -c21 m2 0 0 -C31 -C32 m3 0 C = -cnl -Cn2 -Cn3 m2 Permuting rows of a matrix does not alter the submodule generated by the rows nor does a column permutation. However, the column matrix (P1, P2, -'', Pn) will have to be permuted to correspond to the moduli. So we have the condition. ml 0 0 0 P1 -c21 m2 0 0 P2 -C31 -C32 3 0 P3 - O(mod M). (~) -cnl -Cn2. L Pn O cij < mj Thus, we have a triangular form for the carry propagation matrix for non-redundant systems. Thus, we proved the following theorem. Theorem 4. If N is a non-redundant weighted system with moduli ml m2... mnn and corresponding digit weights p1, P2,... Pn, then there exists a reordering of the moduli (and corresponding weights) such that the condition (*) is satisfied. 24

VI. CONCLUSION In our attempt to understand the problems of number systems, we have been successful so far in giving the structure of a quotient module to them. We applied this result to the case of a non-redundant system N to prove that if N has a structure of a quotient module ~/C (1) C must be triangular or triangularable (2) and if (: - + ZM such that n (x1, X2,... xn) = Pi i i=l1 C is also the kernel of y. This result is interesting, and using this we can obtain the set of conditions on the digit weights, and also investigate the other non-redundant number systems that may have advantages in arithmetic logic. The arithmetic process in redundant systems can be divided into two parts: (1) carry assimilation (2) reduction to canonical form. This can be explained by the submodule C of the redundant system, which will comprise generators for carry assimilation and those for canonical reduction. This is the area that may be successfully investigated using the theory discussed in this report. 25

REFERENCES 1. Garner, H. L., "The Residue Number System," IRE Transactions on Computers, Vol. EC-8, No. 2, pp. 140-147, June 1959. 2. Arnold, R. F., "Linear Number Systems," Information Systems Lab., The Univ. of Mich., Tech. Note 04879-8-T, Oct. 1962. 3. Rozenberg, D. P., "The Algebraic Properties of the Residue Number Systems," IBM No. 61-907-176. 4. Garner, H. L., "Finite Non-Redundant Number System Weights," Information Systems Lab., The Univ. of Mich., Tech. Note 04879-2-T, May 1962. 5. Jacobson, N., Lectures in Abstract Algebra, Vol. 2, Ch. 2-3, Van Nostrand Co., Inc. 6. Rao, T.R.N., "Computer Number Systems: Linear and Non-Linear Categories," Information Systems Lab., The Univ. of Mich., Tech. Note 04879-6-T, Sept. 1962. 26

UNIVERSITY OF MICHIGAN