Univ. Beograd. Publ. Elektrotehn. Fak.

Ser. Mat. 8 (1997), 64–71.

DOUBLY STOCHASTIC GRAPH MATRICES

Russell Merris

Let L(G) be the n × n Laplacian matrix of graph G. This note introduces the positive definite doubly stochastic matrix Ω(G) = (I_{n} + L(G))^{−1}.

Let G = (V, E) be a (simple) graph with vertex set V = {v_{1}, v_{2}, …, v_{n}} and edge set E of cardinality o(E) = m. Let D(G) be the diagonal matrix whose (i, i)- entry is d(v_{i}), the degree of vertex v_{i}. Denote by A(G) the n × n adjacency matrix whose (i, j)-entry is 1 if {v_{i}, v_{j}} ∈ E, and 0 otherwise. The Laplacian matrix is L(G) = D(G) − A(G). By Geršgorin’s Theorem, L(G) is positive semidefinite. Because its rows sum to zero, it is a singular M-matrix. Denote the eigenvalues of L(G) by λ_{1} ≥ λ_{2} ≥ ⋯ ≥ λ_{n−1} ≥ λ_{n} = 0. Then, either from Kirchhoff’s Matrix-Tree Theorem [2; 16] or the general theory of M-matrices [1, p.156; 10], λ_{n−1} > 0 if and only if G is connected, if and only if L(G) is irreducible. This observation led Fiedler [7] to define a(G) = λ_{n−1}, calling it the algebraic connectivity of G.

Numerous variations on the theme if “inverting” L(G) have appeared in the recent literature. (See, for example, [9], [13], [14], [17], and [21].) The purpose of this note is to introduce another.

1. Definition. If G is a graph on n vertices, define

Ω(G) = (I_{n} + L(G))^{−1}.

2. Proposition. If G is a graph on n vertices, then Ω(G) is a positive definite doubly stochastic matrix that is entrywise positive if and only if G is connected. Proof. Because M(G) = I_{n} + L(G) is a symmetric positive definite matrix, it is invertible and its inverse is positive definite. Indeed, the eigenvalues of Ω(G) are

(1)  1 ≥ \frac{1}{1 + a(G)} ≥ ⋯ ≥ \frac{1}{1 + λ_{1}} > 0.

Because M(G) is an M-matrix, its inverse is entrywise nonnegative. Because M(G) is irreducible if and only if G is connected [8, Chap. 3], it follows from the general theory of M-matrices [1, p.141] that Ω(G) is entrywise positive if and only if G is connected.

01991 Mathematics Subject Classification: Primary, 05C50. Secondary, 15A48, 15A51, 15A57.

Let e be the n-by-1 matrix each of whose entries is 1. Because e is an eigenvector of L(G) corresponding to λ_{n} = 0, it is an eigenvector of Ω(G) corresponding to the Perron eigenvalue 1. (Indeed, the eigenvectors of Ω(G) and L(G) are identical.) Hence, Ω(G)e = e, proving that Ω(G) is row stochastic. Beacuse Ω(G) is symmetric, the proof is complete □

Recall that a symmetric matrix is doubly positive (nonnegative) if it is entrywise positive (nonnegative) and positive (semi)definite. Thus, Ω(G) is a doubly nonnegative, doubly stochastic matrix which is doubly positive if and only if G is connected. It turns out that doubly nonnegative, doubly stochastic matrices have been the subject of several recent articles (see, e.g., [11] and [19]); M-matrices whose inverses are stochastic were studied in [20]. Moreover, Ω(G) is not the first doubly stochastic matrix to be associated with G. If Δ is the largest vertex degree of (a nontrivial graph) G, then I_{n} − Δ^{−1}L(G) is doubly stochastic.

Denote by G ∨ u the graph on n + 1 vertices and m + n edges obtained from G by joining each of its vertices to a new vertex u. (A vertex adjacent to every other vertex of a graph is said to be dominating vertex.) Observe that I_{n} + L(G) is the n × n principal submatrix of L(G ∨ u) obtained by deleting the row and column corresponding to u. Let us take a moment to consider Proposition 2 from this perspective.

Let H be a fixed but arbitrary graph on n + 1 vertices, {v_{1}, v_{2}, …, v_{n+1}}. Denote by L_{i}(H) the principal submatrix of L(H) obtained by deleting row and column i. (It seems that

∑_{i=1}^{n+1} L_{i}(H)

is known in the chemical literature as an “Eichinger matrix” [15].)

A real matrix P is said to be doubly superstochastic if there exists a doubly stochastic matrix S such that every element of P is greater than or equal to the corresponding element of S. Evidently, for a nonnegative matrix to be superstochastic each of its row and column sums must be at least 1. As the matrix

A = ( \begin{matrix}0 & 0 & 1 \\ 0 & 0 & 1 \\ 1 & 1 & 0 \end{matrix} )

shows, however, this necessary condition is not sufficient. Indeed [4], a nonnegative n × n matrix is doubly superstochastic if and only if the sum of the elements of every p × q submatrix is at least p + q − n.

3. Proposition. Let H be a connected graph on n + 1 vertices, {v_{1}, v_{2}, …, v_{n+1}}. Then L_{i}(H)^{−1} is a positive definite doubly superstochastic matrix. It is doubly stochastic if and only if v_{i} is a dominating vertex. It is entrywise positive if and only if the graph H − v_{i} (obtained by deleting vertex v_{i} and all the edges incident with it) is connected.

Proof. Because H is connected, L_{i}(H) is positive definite. Hence, it is invertible and its inverse is positive definite. Let Ĥ be the graph obtained from H by adding edges, if necessary, so that v_{i} becomes a dominating vertex. then L_{i}(Ĥ) = D + L_{i}(H), where D is an n × n matrix whose only nonzero entries (if any) are 1’s on the diagonal. In particular, each entry of the M-matrix B = L_{i}(Ĥ) is bigger than or equal to the corresponding entry of the M-matrix A = L_{i}(H). It follows from the general theory of M-matrices [10; 12, Thm 2.5.4] that A^{−1} ≥ B^{−1} (in the entrywise sense), with equality if and only if D = 0. Hence, the result is a consequence of Proposition 2 and the fact that A is irreducible if and only if H − v_{i} is connected. □

If H is a tree and d(v_{i}) = 1, then each entry of A = L_{i}(H)^{−1} is a positive integer. In particular, A ≥ S for every n × n doubly stochastic matrix S.

A general graph–theoretic interpretation for the entries of L_{i}(H)^{−1} can be obtained from the “all minors Matrix-Tree Theorem” [2]. Specifically, the (r, s)- entry of the classical adjoint adj (L_{i}(H)) is the number of 2-tree spanning forests of H in which v_{r} and v_{s} lie in one tree and v_{i} in the other. (If r = s and ε = {v_{r}, v_{i}} is an edge of H, this is the number of spanning trees of H that contain ε, an observation first made in [16, Thm. 2].) Of course, det (L_{i}(H)) = t(H), the number of spanning trees in H.

4. Corollary. Suppose H is a connected graph on n + 1 vertices. Fix i and let μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n} ≥ 0 be the eigenvalues of L_{i}(H). Then μ_{n} ≤ 1 with equality if and only if v_{i} is a dominating vertex. Proof. 1/μ_{n} is the largest eigenvalue of the doubly superstochastic matrix L_{i}(H)^{−1}. □

We now return to Ω(G).

5. Definition. Let G = (V, E) be a graph with vertex set V = {v_{1}, v_{2}, …, v_{n}} and edge set E. Denote by F_{G} the family consisting of all disconnected spanning forests of G. For each F ∈ F_{G}, let γ(F) be the product of the numbers of vertices in the connected components of F and γ_{i}(F) the product of the numbers of vertices in the connected components of F that do not contain vertex v_{i}. Finally, define F_{G}(i, j) = {F ∈ F_{G} : v_{i} and v_{j} belong to the same component of F }.

6. Proposition. Suppose G is a graph with n ≥ 2 vertices and t(G) spanning trees. Then the (i, j)-entry of Ω(G) is a fraction whose numerator is

(2)  t(G) + ∑_{F ∈F_{G}(i,j)}γ_{i}(F),

and whose denominator is

(3)  nt(G) + ∑_{F ∈F_{G}}γ(F).

Proof. Let H = G ∨ u, vhere u is viewed as the (n + 1)st vertex of H. Then, as we have observed, L_{n+1}(H) = I_{n} + L(G). Thus, Ω(G) = adj (L_{n+1}(H))/t(H).

To each spanning tree of G there correspond n different spanning trees of H (obtained by joining u to each of the n vertices of G). Thus, of the spanning trees T of H, exactly nt(G) have the property that T − u is connected. If T is a spanning tree of H such that F = T − u is a disconnected spanning forest of G, then u can/must be adjacent in T to exactly one vertex in each component of F. This gives γ(F) possibilities for T. Hence, t(H) is given by Formula (3).

To each spanning tree T of G, there corresponds one 2-component spanning forest of H in which u is an isolated vertex, namely, T + u. To each F ∈ F_{G}(i, j), there correspond γ_{i}(F) 2-component spanning forests of H in which v_{i} and v_{j} lie in one component and u in the other. (They arise by joining u to one vertex in each of the components of F that do not contain v_{i} and v_{j}.) Hence, by the all minors Matrix-Tree Theorem, the numerator of Ω(G) is given by Formula (2). □

7. Corollary. Suppose G is a graph on vertex set {v_{1}, v_{2}, …, v_{n}}, where n ≥ 2. Let Ω(G) = (ω_{ij}). Then

(i) ω_{ij} = 0 if and only if v_{i} and v_{j} lie in different connected com-

ponents of G;

(ii) ω_{ii} > ω_{ij}, for all j ≠ i, 1 ≤ i ≤ n;

(iii) ω_{ii} ≥ 1/(1 + d(v_{i})); and

(iv) ∑_{j=1}^{n} ∑_{F ∈F_{G}(i,j)} γ_{i}(F) = ∑_{F ∈F_{G}} γ(F).

Proof. A consequence of Formula (2), part (i) is a strengthening of the “entrywise positive” part of Proposition 2. Because F_{G}(i, j) is a proper subset of F_{G}(i, i), part (ii) follows from Formula (2). Part (iii) follows from a result of Fiedler [6] relating the corresponding diagonal entries of two mutually inverse positive definite matrices. While part (iv) can be proved directly by means of an elementary counting argument, it is an immediate consequence of Proposition 6 and the fact that Ω(G) is doubly stochastic. □

Consider the characteristic polynomial of L(G),

p_{G}(x) = det (xI_{n} − L(G)) = (x − λ_{1})(x − λ_{2}) ⋯ (x − λ_{n}).

The sum of the absolute values of the coefficients of p_{G}(x) is

(−1)^{n}p_{G}(−1) = (1 + λ_{1})(1 + λ_{2}) ⋯ (1 + λ_{n})

(4) = det (I_{n} + L_{G}))

(5) = det (L_{n+1}(G ∨ u)).

8. Corollary. Let G be a graph on n ≥ 2 vertices. Then (i) det(Ω(G)) = (−1)^{n}/p_{G}(−1); and

(ii) (−1)^{n}p_{G}(−1) = nt(G) + ∑_{F ∈F_{G}} γ(F).

Proof. Part (i) follows from Equation (4). Part (ii) is a consequence of Equation (5) and the fact that Formula (3) is the number of spanning trees in G ∨ u. (Part (ii) also follows from a result of Kel’mans [5, Thm. 1.4].) □

The second largest eigenvalue of Ω(G) is 1/(1 + a(G)), where a(G) is the algebraic connectivity of G. In particular,

(6)  \frac{1}{1 + a(G)} = max xΩ(G)x^{t},

where the maximum is over all real unit vectors x the sum of whose coordinates is 0.

9. Corollary. Let G be a graph on n ≥ 3 vertices with doubly stochastic graph matrix Ω(G) = (ω_{ij}). If 1 ≤ i < j ≤ n, then

(7)  \frac{1}{1 + a(G)} ≥ \frac{ω_{ii} + ω_{jj} − 2ω_{ij}}{2} .

Proof. Let x = (e_{i} − e_{j})/\sqrt{2}, where e_{i} is the ith standard basis vector in R^{n}. Then (7) is equivalent to 1/(1 + a(G)) ≥ xΩ(G)x^{t}.

[figure: 1; 2; 3; 4; 5; Figure l]

10. Example. If G is the graph illustrated in Figure 1, then

Ω(G) = \frac{1}{52} ( \begin{matrix}32 & 12 & 4 & 2 & 2 \\ 12 & 24 & 8 & 4 & 4 \\ 4 & 8 & 20 & 10 & 10 \\ 2 & 4 & 10 & 31 & 5 \\ 2 & 4 & 10 & 5 & 31 \end{matrix} )

and the value of the right-hand side of (7) is exhibited in position (i, j) of the matrix

B = \frac{1}{104} ( \begin{matrix}∗ & 32 & 44 & 59 & 59 \\ 32 & ∗ & 28 & 47 & 47 \\ 44 & 28 & ∗ & 31 & 31 \\ 59 & 47 & 31 & ∗ & 52 \\ 59 & 47 & 31 & 52 & ∗ \end{matrix} ) .

By Corollary 9, each off diagonal entry of B is a lower bound for 1/(1 + a(G)) ≐ 0.658. (The biggest lower bound emerging from this calculation is 59/104 ≐ 0.567. In general, it seems that the best choice for i and j corresponds to the position of a smallest entry in Ω(G).) The reason for exhibiting both the lower and upper triangular parts of matrix B is that it is the analog of the “resistance distance” matrix [14], in which Ω(G) replaces a generalized inverse of L(G).

11. Definition. Let G be a graph. Define F_{G}[i, j] = F_{G} \ F_{G}(i, j) = {F ∈ F_{G} : v_{i} and v_{j} lie in different components of F }. For each F ∈ F_{G}[i, j], denote by o(F_{i}) the number of vertices in the component of F containing v_{i} and by γ_{i,j}(F) the product of the numbers of vertices in the connected components of F that contain neither v_{i} nor v_{j} (with the understanding that the empty product is 1).

12. Corollary. Let G be a graph on n ≥ 3 vertices. If 1 ≤ i < j ≤ n, then

(8)  ∑_{F ∈F_{G}[i,j]} (o(F_{i}) + o(F_{j}))γ_{i,j}(F) ≤ \frac{2(−1)^{n}p_{G}(−1)}{1 + a(G)} .

Proof. Inequality (8) is just a rearrangement of terms when the values from Proposition 6 and Corollary 8 (ii) are substituted into Inequality (7). □

If A = (a_{ij}) is a real n × n matrix, its permanent is defined by

per (A) = ∑_{σ∈S_{n}} ∏_{i=1}^{n}a_{iσ(i)}.

Dating from the publications of [22], there has been a great deal of interest in permanents of doubly stochastic matrices.

13. Proposition. Let G be a graph on n vertices. Then

per (Ω(G)) ≥ \frac{[n!e]}{(n + 1)^{n}} ,

with equality if and only if G = K_{n}, the complete graph, where [·] is the greatest integer function and e is the base of the natural logarithms. Proof. As the result is easily verified for n ≤ 2, we assume n > 2. Suppose u and v are nonadjacent vertices of G. Let G′ be the graph obtained from G by adding a new edge, {u, v}. Then L(G′) = L(G) + Q, where Q is permutation similar to

the direct sum of ( \begin{matrix}1 & −1 \\ −1 & 1 \end{matrix} ) and the (n − 2)-square zero matrix. In particular,

L(G′) ≥ L(G) in the positive semidefinite sense. Therefore, Ω(G) ≥ Ω(G′), and [3] per (Ω(G)) > per (Ω(G′)). Thus, it remains to show that per (Ω(K_{n})) = [n!e]/(n + 1)^{n}. Because, I_{n} + L(K_{n}) = (n + 1)I_{n} − J_{n}, Ω(K_{n}) = (I_{n} + J_{n})/(n + 1), where J_{n} is the n × n matrix each of whose entries is 1.

Let Q_{k,n} be the set of all (\begin{matrix}n \\ k \end{matrix}) strictly increasing sequences of length k chosen

from {1, 2, …, n}. If A and B are n × n matrices, then [18, p.17]

per (A + B) = ∑_{k=0}^{n} ∑_{α,β∈Q_{k,n}} per (A[α|β]) per (B(α|β)),

where A[α|β] is the submatrix lying in rows α and columns β, and B(α|β) is submatrix of B obtained by deleting rows α and columns β. In particular,

(n + 1)^{n} per (Ω(K_{n})) = per (I_{n} + J_{n})

70 Russell Merris

= ∑_{k=0}^{n} ∑_{α∈Q_{k,n}} per (J_{n}(α|α)) = n! ∑_{k=0}^{n} 1/k! . □

The same proof will show that d_{χ}(Ω(G)) > d_{χ}(Ω(K_{n})) for any of a whole family of “generalized matrix functions”.

Added in proof. The author is grateful to D. J. Klein for pointing out that portions of Proposition 3 and Corollary 8 overlap results previously obtained in V. E. Golender, V. V. Drboglav, A. B. Rosenblit: Graph potentials method and its application for chemical information processing. J. Chem. Inf. Comput. Sci. 21 (1981), 126–204.

REFERENCES

1. A. Berman, R. J. Plemmons: Nonnegative Matrices in the Mathematical Sciences. Academic Press, New York, 1979.

2. S. Chaiken: A combinatorial proof of the all minors matrix tree theorem. SIAM J. Alg. Disc. Meth. 3 (1982), 319–329.

3. G. H. Chan, M. H. Lim: A conjecture involving generalized matrix functions. Linear Algebra Appl. 36 (1981), 157–163.

4. S. C. K. Chu, C. K. Li: Characterization of doubly superstochastic matrices by network flows. Intl. J. Math Ed. in Sci & Tech. 17 (1986), 127–129.

5. D. M. Cvetković, M. Doob, H. Sachs: Spectra of Graphs. Academic Press, New York, 1979.

6. M. Fiedler: Relations between the diagonal elements of two mutually inverse positive definite matrices. Czech. Math. J. 89 (1964), 39–51.

7. M. Fiedler: Algebraic connectivity of graphs. Czech. Math. J. 23 (1973), 298–305.

8. M. Fiedler: Special Matrices and Their Applications in Numerical Mathematics. Martinus Nijhoff, Boston, 1986.

9. M. Fiedler: Moore–Penrose involutions in the classes of Laplacians and simplices. Linear & Multilinear Algebra 39 (1995), 171–178.

10. M. Fiedler, V. Pták: On matrices with non-positive off-diagonal elements and positive principal minors. Czech. Math. J. 12 (1962), 382–400.

11. R. Grone, R. Loewy, S. Pierce: Nonchordal positive semi-definite stochastic matrices. Linear & Multilinear Algebra 32 (1992), 107–113.

12. R. A. Horn, C. R. Johnson: Topics in Matrix Analysis. Cambridge University Press, 1991.

13. S. Kirkland, M. Neumann, B. L. Shader: Characteristic vertices of weighted trees via Perron values. Linear & Multilinear Algebra 40 (1996), 311–325.

14. D. J. Klein, M. Randić: Resistance distance. J. Math. Chem. (1993), 81–95.

Doubly stochastic graph matrices 71

15. M. Kunz: On topological and geometrical distance matrices. J. Math. Chem. 13 (1993), 145–151.

16. M. Lewin: A generalization of the matrix-tree theorem. Math. Z. 181 (1982), 55–70.

17. R. Merris: An edge version of the matrix-tree theorem and the Wiener index. Linear & Multilinear Algebra 25 (1989), 291–296.

18. H. Minc: Permanents. Addison–Wesley, Reading, 1978.

19. N. Shaked–Monderer: Extreme chordal doubly nonnegative matrices with given row sums, manuscript.

20. R. L. Smith: M-matrices whose inverses are stochastic. SIAM J. Alg. Disc. Meth. 2 (1981), 259–264.

21. G. P. H. Styan, G. E. Subak–Sharpe: Inequalities and equalities associated with the Campbell–Youla generalized inverse of the indefinite-admittance matrix of resistive networks. Linear Algebra Appl., to appear.

22. B. L. van der Waerden: Aufgabe 45. Jber. Deutsch. Math. Verein. 35 (1926), 117.

California State University,  (Received October 7, 1996)

Hayward, CA 94542, USA merris@csuhayward.edu