Exact bounds for efficient consistent matrices obtained from a reciprocal matrix

Basic Information

• Paper ID: 2510.12358
• Title: Exact bounds for efficient consistent matrices obtained from a reciprocal matrix
• Authors: Susana Furtado (Universidade do Porto), Charles R. Johnson (Williamsburg, VA)
• Classification: math.CO (Combinatorics)
• Publication Date: October 15, 2025
• Paper Link: https://arxiv.org/abs/2510.12358

Abstract

For a given reciprocal matrix A, this paper provides a union of matrix intervals where any consistent matrix obtained from an efficient vector of A is located within this union, and conversely, any consistent matrix in this union comes from an efficient vector of A. The paper describes the maximum set of entries in the lower and upper bound matrices of each interval that can be attained by some consistent matrix within the interval. This enables us to understand which subsets of alternatives lie above other subsets across all efficient orderings in each interval. Consequently, the partial order relation on alternatives determined by efficient vectors is established. The paper then employs the developed tools to prove that when n×n reciprocal matrices A and B are simple perturbations of consistent matrices or when n=4, the sets of efficient vectors of A and B coincide if and only if A=B.

Research Background and Motivation

Importance of the Problem

1. Multi-criteria Decision Analysis: In multi-criteria decision models, reciprocal matrices (also called pairwise comparison matrices) represent pairwise ratio comparisons between n alternatives, requiring determination of a cardinal ranking vector representing relative weights.
2. Consistency Problem: Ideally, a matrix is consistent if $a_{ij}a_{jk} = a_{ik}$ holds for all triples $1 \leq i,j,k \leq n$. However, consistent matrices rarely occur in practice, necessitating approximation of inconsistent reciprocal matrices by consistent matrices.
3. Efficient Vector Theory: Saaty's early recommendation was to use the right Perron eigenvector as the cardinal ranking vector, but when the matrix is inconsistent, this may not be optimal. Therefore, efficient vectors satisfying Pareto optimality must be sought.

Limitations of Existing Methods

1. Imprecision of Single Matrix Intervals: Previous research 12 provided a single matrix interval, but this interval may contain consistent matrices not derived from efficient vectors.
2. Lack of Exact Boundaries: Existing methods cannot precisely describe which consistent matrices actually come from efficient vectors and which do not.
3. Unclear Partial Order Relations: Existing methods struggle to accurately describe the partial order relations among alternatives.

Core Contributions

1. Exact Union of Matrix Intervals: Provides a union of at most $(n-1)!/2$ matrix intervals where a consistent matrix is located therein if and only if it comes from an efficient vector.
2. Maximum Attainable Entry Sets: Describes the maximum set of entries in the lower and upper bound matrices of each interval that can be attained by consistent matrices within the interval.
3. Characterization of Partial Order Relations: Completely describes the partial order relation on alternatives determined by efficient vectors, determining when certain alternatives lie above others in all efficient orderings.
4. Uniqueness Results: Proves that when A and B are simple perturbations of consistent matrices or when n=4, E(A)=E(B) implies A=B.

Detailed Methodology

Problem Definition

Given an n×n reciprocal matrix $A=[a_{ij}]$ (satisfying $a_{ji}=1/a_{ij}$), find efficient vectors $w \in \mathbb{R}^n_+$ such that the corresponding consistent matrix $W=ww^{(-T)}=[\frac{w_i}{w_j}]$ satisfies specific boundary conditions.

Core Concepts

1. Reciprocal and Consistent Matrices

• Reciprocal Matrices: $PC_n$ denotes the set of all n×n elementwise positive matrices satisfying $a_{ji}=1/a_{ij}$
• Consistent Matrices: Reciprocal matrices satisfying $a_{ij}a_{jk}=a_{ik}$, expressible as $A=ww^{(-T)}$

2. Efficient Vectors

A vector $w \in \mathbb{R}^n_+$ is an efficient vector of matrix A if $|A-vv^{(-T)}| \leq |A-ww^{(-T)}|$ (elementwise absolute value) implies $v$ is proportional to $w$.

3. Hamiltonian Circuits and Path Matrices

• Hamiltonian Circuit: $\tau: \tau_1\tau_2\cdots\tau_n\tau_1$
• Circuit Product: $\tau(A) = a_{\tau_1\tau_2}a_{\tau_2\tau_3}\cdots a_{\tau_n\tau_1}$
• Path Matrix: $P_{A,\tau}=[p_{ij}]$, where $p_{ij}=P_{A,\tau}(i,j)$ represents the path product along circuit $\tau$ from $i$ to $j$

Main Theoretical Results

Theorem 12 (Exact Boundaries)

Let $A \in PC^0_n$, $\tau \in \Gamma(A)$, $w \in \mathbb{R}^n_+$, $W=[\frac{w_i}{w_j}]$. Then: $w \in E_\tau(A) \iff P_{A,\tau} \leq W \leq P_{A,\tau}^{(-T)}$

Theorem 14 (Main Result)

Let $A \in PC^0_n$, $w \in \mathbb{R}^n_+$, $W=ww^{(-T)}$. Then $w \in E(A)$ if and only if there exists $\tau \in \Gamma(A)$ such that: $P_{A,\tau} \leq W \leq P_{A,\tau}^{(-T)}$

Technical Innovations

1. Path Matrix Method: Introduces path matrices $P_{A,\tau}$ to precisely characterize the consistent matrix boundaries corresponding to each efficient vector subset $E_\tau(A)$.
2. Maximum Attainable Set Theory: Defines sets $S_k^{(\tau)}$ to describe the maximum set of entries in path matrices that can be exactly attained by efficient vectors.
3. Non-dominated Condition: Introduces the $(A,S)$-non-dominated concept to identify extreme points of efficient vector sets.

Experimental Setup

Theoretical Verification

The paper is primarily theoretical, with results verified through mathematical proofs. Main components include:

1. Concrete Example Verification:
   • Example 15: Complete calculation for 4×4 matrices
   • Examples 25-27: Ordering analysis in different scenarios
2. Special Case Analysis:
   • Simple perturbations of consistent matrices
   • Complete analysis for n=4

Mathematical Tools

• Monomial similarity transformations (Lemma 9)
• Convex set theory and cone generation
• Hamiltonian circuit analysis in graph theory

Experimental Results

Main Theoretical Results

1. Exact Boundary Characterization

For the 4×4 matrix example (Example 15), three exact matrix intervals are provided:

• Interval 1: Corresponding to circuit $\alpha$, all vectors in decreasing order
• Interval 2: Corresponding to circuit $\beta$, ordering $(1,2,4,3)$
• Interval 3: Corresponding to circuit $\gamma$, ordering $(1,3,2,4)$

This provides more precise information compared to previous single-interval methods.

2. Unique Ordering Conditions

Theorem 29 provides necessary and sufficient conditions for all efficient vectors to have the same ordering:

1. There exists a permutation $i_1i_2\cdots i_n$ such that $P_{A,\tau}(i_t,i_{t+1}) \geq 1$
2. $P_{A,\tau}$ has exactly $\frac{n^2-n}{2}$ off-diagonal elements ≥1
3. For $i,j \in N$, $i>j$, either $P_{A,\tau}(i,j) \geq 1$ or $P_{A,\tau}(j,i) \geq 1$

3. Uniqueness Results

• Theorem 33: For simple perturbations of consistent matrices, $L_A=L_B$ implies $A=B$
• Theorem 51: When $n=4$, $E(A)=E(B)$ implies $A=B$

Case Studies

Example 25 demonstrates the method's advantages:

• Traditional single-interval method boundary: $W_{13}$ range is $[1,7]$
• New method's precise information: When $W_{23}=\frac{6}{7}$, necessarily $W_{24} \geq 2$ and $W_{14} \geq 6$

This precision is unattainable with traditional methods.

Related Work

Historical Development

1. Saaty (1977): Proposed using the right Perron eigenvector as the ranking vector
2. Blanquero et al. (2006): Introduced efficient vectors and graph-theoretic characterization
3. Furtado & Johnson Series:
   • Efficiency of geometric mean
   • Inductive description of efficient vectors
   • Convex set union characterization

Improvements Over Prior Work

Compared to the authors' previous work 12, this paper:

• Improves from a single matrix interval to an exact union of intervals
• Eliminates the problem of including consistent matrices not from efficient vectors
• Provides more precise ordering information

Conclusions and Discussion

Main Conclusions

1. Exact Characterization: Provides exact boundaries for consistent matrices from efficient vectors, resolving imprecision in previous methods.
2. Complete Partial Order: Through path matrix analysis, completely describes the partial order relations among alternatives.
3. Extended Uniqueness: Extends the result E(A)=E(B) ⟹ A=B from n=3 to simple perturbation cases and n=4.

Limitations

1. Computational Complexity: Requires consideration of up to $(n-1)!/2$ Hamiltonian circuits, with computational complexity growing rapidly with n.
2. General Case Unresolved: For general cases with n≥5, E(A)=E(B) ⟹ A=B remains a conjecture.
3. Practical Application: Practical computational implementation of theoretical results requires further research.

Future Directions

1. Algorithm Implementation: Develop efficient algorithms to compute matrix interval unions
2. General Uniqueness: Prove or disprove the uniqueness conjecture for n≥5
3. Application Extension: Apply results to concrete decision analysis problems

In-Depth Evaluation

Strengths

1. Theoretical Rigor: Complete mathematical proofs, precise results, addressing important theoretical problems
2. Methodological Innovation: Path matrix method and non-dominated conditions are effective technical innovations
3. Practical Value: Provides more precise tools for multi-criteria decision analysis
4. Clear Presentation: Complete structure, abundant examples, facilitating understanding

Weaknesses

1. High Computational Complexity: Method's practical application is limited by computational complexity
2. Lack of Algorithm Implementation: Primarily theoretical results without concrete algorithms and implementations
3. Limited Experimental Verification: Mainly verified through mathematical examples, lacking large-scale numerical experiments

Impact

1. Theoretical Contribution: Significant contributions to reciprocal matrix and efficient vector theory
2. Methodological Value: Path matrix method may apply to other related problems
3. Application Prospects: Provides new tools for decision analysis, operations research, and related fields

Applicable Scenarios

1. Multi-criteria Decision Analysis: Theoretical foundation improvements for AHP methods
2. Operations Research Optimization: Optimization problems involving pairwise comparisons
3. Matrix Theory Research: Theoretical analysis of reciprocal matrices

References

The paper cites 33 related references, primarily including:

• Saaty's pioneering work
• The authors' series of research on efficient vector theory
• Related matrix theory and decision analysis literature

The citation coverage is comprehensive, reflecting deep understanding of the field's development trajectory.