# Approximate matrices of systems of max-min fuzzy relational equations

Ismaël Baaj

► To cite this version:

Ismaël Baaj. Approximate matrices of systems of max-min fuzzy relational equations. 2025. hal-05042994

HAL Id: hal-05042994

https://hal.science/hal-05042994v1

Preprint submitted on 22 Apr 2025

HAL is a multi-disciplinary open access
archive for the deposit and dissemination of sci-
entific research documents, whether they are pub-
lished or not. The documents may come from
teaching and research institutions in France or
abroad, or from public or private research centers.

L'archive ouverte pluridisciplinaire HAL, est
destinée au dépôt et à la diffusion de documents
scientifiques de niveau recherche, publiés ou non,
émanant des établissements d'enseignement et de
recherche français ou étrangers, des laboratoires
publics ou privés.

<figure><img src="image_1.png" /></figure>

Distributed under a Creative Commons Attribution 4.0 International License
# APPROXIMATE MATRICES OF SYSTEMS OF MAX-MIN FUZZY RELATIONAL EQUATIONS

A PREPRINT

Ismail Baaj

LEMMA, Paris-Panthéon-Assas University, Paris, 75006, France

ismail.baaj@assas-universite.fr

April 22, 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 $max-T$ compositions where $T$ is a continuous t-norm [11, 13, 14, 19, 21, 23, 24, 31], systems based on $max-*$ compositions, where $*$ is an increasing and continuous function [22], and systems based on $min-I_T$ compositions, where $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
inconsistency of systems of 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 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 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 max-$T$ systems, the author of [4, 5] showed that the greatest Chebyshev approximation of the right-hand side vector of an inconsistent 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 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 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 \square_{\min}^{\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 $A \square_{\min}^{\max}$ uses the t-norm $\min$ as the product and the function $\max$ as the addition. We begin by defining, in (17), the set $\mathcal{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 $\Delta_p$ between the matrix $A$ of the inconsistent system and the set $\mathcal{T}$, 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 $\mathcal{T}$, 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 \square_{\min}^{\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 = \max_{1 \le k \le n} \delta_k^{A^{(i,j)}}$ where $\delta_k^{A^{(i,j)}} = \min_{1 \le j \le 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)} \square_{\min}^{\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 \square_{\min}^{\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 $\mathcal{T}$. 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{j}, \vec{j})}$ of the consistent systems are minimal. This result allows us to compute the distance $\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 $\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{j}, \vec{j})}$ whose distance to the matrix $A$ of the inconsistent system is equal to the scalar $\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,
Corollary 3 and Corollary 4. In Section 5, we translate our results with max-min systems to min-max systems. Finally, we conclude with some perspectives.

## 2 Background

In this section, we give the necessary background for studying max-min systems. We begin by giving some notations. We then remind the solving of max-min systems and some of the results of [5] for handling the inconsistency of max-min systems.

### 2.1 Notations and matrix products

We use the following notations:

**Notation 1.** $[0, 1]^{n \times m}$ denotes the set of matrices of size $(n, m)$ i.e., $n$ rows and $m$ columns, whose components are in $[0, 1]$. In particular:

* $[0, 1]^{n \times 1}$ denotes the set of column vectors of $n$ components,

* $[0, 1]^{1 \times m}$ denotes the set of row matrices of $m$ components.

In the set $[0, 1]^{n \times m}$, we use the order relation $\le$ defined by:

$$A \le B \quad \text{iff we have} \quad a_{ij} \le b_{ij} \quad \text{for all} \quad 1 \le i \le n, 1 \le j \le m,$$

where $A = [a_{ij}]_{1 \le i \le n, 1 \le j \le m}$ and $B = [b_{ij}]_{1 \le i \le n, 1 \le j \le m}$.

The two matrix products $\Box_{\min}^{\max}$ and $\Box_{\to G}^{\min}$ used in this article are defined by modifying the usual matrix product:

* the matrix product $\Box_{\min}^{\max}$ is obtained by taking the t-norm $\min$ as the product and the function $\max$ as the addition.

* the matrix product $\Box_{\to G}^{\min}$ is obtained by taking the Gödel implication $\to_G$, which is defined by:

$$x \to_G y = \begin{cases} 1 & \text{if } x \le y \\ y & \text{otherwise.} \end{cases} \quad \text{in } [0, 1] \quad (1)$$

as the product and the function $\min$ as the addition.

### 2.2 Systems of max-min fuzzy relational equations

Let $A = [a_{ij}] \in [0, 1]^{n \times m}$ be a matrix of size $(n, m)$ and $b = [b_i] \in [0, 1]^{n \times 1}$ be a vector of $n$ components. The system of max-min fuzzy relational equations associated with $(A, b)$ is denoted by:

$$(S) : A \Box_{\min}^{\max} x = b, \quad (2)$$

where $x = [x_j]_{1 \le j \le m} \in [0, 1]^{m \times 1}$ is an unknown vector of $m$ components. By definition of the matrix product $\Box_{\min}^{\max}$, the system $(S)$ is equivalent to the following set of $n$ max-min equations:

$$\max_{1 \le j \le m} \min(a_{ij}, x_j) = b_i, \quad \forall i \in \{1, 2, \dots, n\}.$$

To check if the system $(S)$, see (2), is consistent, we compute the following vector:

$$e = A^t \Box_{\to G}^{\min} b, \quad (3)$$

where $A^t$ is the transpose of $A$ and we use the matrix product $\Box_{\to G}^{\min}$ (Notation 1). The components of the vector $e = [e_j]_{1 \le j \le m}$ are given by:

$$e_j = \min_{1 \le i \le n} (a_{ij} \to_G b_i), \forall j \in \{1, 2, \dots, m\}.$$

The vector $e$ is the potential greatest solution of the system $(S)$.

Thanks to Sanchez's seminal work [29] on the solving of systems max-min fuzzy relational equations, we have the following equivalence:

$$\text{The system } (S) \text{ is consistent} \iff A \Box_{\min}^{\max} e = b. \quad (4)$$
The set of solutions of the system (S) is denoted by:

$$S = S(A, b) = \{v \in [0, 1]^{m \times 1} \mid A \Box_{\min}^{\max} v = b\}. \qquad (5)$$

The structure of the solution set was described by Sanchez in [29] for systems of max-min fuzzy relational equations. He proved that if S is non-empty i.e., the system (S) is consistent, the structure of S is given by the vector $e = A^t \Box_{\rightarrow_G}^{\min} b$, see (3), which is the greatest solution of the system (S) and a finite number of minimal solutions.

**Example 1.** Let a max-min system $A \Box_{\min}^{\max} x = b$ be defined by $A = \begin{bmatrix} 0.79 & 0.29 & 0.28 \\ 0.76 & 0.79 & 0.18 \\ 0.53 & 0.21 & 0.11 \end{bmatrix}$ and $b = \begin{bmatrix} 0.35 \\ 0.6 \\ 0.35 \end{bmatrix}$.

We compute the potential greatest solution of the system:

$$e = A^t \Box_{\rightarrow_G}^{\min} b = \begin{bmatrix} \min(0.79 \rightarrow_G 0.35, 0.76 \rightarrow_G 0.6, 0.53 \rightarrow_G 0.35) \\ \min(0.29 \rightarrow_G 0.35, 0.79 \rightarrow_G 0.6, 0.21 \rightarrow_G 0.35) \\ \min(0.28 \rightarrow_G 0.35, 0.18 \rightarrow_G 0.6, 0.11 \rightarrow_G 0.35) \end{bmatrix} = \begin{bmatrix} 0.35 \\ 0.6 \\ 1 \end{bmatrix}.$$

The equation system $A \Box_{\min}^{\max} x = b$ is consistent because:

$$A \Box_{\min}^{\max} e = \begin{bmatrix} \max(\min(0.79, 0.35), \min(0.29, 0.6), \min(0.28, 1)) \\ \max(\min(0.76, 0.35), \min(0.79, 0.6), \min(0.18, 1)) \\ \max(\min(0.53, 0.35), \min(0.21, 0.6), \min(0.11, 1)) \end{bmatrix} = \begin{bmatrix} 0.35 \\ 0.6 \\ 0.35 \end{bmatrix} = b.$$

So the vector e is the greatest solution of the system.

## 2.3 Handling inconsistent systems of max-min fuzzy relational equations

Recently, the author of [5] studied how to handle inconsistent systems of max-min fuzzy relational equations. The tools introduced by [5] follow the strategy proposed by Pedrycz in [26], which is as follows: given an inconsistent system, we perturb, as slightly as possible, the components of the right-hand side vector of the inconsistent system in order to obtain a consistent system.

To remind the tools of the author [5] we reuse some of his notations:

**Notation 2.** For $x, y, z, u, \delta \in [0, 1]$, we use the following notations:

* $x^+ = \max(x, 0)$,

* $\bar{z}(\delta) = \min(z + \delta, 1)$,

* $\underline{z}(\delta) = \max(z - \delta, 0) = (z - \delta)^+$.

We rely on the following function, which was introduced in [5]:

$$\sigma_G(x, y, z) = \min\left(\frac{(x - z)^+}{2}, (y - z)^+\right) \quad \text{where} \quad x, y, z \in [0, 1]. \qquad (6)$$

Let $T = [t_{ij}]_{1 \le i \le n, 1 \le j \le m} \in [0, 1]^{n \times m}$ be a matrix. We rely on the following function defined for all $i \in \{1, 2, \dots, n\}$, which appears in [5] and uses the matrix T and the right-hand side vector $b = [b_i] \in [0, 1]^{n \times 1}$ of the system $T \Box_{\min}^{\max} x = b$:

$$[0, 1]^{n \times m} \rightarrow [0, 1] : T \mapsto \delta_i^T = \min_{1 \le j \le m} \delta^T(i, j) \qquad (7)$$

where:

$$\delta^T(i, j) = \max[(b_i - t_{ij})^+, \max_{1 \le k \le n} \sigma_G(b_i, t_{kj}, b_k)] \quad (\text{see (6) for the definition of } \sigma_G) \qquad (8)$$

Since the operations involved (minimum, maximum, and taking the positive part) are continuous on the compact set $[0, 1]^{n \times m}$, we get the following result:

**Lemma 1.** For all $i \in \{1, 2, \dots, n\}$, the function $[0, 1]^{n \times m} \rightarrow [0, 1] : T \mapsto \delta_i^T$ is continuous.

□

Given the matrix A of an inconsistent max-min system (S): $A \Box_{\min}^{\max} x = b$, see (2), the author of [5] defines:

**Definition 1.** The set formed by the right-hand side vectors of the consistent systems defined with the same matrix A of the system (S): $A \Box_{\min}^{\max} x = b$ is:

$$C = \{c \in [0, 1]^{n \times 1} \mid \text{the system } A \Box_{\min}^{\max} x = c \text{ is consistent} \}. \qquad (9)$$
**Definition 2.** The Chebyshev distance (using L-infinity norm) associated with the inconsistent max-min system (S) : $A\square_{\min}^{\max}x = b$ (see (2)) is:

$$ \Delta = \min_{c \in \mathcal{C}} \|b - c\|_{\infty} \quad \text{where} \quad \|b - c\| = \max_{1 \le i \le n} |b_i - c_i|. \qquad (10) $$

The author of [5] introduced an analytical formula for computing the Chebyshev distance $\Delta$ (Definition 2) associated to the max-min system (S) : $A\square_{\min}^{\max}x = b$, which relies on $\delta_i^A$, see (7):

$$ \Delta = \Delta(A, b) = \max_{1 \le i \le n} \delta_i^A \qquad (11) $$

The following results were proven in [5]:

$$ \Delta = 0 \iff \text{the system (S): } A\square_{\min}^{\max}x = b \text{ is consistent.} \qquad (12) $$

We define a subset of $\mathcal{C}$, see (9):

**Definition 3.** The set of Chebyshev approximations of the right-hand side vector b of the system (S) : $A\square_{\min}^{\max}x = b$ (see (2)) is defined using the Chebyshev distance $\Delta$ associated with the right-hand side vector b of (S) (see Definition 2):

$$ C_b = \{c \in [0, 1]^{n \times 1} \mid \text{the system } A\square_{\min}^{\max}x = c \text{ is consistent and } \|b - c\| = \Delta\} \subseteq \mathcal{C}. \qquad (13) $$

The author of [5] showed that we can directly obtain one vector in $C_b$: the greatest Chebyshev approximation of the right-hand side vector b:

$$ \hat{b} = A\square_{\min}^{\max}(A^t \square_{\to_G}^{\min} \bar{b}(\Delta)) \in C_b, \qquad (14) $$

where $\bar{b}(\Delta) = [\min(b_i + \Delta, 1)]_{1 \le i \le n}$. So, we have $\|b - \bar{b}\| = \Delta$ and the system $A\square_{\min}^{\max}x = \hat{b}$ is consistent. Obtaining the minimal Chebyshev approximations of b is possible with a method developed in [5], but minimal approximations are more expensive to obtain in terms of computational cost than the greatest Chebyshev approximation $\hat{b}$.

The author of [5] defines:

**Definition 4.** An approximate solution of the system (S) : $A\square_{\min}^{\max}x = b$ is a vector $x^*$ such that the distance between the vector c = $A\square_{\min}^{\max}x^*$ and the vector b is equal to $\Delta$, i.e., we have $\|b - c\| = \Delta$. Thus, the vector $x^*$ is a solution of a consistent system $A\square_{\min}^{\max}x = c$ defined with the matrix A and the vector c, which is a Chebyshev approximation of b (Definition 3), i.e., we have $c \in C_b$.

In [5], the author showed that we can directly obtain the greatest approximate solution of the system (S), which is the following vector:

$$ \eta = A^t \square_{\to_G}^{\min} \bar{b}(\Delta). \qquad (15) $$

Of course, the greatest approximate solution $\eta$ of the system (S) is the greatest solution of the consistent system $A\square_{\min}^{\max}x = \hat{b}$. In [5], the author describes how to obtain a set of minimal approximate solutions.

**Example 2.** Let a max-min system $A\square_{\min}^{\max}x = b$ be defined by:

$$ A = \begin{bmatrix} 0.04 & 0.73 & 0.50 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.90 & 0.35 \end{bmatrix} \quad \text{and} \quad b = \begin{bmatrix} 0.30 \\ 0.42 \\ 0.76 \end{bmatrix} \qquad (16) $$

We compute the Chebyshev distance $\Delta$, see (11), associated with the right-hand side vector b of the max-min system $A\square_{\min}^{\max}x = b$:

$$ \Delta = \max_{1 \le i \le 3} \delta_i^A $$

where:

$$ \delta_1^A = \min(\delta(1, 1), \delta(1, 2), \delta(1, 3)) = \min(0.26, 0, 0) = 0, $$

$$ \delta_2^A = \min(\delta(2, 1), \delta(2, 2), \delta(2, 3)) = \min(0.09, 0.07, 0.06) = 0.06, $$

$$ \delta_3^A = \min(\delta(3, 1), \delta(3, 2), \delta(3, 3)) = \min(0.21, 0.23, 0.41) = 0.21. $$
Therefore, we obtain $\Delta = 0.21$, so, from (12), the system $A\Box_{\min}^{\max}x = b$ is inconsistent. Let us compute $\bar{b}(\Delta) = \begin{bmatrix} 0.51 \\ 0.63 \\ 0.97 \end{bmatrix}$ and the greatest Chebyshev approximation of $b$, see (14):

$$ \hat{b} = A\Box_{\min}^{\max}(A^t\Box_{\rightarrow_G}^{\min}\bar{b}(\Delta)) = \begin{bmatrix} 0.51 \\ 0.63 \\ 0.55 \end{bmatrix}. $$

One can check that $\|b - \hat{b}\| = \Delta$ and that the system $A\Box_{\min}^{\max}x = \hat{b}$ is consistent.

We compute the greatest approximate solution of the inconsistent system $A\Box_{\min}^{\max}x = b$, see (15):

$$ \eta = A^t \Box_{\rightarrow_G}^{\min} \bar{b}(\Delta) = \begin{bmatrix} 1.0 \\ 0.51 \\ 0.63 \end{bmatrix}. $$

One can check that $\eta$ is the greatest solution of the consistent system $A\Box_{\min}^{\max}x = \hat{b}$.

### 3 On minimally modifying the matrix of an inconsistent max-min system

In this section, we present our problem formally: how to minimally modify the matrix $A$ of size $(n, m)$ of an inconsistent max-min system $(S)$: $A\Box_{\min}^{\max}x = b$, see (2), in order to obtain a consistent system, while keeping the right-hand side vector $b$ unchanged.

For this purpose, we introduce the following set, which is formed by the matrices of size $(n, m)$ governing the consistent max-min systems which use the same right-hand side vector: the right-hand side vector $b$ of the system $(S)$:

$$ \mathcal{T} = \{T \in [0, 1]^{n \times m} \mid \text{the system } T \Box_{\min}^{\max} x = b \text{ is consistent}\}. \qquad (17) $$

It is easy to see that the particular matrix $T = [t_{kl}]_{1 \le k \le n, 1 \le l \le m}$ whose coefficients are $t_{kl} := b_k$, belongs to the set $\mathcal{T}$. Therefore $\mathcal{T}$ is a non-empty set.

For each $p \in \{1, 2, \infty\}$, we define the distance from the fixed matrix $A$ to the set $\mathcal{T}$ as:

$$ \hat{\Delta}_p := \inf_{T \in \mathcal{T}} \|T - A\|_p. \qquad (18) $$

Here, $\| \cdot \|_p$ denotes the matrix norm with exponent $p$, namely, for a matrix $X = [x_{ij}] \in \mathbb{R}^{n \times m}$:

$$ \|X\|_p = \begin{cases} \sum_{i=1}^{n} \sum_{j=1}^{m} |x_{ij}|, & p=1, \\ \left(\sum_{i=1}^{n} \sum_{j=1}^{m} |x_{ij}|^2\right)^{1/2}, & p=2, \\ \max_{1 \le i \le n, 1 \le j \le m} |x_{ij}|, & p=\infty. \end{cases} \qquad (19) $$

Our aim is to compute matrices in the set $\mathcal{T}$, i.e., matrices governing consistent max-min systems whose right-hand side vector is $b$, which are the closest to the matrix $A$ of the system $(S)$: $A\Box_{\min}^{\max}x = b$ according to the distance $\hat{\Delta}_p$. We also study how to compute the distance $\hat{\Delta}_p$ with respect to $p$ according to the coefficients of $A$ and $b$.

In this section, we present some preliminary results and tools that will be useful for constructing matrices in the set $\mathcal{T}$ in subsequent sections. We show that the matrices of the set $\mathcal{T}$ defined in (17) dominate in a certain sense the auxiliary matrices noted $A^{(i,j)}$ associated with pairs of indices $(i, j) \in \{1, 2, \dots, n\} \times \{1, 2, \dots, m\}$, that we introduce in Definition 5. We establish useful properties of these auxiliary matrices $A^{(i,j)}$ for our problem.

**Lemma 2.** The formula (18) can be rewritten as:

$$ \hat{\Delta}_p = \min_{T \in \mathcal{T}} \|T - A\|_p. $$

The proof is given in Subsection A.1.

We deduce the following equivalence, which is analog to (12):
**Corollary 1.**

$$ \Delta_p = 0 \iff \text{the system (S) is consistent.} \qquad (20) $$

<figure><img src="image_2.png" /></figure>

**3.1 Constructing the auxiliary matrices $A^{(i,j)}$ from the matrix $A$ of the inconsistent system (S) : $A_{\min}^{\max} x = b$**

We introduce the following notations associated with the system (S) : $A_{\min}^{\max} x = b$, see (2).

**Notation 3.** Let us use the following set of indices:

$$ I = \{1, 2, \dots, n\} \quad \text{and} \quad J = \{1, 2, \dots, m\}. \qquad (21) $$

For all $(i, j) \in I \times J$, a given matrix $T = [t_{ij}]_{1 \le i \le n, 1 \le j \le m} \in [0, 1]^{n \times m}$ and the right-hand side vector $b$ of the system (S), we define the following set using the function $\sigma_G$, see (6):

$$ U_{ij}^{T} := \{k \in I \mid \sigma_{G}(b_{i}, t_{kj}, b_{k}) > 0\}. \qquad (22) $$

Using (6), we get the following equivalent definition of the set $U_{ij}^T$:

$$ U_{ij}^{T} = \{k \in I \mid \theta(i, k) \cdot (t_{kj} - b_{k})^{+} > 0\} \quad \text{where} \quad \theta: I \times I \mapsto \{0, 1\} : \theta(i, k) = \begin{cases} 1 & \text{if } b_i > b_k \\ 0 & \text{otherwise.} \end{cases} \qquad (23) $$

In particular, for any pair of indices $(i, j) \in I \times J$, we can compute the set $U_{ij}^A$ using the matrix $A$ of the system (S). From the formula of the Chebyshev distance $\Delta = \max_{1 \le i \le n} \delta_i^A$, see (11), associated with the right-hand side vector $b$ of the system (S), we set:

$$ N_{\text{cons}} := \{i \in I \mid \delta_i^A = 0\} \quad \text{and} \quad N_{\text{inc}} := \overline{N_{\text{cons}}} = \{i \in I \mid \delta_i^A > 0\}. \qquad (24) $$

The two disjoint sets $N_{\text{cons}}$ and $N_{\text{inc}}$ form a partition of the set $I$ associated with the pair $(A, b)$. We know by (12) that the equality $N_{\text{cons}} = I$ is equivalent to the consistency of the system (S) : $A_{\min}^{\max} x = b$.

**Definition 5.** For any fixed pair of indices $(i, j) \in I \times J$, we define the matrix $A^{(i,j)} := [a_{kl}^{(i,j)}]_{1 \le k \le n, 1 \le l \le m} \in [0, 1]^{n \times m}$, whose coefficients are defined using the matrix $A$, the right-hand side vector $b$ of the inconsistent system (S) : $A_{\min}^{\max} x = b$, and the set $U_{ij}^A$, see (22), by:

$$ a_{ij}^{(i,j)} := \begin{cases} b_i & \text{if } b_i > a_{ij} \\ a_{ij} & \text{if } b_i \le a_{ij} \end{cases} \quad \text{and for} \quad \forall k \in I \setminus \{i\}, \quad a_{kj}^{(i,j)} := \begin{cases} b_k & \text{if } k \in U_{ij}^A \\ a_{kj} & \text{if } k \notin U_{ij}^A \end{cases}. \qquad (25a) $$

$$ \forall k \in I \forall l \in J \setminus \{j\}, \quad a_{kl}^{(i,j)} := a_{kl}. \qquad (25b) $$

The matrix $A^{(i,j)}$ is derived from the matrix $A$ by only modifying some entries in the column with index $j$. Specifically, we have:

$$ \forall (k, l) \in I \times J, \quad a_{kl}^{(i,j)} \in \{b_k, a_{kl}\}. \qquad (26) $$

We begin by establishing some useful properties of the scalars $\delta^{A^{(i,j)}}(s, l)$, which is computed using (8) and associated with the matrix $A^{(i,j)}$ and the right-hand side vector $b$:

**Lemma 3.** Let $(i, j) \in I \times J$ be a fixed pair of indices. Then, we have:

1. $\delta^{A^{(i,j)}}(i, j) = 0$.

2. For all $1 \le s \le n$, we have:

$$ \delta^A(s, j) = 0 \implies \delta^{A^{(i,j)}}(s, j) = 0. $$

3. For all $1 \le s \le n$ and $1 \le l \ne j \le m$, we have:

$$ \delta^{A^{(i,j)}}(s, l) = \delta^{A}(s, l). $$

4. $\|A^{(i,j)} - A\|_{\infty} = \max[(b_i - a_{ij})^+, \max_{k \in I, k \ne i} (\theta(i, k) \cdot (a_{kj} - b_k)^+)]$

where the function $\theta$ is defined in (23).
Any matrix $T = [t_{kl}]_{1 \le k \le n, 1 \le l \le m}$ satisfying $\delta^T(i, j) = 0$ for a given pair of indices $(i, j) \in I \times J$ dominates the auxiliary matrix $A^{(i,j)}$ in the following sense: the distance $|t_{kl} - a_{kl}|$ between a coefficient $t_{kl}$ of the matrix $T$ and the corresponding coefficient $a_{kl}$ of the original matrix $A = [a_{kl}]$ is always at least as large as the distance $|a_{kl}^{(i,j)} - a_{kl}|$ between the coefficient $a_{kl}^{(i,j)}$ of the matrix $A^{(i,j)}$ and $a_{kl}$:

**Lemma 4.** Let $T = [t_{kl}]_{1 \le k \le n, 1 \le l \le m}$ be a matrix such that $\delta^T(i, j) = 0$. Then, we have:

$$1. \quad |a_{kl}^{(i,j)} - a_{kl}| \le |t_{kl} - a_{kl}| \quad \text{for all pairs } (k, l) \in I \times J,$$

$$2. \quad \|A^{(i,j)} - A\|_{p} \le \|T - A\|_{p} \quad \text{for } p \in \{1, 2, \infty\}.$$

In the following lemma, we show that if we first apply the transformation $A \mapsto A^{(i,j)}$ with parameters $(i_1, j_1)$ to the fixed matrix $A$, and then apply to the resulting matrix the same transformation with parameters $(i_2, j_2)$ with $i_1 \ne i_2$, the final result is the same as when the order of these two transformations is reversed.

**Lemma 5.** Let $i_1, i_2 \in I$ with $i_1 \ne i_2$ and $j_1, j_2 \in J$. Define

$$C := A^{(i_1, j_1)}, \quad D := C^{(i_2, j_2)}, \quad E := A^{(i_2, j_2)}, \quad F := E^{(i_1, j_1)}.$$

Then,

$$D = F.$$

The proofs of Lemma 3, 4 and 5 are written in Subsection A.2.

**Example 3.** (continued) We reuse the inconsistent max-min system (S) : $A \square_{\min}^{\max} x = b$ of Example 2 where:

$$A = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix}, \quad b = \begin{bmatrix} 0.3 \\ 0.42 \\ 0.76 \end{bmatrix}.$$

We computed:

$$\Delta = \max_{1 \le i \le n} \delta_i^A = 0.21, \quad \text{where } \delta_1^A = 0, \delta_2^A = 0.06, \text{ and } \delta_3^A = 0.21.$$

Therefore, we have:

$$N_{\text{cons}} = \{1\}, \quad N_{\text{inc}} = \{2, 3\}.$$

We construct the matrices $A^{(i,j)}$, see Definition 5.

Case $(i, j) = (1, 1)$:

$$U_{1,1}^A = \emptyset.$$

Modified matrix:

$$A^{(1,1)} = \begin{bmatrix} 0.3 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

with the (1, 1)-entry changed from 0.04 to 0.3, and we have $\delta^{A^{(1,1)}}(1, 1) = 0$.

Case $(i, j) = (1, 2)$:

$$U_{1,2}^A = \emptyset.$$

Matrix remains:

$$A^{(1,2)} = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

with no changes, and we have $\delta^A(1, 2) = \delta^{A^{(1,2)}}(1, 2) = 0$.

Case $(i, j) = (1, 3)$:

$$U_{1,3}^A = \emptyset.$$

Matrix remains:

$$A^{(1,3)} = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$
with no changes, and we have $\delta^A(1, 3) = \delta^{A^{(1,3)}}(1, 3) = 0$.

Case $(i, j) = (2, 1)$:

$$U_{2,1}^A = \emptyset.$$

Modified matrix:

$$A^{(2,1)} = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.42 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

with the (2, 1)-entry changed from 0.33 to 0.42, and we have $\delta^{A^{(2,1)}}(2, 1) = 0$.

Case $(i, j) = (2, 2)$:

$$U_{2,2}^A = \{1\}, \quad \text{since } \sigma_G(b_2, a_{1,2}, b_1) = \sigma_G(0.42, 0.73, 0.3) = 0.06 > 0.$$

Modified matrix:

$$A^{(2,2)} = \begin{bmatrix} 0.04 & 0.3 & 0.5 \\ 0.33 & 0.42 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

with the (2, 2)-entry changed from 0.35 to 0.42 and the (1, 2)-entry changed from 0.73 to 0.3, and we have $\delta^{A^{(2,2)}}(2, 2) = 0$.

Case $(i, j) = (2, 3)$:

$$U_{2,3}^A = \{1\}, \quad \text{since } \sigma_G(b_2, a_{1,3}, b_1) = \sigma_G(0.42, 0.5, 0.3) = 0.06 > 0.$$

Modified matrix:

$$A^{(2,3)} = \begin{bmatrix} 0.04 & 0.73 & 0.3 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

with the (1, 3)-entry changed from 0.5 to 0.3, and we have $\delta^{A^{(3,3)}}(2, 3) = 0$.

Case $(i, j) = (3, 1)$:

$$U_{3,1}^A = \emptyset.$$

Modified matrix:

$$A^{(3,1)} = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.76 & 0.9 & 0.35 \end{bmatrix},$$

with the (3, 1)-entry changed from 0.55 to 0.76, and we have $\delta^{A^{(3,1)}}(3, 1) = 0$.

Case $(i, j) = (3, 2)$:

$$U_{3,2}^A = \{1\}, \quad \text{since } \sigma_G(b_3, a_{1,2}, b_1) = \sigma_G(0.76, 0.73, 0.3) = 0.23 > 0.$$

Modified matrix:

$$A^{(3,2)} = \begin{bmatrix} 0.04 & 0.3 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

with the (1, 2)-entry changed from 0.73 to 0.3, and we have $\delta^{A^{(3,2)}}(3, 2) = 0$.

Case $(i, j) = (3, 3)$:

$$U_{3,3}^A = \{1, 2\}, \quad \text{since } \sigma_G(b_3, a_{1,3}, b_1) = \sigma_G(0.76, 0.5, 0.3) = 0.2 > 0 \quad (k = 1)$$

and

$$\sigma_G(b_3, a_{2,3}, b_2) = \sigma_G(0.76, 0.94, 0.42) = 0.17 > 0 \quad (k = 2).$$

Modified matrix:

$$A^{(3,3)} = \begin{bmatrix} 0.04 & 0.73 & 0.3 \\ 0.33 & 0.35 & 0.42 \\ 0.55 & 0.9 & 0.76 \end{bmatrix},$$
with the (3,3)-entry changed from 0.35 to 0.76, the (1,3)-entry changed from 0.5 to 0.3, and the (2,3)-entry changed from 0.94 to 0.42, and we have $\delta A^{(3,3)}(3, 3) = 0$.

We now illustrate Lemma 5. For instance, let $i_1 = 1$, $j_1 = 1$, $i_2 = 2$, and $j_2 = 1$. We have $C = A^{(1,1)}$ and $E = A^{(2,1)}$. We compute:

$$D = C^{(2,1)} = \begin{bmatrix} 0.3 & 0.73 & 0.5 \\ 0.42 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix}.$$

where the entry at coordinate (2, 1) is changed from 0.33 in C to 0.42 in D. Similarly,

$$F = E^{(1,1)} = \begin{bmatrix} 0.3 & 0.73 & 0.5 \\ 0.42 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix}.$$

where the entry at coordinate (1, 1) is changed from 0.04 in E to 0.3 in F. Thus, we observe that

$$D = F,$$

which confirms the lemma.

## 3.2 Constructing the matrices $A^{(\vec{i},\vec{j})}$ from the matrix $A$ of the inconsistent system (S) : $A^{\max}_{\min}x = b$

In this subsection, we generalize the construction of auxiliary matrices $A^{(i,j)}$ associated with pairs $(i, j) \in I \times J$ to pairs of index uplets $(\vec{i}, \vec{j}) \in I^h \times J^h$ where $1 \le h \le n$, see (27). In the next section, Theorem 1 will show that for specific pairs $(\vec{i}, \vec{j})$, matrices $A^{(\vec{i}, \vec{j})}$ obtained with the construction (27) belong to the set $\mathcal{T}$, see (17), i.e., using these specific pairs $(\vec{i}, \vec{j})$, the matrices $A^{(\vec{i}, \vec{j})}$ are matrices governing consistent max-min systems whose right-hand side vector is the right-hand side vector $b$ of the system (S).

### 3.2.1 Iterative construction of the matrices $A^{(\vec{i},\vec{j})}$

Let $h$ be an integer satisfying $1 \le h \le n$ where $n = \text{card}(I)$, where the set $I$ is defined in Notation 3, along with the set $J$.

**Definition 6.** For any $h$-tuple $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ consisting of two-by-two distinct indices from the set $I$ (i.e., for all $u, v \in \{1, 2, \dots, h\}$ with $u \ne v$, $i_u \ne i_v$) and a $h$-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$ of indices of the set $J$, we associate the matrix denoted $A^{(\vec{i}, \vec{j})}$ which is constructed by successively applying the modifications indicated by the pairs $(i_1, j_1), (i_2, j_2), \dots, (i_h, j_h)$ (using Definition 5) as follows:

$$A^{(\vec{i}, \vec{j})} = \begin{cases} A^{(i_1, j_1)} & \text{if } h = 1, \\ C^{(i_h, j_h)} & \text{if } h > 1 \text{ and } C := A^{(i_1, j_1) * (i_2, j_2) * \dots * (i_{h-1}, j_{h-1})}. \end{cases} \quad (27)$$

In (27), the matrix $C$ is the intermediate matrix obtained by successively applying the modifications corresponding to the pairs $(i_1, j_1), (i_2, j_2), \dots, (i_{h-1}, j_{h-1})$ to the original matrix $A$. Then, the final matrix $A^{(\vec{i}, \vec{j})}$ is obtained by applying the modification $(i_h, j_h)$ to $C$. This construction can also be written as

$$A^{(\vec{i}, \vec{j})} = (((A^{(i_1, j_1)})(i_2, j_2))(i_3, j_3) \dots)(i_h, j_h).$$

### 3.2.2 Properties of the matrices $A^{(\vec{i},\vec{j})}$

By induction on $h$, one can verify the following properties:

**Proposition 1.**

1. For every $(k, l) \in I \times J$,

$$a_{kl}^{(\vec{i}, \vec{j})} \in \{b_k, a_{kl}\}.$$

2. For every $k \in I$ and for every $l \notin \{j_1, j_2, \dots, j_h\}$,

$$a_{kl}^{(\vec{i}, \vec{j})} = a_{kl}.$$
These properties extend those of the matrices $A^{(i,j)}$ given in (25a), (25b) and (26). They ensure that the modifications introduced by $A^{(\vec{i},\vec{j})}$ affect only the columns indexed by $j_1, j_2, \dots, j_h$, while all other coefficients of the matrix $A$ remain unchanged.

The following result generalizes Lemma 5 in the following sense:

**Proposition 2.** Let $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ be an $h$-tuple of two-by-two distinct indices of the set $I$ and $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$. For any permutation $\pi$ of the set $\{1, 2, \dots, h\}$ i.e., $\pi: \{1, 2, \dots, h\} \to \{1, 2, \dots, h\}: \lambda \mapsto i_\lambda$, define

$$ \vec{i} \triangleleft \pi = (i_{\pi(1)}, i_{\pi(2)}, \dots, i_{\pi(h)}) \quad \text{and} \quad \vec{j} \triangleleft \pi = (j_{\pi(1)}, j_{\pi(2)}, \dots, j_{\pi(h)}). \qquad (28) $$

Then, the matrix obtained by successively modifying $A$ using the pairs $(i_1, j_1), (i_2, j_2), \dots, (i_h, j_h)$ is identical to the matrix obtained by applying these modifications in any permuted order; that is,

$$ A^{(\vec{i}, \vec{j})} = A^{(\vec{i} \triangleleft \pi, \vec{j} \triangleleft \pi)}, \qquad (29) $$

or equivalently,

$$ A^{(i_1, j_1) * (i_2, j_2) * \dots * (i_h, j_h)} = A^{(i_{\pi(1)}, j_{\pi(1)}) * (i_{\pi(2)}, j_{\pi(2)}) * \dots * (i_{\pi(h)}, j_{\pi(h)}).} $$

**Proposition 2** allows us to generalize Lemma 3 and Lemma 4 to the matrices $A^{(\vec{i},\vec{j})}$. We rely on the scalars $\delta^{A^{(\vec{i},\vec{j})}}(s, l)$ (resp. $\delta^A(s, l)$), which are associated with the matrix $A^{(\vec{i},\vec{j})}$ (resp. $A$), see (8).

**Proposition 3.** Let $A = [a_{kl}] \in [0, 1]^{n \times m}$, $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ be an $h$-tuple of two-by-two distinct indices and $\vec{j} = (j_1, \dots, j_h) \in J^h$. We construct the matrix $A^{(\vec{i},\vec{j})} = [a_{kl}^{(\vec{i},\vec{j})}]_{1 \le k \le n, 1 \le l \le m}$ using (27). We have:

1. For all $(k, l) \in I \times J$, we have $a_{kl}^{(\vec{i},\vec{j})} \in \{b_k, a_{kl}\}$.

2. For all $\lambda \in \{1, \dots, h\}$, we have $\delta^{A^{(\vec{i},\vec{j})}}(i_\lambda, j_\lambda) = 0$.

3. For all $s \in I$ and for all $l \in \{j_1, j_2, \dots, j_h\}$, we have $\delta^A(s, l) = 0 \implies \delta^{A^{(\vec{i},\vec{j})}}(s, l) = 0$.

4. For all $s \in I$ and for all $l \notin \{j_1, j_2, \dots, j_h\}$, we have $\delta^{A^{(\vec{i},\vec{j})}}(s, l) = \delta^A(s, l)$.

**Proposition 4.** Let $A = [a_{kl}] \in [0, 1]^{n \times m}$, Let $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ be an $h$-tuple of two-by-two distinct indices of the set $I$ and $\vec{j} = (j_1, \dots, j_h) \in J^h$. We construct the matrix $A^{(\vec{i},\vec{j})} = [a_{kl}^{(\vec{i},\vec{j})}]$ using (27). For any matrix $T \in [0, 1]^{n \times m}$ verifying $\delta^T(i_\lambda, j_\lambda) = 0$ for all $\lambda \in \{1, 2, \dots, h\}$, we have:

$$ \forall (k, l) \in I \times J, \quad |a_{kl}^{(\vec{i},\vec{j})} - a_{kl}| \le |t_{kl} - a_{kl}|. \qquad (30) $$

It clearly follows that:

$$ \|A^{(\vec{i},\vec{j})} - A\|_p \le \|T - A\|_p \quad \text{for } p \in \{1, 2, \infty\}. $$

The proofs of Propositions 1, 2, 3 and 4 are given in Subsection A.3.

### 3.2.3 Computing the coefficients of $A^{(\vec{i},\vec{j})}$

Let us consider $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ a pair of $h$-tuples as in Definition 6. In the following, we present a method for computing the coefficients of the matrix $A^{(\vec{i},\vec{j})}$ in a simpler way than the construction provided in (27).

We introduce three sets $\mathcal{E}_1, \mathcal{E}_2$ and $\mathcal{E}$ of index pairs that depend on $A, b$ and $(\vec{i}, \vec{j})$:

1. The set $\mathcal{E}_1$ is formed by the pairs $(i_\lambda, j_\lambda)$ where $\lambda \in \{1, 2, \dots, h\}$ for which the corresponding component $b_{i_\lambda}$ of the right-hand side vector $b$ is strictly greater than the entry $a_{i_\lambda j_\lambda}$ of the matrix $A$:

$$ \mathcal{E}_1 := \{(i_\lambda, j_\lambda) \in I \times J \mid \lambda \in \{1, \dots, h\} \text{ and } b_{i_\lambda j_\lambda} > a_{i_\lambda j_\lambda}\}. \qquad (31a) $$

2. The set $\mathcal{E}_2$ is defined using the sets $U_{i_\lambda j_\lambda}^A = \{k \in I \mid \sigma_G(b_{i_\lambda}, a_{k j_\lambda}, b_k) > 0\}$, see (22):

$$ \mathcal{E}_2 := \bigcup_{\lambda=1}^{h} \{(k, j_{\lambda}) \mid k \in U_{i_{\lambda} j_{\lambda}}^{A}\} \subseteq I \times J. \qquad (31b) $$
3. Finally, the set $\mathcal{E}$ is defined as the union of the previous two sets:

$$ \mathcal{E} := \mathcal{E}_1 \cup \mathcal{E}_2 \subseteq I \times J. \quad (31c) $$

Note that for every pair $(k, l)$ where $k \in I$ and $l \in J \setminus \{j_1, j_2, \dots, j_h\}$, we have $(k, l) \notin \mathcal{E}$, since both $\mathcal{E}_1$ and $\mathcal{E}_2$ only contain pairs with the second component equal to one of $j_1, \dots, j_h$.

Let us fix an index $\lambda \in \{1, 2, \dots, h\}$ and define the reduced $(h-1)$-tuples $\vec{i}'$ and $\vec{j}'$ by removing the $\lambda$-th component from $\vec{i}$ and $\vec{j}$, respectively. We need to establish relationships between the sets $\mathcal{E}_1, \mathcal{E}_2, \mathcal{E}$, associated to the original pair $(\vec{i}, \vec{j})$, and the sets $\mathcal{E}'_1, \mathcal{E}'_2, \mathcal{E}'$, associated to the reduced pair $(\vec{i}', \vec{j}')$.

Set $\vec{i}' = (i'_1, i'_2, \dots, i'_{h-1})$ and $\vec{j}' = (j'_1, j'_2, \dots, j'_{h-1})$. We have for every $\lambda' \in \{1, 2, \dots, h-1\}$:

$$ i'_{\lambda'} = \begin{cases} i_{\lambda'}, & \text{if } \lambda' \le \lambda - 1, \\ i_{\lambda'+1}, & \text{if } \lambda' \ge \lambda, \end{cases} \quad j'_{\lambda'} = \begin{cases} j_{\lambda'}, & \text{if } \lambda' \le \lambda - 1, \\ j_{\lambda'+1}, & \text{if } \lambda' \ge \lambda. \end{cases} $$

The sets $\mathcal{E}'_1, \mathcal{E}'_2, \mathcal{E}'$ associated with the matrix $A$, the right-hand side vector $b$ of the system $(S)$ and the pair of $(h-1)$-tuples $(\vec{i}', \vec{j}')$, are the following subsets of $I \times J$:

$$ \mathcal{E}'_1 = \{(i'_{\lambda'}, j'_{\lambda'}) \in I \times J \mid \lambda' \in \{1, \dots, h-1\} \text{ and } b_{i'_{\lambda'}, j'_{\lambda'}} > a_{i'_{\lambda'}, j'_{\lambda'}}\}, \quad (32a) $$

$$ \mathcal{E}'_2 = \bigcup_{\lambda'=1}^{h-1} \{(k, j'_{\lambda'}) \mid k \in U_{i'_{\lambda'}, j'_{\lambda'}}^A\}, \quad (32b) $$

$$ \mathcal{E}' = \mathcal{E}'_1 \cup \mathcal{E}'_2. \quad (32c) $$

It is clear from the definitions of the sets $\mathcal{E}_1, \mathcal{E}_2$, and $\mathcal{E}$ that the following properties hold.

**Lemma 6.** Let $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ be a pair of $h$-tuples as in Definition 6. For $h > 1$, let $\mathcal{E}_1, \mathcal{E}_2$, and $\mathcal{E}$ be the sets associated to the pair $(\vec{i}, \vec{j})$ as in (31). Given a fixed index $\lambda \in \{1, 2, \dots, h\}$, let $(\vec{i}', \vec{j}')$ denote the pair obtained by removing the $\lambda$-th component from $(\vec{i}, \vec{j})$. Then, the corresponding sets $\mathcal{E}'_1, \mathcal{E}'_2$, and $\mathcal{E}'$, see (32), satisfy:

$$ 1. \quad \mathcal{E}'_1 = \mathcal{E}_1 \setminus \{(i_{\lambda}, j_{\lambda})\}, $$

$$ 2. \quad \mathcal{E}'_2 \subseteq \mathcal{E}_2, $$

$$ 3. \quad \mathcal{E}' = \mathcal{E}'_1 \cup \mathcal{E}'_2 \subseteq \mathcal{E}. $$

□

The set $\mathcal{E}$, see (31), allows us to construct the matrix $A(\vec{i}, \vec{j})$, see (27), in a simpler way:

**Proposition 5.** Let $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ be a pair of $h$-tuples as in Definition 6. Then, the coefficients of the modified matrix $A(\vec{i}, \vec{j}) = [a_{kl}^{(\vec{i}, \vec{j})}]_{1 \le k \le n, 1 \le l \le m}$, see (27), are given by:

$$ \text{for every } (k, l) \in I \times J, \quad a_{kl}^{(\vec{i}, \vec{j})} = \begin{cases} b_k, & \text{if } (k, l) \in \mathcal{E}, \\ a_{kl}, & \text{if } (k, l) \notin \mathcal{E}. \end{cases} $$

The proof is by induction on $h \ge 1$, see Section A.3.

The $L_\infty$ distance $\|A(\vec{i}, \vec{j}) - A\|_\infty$ can be easily computed using:

**Corollary 2.** Let $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ be a pair of $h$-tuples as in Definition 6. Then, we have:

$$ \|A(\vec{i}, \vec{j}) - A\|_{\infty} = \max_{1 \le \lambda \le h} \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \quad (33) $$

The proof of Corollary 2 is in Section A.3

**Example 4.** (continued)
We reuse the inconsistent max-min system (S) : $A \square_{\min}^{\max} x = b$ of Example 2 where:

$$A = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix}, \quad b = \begin{bmatrix} 0.3 \\ 0.42 \\ 0.76 \end{bmatrix}.$$

Let $\vec{i} = (i_1, i_2) = (1, 2)$ and $\vec{j} = (j_1, j_2) = (1, 1)$. We get $\mathcal{E}_1 = \{(1, 1), (2, 1)\}$ and $\mathcal{E}_2 = \emptyset$. So, we have $\mathcal{E} = \mathcal{E}_1$.

The matrix $A(\vec{i}, \vec{j})$ is:

$$\begin{bmatrix} 0.30 & 0.73 & 0.50 \\ 0.42 & 0.35 & 0.94 \\ 0.55 & 0.90 & 0.35. \end{bmatrix}$$

which is equal to the matrices D and F obtained in the end of Example 4 for illustrating Lemma 5.

# 4 Main results on constructing consistent systems by minimally modifying the matrix of an inconsistent max-min system

In this section, we establish our main results for handling the inconsistency of a max-min system (S) : $A \square_{\min}^{\max} x = b$ by constructing consistent systems close to the system (S): for each obtained consistent system that we obtain, its right-hand side vector is the right-hand side vector b of the system (S) while its matrix is of the form $A(\vec{i}, \vec{j})$ (Definition 6) and is obtained by minimal modifications of the matrix A of the system (S), see Theorem 1 and Theorem 2.

From these results, we compute the distance $\hat{\Delta}_p$, see (18), in a simpler way, see Corollary 3. Furthermore, when using the $L_\infty$ norm, i.e., $p = \infty$, we give an explicit analytical formula (Corollary 4) for computing the distance $\hat{\Delta}_\infty$, see (18). Finally, 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).

## 4.1 Constructing consistent systems close to the initial inconsistent system (S)

We show that for some pairs $(\vec{i}, \vec{j})$, the matrix $A(\vec{i}, \vec{j})$ constructed from A and b with (27), yields a consistent max-min system whose matrix is $A(\vec{i}, \vec{j})$ and its right-hand side vector is still the vector b of the system (S):

**Theorem 1.** We use the non-empty set $N_{inc}$ with $h := \text{card}(N_{inc})$, see (24). Choose an arbitrary enumeration of $N_{inc}$ as $\{i_1, i_2, \dots, i_h\}$ and set $\vec{i} = (i_1, i_2, \dots, i_h)$. Then, for every h-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$, the matrix $A(\vec{i}, \vec{j})$ constructed with (27) yields a consistent system, which is:

$$(S(\vec{i}, \vec{j})) : A(\vec{i}, \vec{j}) \square_{\min}^{\max} x = b.$$

Therefore, the matrix $A(\vec{i}, \vec{j})$ belongs to the set $\mathcal{T}$ see (17).

For $p \in \{1, 2, \infty\}$, we have:

$$\|A(\vec{i}, \vec{j}) - A\|_p \geq \hat{\Delta}_p,$$

see (18) for the definition of $\hat{\Delta}_p$.

The following result highlights the minimality of the modifications made to obtain the matrices $A(\vec{i}, \vec{j})$ from A using (27) and an h-tuple $\vec{i}$ as in Theorem 1:

**Theorem 2.** Retain the notations from Theorem 1 and let

$$A = [a_{kl}]_{1 \le k \le n, 1 \le l \le m} \quad \text{and} \quad \vec{i} = (i_1, i_2, \dots, i_h) \quad \text{such that} \quad N_{inc} = \{i_1, i_2, \dots, i_h\}$$

Then, for every consistent system whose right-hand side vector is b:

$$T \square_{\min}^{\max} x = b, \quad \text{with } T = [t_{kl}]_{1 \le k \le n, 1 \le l \le m} \in \mathcal{T},$$

there exists an h-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$ such that the system

$$A(\vec{i}, \vec{j}) \square_{\min}^{\max} x = b$$
is consistent and, for every $(k, l) \in I \times J$,

$$|a_{kl}^{(i,j)} - a_{kl}| \le |t_{kl} - a_{kl}| \quad \text{where} \quad A^{(i,j)} = [a_{kl}^{(i,j)}]_{1 \le k \le n, 1 \le l \le m}.$$

We have:

$$\|A^{(i,j)} - A\|_p \le \|T - A\|_p \quad \text{for} \quad p \in \{1, 2, \infty\}.$$

The above theorem allows us to compute the distance $\hat{\Delta}_p$, see (18), using the finite set $J^h$ instead of $\mathcal{T}$:
**Corollary 3.** Recall that for $p \in \{1, 2, \infty\}$ we defined in (18):

$$\hat{\Delta}_p := \inf_{T \in \mathcal{T}} \|T - A\|_p.$$

Then, it follows from Theorems 1 and 2 that

$$\hat{\Delta}_p = \min_{\vec{j} \in J^h} \|A^{(\vec{i}, \vec{j})} - A\|_p. \quad (34)$$

Moreover, this minimum is independent of the particular enumeration $\{i_1, i_2, \dots, i_h\}$ of the set $N_{inc}$ chosen to define the h-tuple $\vec{i} = (i_1, i_2, \dots, i_h)$.

The proofs of Theorem 1 and 2 and Corollary 3 are given in Subsection A.4.

## 4.2 Computing the distance $\hat{\Delta}_{\infty}$ by an explicit analytical formula

In the following, using the $L_{\infty}$ norm i.e, $p = \infty$, we aim to construct a matrix $A^{(i,j)}$, see (27), such that

$$\hat{\Delta}_{\infty} = \|A^{(i,j)} - A\|_{\infty}, \quad (35)$$

where $\hat{\Delta}_{\infty}$ is defined in (18) and $A$ is the matrix of the inconsistent system (S): $A \square_{\min}^{\max} x = b$. This construction will allow us to introduce an explicit analytical formula for computing the distance $\hat{\Delta}_{\infty}$.

Our first objective is to find a pair $(\vec{i}, \vec{j})$ satisfying the equality (35). We process as follows:

* We choose an arbitrary enumeration of $N_{inc}$ as $\{i_1, i_2, \dots, i_h\}$, see (24), and set $\vec{i} = (i_1, i_2, \dots, i_h)$.

* To the h-uplet $\vec{i} := (i_1, \dots, i_h)$, we associate an h-uplet $\vec{j} = (j_1, j_2, \dots, j_h)$ whose components satisfy the following requirement: for each $\lambda \in \{1, 2, \dots, h\}$, set

$$j_{\lambda} := \operatorname{argmin}_{j \in J} \|A^{(i_{\lambda}, j)} - A\|_{\infty}, \quad \text{which means that} \quad \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} = \min_{j \in J} \|A^{(i_{\lambda}, j)} - A\|_{\infty}. \quad (36)$$

The above method allows us to introduce the following set of pairs $(\vec{i}, \vec{j})$:

$$L_{A,\infty} = \left\{ (\vec{i}, \vec{j}) \mid \begin{array}{l} \vec{i} = (i_1, \dots, i_h) \text{ is any ordering of } N_{\text{inc}}, \\ \vec{j} = (j_1, \dots, j_h) \text{ with } j_{\lambda} \in \mathcal{J}(i_{\lambda}) \text{ for each } \lambda = 1, \dots, h \end{array} \right\}, \quad (37)$$

where $\mathcal{J}: I \to 2^J: i \to \{j \in J \mid \|A^{(i,j)} - A\|_{\infty} = \min_{j' \in J} \|A^{(i,j')} - A\|_{\infty}\}$.

From Theorem 1, we know that for any $(\vec{i}, \vec{j}) \in L_{A,\infty}$, we have $A^{(\vec{i}, \vec{j})} \in \mathcal{T}$, i.e., the system $A^{(\vec{i}, \vec{j})} \square_{\min}^{\max} x = b$ is consistent and therefore $\hat{\Delta}_{\infty} \le \|A^{(\vec{i}, \vec{j})} - A\|_{\infty}$. The following theorem is the main step to compute $\hat{\Delta}_{\infty}$ by an explicit analytical formula:

**Theorem 3.** Let (S) = $A \square_{\min}^{\max} x = b$ be an inconsistent system. Then, for any $(\vec{i}, \vec{j}) \in L_{A,\infty}$ (see (37)), we have:

1. $\hat{\Delta}_{\infty} = \|A^{(\vec{i}, \vec{j})} - A\|_{\infty}$.

2. $\hat{\Delta}_{\infty} = \max_{1 \le \lambda \le h} \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty}$ where $\vec{i} = (i_1, \dots, i_h)$ and $\vec{j} = (j_1, \dots, j_h)$.

We give an explicit analytical formula for computing the distance $\hat{\Delta}_{\infty}$:
**Corollary 4.** For any system (S) : A□max<sub>min</sub>x = b, we have:

$$
\hat{\Delta}_{\infty} = \max_{i \in I} \min_{j \in J} \max \left[ (b_i - a_{ij})^{+}, \max_{k \in I, k \neq i} \left( \theta(i, k) \cdot (a_{kj} - b_k)^{+} \right) \right] \quad (38)
$$

where $\theta: I \times I \mapsto \{0,1\}: \theta(i,k) = \begin{cases} 1 & \text{if } b_i > b_k \\ 0 & \text{otherwise} \end{cases}$ and was defined in (23).

The formula (38) can be reformulated using the set $N_{\text{inc}}$, see (24):

$$
\hat{\Delta}_{\infty} = \max_{i \in N_{\text{inc}}} \min_{j \in J} \max \left[ (b_i - a_{ij})^+, \max_{k \in I, k \neq i} \left( \theta(i, k) \cdot (a_{kj} - b_k)^+ \right) \right].
$$

The formula (38) of $\hat{\Delta}_{\infty}$ is useful for estimating to which extent the system (S) is inconsistent, with respect to its matrix A. Analogously, using $\Delta$, see (11), we can measure how inconsistent the system (S) is, with respect to its right-hand side vector b. It is easy to see that we have $\Delta \le \hat{\Delta}_{\infty}$ for any max-min system (S).

**Example 5.** (continued) We reuse the inconsistent max-min system (S) : $A \Box_{\min}^{\max} x = b$ of Example 2 and the matrices of Example 3 where $J = \{1, 2, 3\}$ and:

$$
A = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix}, \quad b = \begin{bmatrix} 0.3 \\ 0.42 \\ 0.76 \end{bmatrix}.
$$

We obtained

$$
N_{\text{cons}} = \{1\}, \quad N_{\text{inc}} = \{2, 3\}.
$$

We define two vectors:

$$
\vec{i} = (i_1, i_2) = (2, 3)
$$

(from the elements of $N_{\text{inc}}$) and

$$
\vec{j} = (j_1, j_2) \in \mathcal{J}^2.
$$

Since $|J| = 3$ and the length of $\vec{i}$ is 2, there are $3^2 = 9$ possible choices for $\vec{j}$. For each such pair $(\vec{i}, \vec{j})$, we update A in two steps:

• Step $\lambda = 1$: Update using the pair $(i_1, j_1)$.

• Step $\lambda = 2$: Update using the pair $(i_2, j_2)$.

Below, we detail the nine cases.

Case 1: $\vec{j} = (1, 1)$

• $\lambda = 1$: For $(i_1, j_1) = (2, 1)$, update the (2,1)-entry from 0.33 to 0.42.

• $\lambda = 2$: For $(i_2, j_2) = (3, 1)$, update the (3,1)-entry from 0.55 to 0.76.

The final matrix is

$$
A^{(\vec{i}, \vec{j})} = \begin{bmatrix} 0.04 & 0.73 & 0.5 \\ 0.42 & 0.35 & 0.94 \\ 0.76 & 0.9 & 0.35 \end{bmatrix},
$$

and we have $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = 0.21$.

Case 2: $\vec{j} = (1, 2)$

• $\lambda = 1$: For $(2, 1)$, update the (2,1)-entry from 0.33 to 0.42.

• $\lambda = 2$: For $(3, 2)$, update (1,2)-entry from 0.73 to 0.3.

The final matrix is

$$
A^{(\vec{i}, \vec{j})} = \begin{bmatrix} 0.04 & 0.3 & 0.5 \\ 0.42 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},
$$

and we have $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = 0.43$.

Case 3: $\vec{j} = (1, 3)$
• $\lambda = 1$: For (2, 1), update the (2, 1)-entry from 0.33 to 0.42.

• $\lambda = 2$: For (3, 3), update:
the (3,3)-entry from 0.35 to 0.76, the (1,3)-entry from 0.5 to 0.3, the (2,3)-entry from 0.94 to 0.42.

The final matrix is

$$A^{(\vec{i}, \vec{j})} = \begin{bmatrix} 0.04 & 0.73 & 0.3 \\ 0.42 & 0.35 & 0.42 \\ 0.55 & 0.9 & 0.76 \end{bmatrix},$$

and we have $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = 0.52$.

Case 4: $\vec{j} = (2, 1)$

• $\lambda = 1$: For (2, 2), update:
the (2,2)-entry from 0.35 to 0.42, the (1,2)-entry from 0.73 to 0.3.

• $\lambda = 2$: For (3, 1), update the (3,1)-entry from 0.55 to 0.76.

The final matrix is

$$A^{(\vec{i}, \vec{j})} = \begin{bmatrix} 0.04 & 0.3 & 0.5 \\ 0.33 & 0.42 & 0.94 \\ 0.76 & 0.9 & 0.35 \end{bmatrix},$$

and we have $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = 0.43$.

Case 5: $\vec{j} = (2, 2)$

• $\lambda = 1$: For (2, 2), update:
the (2,2)-entry from 0.35 to 0.42, the (1,2)-entry from 0.73 to 0.3.

• $\lambda = 2$: For (3, 2), no change is made.

The final matrix is

$$A^{(\vec{i}, \vec{j})} = \begin{bmatrix} 0.04 & 0.3 & 0.5 \\ 0.33 & 0.42 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

and we have $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = 0.43$.

Case 6: $\vec{j} = (2, 3)$

• $\lambda = 1$: For (2, 2), update:
the (2,2)-entry from 0.35 to 0.42, the (1,2)-entry from 0.73 to 0.3.

• $\lambda = 2$: For (3, 3), update:
the (3,3)-entry from 0.35 to 0.76, the (1,3)-entry from 0.5 to 0.3, the (2,3)-entry from 0.94 to 0.42.

The final matrix is

$$A^{(\vec{i}, \vec{j})} = \begin{bmatrix} 0.04 & 0.3 & 0.3 \\ 0.33 & 0.42 & 0.42 \\ 0.55 & 0.9 & 0.76 \end{bmatrix},$$

and we have $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = 0.52$.

Case 7: $\vec{j} = (3, 1)$

• $\lambda = 1$: For (2, 3), update the (1,3)-entry from 0.5 to 0.3.

• $\lambda = 2$: For (3, 1), update the (3,1)-entry from 0.55 to 0.76.
The final matrix is

$$A^{(i,j)} = \begin{bmatrix} 0.04 & 0.73 & 0.3 \\ 0.33 & 0.35 & 0.94 \\ 0.76 & 0.9 & 0.35 \end{bmatrix},$$

and we have $\|A^{(i,j)} - A\|_{\infty} = 0.21$.

Case 8: $\vec{j} = (3, 2)$

• $\lambda = 1$: For (2, 3), update the (1,3)-entry from 0.5 to 0.3.

• $\lambda = 2$: For (3, 2), update (1,2)-entry from 0.73 to 0.3.

The final matrix is

$$A^{(i,j)} = \begin{bmatrix} 0.04 & 0.3 & 0.3 \\ 0.33 & 0.35 & 0.94 \\ 0.55 & 0.9 & 0.35 \end{bmatrix},$$

and we have $\|A^{(i,j)} - A\|_{\infty} = 0.43$.

Case 9: $\vec{j} = (3, 3)$

• $\lambda = 1$: For (2, 3), update the (1,3)-entry from 0.5 to 0.3.

• $\lambda = 2$: For (3, 3), update:

the (3,3)-entry from 0.35 to 0.76, the (2,3)-entry from 0.94 to 0.42.

The final matrix is

$$A^{(i,j)} = \begin{bmatrix} 0.04 & 0.73 & 0.3 \\ 0.33 & 0.35 & 0.42 \\ 0.55 & 0.9 & 0.76 \end{bmatrix},$$

and we have $\|A^{(i,j)} - A\|_{\infty} = 0.52$.

Therefore, we constructed nine consistent systems of the form $A^{(i,j)} \square_{\max} x = b$, which use the same right-hand side vector: the right-hand side vector $b$ of the original inconsistent system $A \square_{\max} x = b$.

The best vector pairs (minimizing $\|A^{(i,j)} - A\|_{\infty}$) yield a value of 0.21. In our cases, these are:

((2, 3), (1, 1)) and ((2, 3), (3, 1)).

Moreover, by choosing

$$j_{\lambda} = \underset{j \in J^{h}}{\operatorname{argmin}} \|A^{(i_{\lambda}, j)} - A\|_{\infty},$$

we obtain these vector pairs which results in the best norm $\|A^{(i,j)} - A\|_{\infty} = 0.21$.

# 5 Analogous results for a system of min-max fuzzy relational equations

In [5], we showed how to switch from a system of min-max fuzzy relational equations to a system of max-min fuzzy relational equations. This equivalence is based on the transformation $t \to 1 - t$, which allowed us to show that studying a system of max-min fuzzy relational equations is equivalent to studying a system of min-max fuzzy relational equations, see [5] for more details.

In this section, using the same notations as in [5], we begin by reminding how to solve a system of min-max fuzzy relational equations. Given an inconsistent system of min-max fuzzy relational equations, we study how to obtain consistent min-max systems close to the inconsistent system by minimally modifying the matrix of the inconsistent system. We introduce new tools for a system of min-max fuzzy relational equations corresponding to those already introduced for a system of max-min fuzzy relational equations and we show their correspondences in Table 1.
## 5.1 Solving systems of min-max fuzzy relational equations

Let us use:

**Notation 4.**

* To any matrix $A = [a_{ij}]$, we associate the matrix $A^\circ := [a_{ij}^\circ]$ where $a_{ij}^\circ := 1 - a_{ij}$. Clearly, we have $(A^\circ)^\circ = A$.

* The min-max matrix product $\Box_{\max}^{\min}$ uses the function max as the product and the function min as the addition and for any matrices A and B of size $(n, p)$ and $(p, m)$ respectively, we have:

$$ (A \Box_{\min}^{\max} B)^{\circ} = A^{\circ} \Box_{\max}^{\min} B^{\circ}. \qquad (39) $$

* The max-$\epsilon$ matrix product $\Box_{\epsilon}^{\max}$ uses the $\epsilon$-product defined by:

$$ x \epsilon y = \begin{cases} y & \text{if } x < y \\ 0 & \text{if } x \ge y \end{cases} \quad \text{in } [0, 1]. $$

as the product and the function max as the addition.

Let us use the following system of min-max fuzzy relational equations:

$$ G \Box_{\max}^{\min} x = d \qquad (40) $$

where

$$ G = [g_{ij}]_{1 \le i \le n, 1 \le j \le m} \in [0, 1]^{n \times m}, \quad d = [d_i]_{1 \le i \le n}, \quad \text{and} \quad x = [x_j]_{1 \le j \le m} \in [0, 1]^m \text{ is the unknown vector.} $$

To check if the min-max system $G \Box_{\max}^{\min} x = d$ is consistent, we compute the following vector:

$$ r = G^t \Box_{\epsilon}^{\max} d, \qquad (41) $$

where $G^t$ is the transpose of G and we use the max-$\epsilon$ matrix product $\Box_{\epsilon}^{\max}$ (Notation 4). The vector $r$ is the potential lowest solution of the system $G \Box_{\max}^{\min} x = d$.

Sanchez's result [29] ((reminded in (4)) for solving of a system max-min fuzzy relational equations becomes the following one for solving a system of min-max fuzzy relational equations:

$$ \text{The system } G \Box_{\max}^{\min} x = d \text{ is consistent} \iff G \Box_{\max}^{\min} r = d. \qquad (42) $$

The structure of the solution set of a system of min-max fuzzy relational equations is as follows. If the system $G \Box_{\max}^{\min} x = d$ is consistent, the vector $r = G^t \Box_{\epsilon}^{\max} d$ is the lowest solution of the system, and the system has a finite number of maximal solutions.

To handle the inconsistency of a min-max system, the author of [5] studied the Chebyshev distance associated with the right-hand side vector $d$ of the system $G \Box_{\max}^{\min} x = d$:

$$ \nabla = \nabla(G, d) = \min_{w \in W} \|d - w\|_{\infty} \text{ where } W = \{w \in [0, 1]^{n \times 1} \mid \text{the system } G \Box_{\max}^{\min} x = w \text{ is consistent}\}. \qquad (43) $$

[5] computes by an explicit analytical formula the Chebyshev distance $\nabla$:

$$ \nabla = \max_{1 \le i \le n} \nabla_i^G \qquad (44) $$

where for $i = 1, 2, \dots, n$:

$$ \nabla_i^G = \min_{1 \le j \le m} \max[(g_{ij} - d_i)^+, \max_{1 \le k \le n} \sigma_{\epsilon}(d_i, g_{kj}, d_k)] \qquad (45) $$

and

$$ \sigma_{\epsilon}(u, v, w) = \min\left(\frac{(w-u)^+}{2}, (w-v)^+\right) = \sigma_G(u^{\circ}, v^{\circ}, w^{\circ}). \qquad (46) $$

where $x^\circ := 1 - x$ for any $x \in [0, 1]$ and the function $\sigma_G$ is defined in (6).

Similarly to the case of an inconsistent max-min system, the author of [5] studies how to obtain approximate solutions of an inconsistent min-max system $G \Box_{\max}^{\min} x = d$ and Chebyshev approximations of the right-hand side vector $d$ of this system.
## 5.2 Constructing consistent systems by minimally modifying the matrix of an inconsistent min-max system

In this section, we study how to minimally modify the matrix $G$ of size $(n, m)$ of an inconsistent min-max system $G \square_{\max}^{\min} x = d$, see (40), in order to obtain a consistent min-max system, while keeping the right-hand side vector $d$ unchanged. This study is analogous to that carried out for a max-min system $A \square_{\max}^{\min} x = b$, see Section 3 and Section 4.

Table 1 summarizes the main tools introduced for a max-min system $A \square_{\max}^{\min} x = b$ and those for a min-max system $G \square_{\min}^{\max} x = d$, introduced in what follows. In the case where $G := A^{\circ}$ and $d := b^{\circ}$ (Notation 4), we establish explicit correspondences between the tools of these systems. The rest of this section introduces the tools for a min-max system $G \square_{\min}^{\max} x = d$ and we justify the correspondences with the tools for a max-min system.

<table><caption>Table 1: Tools of the systems $A \square_{\min}^{\max} x = b$ and $G \square_{\max}^{\min} x = d$ and their relations iff $G = A^{\circ}$ and $d = b^{\circ}$.</caption><thead><tr><th></th><th>System: $A \square_{\min}^{\max} x = b$</th><th>System: $G \square_{\max}^{\min} x = d$</th><th>Relation<br>iff $G = A^{\circ}$ and $d = b^{\circ}$</th></tr></thead><tbody><tr><td>Potential greatest/lowest<br>solution</td><td>$e = A^t \square_{\to G}^{\min} b$<br>(greatest solution)</td><td>$r = G^t \square_{\epsilon}^{\max} d$<br>(lowest solution)</td><td>$r = e^{\circ}$</td></tr><tr><td>Chebyshev distance<br>associated with<br>the right-hand side vector</td><td>$\Delta = \Delta(A, b) = \max_{1 \le i \le n} \delta_i^A$</td><td>$\nabla = \nabla(G, d) = \max_{1 \le i \le n} \nabla_i^G$</td><td>$\nabla(G, d) = \Delta(A, b)$</td></tr><tr><td>Subsets of equation indexes</td><td>$N_{\text{cons}}$ and $N_{\text{inc}}$</td><td>$M_{\text{cons}}$ and $M_{\text{inc}}$</td><td>$M_{\text{cons}} = N_{\text{cons}}$<br>$M_{\text{inc}} = N_{\text{inc}}$</td></tr><tr><td>Set of matrices<br>of consistent systems<br>with fixed right-hand side vector</td><td>$\mathcal{T}$</td><td>$\mathcal{Q}$</td><td>$\mathcal{Q} = \mathcal{T}^{\circ}$</td></tr><tr><td>Distance associated with<br>the matrix of the system</td><td>$\hat{\Delta}_p$</td><td>$\hat{\nabla}_p$</td><td>$\hat{\Delta}_p = \hat{\nabla}_p$</td></tr><tr><td>Auxiliary matrices</td><td>$A^{(i,j)}$</td><td>$G^{(i,j)}$</td><td>$G^{(i,j)} = [A^{(i,j)}]^{\circ}$</td></tr><tr><td>Modified matrices</td><td>$A^{(\tilde{i}, \tilde{j})}$</td><td>$G^{(\tilde{i}, \tilde{j})}$</td><td>$G^{(\tilde{i}, \tilde{j})} = [A^{(\tilde{i}, \tilde{j})}]^{\circ}$</td></tr><tr><td>Set of best pairs of vectors<br>(associated with $L_{\infty}$ norm)</td><td>$L_{A, \infty}$</td><td>$P_{G, \infty}$</td><td>$P_{G, \infty} = L_{A, \infty}$</td></tr></tbody></table>

We introduce the following set, which is formed by the matrices of size $(n, m)$ governing the consistent min-max systems which use the same right-hand side vector: the right-hand side vector $d$ of the min-max system $G \square_{\max}^{\min} x = d$:

$$ \mathcal{Q} := \{Q \in [0, 1]^{n \times m} \mid \text{the system } Q \square_{\max}^{\min} x = d \text{ is consistent.} \} \quad (47) $$

For each $p \in \{1, 2, \infty\}$, we define the distance from the matrix $G$ to the set $\mathcal{Q}$ as:

$$ \hat{\nabla}_p := \inf_{Q \in \mathcal{Q}} \|Q - G\|_p. \quad (48) $$

Here, $\| \cdot \|_p$ denotes the matrix norm with exponent $p$. The set $\mathcal{Q}$ and the distance $\hat{\nabla}_p$ are defined for the min-max system $G \square_{\max}^{\min} x = d$ analogously to the set $\mathcal{T}$ and the distance $\hat{\Delta}_p$ for the max-min system $A \square_{\min}^{\max} x = b$, see (17) and (18).

We rely on the max-min system $A \square_{\min}^{\max} x = b$ equivalent to the min-max system $G \square_{\max}^{\min} x = d$ in the following sense:

**Definition 7.** To the min-max system $G \square_{\max}^{\min} x = d$, see (40), we associate the following max-min system:

$$ A \square_{\min}^{\max} x = b \quad \text{where} \quad A := G^{\circ} \quad \text{and} \quad b := d^{\circ}. \quad (49) $$

We notice that we have $\|A - B\|_p = \|A^{\circ} - B^{\circ}\|_p$ for any matrices $A$ and $B$ of size $(n, m)$ (see Notation 4). Therefore, we easily deduce from (39) and Lemma 2 that:

**Lemma 7.** Set $A := G^{\circ}$ and $b := d^{\circ}$, then we have:

1. $\mathcal{Q} = \mathcal{T}^{\circ}$ where $\mathcal{T}^{\circ} := \{T^{\circ} \mid T \in \mathcal{T}\}$, see (17) and (47).

2. $\hat{\nabla}_p = \hat{\Delta}_p = \min_{Q \in \mathcal{Q}} \|Q - G\|_p$, see (18) and (48).
□

We reuse the sets of indices $I = \{1, 2, \dots, n\}$ and $J = \{1, 2, \dots, m\}$ to put some notations:

**Notation 5.** For all $(i, j) \in I \times J$, using the matrix $G$ and the right-hand side vector $d$ of the system $G \square_{\max}^{\min} x = d$ we put:

$$V_{ij}^{G} := \{k \in I \mid \sigma_{\epsilon}(d_{i}, g_{kj}, d_{k}) > 0\}, \qquad (50)$$

where $\sigma_{\epsilon}$ is defined in (46). Thus, we have:

$$V_{ij}^{G} = U_{ij}^{A} \qquad (51)$$

where $U_{ij}^{A}$ is the set associated with the max-min system (49) as in (22).

From the formula for computing the Chebyshev distance $\nabla$ associated with the right-hand side vector $d$ of the system $G \square_{\max}^{\min} x = d$, see (44), we set:

$$M_{\text{cons}} := \{i \in I \mid \nabla_i = 0\} \quad \text{and} \quad M_{\text{inc}} := \{i \in I \mid \nabla_i > 0\} \quad \text{and} \quad h := \text{card}(M_{\text{inc}}). \qquad (52)$$

Thus, we have:

$$M_{\text{cons}} = N_{\text{cons}} \quad \text{and} \quad M_{\text{inc}} = N_{\text{inc}} \qquad (53)$$

where $N_{\text{cons}}$ and $N_{\text{inc}}$ are the sets associated with the max-min system (49) as in (24).

For any pair $(i, j) \in I \times J$, we define an auxiliary matrix $G^{(i,j)}$ using the set $V_{ij}^{G}$:

**Definition 8.** For any pair $(i, j) \in I \times J$, we construct an auxiliary matrix $G^{(i,j)} = [g_{kl}^{(i,j)}]_{1 \le k \le n, 1 \le l \le m}$ by:

$$g_{ij}^{(i,j)} = \begin{cases} d_i & \text{if } d_i < g_{ij} \\ g_{ij} & \text{if } d_i \ge g_{ij} \end{cases} \quad \text{and for} \quad \forall k \in I \setminus \{i\}, \quad g_{kj}^{(i,j)} = \begin{cases} d_k & \text{if } k \in V_{ij}^{G} \\ g_{kj} & \text{if } k \notin V_{ij}^{G} \end{cases}. \qquad (54a)$$

$$\forall k \in I \forall l \in J \setminus \{j\}, \quad g_{kl}^{(i,j)} = g_{kl}. \qquad (54b)$$

The above definitions of the coefficients of the auxiliary matrix $G^{(i,j)}$ correspond to the definitions (25a) and (25b) of the coefficients of the auxiliary matrix $A^{(i,j)}$ associated with the max-min system $A \square_{\min}^{\max} x = b$ (49):

$$\text{for all } (i, j) \in I \times J, \text{ we have} \quad G^{(i,j)} = [A^{(i,j)}]^{\circ}. \qquad (55)$$

We generalize the construction of auxiliary matrices $G^{(i,j)}$ associated with pairs $(i, j) \in I \times J$ to pairs of index uplets $(\vec{i}, \vec{j}) \in I^h \times J^h$ where $1 \le h \le n$:

**Definition 9.** For any $h$-tuple $\vec{i} = (i_1, i_2, \dots, i_h)$ of two-by-two distinct indices of the set $I$ and an $h$-tuple $\vec{j} = (j_1, j_2, \dots, j_h)$ of indices of the set $J$, we associate the matrix denoted $G^{(\vec{i}, \vec{j})}$ which is constructed by successively applying the modifications indicated by the pairs $(i_1, j_1), (i_2, j_2), \dots, (i_h, j_h)$, as follows:

$$G^{(\vec{i}, \vec{j})} = \begin{cases} G^{(i_1, j_1)} & \text{if } h = 1, \\ Y^{(i_h, j_h)} & \text{if } h > 1 \text{ and } Y := G^{(i_1, j_1) * (i_2, j_2) * \dots * (i_{h-1}, j_{h-1})}. \end{cases} \qquad (56)$$

This construction can also be written as

$$G^{(\vec{i}, \vec{j})} = (((G^{(i_1, j_1)})(i_2, j_2))(i_3, j_3) \dots)(i_h, j_h).$$

By induction on $h$, we easily generalize (55):

$$G^{(\vec{i}, \vec{j})} = [A^{(\vec{i}, \vec{j})}]^{\circ} \qquad (57)$$

where $A^{(\vec{i}, \vec{j})}$ is introduced in Definition 6.

We give a simpler construction of the matrices $G^{(\vec{i}, \vec{j})}$. For any $h$-tuple $\vec{i} = (i_1, i_2, \dots, i_h)$ of two-by-two distinct indices of the set $I$ and an $h$-tuple $\vec{j} = (j_1, j_2, \dots, j_h)$ of indices of the set $J$, using the sets $V_{ij}^{G}$ defined in (50), we construct the following sets:

$$\mathcal{F}_1 := \{(i_\lambda, j_\lambda) \in I \times J \mid \lambda \in \{1, \dots, h\} \text{ and } g_{i_\lambda j_\lambda} > d_{i_\lambda}\}, \qquad (58a)$$

$$\mathcal{F}_2 := \bigcup_{\lambda=1}^{h} \{(k, j_{\lambda}) \mid k \in V_{i_{\lambda}j_{\lambda}}^{G}\} \subseteq I \times J, \qquad (58b)$$

$$\mathcal{F} := \mathcal{F}_1 \cup \mathcal{F}_2 \subseteq I \times J. \qquad (58c)$$
Using the equalities $V_{ij}^G = U_{ij}^A$ for all $(i, j) \in I \times J$, see (51), we deduce:

$$ \mathcal{F}_1 = \mathcal{E}_1, \quad \mathcal{F}_2 = \mathcal{E}_2 \quad \text{and} \quad \mathcal{F} = \mathcal{E} \qquad (59) $$

where the sets $\mathcal{E}_1, \mathcal{E}_2$ and $\mathcal{E}$, see (31), are associated with the max-min system $A \square_{\min}^{\max} x = b$ equivalent to the min-max $G \square_{\max}^{\min} x = d$ (see Definition 7). Thus, using (57) and Proposition 5, we easily get:

**Proposition 6.** For any h-tuple $\vec{i} = (i_1, i_2, \dots, i_h)$ of two-by-two distinct indices of the set I and an h-tuple $\vec{j} = (j_1, j_2, \dots, j_h)$ of indices of the set J, we have:

$$ \forall (k, l) \in I \times J, \quad g_{kl}^{(\vec{i}, \vec{j})} = \begin{cases} d_k & \text{if } (k, l) \in \mathcal{F} \\ g_{kl} & \text{if } (k, l) \notin \mathcal{F}. \end{cases} \qquad (60) $$

□

Using the max-min system $A \square_{\min}^{\max} x = b$ equivalent to the min-max system $G \square_{\max}^{\min} x = d$ (see Definition 7), we deduce the main results for the min-max system $G \square_{\min}^{\max} x = d$:

**Theorem 4.** We use the set $M_{inc}$ where $h := \text{card}(M_{inc})$, see (52). Choose an arbitrary enumeration of $M_{inc}$ as $\{i_1, i_2, \dots, i_h\}$ and set $\vec{i} = (i_1, i_2, \dots, i_h)$. Then, for every h-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$, the matrix $G^{(\vec{i}, \vec{j})}$ constructed with (56) yields a consistent system, which is:

$$ G^{(\vec{i}, \vec{j})} \square_{\max}^{\min} x = d. $$

Therefore, the matrix $G^{(\vec{i}, \vec{j})}$ belongs to the set $\mathcal{Q}$, see (47), i.e., $G^{(\vec{i}, \vec{j})} \in \mathcal{Q}$. For $p \in \{1, 2, \infty\}$, we have:

$$ \|G^{(\vec{i}, \vec{j})} - G\|_p \geq \nabla_p, $$

see (48) for the definition of $\nabla_p$.

The proof relies on (53), (57) and Theorem 1.

□

The following result highlights the minimality of the modifications made to obtain the matrices $G^{(\vec{i}, \vec{j})}$ from G using (56) and an h-tuple $\vec{i}$ as in Theorem 4:

**Theorem 5.** Retain the notations from Theorem 4 and let

$$ G = [g_{kl}]_{1 \le k \le n, 1 \le l \le m} \quad \text{and} \quad \vec{i} = (i_1, i_2, \dots, i_h) \quad \text{such that} \quad M_{inc} = \{i_1, i_2, \dots, i_h\}. $$

Then, for every consistent min-max system whose right-hand side vector is d:

$$ T' \square_{\max}^{\min} x = d, \quad \text{with} \quad T' = [t'_{kl}]_{1 \le k \le n, 1 \le l \le m} \in \mathcal{Q}, $$

there exists an h-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$ such that the system

$$ G^{(\vec{i}, \vec{j})} \square_{\max}^{\min} x = d $$

is consistent and, for every $(k, l) \in I \times J$,

$$ |g_{kl}^{(\vec{i}, \vec{j})} - g_{kl}| \le |t'_{kl} - g_{kl}| \quad \text{where} \quad G^{(\vec{i}, \vec{j})} = [g_{kl}^{(\vec{i}, \vec{j})}]_{1 \le k \le n, 1 \le l \le m}. $$

We have:

$$ \|G^{(\vec{i}, \vec{j})} - G\|_p \le \|T' - G\|_p \quad \text{for} \quad p \in \{1, 2, \infty\}. $$

The proof relies on (53), (57) and Theorem 2.

□

The above theorem allows us to compute the distance $\nabla_p$, see (48), using the finite set $J^h$ instead of $\mathcal{Q}$:

**Corollary 5.** Recall that for $p \in \{1, 2, \infty\}$ we defined in (48):

$$ \nabla_p := \inf_{Q \in \mathcal{Q}} \|Q - G\|_p. $$

Then, it follows from Theorems 4 and 5 that

$$ \nabla_p = \min_{\vec{j} \in J^h} \|G^{(\vec{i}, \vec{j})} - G\|_p. \qquad (61) $$

Moreover, this minimum is independent of the particular enumeration $\{i_1, i_2, \dots, i_h\}$ of the set $M_{inc}$ chosen to define the h-tuple $\vec{i} = (i_1, i_2, \dots, i_h)$.
□

In the rest of this section, using the $L_\infty$ norm i.e, $p = \infty$, we introduce a method for constructing a matrix $G(\vec{i}, \vec{j})$, see (56), such that

$$ \hat{\nabla}_{\infty} = \|G(\vec{i}, \vec{j}) - G\|_{\infty}, \qquad (62) $$

This construction will allow us to introduce an explicit analytical formula (Corollary 6) for computing the distance $\hat{\nabla}_{\infty}$, see (48).

We rely on the max-min system $A\Box_{\min}^{\max}x = b$ equivalent to the min-max $G\Box_{\min}^{\max}x = d$ (see Definition 7). We note that we have $\hat{\nabla}_{\infty} = \hat{\Delta}_{\infty}$ where $\hat{\Delta}_{\infty}$ is the distance associated with the system $A\Box_{\min}^{\max}x = b$, see (18).

To find a pair $(\vec{i}, \vec{j})$ satisfying the equality (62), we process as follows:

* We choose an arbitrary enumeration of $M_{\text{inc}}$ as $\{i_1, i_2, \dots, i_h\}$, see (52), and set $\vec{i} = (i_1, i_2, \dots, i_h)$.

* To the h-uplet $\vec{i} := (i_1, \dots, i_h)$, we associate an h-uplet $\vec{j} = (j_1, j_2, \dots, j_h)$ whose components satisfy the following requirement: for each $\lambda \in \{1, 2, \dots, h\}$, set

$$ j_{\lambda} := \operatorname{argmin}_{j \in J} \|G^{(i_{\lambda}, j)} - G\|_{\infty}, \quad \text{which means that} \quad \|G^{(i_{\lambda}, j_{\lambda})} - G\|_{\infty} = \min_{j \in J} \|G^{(i_{\lambda}, j)} - G\|_{\infty}. \qquad (63) $$

The above method allows us to introduce the following set of pairs $(\vec{i}, \vec{j})$:

$$ P_{G,\infty} = \left\{ (\vec{i}, \vec{j}) \mid \begin{array}{l} \vec{i} = (i_1, \dots, i_h) \text{ is any ordering of } M_{\text{inc}}, \\ \vec{j} = (j_1, \dots, j_h) \text{ with } j_{\lambda} \in \mathcal{J}'(i_{\lambda}) \text{ for each } \lambda = 1, \dots, h \end{array} \right\}, \qquad (64) $$

where $\mathcal{J}' : I \to 2^J : i \to \{j \in J \mid \|G^{(i,j)} - G\|_{\infty} = \min_{j' \in J} \|G^{(i,j')} - G\|_{\infty}\}$.

From (53) and (55), we easily deduce the equality $P_{G,\infty} = L_{A,\infty}$ where $L_{A,\infty}$ is defined in (37).

From Theorem 4, we know that for any $(\vec{i}, \vec{j}) \in P_{G,\infty}$, we have $G(\vec{i}, \vec{j}) \in \mathcal{Q}$, i.e., the system $G(\vec{i}, \vec{j})\Box_{\min}^{\max}x = d$ is consistent and therefore $\hat{\nabla}_{\infty} \le \|G(\vec{i}, \vec{j}) - G\|_{\infty}$. We easily deduce from the second statement of Lemma 7, (57) and Theorem 3, the following theorem which is the main step to compute $\hat{\nabla}_{\infty}$ by an explicit analytical formula:

**Theorem 6.** Let $G\Box_{\min}^{\max}x = d$ be an inconsistent system. Then, for any $(\vec{i}, \vec{j}) \in P_{G,\infty}$, we have:

$$ 1. \quad \hat{\nabla}_{\infty} = \|G(\vec{i}, \vec{j}) - G\|_{\infty}. $$

$$ 2. \quad \hat{\nabla}_{\infty} = \max_{1 \le \lambda \le h} \|G^{(i_{\lambda}, j_{\lambda})} - G\|_{\infty} \text{ where } \vec{i} = (i_1, \dots, i_h) \text{ and } \vec{j} = (j_1, \dots, j_h). $$

□

We give an explicit analytical formula for computing the distance $\hat{\nabla}_{\infty}$ using Corollary 4:

**Corollary 6.** For any system $G\Box_{\min}^{\max}x = d$, we have:

$$ \hat{\nabla}_{\infty} = \max_{i \in I} \min_{j \in J} \max \left[ (g_{ij} - d_i)^{+}, \max_{k \in I, k \neq i} \left( \theta'(i, k) \cdot (d_k - g_{kj})^{+} \right) \right] \qquad (65) $$

$$ \text{where } \theta' : I \times I \mapsto \{0, 1\} : \theta'(i, k) = \begin{cases} 1 & \text{if } d_i < d_k \\ 0 & \text{otherwise.} \end{cases} $$

The formula (65) can be reformulated using the set $M_{\text{inc}}$, see (52):

$$ \hat{\nabla}_{\infty} = \max_{i \in M_{\text{inc}}} \min_{j \in J} \max \left[ (g_{ij} - d_i)^{+}, \max_{k \in I, k \neq i} \left( \theta'(i, k) \cdot (d_k - g_{kj})^{+} \right) \right]. $$

□

The distance $\hat{\nabla}_{\infty}$ is useful for estimating to which extent the min-max system $G\Box_{\min}^{\max}x = d$ is inconsistent, with respect to its matrix $G$. Analogously, using $\nabla$, see (44), we can measure how inconsistent the min-max system $G\Box_{\min}^{\max}x = d$ is with respect to its right-hand side vector $d$. It is easy to see that we have $\nabla \le \hat{\nabla}_{\infty}$ for the min-max system $G\Box_{\min}^{\max}x = d$.
# 6 Conclusion

In this article, we handled the inconsistency of a system of max-min fuzzy relational equations by modifying the matrix governing the system. Our main results (Theorem 1 and Theorem 2) allows us to obtain consistent systems that closely 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. The solutions of the obtained consistent systems can be considered as approximate solutions of the inconsistent system. We studied the distance $\Delta_p$ (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, see (18). We showed in Theorem 3 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, see Corollary 3). We also give an explicit analytical formula for computing $\Delta_\infty$, see Corollary 4. Finally, we translated our results for min-max systems.

This work may be useful for solving inconsistency issues in max-min systems involved in max-min learning methods, such as learning the rule parameters of possibilistic rule-based systems [2], learning associate memories [32], or learning capacities of Sugeno integrals according to training data [3]. It can also be useful for applications based on max-min systems, e.g. spatial analysis [12], diagnostic problems [16].
## References

[1] K.-P. Adlassnig. A fuzzy logical model of computer-assisted medical diagnosis. *Methods of Information in Medicine*, 19:141–148, 1980. ISSN 0026-1270.

[2] I. Baaj. Learning rule parameters of possibilistic rule-based system. In *2022 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)*, pages 1–8. IEEE, 2022.

[3] I. Baaj. On learning capacities of Sugeno integrals with systems of fuzzy relational equations. *arXiv e-prints*, art. arXiv:2408.07768, Aug. 2024.

[4] I. Baaj. On the handling of inconsistent systems based on max-product and max-lukasiewicz compositions. *Fuzzy Sets and Systems*, page 109142, 2024. ISSN 0165-0114.

[5] I. Baaj. On the handling of inconsistent systems of max-min fuzzy relational equations. *Fuzzy sets and systems*, 482:108912, 2024. ISSN 0165-0114.

[6] W. Bandler and L. J. Kohout. Semantics of implication operators and fuzzy relational products. *International Journal of Man-Machine Studies*, 12(1):89–116, 1980. ISSN 0020-7373.

[7] W. Bandler and L. J. Kohout. *A Survey of Fuzzy Relational Products in Their Applicability to Medicine and Clinical Psychology*, pages 107–118. Abacus Books. Gordon and Breach, London, 1986. ISBN 9780856264429.

[8] K. Cechlárová. A note on unsolvable systems of max–min (fuzzy) equations. *Linear Algebra and its Applications*, 310(1):123–128, 2000. ISSN 0024-3795.

[9] R. Cimler, M. Gavalec, and K. Zimmermann. An optimization problem on the image set of a (max, min) fuzzy operator. *Fuzzy Sets and Systems*, 341:113–122, 2018. ISSN 0165-0114.

[10] R. A. Cuninghame-Green and K. Cechlárová. Residuation in fuzzy algebra and some applications. *Fuzzy Sets and Systems*, 71(2):227–239, 1995. ISSN 0165-0114.

[11] B. De Baets. *Analytical Solution Methods for Fuzzy Relational Equations*, pages 291–340. Springer US, Boston, MA, 2000. ISBN 978-1-4615-4429-6.

[12] F. Di Martino and S. Sessa. Spatial analysis and fuzzy relation equations. *Advances in Fuzzy Systems*, 2011:6–6, 2011.

[13] A. Di Nola, W. Pedrycz, and S. Sessa. On solution of fuzzy relational equations and their characterization. *Busefal*, 12:60–71, 1982.

[14] A. Di Nola, W. Pedrycz, S. Sessa, and W. P. Zhuang. Fuzzy relation equation under a class of triangular norms: A survey and new results. *Stochastica*, 8(2):99–145, 1984. ISSN 0210-2930.

[15] A. Di Nola, W. Pedrycz, S. Sessa, and E. Sanchez. Fuzzy relation equations theory as a basis of fuzzy modelling: An overview. *Fuzzy sets and systems*, 40(3):415–429, 1991. ISSN 0165-0114.

[16] D. Dubois and H. Prade. Fuzzy relation equations and causal reasoning. *Fuzzy sets and systems*, 75(2):119–134, 1995. ISSN 0165-0114.

[17] P. Li. *Fuzzy Relational Equations: Resolution and Optimization*. PhD thesis, North Carolina State University, 2009.

[18] P. Li. Linear optimization over the approximate solutions of a system of max-min equations. *Fuzzy Sets and Systems*, 484:108946, 2024. ISSN 0165-0114.

[19] P. Li and S.-C. Fang. On the resolution and optimization of a system of fuzzy relational equations with sup-t composition. *Fuzzy Optimization and Decision Making*, 7(2):169–214, 2008.

[20] P. Li and S.-C. Fang. Chebyshev approximation of inconsistent fuzzy relational equations with max-t composition. In *Fuzzy Optimization*, pages 109–124. Springer, 2010.

[21] A. Markovskii. On the relation between equations with max-product composition and the covering problem. *Fuzzy Sets and Systems*, 153(2):261–273, 2005.

[22] Z. Matusiewicz and J. Drewniak. Increasing continuous operations in fuzzy max-* equations and inequalities. *Fuzzy Sets and Systems*, 232:120–133, 2013.

[23] M. Miyakoshi and M. Shimbo. Solutions of composite fuzzy relational equations with triangular norms. *Fuzzy Sets and Systems*, 16(1):53–63, 1985. ISSN 0165-0114.

[24] W. Pedrycz. Fuzzy relational equations with triangular norms and their resolutions. *Busefal*, 11:24–32, 1982.

[25] W. Pedrycz. Applications of fuzzy relational equations for methods of reasoning in presence of fuzzy data. *Fuzzy sets and systems*, 16(2):163–175, 1985.
[26] W. Pedrycz. Inverse problem in fuzzy relational equations. *Fuzzy Sets and Systems*, 36(2):277–291, 1990.

[27] I. Perfilieva and L. Nosková. System of fuzzy relation equations with inf-→ composition: Complete set of solutions. *Fuzzy Sets and Systems*, 159(17):2256–2271, 2008.

[28] B. E. Sagan. *The symmetric group: representations, combinatorial algorithms, and symmetric functions*, volume 203. Springer Science & Business Media, 2013. Chapter 1, page 4.

[29] E. Sanchez. Resolution of composite fuzzy relation equations. *Information and control*, 30(1):38–48, 1976.

[30] E. Sanchez. Solutions in composite fuzzy relation equations: Application to medical diagnosis in brouwerian logic. In *Readings in Fuzzy Sets for Intelligent Systems*, pages 159–165. Morgan Kaufmann, 1993. ISBN 978-1-4832-1450-4.

[31] B.-S. Shieh. Solutions of fuzzy relation equations based on continuous t-norms. *Information Sciences*, 177(19):4208–4215, 2007.

[32] P. Sussner and M. E. Valle. Implicative fuzzy associative memories. *IEEE Transactions on Fuzzy Systems*, 14(6):793–807, 2006.

[33] C.-F. Wen, Y.-K. Wu, and Z. Li. Algebraic formulae for solving systems of max-min inverse fuzzy relational equations. *Information Sciences*, 622:1162–1183, 2023. ISSN 0020-0255.

[34] Y.-K. Wu, Y.-Y. Lur, C.-F. Wen, and S.-J. Lee. Analytical method for solving max-min inverse fuzzy relation. *Fuzzy Sets and Systems*, 440:21–41, 2022. ISSN 0165-0114.

[35] L. A. Zadeh. A theory of approximate reasoning. *Machine intelligence*, 9:149–194, 1979.
# A Proofs

## A.1 Proof of the result in Section 3

**Lemma 2.** The formula (18) can be rewritten as:

$$ \hat{\Delta}_p = \min_{T \in \mathcal{T}} \|T - A\|_p. $$

*Proof.* By applying (11) and (12) to any matrix $T$, we deduce the equality:

$$ \mathcal{T} = \{T \in [0, 1]^{n \times m} \mid \text{for all } i \in \{1, 2, \dots, n\} \text{ we have } \delta_i^T = 0\}. $$

Using Lemma 1, we conclude that $\mathcal{T}$ is a non-empty closed subset of $[0, 1]^{n \times m}$. Since $[0, 1]^{n \times m}$ is compact and the norm $\| \cdot \|_p$ is continuous, the function $T \mapsto \|T - A\|_p$ attains its minimum on $\mathcal{T}$. Therefore,

$$ \hat{\Delta}_p = \min_{T \in \mathcal{T}} \|T - A\|_p. $$

□

## A.2 Proof of the results in Section 3.1

**Lemma 3.** Let $(i, j) \in I \times J$ be a fixed pair of indices. Then, we have:

$$ 1. \delta^{A^{(i,j)}}(i, j) = 0. $$

2. For all $1 \le s \le n$, we have:

$$ \delta^A(s, j) = 0 \implies \delta^{A^{(i,j)}}(s, j) = 0. $$

3. For all $1 \le s \le n$ and $1 \le l \ne j \le m$, we have:

$$ \delta^{A^{(i,j)}}(s, l) = \delta^A(s, l). $$

$$ 4. \|A^{(i,j)} - A\|_{\infty} = \max[(b_i - a_{ij})^+, \max_{k \in I, k \ne i} (\theta(i, k) \cdot (a_{kj} - b_k)^+)] $$

where the function $\theta$ is defined in (23).

*Proof.* Let $A^{(i,j)} = [a_{kl}^{(i,j)}]$. We remind that:

$$ \delta^{A^{(i,j)}}(s, l) = \max[(b_s - a_{sl}^{(i,j)})^+, \max_{1 \le k \le n} \sigma_G (b_s, a_{kl}^{(i,j)}, b_k)] $$

and for every $k$ we have $a_{kj}^{(i,j)} \in \{b_k, a_{kj}\}$, see (26).

1. First, we show that $b_i \le a_{ij}^{(i,j)}$. This inequality clearly follows from

$$ a_{ij}^{(i,j)} = \begin{cases} b_i & \text{if } b_i > a_{ij} \\ a_{ij} & \text{if } b_i \le a_{ij} \end{cases}, $$

see (25a). Moreover, for every $k$ we have:

$$ \sigma_G(b_i, a_{kj}^{(i,j)}, b_k) = 0. $$

This is evident (6) for $k = i$. For $k \ne i$, by (25a), we have:

$$ a_{kj}^{(i,j)} = \begin{cases} b_k & \text{if } k \in U_{ij}^A \\ a_{kj} & \text{if } k \notin U_{ij}^A \end{cases}. $$

If $k \in U_{ij}^A$ then

$$ \sigma_G(b_i, a_{kj}^{(i,j)}, b_k) = \sigma_G(b_i, b_k, b_k) = 0. $$
and if $k \notin U_{ij}^A$ then

$$ \sigma_G(b_i, a_{kj}^{(i,j)}, b_k) = \sigma_G(b_i, a_{kj}, b_k), $$

and by the definition (22) of $U_{ij}^A$ we have

$$ \sigma_G(b_i, a_{kj}, b_k) = 0. $$

$$ \text{Thus, } \delta^{A^{(i,j)}}(i, j) = 0. $$

2. Next, suppose that for $1 \le s \le n$ we have:

$$ \delta^A(s, j) := \max[(b_s - a_{sj})^+, \max_{1 \le k \le n} \sigma_G(b_s, a_{kj}, b_k)] = 0. $$

We show that $\delta^{A^{(i,j)}}(s, j) = 0$. We may assume that $s \neq i$.

As we have $b_s \le a_{sj}$ and $\sigma_G(b_s, a_{kj}, b_k) = 0$ for all $k \in I$, to establish the inequality $b_s \le a_{sj}^{(i,j)}$ and that we have $\sigma_G(b_s, a_{kj}^{(i,j)}, b_k) = 0$ for all $k \in I$, it suffices to use (6) and note that $a_{kj}^{(i,j)} \in \{b_k, a_{kj}\}$, see (26).

3. By (25b), for every $l \neq j$, we have $a_{kl}^{(i,j)} = a_{kl}$ for all $k \in I$. Thus by definition (8), we have:

$$ \delta^{A^{(i,j)}}(s, l) = \delta^A(s, l). $$

4. This equality is a consequence of the definition of the coefficients of the matrix $A^{(i,j)}$, see (25a) and (25b), and of the following relationship based on (23):

$$ \max_{k \in I, k \neq i} \theta(i, k) \cdot (a_{kj} - b_k)^+ = \max_{k \in U_{ij}^A} |a_{kj}^{(i,j)} - a_{kj}| \quad \text{with} \quad \max_{\emptyset} = 0. $$

□

**Lemma 4.** Let $T = [t_{kl}]_{1 \le k \le n, 1 \le l \le m}$ be a matrix such that $\delta^T(i, j) = 0$. Then, we have:

1. $|a_{kl}^{(i,j)} - a_{kl}| \le |t_{kl} - a_{kl}|$ for all pairs $(k, l) \in I \times J$,

2. $\|A^{(i,j)} - A\|_p \le \|T - A\|_p$ for $p \in \{1, 2, \infty\}$.

*Proof.* It is clear that the first statement implies the second one.

To prove the first statement, It suffices to verify the inequality for $l = j$ (see (25b)) and for $k \in I$ such that $a_{kj}^{(i,j)} \neq a_{kj}$.
Using the hypothesis $\delta^T(i, j) = 0$, i.e., $b_i \le t_{ij}$ and $\sigma_G(b_i, t_{kj}, b_k) = 0$ for all $k \in I$, see (8), we observe:

* If $k = i$, then from (25a) we deduce that $b_i > a_{ij}$ and $b_i = a_{ij}^{(i,j)}$, hence

$$ a_{ij} < b_i = a_{ij}^{(i,j)} \le t_{ij} \quad \text{which implies} \quad |a_{ij}^{(i,j)} - a_{ij}| \le |t_{ij} - a_{ij}|. $$

* If $k \neq i$, then by (25a) we have $k \in U_{ij}^A$, i.e.,

$$ \sigma_G(b_i, a_{kj}, b_k) = \min\left(\frac{(b_i - b_k)^+}{2}, (a_{kj} - b_k)^+\right) > 0, $$

and $a_{kj}^{(i,j)} = b_k$. The hypothesis $\sigma_G(b_i, t_{kj}, b_k) = 0$ then implies that $t_{kj} \le b_k$, so that

$$ t_{kj} \le b_k = a_{kj}^{(i,j)} < a_{kj} \quad \text{which implies} \quad |a_{kj}^{(i,j)} - a_{kj}| \le |t_{kj} - a_{kj}|. $$

□

**Lemma 5.** Let $i_1, i_2 \in I$ with $i_1 \neq i_2$ and $j_1, j_2 \in J$. Define

$$ C := A^{(i_1, j_1)}, \quad D := C^{(i_2, j_2)}, \quad E := A^{(i_2, j_2)}, \quad F := E^{(i_1, j_1)}. $$

Then,

$$ D = F. $$
Proof. Note that the matrix $A^{(i,j)}$ is obtained by modifying the column with index $j$ in the matrix $A$ (see (25a) and (25b)). Consequently, if $j_1 \neq j_2$, with such modification, it is clear that the equality $D = F$ holds.

In the case where $j_1 = j_2$, we set $j := j_1 = j_2$ and show $D = F$ by computing the coefficients explicitly. We introduce the following notations for the matrices $C, D, E$, and $F$ of size $(n, m)$:

$$ \bullet \ C := A^{(i_1, j)} = [c_{kl}] \text{ and } D := C^{(i_2, j)} = [d_{kl}]. $$

$$ \bullet \ E := A^{(i_2, j)} = [e_{kl}] \text{ and } F := E^{(i_1, j)} = [f_{kl}]. $$

To prove $D = F$, it suffices to compare the coefficients in the $j$-th column of $C, D, E$ and $F$, and show that the $j$-th column of $D$ equals the $j$-th column of $F$.

In order to establish $d_{i_2j} = f_{i_2j}$ and $d_{i_1j} = f_{i_1j}$, it is enough to prove $d_{i_2j} = f_{i_2j}$ and then, by swapping the roles of $i_1$ and $i_2$, we deduce $d_{i_1j} = f_{i_1j}$. We now show $d_{i_2j} = f_{i_2j}$.

According to (25a), we have

$$ d_{i_2j} = \begin{cases} b_{i_2} & \text{if } b_{i_2} > c_{i_2j} \\ c_{i_2j} & \text{if } b_{i_2} \le c_{i_2j} \end{cases} $$

and, since $i_2 \neq i_1$,

$$ c_{i_2j} = \begin{cases} b_{i_2} & \text{if } i_2 \in U_{i_1j}^A \\ a_{i_2j} & \text{if } i_2 \notin U_{i_1j}^A \end{cases}. $$

Moreover, again by (25a):

$$ f_{i_2j} = \begin{cases} b_{i_2} & \text{if } i_2 \in U_{i_1j}^E \\ e_{i_2j} & \text{if } i_2 \notin U_{i_1j}^E \end{cases}, \quad e_{i_2j} = \begin{cases} b_{i_2} & \text{if } b_{i_2} > a_{i_2j} \\ a_{i_2j} & \text{if } b_{i_2} \le a_{i_2j} \end{cases}. $$

Case 1: $b_{i_2} > a_{i_2j}$.

$$ \bullet \text{ We get } e_{i_2j} = b_{i_2}, \text{ so } f_{i_2j} = b_{i_2}. $$

$$ \bullet \text{ Since } (a_{i_2j} - b_{i_2})^+ = 0, \text{ from (6) and (22), it follows that } i_2 \notin U_{i_1j}^A, \text{ thus } c_{i_2j} = a_{i_2j} < b_{i_2}, \text{ which implies } d_{i_2j} = b_{i_2} = f_{i_2j}. $$

Case 2: $b_{i_2} \le a_{i_2j}$. Then $e_{i_2j} = a_{i_2j}$. We distinguish two subcases:

$$ \bullet \text{ If } i_2 \in U_{i_1j}^A, \text{ then } c_{i_2j} = b_{i_2}, \text{ so } d_{i_2j} = b_{i_2}. \text{ Since } e_{i_2j} = a_{i_2j} \text{ and } i_2 \in U_{i_1j}^A, \text{ it follows that } i_2 \in U_{i_1j}^E, \text{ hence } f_{i_2j} = b_{i_2} = d_{i_2j}. $$

$$ \bullet \text{ If } i_2 \notin U_{i_1j}^A, \text{ then } c_{i_2j} = a_{i_2j} \ge b_{i_2}, \text{ so } d_{i_2j} = a_{i_2j}. \text{ But } e_{i_2j} = a_{i_2j} \text{ and } i_2 \notin U_{i_1j}^A \text{ imply } i_2 \notin U_{i_1j}^E, \text{ so } f_{i_2j} = e_{i_2j} = a_{i_2j} = d_{i_2j}. $$

Thus we have shown $d_{i_2j} = f_{i_2j}$. By interchanging $i_1$ and $i_2$, we also obtain $d_{i_1j} = f_{i_1j}$.

Next, let $k \notin \{i_1, i_2\}$. We will prove $d_{kj} = f_{kj}$ by considering the two cases $k \in U_{i_1j}^A$ or $k \notin U_{i_1j}^A$. From (25a), we have

$$ d_{kj} = \begin{cases} b_k & \text{if } k \in U_{i_2j}^C \\ c_{kj} & \text{if } k \notin U_{i_2j}^C \end{cases}, \quad c_{kj} = \begin{cases} b_k & \text{if } k \in U_{i_1j}^A \\ a_{kj} & \text{if } k \notin U_{i_1j}^A \end{cases}. $$

and

$$ f_{kj} = \begin{cases} b_k & \text{if } k \in U_{i_1j}^E \\ e_{kj} & \text{if } k \notin U_{i_1j}^E \end{cases}, \quad e_{kj} = \begin{cases} b_k & \text{if } k \in U_{i_2j}^A \\ a_{kj} & \text{if } k \notin U_{i_2j}^A \end{cases}. $$

Case A: $k \in U_{i_1j}^A$. Then $\sigma_G(b_{i_1}, a_{kj}, b_k) = \min(\frac{(b_{i_1}-b_k)^+}{2}, (a_{kj}-b_k)^+) > 0$, which implies $b_{i_1} > b_k$ and $a_{kj} > b_k$. Therefore $c_{kj} = b_k$ and $d_{kj} = b_k$.

$$ \bullet \text{ If } k \in U_{i_1j}^E, \text{ then } f_{kj} = b_k = d_{kj}. $$
• If $k \notin U_{i_1 j}^E$, then $f_{kj} = e_{kj}$ and since $\sigma_G(b_{i_1}, e_{kj}, b_k) = 0$, we get $e_{kj} \le b_k$. As by (26), we have $e_{kj} \in \{b_k, a_{kj}\}$, from $b_k < a_{kj}$, we obtain $e_{kj} = b_k$, hence $f_{kj} = e_{kj} = b_k = d_{kj}$.

Case B: $k \notin U_{i_1 j}^A$. Then $\sigma_G(b_{i_1}, a_{kj}, b_k) = \min\left(\frac{(b_{i_1}-b_k)^+}{2}, (a_{kj}-b_k)^+\right) = 0$ and $c_{kj} = a_{kj}$.

• If $k \in U_{i_2 j}^A$, then $e_{kj} = b_k$ and from (6) and (22), we deduce $a_{kj} > b_k$ and $k \in U_{i_2 j}^C$. Hence $d_{kj} = b_k < a_{kj}$ and $b_{i_1} \le b_k$, which implies $k \notin U_{i_1 j}^E$, so finally $f_{kj} = e_{kj} = b_k = d_{kj}$.

• If $k \notin U_{i_2 j}^A$, then $e_{kj} = a_{kj} = c_{kj}$, so by (22), we deduce $k \notin U_{i_1 j}^E$ and $k \notin U_{i_2 j}^C$, leading to $d_{kj} = c_{kj} = e_{kj} = f_{kj}$.

□

### A.3 Proof of the results in Section 3.2

#### Proposition 1.

1. For every $(k, l) \in I \times J$,

$$a_{kl}^{(\vec{i}, \vec{j})} \in \{b_k, a_{kl}\}.$$

2. For every $k \in I$ and for every $l \notin \{j_1, j_2, \dots, j_h\}$,

$$a_{kl}^{(\vec{i}, \vec{j})} = a_{kl}.$$

These properties extend those of the matrices $A^{(i,j)}$ given in (25a), (25b) and (26). They ensure that the modifications introduced by $A^{(\vec{i}, \vec{j})}$ affect only the columns indexed by $j_1, j_2, \dots, j_h$, while all other coefficients of the matrix A remain unchanged.

*Proof.* Let

$$A^{(\vec{i}, \vec{j})} = [a_{kl}^{(\vec{i}, \vec{j})}]_{1 \le k \le n, 1 \le l \le m}.$$

By induction on $h$, we easily obtain the following two results:

- From (25a), (25b) and (27), we deduce:

$$\forall (k, l) \in I \times J, \quad a_{kl}^{(\vec{i}, \vec{j})} \in \{b_k, a_{kl}\}. \qquad (66)$$

- From (25b) and (27), we deduce:

$$\forall k \in I, \forall l \notin \{j_1, j_2, \dots, j_h\}, \quad a_{kl}^{(\vec{i}, \vec{j})} = a_{kl}. \qquad (67)$$

□

**Proposition 2.** Let $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ be an $h$-tuple of two-by-two distinct indices of the set $I$ and $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$. For any permutation $\pi$ of the set $\{1, 2, \dots, h\}$ i.e., $\pi: \{1, 2, \dots, h\} \to \{1, 2, \dots, h\} : \lambda \mapsto i_\lambda$, define

$$\vec{i} \triangleleft \pi = (i_{\pi(1)}, i_{\pi(2)}, \dots, i_{\pi(h)}) \quad \text{and} \quad \vec{j} \triangleleft \pi = (j_{\pi(1)}, j_{\pi(2)}, \dots, j_{\pi(h)}). \qquad (28)$$

Then, the matrix obtained by successively modifying A using the pairs $(i_1, j_1)$, $(i_2, j_2)$, ..., $(i_h, j_h)$ is identical to the matrix obtained by applying these modifications in any permuted order; that is,

$$A^{(\vec{i}, \vec{j})} = A^{(\vec{i} \triangleleft \pi, \vec{j} \triangleleft \pi)}, \qquad (29)$$

or equivalently,

$$A^{(i_1, j_1) * (i_2, j_2) * \dots * (i_h, j_h)} = A^{(i_{\pi(1)}, j_{\pi(1)}) * (i_{\pi(2)}, j_{\pi(2)}) * \dots * (i_{\pi(h)}, j_{\pi(h)})}.$$

*Proof.* The proof of (29) is based on the case $h = 2$ established in Lemma 5 and on the following two results:
• Let $\vec{i} = (i_1, \dots, i_h) \in I^h$ be a tuple of pairwise distinct indices and $\vec{j} = (j_1, \dots, j_h) \in J^h$. For any pair of permutations $(\pi, \pi')$ of the set $\{1, 2, \dots, h\}$, we have

$$ \vec{i} \triangleleft (\pi \circ \pi') = (\vec{i} \triangleleft \pi) \triangleleft \pi', \quad \vec{j} \triangleleft (\pi \circ \pi') = (\vec{j} \triangleleft \pi) \triangleleft \pi'. \qquad (68) $$

Indeed, set $\vec{i}' := \vec{i} \triangleleft \pi = (i'_1, \dots, i'_h)$. For every $\lambda \in \{1, 2, \dots, h\}$, we have $i'_\lambda = i_{\pi(\lambda)}$. It follows that

$$ (\vec{i} \triangleleft \pi) \triangleleft \pi' = \vec{i}' \triangleleft \pi' = (i'_{\pi'(1)}, i'_{\pi'(2)}, \dots, i'_{\pi'(h)}) = (i_{\pi(\pi'(1))}, i_{\pi(\pi'(2))}, \dots, i_{\pi(\pi'(h))}) = \vec{i} \triangleleft (\pi \circ \pi'). $$

The proof of the equality $\vec{j} \triangleleft (\pi \circ \pi') = (\vec{j} \triangleleft \pi) \triangleleft \pi'$ is identical to that of $\vec{i} \triangleleft (\pi \circ \pi') = (\vec{i} \triangleleft \pi) \triangleleft \pi'$.

• Let $\pi, \pi'$ be two permutations of the set $\{1, 2, \dots, h\}$. Suppose that for every $\vec{i} = (i_1, \dots, i_h) \in I^h$ (with pairwise distinct indices) and every $\vec{j} = (j_1, \dots, j_h) \in J^h$, we have the equality (29) for $\pi$ and $\pi'$:

$$ A(\vec{i}, \vec{j}) = A(\vec{i} \triangleleft \pi, \vec{j} \triangleleft \pi) \quad \text{and} \quad A(\vec{i}, \vec{j}) = A(\vec{i} \triangleleft \pi', \vec{j} \triangleleft \pi'). $$

Then, for every $\vec{i} = (i_1, \dots, i_h) \in I^h$ (with pairwise distinct indices) and every $\vec{j} = (j_1, \dots, j_h) \in J^h$, we have

$$ A(\vec{i}, \vec{j}) = A(\vec{i} \triangleleft (\pi \circ \pi'), \vec{j} \triangleleft (\pi \circ \pi')). $$

Indeed, set $\vec{i}' = \vec{i} \triangleleft \pi$ and $\vec{j}' = \vec{j} \triangleleft \pi$. By hypothesis, we have

$$ A(\vec{i}', \vec{j}') = A(\vec{i}' \triangleleft \pi', \vec{j}' \triangleleft \pi'). $$

Then, by (68),

$$ A(\vec{i} \triangleleft (\pi \circ \pi'), \vec{j} \triangleleft (\pi \circ \pi')) = A(\vec{i}' \triangleleft \pi', \vec{j}' \triangleleft \pi') = A(\vec{i}', \vec{j}') = A(\vec{i} \triangleleft \pi, \vec{j} \triangleleft \pi) = A(\vec{i}, \vec{j}). $$

By a classical result in permutation group theory, every permutation $\pi$ of the set $\{1, 2, \dots, h\}$ is a composition of transpositions of the form $\tau = (\lambda, \lambda + 1)$ with $1 \le \lambda \le h - 1$ (see [28]).

For each $1 \le \lambda \le h - 1$, the transposition $\tau = (\lambda, \lambda + 1)$ is the permutation of the set $\{1, 2, \dots, h\}$ defined for every $\lambda' \in \{1, 2, \dots, h\}$ by

$$ \tau_{\lambda'} = \begin{cases} \lambda' & \text{if } \lambda' \notin \{\lambda, \lambda + 1\} \\ \lambda + 1 & \text{if } \lambda' = \lambda \\ \lambda & \text{if } \lambda' = \lambda + 1. \end{cases} $$

We have shown that in order to obtain (29) for every permutation $\pi$, it suffices to establish it for every transposition $\tau = (\lambda, \lambda + 1)$ with $1 \le \lambda \le h - 1$.

Set

$$ C := \begin{cases} A, & \text{if } \lambda = 1 \\ A^{(i_1, j_1)} * \dots * A^{(i_{\lambda-1}, j_{\lambda-1})}, & \text{if } \lambda > 1, \end{cases} \quad D := C^{(i_{\lambda}, j_{\lambda})} * (i_{\lambda+1}, j_{\lambda+1}), \quad E := C^{(i_{\lambda+1}, j_{\lambda+1})} * (i_{\lambda}, j_{\lambda}). $$

Then we have, see (27) and (28):

$$ A(\vec{i}, \vec{j}) = \begin{cases} D, & \text{if } \lambda + 1 = h \\ D^{(i_{\lambda+2}, j_{\lambda+2})} * \dots * (i_h, j_h), & \text{if } \lambda + 1 < h, \end{cases} \quad A(\vec{i} \triangleleft \tau, \vec{j} \triangleleft \tau) = \begin{cases} E, & \text{if } \lambda + 1 = h \\ E^{(i_{\lambda+2}, j_{\lambda+2})} * \dots * (i_h, j_h), & \text{if } \lambda + 1 < h. \end{cases} $$

By applying Lemma 5 to the matrix $C$, we obtain the equality $D = E$, which implies that

$$ A(\vec{i}, \vec{j}) = A(\vec{i} \triangleleft \tau, \vec{j} \triangleleft \tau). $$

□

**Proposition 3.** Let $A = [a_{kl}] \in [0, 1]^{n \times m}$, $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ be an h-tuple of two-by-two distinct indices and $\vec{j} = (j_1, \dots, j_h) \in J^h$. We construct the matrix $A(\vec{i}, \vec{j}) = [a_{kl}]_{1 \le k \le n, 1 \le l \le m}$ using (27). We have:

1. For all $(k, l) \in I \times J$, we have $a_{kl}(\vec{i}, \vec{j}) \in \{b_k, a_{kl}\}$.

2. For all $\lambda \in \{1, \dots, h\}$, we have $\delta A(\vec{i}, \vec{j}) (i_\lambda, j_\lambda) = 0$.
3. For all $s \in I$ and for all $l \in \{j_1, j_2, \dots, j_h\}$, we have $\delta^A(s, l) = 0 \implies \delta^{A(\vec{i}, \vec{j})}(s, l) = 0$.

4. For all $s \in I$ and for all $l \notin \{j_1, j_2, \dots, j_h\}$, we have $\delta^{A(\vec{i}, \vec{j})}(s, l) = \delta^A(s, l)$.

*Proof.* To prove the four statements, we use that for every $\lambda \in \{1, 2, \dots, h\}$, we have

$$A(\vec{i}, \vec{j}) := A^{(i_1, j_1)*(i_2, j_2)*\cdots*(i_h, j_h)} = C^{(i_\lambda, j_\lambda)}, \quad C := A^{(\vec{i}', \vec{j}')}, \qquad (69)$$

with the $(h-1)$-tuples

$$\vec{i}' := (i_1, \dots, \hat{i}_\lambda, \dots, i_h) \quad \text{and} \quad \vec{j}' := (j_1, \dots, \hat{j}_\lambda, \dots, j_h)$$

obtained from the $h$-tuples

$$\vec{i} = (i_1, \dots, i_\lambda, \dots, i_h) \quad \text{and} \quad \vec{j} = (j_1, \dots, j_\lambda, \dots, j_h)$$

by removing the $\lambda$-th component (see Proposition 2).

1. For $h=1$, we have $A(\vec{i}, \vec{j}) = A^{(i_1, j_1)}$, and the result follows from (26).

For $h > 1$, set

$$C := A^{(i_1, j_1)*(i_2, j_2)*\cdots*(i_{h-1}, j_{h-1})} = [c_{kl}]_{1 \le k \le n, 1 \le l \le m}.$$

By definition, $A(\vec{i}, \vec{j}) = C^{(i_h, j_h)}$ and by the induction hypothesis, for all $(k, l) \in I \times J$, we have $c_{kl} \in \{b_k, a_{kl}\}$.

Using (26), we have $a_{kl}^{(\vec{i}, \vec{j})} \in \{b_k, c_{kl}\}$. Then, it follows that for every $(k, l) \in I \times J$,

$$a_{kl}^{(\vec{i}, \vec{j})} \in \{b_k, a_{kl}\}.$$

2. Let $\lambda \in \{1, 2, \dots, h\}$. Set $A(\vec{i}, \vec{j}) = C^{(i_\lambda, j_\lambda)}$ (see (69)). Then, by statement 2 of Lemma 3, we deduce that

$$0 = \delta^{C^{(i_\lambda, j_\lambda)}}(i_\lambda, j_\lambda) = \delta^{A^{(\vec{i}, \vec{j})}}(i_\lambda, j_\lambda).$$

3. For $h=1$, we have $A(\vec{i}, \vec{j}) = A^{(i_1, j_1)}$ and $l=j_1$. By statement 2 of Lemma 3, we deduce that

$$\delta^{A^{(\vec{i}, \vec{j})}}(s, l) = \delta^{A^{(i_1, j_1)}}(s, j_1) = 0.$$

For $h > 1$, we distinguish the following two cases:

* Suppose that $\{j_1, j_2, \dots, j_h\} = \{l\}$. In this case,

$$A^{(\vec{i}, \vec{j})} := A^{(i_1, l)*(i_2, l)*\cdots*(i_h, l)} = C^{(i_h, l)} \quad \text{with} \quad C := A^{(i_1, l)*\cdots*(i_{h-1}, l)}.$$

By the induction hypothesis applied to the matrix $C = A(\vec{i}, \vec{j})$ obtained (see (27)) by $(h-1)$ compositions defined by $\vec{i}' := (i_1, \dots, i_{h-1})$ and $\vec{j}' := (l, l, \dots, l)$, we have $\delta^C(s, l) = 0$. By applying statement 2 of Lemma 3, we conclude that

$$\delta^{A(\vec{i}, \vec{j})}(s, l) = \delta^{C^{(i_h, l)}}(s, l) = 0.$$

* Suppose that $\{j_1, j_2, \dots, j_h\} \setminus \{l\} \neq \emptyset$. Using (29), we may assume that there exists $1 \le h' < h$ such that

$$\forall \lambda \in \{1, \dots, h'\}, \quad j_\lambda = l \quad \text{and} \quad l \notin \{j_{h'+1}, \dots, j_h\}.$$

By the induction hypothesis applied to the matrix

$$C := A^{(i_1, l)*(i_2, l)*\cdots*(i_{h'}, l)}$$

obtained in (27) by $h' < h$ compositions defined by $(i_1, \dots, i_{h'})$ and $(l, l, \dots, l)$, we have $\delta^C(s, l) = 0$. From (27), we deduce that

$$A(\vec{i}, \vec{j}) = C^{(\vec{i}', \vec{j}')},$$

with

$$\vec{i}' := (i_{h'+1}, \dots, i_h) \quad \text{and} \quad \vec{j}' := (j_{h'+1}, \dots, j_h).$$

Since $l \notin \{j_{h'+1}, \dots, j_h\}$, the matrices $C$ and $C(\vec{i}, \vec{j}) = A(\vec{i}, \vec{j})$ have the same $l$-th column, see the second statement of Proposition 1. Hence, by (8) we get:

$$\delta^{A(\vec{i}, \vec{j})}(s, l) = \delta^C(s, l) = 0.$$
4. We observe that the matrices $A^{(\vec{i},\vec{j})}$ and $A$ have the same $l$-th column, see Proposition 1. Hence,

$$ \delta A^{(\vec{i},\vec{j})}(s,l) = \delta^A(s,l). $$

<figure><img src="image_3.png" /></figure>

**Proposition 4.** Let $A = [a_{kl}] \in [0, 1]^{n \times m}$, Let $\vec{i} = (i_1, i_2, \dots, i_h) \in I^h$ be an $h$-tuple of two-by-two distinct indices of the set $I$ and $\vec{j} = (j_1, \dots, j_h) \in J^h$. We construct the matrix $A^{(\vec{i},\vec{j})} = [a_{kl}^{(\vec{i},\vec{j})}]$ using (27). For any matrix $T \in [0, 1]^{n \times m}$ verifying $\delta^T(i_\lambda, j_\lambda) = 0$ for all $\lambda \in \{1, 2, \dots, h\}$, we have:

$$ \forall (k,l) \in I \times J, \quad |a_{kl}^{(\vec{i},\vec{j})} - a_{kl}| \le |t_{kl} - a_{kl}|. \qquad (30) $$

It clearly follows that:

$$ \|A^{(\vec{i},\vec{j})} - A\|_p \le \|T - A\|_p \quad \text{for } p \in \{1, 2, \infty\}. $$

*Proof.* We proceed by induction on $h$. Lemma 4 establishes the case $h = 1$.

Suppose that $h > 1$. Let

$$ C := A^{(i_1,j_1)*(i_2,j_2)*\cdots*(i_{h-1},j_{h-1})} = [c_{kl}]_{1 \le k \le n, 1 \le l \le m}. $$

We have

$$ A^{(\vec{i},\vec{j})} = C^{(i_h,j_h)}, $$

(see (27)). Since $\delta^T(i_\lambda, j_\lambda) = 0$ for all $\lambda \in \{1, 2, \dots, h-1\}$, by the induction hypothesis we have

$$ \forall (k,l) \in I \times J, \quad |c_{kl} - a_{kl}| \le |t_{kl} - a_{kl}|. \qquad (70) $$

It follows from (70) that, in order to establish (30), it suffices to consider the cases where

$$ a_{kl}^{(\vec{i},\vec{j})} \neq c_{kl}. $$

But, by applying (25a) and (25b) to the matrix $C$ and using the equality $A^{(\vec{i},\vec{j})} = C^{(i_h,j_h)}$, we obtain

$$ a_{i_h j_h}^{(\vec{i},\vec{j})} = \begin{cases} b_{i_h} & \text{if } b_{i_h} > c_{i_h j_h} \\ c_{i_h j_h} & \text{if } b_{i_h} \le c_{i_h j_h}, \end{cases} \quad \text{and for } k \neq i_h, \quad a_{k j_h}^{(\vec{i},\vec{j})} = \begin{cases} b_k & \text{if } k \in U_{i_h j_h}^C \\ c_{k j_h} & \text{if } k \notin U_{i_h j_h}^C. \end{cases} \qquad (71) $$

Furthermore,

$$ \forall k \in I, \forall l \in J \setminus \{j_h\}, \quad a_{kl}^{(\vec{i},\vec{j})} = c_{kl}. \qquad (72) $$

This implies that

$$ \{(k,l) \in I \times J \mid a_{kl}^{(\vec{i},\vec{j})} \neq c_{kl}\} \subseteq \{(i_h) \cup U_{i_h j_h}^C\} \times \{j_h\}. $$

It remains to show that

$$ |a_{kl}^{(\vec{i},\vec{j})} - a_{kl}| \le |t_{kl} - a_{kl}| $$

in the case where $l = j_h$, $k \in \{i_h\} \cup U_{i_h j_h}^C$, and $a_{k j_h}^{(\vec{i},\vec{j})} \neq c_{k j_h}$.

Step 1. Suppose that $k = i_h$ and $a_{i_h j_h}^{(\vec{i},\vec{j})} \neq c_{i_h j_h}$. Then, from (71) we deduce that

$$ a_{i_h j_h}^{(\vec{i},\vec{j})} = b_{i_h} \quad \text{and} \quad b_{i_h} > c_{i_h j_h}. $$

By applying the first statement of Proposition 3 to the matrix $C$, we obtain $c_{i_h j_h} = a_{i_h j_h}$. But $\delta^T(i_h, j_h) = 0$ implies $b_{i_h} \le t_{i_h j_h}$, see (8), hence

$$ a_{i_h j_h} = c_{i_h j_h} < b_{i_h} = a_{i_h j_h}^{(\vec{i},\vec{j})} \le t_{i_h j_h}, $$

which implies

$$ |a_{i_h j_h}^{(\vec{i},\vec{j})} - a_{i_h j_h}| \le |t_{i_h j_h} - a_{i_h j_h}|. $$

Step 2. Suppose that $k \in U_{i_h j_h}^C$. That is,

$$ \sigma_G(b_{i_h}, c_{k j_h}, b_k) = \min \left( \frac{(b_{i_h} - b_k)^+}{2}, (c_{k j_h} - b_k)^+ \right) > 0. $$

Then, we have, successively:
* $b_{i_h} > b_k$ and $c_{kj_h} > b_k$. Since by the first statement of Proposition 3, we have $c_{kj_h} \in \{b_k, a_{kj_h}\}$, we deduce that $c_{kj_h} = a_{kj_h}$.

* The hypothesis $\delta^T(i_h, j_h) = 0$ implies

$$ \sigma_G(b_{i_h}, t_{kj_h}, b_k) = \min\left(\frac{(b_{i_h} - b_k)^+}{2}, (t_{kj_h} - b_k)^+\right) = 0. $$

Since $b_{i_h} > b_k$, it follows that $t_{kj_h} \le b_k$.

* From (71), we deduce that $a_{kj_h}^{(\vec{i}, \vec{j})} = b_k$.

Finally, we obtain:

$$ t_{kj_h} \le b_k = a_{kj_h}^{(\vec{i}, \vec{j})} < c_{kj_h} = a_{kj_h}, $$

which implies

$$ |a_{kj_h}^{(\vec{i}, \vec{j})} - a_{kj_h}| \le |t_{kj_h} - a_{kj_h}|. $$

This completes the proof.

<figure><img src="image_4.png" /></figure>

**Proposition 5.** Let $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ be a pair of h-tuples as in Definition 6.

Then, the coefficients of the modified matrix $A(\vec{i}, \vec{j}) = [a_{kl}^{(\vec{i}, \vec{j})}]_{1 \le k \le n, 1 \le l \le m}$, see (27), are given by:

$$ \text{for every } (k, l) \in I \times J, \quad a_{kl}^{(\vec{i}, \vec{j})} = \begin{cases} b_k, & \text{if } (k, l) \in \mathcal{E}, \\ a_{kl}, & \text{if } (k, l) \notin \mathcal{E}. \end{cases} $$

*Proof.* For every $(k, l) \in I \times J$, set

$$ \tilde{a}_{kl} = \begin{cases} b_k & \text{if } (k, l) \in \mathcal{E}, \\ a_{kl} & \text{if } (k, l) \notin \mathcal{E}. \end{cases} \qquad (73) $$

To prove that $a_{kl}^{(\vec{i}, \vec{j})} = \tilde{a}_{kl}$ for every $(k, l) \in I \times J$, we proceed by induction on $h$.

Before performing our induction, note that for every $(k, l) \in I \times J$ such that $l \notin \{j_1, j_2, \dots, j_h\}$, we have $a_{kl}^{(\vec{i}, \vec{j})} = a_{kl} = \tilde{a}_{kl}$: this result is deduced from the second statement of Proposition 1 and the fact that $(k, l) \notin \mathcal{E}$.

* If $h = 1$, then we have:

$$ \mathcal{E}_1 = \begin{cases} \{(i_1, j_1)\} & \text{if } b_{i_1} > a_{i_1 j_1}, \\ \emptyset & \text{if } b_{i_1} \le a_{i_1 j_1}, \end{cases} \quad \mathcal{E}_2 = U_{i_1 j_1}^A \times \{j_1\} \quad \text{and} \quad \mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2, \text{ see (31).} $$

As we have $A(\vec{i}, \vec{j}) = A^{(i_1, j_1)}$, then by using (73), (25a) and (25b), one can easily check that for every $k \in I$, we have $a_{kj_1}^{(\vec{i}, \vec{j})} = \tilde{a}_{kj_1}$.

* Suppose that for all pairs $(\vec{i}, \vec{j})$ of $(h-1)$ tuples as in Definition 6, we have $a_{kl}^{(\vec{i}, \vec{j})} = \tilde{a}_{kl}$ for every $(k, l) \in I \times J$.

Let $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ be a pair of h-tuples as in Definition 6 and $\mathcal{E}_1, \mathcal{E}_2$, and $\mathcal{E}$ be the sets associated to the pair $(\vec{i}, \vec{j})$ as in (31). We will use that for every $\lambda \in \{1, 2, \dots, h\}$, we have, see (27) and (29):

$$ A^{(\vec{i}, \vec{j})} = C^{(i_{\lambda}, j_{\lambda})} \quad \text{where} \quad C = A^{(\vec{i}, \vec{j})} \qquad (74) $$

and $(\vec{i}', \vec{j}')$ is the pair obtained by removing the $\lambda$-th component from $(\vec{i}, \vec{j})$ whose corresponding sets $\mathcal{E}'_1, \mathcal{E}'_2$, and $\mathcal{E}'$ are defined in (32).

Let $(k, l)$ be a pair in $I \times \{j_1, \dots, j_h\}$ and let us prove that $a_{kl}^{(\vec{i}, \vec{j})} = \tilde{a}_{kl}$:

* If $(k, l) \in \mathcal{E}_1$, there is an index $\lambda \in \{1, \dots, h\}$ such that:

$$ (k, l) = (i_{\lambda}, j_{\lambda}), \quad b_{i_{\lambda}} > a_{i_{\lambda} j_{\lambda}} \quad \text{and} \quad \tilde{a}_{kl} = b_{i_{\lambda}}, \text{ see (31) and (73).} $$
By setting $A^{(\vec{i}, \vec{j})} = C^{(i_{\lambda}, j_{\lambda})}$ with $C = A^{(\vec{i}, \vec{j})}$ as in (74), we get from (25a):

$$a_{kl}^{(\vec{i}, \vec{j})} = \begin{cases} b_{i_{\lambda}} & \text{if } b_{i_{\lambda}} > c_{i_{\lambda}j_{\lambda}}, \\ c_{i_{\lambda}j_{\lambda}} & \text{if } b_{i_{\lambda}} \le c_{i_{\lambda}j_{\lambda}} \end{cases} \quad \text{where} \quad C = [c_{k'l'}]_{1 \le k' \le n, 1 \le l' \le m}.$$

If the inequality $b_{i_{\lambda}} \le c_{i_{\lambda}j_{\lambda}}$ holds, then we get $a_{i_{\lambda}j_{\lambda}} < b_{i_{\lambda}} \le c_{i_{\lambda}j_{\lambda}}$. As from the first statement of Proposition 1, we have $c_{i_{\lambda}j_{\lambda}} \in \{b_{i_{\lambda}}, a_{i_{\lambda}j_{\lambda}}\}$, we conclude that in this case $b_{i_{\lambda}} = c_{i_{\lambda}j_{\lambda}} = a_{kl}^{(\vec{i}, \vec{j})}$ so in both cases, we have $a_{kl}^{(\vec{i}, \vec{j})} = b_{i_{\lambda}} = \tilde{a}_{kl}$.

* If $(k, l) \in \mathcal{E}_2$, there is an index $\lambda \in \{1, \dots, h\}$ such that:

$$l = j_{\lambda}, \quad k \in U_{i_{\lambda}j_{\lambda}}^{A} \quad \text{and} \quad \tilde{a}_{kl} = b_{k}, \text{ see (31) and (73).}$$

As $k \neq i_{\lambda}$, see (6) and (22), by setting $A^{(\vec{i}, \vec{j})} = C^{(i_{\lambda}, j_{\lambda})}$ with $C = A^{(\vec{i}, \vec{j})}$ as in (74), we get from (25b):

$$a_{kl}^{(\vec{i}, \vec{j})} = \begin{cases} b_k & \text{if } k \in U_{i_{\lambda}j_{\lambda}}^{C}, \\ c_{kj_{\lambda}} & \text{if } k \notin U_{i_{\lambda}j_{\lambda}}^{C} \end{cases} \quad \text{where} \quad C = [c_{k'l'}]_{1 \le k' \le n, 1 \le l' \le m}$$

As $k \in U_{i_{\lambda}j_{\lambda}}^{A}$, we have $b_{i_{\lambda}} > b_k$ and $a_{kj_{\lambda}} > b_k$, see (6), so if $k \notin U_{i_{\lambda}j_{\lambda}}^{C}$, we deduce $c_{kj_{\lambda}} \le b_k < a_{kj_{\lambda}}$. As from the first statement of Proposition 1, we have $c_{kj_{\lambda}} \in \{b_k, a_{kj_{\lambda}}\}$, we conclude that in this case $b_k = c_{kj_{\lambda}} = a_{kj_{\lambda}}$ so in both cases, we have $a_{kj_{\lambda}} = b_k = \tilde{a}_{kj_{\lambda}}$.

* If $(k, l) \notin \mathcal{E}$, we know from (73) that $\tilde{a}_{kl} = a_{kl}$. As we suppose that $l \in \{j_1, j_2, \dots, j_h\}$, there is an index $\lambda \in \{1, \dots, h\}$ such that $l = j_{\lambda}$. Let us write $A^{(\vec{i}, \vec{j})} = C^{(i_{\lambda}, j_{\lambda})}$ with $C = A^{(\vec{i}, \vec{j})}$ as in (74), then from Lemma 6, we get that $(k, l) = (k, j_{\lambda}) \notin \mathcal{E}'$, so by applying the induction hypothesis to the pair $(\vec{i}', \vec{j}')$, we obtain that $c_{kj_{\lambda}} = a_{kj_{\lambda}}$.

In both cases $k = i_{\lambda}$ or $k \neq i_{\lambda}$, we claim that $a_{kj_{\lambda}}^{(\vec{i}, \vec{j})} = c_{kj_{\lambda}} = a_{kj_{\lambda}}$:

- if $k = i_{\lambda}$, then $(k, j_{\lambda}) \notin \mathcal{E}$ implies that $b_{i_{\lambda}} \le a_{i_{\lambda}j_{\lambda}}$. As we have $c_{i_{\lambda}j_{\lambda}} = a_{i_{\lambda}j_{\lambda}}$, so $b_{i_{\lambda}} \le c_{i_{\lambda}j_{\lambda}}$, then from (25a) applied to the matrix $C$ and the pair $(i_{\lambda}, j_{\lambda})$, we get:

$$a_{i_{\lambda}j_{\lambda}}^{(\vec{i}, \vec{j})} = c_{i_{\lambda}j_{\lambda}} = a_{i_{\lambda}j_{\lambda}}.$$

- if $k \neq i_{\lambda}$, then $(k, j_{\lambda}) \notin \mathcal{E}$ implies that $k \notin U_{i_{\lambda}j_{\lambda}}^{A}$, see (31). From the equality $c_{kj_{\lambda}} = a_{kj_{\lambda}}$, we get from (22) that $k \notin U_{i_{\lambda}j_{\lambda}}^{C}$ and from (25b) applied to the matrix $C$ and the pair $(i_{\lambda}, j_{\lambda})$, we get:

$$a_{kj_{\lambda}}^{(\vec{i}, \vec{j})} = c_{kj_{\lambda}} = a_{kj_{\lambda}}.$$

□

**Corollary 2.** Let $(\vec{i} = (i_1, i_2, \dots, i_h), \vec{j} = (j_1, \dots, j_h))$ be a pair of h-tuples as in Definition 6. Then, we have:

$$\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = \max_{1 \le \lambda \le h} \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \quad (33)$$

*Proof.* By the second statement of Proposition 3, for every $\lambda \in \{1, \dots, h\}$, we have $\delta A^{(\vec{i}, \vec{j})} (i_{\lambda}, j_{\lambda}) = 0$. Using the second statement of Lemma 4 with $T := A^{(\vec{i}, \vec{j})}$, we deduce the inequality $\|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \le \|A^{(\vec{i}, \vec{j})} - A\|_{\infty}$ for every $\lambda \in \{1, \dots, h\}$.

We have proven the inequality $\max_{\lambda \in \{1, \dots, h\}} \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \le \|A^{(\vec{i}, \vec{j})} - A\|_{\infty}$.

As (33) is clear if $A^{(\vec{i}, \vec{j})} = A$, we suppose that $\|A^{(\vec{i}, \vec{j})} - A\|_{\infty} > 0$.

Let us fix $(k, v) \in I \times J$ such that $0 < \|A^{(\vec{i}, \vec{j})} - A\|_{\infty} = |a_{kv}^{(\vec{i}, \vec{j})} - a_{kv}|$.
From the second statement of Proposition 1, we deduce that $v \in \{j_1, j_2, \dots, j_h\}$. Fix $\tilde{\lambda} \in \{1, 2, \dots, h\}$ such that $v = j_{\tilde{\lambda}}$ and note that with this additional notation, we have:

$$0 < \|A^{(i, \tilde{j})} - A\|_{\infty} = |a_{kj_{\tilde{\lambda}}}^{(i, \tilde{j})} - a_{kj_{\tilde{\lambda}}}| \quad (75)$$

Using Proposition 5 with the set $\mathcal{E}$ associated with $(i, \tilde{j})$, we assert that $(k, j_{\tilde{\lambda}}) \in \mathcal{E}$. As $\mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2$, we distinguish the following two cases:

• if $(k, j_{\tilde{\lambda}}) \in \mathcal{E}_1$, then we have $a_{kj_{\tilde{\lambda}}}^{(i, \tilde{j})} = b_k$. Moreover, there exists some $\lambda \in \{1, 2, \dots, h\}$ such that

$$k = i_{\lambda}, \quad j_{\tilde{\lambda}} = j_{\lambda}, \quad \text{and} \quad b_{i_{\lambda}} > a_{i_{\lambda}j_{\lambda}}$$

Then, we have:

$$\begin{aligned} \|A^{(i, \tilde{j})} - A\|_{\infty} &= |a_{kj_{\tilde{\lambda}}}^{(i, \tilde{j})} - a_{kj_{\tilde{\lambda}}}| = |b_{i_{\lambda}} - a_{i_{\lambda}j_{\lambda}}| = |a_{i_{\lambda}j_{\lambda}}^{(i_{\lambda}, j_{\lambda})} - a_{i_{\lambda}j_{\lambda}}| \\ &\le \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \\ &\le \max_{1 \le \lambda' \le h} \|A^{(i_{\lambda'}, j_{\lambda'})} - A\|_{\infty}. \end{aligned}$$

• if $(k, j_{\tilde{\lambda}}) \in \mathcal{E}_2$, then we have $a_{kj_{\tilde{\lambda}}}^{(i, \tilde{j})} = b_k$. Moreover, there exists some $\lambda \in \{1, 2, \dots, h\}$ such that

$$k \in U_{i_{\lambda}j_{\lambda}}^{A} \quad \text{and} \quad j_{\tilde{\lambda}} = j_{\lambda}.$$

Then, we have:

$$\begin{aligned} \|A^{(i, \tilde{j})} - A\|_{\infty} &= |a_{kj_{\tilde{\lambda}}}^{(i, \tilde{j})} - a_{kj_{\tilde{\lambda}}}| = |b_k - a_{kj_{\lambda}}| = |a_{kj_{\lambda}}^{(i_{\lambda}, j_{\lambda})} - a_{kj_{\lambda}}| \\ &\le \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \\ &\le \max_{1 \le \lambda' \le h} \|A^{(i_{\lambda'}, j_{\lambda'})} - A\|_{\infty}. \end{aligned}$$

We have established (33).

□

## A.4 Proof of the results in Section 4

**Theorem 1.** We use the non-empty set $N_{inc}$ with $h := \text{card}(N_{inc})$, see (24). Choose an arbitrary enumeration of $N_{inc}$ as $\{i_1, i_2, \dots, i_h\}$ and set $\vec{i} = (i_1, i_2, \dots, i_h)$. Then, for every $h$-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$, the matrix $A^{(\vec{i}, \vec{j})}$ constructed with (27) yields a consistent system, which is:

$$(S^{(\vec{i}, \vec{j})}) : A^{(\vec{i}, \vec{j})} \squaremax_{\min} x = b.$$

Therefore, the matrix $A^{(\vec{i}, \vec{j})}$ belongs to the set $\mathcal{T}$ see (17). For $p \in \{1, 2, \infty\}$, we have:

$$\|A^{(\vec{i}, \vec{j})} - A\|_{p} \ge \hat{\Delta}_{p},$$

see (18) for the definition of $\hat{\Delta}_p$.

*Proof.* We must show that for every $s \in I$, we have, see (7), (11), (12):

$$\delta_s^{A^{(\vec{i}, \vec{j})}} = 0.$$

We have the partition, see (24):

$$I = N_{\text{inc}} \cup N_{\text{cons}},$$

with

$$N_{\text{inc}} = \{i_1, \dots, i_h\} \quad \text{and} \quad \vec{i} := (i_1, \dots, i_h).$$

• If $s \in N_{\text{inc}}$, then there exists a unique $\lambda \in \{1, 2, \dots, h\}$ such that $s = i_{\lambda}$. By statement 2 of Proposition 3, it follows that

$$\delta_s^{A^{(\vec{i}, \vec{j})}} \le \delta^{A^{(\vec{i}, \vec{j})}}(s, j_{\lambda}) = \delta^{A^{(\vec{i}, \vec{j})}}(i_{\lambda}, j_{\lambda}) = 0.$$
• If $s \in N_{\text{cons}}$, then $\delta_s^A = 0$. Let $l \in J$ be such that $\delta^A(s, l) = 0$. Then, by statements 3 and 4 of Proposition 3, we deduce that

$$ \delta_s^{A(\vec{i}, \vec{j})} \le \delta^{A(\vec{i}, \vec{j})}(s, l) = \delta^A(s, l) = 0. $$

<figure><img src="image_5.png" /></figure>

**Theorem 2.** Retain the notations from Theorem 1 and let

$$ A = [a_{kl}]_{1 \le k \le n, 1 \le l \le m} \quad \text{and} \quad \vec{i} = (i_1, i_2, \dots, i_h) \quad \text{such that} \quad N_{\text{inc}} = \{i_1, i_2, \dots, i_h\} $$

Then, for every consistent system whose right-hand side vector is b:

$$ T^{\square_{\min}^{\max}} x = b, \quad \text{with} \quad T = [t_{kl}]_{1 \le k \le n, 1 \le l \le m} \in \mathcal{T}, $$

there exists an h-tuple $\vec{j} = (j_1, j_2, \dots, j_h) \in J^h$ such that the system

$$ A^{(\vec{i}, \vec{j})} \square_{\min}^{\max} x = b $$

is consistent and, for every $(k, l) \in I \times J$,

$$ |a_{kl}^{(\vec{i}, \vec{j})} - a_{kl}| \le |t_{kl} - a_{kl}| \quad \text{where} \quad A^{(\vec{i}, \vec{j})} = [a_{kl}^{(\vec{i}, \vec{j})}]_{1 \le k \le n, 1 \le l \le m}. $$

We have:

$$ \|A^{(\vec{i}, \vec{j})} - A\|_p \le \|T - A\|_p \quad \text{for} \quad p \in \{1, 2, \infty\}. $$

*Proof.* It is an immediate consequence of Proposition 4 and Theorem 1.

We use the partition

$$ I = N_{\text{inc}} \cup N_{\text{cons}}, $$

with

$$ N_{\text{inc}} = \{i_1, \dots, i_h\} \quad \text{and} \quad \vec{i} := (i_1, \dots, i_h). $$

For every $\lambda \in \{1, 2, \dots, h\}$, since $\delta_{i_\lambda}^T = 0$, we choose $j_\lambda \in J$ such that

$$ \delta^T(i_\lambda, j_\lambda) = 0, $$

and form the h-tuple $(j_1, \dots, j_h)$, see (7), (11), (12).

By Theorem 1, we know that the system

$$ A^{(\vec{i}, \vec{j})} \square_{\min}^{\max} x = b $$

is consistent.

By Proposition 4, we have

$$ \forall (k, l) \in I \times J, \quad |a_{kl}^{(\vec{i}, \vec{j})} - a_{kl}| \le |t_{kl} - a_{kl}|. $$

<figure><img src="image_6.png" /></figure>

**Corollary 3.** Recall that for $p \in \{1, 2, \infty\}$ we defined in (18):

$$ \dot{\Delta}_p := \inf_{T \in \mathcal{T}} \|T - A\|_p. $$

Then, it follows from Theorems 1 and 2 that

$$ \dot{\Delta}_p = \min_{\vec{j} \in J^h} \|A^{(\vec{i}, \vec{j})} - A\|_p. \quad (34) $$

Moreover, this minimum is independent of the particular enumeration $\{i_1, i_2, \dots, i_h\}$ of the set $N_{\text{inc}}$ chosen to define the h-tuple $\vec{i} = (i_1, i_2, \dots, i_h)$.

*Proof.* Let $p \in \{1, 2, \infty\}$. Define

$$ \Delta' = \min_{\vec{j} \in J^h} \|A^{(\vec{i}, \vec{j})} - A\|_p. $$

We must show that $\Delta' = \dot{\Delta}_p$, where

$$ \dot{\Delta}_p = \min_{T \in \mathcal{T}} \|T - A\|_p. $$
• By Theorem 1, for every $\vec{j} \in J^h$ we have

$$A(\vec{i}, \vec{j}) \in \mathcal{T},$$

so that

$$\|A(\vec{i}, \vec{j}) - A\|_p \geq \Delta_p.$$

Hence, $\Delta' \geq \Delta_p$.

• By Theorem 2, for every matrix $T \in \mathcal{T}$ there exists an $h$-tuple $\vec{j} \in J^h$ such that the matrix

$$A(\vec{i}, \vec{j}) = [a_{kl}^{(\vec{i}, \vec{j})}]$$

satisfies

$$\forall (k, l) \in I \times J, \quad |a_{kl}^{(\vec{i}, \vec{j})} - a_{kl}| \leq |t_{kl} - a_{kl}|.$$

For each of the three norms considered, it then follows that

$$\Delta' \leq \|A(\vec{i}, \vec{j}) - A\|_p \leq \|T - A\|_p,$$

and therefore,

$$\Delta' \leq \min_{T \in \mathcal{T}} \|T - A\|_p = \Delta_p.$$

Thus, we deduce that $\Delta' = \Delta_p$.

□

**Theorem 3.** Let $(S) = A \square_{\min}^{\max} x = b$ be an inconsistent system. Then, for any $(\vec{i}, \vec{j}) \in L_{A,\infty}$ (see (37)), we have:

$$1. \quad \Delta_{\infty} = \|A(\vec{i}, \vec{j}) - A\|_{\infty}.$$

$$2. \quad \Delta_{\infty} = \max_{1 \leq \lambda \leq h} \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \quad \text{where } \vec{i} = (i_1, \dots, i_h) \text{ and } \vec{j} = (j_1, \dots, j_h).$$

*Proof.* First, we note that the second statement can be deduced from the first one and Corollary 2.

By the definition (37) of the set $L_{A,\infty}$, Theorem 1 and the inconsistency of the system $(S)$, we deduce that we have:

$$0 < \Delta_{\infty} \leq \|A(\vec{i}, \vec{j}) - A\|_{\infty}.$$

To prove the first statement, one must check that for any matrix $T \in \mathcal{T}$, i.e., the system $T \square_{\min}^{\max} x = b$ is consistent, we have $\|A(\vec{i}, \vec{j}) - A\|_{\infty} \leq \|T - A\|_{\infty}$.

Let $T$ be any matrix in the set $\mathcal{T}$. By the consistency of the system $T \square_{\min}^{\max} x = b$, we have:

$$\forall i \in I \ \exists l \in J \text{ such that } \delta^T(i, l) = 0,$$

see (7), (11)and (12).

For each $\lambda \in \{1, 2, \dots, h\}$, we choose an index $l_{\lambda} \in J$ such that $\delta^T(i_{\lambda}, l_{\lambda}) = 0$ and construct (Definition 5) the matrix $A^{(i_{\lambda}, l_{\lambda})} = [a_{kv}^{(i_{\lambda}, l_{\lambda})}]$ which, by Lemma 4, satisfies:

$$\forall (k, v) \in I \times J, \quad |a_{kv}^{(i_{\lambda}, l_{\lambda})} - a_{kv}| \leq \|A^{(i_{\lambda}, l_{\lambda})} - A\|_{\infty} \leq \|T - A\|_{\infty} \quad (76)$$

As $(\vec{i}, \vec{j}) \in L_{A,\infty}$ we deduce from the definition (37) of the set $L_{A,\infty}$ and (76):

$$\forall \lambda \in \{1, 2, \dots, h\}, \forall (k, v) \in I \times J, \quad |a_{kv}^{(i_{\lambda}, j_{\lambda})} - a_{kv}| \leq \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \leq \|A^{(i_{\lambda}, l_{\lambda})} - A\|_{\infty} \leq \|T - A\|_{\infty}. \quad (77)$$

Let us fix $(k, v) \in I \times J$ such that $0 < \|A(\vec{i}, \vec{j}) - A\|_{\infty} = |a_{kv}^{(\vec{i}, \vec{j})} - a_{kv}|$.

From the second statement of Proposition 1, we deduce that $v \in \{j_1, j_2, \dots, j_h\}$. Fix $\tilde{\lambda} \in \{1, 2, \dots, h\}$ such that $v = j_{\tilde{\lambda}}$ and note that with this additional notation, we have:

$$0 < \|A(\vec{i}, \vec{j}) - A\|_{\infty} = |a_{kj_{\tilde{\lambda}}}^{(\vec{i}, \vec{j})} - a_{kj_{\tilde{\lambda}}}|. \quad (78)$$

Using Proposition 5 with the set $\mathcal{E}$ associated with $(\vec{i}, \vec{j})$, we assert that $(k, j_{\tilde{\lambda}}) \in \mathcal{E}$. As $\mathcal{E} = \mathcal{E}_1 \cup \mathcal{E}_2$, we distinguish the following two cases:
* If $(k, j_{\bar{\lambda}}) \in \mathcal{E}_1$, then we have $a_{kj_{\bar{\lambda}}}^{(\vec{i}, \vec{j})} = b_k$. Moreover, there exists some $\lambda \in \{1, 2, \dots, h\}$ such that
  $k = i_{\lambda}$, $j_{\bar{\lambda}} = j_{\lambda}$, and $b_{i_{\lambda}} > a_{i_{\lambda}j_{\lambda}}$.

Then, we have:

$$ \begin{aligned} \|A^{(\vec{i}, \vec{j})} - A\|_{\infty} &= |a_{kj_{\bar{\lambda}}}^{(\vec{i}, \vec{j})} - a_{kj_{\bar{\lambda}}}| = |b_{i_{\lambda}} - a_{i_{\lambda}j_{\lambda}}| = |a_{i_{\lambda}j_{\lambda}}^{(i_{\lambda}, j_{\lambda})} - a_{i_{\lambda}j_{\lambda}}|, \quad \text{see (25a)} \\ &\le \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \le \|A^{(i_{\lambda}, l_{\lambda})} - A\|_{\infty} \le \|T - A\|_{\infty}, \quad \text{see (77).} \end{aligned} $$

* If $(k, j_{\bar{\lambda}}) \in \mathcal{E}_2$, then we have $a_{kj_{\bar{\lambda}}}^{(\vec{i}, \vec{j})} = b_k$. Moreover, there exists some $\lambda \in \{1, 2, \dots, h\}$ such that:
  $k \in U_{i_{\lambda}j_{\lambda}}^A$ and $j_{\bar{\lambda}} = j_{\lambda}$.

Then, we have:

$$ \begin{aligned} \|A^{(\vec{i}, \vec{j})} - A\|_{\infty} &= |a_{kj_{\bar{\lambda}}}^{(\vec{i}, \vec{j})} - a_{kj_{\bar{\lambda}}}| = |b_k - a_{kj_{\bar{\lambda}}}| = |a_{kj_{\bar{\lambda}}}^{(i_{\lambda}, j_{\lambda})} - a_{kj_{\bar{\lambda}}}|, \quad \text{see (25a)} \\ &\le \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \le \|A^{(i_{\lambda}, l_{\lambda})} - A\|_{\infty} \le \|T - A\|_{\infty}, \quad \text{see (77).} \end{aligned} $$

□

**Corollary 4.** For any system (S) : $A \Box_{\min} x = b$, we have:

$$ \hat{\Delta}_{\infty} = \max_{i \in I} \min_{j \in J} \max \left[ (b_i - a_{ij})^{+}, \max_{k \in I, k \neq i} \left( \theta(i, k) \cdot (a_{kj} - b_k)^{+} \right) \right] \quad (38) $$

where $\theta: I \times I \mapsto \{0, 1\}: \theta(i, k) = \begin{cases} 1 & \text{if } b_i > b_k \\ 0 & \text{otherwise} \end{cases}$ and was defined in (23).

The formula (38) can be reformulated using the set $N_{inc}$, see (24):

$$ \hat{\Delta}_{\infty} = \max_{i \in N_{inc}} \min_{j \in J} \max \left[ (b_i - a_{ij})^{+}, \max_{k \in I, k \neq i} \left( \theta(i, k) \cdot (a_{kj} - b_k)^{+} \right) \right]. $$

*Proof.* We distinguish the following two cases:

* Suppose that the system (S) is consistent. As in this case $\hat{\Delta}_{\infty} = \min_{T \in \mathcal{T}} \|T - A\|_{\infty} = 0$, we must prove that for all $i \in I$ we have:

$$ \min_{j \in J} \max \left[ (b_i - a_{ij})^{+}, \max_{k \in I, k \neq i} \left( \theta(i, k) \cdot (a_{kj} - b_k)^{+} \right) \right] = 0. $$

By (11) and (12), we know that for all $i \in I$, we have:

$$ \delta_i^A := \min_{j \in J} \delta^A(i, j) := \min_{j \in J} \max[(b_i - a_{ij})^+, \max_{k \in I} \sigma_G(b_i, a_{kj}, b_k)] = 0, $$

see (7) and (8).

As $\sigma_G(x, y, z) = \min(\frac{(x-z)^+}{2}, (y-z)^+)$ for all $x, y, z$ in $[0, 1]$, the following implication is true:

$$ \delta_i^A = 0 \implies \min_{j \in J} \max[(b_i - a_{ij})^+, \max_{k \in I, k \neq i} (\theta(i, k) \cdot (a_{kj} - b_k)^+)] = 0. \quad (79) $$

We have proven (38) in the consistent case.

* Suppose that the system (S) is inconsistent. We take a pair $(\vec{i}, \vec{j}) \in L_{A, \infty}$ so by the first statement of Theorem 3, we have

$$ \hat{\Delta}_{\infty} = \|A^{(\vec{i}, \vec{j})} - A\|_{\infty}. $$

As $\vec{i} = (i_1, \dots, i_h)$ where $\{i_1, \dots, i_h\}$ is an enumeration of the set $N_{inc} = \{i \in I \mid \delta_i^A > 0\}$, we deduce from Corollary 2, the definition (37) of the set $L_{A, \infty}$ and the fourth statement of Lemma 3 that we have:

$$ \begin{aligned} \|A^{(\vec{i}, \vec{j})} - A\|_{\infty} &= \max_{1 \le \lambda \le h} \|A^{(i_{\lambda}, j_{\lambda})} - A\|_{\infty} \\ &= \max_{1 \le \lambda \le h} \min_{j \in J} \|A^{(i_{\lambda}, j)} - A\|_{\infty} \\ &= \max_{1 \le \lambda \le h} \min_{j \in J} \max[(b_{i_{\lambda}} - a_{i_{\lambda}j})^+, \max_{k \in I, k \neq i_{\lambda}} (\theta(i_{\lambda}, k) \cdot (a_{kj} - b_k)^+)]. \end{aligned} $$
We conclude that the equality $\hat{\Delta}_{\infty} = \max_{i \in I} \min_{j \in J} \max[(b_i - a_{ij})^+, \max_{k \in I, k \neq i} (\theta(i, k) \cdot (a_{kj} - b_k)^+)]$ is equivalent to:

$$ \max_{i \in \overline{N}_{\text{inc}}} \min_{j \in J} \max[(b_i - a_{ij})^+, \max_{k \in I, k \neq i} (\theta(i, k) \cdot (a_{kj} - b_k)^+)] = 0 \quad \text{with} \quad \max_{\emptyset} = 0. $$

But, as $\overline{N}_{\text{inc}} = \{i \in I \mid \delta_i^A = 0\}$, by using (79) for all $i \in \overline{N}_{\text{inc}}$, we get:

$$ \min_{j \in J} \max[(b_i - a_{ij})^+, \max_{k \in I, k \neq i} (\theta(i, k) \cdot (a_{kj} - b_k)^+)] = 0. $$

We haven proven (38) in the inconsistent case.

□