M-Matrix Inverse problem for distance-regular graphs
Full text
M-Matrix Inverse problem for distance-regular graphs E. Bendito A. Carmona A.M. Encinas Departament de Matem`atica Aplicada III Universitat Polit`ecnica de Catalunya M. Mitjana Departament de Matem`atica Aplicada I Universitat Polit`ecnica de Catalunya 1 Introduction Very often problems in biological, physical and social sciences can be reduced to problems involving matrices which have some special structure. One of the most common situation is where the matrix in question has non– positive off–diagonal and non–negative diagonal entries; that is L=kI −A, k > 0 and A≥0, where the diagonal entries of Aare less or equal than k. These matrices appear in relation to systems of equations or eigenvalue problems in a broad variety of areas including finite difference methods for solving partial differential equations, input–output production and growth models in economics or Markov processes in probability and statistics. Of course, the combinatorial community can recognize within this type of matrices, the combinatorial Laplacian of a k–regular graph where Ais its adjacency matrix. If kis at least the spectral radius of A, then Lis called an M–matrix. We remark that M–matrices arise naturally in some discretizations of differential operators, particularly those with a minimum/maximum principle, such as the Laplacian, and as such are well–studied in scientific computing. In fact M–matrices satisfy monotonicity properties that are the discrete counterpart of the minimum principle, and it makes them suitable for the resolution of large sparse systems of linear equations by iterative methods. As well as a symmetric, irreducible and non–singular M–matrix appears as the discrete counterpart of a Dirichlet problem for a self–adjoint elliptic operator, its inverse corresponds with the Green operator associated with 1
the boundary value problem. On the other hand, when the M–matrix is singular, it can be seen as a discrete analogue of the Poisson equation for a self–adjoint elliptic operator on a manifold without boundary and then, its Moore–Penrose inverse corresponds with the Green operator too. A well–known property of an irreducible non–singular M–matrix is that its inverse is non–negative, [4]. However, the scenario changes dramatically when the matrix is an irreducible and singular M–matrix. In this case, it is known that the matrix has a generalized inverse which is non–negative, but this is not always true for any generalized inverse. For instance, it may happens that the Moore–Penrose inverse has some negative entries. We focus here in studying when the Moore–Penrose inverse of a symmetric, singular and irreducible M–matrix is itself an M–matrix. In particular, we study the case of distance–regular graphs and more specifically strongly regular graphs. 2 Preliminaries The triple Γ = (V, E, c) denotes a finite network; that is, a finite connected graph without loops nor multiple edges, with vertex set V, whose cardinality equals n, and edge set E, in which each edge {x, y}has been assigned aconductance c(x, y)>0. So, the conductance can be considered as a symmetric function c:V×V−→ [0,+∞) such that c(x, x) = 0 for any x∈Vand moreover, x∼y, that is vertex xis adjacent to vertex y, iff c(x, y)>0. The combinatorial Laplacian or simply the Laplacian of the network Γ is the endomorphism of C(V) that assigns to each u∈ C(V) the function L(u)(x) = X y∈V c(x, y)u(x)−u(y), x ∈V. It is well–known that Lis a positive semi–definite self–adjoint operator and has 0 as its lowest eigenvalue whose associated eigenfunctions are constant. So, Lcan be interpreted as an irreducible, symmetric, diagonally dominant and singular M–matrix, L. Therefore, the Poisson equation L(u) = fon Vhas solution iff P x∈V f(x) = 0 and, when this happens, there exists a unique solution u∈ C(V) such that P x∈V u(x) = 0,see [1]. 2
The Green operator is the linear operator G:C(V)−→ C(V) that assigns to any f∈ C(V) the unique solution of the Poisson equation with data f−1 nP x∈V f(x) such that P x∈V u(x) = 0. It is easy to prove that G is a positive semi–definite self–adjoint operator and has 0 as its lowest eigenvalue whose associated eigenfunctions are constant. Moreover, if P denotes the projection on the subspace of constant functions then, L◦G=G ◦ L =I − P. In addition, we define the Green function as G:V×V−→ IR given by G(x, y) = G(εy)(x), where εystands for the Dirac function at y. Therefore, interpreting Gor Gas a matrix, G, it is nothing else but the Moore– Penrose inverse of L, the matrix associated with L. In consequence, Gis an M–matrix iff G(x, y)≤0 for any x, y ∈Vwith x6=y. In [1] it was proved that for any x∈V, there exists νx∈ C(V) such that νx(x) = 0, νx(y)>0 for any y6=xand verifying L(νx) = 1−nεxon V . (1) We call νxthe equilibrium measure of V\ {x}and then we define capacity as the function cap ∈ C(V) given by cap(x) = P y∈V νx(y). 3 The Moore-Penrose inverse of distance–regular graphs We aim here at characterizing when the Moore–Penrose inverse of the combinatorial Laplacian matrix of a distance–regular graph is a M–matrix. Recall that a connected graph Γ is called distance–regular if there are integers bi, ci,i= 0, . . . , d such that for any two vertices x, y ∈Γ at distance i=d(x, y), there are exactly cineighbours of yin Γi−1(x) and bineighbours of yin Γi+1(x), where for any vertex x∈Γ the set of vertices at distance ifrom it is denoted by Γi(x).Moreover, |Γi(x)|will be denoted by ki. In particular, Γ is regular of degree k=b0. The sequence ι(γ) = {b0, b1, . . . , bd−1;c1, . . . , cd}, is called the intersection array of Γ. In addition, ai=k−ci−biis the number of neighbours of yin Γi(x), for d(x, y) = i. Clearly, bd=c0= 0, c1= 1 and the diameter of Γ is d. 3
Lemma 1 ([1, Prop. 4.1]) Let Γbe a distance–regular graph. Then, for all y∈V νx(y) = d(x,y)−1 X j=0 n− |Bj| |∂Bj|and cap(x) = d−1 X j=0 (n− |Bj|)2 |∂Bj| where |Bj|is the number of vertices at distance at most jfrom a given vertex and |∂Bj|=kjbj. The following result has been proved in [3] in a more general context. However, we prove it here for the sake of completeness. Theorem 2 The Moore–Penrose inverse of Lis an M–matrix iff for any x∈V cap(x)≤nνx(y)for any y∼x. Proof The Green function is given by G(x, y) = 1 n2cap(x)−n νx(y), see [1]. Therefore, Gis an M–matrix iff cap(x)≤nmin y∈V\{x}νx(y). The result follows by keeping in mind that min y∈V\{x}νx(y)= min y∼xνx(y), since if the minimum is attained at z6∼ x, then 1 = L(νx)(z) = X y∈V c(x, y)νx(z)−νx(y)≤0, which is a contradiction. Let Lbe the matrix associated with the combinatorial Laplacian of a distance–regular graph. Then, from Theorem 2 we get the following result. Proposition 3 The Moore–Penrose inverse of Lis an M–matrix iff d−1 X i=1 (n− |Bi|)2 |∂Bi|≤n−1 k. 4
In particular, for a strongly regular graph with parameters (n, k, a1, c2), the Moore–Penrose inverse of Lis an M–matrix iff a1≤3k−k2 n−1−n. Proof From Theorem 2 the Moore–Penrose inverse of Lis an M–matrix iff d−1 X j=0 (n− |Bj|)2 |∂Bj|≤n(n−1) k that is, iff (n−1)2 k+ d−1 X j=1 (n− |Bj|)2 |∂Bj|≤n(n−1) k. If Γ is a strongly regular graph, then d= 2 and hence the Moore–Penrose inverse of Lis an M–matrix iff (n−k−1)2≤b1(n−1) and the result follows keeping in mind that b1=k−1−a1. The above conclusion for strongly regular graphs also appeared in [6, Theorem 2.4], expressed in terms of the eigenvalues of the combinatorial Laplacian. If Γ is the n–cycle with vertices labeled {x1, . . . , xn}, then it is easy to verify that νxi(xj) = 1 2|i−j|n−|i−j|and cap(xi) = n(n2−1) 12 , i, j = 1, . . . , n. Therefore, by applying the above proposition, we obtain that the Moore– Penrose inverse of the combinatorial Laplacian of a n–cycle is a M–matrix iff n(n2−1) 12 ≤n(n−1) 2; that is, iff n≤5. This result was already obtained in [2, 5]. In addition, the Moore–Penrose inverse of Mis M†= (gij) where gij =1 12nn2−1−6|i−j|(n− |i−j|), i, j = 1, . . . , n. We point out that Petersen Graph does not fulfill the above condition, since its parameters is (10,3,0,1). Notice that the Green function 5
of the Petersen Graph is G(x, x) = 0.33; G(x, y) = 0.03 if d(x, y) = 1 and G(x, y) = −0.07 if d(x, y) = 2, since for any x, y ∈V,νx(y) = 3 if d(x, y) = 1, νx(y) = 4 if d(x, y) = 2 and cap(x) = 33. As an example of a strongly regular graph that fulfills the above condition we consider the family of Conference Graphs whose parameters are n, n−1 2,n−5 4,n−1 4. Corollary 4 The Moore–Penrose inverse of the Laplacian matrix of a conference graph is an M–matrix. Acknowledgments: This work has been partly supported by the Spanish Research Council (Comisi´on Interministerial de Ciencia y Tecnolog´ıa) under projects MTM2007-62551 and MTM2008-06620-C03-01/MTM. References [1] E. Bendito, A. Carmona, A.M. Encinas. Solving boundary value problems on networks using equilibrium measures. J. Funct. Anal. 171:155– 176, 2000. [2] E. Bendito, A. Carmona, A.M. Encinas, M. Mitjana. Generalized inverses of symmetric M-matrices. Linear Algebra Appl., 432:24382454, 2010. [3] E. Bendito, A. Carmona, A.M. Encinas, M. Mitjana. M-Matrix Generalized Inverses of Symmetric M-Matrices”, submitted. [4] A. Berman and R.J. Plemons. Nonnegative matrices in the mathematical sciences. Classics in Applied Mathematics, vol. 9, SIAM, 1994. [5] Y. Chen, S.J. Kirkland, M. Neumann. Group generalized inverses of M–matrices associated with periodic and nonperiodic Jacobi matrices. Linear Multilinear Algebra, 39:325–340, 1995. [6] S.J. Kirkland, M. Neumann. Group inverses of M–matrices associated with nonnegative matrices having few eigenvalues. Linear Algebra Appl., 220:181–213, 1998. 6