Monotonicity properties of certain Laplacian eigenvectors

Ravindra B. Bapat∗
Indian Statistical Institute,
Delhi Centre, 7 S.J.S.S. Marg,
New Delhi 110 016, India
[email protected]

Abstract

Nath and Paul (Linear Algebra Appl., 460 (2014), 97-110) have shown that the
largest distance Laplacian eigenvalue of a path is simple and the corresponding eigen-
vector has properties similar to the Fiedler vector. We given an alternative proof,
establishing a more general result in the process.

AMS Classification: 05C05, 05C50

Keywords: Laplacian matrix, Distance Laplacian matrix, Tree, Fiedler vector

1 Introduction
Let T be a tree with vertex set V (T ) = {1, . . . , n}. We denote the degree of vertex i by
δi , i = 1, . . . , n. Recall that the Laplacian matrix L of T is the n × n matrix with its (i, j)-
element, i 6= j, equal to −1, if i and j are adjacent, and zero otherwise. The diagonal
elements of L are δ1 , . . . , δn . It is well-known that L is a positive semidefinite matrix with
rank n − 1. Let 0 = λ1 < λ2 ≤ · · · ≤ λn be the eigenvalues of L. The second smallest
eigenvalue λ2 is termed the algebraic connectivity of T and the corresponding eigenvector is
a Fiedler vector. For basic properties of the Laplacian matrix we refer to [2]. We state the
following classical result (see, for example, [2], Chapter 8, [3], Chapter 6).

Theorem 1 Let T be a tree with V (T ) = {1, . . . , n} and let f be a Fiedler vector of T. Let
f (v) denote the component of f indexed by the vertex v. Then one of the two cases must
occur:
∗ The author acknowledges support from the JC Bose Fellowship, Department of Science and Technology,
Government of India.

1
 Case (i). f (v) 6= 0 for any v. Then there is a unique edge {u1 , u2 } such that f (u1 ) > 0
and f (u2 ) < 0. Moreover, the values of f increase along any path starting at u1 and
not containing u2 , and the values of f decrease along any path starting at u2 and not
containing u1 .

Case (ii). f (v) = 0 for some v. Then there is a unique vertex u such that f (u) = 0 and
u is adjacent to a vertex on which f takes a nonzero value. Moreover, along any path
starting at u, the values of f either increase, decrease or are identically zero.

The unique edge in Case (i) is called the characteristic edge, while the unique vertex in
Case (ii) is called the characteristic vertex.
Let T be a tree with V (T ) = {1, . . . , n}. The distance between vertices i, j ∈ V (T ),
denoted dij , is defined to be the length (the number of edges) of the (unique) path from i to
j. We set dii = 0, i = 1, . . . , n. The distance matrix D is the n × n matrix with (i, j)-element
equal to dij .
The distance Laplacian of T, denoted DL , is the n × n matrix with (i, j)-element −dij if
Pn
i 6= j, and the (i, i)-element equal to j=1 dij , i = 1, . . . , n. It has been conjectured by Nath
and Paul [4] that if f is an eigenvector corresponding to the largest eigenvalue of DL , then
it has properties similar to that of a Fiedler vector, more specifically, it satisfies either Case
(i) or Case (ii) of Theorem 1. The conjecture was confirmed for a path in [4]. In this note we
prove a more general statement for a path, employing a technique used by Boman et al[1].

2 Eigenvectors of certain Laplacians

Let A be a symmetric n×n matrix. The Laplacian associated with A, denoted AL , is the n×n
P
matrix with (i, j)-element −aij if i 6= j, and the (i, i)-element equal to j6=i aij , i = 1, . . . , n.
In the rest of this paper we show that Conjectures 1 and 2 are true when the tree T is a
path. The proof of Conjecture 1 for a path is essentially contained in [1], Theorem 3.2. We
give the proof for completeness. We use the same proof technique and prove Conjecture 2 for
a path. Let 1 denote the vector of appropriate size of all ones. We now state a preliminary
result from [1]. The proof is easy and is omitted.

Lemma 2 Let S and T be matrices of order (n − 1) × n and n × (n − 1) respectively, given

by
 
  0 0 ··· 0
−1 1 0 0 0
 1 0 ··· 0 
 
 
 0 −1 1 0 0   
S=

.. .. , T =  1
  1 ··· 0 .
 . .   . .. 
 .
 . . 
  
0 0 ··· −1 1
1 1 ··· 1
0
Then ST = In−1 and T S = In − 1e1 , where e1 is the first column of the identity matrix In .

2
 We now prove a reformulation of a result from [1].

Lemma 3 Let A be an n × n symmetric matrix and let M = SAL T, where S and T are as
in Lemma 2. Let 0 = λ1 , λ2 , · · · , λn be the eigenvalues of AL . Then

(i) The eigenvalues of M are λ2 , . . . , λn .

(ii) If y is an eigenvector of AL such that y ⊥ 1, then Sy is an eigenvector of M corre-

sponding to the same eigenvalue.

(iii) If y is an eigenvector of M, then there exists an eigenvector x of AL corresponding to

the same eigenvalue such that x ⊥ 1 and y = Sx.

Proof: (i). Recall that if X and Y are matrices of order p × q and q × p respectively,
where p ≤ q, and if µ1 , . . . , µp are the eigenvalues of XY, then the eigenvalues of Y X
are given by µ1 , . . . , µp , along with 0 repeated q − p times. Note that M = SAL T and
AL T S = AL (In − 1e1 0 ) = AL , since AL 1 = 0. It follows that the eigenvalues of M are
λ2 , . . . , λ n .
(ii). Let AL y = αy. Note that since y 6= 0 and y ⊥ 1, then Sy 6= 0. We have M Sy =
SAL T Sy = SAL (In − 1e1 0 )y = SAL y = αSy and the proof is complete.
(iii). We define the n × 1 vector x as follows. For i = 1, . . . , n − 1, we set
n−1 n−1
1X X
xi = jyj − yj ,
n j=1 j=i

and
n−1
1X
xn = jyj .
n j=1

Then it can be verified that x ⊥ 1 and y = Sx. Since M y = αy, then SAL T Sx = αSx,
which implies SAL x = αSx. Since x ⊥ 1, we conclude AL x = αx.

Lemma 4 Let A be a symmetric n × n matrix and let M = SAL T, where S and T are as
in Lemma 2.

(i) Suppose aij ≥ aik if j < k < i and aij ≤ aik if i < j < k. Then mij ≥ 0 for any i 6= j.

(ii) Suppose aij ≤ aik if j < k < i and aij ≥ aik if i < j < k. Then mij ≤ 0 for any i 6= j.

Proof:
(i). Suppose aij ≥ aik if j < k < i and aij ≤ aik if i < j < k. For i < j,

mij = (SAL T )ij

Xn
= (SAL )ik tkj
k=1

3
 n
X
= (aik − ai+1,k )
k=j+1
≥ 0.

For i > j, using the fact that AL has zero row sums,
n
X
mij = (aik − ai+1,k )
k=j+1
j
X
= (−aik + ai+1,k )
k=1
≥ 0.

The proof of (ii) is similar.

An examination of the proof of Lemma 4 reveals that the following result is true, which
we state without proof.

Lemma 5 Let A be a symmetric n × n matrix and let M = SAL T, where S and T are as
in Lemma 2.

(i) Suppose aij > aik if j < k < i and aij < aik if i < j < k. Then mij > 0 for any i 6= j.

(ii) Suppose aij < aik if j < k < i and aij > aik if i < j < k. Then mij < 0 for any i 6= j.

Lemma 6 Let A be a symmetric n × n matrix such that aij ≥ 0 for all i 6= j. If λn is

the largest eigenvalue of A, then A has an eigenvector x for λn with xi ≥ 0, i = 1, . . . , n.
Furthermore, if aij > 0 for all i 6= j, then xi > 0, i = 1, . . . , n.

Proof: The result follows from the Perron-Frobenius Theorem, applied to the matrix
A + βI for a sufficiently large β.

The following is our main result.

Theorem 7 Let A be a symmetric, nonnegative n × n matrix with aij ≥ 0 for all i 6= j and
aii = 0, i = 1, . . . , n. Let 0 = λ1 ≤ λ2 ≤ · · · ≤ λn be the eigenvalues of AL .

(i) Suppose aij ≥ aik if j < k < i and aij ≤ aik if i < j < k. Then AL has an eigenvector
x corresponding to λn such that x ⊥ 1 and x1 ≤ · · · ≤ xn .

(ii) Suppose aij ≤ aik if j < k < i and aij ≥ aik if i < j < k. Then AL has an eigenvector
x corresponding to λ2 such that x ⊥ 1 and x1 ≤ · · · ≤ xn .

Proof: (i). Let M = SAL T, where S and T are as in Lemma 2. By Lemma 4, mij ≥ 0
for all i 6= j. By Lemma 3, the largest eigenvalue of M is λn , and by Lemma 6, M has
an eigenvector y corresponding to λn with yi ≥ 0, i = 1, . . . , n. By Lemma 3, AL has an

4
eigenvector x ⊥ 1 corresponding to λn such that y = Sx. Since yi ≥ 0, i = 1, . . . , n, it follows
that x1 ≤ x2 < · · · ≤ xn .
(ii). Let M be as in (i). By Lemma 4, mij ≤ 0 for all i 6= j. Let β be sufficiently large so
that βI − M has all entries nonnegative. By Lemma 3, the eigenvalues of M are λ2 , . . . , λn ,
and hence βI − M has eigenvalues β − λ2 , . . . , β − λn . The largest eigenvalue of βI − M is
β − λ2 and by the Perron-Frobenius Theorem it has an eigenvector y corresponding to this
eigenvalue with yi ≥ 0, i = 1, . . . , n. Clearly y must also be an eigenvector of M corresponding
to λ2 . By Lemma 3, AL has an eigenvector x ⊥ 1 corresponding to λ2 such that y = Sx.
Since yi ≥ 0, i = 1, . . . , n, it follows that x1 ≤ x2 < · · · ≤ xn .

Corollary 8 [4] Let T be the path with V (T ) = {1, . . . , n} and E(T ) = {{i, i + 1} : 1 ≤ i ≤
n − 1}. Let D be the distance matrix of T and let λn be the largest eigenvalue of DL with a
corresponding eigenvector x. Then either x1 ≥ · · · ≥ xn or x1 ≤ · · · ≤ xn .

Proof: Note that D satisfies the condition in Theorem 7, (i). By Lemma 5, if M = SDL T,
then mij > 0 for all i 6= j and hence λn is a simple eigenvalue of M, and therefore of DL .
It follows that the eigenvector of DL corresponding to λn must be unique up to a scalar
multiple. By Theorem 7, for any eigenvector x corresponding to λn , either x1 ≥ · · · ≥ xn or
x1 ≤ · · · ≤ xn .

I sincerely thank Manjunath Krishnapur, Arbind Lal and Sukanta Pati for comments on
an initial version of the manuscript.

References
[1] J.E. Atkins, E.G. Boman and B. Hendrickson, A spectral algorithm for seriation and
the consecutive ones problem, SIAM J. Comput. 28(1) (1998), 297–310.

[2] R.B. Bapat, Graphs and matrices, Second Edition, Springer, London, 2014.

[3] Jason J. Molitierno, Applications of combinatorial matrix theory to Laplacian matrices

of graphs, CRC Press, 2012.

[4] Milan Nath and Somnath Paul, On the distance Laplacian spectra of graphs, Linear
Algebra Appl. 460 (2014), 97–110.