\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}{Proposition}[section]
\newtheorem{corollary}{Corollary}[section]
\newtheorem{lemma}{Lemma}[section] 

%\usepackage[usenames]{color}
%\usepackage[colorlinks=true,
%linkcolor=webgreen,
%filecolor=webbrown,
%citecolor=webgreen]{hyperref}
%
%\definecolor{webgreen}{rgb}{0,.5,0}
%\definecolor{webbrown}{rgb}{.6,0,0}

%\usepackage{amssymb,psfig,epsfig,latexsym,graphicx,here}

%\setlength{\textwidth}{6.5in}
%\setlength{\textheight}{9in}
%\setlength{\oddsidemargin}{0in}
%\setlength{\topmargin}{-0.25in}
%\setlength{\headheight}{0in}
%
%\newtheorem{lemma}{Lemma}
%\newtheorem{theorem}{Theorem}
%\newtheorem{coro}{Corollary}
%\newtheorem{corollary}{Corollary}
%\newtheorem{conj}{Conjecture}

\def\binom#1#2{{#1}\choose{#2}}

\newcommand{\eqn}[1]{(\ref{#1})}
\newcommand{\al}{\alpha}
\newcommand{\be}{\beta}
\newcommand{\ga}{\gamma}
\newcommand{\de}{\delta}
\newcommand{\eps}{\varepsilon}
\newcommand{\Om}{\Omega}
\newcommand{\sset}{\subseteq}
\newcommand{\bsq}{{\vrule height .9ex width .8ex depth -.1ex }}
\newcommand{\hsp}{\hspace*{\parindent}}
\newcommand{\FF}{{\mathbb F}}
\newcommand{\RR}{{\mathbb R}}
\newcommand{\NN}{{\mathbb N}}
\newcommand{\ZZ}{{\mathbb Z}}
\newcommand{\QQ}{{\mathbb Q}}
\newcommand{\sW}{{\mathcal W}}
\newcommand{\sS}{{\mathcal S}}
\newcommand{\sP}{{\mathcal P}}
\newcommand{\beql}[1]{\begin{equation}\label{#1}}
\newcommand{\eeq}{\end{equation}}
\newcommand{\brho}{\mbox{\boldmath $\rho$}}
\newcommand{\btau}{\mbox{\boldmath $\tau$}}
\newcommand{\bzero}{{\mathbf 0}}
\newcommand{\bp}{{\mathbf p}}
\newcommand{\bP}{{\mathbf P}}
\newcommand{\bt}{{\mathbf t}}
\newcommand{\bq}{{\mathbf q}}
\newcommand{\bv}{{\mathbf v}}
\newcommand{\bx}{{\mathbf x}}
\newcommand{\by}{{\mathbf y}}
\newcommand{\bm}{{\mathbf m}}
\newcommand{\leftBra}{\{ \hspace*{-.10in} \{ }
\newcommand{\rightBra}{\} \hspace*{-.10in} \} }


\makeatletter
\def\@sect#1#2#3#4#5#6[#7]#8{\ifnum #2>\c@secnumdepth
     \def\@svsec{}\else
     \refstepcounter{#1}\edef\@svsec{\csname the#1\endcsname.\hskip .75em }\fi
     \@tempskipa #5\relax
      \ifdim \@tempskipa>\z@
        \begingroup #6\relax
          \@hangfrom{\hskip #3\relax\@svsec}{\interlinepenalty \@M #8\par}%
        \endgroup
       \csname #1mark\endcsname{#7}\addcontentsline
         {toc}{#1}{\ifnum #2>\c@secnumdepth \else
                      \protect\numberline{\csname the#1\endcsname}\fi
                    #7}\else
        \def\@svsechd{#6\hskip #3\@svsec #8\csname #1mark\endcsname
                      {#7}\addcontentsline
                           {toc}{#1}{\ifnum #2>\c@secnumdepth \else
                             \protect\numberline{\csname the#1\endcsname}\fi
                       #7}}\fi
     \@xsect{#5}}
\def\@begintheorem#1#2{\it \trivlist \item[\hskip \labelsep{\bf #1\ #2.}]}

\def\section{\@startsection {section}{1}{\z@}{-3.5ex plus -1ex minus
 -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}
\makeatother
\makeatletter
\def\subsection{\@startsection {subsection}{1}{\z@}{-3.5ex plus -1ex minus
 -.2ex}{2.3ex plus .2ex}{\normalsize\bf}}

\makeatother

%\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\vskip .3in

\begin{center}
{\LARGE\bf Acyclic Digraphs and Eigenvalues of $(0,1)$--Matrices} \\
\vspace*{+.2in}
\end{center}

\begin{center}
Brendan D. McKay, 
Department of Computer Science, 
Australian National University, \\ 
Canberra, ACT 0200, AUSTRALIA \\
\href{mailto:bdm@cs.anu.edu.au}{\tt bdm@cs.anu.edu.au} \\
\smallskip

Fr\'ed\'erique~E.~Oggier,\footnote{
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'\'Echange for support.
}
D\'epartement de Math\'ematiques, \\ 
Ecole Polytechnique F\'ed\'erale de Lausanne, 
1015 Lausanne, SWITZERLAND \\
\href{mailto:frederique.oggier@epfl.ch}{\tt frederique.oggier@epfl.ch} \\
\smallskip

Gordon F. Royle, 
Department of Computer Science \& Software Engineering,
University of \\
Western Australia, 
35 Stirling Highway, 
Crawley, WA 6009, AUSTRALIA \\
\href{mailto:gordon@csse.uwa.edu.au}{\tt gordon@csse.uwa.edu.au} \\
\smallskip

N.~J.~A.~Sloane,\footnote{
To whom
correspondence should be addressed.}
Internet and Network Systems Research Department, 
AT\&T Shannon Labs, \\ 
180 Park Avenue, 
Florham Park, NJ 07932--0971, USA \\
\href{mailto:njas@research.att.com}{\tt njas@research.att.com} \\
\smallskip

Ian M. Wanless, 
Department of Computer Science, 
Australian National University, \\ 
Canberra, ACT 0200, AUSTRALIA \\
\href{mailto:imw@cs.anu.edu.au}{\tt imw@cs.anu.edu.au} \\
\smallskip

Herbert S. Wilf, 
Mathematics Department, 
University of Pennsylvania, \\ 
Philadelphia, PA 19104--6395, USA \\
\href{mailto:wilf@math.upenn.edu}{\tt wilf@math.upenn.edu} \\

\bigskip
\end{center}

\begin{abstract}
We show that the number of acyclic directed graphs with $n$
labeled vertices is equal to the number of $n\times n$ $(0, 1)$--matrices 
whose eigenvalues are positive real numbers.
\end{abstract}

\section{Weisstein's conjecture}
Last year Eric W. Weisstein of Wolfram Research, Inc.,
computed the numbers of real $n\times n$ matrices of $0$'s and $1$'s all
of whose eigenvalues are real and positive, for $n = 1, 2, \ldots, 5$.
He observed that the resulting sequence of values, viz.,
\[1,3,25,543,29281\]
coincided with the beginning of sequence 
\htmladdnormallink{A003024}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003024}
in \cite{OEIS},
which counts acyclic digraphs with $n$ labeled vertices.
Weisstein conjectured that the sequences were in fact identical,
and we prove this here.

\medskip

\noindent Notation:  a ``digraph'' means a graph with at most one edge
directed from vertex $i$ to vertex $j$, for $1 \le i \le n, 1 \le j \le n$.
Loops and cycles of length two are permitted, but parallel edges are
forbidden. ``Acyclic'' means there are no cycles of any length.
\begin{theorem}
For each $n=1,2,3,\dots$, the number of acyclic directed graphs with
$n$ labeled vertices is equal to the number of
$n\times n$ matrices of $0$'s and $1$'s whose eigenvalues are
positive real numbers.
\end{theorem}

\paragraph{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
\begin{eqnarray}\label{Eq1}
1&\ge& \frac{1}{n}\mathrm{Trace}(B)\qquad\quad\ (\mathrm{since\ all\ }B_{i,i}\le 1) \nonumber \\
&=&\frac{1}{n}(\lambda_1+\lambda_2+\dots+\lambda_n) \nonumber \\
&\ge&\left(\lambda_1\lambda_2\dots\lambda_n\right)^{\frac{1}{n}}\qquad
(\mbox{by~the~arithmetic-geometric~mean~inequality}) \nonumber \\
&=&\left(\det{B}\right)^{\frac{1}{n}} \nonumber \\
&\ge&1\qquad\qquad\quad\qquad\quad (\mathrm{since}\ \det{B}\ \mathrm{is\ a\ positive\ integer}).
\end{eqnarray}
Since the arithmetic and geometric means of the eigenvalues are equal,
the eigenvalues are all equal, and in fact all $\lambda_i(B)=1$.

Now regard $B$ as the adjacency matrix of a digraph $H$,
which has a loop at each vertex. Since
\[\mathrm{Trace}(B^k)=\sum_{i=1}^n\lambda_i^k=\sum_{i=1}^n1=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. $\Box$

Remark. We found only two related results in the literature.
D. M. Cvetkovi\'c, M. Doob and H. Sachs \cite[p. 81]{CDS95}
show that a digraph $G$ contains no cycle if and only if all eigenvalues
of the adjacency matrix are $0$.
Nicolson \cite{Nic75} shows that for a nonnegative matrix $M$
the following four conditions are equivalent:
(a) there exists a permutation matrix $P$  such that $PMP'$ 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.


\section{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\times n$ matrix with integer entries
and Trace$(B)\le 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 {\em equivalent} if
there is a permutation matrix $P$ such that
$P' B_1 P ~=~ B_2$.
Then the number of equivalence classes of $n \times n$ (0,1)--matrices
with all eigenvalues positive is equal to the number
of acyclic digraphs with $n$ unlabeled vertices.
(These numbers form sequence
\htmladdnormallink{A003087}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A003087} in \cite{OEIS}.) \\
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. $\Box$

(vi) Let $B$ be an $n \times n$ $(-1, +1)$--matrix
with all eigenvalues real and positive. Then $n=1$ and $B=[1]$. \\
Proof. The argument that led to \eqn{Eq1} 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 ~=~
\left[ \begin{array}{cc} 1 & \ast \\ \bf{0} & D \end{array} \right] \,,
$$
where $\bf{0}$ is a column of $0$'s and $D$ is an $n-1 \times 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$. $\Box$

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
\htmladdnormallink{A086510}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A086510},
\htmladdnormallink{A087488}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A087488} in \cite{OEIS} for the initial values),
or if the entries are $-1$, $0$ or $1$
(\htmladdnormallink{A085506}{http://www.research.att.com/cgi-bin/access.cgi/as/njas/sequences/eisA.cgi?Anum=A085506}).

\section{Bibliographic remarks}
Acyclic digraphs were first counted by Robinson \cite{Rob70, Rob73}, and
independently by Stanley \cite{Sta73}: if $R_n$ is the
number of acyclic digraphs with $n$ labeled vertices, then
$$
R_n ~=~ \sum_{k=1}^{n} (-1)^{k+1} {\binom{n}{k}} 2^{k(n-k)} R_{n-k} ~,
$$
for $n \ge 1$, with $R_0 = 1$, and
\[\sum_{n=0}^{\infty}R_n\frac{x^n}{2^{{n\choose
2}}n!}=\left[\sum_{n=0}^{\infty}(-1)^n\frac{x^n}{2^{{n\choose
2}}n!}\right]^{-1} ~.\]
The asymptotic behavior is
\[R_n ~\sim~ n!\frac{2^{{n\choose 2}}}{Mp^n} ~,\]
where $p=1.488\ldots$ and $M=0.474\ldots$.

The asymptotic behavior of $R(n,q)$, the number of these graphs that have $q$
edges, was found by Bender \textit{et al.} \cite{BRRW, BR88}, and the number
that have specified numbers of sources and sinks has been found by Gessel
\cite{Ges96}.

\begin{thebibliography}{aaa}
\bibitem{BRRW} E. A. Bender, L. B. Richmond, R. W. Robinson and N. C. Wormald,
The asymptotic number of acyclic digraphs, I, 
{\em Combinatorica} {\bf 6} (1986), 15--22.

\bibitem{BR88} E. A. Bender and R. W. Robinson, The asymptotic number
of acyclic digraphs, II, {\em J. Combin. Theory}, Ser. {\bf B 44} (1988), 363--369.

\bibitem{CDS95}
D. M. Cvetkovi\'c, M. Doob and H. Sachs, {\em Spectra of Graphs}, 
third ed., Barth, Heidelberg, 1995.

\bibitem{Ges96} I. M. Gessel, Counting acyclic digraphs by sources and sinks,
{\em Discrete Math.}, {\bf 160} (1996), 253--258.

\bibitem{Nic75} V. A. Nicholson,
Matrices with permanent equal to one,
{\em Linear Algebra and Appl.} {\bf 12} (1975), 185--188.

\bibitem{Rob70} R. W. Robinson, Enumeration of acyclic digraphs, in:
R. C. Bose \textit{et al.} (Eds.),
{\em 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.

\bibitem{Rob73}
R. W. Robinson, Counting labeled acyclic digraphs, in:
F. Harary (Ed.),
{\em New Directions in the Theory of Graphs},
Academic Press, NY, 1973, pp. 239--273.

\bibitem{OEIS}
N. J. A. Sloane,
{\em \htmladdnormallink{The On-Line Encyclopedia of Integer Sequences}
{http://www.research.att.com/~njas/sequences/}},
published electronically at www.research.att.com/$\sim$njas/sequences/, 1996--2004.


\bibitem{Sta73} R. P. Stanley, Acyclic orientations of graphs, {\em Discrete
Math.}, {\bf 5} (1973), 171--178.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:
Primary 05A15; Secondary 15A18, 15A36.

\noindent \emph{Keywords:}
$(0, 1)$--matrix, acyclic, digraph, eigenvalue.

\bigskip
\hrule
\bigskip

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

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received May 29 2004;
revised version received August 4 2004.
Published in {\it Journal of Integer Sequences}, August 4 2004.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.math.uwaterloo.ca/JIS/}.
\vskip .1in

\end{document}