# Ordering Properties of the First Eigenvector of Certain Similarity Matrices

Authors: Matthijs J. Warrens; Alexandra de Raadt
Journal: Journal of Mathematics
 (2015)

---

## Abstract

It is shown for coefficient matrices of Russell-Rao coefficients and two asymmetric Dice coefficients that ordinal information on a latent variable model can be obtained from the eigenvector corresponding to the largest eigenvalue.


---

## Body

## 1. Introduction

An important role in statistics and data analysis is played by similarity coefficients. A similarity coefficient is a measure of resemblance or association of two data vectors, such as score patterns, variables, and items. For example, in ecological biology similarity coefficients are used for measuring the degree of coexistence between two species types over different locations. In many research studies the data consist of binary(
0,1
) vectors: presence or absence of disease; presence or absence of species characteristics; yes or no answers in questionnaires; pass or fail in high-stakes testing. For expressing the degree of resemblance of two binary vectors in a number, a variety of similarity coefficients has been proposed [1–3]. Examples are the Jaccard coefficient [4], the Russell-Rao coefficient [5], the Dice coefficient [6], and the simple matching coefficient [7, 8]. In choosing a coefficient, a measure has to be considered in the context of the data-analytic study of which it is a part [9]. Because there are so many similarity coefficients for binary data to choose from, it is important that the different coefficients and their properties are better understood.Instead of studying properties of individual coefficients [10–13] one may also study properties of coefficient matrices [14]. Coefficient matrices are used as input in various techniques of multivariate data analysis, including factor or component analysis [15, 16], hierarchical cluster analysis, and techniques in classification and dissimilarity analysis [17]. Moreover, exploratory data-analytic methods such as principal coordinates analysis and (multiple) correspondence analysis can be defined as eigendecomposition of certain coefficient matrices [15, 16, 18]. It would be interesting to know what information, if any, is reflected in the eigenvectors of a coefficient matrix that is based on a similarity coefficient for binary vectors.In this paper we show for several coefficient matrices that ordinal information on latent variable models can be obtained from the eigenvector corresponding to the largest eigenvalue. It is thus possible to uncover meaningful orderings of various models by using eigenvectors. The results are first of all of theoretical interest. They show that some coefficient matrices have more interesting eigenvectors than others. Coefficient matrices based on some coefficients may thus lead to more interesting data-analytic solutions than matrices corresponding to other coefficients. Furthermore, potentially, the results can enhance the interpretation of a data analysis that uses these coefficient matrices as input.The paper is organized as follows. Notation and two latent variable models are introduced in the next section. In Section3 several ordering properties of eigenvectors corresponding to a largest eigenvalue are presented. An illustration of the results is presented in Section 4. Section 5 contains a conclusion.


## 2. Latent Variable Models

Suppose the data consist ofm binary (
0,1
) vectors of length n. It may be assumed that the scores in the binary vectors are realizations of a latent variable model. In this section we introduce two models in the context of nonparametric item response theory [19, 20]. In item response theory the m vectors are often viewed as m items that, for instance, contain the responses (pass, fail) of a high-stakes test for n subjects. The m items will be indexed by i and j.Letθ denote a one-dimensional latent variable and let L
(
θ
) be its probability density function. Let p
i
(
θ
) denote the response function corresponding to the response 1 on item i. The unconditional probability of a response 1 on item i is then given by(1)
p
i
=
∫
-
∞
∞
p
i
θ
d
L
θ
. Next, assume local independence; that is, conditionally on θ the responses of a subject on the items are stochastically independent. The joint probability of items i and j for a value of θ is then given by p
i
(
θ
)
p
j
(
θ
). The corresponding unconditional probability is(2)
a
i
j
=
∫
-
∞
∞
p
i
θ
p
j
θ
d
L
θ
. Throughout the paper we assume that 0
<
a
i
j
≤
1.Next, we define the latent variable models. Both models have monotone response functions and are frequently applied in the context of measuring ability. The first model is characterized by requirements (3) and (4). The first requirement is that p
i
(
θ
) are monotonically increasing on θ; that is,(3)
p
i
θ
1
≤
p
i
θ
2 for θ
1
<
θ
2. The second requirement is that the m items can be ordered such that p
i
(
θ
) are nonintersecting; that is,(4)
p
i
θ
≥
p
j
θ for i
<
j. The case that assumes (3) and (4), together with the assumptions of local independence and a single latent variable, is called the double monotonicity model in nonparametric item response theory [19, 20]. A well-known result is that if the double monotonicity model holds, then the items can be ordered such that we have(5)
p
i
>
p
j for i
<
j, and(6)
a
i
j
≥
a
i
′
j for i
<
i
′ and j
≠
i
′ [19, 20]. The second model is characterized by requirements (3) and (7). The response functions p
i
(
θ
) may satisfy various orders of total positivity [21]. If the functions p
i
(
θ
) are totally positive of order 2, the items can be ordered such that(7)
p
i
θ
1
p
j
θ
2
-
p
i
θ
2
p
j
θ
1
≥
0 holds for θ
1
<
θ
2 and i
<
j. Schriever [22] proved the following result for a set of response functions that are both monotonically increasing and satisfy total positivity of order 2. If the vectors are ordered such that (3) and (7) hold, then(8)
a
i
j
p
i
≤
a
i
′
j
p
i
′ holds for i
<
i
′ and j
≠
i
′.We conclude this section with a parametric example that satisfies requirements (3), (4), and (7). A well-known model from the field of item response theory is the Rasch [23] model. A response function of this one-parameter logistic model is given by(9)
p
i
θ
,
b
i
=
e
θ
-
b
i
1
+
e
θ
-
b
i
, where b
i is a location parameter. In the context of item response theory the parameter b
i is usually called a difficulty parameter [19, 20]. The functions p
i
(
θ
,
b
i
) form a location family.


## 3. Ordering Properties

In this section we present ordering properties for three coefficient matrices. The coefficient matrices of sizem
×
m are(10)
A
=
a
i
j
,
B
=
a
i
j
p
i
,
C
=
a
i
j
p
j
. An element of the matrix A is a Russell-Rao coefficient for two binary vectors i and j [5, 10]. Some data-analytic properties of the matrix A are discussed in Warrens [14]. The elements of the matrices B and C are conditional probabilities discussed and applied in Dice [6]. The harmonic mean of the two conditional probabilities is equal to the Dice coefficient [6]. Matrix C is also called the conditional adjacency matrix in Post and Snijders [24].A specific result that will be used in the proofs of Theorems2, 3, and 4 below is the Perron-Frobenius theorem [25, 26]. More precisely, only the following weaker version of the Perron-Frobenius theorem will be used.Lemma 1.
If a square matrixD has strictly positive elements, then the eigenvector y corresponding to the largest eigenvalue of D has strictly positive elements.In the proof of Theorems2, 3, and 4 we use certain special matrices. Let S denote the upper triangular matrix of size k
×
k (2
≤
k
≤
m) with unit elements on and above the diagonal and all other elements zero. Its inverse S
-
1 is the matrix with unit elements on the diagonal and with elements -
1 adjacent and above the diagonal. Examples of S and S
-
1 of size 3
×
3 are(11)
S
=
1
1
1
0
1
1
0
0
1
,
S
-
1
=
1
-
1
0
0
1
-
1
0
0
1
. Furthermore, let I be the identity matrix of size (
m
-
k
)
×
(
m
-
k
), and let T denote the diagonal block matrix of size m
×
m with diagonal elements S and I. Examples of T and T
-
1 of size 4
×
4 are(12)
T
=
1
1
1
0
0
1
1
0
0
0
1
0
0
0
0
1
,
T
-
1
=
1
-
1
0
0
0
1
-
1
0
0
0
1
0
0
0
0
1
.We first consider the matrix C. Let y be the eigenvector corresponding to the largest eigenvalue λ of the matrix C. Theorem 2 shows that if the binary vectors can be ordered such that (3) and (4) hold, then this ordering is reflected in the corresponding elements of y.Theorem 2.
Suppose thatk of the m vectors, which without loss of generality can be taken as the first k, can be ordered such that (3) and (4) hold. Then the elements of y of C corresponding to these k vectors satisfy y
1
>
y
2
>
⋯
>
y
k
>
0.Proof.
SinceT is nonsingular, y is an eigenvector of C corresponding to λ if and only if z
=
T
-
1
y is an eigenvector of D
=
T
-
1
C
T corresponding to λ. Under the conditions of the theorem, the elements of D are positive and the elements of D
2 are strictly positive. Application of Lemma 1 then yields that the eigenvector z of D (or D
2) has strictly positive elements. The assertion then follows from the identity z
=
T
-
1
y.
In the remainder of the proof we show thatD has positive elements and D
2 has strictly positive elements. The matrix U
=
T
-
1
C has elements(13)
u
i
j
=
a
i
j
-
a
i
+
1
,
j
p
j for 1
≤
i
<
k and 1
≤
j
≤
m and(14)
u
i
j
=
a
i
j
p
j for k
≤
i
≤
m and 1
≤
j
≤
m. Under the conditions of the theorem properties (5) and (6) hold for the first k items. By (6), we have a
i
j
≥
a
i
+
1
,
j, and the matrix U has positive elements except for u
i
,
i
+
1 for 1
≤
i
≤
k
-
1. However by (5), we have p
i
>
p
i
+
1 and it follows that (15)
u
i
i
+
u
i
,
i
+
1
=
p
i
+
1
a
i
i
-
p
i
+
1
a
i
,
i
+
1
+
p
i
a
i
,
i
+
1
-
p
i
a
i
+
1
,
i
+
1
p
i
p
i
+
1
=
a
i
,
i
+
1
p
i
-
p
i
+
1
p
i
p
i
+
1
>
0 for 1
≤
i
≤
k
-
1. Hence, the matrix D
=
U
T has positive elements. Moreover, because the elements in the last row and last column of D are strictly positive, it follows that the elements of D
2 are strictly positive.An analogous result holds for the matrixA. Let y be the eigenvector corresponding to the largest eigenvalue λ of the matrix A. Theorem 3 shows that if the binary vectors can be ordered such that (3) and (4) hold, then this ordering is reflected in the corresponding elements of y of A.Theorem 3.
Suppose thatk of the m vectors, which without loss of generality can be taken as the first k, can be ordered such that (3) and (4) hold. Then the elements of y of A corresponding to these k vectors satisfy y
1
>
y
2
>
⋯
>
y
k
>
0.Proof.
The proof is similar to the proof of Theorem2. The matrix U
=
T
-
1
A has elements(16)
u
i
j
=
a
i
j
-
a
i
+
1
,
j for 1
≤
i
<
k and 1
≤
j
≤
m and(17)
u
i
j
=
a
i
j for k
≤
i
≤
m and 1
≤
j
≤
m. Under the conditions of the theorem properties (5) and (6) hold for the first k items. By (6), we have a
i
j
≥
a
i
+
1
,
j, and the matrix U has positive elements except for u
i
,
i
+
1 for 1
≤
i
≤
k
-
1. But by (5), we have p
i
>
p
i
+
1, and it follows that(18)
u
i
i
+
u
i
,
i
+
1
=
a
i
i
-
a
i
,
i
+
1
+
a
i
,
i
+
1
-
a
i
+
1
,
i
+
1
=
p
i
-
p
i
+
1
>
0 for 1
≤
i
≤
k
-
1
.Finally, Theorem4 below presents an ordering property of the matrix B. The ordering holds for a slightly stronger model than the one considered in Theorems 2 and 3. Theorem 4 shows that if the binary vectors can be ordered such that (3), (4), and (7) hold, then this ordering is reflected in the corresponding elements of y of B.Theorem 4.
Suppose thatk of the m vectors, which without loss of generality can be taken as the first k, can be ordered such that (3), (4), and (7) hold. Then the elements of y of B corresponding to these k vectors satisfy 0
<
y
1
<
y
2
<
⋯
<
y
k.Proof.
The proof is similar to the proof of Theorems2 and 3. Let T
-
1
′ denote the transpose of T
-
1. The matrix U
=
T
-
1
′
B has elements(19)
u
i
j
=
p
i
-
1
a
i
j
-
p
i
a
i
-
1
,
j
p
i
-
1
p
i for 2
≤
i
≤
k and 1
≤
j
≤
m and(20)
u
i
j
=
a
i
j
p
i for k
<
i
≤
m and 1
≤
j
≤
m. Under the conditions of the theorem properties (5) and (8) hold. By (8), we have p
i
-
1
a
i
j
≥
p
i
a
i
-
1
,
j, and the matrix U has positive elements except for u
i
i
-
1 for 2
≤
i
≤
k. However, by (5), we have p
i
-
1
>
p
i, and it follows that (21)
u
i
,
i
-
1
+
u
i
i
=
p
i
-
1
a
i
,
i
-
1
-
p
i
a
i
-
1
,
i
-
1
+
p
i
-
1
a
i
i
-
p
i
a
i
,
i
-
1
p
i
-
1
p
i
=
a
i
,
i
-
1
p
i
-
1
-
p
i
p
i
-
1
p
i
>
0 for 2
≤
i
≤
k.


## 4. An Illustration

In this section we consider an example from educational testing to illustrate some of the results from Section3. The data consist of responses of 1000 individuals to five items of the LSAT (Law School Admission Test). The test was designed to measure a one-dimensional latent variable. The example is part of a data set given by Bock and Lieberman [27]. The data set is distributed with the R package “ltm” written by Rizopoulos [28].Requirements (3), (4), and (7) cannot be checked directly for real life data. However, it can be shown that the Rasch model in (9) fits these data quite well. Using subroutines from the “ltm” package we fitted the Rasch model and the so-called two-parameter logistic model [19, 20]. In the Rasch model the items are allowed to differ in location. In the more general two-parameter model the items are also allowed to differ in slope. For these data the two-parameter model has four additional parameters. The log likelihoods of the models are -
2466.94 and -
2466.65, respectively, and the corresponding likelihood ratio test has a p value of p
=
.
967. Thus, the extra slope parameters are statistically not warranted.Requirements (3), (4), and (7) can also be studied by verifying if conditions (5), (6), and (8) hold. The proportions of correct responses are p
1
=
.
924, p
2
=
.
709, p
3
=
.
553, p
4
=
.
763, and p
5
=
.
870 for items 1 to 5, respectively. For verifying conditions (6) and (8), we suppose that the items are ordered on the proportions of correct responses, from easiest to hardest item (1, 5, 4, 2, and 3). In other words, in the following we assume that the items are ordered such that condition (5) holds.To study condition (6) we may inspect the matrix A of Russell-Rao coefficients. For the LSAT data this matrix is given by(22)
A
=
.
924
.
806
.
710
.
664
.
524
.
806
.
870
.
678
.
630
.
490
.
710
.
678
.
763
.
553
.
445
.
664
.
630
.
553
.
709
.
418
.
524
.
490
.
445
.
418
.
553
. The elements on the main diagonal are the proportions of correct responses. If we ignore the elements on the main diagonal it can be verified that the other four elements in each column of A are strictly decreasing. Hence, condition (6) holds.Since conditions (5) and (6) hold for all five LSAT items it follows from Theorem 3 that the ordering of the items is reflected in the eigenvector corresponding to the largest eigenvalue of A. The largest eigenvalue is λ
=
3.191 and the associated eigenvector is given by (
.
516
,
.
495
,
.
446
,
.
420
,
.
336
). The item ordering is thus reflected in the elements of the eigenvector.To verify whether condition (8) holds we may inspect the matrix B of Dice coefficients. For the LSAT data this matrix is given by(23)
B
=
1.00
.
872
.
768
.
719
.
567
.
926
1.00
.
779
.
724
.
563
.
931
.
889
1.00
.
725
.
583
.
937
.
889
.
780
1.00
.
590
.
948
.
886
.
805
.
756
1.00
. If we ignore the elements on the main diagonal it can be verified that the remaining four elements in the first, third, and fourth columns of B are strictly increasing. Furthermore, the elements in the second and fifth columns are roughly increasing. In both columns there is one anomaly. We may conclude that condition (8) holds approximately.If the five LSAT items satisfy conditions (5) and (8) it follows from Theorem 4 that the ordering of the items is reflected in the eigenvector corresponding to the largest eigenvalue of B. The largest eigenvalue is λ
=
4.106 and the associated eigenvector is given by (
.
424
,
.
431
,
.
446
,
.
454
,
.
478
). The item ordering is thus reflected in the elements of the eigenvector.


## 5. Conclusion

Similarity coefficients for binary vectors are frequently used in statistics for analyzing the structure between objects. Examples that are commonly used are the Russell-Rao coefficient [5] and the Dice coefficient [6]. Since the choice of a coefficient depends on the context of the data-analytic study, it is important that the different coefficients and their properties are well understood.In this paper we showed that ordinal information on latent variable models is reflected in the eigenvector corresponding to the largest eigenvalue of the coefficient matrices with Russell-Rao coefficients (Theorem3) and two asymmetric coefficients used in Dice [6] (Theorems 2 and 4). For other well-known coefficients like the Jaccard coefficient [4] and the simple matching coefficient similar ordering properties could not been found. The results may indicate that the Russell-Rao coefficient and Dice coefficients may lead to more clearly interpretable output if used as input in clustering methods or principal coordinates analysis. However, more research on this topic is needed.



---

*Source: 582731-2015-11-12.xml*