EUROPEAN JOURNAL OF PURE AND APPLIED MATHEMATICS Vol. 16, No. 2, 2023, 784-790 ISSN 1307-5543 – ejpam.com Published by New York Business Global The Discrete Lyapunov Equation of The Orthogonal Matrix in Semiring Gregoria Ariyanti1,∗, Ana Easti Rahayu Maya Sari1 1 Mathematics Education Study Program, Widya Mandala Surabaya Catholic University, Indonesia Abstract. Semiring is an algebraic structure of (S,+,×). Similar to a ring, but without the condition that each element must have an inverse to the adding operation. The forms (S,+) and (S,×) are semigroups that satisfy the distributive law of multiplication and addition. In matrix theory, there is a term known as the Kronecker product. This operation transforms two matrices into a larger matrix containing all possible products of the entries in the two matrices. This Kronecker product has several properties often used to solve the complex problems of linear algebra and its applications. The Kronecker product is related to the Lyapunov equation of a linear system. Based on previous research in the Lyapunov equation in conventional linear algebra, this paper will describe the characteristics of the Lyapunov equation in a semiring linear system in terms of the Kronecker product. 2020 Mathematics Subject Classifications: 00A64, 34D08, 37M25, 43A46 Key Words and Phrases: Linear system, the Lyapunov equation, semiring, the Kronecker product 1. Introduction A non-empty set G with a binary operation ∗ is known as Group if it has the following properties: associative, a zero element of binary operations ∗, and every element, not a zero element, has an inverse. Meanwhile, a non-empty set R with two binary operations, particularly ∗ and ◦ is called Ring. If it has the following properties: (R, ∗) is a commu- tative group, (R, ◦) is closed, (R, ◦) is associative, and distributive. If the Ring has the following properties: commutative to binary operation ◦, it has a unit element of binary operation ◦, and every element, not a zero element, has an inverse to binary operation ◦, it is called Field. Different algebraic systems will appear if Group and Ring conditions are weakened, particularly Semigrup and Semiring. If a few Group or Ring characteristics are removed, the algebraic structure formed is Semigrup, after which Semiring. One of ∗Corresponding author. DOI: https://doi.org/10.29020/nybg.ejpam.v16i2.4712 Email addresses: gregoria.ariyanti@ukwms.ac.id (G. Ariyanti), ana.easti.rahayu@ukwms.ac.id (A.E.R.M. Sari) https://www.ejpam.com 784 © 2023 EJPAM All rights reserved. G. Ariyanti, A.E.R.M. Sari / Eur. J. Pure Appl. Math, 16 (2) (2023), 784-790 785 the problems and applications often encountered in mathematics is completing the Linear Equations System. The Kronecker product is a binary matrix operator that maps two arbitrarily dimen- sioned matrices into a larger matrix with a particular block structure ([14]). The Kronecker product discussed by Zhou et al. (1996) and Whitcomb (2020) applies to matrices whose elements are real numbers ([4],[11]). The set of real numbers is a field. The linear equations system that researchers have developed is a system of linear equa- tions over Field, which include real numbers R or complex numbers C ([12],[4]). In other studies, the research object is extended not to Field anymore but to commutative Ring and linear equations system Commutative over ring have been discussed by Brown ([4]). Likewise, assuming an extension from the Ring to Ring commutative does not generally change the definition. This paper presents the characteristics of the discrete Lyapunov equation of a matrix. The scope of the topic is a system of linear equations in semiring in terms of the Kronecker product. First, section 2 will review some basic facts about the semiring, the Kronecker product of the matrix in semiring, and the Lyapunov equation of the matrix in semiring. Then, in Section 3, we show a necessary or sufficient condition of the Lyapunov equation in a linear system over semiring in terms of the Kronecker product. 2. Materials and literature review 2.1. Semiring and Matrices in Semiring Definition 1. Semigroup S is an empty set equipped with an associative binary ∗ opera- tion, x ∗ (y ∗ z) = (x ∗ y) ∗ z for every x, y, z ∈ S. Poplin defines a semiring and its properties as follows([2],[13],[12],[11]). Definition 2. Semiring is a non-empty set S with two binary operations, addition (+) and multiplication (×), which have the following properties: commutative and associative properties of +, associative property of ×, distributive property of × to +, the set S has a zero element 0 ∈ S so that 0 + a = a + 0 = a and 0 × a = a × 0 = 0 for every a ∈ S. This zero element is called the absorbent element (absorption), and the set S has a unit element e, e× a = a× e = a for every a ∈ S. The commutative and idempotent characteristics in Group and Ring also apply in Semiring ([13]). Let Mn×1(S) be the set of all vectors n× 1 with the elements of Semiring S. And, let Mn×n(S) be the set of all n × n matrices with the elements of semiring S ([4],[1]). The + and × operation for matrices over Semiring is defined as in Definition 3. Definition 3. Let S Semiring, a positive integer n, and Mn(S) is the set of all n × n matrices over S. For every A,B ∈ Mn(S), + and × operations over Semiring S are defined C = A+B as cij = aij + bij and C = A×B as cij = ∑ l ail × blj. G. Ariyanti, A.E.R.M. Sari / Eur. J. Pure Appl. Math, 16 (2) (2023), 784-790 786 The Semiring S has 0 as a zero element and 1 as an identity element, as in the matrix of conventional algebra. We can form a zero matrix and an identity matrix based on the zero element and the identity element ([2]). The zero matrix n× n over Semiring S is 0n and is defined as a matrix with all elements equal to the 0−element, that is (0n)ij = 0. The identity matrix n × n over S is defined as the matrix with all elements equal to the e−element, that is, [In]ij = { e, if i = j 0, if i ̸= j . In Semiring, the element of Semiring has an inverse operation on + to determine a matrix determinant in Semiring S. A permutation characterizes a determinant of a matrix over a Semiring S. 2.2. Kronecker Product Kronecker’s product is related to the stack operator. The stack operator maps an n×m matrix to an nm× 1 vector ([14]). The stack of the n×m matrix A is represented by vec(A), a vector formed by stacking the columns of A on the vector nm× 1. Example 1. Let A is a matrix with A = [ a b c d ] , then its stack form is vec(A) =  a b c d  . If C is an n×m matrix comprising m column vectors c1, c2, c3, ..., cm, where each ci is an n× 1 vector C = [c1, c2, c3, ..., cm]n×m, then vec(C) =  c1 c2 ... cm  nm×1 . Let X ∈ Mm×n(S), the form vec(X) denote the vector formed by stacking the columns of X into one long vector: vec(X) = [ x11 x21 . . . xm1 x12 x22 . . . x1n x2n . . . xmn ]T . Kronecker product is an operation on two matrices that do not require size ([8], [9]). The notation ⊗ denotes Kronecker products. With S semiring, let A ∈ Mm×n(S) and B ∈ Mp×q(S), then the Kronecker product of A and B is defined as A⊗B :=  a11B . . . a1nB ... . . . ... am1B . . . amnB  ∈ Mmp×nq(S). G. Ariyanti, A.E.R.M. Sari / Eur. J. Pure Appl. Math, 16 (2) (2023), 784-790 787 Furthermore, if A and B are square matrices with A ∈ Mn×n(S) and B ∈ Mm×m(S) then the Kronecker sum of A and B is defined as A⊕B := (A⊗ Im + In ⊗B) ∈ Mnm×nm(S). Properties of Kronecker product is given the following theorem ([8], [14]). Theorem 1. For A ∈ Mm×n(S) and B ∈ Mp×q(S) with S semiring, we have the following properties: the Kronecker product is associative, not in general commutative, that is, (A⊗ B) ̸= (B⊗A), and transpose distributes over the Kronecker product (do not reverse order) (A⊗B)T = AT ⊗BT . Let A ∈ Mn×n(S) and B ∈ Mm×m(S), and λi with i = 1, 2, ..., n be the eigenvalues of A and µi with i = 1, 2, ...,m be the eigenvalues of B. Then we have the following properties: the eigenvalues of A ⊗ B are the mn numbers λiµj , and the eigenvalues of A⊕B = (A⊗Im)+(In⊗B) are the mn numbers λi+µj , with i = 1, 2, ..., n, j = 1, 2, ...,m. 2.3. Discrete Lyapunov equation The linear system is closely related to stability, which can be observed using the eigen- value criterion of matrix A. Furthermore, the stability of the linear system is closely related to the existence of a solution to the Lyapunov equation ([6]). Therefore, this method can determine the system’s stability without knowing the system’s solution. Lya- punov’s equation for a linear system over a field was given by Zhou ([7]). In this study, the Lyapunov equation is defined for a discrete linear system on a semiring, adopting the meaning of the Lyapunov equation for a linear system on a plane. The discrete Lyapunov equation for the linear system over semiring is defined as follows ([10], [5]). Definition 4. Given a matrix A,X,Q ∈ Mn(S). The Lyapunov equation for a linear system over a semiring is defined as AXAT −X +Q = 0. For linear systems over the field, the existence of solutions to the Lyapunov equations is associated with asymptotic stability. The system is asymptotically stable if a solution to the Lyapunov equation exists. On the other hand, if the system is asymptotically stable, a solution to the Lyapunov equation exists. ([6]). 3. Results and discussion The problem of discrete Lyapunov equations over semirings is limited to orthogonal matrices. These are because of the limited nature of the semiring. Theorem 2. Let S is semiring. Then for any matrices A ∈ Mk×m(S), B ∈ Mn×l(S), and X ∈ Mm×n(S), we have vec(AXB) = (BT ⊗A)vec(X). G. Ariyanti, A.E.R.M. Sari / Eur. J. Pure Appl. Math, 16 (2) (2023), 784-790 788 Proof. We have (AXB).k = ∑ j bjkAX.j = ( b1kA b2kA . . . bnkA ) and X.1 X.2 ... X.n  = [ BT .k ⊗A ] vec(X) = [ (BT )Tk. ⊗A ] vec(X). Furthermore, we conclude vec(AXB) = [BT ⊗ A]vec(X) since the transpose of the kth column of B is the kth row of BT . In the following, another property of the Kronecker product for matrix over a semiring is given. Theorem 3. Let A ∈ Mm×m(S), B ∈ Mn×n(S), and X ∈ Mm×n(S), we have vec(AX + XB) = (BT ⊕A)vec(X). Proof. From the definition of Kronecker sum, we have (BT ⊕A)vec(X) = (BT ⊗ Im + In ⊗A)vec(X) = (BT ⊗ Im)vec(X) + (In ⊗A)vec(X). According to Theorem 2, we have (BT ⊕A)vec(X) = vec(ImXB) + vec(AXITn ) = vec(XB) + vec(AX). Example 2. As is well known, the max-plus algebra Rϵ is semiring. Let A, B, and X matrices over max-plus algebra, with A = [ 3 ϵ 1 ] , B = [ 5 0 ] , and X =  2 5 1 2 ϵ −3 . Based on binary operations on max-plus algebra, as given in Ariyanti ([3]), we have AXB = [ 3 ϵ 1 ]  2 5 1 2 ϵ −3 [ 5 0 ] = [ 3 ϵ 1 ]  7 6 −3  = [ 10 ] Because AXB = [ 10 ] , we get vec(AXB) = [ 10 ] . Next, we have (BT ⊗A)vec(X) = ([ 5 0 ] ⊗ [ 3 ϵ 1 ]) [ 2 5 1 2 ϵ −3 ]T = [ 8 ϵ 6 3 ϵ 1 ] [ 2 5 1 2 ϵ −3 ]T = [ 10 ] REFERENCES 789 Due to the limitations of semirings, the existence of discrete solutions to the Lyapunov equations on semirings depends on the orthogonal matrix. This statement is given in the following theorem. Theorem 4. Let discrete Lyapunov equation over semiring AXAT − X + Q = 0 with A ∈ Mn×n(S), Q ∈ Mn×n(S). For A is orthogonal matrice, there is a unique solution X ∈ Mn×n(S) if and only if λi(A) + λj(−A) ̸= 0. Proof. A matrice A is orthogonal if AT = A−1; hence we have AXAT − X + Q = 0 and then (AXAT )A−XA = −QA. Because A is orthogonal, we have AX −XA = −QA. Therefore, AX+X(−A) = Q(−A) and vec(AX+X(−A)) = ((−A)T ⊕A)vec(X). Finally, we have ((−A)T ⊕A)vec(X) = vec(−QA). Based on conditions, we have a unique solution if and only if (−A)T ⊕A non-singular. 4. Conclusion We show that the solutions of the discrete Lyapunov equations for matrices over semir- ings are also valid. The linear system that has been developed is the semiring linear system. Due to its semiring nature, not all elements have inverses. It is necessary to have a par- ticular case, namely by reviewing the Lyapunov equation of the system. In addition, it is required to relate it to the kroner product as given in Theorem 3 and Theorem 4. Fur- thermore, this condition can be used to find other characteristics of a linear system over a semiring. Acknowledgements We gratefully thank the Directorate of Research and Community Service, Deputy for Research and Development Strengthening, The Ministry of Education, Culture, Research, and Technology, Indonesia. References [1] H Anton and C Rorres. Elementary Linear Algebra: Applications Version, 11th edition. John Willey and Sons, The United States of America, 2013. [2] G Ariyanti. A Note of The Linear Equation AX=B with Multiplicatively-Reguler Matrix A in Semiring. International Conference on Applied & Industrial Mathematics and Statistics (ICoAIMS), Journal of Physics: Conference Series, 2019. [3] G Ariyanti. A Note on The Solution of The Characteristic Equation over The Sym- metrized Max-Plus Algebra. BAREKENG: Journal of Mathematics and Its Applica- tion., 16:1347–1354, 2022. [4] WC Brown. Matrices over Commutative Rings. New York : Marcel Dekker, Inc., 1993. REFERENCES 790 [5] AS Hodel and B Tenison. Linear Algebra and Its Applications. Elsevier Science Inc., 1996. [6] A Ibrahim, SI Bala, I Ahmed, MJ Ibrahim, and F Jarad. Numerical construction of lyapunov functions using homotopy continuation method. Advances in the Theory of Nonlinear Analysis and its Applications, 6(3):354–363, 2022. [7] K Glover K Zhou, JC Doyle. Robust and Optimal Control. Prentice Hall, New York, 1996. [8] S Kathrin. On the Kronecker Product. PhD thesis, University of London, 2013. [9] CFV Loan. The ubiquitous kronecker product. Journal of Computational and Applied Mathematics, 123:85–100, 2000. [10] S Massei, D Palitta, and Robol. Solving rank structured sylvester and lyapunov equations. SIAM Journal on Matrix Analysis and Applications, 39(4), 2018. [11] W Mora, A Wasanawichit, and Y Kemprasit. Invertible matrices over idempotent semirings. Chamcuri Journal of Mathematics, 1(2):55–61, 2009. [12] P Narendran. Solving Linear Equations Over Polynomial Semirings. ”11 th Anual IEEE Symposium on Logic in Computer Science”, IEEE Computer Society Press, Los Alamitos, CA, pages 466–472, 1996. [13] PL Poplin. The Semiring of Multisets. PhD thesis, Faculty of North Caroline State University, 2000. [14] LL Whitcomb. Notes on Kronecker Products. Johns Hopkins University, 2020.