# Maximal Consistent Subsystems of Max-T Fuzzy Relational Equations

Ismaïl Baaj
Univ. Artois, CNRS, CRIL, F-62300 Lens, France
<EMAIL_ADDRESS>
###### Abstract

In this article, we study the inconsistency of a system of $\max-T$ fuzzy
relational equations of the form $A\Box_{T}^{\max}x=b$, where $T$ is a t-norm
among $\min$, the product or Lukasiewicz’s t-norm. For an inconsistent
$\max-T$ system, we directly construct a canonical maximal consistent
subsystem (w.r.t the inclusion order). The main tool used to obtain it is the
analytical formula which compute the Chebyshev distance
$\Delta=\inf_{c\in\mathcal{C}}\|b-c\|$ associated to the inconsistent $\max-T$
system, where $\mathcal{C}$ is the set of second members of consistent systems
defined with the same matrix $A$. Based on the same analytical formula, we
give, for an inconsistent $\max-\min$ system, an efficient method to obtain
all its consistent subsystems, and we show how to iteratively get all its
maximal consistent subsystems.

_Keywords_ Fuzzy set theory ; fuzzy relational equations

##  1 Introduction

Sanchez’s seminal work on systems of $\max-\min$ fuzzy relational equations
established necessary and sufficient conditions for a system to be consistent,
i.e., to have solutions [14]. In [15], Sanchez showed that if the system is
consistent, it has a greater solution and a finite set of minimal solutions,
and he then described the complete set of solutions of the system. His work
was then followed by studies on solving systems based on $\max-T$ composition
[7, 11, 12, 13] where $T$ is a given t-norm. However, the inconsistency of
$\max-T$ systems remains difficult to address.

Some authors [4, 10] highlighted that handling the inconsistency of a system
of $\max-T$ fuzzy relational equations can be tackled by finding its maximal
consistent subsystems. Formally, given an inconsistent system defined by a set
of $n$ equations whose indexes are $1,2,\cdots,n$, a consistent subsystem
defined by a subset of these equations, whose indexes form a subset
$R\subseteq\\{1,2,\cdots,n\\}$, is maximal if any subsystem defined by a
strict superset of $R$ is inconsistent.

In this article, using recent works [2, 3] on the handling of the
inconsistency of $\max-T$ systems of the form $A\Box_{T}^{\max}x=b$, where $T$
is a t-norm among $\min$, product or Łukasiewicz’s t-norm, we directly
construct a canonical maximal consistent subsystem of the system
$A\Box_{T}^{\max}x=b$. The indexes of the equations composing this maximal
consistent subsystem are obtained by computing, using the $L_{\infty}$ norm,
the Chebyshev distance $\Delta=\inf_{c\in\mathcal{C}}\|b-c\|$, where
$\mathcal{C}$ is the set of second members of consistent systems defined with
the same matrix $A$. The author of [2, 3] gave three analytical formulas for
computing the Chebyshev distances $\Delta$ associated to the three $\max-T$
systems.
For this purpose, we start by showing that these three analytic formulas
(which we remind in the article, see (14) for $\max-\min$ system, (16) for
$\max-$product system and (19) for max-Łukasiewicz system) have a canonical
single expression, which depends only on the t-norm $T$ considered. For a
$\max-T$ system whose matrix is of size $(n,m)$, $\Delta$’s canonical form is
expressed as $\Delta=\max_{1\leq i\leq n}\delta_{i}$ where
$\delta_{i}=\min_{1\leq j\leq m}\max_{1\leq k\leq n}\delta_{ijk}^{T}$, see
(24). The computation of (at most) $n^{2}\cdot m$ numbers $\delta_{ijk}^{T}$
is therefore necessary to obtain the Chebyshev distance. From $\Delta$’s
canonical form, we introduce the set $N_{c}$, see (25), composed of the
indexes $i$ of the equations of the considered system, whose corresponding
$\delta_{i}$ is equal to zero. In order to prove that the subsystem defined by
the set $N_{c}$ is a maximal consistent subsystem, we first give an important
characterization of the case $\delta_{ijk}^{T}>0$, where $\delta_{ijk}^{T}$ is
involved in $\Delta$’s canonical form (see (Lemma 2) and also (Lemma 1)).
Then, we study any equation whose index $i$ is in the intersection of the
complement of the set $N_{c}$ and a set $R\subseteq\\{1,2,\dots,n\\}$ whose
corresponding subsystem is consistent, see (Lemma 4), (Lemma 5) and (Lemma 6).
These last three lemmas and (Proposition 1) let us prove our main result in
(Theorem 1): the subsystem formed by the equations of the system whose indexes
are in the set $N_{c}$ is a maximal consistent subsystem. Since the Chebyshev
distance $\Delta$ requires the computation of (at most) $n^{2}\cdot m$
numbers, the construction of this maximal consistent subsystem has the same
computational complexity.
We then study the set formed by the consistent subsystems of an inconsistent
$\max-\min$ system. For this purpose, we first arrange in ascending order the
coefficients of the second member of the system, and we rely on the Chebyshev
distance associated to any subsystem $(S_{R})$ defined by a set
$R\subseteq\\{1,2,\dots,n\\}$, see (Lemma 3). Given a consistent subsystem
$(S_{R})$ of the subsystem $(S_{\\{1,2,\dots s\\}})$ where $1\leq s\leq n-1$,
we can construct, by computing $n-s$ explicit numbers, all the consistent
subsystems which are defined by subsets $R^{\prime}\subseteq\\{1,2,\dots,n\\}$
such that $R\subset R^{\prime}$ and
$\text{card}(R^{\prime})=\text{card}(R)+1$. Denoting by ${\cal E}^{s}$ the set
formed by the consistent subsystems of the subsystem $(S_{\\{1,2,\dots
s\\}})$, we thus obtain a method to build ${\cal E}^{s+1}$ (related to
$(S_{\\{1,2,\dots s+1\\}})$) from ${\cal E}^{s}$, see (45), which can be used
to get all the maximal consistent subsystems of the whole $\max-\min$ system,
see (Proposition 2).

The article is structured as follows. In (Section 2), we remind the necessary
background for solving $\max-T$ systems and present some of the results on the
inconsistency of these systems proven in [2, 3] i.e., the formulas to compute
the Chebyshev distances $\Delta$ for a $\max-\min$ system, a $\max-$product
system and a max-Łukasiewicz system, see (14), (16) and (19) respectively. In
(Section 3), we obtain a canonical single expression for these three formulas,
which depends only on the t-norm considered, see (23). We introduce some
notations (Notation 2) and the set $N_{c}$, see (25). Then, we characterize
the case $\delta^{T}_{ijk}>0$, where $\delta^{T}_{ijk}$ is involved in
$\Delta$’s canonical form, and we provide a formula for the Chebyshev distance
associated to a subsystem of the system, which is defined by a subset of
equations of the considered system. In (Section 4), we prove some preliminary
results ((Lemma 4), (Lemma 5), (Lemma 6) and (Proposition 1)), which are
necessary to establish (Theorem 1). In (Section 5), we present our method for
efficiently finding all consistent subsystems of an inconsistent max-min
system and apply it to obtain all the maximal consistent systems of the
inconsistent system. Finally, we conclude by giving some potential
applications of our results, in particular some based on $\max-T$ learning
methods.

##  2 Background

In this section, $T$ denotes a continuous t-norm and $\mathcal{I}_{T}$ its
associated residual implicator [9]. We remind the three main t-norms ($\min$,
product and Łukasiewicz’s t-norm) and their associated residual implicator
(the Gödel implication, the Goguen implication and Łukasiewicz’s implication,
respectively).
We remind the necessary background for solving systems of $\max-T$ fuzzy
relational equations of the form $A\Box_{T}^{\max}x=b$. Finally, we present
some recent results of [2, 3] on the handling of the inconsistency of systems
of $\max-T$ fuzzy relational equations, in which the author gave, for each
$\max-T$ system, an explicit analytic formula for computing the Chebyshev
distance $\Delta=\inf_{c\in\mathcal{C}}\|b-c\|$, where $\mathcal{C}$ is the
set of second members of consistent systems defined with the same matrix $A$.

The following notations are reused from [2, 3]:

######  Notation 1.

The set $[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]$. The set
$[0,1]^{n\times 1}$ is the set of column vectors of $n$ components and
$[0,1]^{1\times m}$ is the set of row matrices of $m$ components.

The order relation $\leq$ on the set $[0,1]^{n\times m}$ is defined by:

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

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

For $x,y,z,u,\delta\in[0,1]$, we put:

  * •

$x^{+}=\max(x,0)$,

  * •

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

  * •

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

###  2.1 T-norms and their associated residual implicators

A triangular-norm (t-norm, see [9]) is a map $T:[0,1]\times[0,1]\mapsto[0,1]$,
which satisfies:

  * $T$ is commutative: $T(x,y)=T(y,x)$,

  * $T$ is associative: $T(x,T(y,z))=T(T(x,y),z)$,

  * $T$ is increasing : $x\leq x^{\prime}\quad\text{and}\quad y\leq y^{\prime}\,\Longrightarrow\,T(x,y)\leq T(x^{\prime},y^{\prime})$,

  * $T$ has $1$ as neutral element: $T(x,1)=x$.

To the t-norm $T$ is associated the residual implicator ${\cal
I}_{T}:[0,1]\times[0,1]\rightarrow[0,1]:(x,y)\mapsto{\cal
I}_{T}(x,y)=\sup\\{z\in[0,1]\,\mid\,T(x,z)\leq y\\}$.

For all $a,b\in[0,1]$, the main properties of the residual implicator ${\cal
I}_{T}$ associated to a continuous t-norm $T$ are:

  * •

${\cal I}_{T}(a,b)=\max\\{z\in[0,1]\,\mid\,T(a,z)\leq b\\}$. Therefore,
$T(a,{\cal I}_{T}(a,b))\leq b$.

  * •

${\cal I}_{T}$ is left-continuous and decreasing in its first argument as well
as right-continuous and increasing in its second argument.

  * •

For all $z\in[0,1]$, we have:

$T(a,z)\leq b\Longleftrightarrow z\leq{\cal I}_{T}(a,b).$

  * •

We have $\,b\leq{\cal I}_{T}(a,T(a,b))$.

The t-norm $\min$ denoted by $T_{M}$, has a residual implicator
$\mathcal{I}_{T_{M}}$ which is the Gödel implication:

$T_{M}(x,y)=\min(x,y)\quad;\quad{\cal
I}_{T_{M}}(x,y)=x\underset{G}{\longrightarrow}y=\begin{cases}1&\text{ if
}x\leq y\\\ \ y&\text{ if }x>y\end{cases}.$ (1)

The t-norm defined by the usual product is denoted by $T_{P}$. Its associated
residual implicator is the Goguen implication:

$T_{P}(x,y)=x\cdot y\quad;\quad{\cal
I}_{T_{P}}(x,y)=x\underset{GG}{\longrightarrow}y=\begin{cases}1&\text{ if
}x\leq y\\\ \frac{y}{x}&\text{ if }x>y\end{cases}.$ (2)

Łukasiewicz’s t-norm is denoted by $T_{L}$ and its associated residual
implicator is Łukasiewicz’s implication ${\cal I}_{T_{L}}$:

$T_{L}(x,y)=\max(x+y-1,0)={(x+y-1)}^{+}\quad;\quad{\cal
I}_{T_{L}}(x,y)=x\underset{L}{\longrightarrow}y=\min(1-x+y,1).$ (3)

###  2.2 Solving systems of $\max-T$ fuzzy relational equations

A system of $\max-T$ fuzzy relational equations based on a matrix
$A=[a_{ij}]\in[0,1]^{n\times m}$ and a column-vector
$b=[b_{i}]\in[0,1]^{n\times 1}$ is of the form:

$(S):A\Box_{T}^{\max}x=b,$ (4)

where $x=[x_{j}]_{1\leq j\leq m}\in[0,1]^{m\times 1}$ is an unknown vector and
the matrix product $\Box_{T}^{\max}$ uses the continuous t-norm $T$ as the
product and $\max$ as the addition.

Using the vector

$e=A^{t}\Box_{{\cal I}_{T}}^{\min}b,$ (5)

where $A^{t}$ is the transpose of $A$ and the matrix product $\Box_{{\cal
I}_{T}}^{\min}$ uses the residual implicator ${\cal I}_{T}$ (associated to
$T$) as the product and $\min$ as the addition, we have the following
equivalence proved by Sanchez for $\max-\min$ composition [14], and extended
to $\max-T$ composition by Pedrycz [12, 13] and Miyakoshi and Shimbo [11]:

$A\Box_{T}^{\max}x=b\text{ is consistent}\Longleftrightarrow
A\Box_{T}^{\max}e=b.$ (6)

######  Example 1.

We study the following $\max-\min$ system denoted $A\Box_{\min}^{\max}x=b$
where:

$A=\begin{bmatrix}1&0.4&0.5&0.7\\\ 0.7&0.5&0.3&0.5\\\ 0.2&1&1&0.6\\\
0.4&0.5&0.5&0.8\end{bmatrix}\text{ and }b=\begin{bmatrix}0.8\\\ 0.7\\\ 0.4\\\
0.4\end{bmatrix}.$ (7)

We compute the potential greatest solution of the system using the Gödel
implication $\rightarrow_{G}$, see (1), which is associated to the t-norm
$\min$:

$e=A^{t}\Box_{\rightarrow_{G}}^{\min}b=\begin{bmatrix}0.8\\\ 0.4\\\ 0.4\\\
0.4\end{bmatrix}.$

We check that:

$A\Box_{\min}^{\max}e=\begin{bmatrix}0.8\\\ 0.7\\\ 0.4\\\ 0.4\end{bmatrix}=b.$

So the system $A\Box_{\min}^{\max}x=b$ is consistent.

###  2.3 Chebyshev distance associated to the second member of a system of
$\max-T$ fuzzy relational equations

To the matrix $A$ and the second member $b$ of the system $(S)$ of $\max-T$
fuzzy relational equations, see (4), is associated the set of vectors
$c=[c_{i}]\in[0,1]^{n\times 1}$ such that the system $A\Box_{T}^{\max}x=c$ is
consistent:

$\mathcal{C}=\\{c=[c_{i}]\in{[0,1]}^{n\times 1}\mid A\Box_{T}^{\max}x=c\text{
is consistent}\\}.$ (8)

This set allows us to define the Chebyshev distance associated to the second
member $b$ of the system $(S)$.

######  Definition 1.

The Chebyshev distance associated to the second member $b$ of the system
$(S):A\Box_{T}^{\max}x=b$ is:

$\Delta=\Delta(A,b)=\inf_{c\in\mathcal{C}}\|b-c\|$ (9)

where:

$\|b-c\|=\max_{1\leq i\leq n}\mid b_{i}-c_{i}\mid.$

The following result was proven for $\max-\min$ system in [5] and recently
extended to $\max-T$ systems in [2]:

$\Delta=\min\\{\delta\in[0,1]\mid\underline{b}(\delta)\leq
F(\overline{b}(\delta))\\},$ (10)

which involves a vector inequality based on the following application:

$F:[0,1]^{n\times 1}\longrightarrow[0,1]^{n\times 1}:c=[c_{i}]\mapsto
F(c)=A\Box_{T}^{\max}(A^{t}\Box_{{\cal I}_{T}}^{\min}c)=[F(c)_{i}]$ (11)

where:

$\forall i\in\\{1,2,\dots,n\\},\,F(c)_{i}=\max_{1\leq j\leq
m}T(a_{ij},\min_{1\leq k\leq n}{\cal I}_{T}(a_{kj},c_{k})).$ (12)

We remind (see [2, 3]) that for any $c\in[0,1]^{n}$ , we have the
inequalities:

$\forall i\in\\{1,2,\dots,n\\}\,,\,F(c)_{i}\leq c_{i}.$ (13)

By solving (10) in the case of a system of $\max-\min$ fuzzy relational
equations $A\Box_{\min}^{\max}x=b$, the author of [3] gave the following
analytical formula for computing the Chebyshev distance associated to its
second member $b$:

$\Delta=\max_{1\leq i\leq n}\min_{1\leq j\leq
m}\,\max[(b_{i}-a_{ij})^{+},\max_{1\leq k\leq
n}\,\,\sigma_{G}\,(b_{i},a_{kj},b_{k})],$ (14)

where

$\sigma_{G}(x,y,z)=\min(\frac{(x-z)^{+}}{2},(y-z)^{+}).$ (15)

Similarly, for the case of a system of $\max$-product fuzzy relational
equations $A\Box_{T_{P}}^{\max}x=b$, the author of [2] gave the following
analytical formula for computing the Chebyshev distance associated to $b$:

$\Delta=\max_{1\leq i\leq n}\min_{1\leq j\leq m}\,\max_{1\leq k\leq
n}\,\sigma_{GG}\,(a_{ij},b_{i},a_{kj},b_{k}),$ (16)

where

$\sigma_{GG}(u,x,y,z)=\max[(x-u)^{+},\min(\varphi(u,x,y,z),(y-z)^{+})]$ (17)

and

$\varphi(u,x,y,z)=\begin{cases}\frac{(x\cdot y-u\cdot z)^{+}}{u+y}&\text{ if
}u>0\\\ x&\text{ if }u=0\end{cases}.$ (18)

The author of [2] also gave the following analytical formula for computing
Chebyshev distance associated to the second member $b$ of a system of
$\max$-Łukasiewicz fuzzy relational equations $A\Box_{T_{L}}^{\max}x=b$:

$\Delta=\max_{1\leq i\leq n}\min_{1\leq j\leq m}\,\max_{1\leq k\leq
n}\,\sigma_{L}\,(1-a_{ij},b_{i},a_{kj},b_{k}),$ (19)

where

$\sigma_{L}(u,x,y,z)=\min(x,\max(v^{+},\frac{(v+y-z)^{+}}{2}))\text{ with
}v=x+u-1.$ (20)

From these formulas, the author of [2, 3] proved that
$F(\overline{b}(\Delta))$ is the greatest Chebyshev approximation of the
second member $b$, so the system $A\Box_{T}^{\max}x=F(\overline{b}(\Delta))$
is consistent and $\|F(\overline{b}(\Delta))-b\|=\Delta$. Therefore, the
author showed the following important equivalence for $\max-T$ systems:

$\Delta=0\Longleftrightarrow\text{ The system }(S)\text{ is consistent.}$ (21)

######  Example 2.

(continued) We reuse the matrix $A$ and the vector $b$ of (Example 1), see
(7).

  * •

The Chebyshev distance associated to the $\max-\min$ system
$A\Box_{\min}^{\max}x=b$ is equal to zero (this system is consistent).

  * •

The Chebyshev distance associated to the second member of the $\max-$product
system $A\Box_{T_{P}}^{\max}x=b$ is roughly equal to $0.083$ (this system is
inconsistent). We compute $F(\overline{b}(\Delta))=\begin{bmatrix}0.883\\\
0.6181\\\ 0.483\\\ 0.483\end{bmatrix}$ and the system
$A\Box_{T_{P}}^{\max}x=F(\overline{b}(\Delta))$ is consistent.

  * •

The Chebyshev distance associated to the second member of the
$\max-$Łukasiewicz system $A\Box_{T_{L}}^{\max}x=b$ is equal to $0.1$ (this
system is inconsistent). We compute
$F(\overline{b}(\Delta))=\begin{bmatrix}0.9\\\ 0.6\\\ 0.5\\\ 0.5\end{bmatrix}$
and the system $A\Box_{T_{L}}^{\max}x=F(\overline{b}(\Delta))$ is consistent.

##  3 Preliminaries

In this section, we begin by showing that the formulas ((14), (16) and (19))
of the Chebyshev distance $\Delta=\Delta(A,b)$ associated to the three
$\max-T$ systems of the form $(S):A\Box_{T}^{\max}x=b$, see (4), have a
canonical single expression, which depends only on the t-norm $T$. We then
give some notations (Notation 2). In particular, we denote by $(S_{R})$ the
subsystem of the system $(S)$ defined using the set
$R\subseteq\\{1,2,\dots,n\\}$ of the indexes of the equations taken from the
system $(S)$ to form the subsystem $(S_{R})$.

We establish some properties ((Lemma 1), (Lemma 2) and (Lemma 3)) of the
numbers $\delta_{ijk}^{T}$ involved in the canonical formula of $\Delta$.
These results will be useful in the next section to prove (Theorem 1), which
allows us to obtain a canonical maximal consistent subsystem of an
inconsistent system $(S)$ just by computing the Chebyshev distance $\Delta$
associated to the system $(S)$.

###  3.1 $\Delta$’s canonical form and notations

Let us rewrite the Chebyshev distance associated to the second member of a
system of $\max-\min$ fuzzy relational equations, see (14), as follows:

$\Delta=\max_{1\leq i\leq n}\min_{1\leq j\leq m}\,\max_{1\leq k\leq
n}\max[(b_{i}-a_{ij})^{+},\,\,\sigma_{G}\,(b_{i},a_{kj},b_{k})]$ (22)

Then, from the formulas of the Chebyshev distances $\Delta$ associated to each
of three systems of $\max-T$ fuzzy relational equations, see (16), (19) and
(22), we can give a canonical formula for $\Delta$ which only depends on the
choice of the t-norm $T$:

$\Delta=\max_{1\leq i\leq n}\delta_{i}\quad\text{ with
}\quad\delta_{i}=\min_{1\leq j\leq m}\,\delta(i,j)\quad\text{ and
}\quad\delta(i,j)=\max_{1\leq k\leq n}\delta_{ijk}^{T}$ (23)

where:

$\delta_{ijk}^{T}=\begin{cases}\max[(b_{i}-a_{ij})^{+},\,\,\sigma_{G}\,(b_{i},a_{kj},b_{k})]&\text{
if }T=T_{M}\text{ (min)}\\\ \sigma_{GG}\,(a_{ij},b_{i},a_{kj},b_{k})&\text{ if
}T=T_{P}\text{ (product)}\\\ \sigma_{L}\,(1-a_{ij},b_{i},a_{kj},b_{k})&\text{
if }T=T_{P}\text{ (\L ukasiewicz's t-norm)}\end{cases}.$ (24)

(We remind that $\sigma_{G}$, $\sigma_{GG}$ and $\sigma_{L}$ are defined in
(15), (17) and (20) respectively and were introduced in [2, 3]).

In this form, we can see that $\Delta$ requires computing (at most)
$n^{2}\cdot m$ numbers $\delta_{ijk}^{T}$.

For a $\max-T$ system $A\Box_{T}^{\max}x=b$, see (4), we use the following
notations:

######  Notation 2.

  * •

$N=\\{1,2,\dots,n\\},\quad M=\\{1,2,\dots,m\\}$,

  * •

for any subset $R\subseteq\\{1,2,\dots,n\\}$, we form the following $\max-T$
subsystem:

$(S_{R}):A_{R}\Box_{T}^{\max}x=b_{R},\text{ where }A_{R}=[a_{ij}]_{i\in
R,1\leq j\leq m}\text{ and }b_{R}=[b_{i}]_{i\in R},$

whose associated Chebyshev distance is denoted
$\Delta_{R}:=\Delta(A_{R},b_{R})$.

Thus, for any $i\in\\{1,2,\dots,n\\}$ , the $\max-T$ system
$(S_{\\{i\\}}):A_{\\{i\\}}\Box_{T}^{\max}x=b_{\\{i\\}}$ is the system reduced
to the $i$-th equation of $(S)$.

From the canonical form of $\Delta$, see (23), we extract the indexes of
equations whose corresponding $\delta_{i}$ is equal to zero, in order to form
the following set:

$N_{c}=\bigg{\\{}i\in\\{1,2,\dots,n\\}\,\mid\,\delta_{i}=0\bigg{\\}}.$ (25)

The complement of the set $N_{c}$ is denoted $\overline{N_{c}}$.

######  Example 3.

(continued) We reuse the matrix $A$ and the vector $b$ of (Example 1), see
(7).

  * •

The $\max-\min$ system $A\Box_{\min}^{\max}x=b$ is consistent. We have
$\delta_{1}=\delta_{2}=\delta_{3}=\delta_{4}=0$ and the set $N_{c}$ is equal
to $\\{1,2,3,4\\}$.

  * •

The $\max-$product system $A\Box_{T_{P}}^{\max}x=b$ is inconsistent. We have
$\delta_{1}=\delta_{3}=\delta_{4}=0$ and $\delta_{2}=0.083$, so the set
$N_{c}$ is equal to $\\{1,3,4\\}$.

  * •

The $\max-$Łukasiewicz system $A\Box_{T_{L}}^{\max}x=b$ is inconsistent. We
have $\delta_{1}=\delta_{3}=\delta_{4}=0$ and $\delta_{2}=0.1$, so the set
$N_{c}$ is equal to $\\{1,3,4\\}$.

###  3.2 Preliminary results

From $\Delta$’s canonical form, see (23), we establish:

######  Lemma 1.

For all $i\in N$ and $j\in M$ (Notation 2), we have
$\delta^{T}_{iji}=(b_{i}-a_{ij})^{+}$.

###### Proof.

  * •

For $T=T_{M}$ (min), from $\sigma_{G}$, see (15), we have for all $i\in N$ and
$j\in M$:

$\sigma_{G}(b_{i},a_{ij},b_{i})=\min(\frac{(b_{i}-b_{i})^{+}}{2},(a_{ij}-b_{i})^{+})=0.$

Therefore, from (24), we have:

$\displaystyle\delta_{iji}^{T_{M}}$
$\displaystyle=\max[(b_{i}-a_{ij})^{+},\,\,\sigma_{G}\,(b_{i},a_{ij},b_{i})]$
$\displaystyle=(b_{i}-a_{ij})^{+}.$

  * •

For $T=T_{P}$ (product), from the formula of $\varphi$, see (18), we have for
all $i\in N$ and $j\in M$:

$\varphi(a_{ij},b_{i},a_{ij},b_{i})=\begin{cases}0&\text{ if }a_{ij}>0\\\
b_{i}&\text{ if }a_{ij}=0\end{cases}.$

We remark that if $a_{ij}=0$, then $(a_{ij}-b_{i})^{+}=0$. Thus, whatever if
$a_{ij}>0$ or $a_{ij}=0$, from the formula of $\sigma_{GG}$, see (17), we
have:

$\displaystyle\delta_{iji}^{T_{P}}$
$\displaystyle=\sigma_{GG}(a_{ij},b_{i},a_{ij},b_{i})$
$\displaystyle=\max[(b_{i}-a_{ij})^{+},\min(\varphi(a_{ij},b_{i},a_{ij},b_{i}),(a_{ij}-b_{i})^{+})]$
$\displaystyle=(b_{i}-a_{ij})^{+}.$

  * •

For $T=T_{L}$ (Łukasiewicz’s t-norm), from the formula of $\sigma_{L}$, see
(20), we have:

$\displaystyle\delta_{iji}^{T_{L}}$
$\displaystyle=\sigma_{L}(1-a_{ij},b_{i},a_{ij},b_{i})$
$\displaystyle=\min(b_{i},\max((b_{i}-a_{ij})^{+},\frac{(b_{i}-a_{ij}+a_{ij}-b_{i})^{+}}{2})$
$\displaystyle=\min(b_{i},(b_{i}-a_{ij})^{+})=(b_{i}-a_{ij})^{+}.$

∎

We establish the following equivalences:

######  Lemma 2.

Let $i\in N$ and $j\in M$ and we assume that $b_{i}\leq a_{ij}$. Then, for all
$k\in N$, we have:

  * •

for $T=T_{M}$ (min):

$\delta^{T}_{ijk}>0\Longleftrightarrow b_{i}>b_{k}\quad\text{and}\quad
a_{kj}>b_{k},$ (26)

  * •

for $T=T_{P}$ (product):

$\delta^{T}_{ijk}>0\Longleftrightarrow a_{ij}>0\quad\text{ and }\quad
a_{kj}>b_{k}\quad\text{ and
}\quad\dfrac{b_{i}}{a_{ij}}>\dfrac{b_{k}}{a_{kj}},$ (27)

  * •

for $T=T_{L}$ (Łukasiewicz’s t-norm):

$\delta^{T}_{ijk}>0\Longleftrightarrow b_{i}>0\quad\text{and}\quad
b_{i}-a_{ij}>b_{k}-a_{kj}.$ (28)

###### Proof.

For $T=T_{M}$, if $b_{i}\leq a_{ij}$ then
$\delta^{T}_{ijk}=\sigma_{G}(b_{i},a_{kj},b_{k})$. From the formula of
$\sigma_{G}$, see (15), we immediately deduce the equivalence.

For $T=T_{P}$, if $b_{i}\leq a_{ij}$ then
$\delta^{T}_{ijk}=\sigma_{GG}(a_{ij},b_{i},a_{kj},b_{k})=\max[(b_{i}-a_{ij})^{+},\min(\varphi(a_{ij},b_{i},a_{kj},b_{k}),(a_{kj}-b_{k})^{+})]=\min(\varphi(a_{ij},b_{i},a_{kj},b_{k}),(a_{kj}-b_{k})^{+})$.
Thus, we have:

$\delta^{T}_{ijk}>0\Longleftrightarrow\varphi(a_{ij},b_{i},a_{kj},b_{k})>0\quad\text{and}\quad
a_{kj}>b_{k}.$

We distinguish two cases when computing $\varphi(a_{ij},b_{i},a_{kj},b_{k})$:
it returns $\frac{(b_{i}\cdot a_{kj}-a_{ij}\cdot b_{k})^{+}}{a_{ij}+a_{kj}}$
if $a_{ij}>0$ or it returns $b_{i}$ if $a_{ij}=0$ (see its definition in
(18)). To have $\varphi(a_{ij},b_{i},a_{kj},b_{k})>0$, we must have
$a_{ij}>0$, as if $a_{ij}=0$, we have
$\varphi(a_{ij},b_{i},a_{kj},b_{k})=b_{i}$ which would be equal to zero since
we suppose $b_{i}\leq a_{ij}$. Finally, the inequality
$\dfrac{b_{i}}{a_{ij}}>\dfrac{b_{k}}{a_{kj}}$ is equivalent to the strict
positivity of $\frac{(b_{i}\cdot a_{kj}-a_{ij}\cdot
b_{k})^{+}}{a_{ij}+a_{kj}}$ (we have $a_{ij}+a_{kj}>0$).

For $T=T_{L}$, we have
$\delta^{T}_{ijk}=\sigma_{L}\,(1-a_{ij},b_{i},a_{kj},b_{k})=\min(b_{i},\max((b_{i}-a_{ij})^{+},\frac{(b_{i}-a_{ij}+a_{kj}-b_{k})^{+}}{2})).$
Since $b_{i}\leq a_{ij}$, we have
$\delta^{T}_{ijk}=\min(b_{i},\frac{(b_{i}-a_{ij}+a_{kj}-b_{k})^{+}}{2})$ and
we immediately deduce the equivalence. ∎

From (Notation 2), we give the formula of the Chebyshev distance associated to
the subsystem $(S_{R}):A_{R}\Box_{T}^{\max}x=b_{R}$:

######  Lemma 3.

For any non-empty subset $R\subseteq\\{1,2,\dots,n\\}$:

  1. 1.

The Chebyshev distance associated to the subsystem $(S_{R})$ is:

$\Delta_{R}=\max_{i\in R}\min_{1\leq j\leq m}\max_{k\in R}\delta^{T}_{ijk}.$
(29)

  2. 2.

We have the following equivalence:

$(S_{R}):A_{R}\Box_{T}^{\max}x=b_{R}\text{ consistent
}\quad\Longleftrightarrow\quad\forall i\in R\,\exists j\in M\,\text{ such that
}\max_{k\in R}\delta^{T}_{ijk}=0.$

The proof of this lemma is easy using (21) and (23).
Let us illustrate this result with the subsystems reduced to a single
equation:

######  Example 4.

For all $i\in\\{1,2,\dots,n\\}$, we have, see (Lemma 1):

$(S_{\\{i\\}}):A_{\\{i\\}}\Box_{T}^{\max}x=b_{\\{i\\}}\text{ consistent
}\Longleftrightarrow\exists j\in M\text{ such that
}\delta^{T}_{iji}=(b_{i}-a_{ij})^{+}=0.$

##  4 Find a maximal consistent subsystem of an inconsistent system of
$\max-T$ fuzzy relational equations

Let us take a non-empty subset $R\subseteq N$ and assume that the subsystem
$(S_{R}):A_{R}\Box_{T}^{\max}x=b_{R}$ is consistent (Notation 2). For an index
$i$ of an equation which is in the intersection of the set $R$ and the
complement $\overline{N_{c}}$ of the set $N_{c}$, see (25), we establish four
important results ((Lemma 4), (Lemma 5), (Lemma 6) and (Proposition 1)).

Finally, we show our main result (Theorem 1), which allows us to obtain a
canonical maximal consistent subsystem of an inconsistent system $(S)$ by
computing the Chebyshev distance of the system $(S)$.

######  Lemma 4.

Let $i\in R\cap\overline{N_{c}}$. Then, we have:

$\forall j\in M,\quad\max_{k\in N}\delta^{T}_{ijk}>0,$ (30) $\exists j\in
M,\quad\max_{k\in R}\delta^{T}_{ijk}=0.$ (31)

###### Proof.

If $i\notin N_{c}$, it means that $\delta_{i}=\min_{j\in M}\max_{k\in
N}\delta^{T}_{ijk}>0$, from which we establish (30). From (29), we also deduce
(31). ∎

######  Lemma 5.

Let $i\in R\cap\overline{N_{c}}$ and $j\in M$ and we assume that:

$\max_{k\in R}\delta^{T}_{ijk}=0.$ (32)

Then, we have:

  1. 1.

$b_{i}\leq a_{ij}$.

  2. 2.

There exists $k_{1}\in\overline{R}$ such that $\delta^{T}_{ijk_{1}}>0.$

###### Proof.

Let us take $k=i$ in (32), then we obtain $\delta^{T}_{iji}=0$. From (Lemma
1), we deduce that we have:

$\delta^{T}_{iji}=(b_{i}-a_{ij})^{+}=0.$

So $b_{i}\leq a_{ij}$.

We apply (30) to the index $j\in M$ and we obtain:

$\max_{k\in N}\delta^{T}_{ijk}>0.$

By taking into account (32), we then deduce that there exists an index
$k_{1}\in\overline{R}$ such that $\delta^{T}_{ijk_{1}}>0.$ ∎

######  Lemma 6.

Let an index $i\in R\cap\overline{N_{c}}$ and an index $j\in M$ satisfy (32).
For any index $k_{1}\in\overline{R}\cap\overline{N_{c}}$ such that
$\delta^{T}_{ijk_{1}}>0$, there exists an index $k_{2}\in\overline{R}$ such
that:

$\delta^{T}_{ijk_{1}}>0,\quad\delta^{T}_{k_{1}jk_{2}}>0,\quad\delta^{T}_{ijk_{2}}>0,\quad
k_{1}\not=k_{2}.$

###### Proof.

From (Lemma 5), we have $b_{i}\leq a_{ij}$. An index $k_{1}\notin N_{c}$ means
that $\forall l\in M,\,\,\max_{k\in N}\delta^{T}_{k_{1}lk}>0$.

By taking $l=j$, we obtain $\max_{k\in N}\delta^{T}_{k_{1}jk}>0.$

Let $k_{2}\in N$ be such that $\delta^{T}_{k_{1}jk_{2}}>0$. Let us check for
each of the three t-norms that we have:

$k_{1}\not=k_{2},\quad\delta^{T}_{ijk_{2}}>0,\quad k_{2}\in\overline{R}.$

  * •

For $T=T_{M}$ (min), as we have $b_{i}\leq a_{ij}$, then by applying (26) to
$\delta^{T}_{ijk_{1}}>0$, we deduce:

$b_{i}>b_{k_{1}}\quad\text{and}\quad a_{k_{1}j}>b_{k_{1}}.$

The inequalities $a_{k_{1}j}>b_{k_{1}}$ and $\delta^{T}_{k_{1}jk_{2}}>0$ allow
us to apply (26) and we obtain:

$b_{k_{1}}>b_{k_{2}},\quad\quad a_{k_{2}j}>b_{k_{2}}.$

So $k_{1}\not=k_{2}$. As we now have:

$b_{i}>b_{k_{1}}>b_{k_{2}},\quad a_{k_{1}j}>b_{k_{1}},\quad
a_{k_{2}j}>b_{k_{2}}.$

and also $b_{i}\leq a_{ij}$ , we deduce from (26) that we have
$\delta^{T}_{ijk_{2}}>0$.

As, by hypothesis, we have $\max_{k\in R}\delta^{T}_{ijk}=0$, we necessarily
have $k_{2}\in\overline{R}$.

  * •

For $T=T_{P}$ (product), by applying (27) to $\delta^{T}_{ijk_{1}}>0$, we
obtain:

$a_{ij}>0,\quad
a_{k_{1}j}>b_{k_{1}},\quad\dfrac{b_{i}}{a_{ij}}>\dfrac{b_{k_{1}}}{a_{k_{1}j}}.$

The inequality $a_{k_{1}j}>b_{k_{1}}$ allows us to apply (27) to
$\delta^{T}_{k_{1}jk_{2}}>0$ and to obtain:

$a_{k_{1}j}>0,\quad
a_{k_{2}j}>b_{k_{2}},\quad\dfrac{b_{k_{1}}}{a_{k_{1}j}}>\dfrac{b_{k_{2}}}{a_{k_{2}j}}.$

So $k_{1}\not=k_{2}$. Furthermore, we deduce from the previous inequalities:

$a_{ij}>0,\quad
a_{k_{2}j}>b_{k_{2}},\quad\dfrac{b_{i}}{a_{ij}}>\dfrac{b_{k_{1}}}{a_{k_{1}j}}>\dfrac{b_{k_{2}}}{a_{k_{2}j}}.$

By applying (27) (we also have $b_{i}\leq a_{ij}$), we obtain
$\delta^{T}_{ijk_{2}}>0$. As, by hypothesis, we have $\max_{k\in
R}\delta^{T}_{ijk}=0$, we necessarily have $k_{2}\in\overline{R}$.

  * •

For $T=T_{L}$ (Łukasiewicz’s t-norm), by applying (28) to
$\delta^{T}_{ijk_{1}}>0$, we obtain:

$b_{i}>0,\quad b_{i}-a_{ij}>b_{k_{1}}-a_{k_{1}j}.$

The inequality $b_{k_{1}}-a_{k_{1}j}<b_{i}-a_{ij}\leq 0$ allows us to apply
(28) to $\delta^{T}_{k_{1}jk_{2}}>0$ and we obtain:

$b_{k_{1}}>0,\quad b_{k_{1}}-a_{k_{1}j}>b_{k_{2}}-a_{k_{2}j}.$

So $k_{1}\not=k_{2}$. Furthermore, we deduce from the previous inequalities:

$b_{i}>0,\quad b_{i}-a_{ij}>b_{k_{1}}-a_{k_{1}j}>b_{k_{2}}-a_{k_{2}j}.$

By applying (28), we obtain $\delta^{T}_{ijk_{2}}>0$. As by hypothesis, we
have $\max_{k\in R}\delta^{T}_{ijk}=0$, we necessarily have
$k_{2}\in\overline{R}$.

∎

The following statement will be very useful to prove our main result:

######  Proposition 1.

We assume that $N_{c}\subseteq R$. Let $i\in R\cap\overline{N_{c}}$ and $j\in
M$ satisfy (32). For any integer $p\geq 1$, we can find a set of indexes
$\\{k_{1},k_{2}\dots,k_{p}\\}\subseteq\overline{R}$ verifying:

$\text{card}\,(\\{k_{1},k_{2}\dots,k_{p}\\})=p\,\,\text{ and
}\,\,\delta^{T}_{ijk_{1}}>0,\,\,\delta^{T}_{ijk_{p}}>0,\text{ and for all
}\,\,l\in\\{1,2,\dots,p-1\\},\,\,\delta^{T}_{k_{l}jk_{l+1}}>0.$ (33)

###### Proof.

We will prove this result by induction on $p$.
For $p=1$, this follows immediately from (Lemma 5).
For $p=2$, let us take an index $k_{1}\in\overline{R}$ satisfying
$\delta_{ijk_{1}}^{T}>0$ and as $\overline{R}\subseteq\overline{N_{c}}$, we
deduce, by applying (Lemma 6), an index $k_{2}\in\overline{R}$ such that the
set $\\{k_{1},k_{2}\\}$ satisfy (33).

Assume that we have constructed a set
$\\{k_{1},k_{2},\dots,k_{p-1}\\}\subseteq\overline{R}$ such that:

$\text{card}(\\{k_{1},k_{2},\dots,k_{p-1}\\})=p-1\text{ and
}\delta^{T}_{ijk_{1}}>0,\,\,\delta^{T}_{ijk_{p-1}}>0,\text{ and for all
}\,\,l\in\\{1,2,\dots,p-2\\},\,\,\delta^{T}_{k_{l}jk_{l+1}}>0.$

Let us prove the existence of an index $k_{p}$ such that the set
$\\{k_{1},k_{2},\dots,k_{p-1},k_{p}\\}$ satisfy (33). We have to prove:

$k_{p}\in\overline{R},\,\,\text{card}\,(\\{k_{1},k_{2}\dots,k_{p}\\})=p\,\,\text{
and }\,\,\delta_{k_{p-1}jk_{p}}^{T}>0\,\,\text{ and
}\,\,\delta_{ijk_{p}}^{T}>0.$

As we have $k_{p-1}\in\overline{R}$ and
$\overline{R}\subseteq\overline{N_{c}}$ we have:

$\delta_{k_{p-1}}=\min_{l\in M}\max_{h\in N}\delta_{k_{p-1}lh}^{T}>0.$

For $l=j$, we deduce:

$\max_{h\in N}\delta_{k_{p-1}jh}^{T}>0.$

Let us take an index $k_{p}\in N$ such that $\delta_{k_{p-1}jk_{p}}^{T}>0$.
Let us remark that if we prove that $\delta_{ijk_{p}}^{T}>0$, by (32), we
conclude that $k_{p}\in\overline{R}$.
Let us check for each of the three t-norms the remaining conditions:
$\text{card}\,(\\{k_{1},k_{2}\dots,k_{p}\\})=p$ and $\delta_{ijk_{p}}^{T}>0$.

  * •

For $T=T_{M}$ (min), by the recurrence hypothesis, we apply $p-1$ times the
equivalence (26) and we obtain:

$b_{i}>b_{k_{1}}>b_{k_{2}}>\dots>b_{k_{p-1}}\text{ and
}a_{k_{p-1}j}>b_{k_{p-1}}.$ (34)

As we have $b_{k_{p-1}}<a_{k_{p-1}j}$, we can apply (26) to
$\delta_{k_{p-1}jk_{p}}^{T_{M}}>0$ and we obtain:

$b_{k_{p-1}}>b_{k_{p}}\text{ and }a_{k_{p}j}>b_{k_{p}}.$ (35)

Then, from (34) we deduce
$b_{i}>b_{k_{1}}>b_{k_{2}}>\dots>b_{k_{p-1}}>b_{k_{p}}$ and
$a_{k_{p}j}>b_{k_{p}}$.
So $\text{card}\,(\\{k_{1},k_{2}\dots,k_{p}\\})=p$. As we have $b_{i}\leq
a_{ij}$ (Lemma 5), we conclude that $\delta_{ijk_{p}}^{T_{M}}>0$.

  * •

For $T=T_{P}$ (product), by the recurrence hypothesis, we apply $p-1$ times
the equivalence (27) and we obtain:

$\frac{b_{i}}{a_{ij}}>\frac{b_{k_{1}}}{a_{k_{1}j}}>\dots>\frac{b_{k_{p-1}}}{a_{k_{p-1}j}}\text{
and }a_{ij}>0,\text{ for all }l\in\\{1,2,\dots,p-2\\},a_{k_{l}j}>0,\text{ and
}a_{k_{p-1}j}>b_{k_{p-1}}.$ (36)

As we have $b_{k_{p-1}}<a_{k_{p-1}j}$, we can apply (27) to
$\delta_{k_{p-1}jk_{p}}^{T_{P}}>0$ and we obtain:

$\frac{b_{k_{p-1}}}{a_{k_{p-1}j}}>\frac{b_{k_{p}}}{a_{k_{p}j}}\text{ and
}a_{k_{p}j}>b_{k_{p}}.$ (37)

Then, from (36) we deduce
$\frac{b_{i}}{a_{ij}}>\frac{b_{k_{1}}}{a_{k_{1}j}}>\frac{b_{k_{2}}}{a_{k_{2}j}}>\dots>\frac{b_{k_{p-1}}}{a_{k_{p-1}j}}>\frac{b_{k_{p}}}{a_{k_{p}j}}$
and $a_{k_{p}j}>b_{k_{p}}$.
So $\text{card}\,(\\{k_{1},k_{2}\dots,k_{p}\\})=p$. As we have $b_{i}\leq
a_{ij}$ (Lemma 5), we conclude that $\delta_{ijk_{p}}^{T_{P}}>0$.

  * •

For $T=T_{L}$ (Łukasiewicz’s t-norm), by the recurrence hypothesis, we apply
$p-1$ times the equivalence (28) and we obtain:

${b_{i}}-{a_{ij}}>{b_{k_{1}}}-{a_{k_{1}j}}>\dots>{b_{k_{p-1}}}-{a_{k_{p-1}j}}\text{
and }b_{i}>0,\text{ for all }l\in\\{1,2,\dots,p-2\\},b_{k_{l}}>0.$ (38)

As we have $b_{k_{p-1}}-{a_{k_{p-1}j}}<{b_{i}}-{a_{ij}}\leq 0$, we can apply
(28) to $\delta_{k_{p-1}jk_{p}}^{T_{L}}>0$ and we obtain:

${b_{k_{p-1}}}-{a_{k_{p-1}j}}>{b_{k_{p}}}-{a_{k_{p}j}}.$ (39)

Then, from (38) we deduce
${b_{i}}-{a_{ij}}>{b_{k_{1}}}-{a_{k_{1}j}}>{b_{k_{2}}}-{a_{k_{2}j}}>\dots>{b_{k_{p-1}}}-{a_{k_{p-1}j}}>{b_{k_{p}}}-{a_{k_{p}j}}$
and $b_{i}>0$.
So $\text{card}\,(\\{k_{1},k_{2}\dots,k_{p}\\})=p$ and by (28) we have
$\delta_{ijk_{p}}^{T_{L}}>0$.

∎

We now prove our main result:

######  Theorem 1.

Assume that there is at least one equation of index $i$ that is solvable
independently of the others, i.e., there is a subsystem reduced to a single
equation $(S_{\\{i\\}})$ that is consistent. Then, we have:

  1. 1.

The set $N_{c}$ is non-empty ($N_{c}\not=\emptyset$).

  2. 2.

The system $(S_{N_{c}}):A_{N_{c}}\Box_{T}^{\max}x=b_{N_{c}}$ is consistent.

  3. 3.

Among the consistent subsystems $(S_{R}):A_{R}\Box_{T}^{\max}x=b_{R}$ of the
system $(S):A\Box_{T}^{\max}x=b$ with $R\subseteq\\{1,2,\dots,n\\}$, the
consistent subsystem $(S_{N_{c}}):A_{N_{c}}\Box_{T}^{\max}x=b_{N_{c}}$ is
maximal in the following sense: any subsystem defined by a strict superset of
$N_{c}$ is inconsistent.

The third statement of the above theorem means that for any non-empty subset
$R\subseteq\\{1,2,\dots,n\\}$, we have:

$\text{ The system }(S_{R})\text{ is consistent and }N_{c}\subseteq
R\Longrightarrow N_{c}=R.$

We begin by proving the second statement, and we will then prove the first and
third statements simultaneously.

###### Proof.

$\bullet$ Proof of the second statement (assuming that $N_{c}\not=\emptyset$).

To prove that the subsystem $(S_{N_{c}})$ is consistent, we must show that
$\Delta_{N_{c}}=0$, see (Lemma 3), which means that for any $i\in N_{c}$,
there is an index $j\in M$ such that $\max_{k\in N_{c}}\delta^{T}_{ijk}=0$.

Let an index $i\in N_{c}$. We have:

$\delta_{i}=\min_{j\in M}\max_{k\in N}\delta^{T}_{ijk}=0.$

We can easily deduce that there is an index $j\in M$ such that:

$0=\max_{k\in N}\delta^{T}_{ijk}\geq\max_{k\in N_{c}}\delta^{T}_{ijk}.$

$\bullet$ Proof of the first and third statement.

Let $R\subseteq N$ be a non-empty set such that $\text{the system
}(S_{R})\text{ is consistent and }N_{c}\subseteq R$. We will show the equality
$N_{c}=R$.

In particular, if we take $R=\\{i\\}$ and we suppose that the subsystem
$(S_{R})$ is consistent, then we trivially have $\emptyset\subset R$, thus
$N_{c}\not=\emptyset$.

Let us show that $N_{c}=R$ by contradiction.

Assume that we have $N_{c}\subset R$. Let an index $i\in
R\cap\overline{N_{c}}$.

By (Lemma 4), we can take an index $j\in M$ verifying (32):

$\max_{k\in R}\delta^{T}_{ijk}=0.$

Then by (Proposition 1), we conclude that for any integer $p\geq 1$, we have
$p\leq\text{card}({\overline{R}})$, which is a contradiction.

We have proven that $N_{c}=R$. ∎

Consequently, the computational complexity for obtaining the maximal
consistent subsystem $(S_{N_{c}})$ of an inconsistent system $(S)$ is the same
as that for computing the Chebyshev distance $\Delta$.

######  Example 5.

(continued) We reuse the matrix $A$ and the vector $b$ of (Example 1), see
(7).

  * •

For the $\max-\min$ system $A\Box_{\min}^{\max}x=b$, its unique maximal
consistent subsystem is the system itself, since the system
$A\Box_{\min}^{\max}x=b$ is consistent and therefore $N_{c}=\\{1,2,3,4\\}$.

  * •

For the inconsistent max-product system $A\Box_{T_{P}}^{\max}x=b$ and the
inconsistent max-Łukasiewicz system $A\Box_{T_{L}}^{\max}x=b$, we have
$N_{c}=\\{1,3,4\\}$. So the system
$(S_{N_{c}}):A_{N_{c}}\Box_{T_{P}}^{\max}x=b_{N_{c}}$ is a maximal consistent
subsystem of the system $A\Box_{T_{P}}^{\max}x=b$ and the system
$(S_{N_{c}}):A_{N_{c}}\Box_{T_{L}}^{\max}x=b_{N_{c}}$ is a maximal consistent
subsystem of the system $A\Box_{T_{L}}^{\max}x=b$. For each inconsistent
system, we obtain a consistent subsystem of it by removing the equation whose
index is $2$.

##  5 Method for easily finding all consistent subsystems of an inconsistent
$\max-\min$ system

In this section, we give an efficient method for obtaining all consistent
subsystems of an inconsistent $\max-\min$ system. We begin by giving some
notations and establishing (Lemma 7). Based on this result, we introduce our
method (Subsection 5.3) which allows us to obtain, iteratively, all the
maximal consistent subsystems of an inconsistent system (Proposition 2).
Finally, we illustrate our method by an interesting example.

###  5.1 Notations

Let $(S):A\Box_{\min}^{\max}x=b$ be a $\max-\min$ system where
$A=[a_{ij}]_{{}1\leq i\leq n,1\leq j\leq m}$ and $b=[b_{i}]_{{}1\leq i\leq
n}$. We suppose that the coefficients of $b$ are ordered in ascending order,
i.e., we have:

$b_{1}\leq b_{2}\leq\dots\leq b_{n}.$ (40)

We reuse (Notation 2) i.e., for any subset $R\subseteq\\{1,2,\dots,n\\}$, we
form the following $\max-\min$ subsystem:
$(S_{R}):A_{R}\Box_{\min}^{\max}x=b_{R},$ where $A_{R}=[a_{ij}]_{i\in R,1\leq
j\leq m}\text{ and }b_{R}=[b_{i}]_{i\in R}$.

We compute the Chebyshev distance associated to the subsystem $(S_{R})$ by
(see (Lemma 3)):

$\Delta_{R}=\max_{i\in R}\delta^{R}_{i}\quad\text{ where
}\quad\delta_{i}^{R}=\min_{1\leq j\leq m}\max_{k\in R}\delta^{T_{M}}_{ijk}.$
(41)

We assume that each of the equations in the system $(S)$ is solvable
independently of the others, which means that all subsystems reduced to one
equation are consistent:

$\text{for all }i\in N,\text{ the system
}(S_{\\{i\\}}):A_{\\{i\\}}\Box_{\min}^{\max}x=b_{i}\text{ is consistent.}$
(42)

For all $s\in N$, we associate to the subsystem $(S_{\\{1,2,\dots,s\\}})$, the
following set:

$\mathcal{E}^{s}=\bigg{\\{}R\in
2^{\\{1,2,\dots,s\\}}\,\mid\,(S_{R}):A_{R}\Box_{\min}^{\max}x=b_{R}\quad\text{is
consistent}\bigg{\\}}.$ (43)

The set $\mathcal{E}^{s}$ is non-empty since, from (42), all singletons
$\\{1\\},\\{2\\},\cdots,\\{s\\}$ are in $\mathcal{E}^{s}$.

###  5.2 Preliminary result

The following result allows us to construct, from a consistent subsystem of
$(S_{\\{1,2,\dots,s\\}})$ a consistent subsystem with a larger number of
equations, if it is possible.

######  Lemma 7.

Let $1\leq s<n-1$ be fixed and consider a subset of equation indexes
$R\in{\cal E}^{s}$ which allows us to form a consistent subsystem of
$(S_{\\{1,2,\dots,s\\}})$. For any $k\in N$ such that $k>s$, we put the
following subset $\widehat{R}_{k}=R\cup\\{k\\}$ and we have (using the formula
(41)):

  1. 1.

$\forall i\in R\,,\,\delta^{\widehat{R}_{k}}_{i}=0$,

  2. 2.

The subsystem $(S_{\widehat{R}_{k}})$ is a consistent subsystem
$\Longleftrightarrow\delta^{\widehat{R}_{k}}_{k}=0.$

###### Proof.

It suffices to prove the first statement.

Let $i\in R$, we have $i<k$, so $b_{i}\leq b_{k}$ and for all $l\in M$, we
have:

$\sigma_{G}(b_{i},a_{kl},b_{k})=\min(\dfrac{(b_{i}-b_{k})^{+}}{2},(a_{kl}-b_{k})^{+})=0.$

Since $\Delta_{R}=0$, let $j\in M$ be such that $\max_{k^{\prime}\in
R}\delta^{T_{M}}_{ijk^{\prime}}=0$.
From $k^{\prime}=i\in R$ and (Lemma 1), we deduce
$0=\delta^{T_{M}}_{iji}=(b_{i}-a_{ij})^{+}$.
From (24) and the inequality $b_{i}\leq b_{k}$, we obtain:

$\delta^{T_{M}}_{ijk}=\sigma_{G}(b_{i},a_{kj},b_{k})=0.$

Finally, we obtain from (41):

$\displaystyle\delta^{\widehat{R}_{k}}_{i}$
$\displaystyle\leq\max_{k^{\prime}\in\widehat{R}_{k}}\delta^{T_{M}}_{ijk^{\prime}}$
$\displaystyle=\max(\max_{k^{\prime}\in
R}\delta^{T_{M}}_{ijk^{\prime}},\delta^{T_{M}}_{ijk})$ $\displaystyle=0.$

∎

###  5.3 Method for finding all consistent subsystems of an inconsistent
$\max-\min$ system

We will now introduce our method, which allows us to build for $1\leq s\leq
n-1$ the set $\mathcal{E}^{s+1}$ from the set $\mathcal{E}^{s}$. Trivially, we
have $\mathcal{E}^{1}=\bigg{\\{}\\{1\\}\bigg{\\}}$.
For $1\leq s\leq n-1$ the set $\mathcal{E}^{s+1}$ is given by:

${\cal E}^{s+1}={\cal
E}^{s}\cup\bigg{\\{}\\{s+1\\}\bigg{\\}}\cup\bigg{\\{}\widehat{R}\mid R\in{\cal
E}^{s},\widehat{R}=R\cup\\{s+1\\},\text{ and
}\delta^{\widehat{R}}_{s+1}=0\bigg{\\}}.$ (45)

The equality (45) is easily deduced from (Lemma 7).
Algorithmically, the main step to deduce ${\cal E}^{s+1}$ from ${\cal E}^{s}$
consists in computing the $\text{card}({\cal E}^{s})$ numbers
$\delta^{\widehat{R}}_{s+1}=\min_{1\leq j\leq
m}\max_{k\in\widehat{R}}\delta^{T_{M}}_{s+1jk}$. From the set
$\mathcal{E}^{n}$ we get all the consistent subsystems of the system $(S)$.

Starting from a consistent subsystem $(S_{R})$ of the system
$(S_{\\{1,\dots,s\\}})$ that we suppose to be maximal among the consistent
subsystems of the system $(S_{\\{1,\dots,s\\}})$, we characterize in which
case $(S_{R})$ is a maximal consistent subsystem of the whole system $(S)$.

######  Proposition 2.

Let $1\leq s<n-1$ and $R\subseteq\\{1,\dots,s\\}$. We suppose that the
subsystem $(S_{R})$ is a maximal consistent subsystem of
$(S_{\\{1,\dots,s\\}})$. Then we have:

$(S_{R})\,\,\text{is a maximal consitent subsystem of the
system}\,\,(S)\Longleftrightarrow\forall
k\in\\{s+1,\dots,n\\},\,\,\delta^{\widehat{R}_{k}}_{k}>0.$ (46)

###### Proof.

The proof of the implication $\Longrightarrow$ follows directly from (Lemma
7). In fact, for any $k\in\\{s+1,\dots,n\\}$ we have
$R\subset\widehat{R}_{k}=R\cup\\{k\\}$. The maximality of the subsystem
$(S_{R})$ implies the non-consistency of the subsystem
$(S_{\widehat{R}_{k}})$, thus $\delta^{\widehat{R}_{k}}_{k}>0$.

To prove the implication $\Longleftarrow$, let $U\subseteq N$ such that the
subsystem $(S_{U})$ is consistent and $R\subseteq U$, we must prove the
equality $R=U$.
By assumption, if $U$ satisfies the inclusion $U\subseteq\\{1,2,\dots,s\\}$,
then we conclude that $R=U$.

Let us prove the inclusion $U\subseteq\\{1,2,\dots,s\\}$ by contradiction.

Suppose that there is an index $k\in\\{s+1,\dots,n\\}\cap U$. Then we have:

$R\subset\widehat{R}_{k}\subseteq U,\quad\widehat{R}_{k}=R\cup\\{k\\}.$

From the consistency of the subsystem $(S_{U})$, we deduce that the subsystem
$(S_{\widehat{R}_{k}})$ is consistent. By applying (Lemma 7), we obtain
$\delta^{\widehat{R}_{k}}_{k}=0$ and then a contradiction. ∎

We can then obtain, iteratively, all the maximal consistent subsystems of the
whole inconsistent system. (Example 6) shows that two maximal consistent
subsystems do not necessarily have the same cardinality.

######  Example 6.

Let the system $A\Box_{\min}^{\max}x=b$ be defined by:

$A=\begin{bmatrix}0.98&0.02&0.10\\\ 0.80&0.31&0.18\\\ 0.78&0.38&0.26\\\
0.77&0.20&0.85\\\ \end{bmatrix}\text{ and }b=\begin{bmatrix}0.13\\\ 0.28\\\
0.54\\\ 0.70\\\ \end{bmatrix}.$

We have $b_{1}<b_{2}<b_{3}<b_{4}$ and each subsystem reduced to a single
equation is consistent i.e., for all $i\in\\{1,2,3,4\\}$, $\text{ the system
}(S_{\\{i\\}}):A_{\\{i\\}}\Box_{\min}^{\max}x=b_{i}\text{ is consistent.}$

We start from $\mathcal{E}^{1}=\bigg{\\{}\\{1\\}\bigg{\\}}$. We have:

  * •

$\mathcal{E}^{2}=\bigg{\\{}\\{1\\},\\{2\\},\\{1,2\\}\bigg{\\}}$,

  * •

$\mathcal{E}^{3}=\bigg{\\{}\\{1\\},\\{2\\},\\{3\\},\\{1,2\\}\bigg{\\}}$,

  * •

$\mathcal{E}^{4}=\bigg{\\{}\\{1\\},\\{2\\},\\{3\\},\\{4\\},\\{1,2\\},\\{1,4\\},\\{2,4\\},\\{3,4\\},\\{1,2,4\\}\bigg{\\}}$.

So, $\\{3,4\\}$ and $\\{1,2,4\\}$ are the two subsets of indexes describing
the maximal consistent subsystems of the inconsistent $\max-\min$ system.

Our method is much faster than checking, using (6), the consistency of each of
the subsystems $(S_{R})$ of $(S)$ one by one.

##  6 Conclusion

In this article, we studied the inconsistency of systems of $\max-T$ fuzzy
relational equations of the form $A\Box_{T}^{\max}x=b$, where $T$ is a t-norm
among $\min$, product or Łukasiewicz’s t-norm. By computing the Chebyshev
distance $\Delta=\inf_{c\in\mathcal{C}}\|b-c\|$ associated to the second
member $b$ of an inconsistent $\max-T$ system where $\mathcal{C}$ is the set
of second members of consistent systems defined with the same matrix $A$,
using the analytical formulas given in [2, 3], we showed in (Theorem 1) that
we can directly find a canonical maximal consistent subsystem of this
inconsistent system. We showed that the computational complexity for obtaining
this maximal consistent subsystem is the same as that required for computing
$\Delta$.

For an inconsistent $\max-\min$ system, we introduced a method for efficiently
obtaining all the consistent subsystems of this system. The method is based on
the formula of $\Delta$ for $\max-\min$ systems and allows us to obtain,
iteratively, all the maximal consistent systems of the considered inconsistent
system. For the moment, we have not attempted to adapt this method to the
cases of $\max-$product and $\max-$Łukasiewicz compositions.

This work may be useful for solving inconsistency issues in $\max-T$ systems
involved in $\max-T$ learning methods, such as the paradigm of [3] for
$\max-\min$ learning weight matrices according to training data, learning the
rule parameters for possibilistic rule-based systems [1, 3] or learning
associate memories [16]. It can also be useful for applications based on
$\max-T$ systems, e.g. spatial analysis [6], diagnostic problems [8].

## References

  * Baaj [2022] Ismaïl Baaj.  Learning rule parameters of possibilistic rule-based system.  In _2022 IEEE International Conference on Fuzzy Systems (FUZZ-IEEE)_ , pages 1–8. IEEE, 2022.
  * Baaj [2023a] Ismaïl Baaj.  Chebyshev distances associated to the second members of systems of Max-product/Lukasiewicz Fuzzy relational equations.  _arXiv e-prints_ , art. arXiv:2302.08554, January 2023a.  doi:10.48550/arXiv.2302.08554.
  * Baaj [2023b] Ismaïl Baaj.  Max-min Learning of Approximate Weight Matrices from Fuzzy Data.  _arXiv e-prints_ , art. arXiv:2301.06141, January 2023b.  doi:10.48550/arXiv.2301.06141.
  * Cechlárová and Dikoxe [1999] Katarína Cechlárová and Pavel Dikoxe.  Resolving infeasibility in extremal algebras.  _Linear algebra and its applications_ , 290(1-3):267–273, 1999.
  * Cuninghame-Green and Cechlárová [1995] RA Cuninghame-Green and Katarína Cechlárová.  Residuation in fuzzy algebra and some applications.  _Fuzzy Sets and Systems_ , 71(2):227–239, 1995\.
  * Di Martino and Sessa [2011] Ferdinando Di Martino and Salvatore Sessa.  Spatial analysis and fuzzy relation equations.  _Advances in Fuzzy Systems_ , 2011:6–6, 2011.
  * Di Nola et al. [1984] Antonio Di Nola, Witold Pedrycz, Salvatore Sessa, and Wang Pei Zhuang.  Fuzzy relation equation under a class of triangular norms: A survey and new results.  _Stochastica_ , 8(2):99–145, 1984.
  * Dubois and Prade [1995] Didier Dubois and Henri Prade.  Fuzzy relation equations and causal reasoning.  _Fuzzy sets and systems_ , 75(2):119–134, 1995\.
  * Klement et al. [2013] Erich Peter Klement, Radko Mesiar, and Endre Pap.  _Triangular norms_ , volume 8.  Springer Science & Business Media, 2013.
  * Li [2009] Pingke Li.  _Fuzzy Relational Equations: Resolution and Optimization_.  PhD thesis, North Carolina State University, 2009.
  * Miyakoshi and Shimbo [1985] Masaaki Miyakoshi and Masaru Shimbo.  Solutions of composite fuzzy relational equations with triangular norms.  _Fuzzy Sets and Systems_ , 16(1):53–63, 1985\.
  * Pedrycz [1982] Witold Pedrycz.  Fuzzy relational equations with triangular norms and their resolutions.  _Busefal_ , 11:24–32, 1982.
  * Pedrycz [1985] Witold Pedrycz.  On generalized fuzzy relational equations and their applications.  _Journal of mathematical Analysis and applications_ , 107(2):520–536, 1985.
  * Sanchez [1976] Elie Sanchez.  Resolution of composite fuzzy relation equations.  _Information and control_ , 30(1):38–48, 1976\.
  * Sanchez [1977] Elie Sanchez.  Solutions in composite fuzzy relation equations: Application to medical diagnosis in brouwerian logic.  In M. M. Gupta, G. N. Saridis, and B. R. Gaines, editors, _Fuzzy automata and decision processes_ , pages 221–234. Amsterdam: North-Holland, 1977\.
  * Sussner and Valle [2006] Peter Sussner and Marcos Eduardo Valle.  Implicative fuzzy associative memories.  _IEEE Transactions on Fuzzy Systems_ , 14(6):793–807, 2006.


EPJ Web of Conferences Lattice2017  11institutetext: Swansea Academy of
Advanced Computing, Swansea University, Singleton Park, Swansea, SA2 8PP, UK
22institutetext: Department of Physics, Pusan National University, Busan
46241, Korea 33institutetext: Extreme Physics Institute, Pusan National
University, Busan 46241, Korea 44institutetext: Institute of Physics, National
Chiao-Tung University, Hsinchu 30010, Taiwan 55institutetext: Department of
Mathematics, Swansea University, Singleton Park, Swansea, SA2 8PP, UK
66institutetext: Department of Physics, Swansea University, Singleton Park,
Swansea, SA2 8PP, UK

# Higgs compositeness in $\mathrm{Sp}(2N)$ gauge theories —
Resymplecticisation, scale setting and topology

Ed Bennett Speaker, Funded by the Supercomputing Wales project, which is part-
funded by the European Regional Development Fund (ERDF) via Welsh
Government.11<EMAIL_ADDRESS>Deog Ki Hong Supported in part by
Korea Research Fellowship program funded by the Ministry of Science, ICT and
Future Planning through the National Research Foundation of Korea
(2016H1D3A1909283) and under the framework of international cooperation
program (NRF-2016K2A9A1A01952069).22 Jong-Wan Lee33footnotemark: 3 2233 C.-J.
David Lin Supported by Taiwanese MoST grant 105-2628-M-009-003-MY444
Biagio Lucini Supported in part by the Royal Society and the Wolfson
Foundation.Supported in part by the STFC Consolidated Grants ST/L000369/1 and
ST/P00055X/1.55 Maurizio Piai66footnotemark: 6 66 Davide
Vadacchino22footnotemark: 266footnotemark: 6 11

###### Abstract

As part of an ongoing programme to study $\mathrm{Sp}(2N)$ gauge theories as
potential realisations of composite Higgs models, we consider the case of
$\mathrm{Sp}(4)$ on the lattice, both as a pure gauge theory, and with two
Dirac fermion flavors in the fundamental representation. In order to compare
results between these two cases and maintain control of lattice artefacts, we
make use of the gradient flow to set the scale of the simulations. We present
some technical aspects of the simulations, including preliminary results for
the scale setting in the two cases and results for the topological charge
history.

##  1 Introduction

Due to its significant potential phenomenological interest, we have embarked
on an extended programme to study $\mathrm{Sp}(2N)$ gauge theories, as
described in more detail in biagiojongwan . In this contribution we report on
some of the technical details of the study to date.

In the current, exploratory phase of the study, we have first used the heat
bath algorithm to study the quenched $\mathrm{Sp}(4)$ theory, including its
glueball spectrum (described in davide ) and the quenched meson spectrum,
which we have fitted to an effective field theory (described in biagiojongwan
). We have then implemented the Hybrid Monte Carlo (HMC) algorithm for
dynamical fermions in the $\mathrm{Sp}(4)$ gauge theory, which will be
described in the first half of this contribution, along with a discussion of
the resymplecticisation procedure used for the heat bath algorithm. An
exploration of the phase structure of the dynamical theory, and preliminary
results for its spectroscopy, are presented in biagiojongwan . We then set the
scale of the theories using the gradient flow scales $t_{0}$ and $w_{0}$, and
verify the ergodicity of the topological charge and observe the topological
susceptibility, the discussion of which forms the second half of this
contribution.

##  2 Lattice action and the HMC algorithm

In davide ; biagiojongwan , we have presented results from the pure gauge
$\mathrm{Sp}(4)$ theory, which we use in biagiojongwan  to perform fits to
Effective Field Theory (EFT). For this purpose, we were able to use the heat
bath algorithm, due to its high ergodicity and computational efficiency.
However, we ultimately intend to perform simulations with dynamical fermions,
in order to fully understand the behaviour near the chiral limit. In this case
the heat bath algorithm is no longer sufficient, and we instead make use of
the HMC algorithm. We must therefore adapt the algorithm to work with the
$\mathrm{Sp}(4)$ gauge group.

As in davide , we use the Wilson gauge action; to this we add the Wilson
fermion action. The molecular dynamics portion of the HMC update evolves the
motion under the gauge force

$F_{\textnormal{G}}^{A}(x,\mu)=\frac{\beta}{4}\frac{1}{T_{F}}\operatorname{Re}\operatorname{tr}_{c}\left[iT^{A}U_{\mu}(x)V_{\mu}^{\dagger}(x)\right]\;,$
(1)

where $V_{\mu}(x)$ is the sum of the forward and backward staples around the
link $U_{\mu}(x)$, and $T^{A}$ are the generators of the $\mathrm{Sp}(4)$
gauge group. The update then proceeds as detailed in DelDebbio:2008tv .

##  3 Resymplecticisation

(a) With reunitarisation only.. (b) With resymplecticisation.

Figure 1: The time history of the plaquette for $N_{\textnormal{f}}=2$,
$\beta=8.0$, $m=1.0$, with and without making use of the resymplecticisation
procedure described in the text. In orange is the value obtained in
Holland:2003kg . The green line in the right panel corresponds to the average
of the data set.

Since the HMC algorithm is implemented in a computer which operates at finite
precision, it is possible that as the simulation progresses, the group
elements will diverge out of the group unless a constraint is applied. In
simulations of $\mathrm{SU}(N)$ theories, this constraint is known as
reunitarisation. When reunitarisation is applied to the $\mathrm{Sp}(4)$
theory, the result shown in Fig. 2(a) is obtained; equilibrium is reached
after a handful of updates, but the simulation slowly drifts away. It is
likely that if left for longer, the result would converge on that of
$\mathrm{SU}(4)$. Thus we require a procedure to return the group element back
to the $\mathrm{Sp}(4)$ group after each update.

To do this, we represent an $\mathrm{Sp}(4)$ matrix as:

$\displaystyle Q(x,\mu)$
$\displaystyle=Q_{0}(x,\mu)\otimes\mathbb{I}_{2}+Q_{1}(x,\mu)\otimes
e_{1}+Q_{2}(x,\mu)\otimes e_{2}+Q_{3}(x,\mu)\otimes e_{3}\;,$ (2)

where

$\displaystyle\mathbb{I}_{2}$ $\displaystyle=\left(\begin{array}[]{cc}1&0\\\
0&1\end{array}\right),$ $\displaystyle e_{1}$
$\displaystyle=\left(\begin{array}[]{cc}i&0\\\ 0&-i\end{array}\right),$
$\displaystyle e_{2}$ $\displaystyle=\left(\begin{array}[]{cc}0&1\\\
-1&0\end{array}\right),$ $\displaystyle e_{3}$
$\displaystyle=\left(\begin{array}[]{cc}0&i\\\ i&0\end{array}\right).$ (11)

Projecting a matrix that may have deviated from $\mathrm{Sp}(4)$ onto this
basis will give a matrix which is once again an element of $\mathrm{Sp}(4)$.
When this is done after every update, the MC history of the plaquette looks as
in Fig. 2(b). In both cases the result is for heavy, but not quenched,
fermions; as might be expected, the average plaquette in the stable case is
close but not identical to the quenched result of Holland:2003kg .

For the pure gauge calculations, an alternative procedure was used, derived
from the (modified) Gram–Schmidt algorithm. Noting that a general
$\mathrm{Sp}(2N)$ matrix $U_{ij}$ is overconstrained, then if elements
$U_{ij}$, $i\in[1,N]$, $\forall j$ are known, then the remainder may be
calculated as

$U_{i+N,j}=-\Omega U_{ij}^{*}\;,$ (12)

where $\Omega$ is the symplectic matrix

$\Omega=\left(\begin{array}[]{cccc}0&0&1&0\\\ 0&0&0&1\\\ -1&0&0&0\\\
0&-1&0&0\end{array}\right)\;.$ (13)

Thus after normalising the elements $U_{1,j}$, the elements $U_{N+1,j}$ can be
calculated. By orthonormalising with respect to both of these sets of
elements, then $U_{2,j}$ may be calculated, and the process repeats until a
full matrix is obtained, which is then guaranteed to be in $\mathrm{Sp}(2N)$.

##  4 Gradient flow

In order to draw comparisons between data at different values of $\beta$ and
$N_{\textnormal{f}}$, it is necessary to set a scale, in order to remove the
dependence on the unknown lattice spacing $a$ from results. This can be done
by rescaling to common units, most easily by making use of the gradient flow,
as popularised by Martin Lüscher Luscher:2010iy . A flow is defined starting
on the gauge field $\left.B_{\mu}\right|_{t=0}=A_{\mu}$ as generated by the
Monte Carlo method, and evolving under the diffusion equation
$\dot{B}_{\mu}=D_{\nu}G_{\nu\mu}$, where
$G_{\mu\nu}=\partial_{\mu}B_{\nu}-\partial_{\nu}B_{\mu}\left[B_{\mu},B_{\nu}\right]$,
and $D_{\mu}=\partial_{\mu}+\left[B_{\mu},\frac{\partial}{\partial t}\right]$.

In terms of lattice observables, this takes the form

$\displaystyle\frac{\partial V_{\mu}(t,x)}{\partial t}$
$\displaystyle=-g_{0}^{2}\left\\{\partial_{x,\mu}S_{\textnormal{latt.}}[V_{\mu}]\right\\}V_{\mu}(t,x)\;$
$\displaystyle V_{\mu}(0,x)$ $\displaystyle=U_{\mu}(x)\;,$ (14)

where $S_{\textnormal{latt.}}$ is the lattice action. This is discretised by
using a fourth-order Runge–Kutta integrator, and has the effect that at $t\neq
0$, observables are renormalised.

In principle, it would be possible for this discrete flow to introduce finite
precision errors causing the $V_{\mu}(t,x)$ to leave the group; for this
reason we added the resymplecticisation described in the previous section
after each flow step. This was however found to have no effect on the results,
so was disabled to improve the efficiency of the program.

(a) $\mathcal{E}(t)$ (b) $\mathcal{W}(t)$

Figure 2: History of the quantities $\mathcal{E}(t)$ and $\mathcal{W}(t)$ as a
function of the flow time $t$ for the pure gauge ensemble at $\beta=8.4$,
comparing the two different definitions of $\mathcal{E}$ described in the
text.

By considering the energy density
$E=-\frac{1}{2}\operatorname{tr}(G_{\mu\nu}G_{\mu\nu})$, a scale $t_{0}$ can
be extracted by finding the value of the flow time at which $\left.\langle
t^{2}E\rangle\right|_{t=t_{0}}=\mathcal{E}_{0}$, where $\mathcal{E}_{0}$ is a
reference value to be chosen. Alternatively, as proposed in Borsanyi:2012zs ,
one can take the time derivative, defining $w_{0}$ as
$\left.t\frac{\partial}{\partial t}\langle
t^{2}E\rangle\right|_{t=w_{0}^{2}}=\mathcal{W}_{0}$, with $\mathcal{W}_{0}$
again a reference value to be chosen. In each case the value of $t_{0}$,
$w_{0}$ has been assumed to have a very weak lattice spacing dependence in
physical units, thus any change in $t_{0}^{2}/a^{2}$, $w_{0}/a$ as a function
of $a$ results from the explicit $a$-dependence in the denominator.

Figure 3: The gradient flow scales $t_{0}$ and $w_{0}$ for the pure gauge
theory, showing a variety of possible values of
$\mathcal{E}_{0}=\mathcal{W}_{0}$ as indicated in the legend.

(a) (b)

Figure 4: The gradient flow scales $t_{0}$ and $w_{0}$ for the
$N_{\textnormal{f}}=2$ theory: (a) showing a variety of possible values of
$\mathcal{E}_{0}=\mathcal{W}_{0}$ as indicated in the legend, and (b) showing
the single value $\mathcal{E}_{0}=\mathcal{W}_{0}=0.35$, comparing with the
same case for the pure gauge theory at $\beta=7.7$ (green line).

There are two commonly-used discretisations for $E$: $E_{\textnormal{plaq.}}$
via the average plaquette, and $E_{\textnormal{sym.}}$ via the symmetric four-
plaquette clover. They must agree in the continuum limit, and thus
discrepancies between them are indicative of finite-lattice spacing artefacts.
As can be see in Fig. 2, the two show an initial discrepancy but reach
agreement after a short time; this has implications on our choice of
$\mathcal{E}_{0}$ and $\mathcal{W}_{0}$. This choice is explored in Figs. 3
and 4(a), showing how the choice affects $t_{0}$, $w_{0}$ in the pure gauge
theory and the $N_{\textnormal{f}}=2$ theory respectively. In the latter, we
show the closest agreement at $\mathcal{E}_{0}=\mathcal{W}_{0}=0.35$, which we
adopt for the subsequent discussion.

While $w_{0}$ agrees between the two definitions of $E$ at this value, the
values for $t_{0}$ do not. Figure 4(b) pulls out the detail for this choice,
showing the $N_{\textnormal{f}}=2$ results at $\beta=6.9$ (red points)
compared with the pure gauge result for $\beta=7.7$, the coarsest lattice
considered to give reliable results davide . Since $\sqrt{8t_{0}}/a$,
$w_{0}/a$ each have a $1/a$ dependence in lattice units, lower values indicate
coarser lattice spacings; thus the $N_{\textnormal{f}}=2$ results are
substantially coarser than the coarsest acceptable pure gauge ensemble,
explaining the divergence in the values of $t_{0}$. While the dynamical
results presented here are proof-of-concept, for future studies of dynamical
simulations, a higher value of $\beta$ will be needed to give an acceptably
fine lattice.

##  5 Topology

As the lattice extent is finite in all directions, a given configuration will
fall into one of a number of topological sectors, labelled by an integer (or,
at finite $a$, near-integer) topological charge $Q$, which is expected to have
a Gaussian distribution about zero. Since it is probabilistically unfavourable
to change a discrete global observable using a small local update, $Q$ can
show very long autocorrelations; as the continuum limit (i.e. the limit of
integer $Q$) is approached, $Q$ can “freeze”, ceasing to change at all.

It is necessary to check that $Q$ is not frozen, and instead moves
ergodically, for two reasons: firstly, the exponential autocorrelation time of
the Monte Carlo simulation as a whole scales as the longest autocorrelation
time in the system; this is likely to be that for $Q$. Secondly, the values of
physical observables depend on which topological sector a configuration is in
Brower:2003yx ; Galletly:2006hq ; sampling a single $Q$ or an unrepresentative
distribution of $Q$s will introduce an uncontrolled systematic error. It is
therefore necessary to verify that $Q$ not only moves sufficiently rapidly,
but also displays the expected Gaussian histogram.

(a) Pure gauge, $L=24$, $\beta=7.7$. $Q_{0}=-0.09\pm 0.32$; $\sigma=6.32\pm
0.32$. (b) $N_{\textnormal{f}}=2$, $L=16$, $\beta=6.9$, $m=-0.92$.
$Q_{0}=1.26\pm 0.97$; $\sigma=6.61\pm 0.98$.

Figure 5: Topological charge histories and histograms for the specified
ensembles.

$Q$ is computed on the lattice as

$\displaystyle Q$ $\displaystyle=\sum_{x}q(x)\;,$ where $\displaystyle
q(x)=\frac{1}{32\pi^{2}}\epsilon_{\mu\nu\rho\sigma}\operatorname{tr}\left\\{U_{\mu\nu}(x)U_{\rho\sigma}(x)\right\\}\,,$
(15)

and $x$ runs over all lattice sites. For gauge configurations generated by
Monte Carlo studies, this observable is dominated by ultraviolet fluctuations;
therefore it is necessary to perform some sort of smoothing to extract the
true value. The gradient flow, as described in the previous section, is used
for this purpose; the calculation of $Q$ is performed for near-zero cost as
the values of $E$ are calculated.

The topological charge history was plotted for all ensembles, including both
pure gauge and those with matter. In all cases, $Q$ was found to move with no
noticeable autocorrelation, and showed the expected Gaussian distribution
centred on $Q=0$, modulo relatively small statistics on some dynamical
ensembles. A sample of these histories are shown in Fig. 5.

Figure 6: The topological susceptibility of the pure gauge and flavoured
theories as a function of the gradient flow scale $w_{0}$.

It is also of interest to observe the topological susceptibility, defined as
$\chi=(\langle Q^{2}\rangle-\langle Q\rangle^{2})/V$; this is plotted as a
dimensionless ratio with the gradient flow $w_{0}$, as a function of $w_{0}$,
in Fig. 6. By comparison with Fig. 4, it is visible that in the heavy fermion
limit, the susceptibility does not approach that of the pure gauge theory. We
interpret this as a second symptom that $\beta=6.9$ is too coarse to obtain
reasonable data with $N_{\textnormal{f}}=2$ in this theory.

##  6 Conclusions

We have implemented the HMC algorithm for dynamical fermions in the
$\mathrm{Sp}(4)$ gauge theory, making use of a quaternion-based
resymplecticisation scheme. We have also implemented a modified Gram–Schmidt-
based resymplecticisation scheme for general $\mathrm{Sp}(2N)$, which we have
used for heat bath computations. We have then made use of the gradient flow to
study the scales $t_{0}$ and $w_{0}$, as well as the topological charge
distribution and susceptibility, for both the pure gauge theory at a variety
of values for $\beta$, and the dynamical theory with $N_{\textnormal{f}}=2$ at
$\beta=6.9$ as an initial proof of concept. The topological charge is found to
move well in all cases, although the statistics are relatively small in the
$N_{\textnormal{f}}=2$ cases. The flow scale $t_{0}$ is found to be self-
inconsistent depending on how it is calculated for $N_{\textnormal{f}}=2$,
indicating that $\beta=6.9$ is too far from the continuum, a conclusion that
is supported by the behaviour of the topological susceptibility. Tests of the
spectroscopy of the dynamical theory are shown in biagiojongwan ; the next
step in this programme of work is to expand the scope of the dynamical
simulations to production runs with larger volumes and statistics, at suitably
fine lattice spacings.

## Acknowledgements

We acknowledge the support of the Supercomputing Wales project, which is part-
funded by the European Regional Development Fund (ERDF) via Welsh Government.

## References

  * (1) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, _Higgs compositeness in $\mathrm{Sp}(2N)$ gauge theories — the low energy theory_, in _Proceedings,35th International Symposium on Lattice Field Theory (Lattice2017): Granada, Spain_, to appear in EPJ Web Conf.
  * (2) E. Bennett, D.K. Hong, J.W. Lee, C.J.D. Lin, B. Lucini, M. Piai, D. Vadacchino, _Higgs compositeness in $\mathrm{Sp}(2N)$ gauge theories — the pure gauge model_, in _Proceedings,35th International Symposium on Lattice Field Theory (Lattice2017): Granada, Spain_, to appear in EPJ Web Conf.
  * (3) L. Del Debbio, A. Patella, C. Pica, PoS LATTICE2008, 064 (2008), 0812.0570
  * (4) K. Holland, M. Pepe, U.J. Wiese, Nucl. Phys. B694, 35 (2004), hep-lat/0312022
  * (5) M. Lüscher, JHEP 08, 071 (2010), [Erratum: JHEP03,092(2014)], 1006.4518
  * (6) S. Borsanyi et al., JHEP 09, 010 (2012), 1203.4469
  * (7) R. Brower, S. Chandrasekharan, J.W. Negele, U.J. Wiese, Phys. Lett. B560, 64 (2003), hep-lat/0302005
  * (8) D. Galletly, M. Gurtler, R. Horsley, H. Perlt, P.E.L. Rakow, G. Schierholz, A. Schiller, T. Streuer, Phys. Rev. D75, 073015 (2007), hep-lat/0607024


# AI as mediator between composers, sound designers, and creative media
producers

Sebastian Löbbers  Centre for Digital Music, Queen Mary University of
LondonMile End Road, E1 4NSLondonUnited Kingdom<EMAIL_ADDRESS>,
Mathieu Barthet  Centre for Digital Music, Queen Mary University of LondonMile
End Road, E1 4NSLondonUnited Kingdom<EMAIL_ADDRESS>and  György Fazekas
Centre for Digital Music, Queen Mary University of LondonMile End Road, E1
4NSLondonUnited Kingdom<EMAIL_ADDRESS>
(2023; 22 February 2023)

###### Abstract.

Musical professionals who produce material for non-musical stakeholders often
face communication challenges in the early ideation stage. Expressing musical
ideas can be difficult, especially when domain-specific vocabulary is lacking.
This position paper proposes the use of artificial intelligence to facilitate
communication between stakeholders and accelerate the consensus-building
process. Rather than fully or partially automating the creative process, the
aim is to give more time for creativity by reducing time spent on defining the
expected outcome. To demonstrate this point, the paper discusses two
application scenarios for interactive music systems that are based on the
authors’ research into gesture-to-sound mapping.

gesture-to-sound mapping, AI mediated collaboration, human-human ideation

††copyright: acmcopyright††journalyear: 2023††conference: Make sure to enter
the correct conference title from your rights confirmation emai; April 28,
2023; Hamburg, Germany††booktitle: CHI ’23 Workshop: Integrating AI in Human-
Human Collaborative Ideation††ccs: Applied computing Sound and music
computing††ccs: Human-centered computing User interface programming††ccs:
Human-centered computing Collaborative and social computing devices

##  1\. Introduction

Composers and sound designers often work with, or for, people who do not have
expert musical knowledge. For example, a composer may work with a filmmaker or
choreographer to create an original score serving a narrative, and a sound
designer may be hired by a company to produce audio branding suiting their
corporate identity. In both situations, the two sides are likely to propose
and share ideas in an early exploratory stage to define more precisely what
the sounds or music should express. A potential bottleneck lies in the
imbalance in musical knowledge between the two parties. Individuals can have
strong opinions and preferences for sound and music but when questioned about
the underlying reasons, semantic descriptions differ between non-musicians and
musicians (Yang et al., 2021). Compared to non-experts, musicians tend to rely
on technical terms instead of everyday language which can be hard to decode
for a composer or sound designer. While technical language (e.g. “a piece in
the Lydian mode”) can express ideas to domain experts, it is opaque to other
stakeholders. In some cases, non-verbal forms of communication like gestures
or body movement might be preferred, e.g. when producers describe spatial
audio (Deacon et al., 2022). In practice, these difficulties are overcome by
sharing sound and music material that represents intended ideas and can be
referenced in the ideation process. However, this introduces two new issues:
(1) how is this material found? Stakeholders may use their own knowledge of
existing musical compositions (“internal” catalogue of music), but this
becomes less viable when searching for specific sounds; (2) despite having a
reference in mind, a composer or sound designer may create material that
ultimately does not suit the assignment. How can ideas be quickly adapted for
prototyping, e.g. fitting composed music to a film or choreography, to reduce
“wasted” work?

Recent advancements in artificial intelligence (AI) present new opportunities
for music professionals, for example by generating audio from text-prompts
(Agostinelli et al., 2023), creating guitar tablatures in a specific genre
(Sarmento et al., 2023), visualising sound intelligently (Garber et al., 2021)
or retrieving audio from graphical sketches (Engeln et al., 2021) and gestures
(Zbyszyński et al., 2021). However, AI research often focuses on the
optimisation of quantifiable metrics like audio quality or classification
accuracy, rather than exploring its role for application in the “real world”.
Reflecting on the authors’ own work that uses AI for gesture-to-sound
mappings, two potential applications are imagined to aid human-human music and
sound ideation. The paper shortly describes these applications in the next
section and discusses them in the context of the Integrating AI in Human-Human
Collaborative Ideation workshop in Section 3.

##  2\. Case studies

This section presents two interactive music systems, Liquid Dance and
SketchSynth, and explores their capabilities for collaborative music and sound
ideation in two hypothetical case studies that are based on the first author’s
experience as a professional composer and sound designer.

###  2.1. Liquid Dance

(a) Video still

(b) Flowchart

Figure 1. Liquid Dance overview. Demonstration available at
https://youtu.be/fYInCkaOZO8.

As illustrated in Figure 1, Liquid Dance uses motion capture and a fluid
particle simulation to quantify the intensity of dance movements and
automatically assemble musical snippets creating a suitable score in real-
time. It was developed in collaboration with a choreographer for the music AI
startup MXX111https://www.mxx.ai/ to showcase their intelligent music editing
software with an interactive performance. At a later stage, an unrelated
composition project for dance sparked the idea of using Liquid Dance for rapid
testing of musical ideas for choreography. This is described in the following
scenario:

A choreographer and music composer have chosen several reference music pieces
and are now interested in testing their compatibility with a choreographed
dance performance. To achieve this, they plan on using a system that will
enable them to dance alongside the music pieces, automatically selecting
segments that best match the intensity of the dance movements. By using this
method, they hope to gain a better understanding of how the selected music
will work in tandem with the choreography.

###  2.2. SketchSynth

(a) Video still

(b) Flowchart

Figure 2. SketchSynth overview. Demonstration available at
https://youtu.be/arSFt3iBAUM.

SketchSynth is based on the authors’ research into cross-modal perception of
musical timbre (Löbbers et al., 2021; Löbbers and Fazekas, 2022, 2023). It
employs AI and algorithmic methods to predict sound from a graphical sketch
input as illustrated in Figure 2. The following scenario describes a potential
application in industrial sound design:

A sound designer and product manager are looking for suitable sounds to
incorporate into their product. To facilitate this process, they plan on using
SketchSynth, which enables non-experts to express their ideas and explore the
sonic space through an intuitive mode of interaction. Both parties can
literally draw out ideas until reaching a consensus from which the sound
designer can elaborate in greater detail.

##  3\. Discussion and conclusion

In both case studies AI acts as a translator between non-verbal expression and
sound or music creation. While an expert human actor is likely capable of
creating suitable content from these expressions, a machine can be trained to
perform this task much faster in real-time. This gives stakeholders the
opportunity to test initial ideas much faster, focus on their interpersonal
relationships and leave more time for the creative process that is arguably
done best by a human professional. In this context, AI is seen strictly as a
tool that is expected to reliably perform a complex but well-defined task.
Liquid Dance uses a robust, but very specific setup that might only be useful
for a narrow type of projects; SketchSynth tries to find universal sketch-to-
sound mappings that might be too broad to communicate sound in sufficient
detail. As user needs are likely to change between or even during projects,
the scope of AI tools might have to change with them. This raises the question
of not only how AI is used during human-human ideation, but also how it is
trained and set up. One approach is to choose a model that was trained on a
diverse dataset to solve a large number of projects. However, this might hand
over too much agency leading to unexpected behaviour not suitable for the task
at hand. Therefore, a user might want to adjust a system in an initial
“briefing” stage to prepare for the upcoming task. Using the case studies in
this paper as an example: for SketchSynth this could mean confining the space
of possible sounds, e.g. to mechanic sounds for an electronic car project or
digital blips for a mobile game; or for Liquid Dance, optimising the interface
for a specific dance style, e.g. ballet or contemporary, and conditioning the
AI-driven music segmentation on a specific genre like classical or electronic
music. Ultimately, it remains for the user to define how much agency they want
their system to display during the ideation process. In conclusion, recent AI-
driven music research can find valuable application in aiding human-human
ideation for example as a translator for non-verbal descriptions of sound and
music. However, AI tools may have to be adjustable to user needs and project
requirements to avoid unpredictable or inadequate behaviour.

##  4\. Acknowledgments

EPSRC and AHRC Centre for Doctoral Training in Media and Arts Technology
(EP/L01632X/1).

## References

  * (1)
  * Agostinelli et al. (2023) Andrea Agostinelli, Timo I Denk, Zalán Borsos, Jesse Engel, Mauro Verzetti, Antoine Caillon, Qingqing Huang, Aren Jansen, Adam Roberts, Marco Tagliasacchi, et al. 2023\.  MusicLM: Generating Music From Text.  _arXiv preprint arXiv:2301.11325_ (2023).
  * Deacon et al. (2022) Thomas Deacon, Patrick Healey, and Mathieu Barthet. 2022\.  “It’s cleaner, definitely”: Collaborative Process in Audio Production.  _Computer Supported Cooperative Work (CSCW)_ (2022), 1–31.
  * Engeln et al. (2021) Lars Engeln, Nhat Long Le, Matthew McGinity, and Rainer Groh. 2021.  Similarity Analysis of Visual Sketch-based Search for Sounds.  In _Proceedings of Audio Mostly 2021_. Association for Computing Machinery, Trento, Italy, 101–108.  https://doi.org/10.1145/3478384.3478423
  * Garber et al. (2021) Leandro Garber, T Ciccola, and JC Amusategui. 2021\.  AudioStellar, an open source corpus-based musical instrument for latent sound structure discovery and sonic experimentation. In _Proceedings of International Computer Music Conference_. Michigan Publishing Services, Santiago, Chile, 62–67.  https://hdl.handle.net/2027/fulcrum.t435gg568
  * Löbbers et al. (2021) Sebastian Löbbers, Mathieu Barthet, and György Fazekas. 2021.  Sketching sounds: an exploratory study on sound-shape associations. In _Proceedings of International Computer Music Conference_. Michigan Publishing Services, Santiago, Chile, 299–304.  https://hdl.handle.net/2027/fulcrum.t435gg568
  * Löbbers and Fazekas (2022) Sebastian Löbbers and György Fazekas. 2022.  Seeing Sounds, Hearing Shapes: a gamified study to evaluate sound-sketches. In _Proceedings International Computer Music Conference_. Michigan Publishing Services, Limerick, Ireland, 174–179.  https://hdl.handle.net/2027/fulcrum.nk322g689
  * Löbbers and Fazekas (2023) Sebastian Löbbers and György Fazekas. 2023.  SketchSynth: cross-modal control of sound synthesis.  _EvoMUSART preprint_ (2023).  https://sebastianlobbers.com/static/76293e97d37a3d69941f2f1b047cec7e/SketchSynth_cross-modal_control_of_sound_synthesis.pdf
  * Sarmento et al. (2023) Pedro Sarmento, Adarsh Kumar, Yu-Hua Chen, CJ Carr, Zack Zukowski, and Mathieu Barthet. 2023\.  GTR-CTRL: Instrument and Genre Conditioning for Guitar-Focused Music Generation with Transformers.  _arXiv preprint arXiv:2302.05393_ (2023).
  * Yang et al. (2021) Simin Yang, Courtney Nicole Reed, Elaine Chew, and Mathieu Barthet. 2021.  Examining emotion perception agreement in live music performance.  _IEEE transactions on affective computing_ (2021).
  * Zbyszyński et al. (2021) Michael Zbyszyński, Balandino Di Donato, Federico Ghelli Visi, and Atau Tanaka. 2021.  Gesture-Timbre Space: Multidimensional Feature Mapping Using Machine Learning. In _Proceedings of International Symposium on Computer Music Multidisciplinary Research_. Springer, Tokyo, Japan, 600–622.  https://doi.org/10.1007/978-3-030-70210-6_39