Bulletin T.CXXIX de l’Académie serbe des sciences et des arts - 2004 Classe des sciences mathématiques et naturelles sciences mathématiques, N\underline{o} 29

GENERALIZED INVERSE OF THE LAPLACIAN MATRIX AND SOME APPLICATIONS

I. GUTMAN, W. XIAO

(Presented at the 9th Meeting, held on December 26, 2003)

A b s t r a c t. The generalized inverse L^{†} of the Laplacian matrix of a connected graph is examined and some of its properties are established. In some physical and chemical considerations the quantity r_{ij} = (L^{†})_{ii} + (L^{†})_{jj} − (L^{†})_{ij} − (L^{†})_{ji} is encountered; it is called resistance distance. Based on the results obtained for L^{†} we prove some previously known and deduce some new properties of the resistance distance.

AMS Mathematics Subject Classification (2000): 05C50

Key Words: Laplacian matrix, Laplacian eigenvector (of graph), Laplacian eigenvalue (of graph), resistance distance

1. Introduction

In this work we are concerned with simple graphs, i.e., graphs without multiple or directed edges, and without loops. Let G be such a graph and let n be the number of its vertices, n ≥ 2 . Denote the vertices of G by v_{1}, v_{2}, …, v_{n}. Throughout this paper it is assumed that G is connected.

The degree d_{i} of the vertex v_{i} is the number of first neighbors of this vertex. Then the Laplacian matrix L = L(G) = ||L_{ij}|| of the graph G is defined as a square matrix of order n whose (i, j)-entry is given by

L_{ij} = \{ \begin{matrix}d_{i} & if i = j \\ −1 & if i ≠ j and the vertices v_{i} and v_{j} are adjacent \\ 0 & if i ≠ j and the vertices v_{i} and v_{j} are not adjacent . \end{matrix} (1)

Consequently, the Laplacian matrix is real and symmetric. Because the sum of each row and of each column is zero, this matrix is singular.

In what follows all matrices encountered are supposed to be square, of order n. If M is such a matrix, then M^{t} denotes its transpose and M^{−1} its inverse (provided it exists). By I is denoted the unit matrix, whereas by J and O the matrices whose all elements are, respectively, equal to unity and to zero.

The eigenvectors and eigenvalues of L(G) are said to be the Laplacian eigenvectors and Laplacian eigenvalues of the graph G. The Laplacian eigenvalues of the graph G will be denoted by μ_{k} and the corresponding eigenvectors by u_{k} , k = 1, 2, …, n, so that the equality

L(G) u_{k} = μ_{k} u_{k}

holds for k = 1, 2, …, n. In addition, u_{k} = (u_{1k}, u_{2k}, …, u_{nk})^{t} for k = 1, 2, …, n.

As usual, the Laplacian eigenvalues are labeled so that μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n}.

For details of Laplacian graph spectral theory see the surveys [1–7] and the recent paper [8]. Of the known results in this field we need the following.

It is always possible to choose the Laplacian eigenvectors to be real, normalized and mutually orthogonal. Throughout this paper we assume that this is the case.

Then U = (u_{1}, u_{2}, …, u_{n}) = ||u_{ij}|| is an orthogonal matrix, i.e., U U^{t} = U^{t} U = I, implying

∑_{k=1}^{n} u_{ki} u_{kj} = ∑_{k=1}^{n} u_{ik} u_{jk} = δ_{ij}  (2)

where, as usual, δ_{ij} = 1 for i = j and δ_{ij} = 0 for i ≠ i.

Because of U^{t} L(G) U = diag (μ_{1}, μ_{2}, …, μ_{n}) , we further have

L_{ij} = ∑_{k=1}^{n} μ_{k} u_{ik} u_{jk} .  (3)

For all graphs, μ_{n} = 0 . For all connected graphs, μ_{n−1} > 0 . The eigenvector corresponding to μ_{n} is of the form u_{n} = \frac{1}{\sqrt{n}} (1, 1, …, 1)^{t}. Because the eigenvectors u_{k} , k = 1, 2, …, n − 1 , are orthogonal to u_{n}, the relations

∑_{j=1}^{n} u_{jk} = 0  (4)

are obeyed for k = 1, 2, …, n − 1 .

Let M = ||M_{ij}|| be a square matrix, λ_{1}, λ_{2}, …, λ_{n} its eigenvalues and c_{k} = (c_{1k}, c_{2k}, …, c_{nk})^{t} its eigenvector, corresponding to λ_{k} , k = 1, 2, …, n. Let the eigenvectors of M be real, normalized and mutually orthogonal. Then,

M_{ij} = ∑_{k=1}^{n} λ_{k} c_{ik} c_{jk}

and if f(λ_{k}) exists for all values of k, then the matrix f(M) = ||(f(M))_{ij}|| is defined as

(f(M))_{ij} = ∑_{k=1}^{n} f(λ_{k}) c_{ik} c_{jk} .

In particular, if no eigenvalue of M is equal to zero,

(M^{−1})_{ij} = ∑_{k=1}^{n} \frac{1}{λ_{k}} c_{ik} c_{jk} .

If the matrix M is singular (i.e., some of its eigenvalues are equal to zero) then it has no inverse. For such matrices one defines the so-called generalized inverse [9,10] M^{†} = ||(M^{†})_{ij}||, as

(M^{†})_{ij} = ∑_{k=1}^{n} g(λ_{k}) c_{ik} c_{jk}

where

g(λ_{k}) = \{ \begin{matrix}1/λ_{k} & if λ_{k} ≠ 0 \\ 0 & if λ_{k} = 0 . \end{matrix}

In the special case of the Laplacian matrix of a connected graph, the generalized inverse L^{†} = L^{†}(G) = ||(L^{†})_{ij}|| is defined via

(L^{†})_{ij} = ∑_{k=1}^{n−1} \frac{1}{μ_{k}} u_{ik} u_{jk} .  (5)

Formula (5) is equivalent to U^{t} L^{†}(G) U = diag (1/μ_{1}, 1/μ_{2}, …, 1/μ_{n−1}, 0) , and implies that u_{1}, u_{2}, …, u_{n−1}, u_{n} are the eigenvectors of L^{†} with eigenvalues 1/μ_{1}, 1/μ_{2}, …, 1/μ_{n−1}, 0 , respectively.

2. Elementary Results

From (5) it immediately follows:

Lemma 1. The generalized inverse L^{†} of the Laplacian matrix of a connected graph is a real and symmetric matrix.

Lemma 2. The Laplacian matrix and its generalized inverse satisfy the relations

L J = J L = O ; L^{†} J = J L^{†} = O .

P r o o f. The relations stated in Lemma 2 are direct consequences of the fact that the sum of each row and each column of both L and L^{†} is equal to zero. For the Laplacian matrix this is evident from its definition, Eq. (1). For the sum of the elements in a row of L^{†} we get

∑_{j=1}^{n}(L^{†})_{ij} = ∑_{j=1}^{n} ∑_{k=1}^{n−1} \frac{1}{μ_{k}} u_{ik} u_{jk} = (∑_{k=1}^{n−1} \frac{1}{μ_{k}} u_{ik}) (∑_{j=1}^{n} u_{jk})

which is equal to zero because of relations (4). □

Lemma 3. If L and L^{†} pertain to a connected graph on n vertices, then

L L^{†} = L^{†} L = I − \frac{1}{n} J .

P r o o f. In view of Eqs. (3) and (5), and taking into account (2),

(L L^{†})_{ij} = ∑_{h=1}^{n} L_{ih} (L^{†})_{hj} = ∑_{h=1}^{n} (∑_{k=1}^{n} μ_{k} u_{ik} u_{hk}) (∑_{ℓ=1}^{n−1} \frac{1}{μ_{ℓ}} u_{hℓ} u_{jℓ})

= ∑_{k=1}^{n} ∑_{ℓ=1}^{n−1} \frac{μ_{k}}{μ_{ℓ}} u_{ik} u_{jℓ} (∑_{h=1}^{n} u_{hk} u_{hℓ}) = ∑_{k=1}^{n} ∑_{ℓ=1}^{n−1} \frac{μ_{k}}{μ_{ℓ}} u_{ik} u_{jℓ} δ_{kℓ}

= ∑_{ℓ=1}^{n−1} u_{iℓ} u_{jℓ} = ∑_{ℓ=1}^{n} u_{iℓ} u_{jℓ} − u_{in} u_{jn} = δ_{ij} − \frac{1}{n}

because of u_{in} = u_{jn} = \frac{1}{\sqrt{n}} . □

3. An Auxiliary Matrix

Whereas the Laplacian matrix L of a connected graph is singular, the matrix L + \frac{1}{n} J is non-singular.

Theorem 4. Let G be a connected graph, with Laplacian eigenvectors u_{1}, u_{2}, …, u_{n} and Laplacian eigenvalues μ_{1}, μ_{2}, …, μ_{n−1}, μ_{n} = 0 . Then u_{1}, u_{2}, …, u_{n} are also the eigenvectors of the matrix L(G) + \frac{1}{n} J with eigenvalues μ_{1}, μ_{2}, …, μ_{n−1}, 1 .

P r o o f. Let k < n. Then

(L + \frac{1}{n} J) u_{k} = L u_{k} + \frac{1}{n} J u_{k} = μ_{k} u_{k}

because, as a consequence of (4), J u_{k} = (0, 0, …, 0)^{t}.

Let k = n. Then L u_{n} = (0, 0, …, 0)^{t} whereas J u_{n} = n u_{n} because of u_{n} = \frac{1}{\sqrt{n}}(1, 1, …, 1)^{t}. Therefore,

(L + \frac{1}{n} J) u_{n} = \frac{1}{n} J u_{n} = u_{n}

and thus the eigenvalue of the matrix L + \frac{1}{n} J , corresponding to the eigenvector u_{n}, is equal to 1. □

Theorem 5. If G is a connected graph, then the inverse of the matrix L(G) + \frac{1}{n} J exists and is equal to L^{†}(G) + \frac{1}{n} J .

P r o o f. The existence of (L(G) + \frac{1}{n} J)^{−1} is guaranteed by Theorem 4. Using Lemmas 2 and 3, and the fact that J^{2} = n J , we have

(L + \frac{1}{n} J) (L^{†} + \frac{1}{n} J) = L L^{†} + \frac{1}{n}J L^{†} + \frac{1}{n} L J + \frac{1}{n^{2}} J^{2}

= (I − \frac{1}{n} J) + O + O + \frac{1}{n} J = I .  □

In what follows we denote the matrix (L(G) + \frac{1}{n} J)^{−1} by X. This matrix was studied in an earlier work [11] where also Theorem 4 was proven. According to Theorem 5 we now have

X = L^{†} + \frac{1}{n} J .  (6)

4. A Connection to Physics and Chemistry

In theoretical chemistry the notion of resistance distance was recently introduced [12]. This quantity is conceived in the following manner. To a connected graph G an electric network N (G) is associated, so that each edge of G is replaced by a resistor of unit resistance. Then the resistance distance between two distinct vertices v_{i} and v_{j} of the graph G, denoted by r_{ij} , is the effective electrical resistance between the corresponding two nodes of the network N (G) . By standard methods of the theory of electrical networks (using the Ohm and Kirchhoff laws) is can be shown that [13–15]

r_{ij} = (L^{†})_{ii} + (L^{†})_{jj} − (L^{†})_{ij} − (L^{†})_{ji}  (7)

which holds for i ≠ j. If, in addition we set r_{ii} = 0 for all i = 1, 2, …, n, then (7) formally holds also in this case, and we may define the resistance matrix as R = R(G) = ||r_{ij}||.

The resistance distance and the resistance matrix were much studied in the recent mathematico–chemical literature; for details see [11,16–20] and the references cited therein. Using the results from the preceding sections, we can now easily deduce some previously known and some hitherto not communicated relations for the resistance distance.

First of all, because of the symmetry of the generalized inverse (Lemma 1), formula (7) is simplified as

r_{ij} = (L^{†})_{ii} + (L^{†})_{jj} − 2 (L^{†})_{ij} .  (8)

Combining (8) with (5) we obtain

r_{ij} = ∑_{k=1}^{n−1} \frac{1}{μ_{k}} (u_{ik} u_{ik} + u_{jk} u_{jk} − 2 u_{ik} u_{jk}) = ∑_{k=1}^{n−1} \frac{1}{μ_{k}} (u_{ik} − u_{jk})^{2} ,

a formula earlier deduced in [19], but in a completely different (and more complicated) manner. Combining (8) with (6) we obtain

r_{ij} = X_{ii} + X_{jj} − 2 X_{ij},

also a formula earlier deduced in [11], again in a completely different and more complicated manner.

Theorem 6. If the matrices L, L^{†}, and R pertain to a connected graph, then

L R L = −2 L  (9)

Generalized inverse of the Laplacian matrix and some applications 21

and

L^{†} R L^{†} = −2 (L^{†})^{3} .  (10)

P r o o f. We first deduce the identity (10).

(L^{†} R L^{†})_{ij} = ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(L^{†})_{ik} r_{kℓ} (L^{†})_{ℓj}
= ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(L^{†})_{ik} [(L^{†})_{kk} + (L^{†})_{ℓℓ} − 2 (L^{†})_{kℓ}] (L^{†})_{ℓj}
= ∑_{k=1}^{n}(L^{†})_{ik} (L^{†})_{kk} (∑_{ℓ=1}^{n}(L^{†})_{ℓj}) + ∑_{ℓ=1}^{n}(L^{†})_{ℓj} (L^{†})_{ℓℓ} (∑_{k=1}^{n}(L^{†})_{ik})
− 2 ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(L^{†})_{ik} (L^{†})_{kℓ} (L^{†})_{ℓj} .

By Lemma 2,

∑_{ℓ=1}^{n}(L^{†})_{ℓj} = 0 and ∑_{k=1}^{n}(L^{†})_{ik} = 0

and therefore,

(L^{†} R L^{†})_{ij} = −2 ∑_{k=1}^{n} ∑_{ℓ=1}^{n}(L^{†})_{ik} (L^{†})_{kℓ} (L^{†})_{ℓj} = −2 [(L^{†})^{3}]_{ij}

which is tantamount to Eq. (10).

Now, multiplying (10) by L^{2} from both left and right we get

L^{2} L^{†} R L^{†} L^{2} = −2 L^{2}(L^{†})^{3} L^{2} .

By Lemmas 2 and 3,

L^{2} L^{†} = L (L L^{†}) = L (I − \frac{1}{n} J) = L
L^{†} L^{2} = (L^{†} L) L = (I − \frac{1}{n} J) L = L .

Therefore

L^{2} L^{†} R L^{†} L^{2} = L R L

and

L^{2}(L^{†})^{3} L^{2} = L L^{†} L = (I − \frac{1}{n} J) L = L .

Formula (9) follows. □

Theorem 7. In the case of connected graphs, the generalized inverse of the Laplacian matrix can be expressed in terms of the resistance matrix:

L^{†} = −\frac{1}{2} [R − \frac{1}{n} (R J + J R) + \frac{1}{n^{2}} J R J] .

P r o o f. Multiply (10) by L from both left and right, and use the same way of reasoning as in the proof of Theorem 6. □

REFERENCES

[1] R. B. B a p a t, The Laplacian matrix of a graph, Math. Student 65 (1996) 214–223.

[2] R. G r o n e, R. M e r r i s, The Laplacian spectrum of a graph II , SIAM J. Discr. Math. 7 (1994), 221–229.

[3] R. G r o n e, R. M e r r i s, V. S. S u n d e r, The Laplacian spectrum of a graph, SIAM J. Matrix Anal. Appl. 11 (1990), 218–238.

[4] R. M e r r i s, Laplacian matrices of graphs: A survey, Lin. Algebra Appl. 197–198 (1994), 143–176.

[5] R. M e r r i s, A survey of graph Laplacians, Lin. Multilin. Algebra 39 (1995), 19–31.

[6] R. M e r r i s, Laplacian graph eigenvectors, Lin. Algebra Appl. 278 (1988), 221–236.

[7] B. M o h a r, The Laplacian spectrum of graphs, in: Y. Alavi, G. Chartrand, O. R. Ollermann, A. J. Schwenk (Eds.), Graph theory, combinatorics, and applications, Wiley, New York, 1991, pp. 871–898.

[8] I. G u t m a n, Some properties of Laplacian eigenvectors, Bull. Acad. Serbe Sci. Arts (Cl. Math. Natur.) 127 (2003) 1–6.

[9] A. B e n – I s r a e l, T. N. E. G r e v i l l e, Generalized Inverses – Theory and Applications, Wiley, New York, 1974.

[10] S. L. C a m p b e l l, C. D. M e y e r, Generalized Inverses of Linear Transformations, Pitman, London, 1979.

[11] W. X i a o, I. G u t m a n, On resistance matrices, MATCH Commun. Math. Comput. Chem. 49 (2003), 67–81.

[12] D. J. K l e i n, M. R a n d i ć, Resistance distance, J. Math. Chem. 12 (1993), 81–95.

[13] S. S e s h u, M. B. R e a d, Linear Graphs and Electrical Networks, Addison–Wesley, Reading, 1961.

[14] J. A. E d m i n s t e r, Electric Circuits, McGraw–Hill, New York, 1965.

[15] B. B o l l o b á s, Modern Graph Theory, Springer–Verlag, New York, 1998, chapter 9.

[16] R. B. B a p a t, Resistance distance in graphs, Math. Student 68 (1999), 87–98.

[17] J. L. P a l a c i o s, Resistance distance in graphs and random walks, Int. J. Quantum Chem. 81 (2001), 29–33.

[18] D. J. K l e i n, Resistance–distance sum rules, Croat. Chem. Acta 75 (2002), 633–649.

[19] W. X i a o, I. G u t m a n, Resistance distance and Laplacian spectrum, Theor. Chem. Acc. 110 (2003) 284–289.

[20] R. B. B a p a t, I. G u t m a n, W. X i a o, A simple method for computing resistance distance, Z. Naturforsch. 58a (2003) 494–498.

Faculty of Science University of Kragujevac P. O. Box 60 34000 Kragujevac Serbia and Montenegro Department of Computer Science South China University of Technology Guangzhou 510641 P. R. China, and Xiamen University P. O. Box 1003 Xiamen 361005 P. R. China