A Generic Matrix Manipulator Dylan Killingbeck Department of Computer Science, Brock University, St. Catharines, Ontario, Canada, L2S 3A1 dk10qt@brocku.ca Abstract. In this paper we describe a generic matrix manipulator system that performs operations on matrices in a flexible way using a graphical user interface. A user defines allowable data entries called a basis, as well as n-ary operations defined on basis elements. These operations can be used in multiple ways to define operations on matrices. A basis and n- ary operations can be entered into the system by various ways including predefined, Java datatypes, JavaScript, and various XML formats defining certain mathematical structures. Keywords: Allegory, Matrix Manipulation, Semiring, Sup-Semiring 1 Introduction It is well known that matrices can be used in several key areas of science to provide meaning to data. Often these matrices can be manipulated to provide a solution, based upon the data that they hold and the operations defined be- tween the coefficients. Relations can be represented as graphs, or more specifi- cally as a matrices that defines the relationships between nodes and vertices [7, p. 6]. Using this method of representation an observer can verify a qualitative relationship between elements associated within the relation, and then preform further study using relation algebraic definitions and constructions. For exam- ple matrices can be used to represent a relation given as a graph and determine if a Hamiltonian cycle exists. Matrices in generalized linear algebra can also be used to represent quantitative information, and similarly this can provide further information about the meaning of the data. To provide an example, a matrix can represent an interconnected network by which the probability for success of a message traveling between two nodes is represented by a value on the unit interval. Between the matrix representations of qualitative and quantitative informa- tion, it is complex to find meaning, and as such a generic system with user specified parameters is required to further study their behavior. A generic sys- tem that is able to flexibly manipulate matrices by user defined operations lifted from the coefficients to matrices, with the inclusion of a user defined data sets (or basis) will allow for an observer to reason between matrices more eas- ily. This generic system will perform similar to the RelView system (see [1]) 62 D. Killingbeck through a graphical user interface, however it will expand further upon matrix operations, and representations. Primarily, this generic system will focus on au- tomatically inferencing types of operations, and checking the results to ensure compatibility, expanding on RelViews limitations. The remainder of this paper will discuss the mathematical preliminaries, and finally the implementation of this generic matrix manipulator system in detail. 2 Mathematical Preliminary This section will define the basic definitions of concepts and properties associ- ated with the quantitative and qualitative aspect of matrices. We will start with the quantitative aspect by introducing semirings as a very general approach to linear algebra. 2.1 Semirings We want to provide a structure that capture the quantitative and qualitative in- formation as discussed in the introduction. We summarize the theory presented in [5] and start with the definition of a semiring. Definition 1. xR,+,,0R ,1R y denotes a semiring if: 1. R is a commutative monoid, i.e. we have: (a) x+0R =x for all xPR , (Identity) (b) x+(y+z)=(x+y)+z for all x,y,zPR , (Associativity) (c) x+y=y+x for all x,yPR , (Commutativity) 2. R is a monoid i.e., we have: (a) x1R = 1R x = x for all xPR , (Identity) (b) x(yz)=(xy)z for all x,y,zPR , (Associativity) 3. Multiplication will distribute over addition, from both the left and the right: (a) x(y+z) = xy+xz , (Left Distributivity) (b) (x+y)z = xz+yz , (Right Distributivity) 4. 0R is the annihilator for multiplication over R, meaning: (a) 0R x=0R =0R x for all xPR , (Annihilator Law) A commutative semiring is a semiring where the monoid xR, , 1R y is commu- tative. An additively idempotent semiring is a semiring so that x x  x for all x P R, similarily a multiplicatively idempotent semiring is semiring so that x  x  x2  x for all x P R. We will denote the set of multiplicative idempotent elements of a semiring R by I pRq. Semirings are widely used in theoretical computer science, for example in parsing formal languages [3], or if a semiring is commutative and idempotent (multiplicatively) then it forms a lower semilattice with respect to multiplica- tion. A generalization of this property is stated in the first theorem below [5]. Theorem 1. Let xR, , , 0, 1y be a commutative semiring. Then xI pRq, , 0, 1y is a lower semilattice with least element 0 and greatest element 1. A Generic Matrix Manipulator 63 2.2 Allegory An allegory is the generalization of the category of binary relations between two sets. A morphism R from source A and target B is denoted as R : A Ñ B, from category R, with all the possible morphisms denoted as RrA, B s [2]. Composition is denoted by ;, for example R; S, which reads first R and then S. IA denotes the identity morphism for an object A. Definition 2. A category R is an allegory if: 1. The class of morphisms RrA, B s form a lower semilattice, with meet denoted by [ and the induced ordering by „. Elements within this class are called relations. 2. For all relations Q, there is a converse such that R:AÑB and S:BÑC the following holds: pQ; S q! = S ! ; Q! , and pQ! q! = Q. 3. For all relations Q: AÑB, R, S:BÑC, then Q;(R[S) „ Q;R[Q;S. 4. For all relations Q:AÑB, R:BÑC and S:AÑC, the modular law Q;R [ S „ Q;(R [ Q! ;S) holds. Finally RrA, B s is a distributive allegory if RrA, B s is a distributive lattice with join \ and least element KKAB , satisfying the additional properties: 5. Q; KKBC KKAC for all relations Q : A Ñ B, 6. Q; pR \ S q  Q; R \ Q; S for all relations Q : A Ñ B, R, S : B Ñ C. Rel, the category of binary relations between sets as well as the category L-Rel of L-valued relations between sets form a distributive allegory. 2.3 Matrices over Semirings Matrices of size m  n will form over a semiring of equal size, induced by addi- tion, denoted by , for example if R is a semiring denoted by xR, , , 0R , 1R y and M is an m  n matrix, then M  raij smn where coefficients aij are elements from R. Regular matrix addition and multiplication is respectively defined by: [aij smn +[bij smn = [aij +bij smn , and [aij smn  rbjk snp = r ° a b s n ij jk mp  j 1 Similarly we can define the transpose of a matrix, and the Hadamard product of two equal sized matrices, respectively defined by: raij s! mn = raji smn , and raij smn  rbij smn = raij  bij smn 0R is defined as the zero matrix r0smn , and 1R is defined at r1smn . M r0smn  M , and M  r0smn  r0smn . Additionally as + is commutative then M M 1  M 1 M , and as + is associative M pM 1 +M 2 ) = (M M 1 q M 2 . A matrix that consists of only multiplicatively idempotent elements as coefficients is idempo- tent with respect to the Hadamard product. It is a well-known fact that matrices over a lower semilattice form an alle- gory which leads to the following theorem. Theorem 2. Consider the category of matrices with coefficients from a commutative semiring. Then the subcategory of idempotent matrices with respect to the Hadamard product forms an allegory. 64 D. Killingbeck 2.4 Sup-Semiring Recall idempotent elements from a semiring form a lower-semilattice, alterna- tives matrices with idempotent coefficients form an allegory. We will use these concepts to formulate a new structure, to derive a distributive lattice, and a distributive allegory. Definition 3. xD, , , \, 0D , 1D y denotes a sup-semiring if: 1. xD, , , 0D , 1D y is a commutative semiring. 2. xD, \y is a commutative semigroup, then (a) x \ py \ z q  px \ y q \ z for all x,y,zPD, (Associativity) (b) x \ y  y \ x for all x,yPD, (Commutativity) 3. px \ y q  px \ y q  x \ y for all x,yPD, (Relative Idempotency) 4. x  px \ y q  x for all x,yPD, (Absorption) 5. if x2  x, then x \ px  y q  x for all x,yPD, (Relative Absorption) 6. if x2  x, y 2  y and z 2  z, then x  py \ z q  x  y \ x  z for all x,y,zPD. (Relative Distributivity) In the case of a sup-semiring we are able to strengthen Theorem 1: Theorem 3. Let xD, , , \, 0, 1y be a sup-semiring. Then the structure xI pDq, , \, 0, 1y is a distributive lattice. Similarly, in the case of a sup-semiring, we are able to strengthen Theorem 2 as follows. Theorem 4. Consider the category of matrices with coefficients from a sup-semiring. Then the subcategory of idempotent matrices with respect to the Hadamard product forms a distributive allegory. 3 Brief Description of the System As already mentioned in the introduction, a generic matrix manipulator system will be required to carry out various operations and provide meaning to these combined structures. This section will outline the various features, implemen- tations and user interactions provided by the system. The matrix manipulator system is constructed using the Java environment as it offers flexibility to the developer, which can be passed on to the user. This system has previously been started by Milene Santos Teixeira as a project [6]. During this project the basic matrix operations such as matrix multiplication, addition etc have been im- plemented as methods that use operations on the coefficients of the matrix as parameters. The coefficients and their operations are loaded from user-defined files in XML format. Currently the system is further developed by the author as part of his MSc. thesis. A Generic Matrix Manipulator 65 3.1 User Input The heart of the system relies on input provided by a user. A user must supply information about two components of the system. The first, a basis to outline co- efficients (elements), as well as operations between these coefficients. Secondly, operations between matrices must also be defined. Once these components are defined, a user can supply commands to the system to manipulate matrices. The manipulation possibilities includes: 1. Performing operations on coefficients (elements) within a matrix 2. Performing operations between matrices 3. Storing results, recalling results through executing equations. Essentially a user will use the graphical user interface to facilitate the input of the basis component and any desirable operations. Once information has been loaded into the system, the user is free to manip- ulate the constructed environment within the system as desired, through the graphical user interface, as well as inputting commands through an input field. This input field will accept only valid input based on stored matrices (vari- ables), and the user defined operations between matrices. In order to facilitate such input a flexible parser must be constructed at runtime to parse user in- put, based on the environment. JParsec, an implementation of Haskell Parsec, is used as it is a two stage parser that provides the flexibility required to parse user input at runtime, given operators with specified operator priority [8]. 3.2 User Defined Matrix Matrices represented in this generic system can be of various forms to provide flexibility. A user may specify the values of the coefficients that correspond specifically to the source (row) and the target (column) values. To be even more general, a matrix can consists of only 1 object type A, and having morphisms that such that F is a morphism, then F : A Ñ A. This type of matrix is con- venient to represent Boolean matrices, matrices with real coefficients, or even matrices with integer coefficients. To be more specific, matrices within the sys- tem can also represent homogeneous relations, or heterogeneous relations. To provide an example, the following figure below demonstrates a relation with sources along the rows, and targets along the columns. A B A A M A 1 3 2 1 B 2 4 3 1 Fig. 1. Typical matrix with sources A and B and targets A,B,A and A Source and target objects, along with their morphisms must produce a result that is defined and allowable in the system, which is enforced by the user de- fined basis. 66 D. Killingbeck 3.3 User Defined Basis As previously outlined, a user defines a basis which specifies the allowable en- vironment values and n-ary operations between the elements (coefficients). For example, if the basis is defined as the set N, then possible operations could be addition, multiplication, etc. as defined for natural number. Operations defined within the basis must be closed on the given environment. In other words, the operations must accept arbitrary values from then environment as arguments and must return a value within the environment as a result. To make the system as generic as possible, these operations can be loaded into the system through various ways: 1. Java datatypes, i.e., int, double, boolean... 2. XML formats, i.e., lattice structures, graphs... Below is a typical explicit example, whereby the user defined basis is supplied by .xml files. The first .xml file defines the allowable objects, and data types for the various source and target morphisms (integer in this case): A,B 1,2 1,2,3 1,2,3,4,5 Above we can see that this basis is defined for only A and B objects, and is explicitly defined. Morphism maps are defined for each source and target object as per above, that is to say with a source A and a target A, the resulting value can only be an integer, with a value of 1 or 2. Since this explicit morphism is defined as symmetric, a source A and a target B is the same as a source B and a target A. In addition to the user supplied basis .xml file, the user must provide op- eration for the matrix coefficients, as mentioned above. A typical user defined operation in .xml format is supplied below: (A,A),(B,B) A Generic Matrix Manipulator 67 (1,2),(2,1) (1,2),(2,1),(3,3) (1,2),(2,4),(3,2),(4,5),(5,1) Above we can see that the operation is a unary operator, with a name, code, notation type and corresponding basis. The notation maps the first value of the tuple, to the given second value in the tuple. For example, if the source is A and the target is A and the value is 1, the resulting value of the operation is 2. To make the system more convenient, various mathematical structures can be automatically generated by the user. For example, if the user provides a Hasse diagram, then it can be used to generate the corresponding matrix repre- sentation, and basis. 3.4 User Defined Operations Recall, a user is able to specify operations between matrices. These operations have an arbitrary number of parameters, hence the operations can theoretically be n-ary operators, keeping the concept of being generic. These operations be- tween matrices are comprised of the operations defined within the basis. Fur- thermore, there are two ways that these n-ary operators can be evaluated on matrice. First, operations can be evaluated component wise as defined above, for example matrix addition defined for elements in M p2, Rq (the set of all 2  2 matrices with real coefficients), or more specifically the Hadamard product is component wise multiplication. Secondly, operations between two matrices can be defined similar to regular matrix multiplication, as defined above. This type of operation requires two binary operations, the first to provide a result be- tween two coefficients, and the second combines the results of the first opera- tion. An example of this can be observed through regular matrix multiplication in M p2, Rq, where regular multiplication is the first operation, and the second operation is addition. Operations between matrices must rely on the underlying operations de- fined in the basis. This is to ensure that the operations between matrices pro- duce results containing elements defined by the basis. For example, using reg- ular addition defined for matrices with real coefficients, implies that the addi- tion between coefficients is also defined within the basis. These operations can therefore be described as higher order functions, or functions built by using previously defined functions. 68 D. Killingbeck Similar to a user defined basis, a user may define these operations between matrices through various methods to increase convenience and usability. A user can define an operation by several methods including: 1. XML formats, i.e. explicitly defined. 2. JavaScript, i.e., user defined functions parsed from JavaScript. 3. Java built-in operations, i.e. addition, multiplication, min, max... 4. Special mathematical structures such as lattices, additive cyclic groups Zn modulo an integer n, or multiplicative monoids/groups Zn modulo an in- teger n. A user defined operation between matrices must require a symbol to represent the operation for user command input, this symbol is required as part of the operation definition. To further enhance the flexibility of the system, operations can either be in prefix, infix or postfix format. Finally, operations defined by this system do not require special properties such as associativity or commutativity. The system is more general then re- quired to investigate matrices over semirings or sup-semirings, and in fact any arbitrary matrices can be used, with corresponding user provided operations. 3.5 Graphical User Interface Another important component of the matrix manipulator system is the graphi- cal user interface (GUI). The GUI allows the user to have a visual representation of the data set they are working with, and also input commands into the sys- tem. Overall, the matrix manipulator system will have a comparable interface molded after the RelView system [1]. The GUI is written using Java Swing com- ponents to provide a familiar interface, rich component listing as well as reduce developer complexity. The user is able to modify the working space to modify the representations of matrices, for example they can modify the font, size and spacing of coefficients within the matrix. The GUI will provide feedback to the user in the form of a visual display, and also provide feedback be denoting working conditions such as the operations defined, or basis loaded. 4 Conclusion In order to investigate and simplify matrix manipulation, the creation of a for- mal system is required. This paper has outlined the requirements, and other- wise desirable features as needed to facilitate such a system. The more flexible the generic matrix manipulator system is, the more use it will be to those re- quiring such a tool to investigate structures. In closing, the system is currently in development as part of the author’s MSc. thesis. References 1. Berghammer R.: Relview System. http://www.informatik.uni-kiel.de/ progsys/relview/: Christian-Albrechts-University of Kiel (2012). A Generic Matrix Manipulator 69 2. Freyd P., Scedrov A.: Categories, Allegories. North-Holland (1990). 3. Goodman J.: Semiring Parsing. Computational Linguistics, 25(4), 573-605 (1999). 4. Hebisch U., & Weinert H.: Semirings. World Scientific (1998). 5. Killingbeck D., Santos Teixeira M., Winter M.: Relations among Matrices over a Semir- ing. In Kahl W., Oliveira J.N., Winter M. (Eds.): Relational and Algebraic Methods in Computer Science (RAMiCS 15), LNCS 9348, 96-113 (2015). 6. Santos Teixeira M.: A Generic Matrix Manipulator. Undergraduate Project (COSC 3P99), Brock University (2014). 7. Schmidt G., Ströhlein T.: Relations And Graphs. Springer (1993). 8. Yu B.: JParsec. https://github.com/jparsec/jparsec/: GitHub (2014).