Leading eigenvalues of adjacency matrices of star-like graphs with fixed numbers of vertices and edges

Abstract

For a sequence of adjacency matrices, describing the unfolding of a network from the graph of a star, through graphs of a broom, to the graph of a link with constant vertices and edges, we show that the leading eigenvalue (the spectral radius) satisfies a simple algebraic equation. The equation allows easy numerical computation of the leading eigenvalue as well as a direct proof of its monotonicity in terms of the maximal degree of vertices.

Keywords:

• Leading eigenvalue
• Adjacency matrix
• network
• infectious disease model

PUBLIC INTEREST STATEMENT

In a network of agents susceptible to an infectious disease, assume that we know all details of the structure of the network: whether and how different agents are connected to each other. How can we predict whether the infectious disease will cause an epidemic if one or more agents are infected? How can we design policies to alter the structure of the network in order to reduce the speed at which the disease spreads? Similar problems arise in many other networks. These problems can often be formulated as a mathematical problem of understanding how certain global quantities such as the leading eigenvalue of a nonnegative matrix depends on its entries. In a simple situation when a network in the shape of a star unfolding into a broom and eventually forming a link, we give a complete description of the leading eigenvalue in terms of the network structure.

1. Introduction

Our study of how the leading eigenvalue, or the spectral radius, of an adjacency matrix of a network varies when the structure of the network changes is motivated by recent interests of research in how an infectious disease spreads over a network (Brauer, 2008; Diekmann & Heesterbeek, 2000; Newman, 2002, 2010). M.E.J. Newman stated in the introduction to Chapter 16 of (Newman, 2010): “once we have measured and quantified the structure of a network, how do we turn the results into predictions or conclusions about how the overall system will behave? Unfortunately, progress in this area has been far slower than progress on characterizing structure … ”. Imagine that we have a network of $n$ agents susceptible to an infectious disease just discovered in the network. Assume that $0\le {\beta }_{ij}\le 1$ is the transmission rate from agent $i$ to agent $j$ and $0\le {\delta }_i\le 1$ is the recovery rate for agent $i$. Then, there is a close relation between the leading eigenvalue of the matrix $A=(a_{ij})$, where $a_{ij}={\beta }_{ij},i\ne j,a_{ii}={\delta }_i$, and the essential parameters of the infectious disease: the reproductive number $R_0$, the speed at which the infectious disease can spread in the network, and the rate at which the disease is eradicated from the network (Diekmann & Heesterbeek, 2000; Gatto, Mari, & Rinaldo, 2013; Jiang, 2016; Kostova, 2009). When the transmission rates and the recovery rates are independent of individual agent, the study of the leading eigenvalue of the matrix $A$ on its entries is reduced to determining how the leading eigenvalue of an adjacency matrix depends on the topology of the network. There are abundant results in graph theory on this subject, e.g. (Brouwer & Haemers, 2010; Brualdi & Hoffman, 1985; Bunimovich & Webb, 2014; Li & Feng, 1979; Liu, Lu, & Tian, 2004; Patuzzi, de Freitas, & Del-Vecchio, 2014). Many address the dependence of the leading eigenvalue on the underlying undirected connected graph. However, the underlying structure of the graph is usually not motivated by actual problems in applications nor dynamic. In this short paper, our interest is restricted to the study of the follow particular problem: assuming that the structure of a graph of $n$ agents is evolving along a well-defined path, how does its leading eigenvalue change? We solve this problem completely in the simple case where the graph unfolds from a star to a link while both numbers of vertices and edges remain constant. The leading eigenvalue can be uniquely determined by solving a quite simple algebraic equation. As a consequence, we obtain its asymptotic behavior as the size of the network increases and also a direct proof of its monotonicity in terms of the maximal degree of vertices.

2. Main result

Let $G_k,k=1,2,\cdots ,n-1$ be the following sequence of undirected connected graphs of vertices $\{v_1,v_2,\cdots ,v_n\}$. The set of edges of $G_1$ is $E_1=\{e(1,2),e(1,3),\cdots ,e(1,n)\}$ and for $2\le k\le n-1$, the set of edges of $G_k$, $E_k=\{e(1,2),e(2,3),\cdots ,e(k-1,k),e(k,k+1),\cdots ,e(k,n)\}$. Note that $G_1$ and $G_2$ are the same star of $n$ vertices and $G_{n-1}$ is the link between two vertices $v_1$ and $v_n$.

The adjacency matrix $A=(a_{ij})$ of any graph is a square matrix with entries either $0$ or $1$. An entry $a_{ij}$ of an Adjacency matrix is $1$ if and only if two vertices $v_i$ and $v_j$ are connected by an edge. When a graph is undirected, its adjacency matrix is a symmetric nonnegative matrix. By the Perron-Frobenius theorem, matrix $A$ has an eigenvalue $\lambda >0$, the leading eigenvalue, which is simple and greater than the magnitude of any other eigenvalues of $A$ (Berman & Plemmons, 1994; Brouwer & Haemers, 2010).

For $k=1,2,\cdots ,n-1$, let $A_n(k)$ denote the adjacency matrix of the graph $G_k$ and let ${\lambda }_n(k)$ be the leading eigenvalue of $A_n(k)$. Let $m=n-k-1$. We note that the diameter of the graph $G_k$ is exactly $k$ and the unique maximal degree of vertices of $G_k$ is $n-k+1=m+2$.

Theorem 1.

The leading eigenvalue of $A_n(k)$, ${\lambda }_n(k)$, decreases in $k$, $k=2,\cdots ,n-1$. For $n\ge 7$ and $1\le k\le n-4$,

(1) ${\lambda }_n(k)=\sqrt{x_n(k)}+\frac{1}{\sqrt{x_n(k)}},$(1)

where $x_n(k)\in (1,n-k-1)$ is the unique solution to the equation

(2) $x^{k+1}=\frac{(n-k-1)x-1}{(n-k-1)-x},orequivalently,x^{n-m}=\frac{mx-1}{m-x}.$(2)

Since the one-variable function $t+\frac{1}{t}$ is an increasing function on the interval $[1,\mathrm{\infty })$, the monotonicity of ${\lambda }_n(k)$ in $k$ follows from the monotonicity of $x_n(k)$ once the relation (1) is established. A direct estimation of the unique solution $x_n(m)>1$ to the equation $x^{n-m}=\frac{mx-1}{m-x}$ leads to the following asymptotic behavior of $x_n(m)$ when $n$ approaches infinite.

Corollary 1.

For each fixed $m\ge 3$, $\underset{n\to \mathrm{\infty }}{lim}{x}_n(m)=m.$

Remarks

1. The monotonicity of ${\lambda }_n(k)$ in $k$ is known. It follows from a theorem in (Li & Feng, 1979) and also from Corollary 2.2 in (Patuzzi et al., 2014). Showing that the leading eigenvalue ${\lambda }_n(k)$ satisfying the equations (1) and (2) is new. The equations give not only an alternative direct proof of the monotonicity of ${\lambda }_n(k)$ in $k$, but also a way to estimate the rate of change of ${\lambda }_n(k)$ in $k$. 2. This formulation of the leading eigenvalue is reminiscent of another interesting result concerning the limit points of all leading eigenvalues of trees with $\lambda <3$ (Hoffman, 1972). 3. The graph $G_k$ is called a broom in (Del-Vecchio, Gutman, Trevisan, & Vinagre, 2009).

The rest of the paper is devoted to the proof the main theorem. In Section 3.1, using the standard cofactor expansion, we first show the leading eigenvalue ${\lambda }_n(k)$ of the adjacency matrix $A_n(k)$ satisfies a recursive relation of characteristic polynomials of the tri-diagonal adjacency matrices. Solving this recursive relation, we obtain a representation of the eigenvalue ${\lambda }_n(k)$ in terms of the unique solution of a simple algebraic equation. The monotonicity of ${\lambda }_n(k)$ in terms of $n$ follows easily. A detailed proof of the monotonicity of ${\lambda }_n(k)$ in $k$ via the implicit differentiation is in Section 3.2.

3. Proofs

For $k=1,2,\cdots ,n-1$, let $P_n(k)$ denote the characteristic polynomial of the adjacency matrix $A_n(k):$ $P_n(k)=det(\lambda I-A_n(k))$. Let $Q_k=det(\lambda I-A_k(k-1))$ denote the characteristic polynomial of the tri-diagonal adjacency matrix $A_k(k-1)$. We can directly verify via cofactor expansion that $P_n(k)$ and $Q_k$ possess the following properties. The second recursive relation is obtained by expanding the determinant along the last column first and then the last row. Iterating the recursive relation, we obtain the third equation. The details of the proof of these recursive relations are omitted since the verification of them is straightforward. See also (Del-Vecchio et al., 2009; Kulkarni, Schmidt, & Tsui, 1999).

Proposition 1

(1) $Q_1=\lambda ,Q_2={\lambda }^2-1,Q_k=\lambda Q_{k-1}-Q_{k-2},k\ge 3.$

(2) $P_n(k)=\lambda P_{n-1}(k)-{\lambda }^{n-k-1}{Q}_{k-1}.$

(3) $P_n(k)={\lambda }^{n-k-1}[\lambda Q_k-(n-k)Q_{k-1}],2\le k\le n-1$.

3.1. Eigenvalue ${\lambda }_n(k)$ satisfying the equations (1) and (2)

By Proposition 1 (3), the leading eigenvalue ${\lambda }_n(k)>0$ of $A_n(k)$ satisfies the equation

(3) $\lambda Q_k-(n-k)Q_{k-1}=0.$(3)

For convenience, we let $m=n-k-1$. For $1\le k\le n-1$, $0\le m\le n-2$. We have the following characterization of ${\lambda }_n(k)$ when $m\ge 3$.

Lemma 1 When $m\ge 3$, the leading eigenvalue ${\lambda }_n(k)$ has the properties ${\lambda }_n(k)>2$ and ${\lambda }_n(k)=\sqrt{x_n(k)}+\frac{1}{\sqrt{x_n(k)}}$, where $x_n(k)\in (1,m)$ is the unique real solution to the equation

(4) $x^{n-m}=\frac{mx-1}{m-x}.$(4)

Proof.

We consider the recursive relation (1) in Proposition 1, $Q_{k+1}=\lambda Q_k-Q_{k-1}$, $k=2,3,\cdots$. Let $\lambda =b+\frac{1}{b}$. The equation has a unique real solution for $b$ if and only if $\lambda \ge 2$. Otherwise, $b$ is a complex number. We have

(5) $Q_{k+1}=\lambda Q_k-Q_{k-1}=\left(b+\frac{1}{b}\right)Q_k-Q_{k-1}=b{Q}_k+\frac{1}{b}{Q}_k-Q_{k-1}$(5)

and thus,

(6) $Q_{k+1}-b{Q}_k=\frac{1}{b}\left(Q_k-b{Q}_{k-1}\right).$(6)

Iterate Equation (6) and notice that $Q_1=\lambda$ and $Q_2={\lambda }^2-1$. Since ${\lambda }^2-1-b\lambda =\frac{1}{b^2}$, we have

(7) $Q_{k+1}-b{Q}_k=\frac{1}{b^{k-1}}({\lambda }^2-1-b\lambda )=\frac{1}{b^{k+1}}$(7)

Further iterate the last recursive relation, we have for $i=1,2,\cdots$,

(8) $Q_{k+1}=\frac{1}{b^{k+1}}++\dots +\frac{1}{b^{k-2i+1}}+b^{i+1}{Q}_{k-i}.$(8)

Thus, when $i=k-2$,

(9) $Q_{k+1}=\frac{1}{b^{k+1}}+\frac{1}{b^{k-1}}+\dots +b^{k-5}+b^{k-1}{Q}_2.$(9)

Sum up the geometric progression we have, for $k\ge 2$,

(10) $Q_{k+1}=\frac{1}{b^{k+1}}\left[\frac{1-b^{2(k-1)}}{1-b^2}\right]+b^{k-1}{Q}_2$(10)

(11) $=\frac{1}{b^{k+1}}\left[\frac{1-b^{2(k-1)}}{1-b^2}\right]+b^{k-1}(b^2+\frac{1}{b^2}+1)=\frac{1-b^{2k+4}}{b^{k+1}(1-b^2)}.$(11)

We now solve the equation

(12) $\lambda Q_k-(n-k)Q_{k-1}=0.$(12)

Use the formulas $Q_k=\frac{1-b^{2k+2}}{b^k(1-b^2)}$ and $Q_{k-1}=\frac{1-b^{2k}}{b^{k-1}(1-b^2)}$. We have

(13) $\left(b+\frac{1}{b}\right)(1-b^{2k+2})-(n-k)(b-b^{2k+1})=0.$(13)

Multiply both sides by $b$ and simplify. We have

(14) $((n-k)-b^2-1)b^{2k+2}=(n-k)b^2-b^2-1.$(14)

Or,

(15) $b^{2k+2}=\frac{(n-k-1)b^2-1}{(n-k-1)-b^2}.$(15)

Let $m=n-k-1$ and $x=b^2$. So we have

(16) $x^{n-m}=\frac{mx-1}{m-x}.$(16)

We conclude that $\lambda Q_k-(n-k)Q_{k-1}=0$ has a real positive solution $\lambda >2$ if and only if the equation $x^{n-m}=\frac{mx-1}{m-x}$ has a real positive solution in $(1,\mathrm{\infty })$. The existence and uniqueness of the solution to the equation $x^{n-m}=\frac{mx-1}{m-x}$ in the interval $(1,\mathrm{\infty })$ are proved in the next lemma.

Lemma 2. For $m\ge 3$ and $n>m,n\ge 7$, the equation $x^{n-m}=\frac{mx-1}{m-x}$ has a unique solution $x=x_n(m)\in (1,m)$ and $x_n(m)$ increases in $n$.

Proof.

Notice that $\frac{mx-1}{m-x}<0$ when $x>m$. So possible solutions to $x^{n-m}=\frac{mx-1}{m-x}$ are located in $(0,m)$. $x=1$ is always a solution. But the corresponding values $\lambda =2$ and $b=1$ do not satisfy the equation $\lambda Q_k-(n-k)Q_{k-1}=0$ when $n\ge 7$ and $m\ge 3$.

Let $f(x)=x^{n-m}$ and $g(x)=\frac{mx-1}{m-x}$. We have $f^{\prime }(1)=n-m=k+1\ge 3$ when $k\ge 2$. But $g^{\prime }(1)=1+\frac{2}{m-1}\le 2$. Thus, for $x>1$ and $x$ is sufficiently close to $1$, we have $g(x)<f(x)$. On the other hand ${lim}_{x\to m^{-}}g(x)=\mathrm{\infty }$ while $f(m)$ is finite. So, $f(x)=g(x)$ must have at least one solution in $(1,m)$.

To see the solution is unique, we take the logarithm of both $f(x)$ and $g(x)$. Let $F(x)=lnf(x)$ and $G(x)=ln(mx-1)-ln(m-x)$. Let $x_1$ be the smallest solution to the equation $F(x)=G(x)$ in $(1,m)$. We show that $F^{\prime }(x)<G^{\prime }(x)$ for all $x\in (x_1,m)$ and thus $F(x)<G(x)$ for all $x\in (x_1,m)$. Since there is no solution to $F(x)=G(x)$ in the interval $(1,x_1)$ and $F^{\prime }(1)>G^{\prime }(1)$, we have $F(x)>G(x)$ for $x\in (1,x_1)$, which implies $F^{\prime }(x_1)\le G^{\prime }(x_1)$.

To see that $F^{\prime }(x)<G^{\prime }(x)$ for $x\in (x_1,m)$. We start with $F^{\prime }(x_1)\le G^{\prime }(x_1)$, i.e.,

(17) $\frac{n-m}{x_1}\le \frac{1}{x_1-\frac{1}{m}}+\frac{1}{m-x_1},$(17)

or

(18) $n-m\le \frac{x_1}{x_1-\frac{1}{m}}+\frac{x_1}{m-x_1}.$(18)

We have

(19) $\frac{n-m}{x}\le \frac{x_1}{x}\left(\frac{1}{x_1-\frac{1}{m}}+\frac{1}{m-x_1}\right)<\frac{1}{x_1-\frac{1}{m}}+\frac{1}{m-x_1}.$(19)

We now show that the function $\frac{1}{x-\frac{1}{m}}+\frac{1}{m-x}$ is increasing in $x$ by showing its derivative is positive in the interval $(x_1,m)$. Taking the derivative, we have

(20) $\left[\frac{1}{x-\frac{1}{m}}+\frac{1}{m-x}\right]=-\frac{1}{{(x-\frac{1}{m})}^2}+\frac{1}{{(m-x)}^2}.$(20)

To see that it is positive, we need to show $m-x<x-\frac{1}{m}$, i.e., $x>\frac{1}{2}(m+\frac{1}{m}).$

Since $x^{n-m}$ increases in $n$, $x_1$ as a function of $n$ increases in $n$. We now consider the value of $x_1$ when $n-m=3$ or $k=2$. We have $x^3=\frac{mx-1}{m-x}$. Simplify the equation. We have $x^2-mx+1=0$ since we are looking for solutions in $(1,m)$. we have $x_1=\frac{1}{2}(m+\sqrt{m^2-4})$ when $n-m=3$. Thus, for $n-m\ge 3$, $x_1$, the smallest solution to the equation $x^{n-m}=\frac{mx-1}{m-x}$ in $(1,m)$ satisfies the inequality $x_1\ge \frac{1}{2}(m+\sqrt{m^2-4})$. Note that when $m\ge 3$, $\sqrt{m^2-4}>\frac{1}{m}$. Thus, we have for $m\ge 3$, $x_1>\frac{1}{2}(m+\frac{1}{m}).$

It yields that for $x\in (x_1,m)$,

(21) $\frac{n-m}{x}<\frac{1}{x_1-\frac{1}{m}}+\frac{1}{m-x_1}<\frac{1}{x-\frac{1}{m}}+\frac{1}{m-x},$(21)

i.e., $F^{\prime }(x)<G^{\prime }(x).$ So, the solution to $F(x)=G(x)$ is unique in $(1,m)$.

3.2. Monotonicity of $x_n(m)$ in $m$: $m\ge 3$

The characterization of the leading eigenvalue of the adjacency matrix $A_n(k)$ provides a direct way to prove its monotonicity in $m$. Let $x_n(m)$ denote the unique solution to the equation $x^{n-m}=\frac{mx-1}{m-x}$.

Proposition 2. When $n-m\ge 3$ and $m\ge 3$, $x_n(m)<x_n(m+1)<m$.

Proof. We treat $m$ as a continuous variable and denote by $x^{\prime }$ the derivative $\frac{d{x}_n(m)}{dm}$. Multiply $x^m$ to both sides of the equation. We have

(22) $x^n(m-x)=x^m(mx-1).$(22)

With $n$ fixed, taking the derivative with respect to $m$, we have

(23) $n{x}^{n-1}{x}^{\prime }(m-x)+x^n(1-x^{\prime })=(x+m{x}^{\prime })x^m+(mx-1)(m{x}^{m-1}{x}^{\prime }+x^{m}lnx).$(23)

Thus,

(24) $x^{\prime }=\frac{x^{m+1}-x^n+(mx-1)x^{m}lnx}{n{x}^{n-1}(m-x)-x^n-m{x}^m-m(mx-1)x^{m-1}}.$(24)

We now show

(25) $x^{m+1}-x^n+(mx-1)x^{m}lnx<0$(25)

and

(26) $n{x}^{n-1}(m-x)-x^n-m{x}^m-m(mx-1)x^{m-1}<0$(26)

under the conditions $n-m\ge 3$ and $m\ge 3$.

Divide the expression $x^{m+1}-x^n+(mx-1)x^{m}lnx$ by $x^m$. We have

(27) $x+(mx-1)lnx-x^{n-m}=x(-x^{n-m-1}+1+mlnx)-lnx.$(27)

When $n-m-1\ge 2$,

(28) $-x^{n-m-1}+1+mlnx\le -x^2+1+mlnx.$(28)

Since $x\ge \frac{1}{2}(m+\sqrt{m^2-4})$ and $x<m$, we have

(29) $-x^2+1+mlnx<-\frac{1}{4}(m+\sqrt{m^2-4}{)}^2+1+mlnm$(29)

(30) $=-\frac{1}{2}(m^2+m\sqrt{m^2-4})+2+mlnm.$(30)

The function in the last equation decreases in $m$ when $m\ge 3$ and has a negative value at $m=3$. So,

(31) $x+(mx-1)lnx-x^{n-m}<0.$(31)

To see $n{x}^{n-1}(m-x)-x^n-m{x}^m-m(mx-1)x^{m-1}<0$, we again divide the expression by $x^m$: we have $(n(m-x)-x)x^{n-m-1}-m-\frac{m}{x}(mx-1)$.

Since $x^{n-m}=\frac{mx-1}{m-x}$, we replace $m-x$ by the $(mx-1)x^{m-n}$ in the last expression. We now have

(32) $(n(m-x)-x)x^{n-m-1}-m-\frac{m}{x}(mx-1)=\frac{n(mx-1)}{x}-x^{n-m}-m-\frac{m}{x}(mx-1)=\frac{n-m}{x}(mx-1)-x^{n-m}-m.$(32)

Let $n-m=t$ and $h(t,m,x)=x^t+m-\frac{t}{x}(mx-1)$. We show that $\frac{\mathrm{\partial }h}{\mathrm{\partial }t}>0$. Indeed,

(33) $\frac{\mathrm{\partial }h}{\mathrm{\partial }t}=x^{t}lnx-\frac{mx-1}{x}=x^{t}lnx-m+\frac{1}{x}>0$(33)

when $t\ge 3$ and $x\ge \frac{1}{2}(m+\sqrt{m^2-4})$. Thus, for $t\ge 3$ and $x\ge \frac{1}{2}(m+\sqrt{m^2-4})$,

(34) $h(t,m,x)\ge h(3,m,x)=x^3+m-\frac{3}{x}(mx-1)=x^3-2m+\frac{3}{x}>0.$(34)

This means

(35) $\frac{n-m}{x}(mx-1)-x^{n-m}-m<0.$(35)

We thus conclude that $\frac{d}{dm}{x}_n(m)>0$ when $n-m\ge 3$ and $m\ge 3$.

The function $x_n(m)$ is also monotonic in $m$ when $m\le 3$. We leave the proofs to interested readers in these special cases.

When $m\ge 3$ and $n-m\ge 3$, using the equation $x^{n-m}=\frac{mx-1}{m-x}$ and the monotonicity of $x_n(m)$ in $n$, we can conclude that $x_{m+3}(m)\ge \frac{m}{2}$ since $(\frac{m}{2}{)}^3>\frac{m(\frac{m}{2})-1}{m-\frac{m}{2}}$ (see also the proof of Lemma 2 for a better estimate). For each fixed $m\ge 3$, $x_n(m)$ now can be estimated when $n-m\ge 3$: $m-x=(mx-1)x^{m-n}=(m-\frac{1}{x})x^{m-n+1}<m(\frac{m}{2}{)}^{-n+m+1}$. We see that $x_n(m)$ converges to $m$ exponentially fast. Thus, for each fixed $m$, the leading eigenvalue ${\lambda }_n$ converges to $\sqrt{m}+\frac{1}{\sqrt{m}}$. Corollary 1 follows immediately from this direct estimation of $m-x_n(m)$:

Proposition 3 For $m\ge 3$ and $n-m\ge 3$,

$0<m-x_n(m)<m(\frac{m}{2}{)}^{-n+m+1}.$

Acknowledgements

The authors thank Kenneth Berenhaut for discussions and comments and anonymous reviewers for their comments and suggestions.

Additional information

Funding

The authors received no direct funding for this research.

Notes on contributors

William D. Fries

Mr. William D. Fries is currently a Ph.D. student in Graduate Studies in Applied Mathematics at University of Arizona. He graduated in 2016 with a B.A. in Mathematics and Religious Studies from Washington and Lee University and in 2018 with a M.A. in Mathematics from Wake Forest University. This work was part of his master's degree thesis.

Miaohua Jiang

Dr. Miaohua Jiang is a professor in the Department of Mathematics and Statistics at Wake Forest University in North Carolina. U.S.A. He received a B.S. and an M.S. in Mathematics from Wuhan University and East China Normal University in China, respectively, and a Ph.D. in Mathematics from the Pennsylvania State University. Prior to starting his current position, Dr. Jiang held post-doctoral positions at the Center for Dynamical Systems and Nonlinear Studies at Georgia Institute of Technology and the Institute for Mathematics and its Applications at University of Minnesota. Dr. Jiangs research interests include smooth dynamical systems and ergodic theory and their applications in economics and biology.