=Paper=
{{Paper
|id=Vol-1454/ramics15-st_61-69
|storemode=property
|title=A Generic Matrix Manipulator
|pdfUrl=https://ceur-ws.org/Vol-1454/ramics15-st_61-69.pdf
|volume=Vol-1454
}}
==A Generic Matrix Manipulator==
https://ceur-ws.org/Vol-1454/ramics15-st_61-69.pdf
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).