Acyclic Digraphs and Eigenvalues of (0, 1)–Matrices

Brendan D. McKay, Department of Computer Science, Australian National University,

Canberra, ACT 0200, AUSTRALIA

                             bdm@cs.anu.edu.au

Frédérique E. Oggier,^{1} Département de Mathématiques, Ecole Polytechnique Fédérale de Lausanne, 1015 Lausanne, SWITZERLAND

                         frederique.oggier@epfl.ch

Gordon F. Royle, Department of Computer Science & Software Engineering, University of

Western Australia, 35 Stirling Highway, Crawley, WA 6009, AUSTRALIA

                          gordon@csse.uwa.edu.au

N. J. A. Sloane,^{2} Internet and Network Systems Research Department, AT&T Shannon

Labs, 180 Park Avenue, Florham Park, NJ 07932–0971, USA

                           njas@research.att.com

Ian M. Wanless, Department of Computer Science, Australian National University, Canberra, ACT 0200, AUSTRALIA

                             imw@cs.anu.edu.au

Herbert S. Wilf, Mathematics Department, University of Pennsylvania, Philadelphia, PA 19104–6395, USA

                            wilf@math.upenn.edu

Abstract We show that the number of acyclic directed graphs with n labeled vertices is equal

to the number of n × n (0, 1)–matrices whose eigenvalues are positive real numbers.

1. Weisstein’s conjecture

Last year Eric W. Weisstein of Wolfram Research, Inc., computed the numbers of real n × n matrices of 0’s and 1’s all of whose eigenvalues are real and positive, for n = 1, 2, …, 5. He observed that the resulting sequence of values, viz.,

1, 3, 25, 543, 29281

1 This work was carried out during F. E. Oggier’s visit to AT&T Shannon Labs during the summer of 2003. She thanks the Fonds National Suisse, Bourses et Programmes d’Échange for support.

2 To whom correspondence should be addressed.

coincided with the beginning of sequence A003024 in [8], which counts acyclic digraphs with n labeled vertices. Weisstein conjectured that the sequences were in fact identical, and we prove this here.

Notation: a “digraph” means a graph with at most one edge directed from vertex i to vertex j, for 1 ≤ i ≤ n, 1 ≤ j ≤ n. Loops and cycles of length two are permitted, but parallel edges are forbidden. “Acyclic” means there are no cycles of any length.

Theorem 1.1. For each n = 1, 2, 3, …, the number of acyclic directed graphs with n labeled vertices is equal to the number of n×n matrices of 0’s and 1’s whose eigenvalues are positive real numbers.

Proof. Suppose we are given an acyclic directed graph G. Let A = A(G) be its vertex adjacency matrix. Then A has only 0’s on the diagonal, else cycles of length 1 would be present. So define B = I + A, and note that B is also a matrix of 0’s and 1’s. We claim B has only positive eigenvalues.

Indeed, the eigenvalues will not change if we renumber the vertices of the graph G consistently with the partial order that it generates. But then A = A(G) would be strictly upper triangular, and B would be upper triangular with 1’s on the diagonal. Hence all of its eigenvalues are equal to 1.

Conversely, let B be a (0, 1)–matrix whose eigenvalues are all positive real numbers. Then we have

1 ≥ \frac{1}{n}Trace(B)  (since all B_{i,i} ≤ 1)
= \frac{1}{n}(λ_{1} + λ_{2} + ⋯ + λ_{n})
≥ (λ_{1}λ_{2} … λ_{n})^{\frac{1}{n}}  (by the arithmetic-geometric mean inequality)
= (det B)^{\frac{1}{n}}
≥ 1  (since det B is a positive integer).  (1)

Since the arithmetic and geometric means of the eigenvalues are equal, the eigenvalues are all equal, and in fact all λ_{i}(B) = 1.

Now regard B as the adjacency matrix of a digraph H, which has a loop at each vertex. Since

Trace(B^{k}) = ∑_{i=1}^{n} λ_{i}^{k} = ∑_{i=1}^{n} 1 = n,

for all k, the number of closed walks in H, of each length k, is n.

Since the trace of B is equal to n, all diagonal entries of B are 1’s. Thus we account for all n of the closed walks of length k that exist in the graph H by the loops at each vertex. There are no closed walks of any length that use an edge of H other than the loops at the vertices.

Put A = B − I. Then A is a (0, 1)–matrix that is the adjacency matrix of an acyclic digraph. □

Remark. We found only two related results in the literature. D. M. Cvetković, M. Doob and H. Sachs [3, p. 81] show that a digraph G contains no cycle if and only if all eigenvalues of the adjacency matrix are 0. Nicolson [5] shows that for a nonnegative matrix M the following four conditions are equivalent: (a) there exists a permutation matrix P such that P MP′ is strictly upper triangular; (b) there is no positive cycle in M (i.e. in the weighted digraph there is no cycle whose edges all have positive weight); (c) permanent(M + I) = 1; and (d) M is nilpotent.

2. Corollaries.

(i) Let B be a (0, 1)–matrix whose eigenvalues are all positive real numbers. Then the eigenvalues are in fact all equal to 1. The only symmetric (0, 1)–matrix with positive eigenvalues is the identity.

(ii) Let B be an n × n matrix with integer entries and Trace(B) ≤ n. Then B has all eigenvalues real and positive if and only if B = I + N, where N is nilpotent.

(iii) If a digraph contains a cycle of length greater than 1, then its adjacency matrix has an eigenvalue which is zero, negative, or strictly complex. In fact, a more detailed argument, not given here, shows that if the length of the shortest cycle is at least 3, then there is a strictly complex eigenvalue.

(iv) The eigenvalues of a digraph consist of n − k 0’s and k 1’s if and only if the digraph is acyclic apart from k loops.

(v) Define two matrices B_{1}, B_{2} to be equivalent if there is a permutation matrix P such that P′B_{1}P = B_{2}. Then the number of equivalence classes of n × n (0,1)–matrices with all eigenvalues positive is equal to the number of acyclic digraphs with n unlabeled vertices. (These numbers form sequence A003087 in [8].) Proof. Two labeled graphs G_{1}, G_{2} with adjacency matrices A(G_{1}), A(G_{2}) correspond to the same unlabeled graph if and only if there is a permutation matrix P such that P′A(G_{1})P = A(G_{2}). The result now follows immediately from the theorem. □

(vi) Let B be an n × n (−1, +1)–matrix with all eigenvalues real and positive. Then n = 1 and B = [1]. Proof. The argument that led to (1) still applies and shows that all the eigenvalues are 1, det B = 1 and Trace(B) = n. By adding or subtracting the first row of B from all other rows we can clear the first column, obtaining a matrix

C = [ \begin{matrix}1 & ∗ \\ 0 & D \end{matrix} ] ,

where 0 is a column of 0’s and D is an n − 1 × n − 1 matrix with entries −2, 0, +2 and det D = det C = det B = 1. Hence 2^{n−1} divides 1, so n = 1. □

It would be interesting to investigate the connections between matrices and graphs in other cases–for example if the eigenvalues are required only to be real and nonnegative (see sequences A086510, A087488 in [8] for the initial values), or if the entries are −1, 0 or 1 (A085506).

3. Bibliographic remarks

Acyclic digraphs were first counted by Robinson [6, 7], and independently by Stanley [9]: if R_{n} is the number of acyclic digraphs with n labeled vertices, then

R_{n} = ∑_{k=1}^{n}(−1)^{k+1}\binom{n}{k}2^{k(n−k)}R_{n−k} ,

for n ≥ 1, with R_{0} = 1, and

∑_{n=0}^{∞} R_{n} \frac{x^{n}}{2^{\binom{n}{2}}n!} = [∑_{n=0}^{∞}(−1)^{n} \frac{x^{n}}{2^{\binom{n}{2}}n!}]^{−1} .

The asymptotic behavior is

R_{n} ∼ n!\frac{2^{\binom{n}{2}}}{Mp^{n}} ,

where p = 1.488 … and M = 0.474 . . ..

The asymptotic behavior of R(n, q), the number of these graphs that have q edges, was found by Bender et al. [1, 2], and the number that have specified numbers of sources and sinks has been found by Gessel [4].

References

[1] E. A. Bender, L. B. Richmond, R. W. Robinson and N. C. Wormald, The asymptotic number of acyclic digraphs, I, Combinatorica 6 (1986), 15–22.

[2] E. A. Bender and R. W. Robinson, The asymptotic number of acyclic digraphs, II, J. Combin. Theory, Ser. B 44 (1988), 363–369.

[3] D. M. Cvetković, M. Doob and H. Sachs, Spectra of Graphs, third ed., Barth, Heidelberg, 1995.

[4] I. M. Gessel, Counting acyclic digraphs by sources and sinks, Discrete Math., 160 (1996), 253–258.

[5] V. A. Nicholson, Matrices with permanent equal to one, Linear Algebra and Appl. 12 (1975), 185–188.

[6] R. W. Robinson, Enumeration of acyclic digraphs, in: R. C. Bose et al. (Eds.), Proc. Second Chapel Hill Conf. on Combinatorial Mathematics and its Applications (Univ. North Carolina, Chapel Hill, N.C., 1970), Univ. North Carolina, Chapel Hill, N.C., 1970, pp. 391-399.

[7] R. W. Robinson, Counting labeled acyclic digraphs, in: F. Harary (Ed.), New Directions in the Theory of Graphs, Academic Press, NY, 1973, pp. 239–273.

[8] N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at www.research.att.com/∼njas/sequences/, 1996–2004.

[9] R. P. Stanley, Acyclic orientations of graphs, Discrete Math., 5 (1973), 171–178.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 15A18, 15A36. Keywords: (0, 1)–matrix, acyclic, digraph, eigenvalue.

(Concerned with sequences \underline{A003024}, \underline{A003087}, \underline{A085506}, \underline{A086510}, and \underline{A087488}.)

Received May 29 2004; revised version received August 4 2004. Published in Journal of Integer Sequences, August 4 2004.

Return to Journal of Integer Sequences home page.