PaperlayerView exact revision on arXiv

Source-linked AI summary

Efficient tensor bases for pairwise comparisons

Konrad Kułakowski, Ryszard Smarzewski

arXiv:2608.25923v1cs.CEecon.EMmath.OC

TL;DR

Pairwise-comparison theory lacked efficient explicit orthogonal formulas for the additively consistent subspace. The paper uses a tensor description to construct an orthogonal basis and projections, yielding new logarithmic, Saaty, and SVD formulas while supporting that no windowing method is universally superior.

  • Problem

    Efficient explicit expressions for an orthogonal basis of the additively consistent subspace had not been found, despite the problem’s longstanding study.

  • Method

    The paper uses tensor descriptions of best consistent approximations and Gram–Schmidt orthogonalization to construct the basis and derive projection formulas.

  • Results

    The constructed orthogonal basis yields new logarithmic, Saaty, and SVD projection formulas, with comparisons supporting that no windowing method is better in all cases.

  • Takeaways & Limitations

    The results provide an argument against claims of the eigenvector method’s absolute superiority and motivate further theoretical and numerical comparisons.

  • Takeaways & Limitations

    Further studies are needed because the choice of norm may substantially affect approximation quality, especially for the spectral matrix norm.

Abstract

from arXiv · show

In this study, we construct the first orthogonal basis for additively consistent subspace in pairwise comparisons theory. This construction is based on our representation of additively consistent best approximations of skew-symmetric matrices with respect to a tensor basis having minimal support. The orthogonal basis establishes the logarithmic consistent projection for the orthogonal windowing of pairwise comparisons matrices. It is compared with the windowing of the Saaty and SVD types. These comparisons resulted in new composite formulae for logarithmic, Saaty, and SVD projections. The theoretical considerations presented in the paper are accompanied by numerous examples.

1 Introduction

The introduction frames pairwise comparison matrices as multiplicative preference representations that become amenable to linear algebra after logarithmic transformation. It motivates constructing an explicit orthogonal basis and projection formulas to advance logarithmic projection and compare it with Saaty and SVD approaches.

  • Foundations: Pairwise comparison matrices encode relative importance through positive quotient entries mij, often represented as ratios of unknown weights xi/xj.Their multiplicative interpretation captures how many times one element is more important than another.
  • Foundations: Taking logarithms converts multiplicative comparisons into additive relations, enabling linear-algebraic methods for deriving priority vectors.The transformed entries ln mij approximate ln xi − ln xj.
  • Consistency and approximation: Consistency is central to AHP, where a pairwise comparison matrix is approximated by a consistent matrix using methods such as Saaty, least-squares, and logarithmic least-squares approaches.The approximation is formulated within the group of pairwise comparison matrices and its subgroup of consistent matrices.
  • Contributions: The work constructs the first explicit orthogonal basis, derives closed-form orthogonal projection expressions, and develops new logarithmic projection formulas for comparison with Saaty and SVD projections.This extends earlier use of logarithmic transformation by providing an explicit basis and projection construction.
  • Orthogonal-basis problem: Problem 1.1 seeks an orthogonal basis preserving the spans of an existing basis while providing formulas suitable for numerical calculation.Although Gram–Schmidt gives a unique solution up to nonzero multiplicative constants, its recurrence formulas are described as almost never numerically efficient.

2 Main results

The paper solves the longstanding problem of constructing efficient explicit orthogonal consistent tensor bases for pairwise-comparison matrices. This construction also clarifies orthogonal, Saaty, and SVD projections, including a composite representation of the SVD projection and evidence against universal superiority of any windowing method.

  • Orthogonal basis: The authors provide the most efficient orthogonal consistent tensor basis {B1, . . . , Bn−1} of An, solving Problem 1.1.Efficient explicit expressions for this basis had not previously been found.
  • Orthogonal decomposition: The construction characterizes the orthogonal direct-sum decomposition Sn = An ⊕ A⊥n for skew-symmetric matrices under the weighted Frobenius inner product.The authors introduced suitable bases for An and A⊥n to obtain this decomposition.
  • Projection methods: The new orthogonal basis sheds light on orthogonal, Saaty, and SVD projections from both theoretical and computational perspectives.These three projection types are studied in Sections 4, 7, 8, and 9.
  • Projection methods: The SVD projection satisfies TCM = RC(TGM) = PC(TG M) and is both norm-based and eigenvector-based.This makes it a unique pairwise-comparisons method with both properties.
  • Projection methods: Related projection results support the conclusion that no windowing method is better in all cases, countering claims of the eigenvector method’s absolute superiority.The paper presents this as an additional argument against the claim by Saaty and Vargas.

3 Tensor notation of consistent matrices

This section defines tensor operations and establishes the equivalence between multiplicatively consistent pairwise-comparison matrices and additively consistent skew-symmetric matrices. Consistent matrices are characterized by reciprocal and transitive relations, while their logarithms admit priority-vector tensor representations.

  • Tensor operations: Tensor products and tensor sums are defined for vectors in R^n and act as endomorphisms on R^n.Vectors are treated as column vectors, with the standard inner product, tensor product, and tensor sum.
  • Pairwise-comparison matrices: A positive matrix is a pairwise-comparison matrix when it is reciprocal, satisfying m_ij = 1/m_ji.Reciprocity is specified for all indices i, j = 1, . . . , n.
  • Pairwise-comparison matrices: A reciprocal matrix is consistent when it satisfies the transitivity condition c_ij = c_ik c_kj for 1 ≤ i < k < j ≤ n.The consistent matrices form a subgroup under the Hadamard product of pairwise-comparison matrices.
  • Logarithmic representation: The logarithm maps the multiplicative group of pairwise-comparison matrices isomorphically onto the additive group of skew-symmetric matrices.The exponential function is the inverse map, since reciprocity is equivalent to ln m_ij = −ln m_ji.
  • Additive consistency: Additive consistency is defined by a_ij = a_ik + a_kj and is equivalent to representing A as a tensor difference generated by an additive priority vector.The additive priority vector is unique up to an additive constant; exponentiating A yields a consistent matrix, and taking logarithms reverses this correspondence.

4 Consistent approximation of PC matrices

This section formulates consistent approximation of pairwise-comparison matrices and establishes existence of best consistent approximations. It then contrasts the non-convex multiplicative problem with a better-posed logarithmic formulation and Saaty’s eigenvector method.

  • Multiplicative approximation: Consistent approximation seeks a matrix C = x ⊘x in the consistent subgroup Cn that is nearest to a given pairwise-comparison matrix M under a matrix norm.The resulting C is called a best consistent approximation or nearest consistent matrix.
  • Existence: Every M ∈ Mn has at least one best consistent approximation, although the consistent subgroup Cn is neither bounded nor closed in Rn×n.The existence result is established as Theorem 4.1.
  • Multiplicative approximation: The consistent approximation problem is non-convex and may have multiple solutions, creating potential numerical ill-posedness unlike Saaty’s eigenvector method.Saaty’s method uses a uniquely determined positive eigenvector up to a positive constant.
  • Logarithmic approximation: The logarithmic formulation approximates S = ln M by an additively consistent matrix and maps the solution back as C = w ⊘w with w = exp(ˆy).The additive problem has at least one solution for every S, and uniqueness holds for strictly convex norms.
  • Logarithmic approximation: For the weighted Frobenius norm, the logarithmic solution is uniquely determined and its priority vector w is expressed through generalized geometric means.The weights ϱ are positive, and their choice may be important for randomly disturbed AHP data.

5 Characterization of additive consistency

This section characterizes additively consistent matrices as a subspace of skew-symmetric matrices and constructs a basis for that subspace. The basis has minimal support, while weighted Frobenius projection provides a unique consistent approximation.

  • Subspace characterization: The additively consistent matrices form a subspace An of the 1/2n(n −1)-dimensional space Sn of skew-symmetric matrices.They are defined by skew-symmetry and additive consistency relations.
  • Projection: The weighted Frobenius projection PA maps Sn orthogonally onto An and yields a unique additively consistent approximation PAS.The projected matrix has the form [yi −yj], with an additive priority vector determined under the weighted inner product.
  • Basis construction: Every matrix A = [yi −yj] in An is a linear combination of the basis matrices Ak = ek ⊗e −e ⊗ek for k = 1, . . . , n −1.The vectors y1, . . . , yn are generalized arithmetic means of the rows of A.
  • Basis construction: The set {A1, . . . , An−1} is a basis of An, so the subspace has n −1 basis matrices.The matrices are shown to be additively consistent and linearly independent.
  • Examples and comparison: For n = 3 and n = 4, the section illustrates the constructed bases and their orthogonalization, and contrasts the latter with an alternative basis lacking minimal support.The alternative matrix bA2 has 8 nonzero entries, whereas the minimal support cardinality is 6.

6 Orthogonal basis of An

This section constructs an orthogonal basis of the additively consistent subspace A_n under the standard Frobenius inner product. It derives closed-form basis matrices through a linear mapping and applies the basis to skew-symmetric matrices.

  • Orthogonal basis construction: For any n > 2, the paper constructs an orthogonal basis {B_1, ..., B_{n−1}} of A_n = span{A_1, ..., A_{n−1}}.The construction is carried out for the standard Frobenius inner product on R^n×n.
  • Orthogonal basis construction: The basis {B_1, ..., B_{n−1}} is defined from {A_1, ..., A_{n−1}} using Gram-Schmidt recurrent formulae.The matrices A_k are defined as A_k = e_k ⊗ e − e ⊗ e_k for k = 1, ..., n−1.
  • Closed-form relations: Each basis matrix satisfies B_k = A_k + 1/(n−k+1)(A_1 + · · · + A_{k−1}), with an equivalent expression in earlier B_j.These relations are established inductively from the inner-product identities for the A_k and B_k matrices.
  • Closed-form basis representation: Using L(x) = x ⊗ e − e ⊗ x, each B_k is represented as B_k = L(x_k), where x_k has its first k−1 entries equal to 1/(n−k+1).This representation yields closed formulae for the orthogonal basis and identifies A_k = L(e_k).
  • Application to skew-symmetric matrices: The orthogonal basis is then used to obtain a representation for any skew-symmetric matrix S, with the R^4×4 example giving ⟨S, B_2⟩/⟨B_2, B_2⟩ = −2s_12 + s_13 + s_14 + 3s_23 + 3s_24.The example illustrates the resulting coefficient formula for the second basis matrix.

7 Orthogonal windowing of PC matrices

This section defines the PC projection of pairwise-comparison matrices onto the consistent subgroup and relates it to orthogonal projection after taking logarithms. It then introduces PC windowing through an inner power and an orthogonal basis of the additive subspace.

  • PC projection: Definition 7.1 maps a PC matrix onto the consistent subgroup using a positive weight vector and entrywise formulas for the projected matrix.The projection is denoted PC_M = [r_ij].
  • PC projection: The PC projection extends to all positive matrices and has a close relationship with the orthogonal projection P_A applied to ln M.The relationship is investigated in Theorem 6.3.
  • PC windowing: PC windowing is formulated by analogy with FFT windowing in Fourier analysis using an inner power for matrices.The inner power is defined for matrices M = [m_ij] and B = [b_ij] in R^n×n.
  • PC windowing: The orthogonal decomposition assumes an orthogonal basis {B_1, ..., B_n−1} of A_n under the standard Frobenius inner product.This assumption supports the explicit formulas for B_k given in Theorem 6.3 and Corollary 6.4.

8 Saaty windowing of PC matrices

The Saaty projection is grounded in the Perron positive eigenpair and is widely used for positive pairwise-comparison matrices. However, both Saaty’s and logarithmic projections fail to distinguish matrices near their respective stochastic structures, supporting the view that no windowing method is universally superior.

  • Saaty projection: The Saaty projection uses the unique positive Perron eigenvector associated with a positive matrix’s dominant eigenvalue.The Perron eigenvalue is simple and exceeds the moduli of all other eigenvalues.
  • Saaty projection: Saaty’s projection is widely applied in psychology, product management, strategic planning, finance, banking, and market research despite criticism of the eigenvector approach.
  • Stochastic matrices: Saaty’s projection maps every positive stochastic matrix to the all-ones matrix, so it cannot distinguish between any two stochastic matrices.This limitation may reduce its usefulness for positive matrices close to stochastic matrices.
  • Multiplicatively stochastic matrices: The logarithmic PC projection likewise maps every multiplicatively stochastic matrix to the all-ones matrix under unit weights.The same conclusion holds for weighted inner products when each row satisfies the stated weighted logarithmic condition.
  • Comparison of methods: The examples support the conclusion that no windowing method is superior in all cases, contrary to the claim that the eigenvector method dominates logarithmic least squares.
  • Future investigation: A Perron-eigenvector-based choice of positive weights is proposed for future numerical study because theoretical considerations suggest it may help when Saaty’s eigenvector approach fails.

9 SVD windowing of PC matrices

This section introduces SVD windowing for positive pairwise-comparison matrices and characterizes it through relationships with Saaty, logarithmic, tensor, and eigenvector projections. It also identifies matrix classes where these windowing methods coincide and notes Sinkhorn normalization for positive matrices.

  • SVD construction: The SVD decomposes M into orthogonal singular-vector matrices U and V and ordered nonnegative singular values σ1 ≥ ··· ≥ σn.The singular vectors are the columns of U and V, corresponding to singular values σk.
  • SVD construction: The SVD projection is defined as the consistent projection of positive matrices onto the consistent subspace and can be extended to all positive matrices.The section explicitly names this construction the SVD projection and states that its domain may be extended to all positive matrices in Rn×n.
  • Special cases: For normal positive matrices, eigenvector and SVD windowing coincide.The equality follows because the singular values are the absolute eigenvalues and the largest singular value equals the leading eigenvalue.
  • Composite characterization: The SVD projection is a composite projection of the distance-based logarithmic and tensor projections, unlike the eigenvector projection.The theorem states this composite relationship for every pairwise-comparison matrix M.
  • Special cases: On the supergroup of tensor products of positive vectors, Saaty and SVD windowing coincide, supporting the conclusion that neither method is universally superior.The cited lemma is presented as a theoretical argument for that comparative conclusion.
  • Composite characterization: The SVD projection is also characterized as a composite projection of the eigenvector and tensor projections.Theorem 9.4 gives this characterization for every pairwise-comparison matrix M.

10 Conclusions

The study constructs the first explicit orthogonal basis for the space of additively consistent matrices, resolving a problem posed in 1997. It also emphasizes that norm selection matters and that the basis can be orthogonalized under weighted or arbitrary inner products.

  • Conclusions: The study constructs the first orthogonal basis for the space A_n of all additively consistent matrices in R^n×n, resolving a 1997 problem.Earlier studies considered the problem, but did not provide explicit formulae for the basis.
  • Conclusions: The commonly used Frobenius norm may be too restrictive, making the choice of norm important because it can improve or worsen approximation quality.The passage places norm selection within the broader context of real-world approximation theory.
  • Conclusions: For W = [w_ij] > 0, an orthogonal basis can be computed using weighted Gram–Schmidt orthogonalization, and the same holds for any inner product in R^n×n.The procedure may start from either the basis {A_1, ..., A_n−1} or the orthogonal basis {B_1, ..., B_n−1}.
Loading 2608.25923v1…