# Two Proofs and One Algorithm Related to the Analytic Hierarchy Process

Authors: Miron Pavluš; Rostislav Tomeš; Lukáš Malec
Journal: Journal of Applied Mathematics
 (2018)

---

## Abstract

36 years ago, Thomas Saaty introduced a new mathematical methodology, called Analytic Hierarchy Process (AHP), regarding the decision-making processes. The methodology was widely applied by Saaty and by other authors in the different human activity areas, like planning, business, education, healthcare, etc. but, in general, in the area of management. In this paper, we provide two new proofs for well-known statement that the maximal eigenvalueλmax is equal to n for the eigenvector problem Aw=λw, where A is, so-called, the consistent matrix of pairwise comparisons of type n×n (n≥ 2) with the solution vector w that represents the probability components of disjoint events. Moreover, we suggest an algorithm for the determination of the eigenvalue problem solution Aw=nw as well as the corresponding flowchart. The algorithm for arbitrary consistent matrix A can be simply programmed and used.


---

## Body

## 1. Introduction

Literature regarding the Analytic Hierarchy Process is rather extensive. The well-known database Current Contents Connect provides a growing number of records in all document types (articles, books, reports, reviews, etc.) regarding the acronym AHP in a publication title. For the last 15 years, the number of records can be seen in Figure1. These publications are mainly focused on different AHP applications, for example, a brown coal deposit [1], a comparative analysis of group aggregation techniques [2], a lab fire prevention management system [3], a green vendor evaluation and selection in production outsourcing in mining industry [4], an approximation of risk assessment [5], an evaluation of healthcare equipment [6], or many others.Figure 1
Records of AHP term in the database.Recently, the mathematical principles of AHP were published by Saaty [7]. This monograph involves a lot of mathematical findings that were collected in the area of decision-making processes, particularly, in the area of the AHP, starting from first publication [8] in 1980.In this paper, we add two proofs regarding the main statement in AHP theory as well as a corresponding algorithm for practical use. Neither proofs nor algorithm has been involved in [7].Let us consider a consistent matrixA, n×n(n≥2) in the form(1)A=1a1a2⋯an-11a11a2a1⋯an-1a11a2a1a21⋯an-1a2⋮⋮⋮⋱⋮1an-1a1an-1a2an-1⋯1where a1,a2,…,an-1 are given positive constants, known in AHP theory as priorities. Let the column vector w=p1,p2,…pnT reflect the probabilities pi(pi≥0) of disjoint events ωi=1,2,…,n so that the space Ω of elementary events ωi is given as a union Ω=ω1∪ω2∪…ωn of such events ωi, which are disjoint (ωi∩ωj=⊘, i≠j). Elementary events represent different criteria or alternatives in the AHP scheme and probabilities pi=P(ωi) are known as the weights. As usual, it must be required(2)∑i=1npi=1for probability components pi. Product Aw is a column vector whose components are sums of many addends if n is sufficiently large natural number. Therefore, it is better to find a real number λ such that the simpler product λw is equal to the complex product Aw. Hence, we have the equation Aw=λw. Certainly, such equation has the trivial solution w=00…0T for arbitrary real number λ but this is not interesting for us because this zero solution does not satisfy condition (2). If somebody is looking for nontrivial solutions w≠00…0T, then the system Aw=λw, rewritten into the form (A-λE)w=0→ must have a singular matrix A-λE, i.e., determinant A-λE=0. Here, E marks the unit matrix.


## 2. Derivation

Now, we will demonstrate a way for how to derive the determinantA-λE for arbitrary consistent matrix A of type n×n.By the calculation of determinantA-λE [9–11], resp. by means of Laplace expansion the validity of following formula can be evaluated (3)A-λE=1-λa1a2⋯an-11a11-λa2a1⋯an-1a11a2a1a21-λ⋯an-1a2⋮⋮⋮⋱⋮1an-1a1an-1a2an-1⋯1-λ=-λn-1n-λ.The casesn=2 and n=3 are considered as special using fundamental rules like Sarrus. Next, we present two different ways for how to prove statement (3), which are involved neither in [7, 12] nor in other works known to the authors of this paper. The first proof is done by the direct calculation of the determinant on the left hand side of statement (3). The second proof is based on the mathematical induction method.


## 3. Proof by Direct Calculation of Determinant

At the beginning, we arrange the determinant of (3). We choose the factors 1/a1,1/a2,…,1/an-1 from the second, third, fourth, up till n-th row. Thus, we get(4)1-λa1a2⋯an-11a11-λa2a1⋯an-1a11a2a1a21-λ⋯an-1a2⋮⋮⋮⋱⋮1an-1a1an-1a2an-1⋯1-λ=1a11a2⋯1an-1×1-λa1a2⋯an-11a11-λa2⋯an-11a1a21-λ⋯an-1⋮⋮⋮⋱⋮1a1a2⋯an-11-λ.Then, the factors a1,a2,…,an-1 are set from the second, third, fourth, up till n-th column of the last determinant. We continuously obtain(5)a1a1a2a2⋯an-1an-11-λ11⋯111-λ1⋯1111-λ⋯1⋮⋮⋮⋱⋮111⋯1-λ.By this way, we have arranged the determinant of (3) to the simple determinant(6)z11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zof type n×n, where z=1–λ.Next, we will express such determinant. By elimination in the first column and by selection of the common factor(z-1)/z from corresponding rows, we will get(7)z11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯z.-1z↩↩⋮↩=z11⋯10z2-1zz-1z⋯z-1z0z-1zz2-1z⋯z-1z⋮⋮⋮⋱⋮0z-1zz-1z⋯z2-1z=z-1zn-1z11⋯10z+11⋯101z+1⋯1⋮⋮⋮⋱⋮011⋯z+1.The similar elimination in the second, third, fourth up till n-th column provides sequentially(8)
z
-
1
z
n
-
1
z
1
1
⋯
1
0
z
+
1
1
⋯
1
0
1
z
+
1
⋯
1
⋮
⋮
⋮
⋱
⋮
0
1
1
⋯
z
+
1
.
-
1
z
+
1
↩
⋮
↩
=
z
-
1
z
n
-
1
z
z
+
1
n
-
2
×
z
1
1
⋯
1
0
z
+
1
1
⋯
1
0
0
z
+
2
⋯
1
⋮
⋮
⋮
⋱
⋮
0
0
1
⋯
z
+
2
.
-
1
z
+
2
⋮
↩
=
…
=
z
-
1
z
n
-
1
z
z
+
1
n
-
2
…
z
+
n
-
3
z
+
n
-
2
n
-
n
-
1
×
z
1
1
⋯
1
0
z
+
1
1
⋯
1
0
0
z
+
2
⋯
1
⋮
⋮
⋮
⋱
⋮
0
0
0
⋯
z
+
n
-
1
.If we realize that the last determinant is equal to product of all diagonal elements and using elementary operations, the final result can be expressed(9)z-1n-1z+n-1,which is the same result as the right hand side of statement (3), provided that z=1-λ.


## 4. Proof by Mathematical Induction Method

The equation (3) is valid for n=2. Next, we suppose that statement (3) holds for arbitrary natural n(n≥2) and it will be proved that the statement is valid also for the next natural, i.e.,n + 1. So, we will prove that(10)1-λa1a2⋯an1a11-λa2a1⋯ana11a2a1a21-λ⋯ana2⋮⋮⋮⋱⋮1ana1ana2an⋯1-λ=-λnn+1-λ.By a similar way to that done in the beginning of Section 3, one can choose the factors 1/a1,1/a2,…,1/an-1 from the second, third, fourth, up till (n+1)-th row and one can choose the factors a1,a2,…,an from the second, third, fourth, up till (n+1)-th column of the determinant in (10). Thus, we get the determinant(11)z11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zof n+1 rows and n+1 columns. Next, we do the standard Laplace expansion, see, e.g. [10, 11] according to the last (n+1)-th row, so that(12)z11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zn+1×n+1=-1n+1+11111⋯1z11⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n+-1n+1+21z11⋯1111⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n+…+-1n+1+n+1zz11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zn×n.Now, we arrange all determinants of type n×n so that the row of units is the first row. This can be achieved by switching adjacent rows around, which operation leads to a sign change of the determinant. Thus, we have(13)z11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zn+1×n+1=-1n+1+11111⋯1z11⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n+-1n+1+21-1111⋯1z11⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n+…+-1n+1+n+1zz11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zn×n.The multiple common determinant (with units in the first row) can be chosen after bracket and due to this, we obtain(14)∑i=1n-1n+1+i1-1i-1111⋯1z11⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n+-1n+1+n+1zz11⋯11z1⋯111z⋯1⋮⋮⋮⋱⋮111⋯zn×n.We arrange the sum near the first determinant in the form(15)∑i=1n-1n+1+i1-1i-1=∑i=1n-1n+2i=n-1n.Then, the second determinant is substituted according to the induction assumption (3) which results in(16)n-1n111⋯1z11⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n+zz-1n-1z+n-1.We make the following arrangement of the last determinant. The first row of units from the rest of the rows is subtracted. Thus, the process continues into(17)zz-1n-1z+n-1+n-1n111⋯1z11⋯11z1⋯1⋮⋮⋮⋱⋮111⋯1n×n=zz-1n-1z+n-1+n-1n111⋯1z-100⋯00z-10⋯0⋮⋮⋮⋱⋮000⋯0n×n.Finally, the last determinantal operation is the expansion according to last column. Then, we get(18)zz-1n-1z+n-1+n-1n-1n+1×z-100⋯00z-10⋯000z-1⋯0⋮⋮⋮⋱⋮000⋯z-1n-1×n-1or(19)zz-1n-1z+n-1+n-1n-1n+1z-1n-1=z-1n-1zz+n-1-n=z-1n-1z2+zn-z-n=z-1n-1z-1z+n=z-1nz+n,provided z=1-λ. It is proven that the determinant on the left hand side of (10) is equal to the expression on its right hand side. Thus, statement (3) holds for arbitrary natural n(n≥2) as it results from mathematical induction methodology.


## 5. Main Statement

Both the proof by direct calculation of determinant in Section3 and the proof by mathematical induction method in Section 4 lead to the same result; namely, the determinant A-λE is equal to (-λ)n-1n-λ for arbitrary consistent matrix A with arbitrary natural n(n≥2).If somebody looks for the eigenvalues of the consistent matrixA with arbitrary natural n(n≥2), then the equation A-λE=0 holds, or (-λ)n-1n-λ=0. From here, we have the following main theorem.Theorem 1.
The arbitrary consistent matrixA with arbitrary natural n(n≥2) has the following eigenvalues λ1=λ2=…=λn-1=0, but λn=n.
Hence, the maximal eigenvalue isλmax=λn=n. The reason why we are not interested in the other eigenvalues is simple: the components of eigenvectors w=p1p2…pnT for the other eigenvalues do not fulfil the conditions pi≥0, i=1,2,…,n. We demonstrate this by the next simple example.Example 1.
Let us consider the following consistent matrix(20)A=113231612161of type 3 × 3. According to Theorem 1, the matrix has the following eigenvalues: λ1=λ2=0 and λ3=3. Determine the eigenvectors of nonnegative components for eigenvalues λ2=0 and λ3=3.Letλ2=0. Then, the matrix A-0E equals(21)113231612161and the system (A-0E)w=0→ can be solved by the elimination method in the way(22)113203160121610-3-12↩↩~1132000000000.Hence, we have one equation p1+p2/3+2p3=0 with three unknowns: p1, p2, and p3. Moreover, the solution w=p1p2p3T must fulfil condition (2) that means p1+p2+p3=1. So, we solve two equations with three unknowns: p1, p2, and p3. One unknown, let us say p3, is a free one, and after substitution, one can get p1=-1/2-5/2p3. This means if p3≥0 then p1<0 which is not feasible.On the other hand,λ3=3. Then, the system (A-3E)w=0→ by the same elimination provides(23)-213203-2601216-203214↩↩~-213200-3290014-32016↩~-213200-32900000and including condition (2) one can get the unique solutionw = (2/92/31/9)T, where all components are nonnegative. Thus, the result λ=λmax is evident.


## 6. Algorithm for Determination of Components

In this section, we will demonstrate an algorithm which determines all componentspi≥0, i=1,2,…,n, of the solution w=p1p2…pnT if a consistent matrixA of type n×n is given by arbitrary naturaln (n≥ 2); see (1). As we have seen in Section 4, it must be solved by (A-λE)w=0→ with λ=λmax=n; otherwise some components pi can be negative and therefore these components do not represent probabilities of any event. In this case, the system (A-nE)w=0→ has the explicit form(24)1-na1a2⋯an-11a11-na2a1⋯an-1a11a2a1a21-n⋯an-1a2⋮⋮⋮⋱⋮1an-1a1an-1a2an-1⋯1-np1p2p3⋮pn=000⋮0which is arranged by the following way. First, we multiply the second, third, up ton-th row by a1,a2,…,an-1. The following is obtained(25)1-na1a2⋯an-11a11-na2⋯an-11a1a21-n⋯an-1⋮⋮⋮⋱⋮1a1a2⋯an-11-np1p2p3⋮pn=000⋮0.Second, we rewrite the last system in the form(26)1-n11⋯111-n1⋯1111-n⋯1⋮⋮⋮⋱⋮111⋯1-np1a1p2a2p3⋮an-1pn=000⋮0to get a simpler matrix. Then, we use the elimination method as(27)1-n11⋯1011-n1⋯10111-n⋯10⋮⋮⋮⋱⋮⋮111⋯1-n0.-11-n↩↩⋮↩~1-n11⋯1002-n1⋯10012-n⋯10⋮⋮⋮⋱⋮⋮011⋯2-n0.-12-n↩⋮↩↩~…~1-n11⋯1002-n1⋯10003-n⋯10⋮⋮⋮⋱⋮⋮000⋯00.We can see that the last row is zero which is evident due to determinant A-λE with the eigenvalue λ=n being equal to zero. Thus, there exist many eigenvectors w=p1p2…pnT that satisfy (24). In this set, we choose only one eigenvector satisfying condition (2). This can be achieved by means of the substitution of zero row in the last system arrangement with the following row. Condition (2) can be written in the matrix form(28)111⋯1p1p2p3⋮pn=1;however, our consideration is related to the unknown(29)p1a1p2a2p3⋮an-1pnin the last system arrangement. So, condition (2) must be rewritten as(30)11a11a2⋯1an-1p1a1p2a2p3⋮an-1pn=1and due to this, we will have the system(31)1-n11⋯1002-n1⋯10003-n⋯10⋮⋮⋮⋱⋮⋮11a11a2⋯1an-11for unknown vector (29).A core of the suggested algorithm consists in the elimination of the last row of the system (31). This elimination can be processed by the following steps.Step 1. The first row in (31) is multiplied by fraction -1/(1-n) and the multiplied row is added to the last row. We denote the fraction by cn-1. Due to this operation, the last modified row has the first element zero and the second element is 1/a1+cn-1.Step 2. The second row in (31) is multiplied by fraction -(1/a1+cn-1)/(2-n) and the multiplied row is added to the last modified row. We denote the fraction by cn-2. Due to this operation, the new modified row has ther-st two elements as zeros and the third element is 1/a2+cn-1+cn-2.Etc.Step n - 1. The (n-1)-st row in (31) is multiplied by fraction -(1/an-2+cn-1+cn-2+…+c2)/(-1) and the multiplied row is added to the last modified row. We denote the fraction byc1. Due to such operation, the new modified row has the first (n–1) elements as zeros and the last element is 1/an-1+cn-1+cn-2+…+c1. A key point of elimination process is to get system (31) into the form(32)1-n11⋯1002-n1⋯10003-n⋯10⋮⋮⋮⋱⋮0000⋯c01,where(33)c0=1an-1+cn-1+cn-2+…+c1,as it follows from the elimination process. Thus, we come to Algorithm 1.Algorithm 1:Calculation of eigenvector components.
Input:  a1,a2,…,an-1 (n≥2)→ given priorities Output:  p1,p2,…,pn→ unknown eigenvector components ( 1 )  cn-1←1/(n-1); → initial assignment ( 2 )  while n>2  do→ if n = 2 then jump to step (7) ( 3 )  for each  k∈2,3,…,n-1  do→ cycle for index k ( 4 )  cn-k←(1/ak-1+∑i=1n-1cn-i)/(n-k); → cn-2,cn-1,…,c1 ( 5 )  end ( 6 )  end ( 7 )  c0←1/an-1+∑i=1n-1cn-i;→ relation (33) ( 8 )  pn←1/c0an-1; → last unknown component pn ( 9 )  for each  k∈n-1,n-2,…,1  do→ cycle for index k (10)pk←1/(n-k)ak-1∑i=k+1nai-1pi; → pn-1,pn-2,…,p1 ( 11 )  endFor programming purposes, however, the flowchart in Figure2 is more suitable than the algorithm individual steps.Figure 2
Flowchart of the algorithmHowever, there are more ways for how to calculate the eigenvector components. In Sections2 and 3 of this paper, we provided two proofs for well-known statement that λmax is equal to n for the eigenvector problem Aw=λw. Thus, the system (A-λE)w=0→ can be directly solved with λ=λmax=n, (A-nE)w=0→, where the components pi of vector w=p1,p2,…pnT represent probabilities of any event. There is no need to calculate λmax because λmax=n. Algorithm 1 helps to calculate components p1,p2,…pn directly using positive constants a1,a2,…,an-1 from the first row of consistent pairwise matrix A, n×n(n≥2).Example 2.
We have the following consistent matrix(34)A=12.4143.1664.1384.1385.3790.41411.3111.7141.7142.2290.3160.76311.3071.3071.6990.2420.5830.76511.0001.3000.2420.5830.7651.00011.3000.1860.4490.5880.7690.7691of type 6 × 6, which is pairwise matrix of quantitative criterion. We need to solve the system (A-nE)w=0→. In this example, we exceptionally use, instead of standard mathematical tools, modeling inMS Excel, specifically using its additional toolSolver. We obtain vector w=0.4170.1730.1320.1010.1010.007T.The constantsa1 = 2.414, a2 = 3.166, a3 = 4.138, a4 = 4.138, and a5 = 5.379 are used in the algorithm described in Section 6. The result is w=0.4170.1730.1320.1010.1010.007T. We can see that using such algorithm it gives the same results.


## 7. Conclusion

This paper has a mathematical methodological character utilizing only basic matrix theory. It shows two ways for how to prove the well-known statement regarding the set of eigenvalues ofAw=λw with a consistent matrixA of type n×n(n≥2), and it demonstrates how to find the corresponding eigenvector components presented as some probabilities of events for maximal eigenvalue λ=λmax=n.The derived and suggested algorithm can be easily programmed in different languages (C++, C, FORTRAN, MATHEMATICA, etc.) and can be used in AHP methodology for determination of weights (probabilities) when comparing the criteria to a goal or when comparing the alternatives to an individual criterion. During such comparison, it is important to make sure that the criteria or alternatives present a set of disjoint events (ωi∩ωj = ⊘, i≠j). If some events, say ωi and ωj, are such that ωi∩ωj=⊘, i≠j, then condition (2) does not hold and the calculated weights do not reflect any real examined problem. In such a case, we suggest considering the intersection ωi∩ωj as a new event, say ωk=ωi∩ωj, and incorporating this new event into the previous set of events. Next, we note that the statement and algorithm suggested in the paper hold for arbitrary natural n(n≥2). This enables formulating and solving the relatively complex AHP problems with large number of criteria and huge number of alternatives like those in [1–6].During practical evaluation of AHP, it can happen that the matrixA is not consistent but is close to a consistent matrix A′. In this case, certainly, λmax(A) differs from λmax(A′) and the corresponding difference is measured by means of, so-called, consistency index(35)λA-nn-1that was introduced by Saaty in [8]. If the consistency index is close to zero, then the suggested algorithm can be applied, but condition (2) holds only approximately. The usual problem of how to obtain λmax(A) for a nonconsistent general matrixA can be solved by means of the software packages which provide eigenvalues for the general full matrices. Such access, however, does not suppose any special matrix structure, like AHP matrix (1), and the eigenvalue software calculations in this general case are computationally difficult, especially when n is large natural number. The special structure nonconsistent matrices which are close to AHP matrix are not considered in this paper and can be analyzed in the future research.It can be said that there are some methods to repair consistency of matrices. Xu [13] defined a criterion to find unusual and false element and proposed method based on finding such elements in matrix and repair it. The repaired matrix has (after calculating new element instead of unusual one) an acceptable consistency. Saaty [12] proposed method based on additive perturbation using aijwj/wi, i≠j, where w is an eigenvector, and focused their attention on element of the matrix A which provokes inconsistency. The consistency is generally more acceptable by substituting this element.



---

*Source: 5241537-2018-12-02.xml*