APPROXIMATE MATRICES OF SYSTEMS OF MAX-MIN FUZZY RELATIONAL EQUATIONS

A PREPRINT Ismaïl Baaj LEMMA, Paris-Panthéon-Assas University, Paris, 75006, France ismail.baaj@assas-universite.fr

April 23, 2025

ABSTRACT

In this article, we address the inconsistency of a system of max-min fuzzy relational equations by minimally modifying the matrix governing the system in order to achieve consistency. Our method yields consistent systems that approximate the original inconsistent system in the following sense: the right-hand side vector of each consistent system is that of the inconsistent system, and the coefficients of the matrix governing each consistent system are obtained by modifying, exactly and minimally, the entries of the original matrix that must be corrected to achieve consistency, while leaving all other entries unchanged.

To obtain a consistent system that closely approximates the considered inconsistent system, we study the distance (in terms of a norm among \(L_{1}\), \(L_{2}\) or \(L_{\infty}\)) between the matrix of the inconsistent system and the set formed by the matrices of consistent systems that use the same right-hand side vector as the inconsistent system. We show that our method allows us to directly compute matrices of consistent systems that use the same right-hand side vector as the inconsistent system whose distance in terms of \(L_{\infty}\) norm to the matrix of the inconsistent system is minimal (the computational costs are higher when using \(L_{1}\) norm or \(L_{2}\) norm). We also give an explicit analytical formula for computing this minimal \(L_{\infty}\) distance. Finally, we translate our results for systems of min-max fuzzy relational equations and present some potential applications.

Keywords Fuzzy set theory, Systems of fuzzy relational equations

1 Introduction

Systems of fuzzy relational equations are the basis of many fuzzy modeling approaches [15, 16, 25], including Zadeh’s possibility theory for approximate reasoning [35], and have been applied in some practical areas of Artificial Intelligence (AI), such as medical diagnosis [1, 7, 30]. The pioneering work of Sanchez [29, 30] provided necessary and sufficient conditions for a system of max-min fuzzy relational equations to be consistent, i.e., when the system has solutions. Sanchez showed that, when a max-min system is consistent, the structure of its solutions set is given by a solution which is the greatest and a finite number of minimal solutions. His work has been extended to systems based on \(\mathrm{max}-T\) compositions where T is a continuous t-norm [11, 13, 14, 19, 21, 23, 24, 31], systems based on \(\mathrm{max}-*\) compositions, where ∗ is an increasing and continuous function [22], and systems based on \(\operatorname*{min}-\mathcal{T}_{T}\) compositions, where \(\mathcal{I}_{T}\) is the residual implicator associated with a continuous t-norm T , see [6, 27].

However, addressing the inconsistency of systems of fuzzy relational equations remains an open problem today[11, 17, 26]. For max-min systems, researchers have worked on finding approximate solutions [9, 10, 20, 18], and on the computation of approximate inverses of fuzzy matrices [33, 34]. An emerging development is based on Pedrycz’s approach [26]: Perdycz proposed to slightly modify the right-hand side vector of an inconsistent max-min system in order to obtain a consistent system. Then, the solutions of the obtained consistent system are considered as approximate solutions of the inconsistent system. Some authors proposed algorithms [9, 10, 20] based on Pedrycz’s approach for obtaining a consistent system close to a given inconsistent system. More recently, the author of [4, 5] studied the

Approximate matrices of systems of max-min fuzzy relational equations A PREPRINT

inconsistency of systems of \(\mathrm{max}\!-\!T\) fuzzy relational equations, where T is a continuous t-norm among minimum, product, or Lukasiewicz’s t-norm. For each of the three \(\mathrm{max}-T\) systems, the author of [4, 5] provided an explicit analytical formula to compute the Chebyshev distance (defined by L-infinity norm) between the right-hand side vector of an inconsistent system and the set of right-hand side vectors of consistent systems defined with the same composition and the same matrix as the inconsistent system. Based on these results, the author of [4, 5] studied the Chebyshev approximations of the right-hand side vector of a given inconsistent system of \(\mathrm{max}\!-\!T\) fuzzy relational equations[10, 20], where each of these approximations is the right-hand side vector of a consistent system defined with the same matrix as the inconsistent system and such that its distance to the right-hand side vector of the inconsistent system is equal to the computed Chebyshev distance. For each of the three \(\mathrm{max}\!-\!T\) systems, the author of [4, 5] showed that the greatest Chebyshev approximation of the right-hand side vector of an inconsistent \(\mathrm{max}-T\) system can be computed by an explicit analytical formula. Furthermore, for max-min systems, the author of [5] provided the complete description of the structure of the set of Chebyshev approximations. The author of [4, 5] also studied the approximate solutions of inconsistent \(\mathrm{max}-T\) systems, defined as the solutions of the consistent systems whose matrix is that of the inconsistent system and whose right-hand side vector is a Chebyshev approximation of the right-hand side vector of the inconsistent system. For each of the three \(\mathrm{max}-T\) systems, the author of [4, 5] showed that the greatest approximate solution of a given inconsistent system can be computed by an explicit analytical formula. For systems based on the max-min composition, the author of [5] gave a complete description of the structure of the approximate solutions set of the inconsistent system. Furthermore, for max-min systems, the author of [18] proposed a linear optimization method for computing \(L_{\infty}\) and \(L_{1}\) approximate solutions.

The works [5, 9, 10, 20] build on Pedrycz’s approach, focus on minimally modifying the right-hand side vector of an inconsistent systems, while keeping the matrix unmodified. In this article, we follow a different approach: we focus on minimally modifying the matrix of an inconsistent max-min system in order to obtain a consistent system, while keeping the right-hand side vector unchanged. This problem was studied by [8, 20] where the authors proposed algorithms for estimating the Chebyshev distance between the matrix of an inconsistent system and the closest matrix of a consistent system, where both systems have the same fixed right-hand side vector.

In this article, we consider an inconsistent system of max-min fuzzy relational equations of the form \(A{\sqcap}_{\operatorname*{min}}^{\operatorname*{max}}x=b,\), where the matrix A is of size \((n,m)\), the right-hand side vector b has n components, x is an unknown vector of m components and the matrix product \(\boxed{\begin{array}{r l}\end{array}}\) uses the t-norm min as the product and the function max as the addition. We begin by defining, in (17), the set T , which is formed by the matrices governing the consistent max-min systems that use the same right-hand side vector: the right-hand side vector b of the inconsistent system. Then, we introduce, in (18), the distance denoted by \(\mathring{\Delta}_{p}\) between the matrix A of the inconsistent system and the set \({\boldsymbol{\tau}}\), which is measured with respect to a given norm among \(L_{1}\), \(L_{2}\), or \(L_{\infty}\).

To introduce our method for constructing matrices of the set \(\tau\), we begin with a preliminary study. We define an auxiliary matrix \(A^{(i,j)}\), which minimally modify the matrix A of the inconsistent system \(A\varPi_{\operatorname*{min}}^{\operatorname*{max}}x=b\), in order to satisfy the following constraint: \(\delta^{A^{(i,j)}}(i,j)=0\), see (8) and Lemma 3, where the scalar \(\delta^{A^{(i,j)}}(i,j)\) is involved in the formula of [5] of the Chebyshev distance \(\Delta=\operatorname*{max}_{1\leq k\leq n}\delta_{k}^{A^{(i,j)}}\) where \(\delta_{k}^{A^{(i,j)}}=\operatorname*{min}_{1\leq j\leq m}\delta^{A^{(i,j)}}(k,j)\), see (11), associated with the right-hand side vector b of the max-min system \(A^{(i,j)}\Pi_{\operatorname*{min}}^{\operatorname*{max}}x=b\). We then define the matrices \(A^{(\vec{i},\vec{j})}\) in (27), whose construction is an iterative composition (27) of auxiliary matrices \(A^{(i,j)}\). In Proposition 5, we give a simpler construction of these matrices \(A^{(\vec{i},\vec{j})}\).

When the pair of vectors \((\vec{i},\vec{j})\) used to construct the matrices \(A^{(\vec{i},\vec{j})}\) of (27) are set from the subset of indices corresponding to the inconsistent equations of the system \(A\varPi_{\operatorname*{min}}^{\operatorname*{max}}x=b\) with respect to the Chebyshev distance \(\Delta\) (each equation whose index \(i\in\{1,2,\dots,n\}\) is such that \(\delta_{i}^{A}>0,\), see (11)) and a subset of column indices of the matrix A, we prove in Theorem 1 that the matrices \(A^{(\vec{i},\vec{j})}\) belong to the set \(\tau\). The matrices \(A^{(\vec{i},\vec{j})}\) of consistent systems constructed in Theorem 1 have important properties. In Theorem 2, we show that the modifications applied to the original matrix A of the inconsistent system to obtain the matrices \(A^{(\vec{i},\vec{j})}\) of the consistent systems are minimal. This result allows us to compute the distance \(\mathring{\Delta}_{p}\), see (18), in a simpler way, see Corollary 3. Furthermore, when using the \(L_{\infty}\) norm, i.e., \(p=\infty.\), we show that the distance \(\mathring{\Delta}_{\infty}\), see (18), can be computed using an explicit analytical formula, see Corollary 4, and we provide a method to construct a non-empty and finite subset of matrices \(A^{(\vec{i},\vec{j})}\) whose distance to the matrix A of the inconsistent system is equal to the scalar \(\hat{\Delta}_{\infty}\), see (37). Finally, we translate the tools and results obtained for max-min systems to the corresponding tools and results for min-max systems, see Subsection 5.2.

The article is structured as follows. In Section 2, we give the necessary background for studying inconsistent max-min systems. In Section 3, we present our problem formally and we introduce the construction of the auxiliary matrices, and the iterative construction (27) based on them. In Section 4, we show our main results: Theorem 1, Theorem 2,

2