# Characterization of Consistent Completion of Reciprocal Comparison Matrices

Authors: Julio Benítez; Laura Carrión; Joaquín Izquierdo; Rafael Pérez-García
Journal: Abstract and Applied Analysis
 (2014)

---

## Abstract

Analytic hierarchy process (AHP) is a leading multi-attribute decision-aiding model that is designed to help make better choices when faced with complex decisions involving several dimensions. AHP, which enables qualitative analysis using a combination of subjective and objective information, is a multiple criteria decision analysis approach that uses hierarchical structured pairwise comparisons. One of the drawbacks of AHP is that a pairwise comparison cannot be completed by an actor or stakeholder not fully familiar with all the aspects of the problem. The authors have developed a completion based on a process of linearization that minimizes the matrix distance defined in terms of the Frobenius norm (a strictly convex minimization problem). In this paper, we characterize when an incomplete, positive, and reciprocal matrix can be completed to become a consistent matrix. We show that this characterization reduces the problem to the solution of a linear system of equations—a straightforward procedure. Various properties of such a completion are also developed using graph theory, including explicit calculation formulas. In real decision-making processes, facilitators conducting the study could use these characterizations to accept an incomplete comparison body given by an actor or to encourage the actor to further develop the comparison for the sake of consistency.


---

## Body

## 1. Introduction

The so-called analytic hierarchy process (AHP) [1, 2] has been accepted as a leading multiattribute decision-aiding model both by practitioners and academicians, since it is designed to make better choices when faced with complex decisions involving several dimensions. As a multiple criteria decision analysis (MCDA) technique [3], AHP solves optimization discrete decision problems that involve choosing one of several alternatives. In many fields, decision making (DM) has become very complex due to a large number of alternatives and multiple goals that sometimes conflict with each other. The AHP approach, which enables qualitative analysis using a combination of subjective and objective information/data, is an MCDA approach that uses hierarchically structured pairwise comparisons.One of the weaknesses of AHP, which AHP shares with other decision models, comes from the fact that typically the input is static. In other words, users must provide all the preference data at the same time, and the criteria must be completely defined from the start. Nevertheless, changing scenarios are currently more than frequent, due to various sources of uncertainty, and pairwise comparison cannot be successfully completed when there are many alternatives to be considered and/or the comparison is required from an actor or stakeholder not fully familiar with all the aspects of the problem. The current trend toward greater interactive involvement of citizens in policy making is unavoidable and highly desirable. It is generally agreed that better decisions are implemented with less conflict and more success when they are driven by stakeholders [4]. Public participation is also likely to improve the quality of decisions; using a wider pool of knowledge and understanding can prevent obstacles that would obstruct effective implementation of a particular decision [5, 6].For example, environmental (field of expertise of the authors) projects and programs are likely to be more relevant, successful, and sustainable if their actors are involved in planning, implementation, and evaluation [7, 8]. Moreover, integrating water resource management is a reference framework for water management in many countries [9]. For example, the Water Framework Directive (WFD) [10] was enforced in Europe in 2000. Taking the example down a level in concretion, in [11] the authors describe a management model to address the main needs of an aquifer, with this being a problem of environmental, social and public policy; the relevant decisions are enriched, when incorporating the interests of the parties concerned, including academics, users, and administrators of the aquifer.However, some actors may not be completely familiar with one or more of the elements about which they have to issue their judgement or opinion. As a result, it is difficult to gather complete information about the preferences of such a stakeholder at a given moment. It seems reasonable to enable such actors to express their preferences several times at their own convenience. Meanwhile, partial results based on partial preference data may be generated from data collected at various times—and this data may eventually be consolidated when the information is complete. Based on a process of linearization [12] that minimizes a matrix distance defined in terms of the Frobenius norm (a strictly convex minimization problem based on the best one rank approximation) in [13] the authors have initiated a line towards a dynamic model of AHP by addressing the problem of adding new criteria or deleting obsolete criteria. In [14] this research line was extended to propose a framework that enables users to provide data on their preferences in a partial and/or incomplete way and at different times. The consistent completion of a reciprocal matrix as a mechanism to obtain a consistent body of opinion issued in an incomplete manner by a specific actor was addressed. This feature can help stakeholders not fully problem acquainted participate in processes.Public participation is, however, not a panacea. Collaboration and participation cannot solve every problem and should not be used as a surrogate for other systematic attempts to plan and manage decision issues [15, 16]. Public participation efforts must be responsive to the needs of the stakeholders. It is also critical to recognize that participation processes require a flexible approach that is appropriate to user conditions. As a result, the need to integrate multiple criteria and uncertainty demands a systematic framework to suitably represent and handle the information [17].In particular, uncertainty produced by a lack of comprehensive knowledge on the part of the stakeholders must be handled suitably. In a real participatory DM process, the facilitator in charge of conducting the study may have to face an incomplete body of opinion given by an actor. In this event, he or she needs robust criteria to either accept the opinion or encourage the actor to further develop the comparison so that the judgment is eventually completed consistently, thus helping ensure an optimal decision.In this paper, we provide a solution to this issue by solving the following problem: to characterize when an incomplete, positive, reciprocal matrix can be completed to become a consistent matrix. If the incomplete judgment given by an actor passes this test, then the facilitator will feel confident about accepting it. Otherwise, the facilitator should keep on working with the actor until the characterization criterion is met. We show that this characterization reduces the consistent completion of an incomplete, positive, reciprocal matrix to the solution of a linear system of equations—a straightforward procedure. In addition, the uniqueness of the completion is studied using graph theory and we offer several ways to find such completion when it exists.This paper is organized as follows. In Section2 we give a formal statement of the problem and provide some prerequisites. Sections 3 and 4, respectively, address the main objectives of the paper, namely, the characterization and the uniqueness, together with the computation of the consistent completion (when it exists). In Section 5, these results are applied to two comparison matrices for deciding suitable leakage policies within the framework of water supply management. Section 6 contains the conclusions and closes the paper.


## 2. Prerequisites and Formal Statement of the Problem

### 2.1. A Brief Review of AHP

AHP [1, 2, 18] is a multiple attribute decision method that uses structured pairwise comparisons with numerical judgements from an absolute scale of numbers. The fundamentals of AHP, including its hierarchical, multilevel structure with goals, criteria, and alternatives, the way in which judgement is compiled into positive reciprocal matrices, the estimation of the relative weights of the decision elements, the use of prioritization techniques, and the way in which aggregation is performed to obtain a final composite vector of priorities, can be found in any handbook and many papers about the subject (see, e.g., [1, 17, 18]).In this paper, we consider a nine-point scale developed by Saaty [1, 2], with the possibility of including intermediate numerical values on this scale. Thus, as a result of the comparison performed, an n×n matrix A=(aij), is formed, with n being the number of the decision elements and aij measuring the relative importance of element i over element j. To extract priority vectors from the comparison matrices, the eigenvector method, which was first proposed by Saaty in his seminal paper [1], is used in this paper.A comparison matrix,A, exhibits a basic property, namely reciprocity:
(1)aij=1aji,∀i,j∈{1,…,n}.
This property implies the homogeneity: if elements i and j are considered equally important, then aij=1. In particular, one has aii=1.Definition 1.
Ann×n matrix A is reciprocal when aij>0 for any i,j and the condition (1) is satisfied.In addition to the reciprocity property, another property, consistency, should theoretically be desirable for a comparison matrix.Definition 2.
Ann×n matrix A is consistent when aij>0 for any i,j and
(2)aijajk=aik,∀i,j,k∈{1,…,n}
is satisfied.Consistency expresses the coherence that may exist between judgements about the elements of a set. Since preferences are expressed in a subjective manner it is reasonable for some kind of incoherence to exist. When dealing with intangibles, judgements are rarely consistent unless they are forced in some artificial manner.In addition, a comparison matrix is not generally consistent because it contains comparison values obtained through numerical judgement using a fixed scale. For most problems, estimates of these values by an expert are assumed to be small perturbations of the “right” values. This implies small perturbations for the eigenvalues and eigenvectors (see, e.g., [19]). For a consistent matrix A, the leading eigenvalue and the principal (Perron) eigenvector of A provide information to deal with complex decisions, with the normalized Perron eigenvector giving the sought priority vector [18]. In the general case, however, as said, A is not consistent. For nonconsistent matrices, the problem to solve is the eigenvalue problem Aw=λmax⁡w, where λmax⁡ is the unique largest eigenvalue of A that gives the Perron eigenvector as an estimate of the priority vector.


### 2.2. Notations and Basic Facts

The set ofn×m real matrices is denoted by ℝn,m. We write ℝn,m+={A=(aij)∈ℝn,m:aij>0foralli,j}. If A is a matrix, then tr⁡(A) and AT will denote the trace and the transpose of A, respectively. The standard basis of ℝn is denoted by {e1,…,en}. Any vector of ℝn will be considered a column. The vector (1,…,1)T∈ℝn will be denoted by 1n.As can be seen from (1) and (2), any consistent matrix is reciprocal. Also, it can be easily proven that the rank of any consistent matrix is 1.We will use the mappingsL:ℝn,m+→ℝn,m and E:ℝn,m→ℝn,m+ given by L(A)=(log⁡(aij)) and E(A)=(exp⁡(aij)), respectively, where A=(aij). Evidently, for A∈ℝn,n+,
(3)Aisreciprocal⟺L(A)isskewsymmetric.
The image by L of the set of consistent matrices will play an important role in the sequel. Precisely, we define
(4)ℒn={L(A):A∈ℝn,n+isconsistent}.
A basic property of ℒn is established in the next result.Theorem 3 (Theorem 2.2 of [12] ).
If we define(5)ϕn:ℝn⟶ℝn,n,ϕn(v)=v1nT-1nvT,
then ϕn is linear, ker⁡ϕn=span⁡{1n}, Im⁡ϕn=ℒn, and dim⁡ℒn=n-1.


### 2.3. Problem Definition

The purpose of this paper is to characterize when a reciprocal and incomplete matrix can be completed to become a consistent matrix. We state the precise formulation of the completion problem.Problem 4.
Letn∈ℕ and 1≤i1,j1,…,iq,jq≤n be such that ir<jr for r=1,…,q. Let α1,…,αq be given positive numbers. Can we find a consistent matrix A=(aij)∈ℝn,n+ such that airjr=αr and ajrir=-αr for any r=1,…,q? In case that the answer to this question is affirmative, find all matrices A verifying the condition of the aforementioned question.Although the following result can be dealt by means of the general characterization given in Theorem7, we will prove it using Theorem 3.Theorem 5.
LetA∈ℝn,n+. The following statements are equivalent: (i)
There existA1∈ℝn,m+, A2∈ℝm,n+, and A3∈ℝm,m+ such that B=[AA1A2A3] is consistent.(ii)
A is consistent.Proof.
(i)⇒ (ii): since B is consistent, the relations given in (2) hold for all indices and in particular for a subset of them.
(ii)⇒ (i): if A is consistent, then, by Theorem 3, there exists u∈ℝn such that L(A)=u1nT-1nuT. Let w be an arbitrary vector of ℝm, and define v∈ℝn+m in such a way that vT=[uTwT]. Let us define
(6)A1=E(u1mT-1nwT),A2=E(w1nT-1muT),A3=E(w1mT-1mwT),B=[AA1A2A3].
We get
(7)L(B)=[u1nT-1nuTu1mT-1nwTw1nT-1muTw1mT-1mwT],=[uw][1nT1mT]-[1n1m][uTwT].
Hence L(B)=v1n+mT-1n+mvT, showing that B is consistent.Observe that the proof of the former theorem enables us to give the general solution of the following problem: find all consistent completions of the matrix(8)B=[A⋆⋯⋆⋆1⋯⋆⋮⋮⋱⋮⋆⋆⋯1]∈ℝn+m,n+m,
where A∈ℝn,n is consistent. Since A is consistent, there exists u∈ℝn such that L(A)=ϕn(u). It is now enough to pick any w∈ℝm and define B as in (6).To motivate the notation and the precise definition of the problem considered in this paper, let us consider the following example. Let(9)A=[123⋆1213413131⋆⋆14⋆1].
By taking logarithms of the entries of the matrix, the aforementioned completion problem can be managed. Since the image by L of any reciprocal matrix is skew symmetric, in order to find a consistent completion of an incomplete reciprocal matrix, it is enough to restrict ourselves to the subset of reciprocal matrices of order n. From (9) we obtain
(10)L(A)=[0log⁡2log⁡3⋆-log⁡20log⁡3log⁡4-log⁡3-log⁡30⋆⋆-log⁡4⋆0],
then any skew symmetric completion of L(A) is of the form
(11)C(λ,μ)=[0log⁡2log⁡3λ-log⁡20log⁡3log⁡4-log⁡3-log⁡30μ-λ-log⁡4-μ0]=[0log⁡2log⁡30-log⁡20log⁡3log⁡4-log⁡3-log⁡3000-log⁡400]+λ[000100000000-1000]+μ[00000000000100-10],
where λ,μ∈ℝ.From now on, we define for1≤i<j≤n the following skew symmetric matrices
(12)Bij=eiejT-ejeiT.
Thus, with this notation, the skew symmetric completion considered in equalities (9), (10), and (11) takes the simpler form
(13)C(λ,μ)=C0+λB14+μB34,
where
(14)C0=[0log⁡2log⁡30-log⁡20log⁡3log⁡4-log⁡3-log⁡3000-log⁡400].
Furthermore, observe that matrix C0 appearing in (13) can be written as
(15)C0=∑(i,j)∈N4∖{(1,4),(3,4)}‍ρijBij,
where Nn={(i,j):1≤i<j≤n} and ρij are real numbers that can be easily determined from the incomplete matrix A given in (9). In an informal way, we can think of C0 as the incomplete skew symmetric matrix to be completed, and (1,4), and (3,4)—and their symmetric positions with respect to the principal diagonal—as the void positions that must be filled.We need the following lemma [14].Lemma 6.
Let the matricesBij be defined as in (12) and let the mapping ϕn be defined as in (5). Then
(16)tr⁡(BpqTBij)={2if(p,q)=(i,j),0if(p,q)≠(i,j),tr⁡(BijTϕn(v))=2(ei-ej)Tv
for anyv∈ℝn.


## 2.1. A Brief Review of AHP

AHP [1, 2, 18] is a multiple attribute decision method that uses structured pairwise comparisons with numerical judgements from an absolute scale of numbers. The fundamentals of AHP, including its hierarchical, multilevel structure with goals, criteria, and alternatives, the way in which judgement is compiled into positive reciprocal matrices, the estimation of the relative weights of the decision elements, the use of prioritization techniques, and the way in which aggregation is performed to obtain a final composite vector of priorities, can be found in any handbook and many papers about the subject (see, e.g., [1, 17, 18]).In this paper, we consider a nine-point scale developed by Saaty [1, 2], with the possibility of including intermediate numerical values on this scale. Thus, as a result of the comparison performed, an n×n matrix A=(aij), is formed, with n being the number of the decision elements and aij measuring the relative importance of element i over element j. To extract priority vectors from the comparison matrices, the eigenvector method, which was first proposed by Saaty in his seminal paper [1], is used in this paper.A comparison matrix,A, exhibits a basic property, namely reciprocity:
(1)aij=1aji,∀i,j∈{1,…,n}.
This property implies the homogeneity: if elements i and j are considered equally important, then aij=1. In particular, one has aii=1.Definition 1.
Ann×n matrix A is reciprocal when aij>0 for any i,j and the condition (1) is satisfied.In addition to the reciprocity property, another property, consistency, should theoretically be desirable for a comparison matrix.Definition 2.
Ann×n matrix A is consistent when aij>0 for any i,j and
(2)aijajk=aik,∀i,j,k∈{1,…,n}
is satisfied.Consistency expresses the coherence that may exist between judgements about the elements of a set. Since preferences are expressed in a subjective manner it is reasonable for some kind of incoherence to exist. When dealing with intangibles, judgements are rarely consistent unless they are forced in some artificial manner.In addition, a comparison matrix is not generally consistent because it contains comparison values obtained through numerical judgement using a fixed scale. For most problems, estimates of these values by an expert are assumed to be small perturbations of the “right” values. This implies small perturbations for the eigenvalues and eigenvectors (see, e.g., [19]). For a consistent matrix A, the leading eigenvalue and the principal (Perron) eigenvector of A provide information to deal with complex decisions, with the normalized Perron eigenvector giving the sought priority vector [18]. In the general case, however, as said, A is not consistent. For nonconsistent matrices, the problem to solve is the eigenvalue problem Aw=λmax⁡w, where λmax⁡ is the unique largest eigenvalue of A that gives the Perron eigenvector as an estimate of the priority vector.


## 2.2. Notations and Basic Facts

The set ofn×m real matrices is denoted by ℝn,m. We write ℝn,m+={A=(aij)∈ℝn,m:aij>0foralli,j}. If A is a matrix, then tr⁡(A) and AT will denote the trace and the transpose of A, respectively. The standard basis of ℝn is denoted by {e1,…,en}. Any vector of ℝn will be considered a column. The vector (1,…,1)T∈ℝn will be denoted by 1n.As can be seen from (1) and (2), any consistent matrix is reciprocal. Also, it can be easily proven that the rank of any consistent matrix is 1.We will use the mappingsL:ℝn,m+→ℝn,m and E:ℝn,m→ℝn,m+ given by L(A)=(log⁡(aij)) and E(A)=(exp⁡(aij)), respectively, where A=(aij). Evidently, for A∈ℝn,n+,
(3)Aisreciprocal⟺L(A)isskewsymmetric.
The image by L of the set of consistent matrices will play an important role in the sequel. Precisely, we define
(4)ℒn={L(A):A∈ℝn,n+isconsistent}.
A basic property of ℒn is established in the next result.Theorem 3 (Theorem 2.2 of [12] ).
If we define(5)ϕn:ℝn⟶ℝn,n,ϕn(v)=v1nT-1nvT,
then ϕn is linear, ker⁡ϕn=span⁡{1n}, Im⁡ϕn=ℒn, and dim⁡ℒn=n-1.


## 2.3. Problem Definition

The purpose of this paper is to characterize when a reciprocal and incomplete matrix can be completed to become a consistent matrix. We state the precise formulation of the completion problem.Problem 4.
Letn∈ℕ and 1≤i1,j1,…,iq,jq≤n be such that ir<jr for r=1,…,q. Let α1,…,αq be given positive numbers. Can we find a consistent matrix A=(aij)∈ℝn,n+ such that airjr=αr and ajrir=-αr for any r=1,…,q? In case that the answer to this question is affirmative, find all matrices A verifying the condition of the aforementioned question.Although the following result can be dealt by means of the general characterization given in Theorem7, we will prove it using Theorem 3.Theorem 5.
LetA∈ℝn,n+. The following statements are equivalent: (i)
There existA1∈ℝn,m+, A2∈ℝm,n+, and A3∈ℝm,m+ such that B=[AA1A2A3] is consistent.(ii)
A is consistent.Proof.
(i)⇒ (ii): since B is consistent, the relations given in (2) hold for all indices and in particular for a subset of them.
(ii)⇒ (i): if A is consistent, then, by Theorem 3, there exists u∈ℝn such that L(A)=u1nT-1nuT. Let w be an arbitrary vector of ℝm, and define v∈ℝn+m in such a way that vT=[uTwT]. Let us define
(6)A1=E(u1mT-1nwT),A2=E(w1nT-1muT),A3=E(w1mT-1mwT),B=[AA1A2A3].
We get
(7)L(B)=[u1nT-1nuTu1mT-1nwTw1nT-1muTw1mT-1mwT],=[uw][1nT1mT]-[1n1m][uTwT].
Hence L(B)=v1n+mT-1n+mvT, showing that B is consistent.Observe that the proof of the former theorem enables us to give the general solution of the following problem: find all consistent completions of the matrix(8)B=[A⋆⋯⋆⋆1⋯⋆⋮⋮⋱⋮⋆⋆⋯1]∈ℝn+m,n+m,
where A∈ℝn,n is consistent. Since A is consistent, there exists u∈ℝn such that L(A)=ϕn(u). It is now enough to pick any w∈ℝm and define B as in (6).To motivate the notation and the precise definition of the problem considered in this paper, let us consider the following example. Let(9)A=[123⋆1213413131⋆⋆14⋆1].
By taking logarithms of the entries of the matrix, the aforementioned completion problem can be managed. Since the image by L of any reciprocal matrix is skew symmetric, in order to find a consistent completion of an incomplete reciprocal matrix, it is enough to restrict ourselves to the subset of reciprocal matrices of order n. From (9) we obtain
(10)L(A)=[0log⁡2log⁡3⋆-log⁡20log⁡3log⁡4-log⁡3-log⁡30⋆⋆-log⁡4⋆0],
then any skew symmetric completion of L(A) is of the form
(11)C(λ,μ)=[0log⁡2log⁡3λ-log⁡20log⁡3log⁡4-log⁡3-log⁡30μ-λ-log⁡4-μ0]=[0log⁡2log⁡30-log⁡20log⁡3log⁡4-log⁡3-log⁡3000-log⁡400]+λ[000100000000-1000]+μ[00000000000100-10],
where λ,μ∈ℝ.From now on, we define for1≤i<j≤n the following skew symmetric matrices
(12)Bij=eiejT-ejeiT.
Thus, with this notation, the skew symmetric completion considered in equalities (9), (10), and (11) takes the simpler form
(13)C(λ,μ)=C0+λB14+μB34,
where
(14)C0=[0log⁡2log⁡30-log⁡20log⁡3log⁡4-log⁡3-log⁡3000-log⁡400].
Furthermore, observe that matrix C0 appearing in (13) can be written as
(15)C0=∑(i,j)∈N4∖{(1,4),(3,4)}‍ρijBij,
where Nn={(i,j):1≤i<j≤n} and ρij are real numbers that can be easily determined from the incomplete matrix A given in (9). In an informal way, we can think of C0 as the incomplete skew symmetric matrix to be completed, and (1,4), and (3,4)—and their symmetric positions with respect to the principal diagonal—as the void positions that must be filled.We need the following lemma [14].Lemma 6.
Let the matricesBij be defined as in (12) and let the mapping ϕn be defined as in (5). Then
(16)tr⁡(BpqTBij)={2if(p,q)=(i,j),0if(p,q)≠(i,j),tr⁡(BijTϕn(v))=2(ei-ej)Tv
for anyv∈ℝn.


## 3. Characterization of the Completion of a Reciprocal Matrix

Now we are ready to establish the first main result of this paper. In the statement of the next theorem we use two sets of indices of matrixA, I, and J. The unspecified entries of A above the main diagonal will be located at the indices belonging to I. For example, for the matrix A given in (9) we have I={(1,4),(3,4)} and J=N4∖I.Theorem 7.
Let1≤i1,j1,…,ik,jk≤n be indices such that ir<jr for r=1,…,k. Denote I={(i1,j1),…,(ik,jk)} and J=Nn∖I. Let C0=∑(i,j)∈J‍ρijBij. The following statements are equivalent.(i)
There existλ1,…,λk∈ℝ such that C0+∑r=1k‍λrBirjr∈ℒn.(ii)
There existsw=(w1,…,wn)T∈ℝn such that w1+⋯+wn=0 and ρpq=wp-wq for any (p,q)∈J.(iii)
There existsw=(w1,…,wn)T∈ℝn such that ρpq=wp-wq for any (p,q)∈J. Furthermore, in the case that the statements hold, then
(17)λr=wir-wjr,∀r∈{1,…,k}.Proof.
(i)⇒ (ii): by Theorem 3, there exists v∈ℝn such that
(18)∑(i,j)∈J‍ρijBij+∑r=1k‍λrBirjr=ϕn(v).
Note that any vector and in particular v can be splitted as v=α1n+w, where α∈ℝ and w is orthogonal to 1n. Here we assume that the inner product in ℝn is the standard inner product; that is, 〈x,y〉=xTy. Hence, if w=(w1,…,wn)T, then w1+⋯+wn=0. By Theorem 3 we obtain ϕn(v)=ϕn(w). Let us recall that the trace is a linear operator. If (p,q)∈J, then (18) and Lemma 6 yield
(19)ρpq=(ep-eq)Tw=wp-wq.
Let r∈{1,…,k}. We obtain from (18) and Lemma 6(20)λr=(eir-ejr)Tw=wir-wjr.
(ii)⇒ (iii) is trivial.
(iii)⇒ (i): let us define λr=wir-wjr for any r∈{1,…,k} and
(21)R=∑(i,j)∈J‍ρijBij+∑r=1k‍λrBirjr-ϕn(w).
Observe that from Lemma 6 one has
(22)if(p,q)∈J,thentr⁡(BpqTR)=2ρpq-2(wp-wq)=0ifr∈{1,…,k},thentr⁡(BirjrTR)=2λr-2(wir-wjr)=0.
Let us now recall the following.(a)
ϕn(w) is skew symmetric. This fact can be easily deduced from (5) by proving ϕn(v)T=-ϕn(v). Hence (21) and the fact that any Bij is also skew symmetric prove that R is skew symmetric.(b)
The setℝn,n can be endowed with the inner product 〈M,N〉=tr⁡(MTN).(c)
The matricesBij for 1≤i<j≤n form a basis for the subset of ℝn,n composed of skew symmetric matrices.
Previous item (c) and implications (22) lead to the fact that R is orthogonal to any skew symmetric matrix. By previous item (a) we obtain 〈R,R〉=0. Thus, R=0. Hence, by Theorem 3, we obtain C0+∑r=1k‍λrBir,jr=ϕn(w)∈Im⁡ϕn=ℒn.Note. Observe that we have reduced the completion problem to study the linear system occurring in item (ii)—or (iii)—of the previous theorem. We shall see how this theorem works in two specific situations.Example 8.
We will apply Theorem7 in order to show that matrix A in (9) cannot be completed to be consistent. If this completion was feasible, then by Theorem 7 and (14), there would exist w=(w1,w2,w3,w4)T∈ℝ4 such that
(23)log⁡2=w1-w2,log⁡3=w1-w3,log⁡3=w2-w3,log⁡4=w2-w4.
It can be quickly shown that this linear system has no solution.Example 9.
We will see if(24)A=[1⋆13⋆1233321]
has a consistent completion. By taking logarithms, we construct
(25)C0=[00-log⁡300log⁡2-log⁡3log⁡3log⁡3-log⁡20].
If there is a consistent completion, by item (iii) of Theorem 7, then there will exist w=(w1,w2,w3)T∈ℝ3 such that
(26)-log⁡3=w1-w3,log⁡2-log⁡3=w2-w3.
This system, clearly, is solvable. Hence, the completion is possible. We will see how Theorem 7 enables us to find such completion(s). The general solution of (26) is
(27)w1=-log⁡3+α,w2=log⁡2-log⁡3+α,w3=α,α∈ℝ.
If X is any consistent completion of A, then item (i) of Theorem 7 guarantees that there exists λ∈ℝ such that L(X)=C0+λB12, and such λ can be obtained from (17) obtaining λ=w1-w2=-log⁡2. Thus, L(X)=C0-log⁡2·B12. We conclude that there is a unique consistent completion of A and it is given by
(28)X=[1121321233321].


## 4. Completion of Reciprocal Matrices and Graph Theory: Uniqueness of the Completion

In this section we develop several useful results that enable us to study the uniqueness of the consistent completion and to compute in a straightforward manner all possible completions. Let us start by having a deeper look at the linear systems (23) and (26).We have, respectively,(29)[1-10010-1001-10010-1][w1w2w3w4]=[log⁡2log⁡3log⁡3log⁡4],[10-101-1][w1w2w3]=[-log⁡3log⁡2-log⁡3].
The transposes of the matrices of the above systems are the incidence matrices of the directed graphs of Figure 1.Directed graphs corresponding to Examples8 and 9.
(a)
(b)For an arbitraryn×n incomplete reciprocal matrix A=(aij), we use the following procedure to construct a directed graph, denoted by GA: If i≥j, then there is no arrow from i to j. If i<j and we do not know the entry aij, then there is no arrow from i to j. If i<j and we know the entry aij, then there is an arrow from i to j. Now, we easily construct the incidence matrix of GA, denoted in the sequel by MA. Observe that any incidence matrix has exactly two nonzero entries, namely, 1 and -1, in each column.To describe the linear system that appears in item (iii) of Theorem7, we also define, for an incomplete reciprocal matrix A∈ℝn,n, the vector bA=(b1,…,bm)T∈ℝm by the following procedure.(a)
m is the number of columns of MA; that is, m is the number of arrows of the directed graph GA. Explicitly, m=n(n-1)/2-k, where the meaning of k∈ℕ is given in Theorem 7: 2k is the number of entries of A to be filled.(b)
Forr=1,…,m, let us pay attention to the rth column of MA and let i,j be the unique indices such that the entry (i,r) of MA is 1 and the entry (j,r) of MA is −1. We set br=log⁡(aij).Observe thatMA and bA are unique up to a permutation.Theorem7 can be rephrased as follows.Theorem 10.
IfA is an incomplete reciprocal matrix, then A can be completed to be a consistent matrix if and only if the system MATw=bA is consistent.We present here an m-file that can be executed in Matlab or Octave. This file checks if an incomplete reciprocal matrix can be completed to be consistent. We use Theorem10 and the following criterion: the linear system MATw=bA is solvable if and only if MAT(MAT)†bA=bA, where the superscript † means the Moore-Penrose inverse (see Algorithm 1).Algorithm 1
f
unction
[M
,
b
,
N]  = test(A,  P)
%
A  is the matrix to be completed(if we do not knowa_{ij}, thenA(i,   j)=1
%
P  isa  (0, 1)-matrix such that if we do not knowa_{ij}, then  P(i,j)=1.
% if we know
a_{ij}, thenP(i,j)=0.
% Use:
[
M
,
b
,
N
]
= test
(
A
,  P)
%
M  =M_A;b  =b_A ;N  = pseudo-inverse of the transpose ofM_A
[
n
,
m
]
=size
(A)
;
n
1
=
(
n
∧
2
−
n
)
/2;
n
2 = sum
(
sum
(
P
))
/2;
n
3 =
n
1−
n
2;
M
= zeros
(
n
3,
n
)
;
k
= 1;
b
= zeros
(
n
3, 1
)
;
for
i=1
:
n
forj=i+1:n
IfP(i,  j)==0
M(k,  i)=1; M(k,  j)=−1;
b(k)=log(A(i,  j));
k=k+1;
end
end
e
nd
M=M
′
;
N
=
pinv(M
′
);
% Since there are numerical errors, a tolerance is used
if norm(M
′
*N*b−b) > 10∧(−10)
disp(‘There is no consistent completion’)
e
lse
disp(‘There is consistent completion’)
endThere is a trivial bound fork (let us recall that 2k is the number of entries of A to be filled). Since the diagonal entries of A∈ℝn,n must be equal to 1, then 2k≤n2-n. The following result gives a sufficient condition for a reciprocal incomplete matrix to be completed to be consistent.Theorem 11.
LetA∈ℝn,n be a reciprocal incomplete matrix and let 2k be the number of void entries (located up and down the main diagonal of A). If GA has p connected components and 2k≥n2-3n+2p, then A can be completed to be consistent.Proof.
We denotem=n(n-1)/2-k and we construct bA∈ℝm as the previous procedure states. Evidently, MA∈ℝn,m. Since GA has p connected components, then the rank of MA is n-p (see, e.g., [20, Th. 2.3]). Let ℛ(MAT) be the range space of MAT, which obviously satisfies ℛ(MAT)⊂ℝm. From dim⁡ℛ(MAT)=rank⁡(MAT)=rank⁡(MA)=n-p≥n(n-1)/2-k=m we obtain ℛ(MAT)=ℝm; hence bA∈ℛ(MAT), which shows that the linear system MATw=bA is consistent.Example 12.
In this example we will see that the graphGA can be disconnected. Let a∈ℝ be positive, and let us consider
(30)A=[1⋆⋆⋆1a⋆1a1].
The graph GA and its incidence matrix MA are shown in Figure 2. Obviously, GA has two connected components.
To find all possible consistent completions ofA, we must consider the system MATw=bA:
(31)[01-1][w1w2w3]=log⁡a.
Its general solution is w1,w2∈ℝ, w3=w2-log⁡a.
IfX is any consistent completion of A, then Theorem 7 ensures that λ1=w1-w2 and λ2=w1-w3=w1-w2+log⁡a are such that
(32)L(X)=[00000log⁡a0-log⁡a0]+λ1B12+λ2B13=[0w1-w2w1-w2+log⁡a-w1+w20log⁡a-w1+w2-log⁡a-log⁡a0].
By denoting b=exp⁡(w1-w2) we obtain
(33)X=[1bab1b1a1(ab)1a1].
Observe that the consistent completion of A is not unique since b∈ℝ+ is arbitrary.Figure 2
A disconnected graph and its incidence matrix.In the case that the completion is possible, we will show that it is unique in a particular situation: the corresponding graph is connected. We will denote by𝒩(C) the null space of matrix C, that is, all vectors x such that Cx=0. For future use, we will need the following lemma.Lemma 13.
LetG be a graph and M its incidence matrix. Then
(34)𝒩(MT)={x=(x1,…,xn)T:xi=xj⟺iandjareinthesameconnectedcomponentofG(x1,…,xn)T}.
Hence, the dimension of 𝒩(MT) is the number of connected components of graph G. In particular, if the graph is connected, then 𝒩(MT)=span⁡{1n}.Proof.
Letx∈ℝn be such that MTx=0. This implies that “if there is an edge connecting nodes i and j, then xi=xj.” Hence xi=xj if and only if i and j are in the same connected component of G.In the next result, the hypothesis2k<n(n-1) serves to guarantee m>0.Theorem 14.
LetA∈ℝn,n be a reciprocal incomplete matrix and 2k be the number of void entries (located up and down the main diagonal of A). If 2k<n(n-1), GA is connected and there exists a consistent completion of A, then this completion is unique.Proof.
Let us defineMA, bA, and m as in Theorem 11. Since there is a consistent completion of A, then the linear system MATw=bA is consistent. Let w0=(c1,…,cn)T be a solution. It is simple to prove that {w∈ℝn:MATw=bA}=w0+𝒩(MAT). Using this fact and Lemma 13 we have that if w is any solution of MATw=bA, then there exists α∈ℝ such that
(35)w=w0+α1n=(c1+α,…,cn+α)T.
Any possible completion of A must be computed using the values λ1,…,λk from (17); then λr=wir-wjr=cir-cjr for r=1,…,k. This shows that the completion is unique.Observe that if there is a consistent completion ofA, then the general solution of MATw=bA is given by w0+𝒩(MAT), where w0 is a particular solution of MATw=bA. It is simple to prove that if N is a matrix satisfying MATNMAT=MAT, then NbA verifies the system MATw=bA. Hence the general solution of this latter system is
(36){NbA+x:x∈𝒩(MAT)},
where N is an arbitrary but fixed matrix such that MATNMAT=MAT. We can choose N=(MAT)†, where the superindex † means the Moore-Penrose inverse of a matrix. Now, observe that (MAT)†=(MA†)T and in [20, Ch. 2] a method for finding the Moore-Penrose inverse of an incidence matrix is given.Another result that will be useful is the following (see [21, Ch. 2]). “Let A be an m×n matrix and b∈ℝm such that the system Ax=b is consistent. If N is any matrix satisfying ANA=A, then the general solution of the Ax=b is given by Nb+(I-NA)y for arbitrary y∈ℝn”. This result enables us to find the general solution of MATw=bA without computing the null space of MAT as in (36).Finally, notice that, to find the consistent completion ofA (as distilled in the proof of Theorem 14) when the corresponding graph GA is connected, we can discard the vector x in the null space of 𝒩(MAT) appearing in (36).Example 15 (this is the revisited previous Example9).
LetA be the incomplete matrix given in (24). Following the notation of Table 1 we have k=1, n=3, m=2, and p=1. By Theorem 11 we obtain that there is a consistent completion. A solution of MATw=bA is (by employing N as the Moore-Penrose inverse of MAT)
(37)w=(MAT)†bA=13[2-1-12-1-1][-log⁡3log⁡2-log⁡3]=13[-log⁡2-log⁡32log⁡2-log⁡3-log⁡2+2log⁡3]
and λ=w1-w2=-log⁡2. This example finishes as before.Table 1
Notation.
Incomplete matrixA
Directed graphGA
Incidence matrixMA
n
Size ofA
Points ofGA
Rows ofMA
m
Arrows ofGA
Columns ofMA
2
k
Entries ofA to be filled
p
Connected components ofGAExample 16 (this is the revisited Example12).
LetA be the incomplete matrix given in (30). Following the notation of Table 1 we have n=3, m=1, k=2, and p=2. Any solution of MATw=bA is given by
(38)w=(MAT)†bA+x=[012-12]log⁡a+x,
with x∈𝒩(MAT). But any vector of 𝒩(MAT) is of the form (x,y,y)T, where x,y∈ℝ. Hence
(39)w=[xy+log⁡a2y-log⁡a2].
Theorem 5 ensures that λ1=w1-w2=x-y-log⁡⁡a/2 and λ2=w1-w3=x-y+log⁡⁡a/2 satisfy that Y=log⁡a·B23+λ1·B12+λ2·B13 is a matrix such that E(Y) is any consistent completion of A. By denoting b=exp⁡(x-y)/a we obtain the same solution of the Example 12 obtained previously.
Another way of obtaining the same solution is by means of(40)w=(MAT)†bA+(I-(MAT)†MAT)y=[012-12]log⁡a+[1000121201212][y1y2y3].
Obviously, one obtains the same solution as in (39) by assigning y1→x and y1+y2→y.Let us observe that the linear systemMATw=bA is consistent if and only if bA∈ℛ(MAT). But standard linear algebra produces ℛ(MAT)=𝒩(MA)⊥. Hence we have that the linear system MATw=bA is consistent if and only bATx=0 for any x∈𝒩(MA).In next result we find the null space of𝒩(MA) for some types of graphs. To this end, we recall the concept of cycle in a graph. A cycle is a chain starting at a point and finishing at the same point. For instance, the left graph of Figure 1 has a cycle 1→2→3→1 (observe that the edge 3→1 is oriented in the opposite direction).LetG be an oriented graph (with the notation established in Table 1) whose edges are denoted by e1,…,em, with the enumeration of the edges being dictated by the incidence matrix. For example, for the left graph of Figure 1, the edge 2→3 is the third one. For a of set 𝒮 of edges (maybe the orientation of these edges can be distinct to the one given by the graph) we define the following vector v=(v1,…,vm)T∈ℝm: set vi=1 if ei∈𝒮 and the orientation of ei agrees with the corresponding one of 𝒮. Set vi=-1 if ei∈𝒮 and the orientation of ei is the opposite of the corresponding one of 𝒮. Set vi=0 if ei∉𝒮. For example, for the left graph of Figure 1 we associate the cycle 1→2→3→1 to (1,-1,1,0)T because the first and third edges (1→2 and 2→3) are in the loop; the second edge (1→3) appears in the cycle but in reverse and the fourth edge (2→4) does not appear in the cycle.Some further properties of the consistent completion ofA can be deduced if the associated graph GA is planar (see, e.g., [22] or any textbook on graph theory for a deeper insight of planar graphs). Let us remark that GA is not necessarily planar as the following example shows. Let
(41)B=[1⋆⋆⋆1⋆⋆⋆1],C=[abcdefghi],D=[a-1d-1g-1b-1e-1h-1c-1f-1i-1],
with a,b,…,i being positive numbers. The matrix A=[BCDB] leads to a nonplanar graph, namely, the complete (3,3) bipartite graph. Also, observe that a planar graph divides the plane into several faces; there is only one unbounded face; and any bounded face corresponds to a cycle. If f denotes the number of bounded faces, the very well-known Euler’s formula holds:
(42)n-m+f=p.
It is a known fact (see, e.g., [22, Ch. 2]) that any vector x corresponding to a cycle belongs to the null space of the incidence matrix of the graph.Theorem 17.
LetG be a planar oriented graph and M its incidence matrix. If x1,…,xf correspond to the bounded faces of the graph, then {x1,…,xf} is a basis of 𝒩(M).Proof.
By the previous paragraph we havex1,…,xf∈𝒩(M). We shall prove the next affirmation by induction on f. “If x1,…,xf correspond to the bounded faces of a graph, then x1,…,xf are linearly independent”. For f=1 the theorem obviously is true since x1≠0. Assume that the claim is true for f-1 and let x1,…,xf correspond to the f bounded faces of a graph such that ∑j=1f‍αjxj=0. There must be at least one edge from the unbounded face. This edge, let us say the ith edge, belongs to only one face (any edge is a boundary of two faces; but if one face is unbounded, the other face must be bounded), let us say xk this face. Looking at the ith coordinate of ∑j=1f‍αjxj=0 we conclude that αk=0. Now, the faces of the graph obtained by deleting the ith edge in the original graph are x1,…,xk-1,xk+1,…,xf. Since ∑j=1,j≠kf‍αjxj=0, by the induction hypothesis we have that α1=⋯=αf=0.
To finish the proof of the theorem, let us recall that the rank of the incidence matrix isn-p, where n is the number of points and p the number of connected components. It will be also useful to remark that the incidence matrix has n rows and m columns, with m being the number of edges. By Euler’s formula (42) we have
(43)dim⁡𝒩(M)=m-rk⁡(M)=m-(n-p)=f.
Since x1,…,xf are independent vectors in a f-dimensional subspace, these vectors form a basis of this subspace.Corollary 18.
LetA be an incomplete reciprocal matrix. If GA is planar and has no bounded faces, then there exists a consistent completion of A. Observe that by construction, GA is always oriented.Example 19 (Example8 revisited).
Looking at the left graph of Figure1, we see that the only bounded face corresponds to the cycle 1→2→3→1. Hence a basis of 𝒩(MA) is {(1,-1,1,0)T}. Since the matrix A of Example 8 has a consistent completion if and only if bA∈𝒩(MA)⊥, bA=(log⁡2,log⁡3,log⁡3,log⁡4)T, and (1,-1,1,0)TbA=log⁡2≠0, matrix A cannot be completed to a consistent matrix.Let us now consider an incomplete reciprocal matrix that cannot be completed to be consistent. How can the known entries be modified to complete the matrix to be consistent? The answer will be clear if we recall the following summary.For an incomplete reciprocal matrixA, the following affirmations are equivalent.(i)
There exists a consistent completion ofA.(ii)
The linear systemMATw=bA is consistent.(iii)
bATx=0 for any x∈𝒩(MA).Example 20.
If we want to modify some entries of matrixA given in (9) in order to have a consistent completion, let us start by writing
(44)A=[1a1a2⋆a1-11a3a4a2-1a3-11⋆⋆a4-1⋆1],bA=[log⁡a1log⁡a2log⁡a3log⁡a4].
Now we can choose the entries a1,…,a4 by using one of the above items. But as we know the null space of MA—in fact, from Example 19 we know that a basis of 𝒩(MA) is spanned by x=(1,-1,1,0)T—we choose item (iii). 							(45)ThereisaconsistentcompletionofA⟺bATx=0⟺log⁡a1-log⁡a2+log⁡a3=0⟺a1a3=a2.
It is noteworthy that the value of a4 is arbitrary.


## 5. Application to Leakage Control in a Water Supply System

By way of illustration, in this section we use some examples corresponding to a problem that challenges water supply managers, and in which the main objective is to achieve a suitable leakage policy to minimize water loss (see, e.g., [23]). The criteria considered are given in the examples. Finally, various management alternatives for leakage control are considered: ranging from active leakage control (ALC) to passive leakage control (PLC). ALC involves taking actions in supply systems or individual hydrometric district areas, to identify and repair detectable leaks that have not been reported. PLC refers to repairing only reported or evident leaks.We use the characterization presented in this paper as a decision support tool to assess the consistency of incomplete judgments given by specific stakeholders.Example 21.
We consider here the following multiple criteria to decide on the alternatives:C1: planning development cost and its implementation,C2: budgets and payment appropriations,C3: investment recovery,C4: social cost,C5: environmental cost.In this example, we use the point of view of an employee who develops water supply projects in a company in Spain. The actor has given an incomplete body of opinion and is unable to provide a robust viewpoint regarding some criteria, particularly comparisons regarding social (C4) and environmental (C5) costs, as well as planning development cost (C1).LetA be the following incomplete reciprocal matrix that represents the incomplete judgment given by the stakeholder:
(46)A=[1121⋆⋆2127⋆1121412⋆1714118⋆⋆281].By running the file given in Section4, we find that there is no consistent completion of A. However, the associated directed graph of this incomplete matrix is relatively easy to obtain (see Figure 3). We can see that this graph is planar. Thus, Theorem 17 enables us to very quickly obtain a basis of 𝒩(MA): the basis corresponds to cycles 1→2→3→1, 2→3→4→2, and 3→4→5→3. Explicitly we have that the following vectors
(47)x1=(1,-1,1,0,0,0,0)T,x2=(0,0,1,-1,1,0,0)T,x3=(0,0,0,0,1,-1,1)T
form a basis of 𝒩(MA).Figure 3
Directed graph corresponding to Example21.In this case, a slight modification of some entries ofA=(aij) makes a consistent completion feasible. In effect, by forcing bATx1=bATx2=bATx3=0, we find that the three following conditions must be simultaneously satisfied:
(48)a12a23=a13,a23a34=a24,a34a45=a35.
Observe that the first and the third equalities from (48) are satisfied by the original matrix A, whereas the second equality does not hold.The stakeholder considers that some entries can be changed. Sincea23 and a34 appear in the first and third equalities, the stakeholder is asked to modify only a24, and his answer is affirmative. By modifying entry a24 to 8, we obtain a matrix that is consistently completed. This alteration does not change the opinion of the stakeholder, because the old value, 7, and the new value, 8, correspond to similar verbal judgements of preference in Saaty’s scale. Let us rename A, the new reciprocal incomplete matrix,
(49)A=[1121⋆⋆2128⋆1121412⋆1814118⋆⋆281].We execute the m-file in order to findMA, bA, and N=(MAT)†. This m-file also ensures that there is a consistent completion of B (this fact was previously known because (48) are satisfied). This completion is unique by Theorem 14. As we mentioned, this unique completion of A can be obtained from (36) by discarding the vectors of 𝒩(MAT). By executing≫w = N*bwhereN=(MAT)† and b=bA, we obtainw =
0.0000
0.6931
0.0000
−1.3863
0.6931Theorem7 enables us to obtain the unique completion. It can be quickly found by using the calls in Algorithm 2.Algorithm 2
>
> [i j
]
= find(P);
>> r=length(i);
>> for index=1:r
A(i(index),j(index)) = exp(w(i(index))
−
w(j(index)));
endThus obtaining a consistent completion of the matrix which is satisfactory for the stakeholder≫AA =1.0000 0.5000 1.0000 4.0000 0.50002.0000 1.0000 2.0000 8.0000 1.00001.0000 0.5000 1.0000 4.0000 0.50000.2500 0.1250 0.2500 1.0000 0.12502.0000 1.0000 2.0000 8.0000 1.0000Example 22.
A final example shows an incomplete judgment that cannot be consistently completed. The criteria used to decide between the alternatives may be varied and take into account economic, environmental, and social impacts. In addition to the five criteria shown in Example21, two more criteria are used: C6: construction of tanks and reservoirs,C7: CO2 emissions.LetA be the matrix that corresponds to an incomplete judgment.
(50)A=[125175⋆121212⋆21151211521121251⋆3⋆17⋆0.5⋆112⋆15121132112⋆12⋆⋆21].
By running the previous file, we find that there is no consistent completion of A. We can obtain the directed graph corresponding to this example. This graph is more complex than the other example. However, since we know the entries ai,j for i∈{2,3,6} and j∈{1,4,7}, then the graph associated with the matrix of this example contains the complete (3,3) bipartite graph. Hence, the graph associated with A is not planar. In this case, the facilitator should invite the stakeholder to work further in order to reach a point where a consistent completion is possible.


## 6. Conclusions

MCDA, in particular AHP, has emerged as a decision support tool to integrate technical information and stakeholder values. Over the last decade, there has been a significant growth in MCDA applications in many fields, including decision support tools [24]. These techniques provide a systematic approach to combine information inputs with benefit/cost information and decision maker or stakeholder views to rank alternatives [25].Since vast investments are frequently at stake, DM must be performed with extreme care. In this regard, facilitators conducting participatory processes need robust tools that enable them to make discerning decisions when collecting opinions from various stakeholders.In this paper, by characterizing incomplete comparison matrices that can be consistently completed we have provided a robust tool to decide if an incomplete comparison body given by an actor is acceptable or, on the contrary, the actor must further develop the comparison for the sake of consistency. This tool is very simple since it reduces to the solution of a linear set of equations. Using graph theory we have developed several useful results that enable us to study the uniqueness of the consistent completion and to compute all the possible completions in a straightforward manner. Finally, in Section5 we have provided an illustrative example corresponding to the (incomplete) opinion given by a stakeholder in a DM process regarding the most suitable water leak management policy in a water distribution system. As can be observed, the calculations are simple and clear and can be easily implemented in any decision support tool based on AHP.



---

*Source: 349729-2014-02-25.xml*