# Spectrum of a class of matrices and its applications111L. You’s research is
supported by the Zhujiang Technology New Star Foundation of Guangzhou (Grant
No. 2011J2200090) and Program on International Cooperation and Innovation,
Department of Education, Guangdong Province (Grant No.2012gjhz0007).

Lihua You 222Corresponding author<EMAIL_ADDRESS>Man Yang 333Email
address<EMAIL_ADDRESS> Jinxi Li444Email address<EMAIL_ADDRESS>Liyong Ren555Email address<EMAIL_ADDRESS>
(School of Mathematical Sciences, South China Normal University,
Guangzhou, 510631, P.R. China
)

Abstract  In this paper, we give the spectrum of a matrix by using the
quotient matrix, then we apply this result to various matrices associated to a
graph and a digraph, including adjacency matrix, (signless) Laplacian matrix,
distance matrix, distance (signless) Laplacian matrix, to obtain some known
and new results. Moreover, we propose some problems for further research.

AMS Classification: 05C50, 05C35, 05C20, 15A18

Keywords: Matrix; Quotient matrix; Graph; Digraph; Spectrum; Spectral radius

##  1 Introduction

We begin by recalling some definitions. Let $M$ be an $n\times n$ matrix,
$\lambda_{1},\lambda_{2},\ldots,\lambda_{n}$ be the eigenvalues of $M$. It is
obvious that the eigenvalues may be complex numbers since $M$ is not symmetric
in general. We usually assume that
$|\lambda_{1}|\geq|\lambda_{2}|\geq\ldots\geq|\lambda_{n}|$. The spectral
radius of $M$ is defined as $\rho(M)=|\lambda_{1}|$, i.e., it is the largest
modulus of the eigenvalues of $M$. If $M$ is a nonnegative matrix, it follows
from the Perron-Frobenius theorem that the spectral radius $\rho(M)$ is a
eigenvalue of $M$. If $M$ is a nonnegative irreducible matrix, it follows from
the Perron-Frobenius theorem that $\rho(M)=\lambda_{1}$ is simple.

Let $G$ be a connected graph with vertex set $V(G)$ and edge set $E(G)$. Let
$A(G)=(a_{ij})$ denote the adjacency matrix of $G$, where $a_{ij}$ is equal to
the number of edges $v_{i}v_{j}$. The spectral radius of $A(G)$, denoted by
$\rho(G)$, is called the spectral radius of $G$. Let
$diag(G)=diag(d_{1},d_{2},\ldots,d_{n})$ be the diagonal matrix with degree of
the vertices of $G$ and $Q(G)=diag(G)+A(G)$ be the signless Laplacian matrix
of $G$, $L(G)=diag(G)-A(G)$ be the Laplacian matrix of $G$. The spectral
radius of $Q(G)$, denoted by $q(G)$, is called the signless Laplacian spectral
radius of $G$. The spectral radius of $L(G)$, denoted by $\mu(G)$, is called
the Laplacian spectral radius of $G$.

For $u,v\in V(G)$, the distance between $u$ and $v$, denoted by $d_{G}(u,v)$
or $d_{uv}$, is the length of the shortest path connecting them in $G$. For
$u\in V(G)$, the transmission of vertex $u$ in $G$ is the sum of distances
between $u$ and all other vertices of $G$, denoted by $Tr_{G}(u)$.

Let $G$ be a connected graph with vertex set
$V(G)=\\{v_{1},v_{2},\ldots,v_{n}\\}$. The distance matrix of $G$ is the
$n\times n$ matrix $\mathcal{D}(G)=(d_{ij})$ where $d_{ij}=d_{v_{i}v_{j}}$.
The distance spectral radius of $G$, denoted by $\rho^{\mathcal{D}}(G)$, is
the spectral radius of $\mathcal{D}(G)$, which is the largest eigenvalue of
$\mathcal{D}(G)$.

In fact, for $1\leq i\leq n$, the transmission of vertex $v_{i}$,
$Tr_{G}(v_{i})$ is just the $i$-th row sum of $\mathcal{D}(G)$. Let
$Tr(G)=diag(Tr_{G}(v_{1}),Tr_{G}(v_{2}),\ldots,Tr_{G}(v_{n}))$ be the diagonal
matrix of vertex transmission of $G$. M. Aouchiche and P. Hansen [1]
introduced the Laplacian and the signless Laplacian for the distance matrix of
a connected graph. The matrix $\mathcal{L}(G)=Tr(G)-\mathcal{D}(G)$ is called
the distance Laplacian of $G$, while the matrix
$\mathcal{Q}(G)=Tr(G)+\mathcal{D}(G)$ is called the distance signless
Laplacian matrix of $G$. It is obvious that $\mathcal{Q}(G)$ is irreducible,
nonnegative, symmetric and positive semidefinite. The distance signless
Laplacian spectral radius of $G$, denoted by $q^{\mathcal{D}}(G)$, is the
spectral radius of $\mathcal{Q}(G)$, which is the largest eigenvalue of
$\mathcal{Q}(G)$. The spectral radius of $\mathcal{L}(G)$, denoted by
$\mu^{\mathcal{D}}(G)$, is called the distance Laplacian spectral radius of
$G$.

Since $G$ is a connected graph, then $A(G)$, $Q(G)$, $\mathcal{D}(G)$ and
$\mathcal{Q}(G)$ are nonnegative irreducible matrices, it follows from the
Perron Frobenius Theorem that $\rho(G)$, $q(G)$, $\rho^{\mathcal{D}}(G)$ and
$q^{\mathcal{D}}(G)$ are real numbers and there is a positive unit eigenvector
corresponding to $\rho(G)$, $q(G)$, $\rho^{\mathcal{D}}(G)$ and
$q^{\mathcal{D}}(G)$, respectively.

Let $\overrightarrow{G}=(V(\overrightarrow{G}),E(\overrightarrow{G}))$ be a
digraph, where $V(\overrightarrow{G})=\\{v_{1},v_{2},\ldots,v_{n}\\}$ and
$E(\overrightarrow{G})$ are the vertex set and arc set of
$\overrightarrow{G}$, respectively. A digraph $\overrightarrow{G}$ is simple
if it has no loops and multiple arcs. A digraph $\overrightarrow{G}$ is
strongly connected if for every pair of vertices $v_{i},v_{j}\in
V(\overrightarrow{G})$, there are directed paths from $v_{i}$ to $v_{j}$ and
from $v_{j}$ to $v_{i}$. In this paper, we consider finite, simple strongly
connected digraphs.

Let $\overrightarrow{G}$ be a digraph. If two vertices are connected by an
arc, then they are called adjacent. For $e=(v_{i},v_{j})\in
E(\overrightarrow{G})$, $v_{i}$ is the tail (the initial vertex) of $e$,
$v_{j}$ is the head (the terminal vertex) of $e$.

Let $N^{-}_{\overrightarrow{G}}(v_{i})=\\{v_{j}\in
V(\overrightarrow{G})|(v_{j},v_{i})\in E(\overrightarrow{G})\\}$ and
$N^{+}_{\overrightarrow{G}}(v_{i})=\\{v_{j}\in V(\overrightarrow{G})|$
$(v_{i},v_{j})\in E(\overrightarrow{G})\\}$ denote the in-neighbors and out-
neighbors of $v_{i}$, respectively.

For a digraph $\overrightarrow{G}$, let $A(\overrightarrow{G})=(a_{ij})$
denote the adjacency matrix of $\overrightarrow{G}$, where $a_{ij}$ is equal
to the number of arcs $(v_{i},v_{j})$. The spectral radius of
$A(\overrightarrow{G})$, denoted by $\rho(\overrightarrow{G})$, is called the
spectral radius of $\overrightarrow{G}$.

Let $diag(\overrightarrow{G})=diag(d^{+}_{1},d^{+}_{2},\ldots,d^{+}_{n})$ be
the diagonal matrix with outdegree of the vertices of $\overrightarrow{G}$ and
$Q(\overrightarrow{G})=diag(\overrightarrow{G})+A(\overrightarrow{G})$ be the
signless Laplacian matrix of $\overrightarrow{G}$,
$L(\overrightarrow{G})=diag(\overrightarrow{G})-A(\overrightarrow{G})$ be the
Laplacian matrix of $\overrightarrow{G}$. The spectral radius of
$Q(\overrightarrow{G})$, $\rho(Q(\overrightarrow{G}))$, denoted by
$q(\overrightarrow{G})$, is called the signless Laplacian spectral radius of
$\overrightarrow{G}$.

For $u,v\in V(G)$, the distance from $u$ to $v$, denoted by
$d_{\overrightarrow{G}}(u,v)$ or $d_{uv}$, is the length of the shortest
directed path from $u$ to $v$ in ${\overrightarrow{G}}$. For $u\in
V({\overrightarrow{G}})$, the transmission of vertex $u$ in
${\overrightarrow{G}}$ is the sum of distances from $u$ to all other vertices
of ${\overrightarrow{G}}$, denoted by $Tr_{{\overrightarrow{G}}}(u)$.

Let ${\overrightarrow{G}}$ be a connected digraph with vertex set
$V({\overrightarrow{G}})=\\{v_{1},v_{2},\ldots,v_{n}\\}$. The distance matrix
of ${\overrightarrow{G}}$ is the $n\times n$ matrix
$\mathcal{D}({\overrightarrow{G}})=(d_{ij})$ where
$d_{ij}=d_{\overrightarrow{G}}(v_{i},v_{j})$. The distance spectral radius of
$\overrightarrow{G}$, denoted by $\rho^{\mathcal{D}}(\overrightarrow{G})$, is
the spectral radius of $\mathcal{D}(\overrightarrow{G})$.

In fact, for $1\leq i\leq n$, the transmission of vertex $v_{i}$,
$Tr_{\overrightarrow{G}}(v_{i})$ is just the $i$-th row sum of
$\mathcal{D}(\overrightarrow{G})$. Let
$Tr(\overrightarrow{G})=diag(Tr_{\overrightarrow{G}}(v_{1}),Tr_{\overrightarrow{G}}(v_{2}),\ldots,Tr_{\overrightarrow{G}}(v_{n}))$
be the diagonal matrix of vertex transmission of $\overrightarrow{G}$. The
distance signless Laplacian matrix of ${\overrightarrow{G}}$ is the $n\times
n$ matrix defined similar to the undirected graph by Aouchiche and Hansen as

$\mathcal{Q}({\overrightarrow{G}})=Tr({\overrightarrow{G}})+\mathcal{D}({\overrightarrow{G}}).$

Let
$\mathcal{L}(\overrightarrow{G})=Tr({\overrightarrow{G}})-\mathcal{D}({\overrightarrow{G}})$
be the distance Laplacian matrix of $\overrightarrow{G}$. The distance
signless Laplacian spectral radius of $\overrightarrow{G}$,
$\rho(\mathcal{Q}(\overrightarrow{G}))$, denoted by
$q^{\mathcal{D}}(\overrightarrow{G})$, is the spectral radius of
$\mathcal{Q}(\overrightarrow{G})$.

Since $\overrightarrow{G}$ is a simple strongly connected digraph, then
$A(\overrightarrow{G})$, $Q(\overrightarrow{G})$,
$\mathcal{D}({\overrightarrow{G}})$ and $\mathcal{Q}({\overrightarrow{G}})$
are nonnegative irreducible matrices. It follows from the Perron Frobenius
Theorem that $\rho(\overrightarrow{G})$,
$\rho(Q(\overrightarrow{G}))=q(\overrightarrow{G})$,
$\rho^{\mathcal{D}}(\overrightarrow{G})$ and
$\rho(\mathcal{Q}(\overrightarrow{G}))=q^{\mathcal{D}}(\overrightarrow{G})$
are positive real numbers and there is a positive unit eigenvector
corresponding to $\rho(\overrightarrow{G})$, $q(\overrightarrow{G})$,
$\rho^{\mathcal{D}}(\overrightarrow{G})$ and
$q^{\mathcal{D}}(\overrightarrow{G})$, respectively.

For a connected graph $G=(V(G),E(G))$, the vertex connectivity of a graph
denoted by $\kappa(G)$, is the minimum number of vertices whose deletion
yields the resulting graph disconnected. Clearly, let $G$ be a connected graph
on $n$ vertices, then $1\leq\kappa(G)\leq n-1$. Similarly, for a strongly
connected digraph
$\overrightarrow{G}=(V(\overrightarrow{G}),E(\overrightarrow{G}))$, the vertex
connectivity of a digraph denoted by $\kappa(\overrightarrow{G})$, is the
minimum number of vertices whose deletion yields the resulting digraph non-
strongly connected. Clearly, let $\overrightarrow{G}$ be a strongly connected
digraph with $n$ vertices, then $1\leq\kappa(\overrightarrow{G})\leq n-1$.

There are many literatures about graphs’ and digraphs’ connectivity. For early
work, see [27], Ye-Fan-Liang characterize the graphs with the minimal least
eigevalue among all graphs with given vertex connectivity or edge
connectivity. In 2010, Ye-Fan-Wang [28] characterize the graphs with maximum
signless Laplacian or adjacency spectral radius among all graphs with fixed
order and given vertex or edge connectivity. Liu [24] characterized the
minimal distance spectral radius of simple connected graphs with given vertex
connectivity, or matching number, or chromatic number, respectively. Brualdi
[4] wrote a stimulating survey on this topic.

In 2012, Lin-Shu-Wu-Yu [20] establish some upper or lower bounds for digraphs
with some given graph parameters, such as clique number, girth, and vertex
connectivity, and characterize the corresponding extremal graphs, give the
exact value of the spectral radii of those digraphs. Besides, Lin-Yang-Zhang-
Shu [22] characterize the extremal digraphs (graphs) with minimum distance
spectral radius among among all digraphs (graphs) with given vertex (edge)
connectivity.

In 2013, Lin-Drury [18] characterize the extremal digraphs which attain the
maximum Perron root of digraphs with given arc connectivity and number of
vertices. Lin-Shu [21] determine the extremal digraph with the minimal
distance spectral radius with given arc connectivity. Xing-Zhou [26] determine
the graphs with minimal distance signless Laplacian spectral radius among the
connected graphs with fixed number of vertices and connectivity. Oscar Rojo
and Eber Lenes [25] obtained a sharp upper bound on the incidence energy of
graphs in terms of connectivity. Furthermore, some upper or lower bounds were
obtained by the outdegrees and the average 2-outdegrees [6, 11].

In 2014, Hong-You [13] determine the digraphs with maximal signless Laplacian
spectral radius among the strongly connected digraphs with given vertex
connectivity. On the other hand, some extremal digraphs which attain the
maximum or minimum spectral radius, the signless Laplacian spectral radius,
the distance spectral radius, or the distance signless Laplacian spectral
radius of digraphs with given parameters, such as given vertex connectivity,
given arc connectivity, given dichromatic number, given clique number, given
girth and so on, were characterized, see e.g. [18, 21, 20, 22, 26].

In this paper, we give the spectrum of a matrix using the quotient matrix, and
also apply these results to various matrices associated with graphs and
digraphs as mentioned above. Some know results are improved.

##  2 Some preliminaries

######  Definition 2.1.

([3, 14]) Let $A=(a_{ij}),B=(b_{ij})$ be $n\times n$ matrices. If $a_{ij}\leq
b_{ij}$ for all $i$ and $j$, then $A\leq B$. If $A\leq B$ and $A\neq B$, then
$A<B$. If $a_{ij}<b_{ij}$ for all $i$ and $j$, then $A\ll B$.

######  Lemma 2.2.

([3, 14]) Let $A,B$ be $n\times n$ matrices with the spectral radius $\rho(A)$
and $\rho(B)$. If $0\leq A\leq B$, then $\rho(A)\leq\rho(B)$. Furthermore, if
$B$ is irreducible and $0\leq A<B$, then $\rho(A)<\rho(B)$.

By Lemma 2.2, we have the following results in terms of digraphs.

######  Corollary 2.3.

Let $\overrightarrow{G}$ be a digraph and $\overrightarrow{H}$ be a spaning
subdigraph of $\overrightarrow{G}$. Then

(i) $\rho(\overrightarrow{H})\leq\rho(\overrightarrow{G})$,
$q(\overrightarrow{H})\leq q(\overrightarrow{G})$.

(ii)  If $\overrightarrow{G}$ is strongly connected, and $\overrightarrow{H}$
is a proper subdigraph of $\overrightarrow{G}$, then
$\rho(\overrightarrow{H})<\rho(\overrightarrow{G})$,
$q(\overrightarrow{H})<q(\overrightarrow{G})$.

(iii)  If $\overrightarrow{G}$ and $\overrightarrow{H}$ are strongly
connected, then
$\rho^{\mathcal{D}}(\overrightarrow{H})\geq\rho^{\mathcal{D}}(\overrightarrow{G})$,
$q^{\mathcal{D}}(\overrightarrow{H})\geq q^{\mathcal{D}}(\overrightarrow{G})$.

(iv)  If $\overrightarrow{H}$ is a proper subdigraph of $\overrightarrow{G}$,
then
$\rho^{\mathcal{D}}(\overrightarrow{H})>\rho^{\mathcal{D}}(\overrightarrow{G})$,
$q^{\mathcal{D}}(\overrightarrow{H})>q^{\mathcal{D}}(\overrightarrow{G})$.

The theorem for undirected graph is also established.

######  Lemma 2.4.

([3]) If $A$ is an $n\times n$ nonnegative matrix with the spectral radius
$\rho(A)$ and row sums $r_{1},r_{2},\ldots,r_{n}$, then $\min\limits_{1\leq
i\leq n}r_{i}\leq\rho(A)\leq\max\limits_{1\leq i\leq n}r_{i}$. Moreover, if
$A$ is irreducible, then one of the equalities holds if and only if the row
sums of $A$ are all equal.

By Lemma 2.4, we have
$\rho(\overset{\longleftrightarrow}{K_{n}})=\rho^{\mathcal{D}}(\overset{\longleftrightarrow}{K_{n}})=n-1$,
$q(\overset{\longleftrightarrow}{K_{n}})=q^{\mathcal{D}}(\overset{\longleftrightarrow}{K_{n}})=2(n-1)$;
$\rho(\overrightarrow{C_{n}})=1$, $q(\overrightarrow{C_{n}})=2$,
$\rho^{\mathcal{D}}(\overrightarrow{C_{n}})=\frac{n(n-1)}{2}$,
$q^{\mathcal{D}}(\overrightarrow{C_{n}})=n(n-1)$. Then by Corollary 2.3, we
have

######  Corollary 2.5.

Let $\overrightarrow{G}$ be a strongly connected digraph with $n$ vertices.
Then

$\rho(\overrightarrow{G})\leq n-1,\quad q(\overrightarrow{G})\leq
2n-2,\quad\rho^{\mathcal{D}}(\overrightarrow{G})\geq n-1,\quad
q^{\mathcal{D}}(\overrightarrow{G})\geq 2n-2,$

with equality holds if and only if
$\overrightarrow{G}\cong\overset{\longleftrightarrow}{K_{n}}$.

######  Corollary 2.6.

Let $\overrightarrow{G}$ be a strongly connected digraph with $n$ vertices.
Then

$\rho(\overrightarrow{G})\geq 1,\quad q(\overrightarrow{G})\geq
2,\quad\rho^{\mathcal{D}}(\overrightarrow{G})\leq\frac{n(n-1)}{2},\quad
q^{\mathcal{D}}(\overrightarrow{G})\leq n(n-1),$

with equality holds if and only if
$\overrightarrow{G}\cong\overrightarrow{C_{n}}.$

###### Proof.

In [21], Theorem 3.2 show that
$\rho^{\mathcal{D}}(\overrightarrow{G})\leq\frac{n(n-1)}{2},$ and the equality
holds if and only if $\overrightarrow{G}\cong\overrightarrow{C_{n}}.$ Now we
only show $q^{\mathcal{D}}(\overrightarrow{G})\leq n(n-1)$ and the equality
holds if and only if $\overrightarrow{G}\cong\overrightarrow{C_{n}}.$

If $\overrightarrow{G}$ has a Hamiltonian dicycle, we have
$q^{\mathcal{D}}(\overrightarrow{G})\leq
q^{\mathcal{D}}(\overrightarrow{C_{n}})$ and the equality holds if and only if
$\overrightarrow{G}\cong\overrightarrow{C_{n}}$ by Corollary 2.3.

If $\overrightarrow{G}$ does not contain a Hamiltonian dicycle. Noting that
$\max\limits_{1\leq i\leq n}r_{i}\leq n(n-1)$. If $\max\limits_{1\leq i\leq
n}r_{i}<n(n-1)$, then
$q^{\mathcal{D}}(\overrightarrow{G})\leq\max\limits_{1\leq i\leq
n}r_{i}<n(n-1)=q^{\mathcal{D}}(\overrightarrow{C_{n}})$ by Lemma 2.4.

If $\max\limits_{1\leq i\leq n}r_{i}=n(n-1)$, then $\overrightarrow{G}$
contains a vertex $v_{1}$ such that $2Tr_{\overrightarrow{G}}(v_{1})=n(n-1),$
then $\overrightarrow{G}$ contains a Hamiltonian dipath $P$ initiating at
$v_{1}$. Suppose that $P=v_{1}\rightarrow v_{2}\rightarrow\ldots\rightarrow
v_{n}$ is the Hamiltonian dipath initiating at $v_{1}$. Then there is no arc
$(v_{i},v_{j})\in E(\overrightarrow{G})$ if $j-i\geq 2$ since
$Tr_{\overrightarrow{G}}(v_{1})=\frac{n(n-1)}{2}$. Since $\overrightarrow{G}$
is strongly connected and does not a Hamiltonian dicycle, there exists a
dipath $P^{\prime}$ from $v_{n}$ to $v_{1}$ and thus there exists some vertex,
namely, $v_{k}(k\neq n)$, is adjacent to $v_{1}$, that is $(v_{k},v_{1})\in
E(\overrightarrow{G})$. Since $v_{k}$ is on the Hamiltonian dipath $P$, we
have $(v_{k},v_{k+1})\in E(\overrightarrow{G}).$ Hence

$r_{k}\leq
2(1+1+2+\ldots+n-2)<2(1+2+\ldots+n-1)=2Tr_{\overrightarrow{G}}(v_{1})=n(n-1),$

it implies that the row sums of $\mathcal{Q}(\overrightarrow{G})$ are not
equal. Then by Lemma 2.4, we have

$q^{\mathcal{D}}(\overrightarrow{G})<q^{\mathcal{D}}(\overrightarrow{C_{n}}).$

Combining the above arguments, we complete the proof. ∎

##  3 The spectrum of a matrix

Let $I_{p}$ be the $p\times p$ identity matrix and $J_{p,q}$ be the $p\times
q$ matrix in which every entry is $1$, or simply $J_{p}$ if $p=q$. Let $M$ be
a matrix of order $n$, $\sigma(M)$ be the spectrum of the matrix $M$,
$P_{M}(\lambda)=det(xI_{n}-M)$ be the characteristic polynomial of matrix $M$.

######  Definition 3.1.

([23]) Let $M$ be a real matrix of order $n$ described in the following block
form

$M=\left(\begin{array}[]{ccc}M_{11}&\cdots&M_{1t}\\\ \vdots&\ddots&\vdots\\\
M_{t1}&\cdots&M_{tt}\\\ \end{array}\right),$ (3.1)

where the diagonal blocks $M_{ii}$ are $n_{i}\times n_{i}$ matrices for any
$i\in\\{1,2,\ldots,t\\}$ and $n=n_{1}+\ldots+n_{t}$. For any
$i,j\in\\{1,2,\ldots,t\\}$, let $b_{ij}$ denote the average row sum of
$M_{ij}$, i.e. $b_{ij}$ is the sum of all entries in $M_{ij}$ divided by the
number of rows. Then $B(M)=(b_{ij})$ (simply by $B$) is called the quotient
matrix of $M$. If in addition for each pair $i,j$, $M_{ij}$ has constant row
sum, then $B(M)$ is called the equitable quotient matrix of $M$.

######  Lemma 3.2.

Let $M=(m_{ij})_{n\times n}$ be defined as (3.1), and for any
$i,j\in\\{1,2\ldots,t\\}$, the row sum of each block $M_{ij}$ be constant. Let
$B=B(M)=(b_{ij})$ be the equitable quotient matrix of $M$, and $\lambda$ be an
eigenvalue of $B$. Then $\lambda$ is also an eigenvalue of $M$.

###### Proof.

Let $By=\lambda y$ where $y=(y_{1},y_{2},\ldots,y_{t})^{T}$. Define
$Y=(y_{11},\ldots,y_{1,n_{1}},\ldots,y_{t1},\ldots,y_{t,n_{t}})^{T}$ by the
relation $y_{i1}=y_{i2}=\ldots=y_{i,n_{i}}=y_{i}$ for each
$i\in\\{1,2,\ldots,t\\}$. For any $i\in\\{1,2,\ldots,t\\}$ and
$k\in\\{1,2,\ldots,n_{i}\\}$, let $M_{i}(k)$ be the $k$-th row of the $i$-th
row blocks $(M_{i1},\ldots,M_{it})$, that is, $M_{i}(k)$ is the $l$-th row of
$M$ where $l=n_{1}+\ldots+n_{i-1}+k$, then by
$M_{i}(k)Y=(MY)_{l}=\sum\limits_{j=1}^{n_{1}}m_{lj}y_{1}+\sum\limits_{j=n_{1}+1}^{n_{1}+n_{2}}m_{lj}y_{2}+\ldots+\sum\limits_{j=n_{1}+\ldots+n_{t-1}+1}^{n_{1}+\ldots+n_{t}}m_{lj}y_{t}$
and the definition of $b_{ij}$ for each $i,j\in\\{1,2,\ldots t\\}$, we have

$\lambda Y_{l}=\lambda y_{ik}=\lambda
y_{i}=(By)_{i}=\sum\limits_{j=1}^{t}b_{ij}y_{j}=M_{i}(k)Y=(MY)_{l},$

thus we have $MY=\lambda Y,$ and we complete the proof. ∎

######  Example 3.1.

Let $G=(V,E)$ be the Petersen graph as Figure 1. Let $\\{V_{1},V_{2}\\}$ be a
partition of $V=\\{1,2,\ldots,10\\}$, where $V_{1}=\\{1,2,3,4,5\\}$ and
$V_{2}=\\{6,7,8,9,10\\}$. Then the equitable quotient matrices
$B(A),B(L),B(Q),B(\mathcal{D}),B(\mathcal{L}),B(\mathcal{Q})$ corresponding to
the adjacency matrix $A(G)$, the Laplacian matrix $L(G)$, the signless
Laplacian matrix $Q(G)$, the distance matrix $\mathcal{D}(G)$, the distance
Laplacian matrix $\mathcal{L}(G)$, the distance signless Laplacian matrix
$\mathcal{Q}(G)$, respectively, are as follows:

12345678910Figure $1$. The Petersen graph

$B(A)=\left(\begin{array}[]{lcr}2&1\\\ 1&2\\\ \end{array}\right),\qquad
B(L)=\left(\begin{array}[]{lcr}1&-1\\\ -1&1\\\ \end{array}\right),\qquad
B(Q)=\left(\begin{array}[]{lcr}5&1\\\ 1&5\\\ \end{array}\right),$

$B(\mathcal{D})=\left(\begin{array}[]{lcr}6&9\\\ 9&6\\\
\end{array}\right),\qquad B(\mathcal{L})=\left(\begin{array}[]{lcr}9&-9\\\
-9&9\\\ \end{array}\right),\qquad
B(\mathcal{Q})=\left(\begin{array}[]{lcr}21&9\\\ 9&21\\\ \end{array}\right).$

Then

$\rho(B(A))=3,\rho(B(L))=2,\rho(B(Q))=6,\rho(B(\mathcal{D}))=15,\rho(B(\mathcal{L}))=18,\rho(B(\mathcal{Q}))=30,$

but by directly calculating, we have

$\rho(G)=3,\mu(G)=5,q(G)=6,\rho^{\mathcal{D}}(G)=15,\mu^{\mathcal{D}}(G))=18,q^{\mathcal{D}}(G)=30.$

We see that the largest eigenvalue of the equitable quotient matrix $B(M)$ is
the largest eigenvalue of $M$ when $M$ is the adjacency matrix $A(G)$, the
signless Laplacian matrix $Q(G)$, the distance matrix $\mathcal{D}(G)$, the
distance Laplacian matrix $\mathcal{L}(G)$ or the distance signless Laplacian
matrix $\mathcal{Q}(G)$ of a graph $G$, and the result is totally different
when $M$ is the Laplacian matrix $L(G)$ of a graph $G$.

######  Lemma 3.3.

Let $M$ be defined as (3.1), and for any $i,j\in\\{1,2\ldots,t\\}$,
$M_{ii}=l_{i}J_{n_{i}}+p_{i}I_{n_{i}},$ $M_{ij}=s_{ij}J_{n_{i},n_{j}}$ for
$i\not=j$, where $l_{i},p_{i},s_{ij}$ are real numbers, $B=B(M)$ be the
quotient matrix of $M$. Then

$\sigma(M)=\sigma(B)\cup\\{p_{i}^{[n_{i}-1]}\mid i=1,2\ldots,t\\},$ (3.2)

where $\lambda^{[t]}$ means that $\lambda$ is an eigenvalue with multiplicity
$t$.

###### Proof.

It is obvious that for any $i,j\in\\{1,2\ldots,t\\}$, $M_{ij}$ has constant
row sum, so $B$ is the equitable quotient matrix of $M$. Then
$\sigma(B)\subseteq\sigma(M)$ by Lemma 3.2.

On the other hand, we note that
$\sigma(l_{i}J_{n_{i}}+p_{i}I_{n_{i}})=\\{l_{i}n_{i}+p_{i},p_{i}^{[n_{i}-1]}\\}$,
where $l_{i}J_{n_{i}}+p_{i}I_{n_{i}}$ has the all-one vector $J_{n_{i},1}$
such that
$(l_{i}J_{n_{i}}+p_{i}I_{n_{i}})J_{n_{i},1}=(l_{i}n_{i}+p_{i})J_{n_{i},1}$,
and its all other eigenvectors corresponding to eigenvalue $p_{i}$ are
orthogonal to $J_{n_{i},1}$.

Let $x$ be an any eigenvector such that
$(l_{i}J_{n_{i}}+p_{i}I_{n_{i}})x=p_{i}x$, then $x^{T}J_{n_{i},1}=0$, and
$(\mathbf{0}_{1,n_{1}},\ldots,x^{T},\ldots,\mathbf{0}_{1,n_{t}})^{T}$ is an
eigenvector of $M$ corresponding to eigenvalue $p_{i}$. Therefore the $p_{i}$
is an eigenvalue of $M$ with multiplicities at least $n_{i}-1$. And thus we
obtain at least $\sum_{i=1}^{t}(n_{i}-1)=n-t$ eigenvalues of $M$, that is,
$\\{p_{1}^{[n_{1}-1]},\ldots,p_{t}^{[n_{t}-1]}\\}\subseteq\sigma(M)$.

Therefore
$\sigma(B)\cup\\{p_{1}^{[n_{1}-1]},\ldots,p_{t}^{[n_{t}-1]}\\}\subseteq\sigma(M)$
by Lemma 3.2, and
$|\sigma(M)|\leq|\sigma(B)|+|\\{p_{1}^{[n_{1}-1]},\ldots,p_{t}^{[n_{t}-1]}\\}|=n$
by $|\sigma(B)|=t$ and
$|\\{p_{1}^{[n_{1}-1]},\ldots,p_{t}^{[n_{t}-1]}\\}|=n-t$.

If there exists some $p_{i}$ such that $p_{i}\in\sigma(B)$ where
$i\in\\{1,2,\ldots,t\\}$, by the proof of Lemma 3.2, we have $My=p_{i}y$ with
$y=(y_{11},\ldots,y_{1,n_{1}},\ldots,y_{t1},\ldots,y_{t,n_{t}})^{T}$, where
$y_{i1}=y_{i2}=\ldots=y_{i,n_{i}}=y_{i}$ for each $i\in\\{1,2,\ldots,t\\}$.
Then we have
$(\mathbf{0}_{1,n_{1}},\ldots,x^{T},\ldots,\mathbf{0}_{1,n_{t}})y$$=y_{i}(x^{T}J_{n_{i},1})=0$,
it implies that the eigenvectors corresponding to the eigenvalue $p_{i}$ of
$B$ and the eigenvalue $p_{i}$ in
$\\{p_{1}^{[n_{1}-1]},\ldots,p_{t}^{[n_{t}-1]}\\}$ are all orthogonal, then
$|\sigma(M)|=|\sigma(B)|+|\\{p_{1}^{[n_{1}-1]},\ldots,p_{t}^{[n_{t}-1]}\\}|=n$
and thus (3.2) holds. ∎

######  Example 3.2.

Let $G=K_{n_{1},n_{2},\ldots,n_{t}}$ be a complete t-partite graph with $n$
vertices for $t\geq 2$, the adjacency matrix $A=A(G)$, the Laplacian matrix
$L=L(G)$, the signless Laplacian matrix $Q=Q(G)$, the distance matrix
$\mathcal{D}=\mathcal{D}(G),$ the distance Laplacian matrix
$\mathcal{L}=\mathcal{L}(G)$ and the distance signless Laplacian matrix
$\mathcal{Q}(G)$ of $G=K_{n_{1},n_{2},\ldots,n_{t}}$ are as follows:

(1). $A=M$, where $l_{i}=p_{i}=0,s_{ij}=1$ for $i\not=j$ where
$i,j\in\\{1,2,\ldots,t\\}.$

(2). $L=M$, where $l_{i}=0,p_{i}=n-n_{i},s_{ij}=-1$ for $i\not=j$ where
$i,j\in\\{1,2,\ldots,t\\}.$

(3). $Q=M$, where $l_{i}=0,p_{i}=n-n_{i},s_{ij}=1$ for $i\not=j$ where
$i,j\in\\{1,2,\ldots,t\\}.$

(4). $\mathcal{D}=M$, where $l_{i}=2,p_{i}=-2,s_{ij}=1$ for $i\not=j$ where
$i,j\in\\{1,2,\ldots,t\\}.$

(5). $\mathcal{L}=M$, where $l_{i}=-2,p_{i}=n+n_{i},s_{ij}=-1$ for $i\not=j$
where $i,j\in\\{1,2,\ldots,t\\}.$

(6). $\mathcal{Q}=M$, where $l_{i}=2,p_{i}=n+n_{i}-4,s_{ij}=1$ for $i\not=j$
where $i,j\in\\{1,2,\ldots,t\\}.$

It is obvious that for any $i,j\in\\{1,2\ldots,t\\}$, $M_{ij}$ has constant
row sum. Then the corresponding equitable quotient matrices are as follows:

$B(A)=\left(\begin{array}[]{cccc}0&n_{2}&\cdots&n_{t}\\\
n_{1}&0&\cdots&n_{t}\\\ \vdots&\vdots&\ddots&\vdots\\\ n_{1}&n_{2}&\cdots&0\\\
\end{array}\right),\qquad
B(L)=\left(\begin{array}[]{cccc}n-n_{1}&-n_{2}&\cdots&-n_{t}\\\
-n_{1}&n-n_{2}&\cdots&-n_{t}\\\ \vdots&\vdots&\ddots&\vdots\\\
-n_{1}&-n_{2}&\cdots&n-n_{t}\\\ \end{array}\right),$

$B(Q)=\left(\begin{array}[]{cccc}n-n_{1}&n_{2}&\cdots&n_{t}\\\
n_{1}&n-n_{2}&\cdots&n_{t}\\\ \vdots&\vdots&\ddots&\vdots\\\
n_{1}&n_{2}&\cdots&n-n_{t}\\\ \end{array}\right),\quad
B(\mathcal{D})=\left(\begin{array}[]{cccc}2n_{1}-2&n_{2}&\cdots&n_{t}\\\
n_{1}&2n_{2}-2&\cdots&n_{t}\\\ \vdots&\vdots&\ddots&\vdots\\\
n_{1}&n_{2}&\cdots&2n_{t}-2\\\ \end{array}\right),$

$B(\mathcal{L})=\left(\begin{array}[]{cccc}n-n_{1}&-n_{2}&\cdots&-n_{t}\\\
-n_{1}&n-n_{2}&\cdots&-n_{t}\\\ \vdots&\vdots&\ddots&\vdots\\\
-n_{1}&-n_{2}&\cdots&n-n_{t}\\\ \end{array}\right),$

$B(\mathcal{Q})=\left(\begin{array}[]{cccc}n+3n_{1}-4&n_{2}&\cdots&n_{t}\\\
n_{1}&n+3n_{2}-4&\cdots&n_{t}\\\ \vdots&\vdots&\ddots&\vdots\\\
n_{1}&n_{2}&\cdots&n+3n_{t}-4\\\ \end{array}\right).$

By Lemma 3.3, we have

(1).
$P_{A}(\lambda)=\lambda^{n-t}P_{B(A)}(\lambda)=\lambda^{n-t}[\prod\limits_{i=1}^{t}(\lambda+n_{i})-\sum\limits_{i=1}^{t}n_{i}\prod\limits_{j=1,j\neq
i}^{t}(\lambda+n_{j})].$

(2).
$P_{L}(\lambda)=\prod\limits_{i=1}^{t}(\lambda-n+n_{i})^{n_{i}-1}P_{B(L)}(\lambda)=\lambda(\lambda-n)^{t-1}\prod\limits_{i=1}^{t}(\lambda-n+n_{i})^{n_{i}-1}.$

(3).
$P_{Q}(\lambda)=\prod\limits_{i=1}^{t}(\lambda-n+n_{i})^{n_{i}-1}P_{B(Q)}(\lambda)$

$=\prod\limits_{i=1}^{t}(\lambda-n+n_{i})^{n_{i}-1}[\prod\limits_{i=1}^{t}(\lambda-n+2n_{i})-\sum\limits_{i=1}^{t}n_{i}\prod\limits_{j=1,j\neq
i}^{t}(\lambda-n+2n_{j})].$

(4). $P_{\mathcal{D}}(\lambda)=(\lambda+2)^{n-t}P_{B(\mathcal{D})}(\lambda)$

$=(\lambda+2)^{n-t}[\prod\limits_{i=1}^{t}(\lambda-
n_{i}+2)-\sum\limits_{i=1}^{t}n_{i}\prod\limits_{j=1,j\neq i}^{t}(\lambda-
n_{j}+2)].\hskip 11.38092pt{\rm(\cite[cite]{[\@@bibref{}{2013LAA2}{}{}]})}$

(5). $P_{\mathcal{L}}(\lambda)=\prod\limits_{i=1}^{t}(\lambda-n-
n_{i})^{n_{i}-1}P_{B(\mathcal{L})}(\lambda)=\lambda(\lambda-n)^{t-1}\prod\limits_{i=1}^{t}(\lambda-
n-n_{i})^{n_{i}-1}.$

(6). $P_{\mathcal{Q}}(\lambda)=\prod\limits_{i=1}^{t}(\lambda-n-
n_{i}+4)^{n_{i}-1}P_{B(\mathcal{Q})}(\lambda)$

$=\prod\limits_{i=1}^{t}(\lambda-n-
n_{i}+4)^{n_{i}-1}[\prod\limits_{i=1}^{t}(\lambda-n-2n_{i}+4)-\sum\limits_{i=1}^{t}n_{i}\prod\limits_{j=1,j\neq
i}^{t}(\lambda-n-2n_{j}+4)].$

It is obvious that we obtain the spectrums of $L$ and $\mathcal{L}$
immediately. In fact,
$\sigma(L)=\\{0,n^{[t-1]},(n-n_{i})^{[n_{i}-1]},i\in\\{1,2,\ldots,t\\}\\}$,
and
$\sigma(\mathcal{L})=\\{0,n^{[t-1]},(n+n_{i})^{[n_{i}-1]},i\in\\{1,2,\ldots,t\\}\\}.$

A block of $G$ is a maximal connected subgraph of $G$ that has no cut-vertex.
A graph $G$ is a clique tree if each block of $G$ is a clique. We call
$\mathbb{K}_{u,n_{2},\ldots,n_{k+1}}$ is a clique star if we replace each edge
of the star $K_{1,k}$ by a clique $K_{n_{i}}$ such that $V(K_{n_{i}})\cap
V(K_{n_{j}})=u$ for $i\neq j$ and $i,j\in\\{2,\ldots,k+1\\}.$

######  Example 3.3.

Let $G=\mathbb{K}_{u,n_{2},\ldots,n_{k+1}}$, where $n_{1}=|\\{u\\}|=1$,
$n_{i}\geq 2$ for any $i\in\\{2,\ldots,k+1\\}$ and
$n=n_{1}+n_{2}+n_{3}+\ldots+n_{k+1}-k$. Then the adjacency matrix $A=A(G)$,
the Laplacian matrix $L=L(G)$, the signless Laplacian matrix $Q=Q(G)$, the
distance matrix $\mathcal{D}=\mathcal{D}(G),$ the distance Laplacian matrix
$\mathcal{L}=\mathcal{L}(G)$ and the distance signless Laplacian matrix
$\mathcal{Q}(G)$ of $G=\mathbb{K}_{u,n_{2},\ldots,n_{k+1}}$ are as follows.

(1). $A=M$, where $l_{1}=p_{1}=0$ and $l_{i}=1,p_{i}=-1$ for $i\not=1$,
$s_{ij}=1$ for $i=1\mbox{or }j=1$, and $s_{ij}=0$ for any
$i,j\in\\{2,\ldots,k+1\\}$ and $i\neq j$.

(2). $L=M$, where $l_{1}=n-1,p_{1}=0$ and $l_{i}=-1,p_{i}=n_{i}$ for
$i\not=1$, $s_{ij}=-1$ for $i=1\mbox{or }j=1$, and $s_{ij}=0$ for any
$i,j\in\\{2,\ldots,k+1\\}$ and $i\neq j$.

(3). $Q=M$, where $l_{1}=n-1,p_{1}=0$ and $l_{i}=1,p_{i}=n_{i}-2$ for
$i\not=1$, $s_{ij}=1$ for $i=1\mbox{or }j=1$, and $s_{ij}=0$ for any
$i,j\in\\{2,\ldots,k+1\\}$ and $i\neq j$.

(4). $\mathcal{D}=M$, where $l_{1}=0,p_{1}=0$ and $l_{i}=1,p_{i}=-1$ for
$i\not=1$, $s_{ij}=1$ for $i=1\mbox{or }j=1$, and $s_{ij}=2$ for any
$i,j\in\\{2,\ldots,k+1\\}$ and $i\neq j$.

(5) $\mathcal{L}=M$, where $l_{1}=n-1,p_{1}=0$ and $l_{i}=-1,p_{i}=2n-n_{i}$
for $i\not=1$, $s_{ij}=-1$ for $i=1\mbox{or }j=1$, and $s_{ij}=-2$ for any
$i,j\in\\{2,\ldots,k+1\\}$ and $i\neq j$.

(6). $\mathcal{Q}=M$, where $l_{1}=n-1,p_{1}=0$ and $l_{i}=1,p_{i}=2n-n_{i}-2$
for $i\not=1$, $s_{ij}=1$ for $i=1\mbox{or }j=1$, and $s_{ij}=2$ for any
$i,j\in\\{2,\ldots,k+1\\}$ and $i\neq j$.

It is obvious that for any $i,j\in\\{2,\ldots,k+1\\}$, $M_{ij}$ has constant
row sum. Then the corresponding equitable quotient matrices are as follows:

$B(A)=\left(\begin{array}[]{cccc}0&n_{1}-1&\cdots&n_{k}-1\\\
1&n_{1}-2&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\ 1&0&\cdots&n_{k}-2\\\
\end{array}\right),\qquad
B(L)=\left(\begin{array}[]{cccc}n-1&1-n_{1}&\cdots&1-n_{k}\\\ -1&1&\cdots&0\\\
\vdots&\vdots&\vdots\ddots&\vdots\\\ -1&0&\cdots&1\\\ \end{array}\right),$

$B(Q)=\left(\begin{array}[]{cccc}n-1&n_{1}-1&\cdots&n_{k}-1\\\
1&2n_{1}-3&\cdots&0\\\ \vdots&\vdots&\ddots&\vdots\\\ 1&0&\cdots&2n_{k}-3\\\
\end{array}\right),\qquad
B(\mathcal{D})=\left(\begin{array}[]{cccc}0&n_{1}-1&\cdots&n_{k}-1\\\
1&n_{1}-2&\cdots&2n_{k}-1\\\ \vdots&\vdots&\ddots&\vdots\\\
1&2n_{1}-1&\cdots&n_{k}-2\\\ \end{array}\right),$

$B(\mathcal{L})=\left(\begin{array}[]{cccc}n-1&1-n_{1}&\cdots&1-n_{k}\\\
-1&2n-2n_{1}+1&\cdots&-2(n_{k}-1)\\\ \vdots&\vdots&\ddots&\vdots\\\
-1&-2(n_{1}-1)&\cdots&2n-2n_{k}+1\\\ \end{array}\right),$

$B(\mathcal{Q})=\left(\begin{array}[]{cccc}n-1&n_{1}-1&\cdots&n_{k}-1\\\
1&2n-3&\cdots&2n_{k}-1\\\ \vdots&\vdots&\ddots&\vdots\\\
1&2(n_{1}-1)&\cdots&2n-3\\\ \end{array}\right).$

By Lemma 3.3, we have

(1). $P_{A}(\lambda)=(\lambda+1)^{n-k-1}P_{B(A)}(\lambda)$

$=(\lambda+1)^{n-k-1}[\lambda\prod\limits_{i=2}^{k+1}(\lambda-
n_{i}+2)-\sum\limits_{i=2}^{k+1}(n_{i}-1)\prod\limits_{j=2,j\neq
i}^{k+1}(\lambda-n_{j}+2)].$

(2). $P_{L}(\lambda)=(\lambda-
n_{i})^{n_{i}-2}P_{B(L)}(\lambda)=\lambda(\lambda-n)(\lambda-1)^{k-1}(\lambda-
n_{i})^{n_{i}-2}.$

(3). $P_{Q}(\lambda)=\prod\limits_{i=2}^{k+1}(\lambda-
n_{i}+2)^{n_{i}-2}P_{B(Q)}(\lambda)$

$=\prod\limits_{i=2}^{k+1}(\lambda-
n_{i}+2)^{n_{i}-2}[\lambda\prod\limits_{i=2}^{k+1}(\lambda-2n_{i}+3)-\sum\limits_{i=2}^{k+1}(n_{i}-1)\prod\limits_{j=2,j\neq
i}^{k+1}(\lambda-2n_{j}+3)].$

(4). $P_{\mathcal{D}}(\lambda)=(\lambda+1)^{n-k-1}P_{B(\mathcal{D})}(\lambda)$

$=(\lambda+1)^{n-k-1}[\lambda\prod\limits_{i=2}^{k+1}(\lambda+n_{i})-(2\lambda+1)\sum\limits_{i=2}^{k+1}(n_{i}-1)\prod\limits_{j=2,j\neq
i}^{k+1}(\lambda+n_{j})].$

(5).
$P_{\mathcal{L}}(\lambda)=(\lambda-2n+n_{i})^{n_{i}-2}P_{B(\mathcal{L})}(\lambda)=\lambda(\lambda-n)(\lambda-2n+1)^{k-1}(\lambda-2n+n_{i})^{n_{i}-2}.$

(6).
$P_{\mathcal{Q}}(\lambda)=\prod\limits_{i=2}^{k+1}(\lambda-2n+n_{i}+2)^{n_{i}-2}P_{B(\mathcal{Q})}(\lambda)$

$=\prod\limits_{i=2}^{k+1}(\lambda-2n+n_{i}+2)^{n_{i}-2}[(\lambda-n+1)\prod\limits_{i=2}^{k+1}(\lambda-2n+2n_{i}+1)$

$-(2\lambda-2n+3)\sum\limits_{i=2}^{k+1}(n_{i}-1)\prod\limits_{j=2,j\neq
i}^{k+1}(\lambda-2n+2n_{j}+1)].$

It is obvious that we can obtain the spectrum of $L$ and $\mathcal{L}$
immediately. In fact,
$\sigma(L)=\\{0,n,1^{[k-1]},n_{i}^{[n_{i}-2]},i\in\\{2,3,\ldots,k+1\\}\\}$ and
$\sigma(\mathcal{L})=\\{0,n,(2n-1)^{[k-1]},(2n-n_{i})^{[n_{i}-2]},i\in\\{2,3,\ldots,k+1\\}\\}.$

By Lemma 3.2, Example 3.1 and Examples 3.2–3.3, we proposed the following
conjecture for further research.

######  Conjecture 3.4.

Let $M$ be a nonnegative matrix, $B(M)$ be the equitable quotient matrix of
$M$. Then the largest eigenvalue of $B(M)$ is the largest eigenvalue of $M$.

Consider two sequences of real numbers:
$\lambda_{1}\geq\lambda_{2}\geq...\geq\lambda_{n}$, and
$\mu_{1}\geq\mu_{2}\geq...\geq\mu_{m}$ with $m<n$. The second sequence is said
to interlace the first one whenever
$\lambda_{i}\geq\mu_{i}\geq\lambda_{n-m+i}$ for $i=1,2,...,m$. The interlacing
is called tight if there exists an integer $k\in[1,m]$ such that
$\lambda_{i}=\mu_{i}$ hold for $1\leq i\leq k$ and $\lambda_{n-m+i}=\mu_{i}$
hold for $k+1\leq i\leq m$.

######  Lemma 3.5.

([12]) Let $M$ be a symmetric matrix and have the block form as (3.1), $B$ be
the quotient matrix of $M$. Then

(1)  The eigenvalues of $B$ interlace the eigenvalues of $M$.

(2)  If the interlacing is tight, then $B$ is the equitable matrix of $M$.

By Lemmas 3.2-3.5, we have the following result immediately.

######  Theorem 3.1.

Let $M=(m_{ij})_{n\times n}$ be a symmetric matrix and defined as (3.1),
$B=B(M)$ be the quotient matrix of $M$, and
$\mu_{1}\geq\mu_{2}\geq...\geq\mu_{m}$ be all eigenvalues of $B$. Then
$\mu_{1},\mu_{2},...,\mu_{m}$ are eigenvalues of $M$ if and only if $B$ is the
equitable matrix of $M$.

##  4 Spectral radius of strongly connected digraphs with given connectivity

Let $\Omega(n,k)$ be the set of all simple strong connected digraphs on $n$
vertices with vertex connectivity $k$. Let
$\overrightarrow{G}_{1}\bigtriangledown\overrightarrow{G}_{2}$ denote the
digraph $G=(V,E)$ obtained from two disjoint digraphs
$\overrightarrow{G}_{1}$, $\overrightarrow{G}_{2}$ with vertex set
$V=V(\overrightarrow{G}_{1})\cup V(\overrightarrow{G}_{2})$ and arc set
$E=E(\overrightarrow{G}_{1})\cup
E(\overrightarrow{G}_{2})\cup\\{(u,v),(v,u)|u\in
V(\overrightarrow{G}_{1}),v\in V(\overrightarrow{G}_{2})\\}.$

Let $p,k$ be integers with $1\leq k\leq n-2,1\leq p\leq n-k-1,$
$\overrightarrow{K}(n,k,p)$ denote the digraph
$\overrightarrow{K_{k}}\bigtriangledown(\overrightarrow{K_{p}}\cup\overrightarrow{K}_{n-p-k})\cup
E,$ where
$E=\\{(u,v)|u\in\overrightarrow{K_{p}},v\in\overrightarrow{K}_{n-p-k}\\}$.
Clearly, $\overrightarrow{K}(n,k,p)\in\Omega(n,k).$ Then the adjacency matrix,
the signless Laplacian matrix, the distance matrix, the distance signless
Laplacian matrix of $\overrightarrow{K}(n,k,p)$ are as follows, where
$q=n-p-k$.

$A(\overrightarrow{K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}-I_{p}&J_{p,k}&J_{p,q}\\\
J_{k,p}&J_{k}-I_{k}&J_{k,q}\\\ \mathbf{0}_{q,p}&J_{q,k}&J_{q}-I_{q}\\\
\end{array}\right),$
$Q(\overrightarrow{K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}+(n-2)I_{p}&J_{p,k}&J_{p,q}\\\
J_{k,p}&J_{k}+(n-2)I_{k}&J_{k,q}\\\
\mathbf{0}_{q,p}&J_{q,k}&J_{q}+(n-p-2)I_{q}\\\ \end{array}\right),$
$\mathcal{D}(\overrightarrow{K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}-I_{p}&J_{p,k}&J_{p,q}\\\
J_{k,p}&J_{k}-I_{k}&J_{k,q}\\\ 2J_{q,p}&J_{q,k}&J_{q}-I_{q}\\\
\end{array}\right),$
$\mathcal{Q}(\overrightarrow{K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}+(n-2)I_{p}&J_{p,k}&J_{p,q}\\\
J_{k,p}&J_{k}+(n-2)I_{k}&J_{k,q}\\\ 2J_{q,p}&J_{q,k}&J_{q}+(n+p-2)I_{q}\\\
\end{array}\right).$

######  Proposition 4.1.

([2]) Let $\overrightarrow{G}$ be a strongly connected digraphs with vertex
connectivity $k$. Suppose that $S$ is a $k$-vertex cut of $\overrightarrow{G}$
and
$\overrightarrow{G}_{1},\overrightarrow{G}_{2},\ldots,\overrightarrow{G}_{t}$
are the strongly connected components of $\overrightarrow{G}-S$. Then there
exists an ordering of
$\overrightarrow{G}_{1},\overrightarrow{G}_{2},\ldots,\overrightarrow{G}_{t}$
such that for $1\leq i\leq t$ and $v\in V(\overrightarrow{G}_{i})$, every tail
of $v$ is in $\bigcup\limits_{j=1}^{i-1}\overrightarrow{G}_{j}$.

######  Remark 4.2.

By Proposition 4.1, we know that $\overrightarrow{G}_{1}$ is the strongly
connected component of $\overrightarrow{G}-S$ where the inneighbors of
vertices of $V(\overrightarrow{G}_{1})$ in
$\overrightarrow{G}-S-\overrightarrow{G}_{1}$ are zero. Let
$\overrightarrow{G}_{2}=\overrightarrow{G}-S-\overrightarrow{G}_{1}$. We add
arcs to $\overrightarrow{G}$ until both induced subdigraph of
$V(\overrightarrow{G}_{1})\cup S$ and induced subdigraph of
$V(\overrightarrow{G}_{2})\cup S$ attain to complete digraphs, add arc $(u,v)$
for any $u\in V(\overrightarrow{G}_{1})$ and any $v\in
V(\overrightarrow{G_{2}})$, the new digraph denoted by $\overrightarrow{H}$.
Clearly, $\overrightarrow{H}=\overrightarrow{K}(n,k,p)\in\Omega(n,k)$ for some
$p$ such that $1\leq p\leq n-k-1$. Since $\overrightarrow{G}$ is the spanning
subdigraph of $\overrightarrow{H}$, then by Corollary 2.3, we have
$\rho(\overrightarrow{G})\leq\rho(\overrightarrow{K}(n,k,p))$,
$q(\overrightarrow{G})\leq q(\overrightarrow{K}(n,k,p))$,
$\rho^{\mathcal{D}}(\overrightarrow{G})\geq\rho^{\mathcal{D}}(\overrightarrow{K}(n,k,p))$
and $q^{\mathcal{D}}(\overrightarrow{G})\geq
q^{\mathcal{D}}(\overrightarrow{K}(n,k,p))$. Thus the extremal digraphs which
achieve the maximal (signless Laplacian) spectral radius and the minimal
distance (signless Laplacian) spectral radius in $\Omega(n,k)$ must be some
$\overrightarrow{K}(n,k,p)$ for $1\leq p\leq n-k-1$.

######  Theorem 4.1.

Let $n,k$ be given positive integers with $1\leq k\leq n-2$,
$\overrightarrow{G}\in\Omega(n,k).$ Then

(i). ([20])

$\rho(\overrightarrow{G})\leq\frac{n-2+\sqrt{(n-2)^{2}+4k}}{2},$ (4.1)

with equality if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,1)$ or
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,n-k-1).$

(ii). ([13])

$q(\overrightarrow{G})\leq\frac{2n+k-3+\sqrt{(2n-k-3)^{2}+4k}}{2},$ (4.2)

with equality if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,n-k-1).$

(iii). ([22])

$\rho^{\mathcal{D}}(\overrightarrow{G})\geq\frac{n-2+\sqrt{(n+2)^{2}-4k-8}}{2},$
(4.3)

with equality if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,1)$ or
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,n-k-1)$.

(iv).

$q^{\mathcal{D}}(\overrightarrow{G})\geq\frac{3n-3+\sqrt{(n+3)^{2}-8k-16}}{2},$
(4.4)

with equality if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,1).$

###### Proof.

Now we show (i) holds. We apply Lemma 3.3 to $A=A(\overrightarrow{K}(n,k,p))$.
Since $t=3$, $l_{i}=1,p_{i}=-1$ for $1\leq i\leq 3$, $s_{31}=0$ and $s_{ij}=1$
for others $i,j\in\\{1,2,3\\}$ and $i\not=j$, we have
$\sigma(A)=\sigma(B(A))\cup\\{(-1)^{[n-3]}\\}$, where the corresponding
equitable quotient matrix of $A$ is

$B(A)=\left(\begin{array}[]{ccc}p-1&k&q\\\ p&k-1&q\\\ 0&k&q-1\\\
\end{array}\right),$

the eigenvalues of $B(A)$ are
$-1,\frac{n-2\pm\sqrt{4p^{2}-4(n-k)p+n^{2}}}{2}$. Thus
$\rho(A)=\frac{n-2+\sqrt{4p^{2}-4(n-k)p+n^{2}}}{2}$.

It is obvious that
$\frac{n-2+\sqrt{4p^{2}-4(n-k)p+n^{2}}}{2}\leq\frac{n-2+\sqrt{(n-2)^{2}+4k}}{2}$,
and equality holds if and only if $p=1$ or $p=n-k-1$. Thus (4.1) holds and
equality holds if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,1)$ or
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,n-k-1).$

Now we show (ii) holds. Similarly, we apply Lemma 3.3 to
$Q=Q(\overrightarrow{K}(n,k,p))$. Since $t=3$, $l_{i}=1$ for $1\leq i\leq 3$,
$p_{1}=p_{2}=n-2$, $p_{3}=n-p-2,$ $s_{31}=0$ and $s_{ij}=1$ for others
$i,j\in\\{1,2,3\\}$ and $i\not=j$, we have
$\sigma(Q)=\sigma(B(Q))\cup\\{(n-2)^{[p+k-2]},(n-p-2)^{[q-1]}\\},$ where the
corresponding equitable quotient matrix of $Q$ is

$B(Q)=\left(\begin{array}[]{ccc}p+n-2&k&q\\\ p&k+n-2&q\\\ 0&k&q+n-p-2\\\
\end{array}\right),$

the eigenvalues of $B(Q)$ are
$n-2,\frac{(3n-p-4)\pm\sqrt{(n-3p)^{2}+8pk}}{2}$. Thus
$\rho(Q)=\frac{3n-p-4+\sqrt{(n-3p)^{2}+8pk}}{2}$.

By the same proof of Theorem 7.6 in [13], we can show (4.2) holds by proving

$\frac{3n-p-4+\sqrt{(n-3p)^{2}+8pk}}{2}\leq\frac{2n+k-3+\sqrt{(2n-k-3)^{2}+4k}}{2}$

for $1\leq p\leq n-k-1$, and equality holds if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,n-k-1).$

Now we show (iii) holds. We apply Lemma 3.3 to
$\mathcal{D}=\mathcal{D}(\overrightarrow{K}(n,k,p))$. Since $l_{i}=1,p_{i}=-1$
for $1\leq i\leq 3$, $s_{31}=2$ and $s_{ij}=1$ for others $i,j\in\\{1,2,3\\}$
and $i\not=j$, we have
$\sigma(\mathcal{D})=\sigma(B(\mathcal{D}))\cup\\{(-1)^{[n-3]}\\},$ and the
corresponding equitable quotient matrix of $\mathcal{D}$ is

$B(\mathcal{D})=\left(\begin{array}[]{ccc}p-1&k&q\\\ p&k-1&q\\\ 2p&k&q-1\\\
\end{array}\right),$

the eigenvalues of $B(\mathcal{D})$ are
$-1,\frac{(n-2)\pm\sqrt{-4p^{2}+4(n-k)p+n^{2}}}{2}$. Thus
$\rho(\mathcal{D})=\frac{n-2+\sqrt{-4p^{2}+4(n-k)p+n^{2}}}{2}$.

It is obvious that
$\frac{n-2+\sqrt{-4p^{2}+4(n-k)p+n^{2}}}{2}\geq\frac{n-2+\sqrt{(n+2)^{2}-4k-8}}{2}$,
and equality holds if and only if $p=1$ or $p=n-k-1$. Thus (4.3) holds and
equality holds if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,1)$ or
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,n-k-1).$

Now we show (iv) holds. We apply Lemma 3.3 to
$\mathcal{Q}=\mathcal{Q}(\overrightarrow{K}(n,k,p))$. Since
$l_{1}=l_{2}=l_{3}=1,$ $p_{1}=p_{2}=n-2,$ $p_{3}=n+p-2,$ $s_{31}=2$ and
$s_{ij}=1$ for others $i,j\in\\{1,2,3\\}$ and $i\not=j$, we have
$\sigma(\mathcal{Q})=\sigma(B(\mathcal{Q}))\cup\\{(n-2)^{[p+k-2]},(n+p-2)^{[q-1]}\\},$
and the corresponding equitable quotient matrix of $\mathcal{Q}$ is

$B(\mathcal{Q})=\left(\begin{array}[]{ccc}p+n-2&k&q\\\ p&k+n-2&q\\\
2p&k&q+n+p-2\\\ \end{array}\right),$

the eigenvalues of $B(\mathcal{Q})$ are
$n-2,\frac{(3n+p-4)\pm\sqrt{(n+3p)^{2}-16p^{2}-8kp}}{2}$. Thus

$\rho(\mathcal{Q})=\frac{3n+p-4+\sqrt{(n+3p)^{2}-16p^{2}-8kp}}{2}.$

Now we show
$\frac{3n+p-4+\sqrt{(n+3p)^{2}-16p^{2}-8kp}}{2}\geq\frac{3n-3+\sqrt{(n+3)^{2}-8k-16}}{2}$
for $1\leq p\leq n-k-1$, and the equality holds if and only if $p=1$. Let
$f(p)=\frac{3n+p-4+\sqrt{(n+3p)^{2}-16p^{2}-8kp}}{2}$. Then

$\frac{\partial^{2}f(p)}{\partial
p^{2}}=\frac{-4((2n-k)(n-k)+k^{2})}{((n+3p)^{2}-16p^{2}-8kp)^{\frac{3}{2}}}<0.$

Thus, for fixed $n$ and $k$, the minimal value of $f(p)$ must be taken at
either $p=1$ or $p=n-k-1$. Let $\alpha=k^{2}-6k-7+8n$ and
$\beta=n^{2}+6n-7-8k$. Then

$2[f(n-k-1)-f(1)]=n-k-2+\sqrt{\alpha}-\sqrt{\beta}=(n-k-2)(1-\frac{n+k}{\sqrt{\alpha}+\sqrt{\beta}}).$

We can assume that $n>k+2$ since in case $k=n-2$ there is only one value of
$p$ under consideration. Now suppose that $f(n-k-1)-f(1)\leq 0$. We will
produce a contradiction. We have

$\sqrt{\alpha}+\sqrt{\beta}\leq n+k,\sqrt{\alpha}-\sqrt{\beta}\leq-n+k+2.$

Whence $\sqrt{\alpha}\leq k+1$ and $\alpha\leq(k+1)^{2}$ which reduces to
$k\geq n-1$ which is out of range. Thus $f(n-k-1)>f(1)$ and
$q^{\mathcal{D}}(\overrightarrow{G})\geq
f(1)\texttt{}=q^{\mathcal{D}}(\overrightarrow{K}(n,k,1))=\frac{3n-3+\sqrt{(n+3)^{2}-8k-16}}{2}$,
with equality if and only if
$\overrightarrow{G}\cong\overrightarrow{K}(n,k,1).$ ∎

It is natural that whether there exists similar result for the Laplacian
spectral radius or the distance Laplacian spectral radius in $\Omega(n,k)$ or
not? In fact, we can obtain the spectrum of the Laplacian matrix or the
distance Laplacian matrix of $\overrightarrow{K}(n,k,p)$ immediately.

######  Proposition 4.3.

Let $\overrightarrow{K}(n,k,p)$ defined as before. Then

(i). $\sigma(L(\overrightarrow{K}(n,k,p)))=\\{0,n^{[p+k-1]},(n-p)^{[q]}\\}.$

(ii).
$\sigma(\mathcal{L}(\overrightarrow{K}(n,k,p)))=\\{0,n^{[p+k-1]},(n+p)^{[q]}\\}.$

###### Proof.

Firstly, the Laplacian matrix $L(\overrightarrow{K}(n,k,p))$ and the distance
Laplacian matrix $\mathcal{L}(\overrightarrow{K}(n,k,p))$ of
$\overrightarrow{K}(n,k,p)$ are the following matrices, where $q=n-p-k$.

$L=L(\overrightarrow{K}(n,k,p))=\left(\begin{array}[]{ccc}-J_{p}+nI_{p}&-J_{p,k}&-J_{p,q}\\\
-J_{k,p}&-J_{k}+nI_{k}&-J_{k,q}\\\
\mathbf{0}_{q,p}&-J_{q,k}&-J_{q}+(n-p)I_{q}\\\ \end{array}\right),$

$\mathcal{L}=\mathcal{L}(\overrightarrow{K}(n,k,p))=\left(\begin{array}[]{ccc}-J_{p}+nI_{p}&-J_{p,k}&-J_{p,q}\\\
-J_{k,p}&-J_{k}+nI_{k}&-J_{k,q}\\\ -2J_{q,p}&-J_{q,k}&-J_{q}+(n+p)I_{q}\\\
\end{array}\right).$

Then the corresponding equitable quotient matrices are as follows:

$B(L)=\left(\begin{array}[]{ccc}n-p&-k&-q\\\ -p&n-k&-q\\\ 0&-k&k\\\
\end{array}\right),\qquad
B(\mathcal{L})=\left(\begin{array}[]{lcr}n-p&-k&-q\\\ -p&n-k&-q\\\
-2p&-k&n+p-q\\\ \end{array}\right).$

Then by Lemma 3.3 and directly calculating, we obtain (i) and (ii). ∎

##  5 Spectral radius of connected graphs with given connectivity

Let $\mathcal{C}(n,k)$ be the set of all simple connected graphs on $n$
vertices with vertex connectivity $k$. Let ${G_{1}}\bigtriangledown{G_{2}}$
denote the graph $G=(V,E)$ obtained from two disjoint graphs ${G_{1}}$,
${G_{2}}$ by joining each vertex of $G_{1}$ to each vertex of $G_{2}$ with
vertex set $V=V({G}_{1})\cup V({G}_{2})$ and edge set $E=E({G}_{1})\cup
E({G}_{2})\cup\\{uv|u\in V({G}_{1}),v\in V({G}_{2})\\}$.

Let $p,k$ be integers with $1\leq k\leq n-2,1\leq p\leq n-k-1,$ and
${K}(n,k,p)$ be the graph ${K_{k}}\bigtriangledown({K_{p}}\cup{K}_{n-p-k})$.
Clearly, ${K}(n,k,p)\in\mathcal{C}(n,k).$ Then the adjacency matrix, the
signless Laplacian matrix, the distance matrix, the distance signless
Laplacian matrix of ${K}(n,k,p)$ are as follows, where $q=n-p-k$.

$A({K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}-I_{p}&J_{p,k}&\mathbf{0}_{p,q}\\\
J_{k,p}&J_{k}-I_{k}&J_{k,q}\\\ \mathbf{0}_{q,p}&J_{q,k}&J_{q}-I_{q}\\\
\end{array}\right),$
$Q({K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}+(p+k-2)I_{p}&J_{p,k}&\mathbf{0}_{p,q}\\\
J_{k,p}&J_{k}+(n-2)I_{k}&J_{k,q}\\\
\mathbf{0}_{q,p}&J_{q,k}&J_{q}+(n-p-2)I_{q}\\\ \end{array}\right),$
$\mathcal{D}({K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}-I_{p}&J_{p,k}&2J_{p,q}\\\
J_{k,p}&J_{k}-I_{k}&J_{k,q}\\\ 2J_{q,p}&J_{q,k}&J_{q}-I_{q}\\\
\end{array}\right),$
$\mathcal{Q}({K}(n,k,p))=\left(\begin{array}[]{lcr}J_{p}+(n+q-2)I_{p}&J_{p,k}&2J_{p,q}\\\
J_{k,p}&J_{k}+(n-2)I_{k}&J_{k,q}\\\ 2J_{q,p}&J_{q,k}&J_{q}+(n+p-2)I_{q}\\\
\end{array}\right).$

######  Remark 5.1.

Let ${G}$ be a connected graphs with vertex connectivity $k$. Suppose that $S$
is a $k$-vertex cut of ${G}$, and $G_{1}$ is a connected component of $G-S$.
Let ${G_{2}}={G}-S-{G_{1}}$, we add edges to ${G}$ until both induced subgraph
of $V({G_{1}})\cup S$ and induced subgraph of $V({G_{2}})\cup S$ attain to
complete graphs, the new graph denoted by ${H}$. Clearly,
${H}={K}(n,k,p)\in\mathcal{C}(n,k)$ for some $p$ such that $1\leq p\leq
n-k-1$. Since ${G}$ is the spanning subgraph of ${H}$, then by Corollary 2.3,
we have $\rho({G})\leq\rho({K}(n,k,p))$, $q({G})\leq q({K}(n,k,p))$,
$\rho^{\mathcal{D}}({G})\geq\rho^{\mathcal{D}}({K}(n,k,p))$ and
$q^{\mathcal{D}}({G})\geq q^{\mathcal{D}}({K}(n,k,p))$. Thus the extremal
graphs which achieve the maximal (signless Laplacian) spectral radius and the
minimal distance (signless Laplacian) spectral radius in $\mathcal{C}(n,k)$
must be some $K(n,k,p)$ for $1\leq p\leq n-k-1$.

######  Theorem 5.1.

Let $n,k$ be given positive integers with $1\leq k\leq n-2$,
${G}\in\mathcal{C}(n,k).$ Then

(i) ([28]) $\rho({G})\leq\rho(K(n,k,1)),$ and $\rho({{K}(n,k,1)}$ is the
largest root of equation (5.1):

$\lambda^{3}-(n-3)\lambda^{2}-(n+k-2)\lambda+k(n-k-2)=0,$ (5.1)

with equality holds if and only if $G=K(n,k,1).$

(ii) ([28])

$q({G})\leq q(K(n,k,1))=\frac{2n+k-4+\sqrt{(2n-k-4)^{2}+8k}}{2},$ (5.2)

with equality holds if and only if $G=K(n,k,1).$

(iii) ([22]) $\rho^{\mathcal{D}}({G})\geq\rho^{\mathcal{D}}(K(n,k,1)),$ and
$\rho^{\mathcal{D}}({{K}(n,k,1)}$ is the largest root of equation (5.3):

$\lambda^{3}-(n-3)\lambda^{2}-(5n-3k-6)\lambda+kn-k^{2}+2k-4n+4=0,$ (5.3)

with equality holds if and only if $G=K(n,k,1).$

(iv) ([26]) $q^{\mathcal{Q}}({G})\geq q^{\mathcal{Q}}(K(n,k,1)),$ and
$q^{\mathcal{Q}}({{K}(n,k,1)}$ is the largest root of equation (5.4):

$\lambda^{3}-(5n-k-6)\lambda^{2}+(8n^{2}-19kn-24n+8k+16)\lambda-4n^{3}+2(k+10)n^{2}-2(5k+16)n+12k+16=0,$
(5.4)

with equality holds if and only if $G=K(n,k,1).$

###### Proof.

Firstly, we show (i) holds. We apply Lemma 3.3 to $A=A({K}(n,k,p))$. Since
$t=3$, $l_{1}=l_{2}=l_{3}=1,$ $p_{1}=p_{2}=p_{3}=-1,$ $s_{13}=s_{31}=0$ and
$s_{12}=s_{21}=s_{23}=s_{32}=1$, we have
$\sigma(A)=\sigma(B(A))\cup\\{(-1)^{[n-3]}\\},$ where the corresponding
equitable quotient matrix of $A$ is $B(A)=\left(\begin{array}[]{ccc}p-1&k&0\\\
p&k-1&q\\\ 0&k&q-1\\\ \end{array}\right),$ the eigenvalues of $B(A)$ are the
roots of the equation

$\lambda^{3}-(n-3)\lambda^{2}+(pq-2n+3)\lambda+pq-n+pqk+1=0.$ (5.5)

It is obvious that $\rho(A({K}(n,k,p)))$ is the largest root of the equation
(5.5).

Now we show $\rho(A({K}(n,k,1)))=\max\\{\rho(A({K}(n,k,p)))|1\leq p\leq
n-k-1\\}$. We note that $p+q=n-k$ and the adjacency matrix is symmetric,
without loss of generality, we assume that $q\geq p\geq 1$. Let
$f_{p,q}(\lambda)=\lambda^{3}-(n-3)\lambda^{2}+(pq-2n+3)\lambda+pq-n+pqk+1$.
Let $H={K_{k}}\bigtriangledown({K_{p-1}}\cup{K}_{q+1})={K}(n,k,p-1)$.
Obviously, $H\in\mathcal{C}(n,k)$ and $\rho(H)$ is the largest root of
$f_{p-1,q+1}(\lambda)=0$, then

$f_{p,q}(\lambda)-f_{p-1,q+1}(\lambda)$
$=pq\lambda+pq+pqk-(p-1)(q+1)\lambda-(p-1)(q+1)-(p-1)(q+1)k$

$=(q+1-p)(\lambda+k+1)>0$,

and

$f_{p,q}(\rho(H))=f_{p,q}(\rho(H))-f_{p-1,q+1}(\rho(H))>0=f_{p,q}(\rho({K}(n,k,p))).$

It implies $\rho(H)=\rho({K}(n,k,p-1))>\rho({K}(n,k,p))$. Thus
$\rho({G})\leq\rho(K(n,k,1))$, $\rho({{K}(n,k,1)})$ is the largest root of the
equation (5.1), $\rho({G})=\rho(K(n,k,1))$ if and only if $G=K(n,k,1).$

Second, we show (ii) holds. We apply Lemma 3.3 to $Q=Q({K}(n,k,p))$. Since
$t=3$, $l_{1}=l_{2}=l_{3}=1,$ $p_{1}=p+k-2,$ $p_{2}=n-2,$ $p_{3}=n-p-2,$
$s_{13}=s_{31}=0$ and $s_{12}=s_{21}=s_{23}=s_{32}=1$, we have
$\sigma(Q)=\sigma(B(Q))\cup\\{(p+k-2)^{[p-1]},(n-2)^{[k-1]},(n-p-2)^{[q-1]}\\}$
where the corresponding equitable quotient matrix of $Q$ is

$B(Q)=\left(\begin{array}[]{ccc}2p+k-2&k&0\\\ p&k+n-2&q\\\ 0&k&q+n-p-2\\\
\end{array}\right),$

the eigenvalues of $B(Q)$ are
$n-2,n-2+\frac{k}{2}\pm\frac{1}{2}\sqrt{(k-2n)^{2}+16p(k-n+p)}$. Thus
$\rho(Q)=n-2+\frac{k}{2}+\frac{1}{2}\sqrt{(k-2n)^{2}+16p(k-n+p)}.$

Let $f(p)=n-2+\frac{k}{2}+\frac{1}{2}\sqrt{(k-2n)^{2}+16p(k-n+p)}$, then
$f(1)=f(n-k-1)=\max\\{f(p)|1\leq p\leq n-k-1\\}.$ Therefore,
$q({G})\leq\frac{2n+k-4+\sqrt{(2n-k-4)^{2}+8k}}{2},$ and we complete the proof
of (ii) by ${K}(n,k,1)\cong{K}(n,k,n-k-1)$.

Third, we show (iii) holds. We apply Lemma 3.3 to
$\mathcal{D}=\mathcal{D}({K}(n,k,p))$. Since $t=3$, $l_{1}=l_{2}=l_{3}=1,$
$p_{1}=p_{2}=p_{3}=-1,$ $s_{13}=s_{31}=2$ and $s_{12}=s_{21}=s_{23}=s_{32}=1$,
we have $\sigma(\mathcal{D})=\sigma(B(\mathcal{D}))\cup\\{(-1)^{[n-3]}\\}$
where the corresponding equitable quotient matrix of $\mathcal{D}$ is

$B(\mathcal{D})=\left(\begin{array}[]{ccc}p-1&k&2q\\\ p&k-1&q\\\ 2p&k&q-1\\\
\end{array}\right),$

the eigenvalues of $B(\mathcal{D})$ are the roots of the equation:

$\lambda^{3}-(n-3)\lambda^{2}-(3pq+2n-3)\lambda+pqk-3pq-n+1=0.$ (5.6)

It is obvious that $\rho(\mathcal{D}({K}(n,k,p)))$ is the largest root of the
equation (5.6).

Similar to the proof of (i), we can show (iii) holds, we omit it.

Finally, we show (iv) holds. We apply Lemma 3.3 to
$\mathcal{Q}=\mathcal{Q}({K}(n,k,p))$. Since $t=3$, $l_{1}=l_{2}=l_{3}=1,$
$p_{1}=n+q-2,$ $p_{2}=n-2,$ $p_{3}=n+p-2,$ $s_{13}=s_{31}=2$ and
$s_{12}=s_{21}=s_{23}=s_{32}=1$, we have
$\sigma(\mathcal{Q})=\sigma(B(\mathcal{Q}))\cup\\{(n+q-2)^{[p-1]},(n-2)^{[k-1]},(n+p-2)^{[q-1]}\\}$
where the corresponding equitable quotient matrix of $\mathcal{Q}$ is

$B(\mathcal{Q})=\left(\begin{array}[]{lcr}n+p+q-2&k&2q\\\ p&n+k-2&q\\\
2p&k&n+p+q-2\\\ \end{array}\right),$

the eigenvalues of $B(\mathcal{Q})$ are the roots of the equation:
$\lambda^{3}-(5p+5q+4k-6)\lambda^{2}+(8p^{2}+8q^{2}+5k^{2}+12pq+13pk+13qk-20p-20q-16k+12)\lambda-4p^{3}-4q^{3}-2k^{3}-8p^{2}q-8pq^{2}-10p^{2}k-10q^{2}k-8pk^{2}-8qk^{2}-16pqk+16p^{2}+16q^{2}+10k^{2}+24pq+26pk+26qk-20p-20q-16k+8=0.$

Similar to the proof of (i), we can show (iv) holds, we omit it. ∎

It is natural that whether there exists similar result for the Laplacian
spectral radius or the distance Laplacian spectral radius in
$\mathcal{C}(n,k)$ or not? In fact, we can obtain the spectrum of the
Laplacian matrix or the distance Laplacian matrix of $K(n,k,p)$ immediately.

######  Proposition 5.2.

Let $K(n,k,p)$ defined as before. Then

(i). $\sigma(L(K(n,k,p)))=\\{0,k,n^{[k]},(p+k)^{[p-1]},(q+k)^{[q-1]}\\}.$

(ii).
$\sigma(\mathcal{L}(K(n,k,p)))=\\{0,n+p+q,n^{[k]},(n+q)^{p-1},(n+p)^{q-1}\\}.$

###### Proof.

Firstly, the Laplacian matrix $L(K(n,k,p))$ and the distance Laplacian matrix
$\mathcal{L}(K(n,k,p))$ of $K(n,k,p)$ are the following matrices, where
$q=n-p-k$.

$L=L(K(n,k,p))=\left(\begin{array}[]{ccc}-J_{p}+(p+k)I_{p}&-J_{p,k}&\mathbf{0}_{p,q}\\\
-J_{k,p}&-J_{k}+nI_{k}&-J_{k,q}\\\
\mathbf{0}_{q,p}&-J_{q,k}&-J_{q}+(q+k)I_{q}\\\ \end{array}\right),$
$\mathcal{L}=\mathcal{L}(K(n,k,p))=\left(\begin{array}[]{ccc}-J_{p}+(n+q)I_{p}&-J_{p,k}&-2J_{p,q}\\\
-J_{k,p}&-J_{k}+nI_{k}&-J_{k,q}\\\ -2J_{q,p}&-J_{q,k}&-J_{q}+(n+p)I_{q}\\\
\end{array}\right).$

Then the corresponding equitable quotient matrices are as follows:

$B(L)=\left(\begin{array}[]{ccc}k&-k&0\\\ -p&n-k&-q\\\ 0&-k&k\\\
\end{array}\right),\qquad
B(\mathcal{L})=\left(\begin{array}[]{ccc}n+q-p&-k&-2q\\\ -p&n-k&-q\\\
-2p&-k&n+p-q\\\ \end{array}\right).$

Then by Lemma 3.3 and directly calculating, we obtain (i) and (ii). ∎

## References

  * [1] M. Aouchiche, P. Hansen, Two Laplacian for the distance matrix of a graph, Linear Algebra Appl. 439 (2013) 21–33.
  * [2] J.A. Bondy, U.S.R. Murty, Graph Theory with Applications, Macmillan, London, 1976.
  * [3] Abraham Berman, Robert J. Plemmons, Nonnegative Matrices in the Mathematical Sciences, New York: Academic Press, 1979.
  * [4] R. Brualdi, Spectra of digraphs, Linear Algebra Appl. 432 (2010) 2181–2213.
  * [5] Andries E. Brouwer, Willem H. Haemers, Spectra of graphs - Monograph -, Springer, 2011.
  * [6] S. Burcu Bozkurt and Durmus Bozkurt, On the signless Laplacian spectral radius of digraphs, Ars Combinatoria, 108 (2013) 193–200.
  * [7] D. Cvetkovic, P. Rowlinson, S. Simic, An Introduction to the Theory of Graph Spectra, London, 2010.
  * [8] Y.Y. Chen, H.Q. Lin, J.L. Shu, Sharp upper bounds on the distance spectral radius of a graph, Linear Algebra Appl. 439 (2013) 2659–2666.
  * [9] S.W. Drury, H.Q. Lin, Extremal digraphs with given clique number, Linear Algebra Appl. 439 (2013) 328–345.
  * [10] Roman Drnovsêk, The spread of the spectrum of a nonnegative matrix with a zero diagonal element, Linear Algebra Appl. 439 (2013) 2381–2387.
  * [11] X. Duan, B. Zhou, Sharp bounds on the spectral radius of a nonnegative matrix, Linear Algebra Appl. 439 (2013) 2961–2970.
  * [12] W.H. Haemers, Interlacing eigenvalues and graph, Linear Algebra Appl. 226–228 (1995) 593–616.
  * [13] W.X. Hong, L.H. You, Spectral radius and signless Laplacian spectral radius of strongly connected digraphs, Linear Algebra Appl. 457 (2014) 93–113.
  * [14] R.A. Horn, Charles R. Johnson, Matrix Analysis, Cambridge University Press, 1986.
  * [15] G. Indulal, I. Gutman, On the distance spectra of some graphs, Mathematical Communications, 13 (2008) 123–131.
  * [16] J.B. Jensen, G. Gutin, Digraphs Theory, Algorithms and Applications, Springer, 2001.
  * [17] H.Q. Lin, Y. Hong, J.F. Wang, J.L. Shu, On the distance spectrum of graphs, Linear Algebra Appl. 439 (2013) 1662–1669.
  * [18] H.Q. Lin, S.W. Drury, The maximum Perron roots of digraphs with some given parameters, Discrete Math. 313 (2013) 2607–2613.
  * [19] H.Q. Lin, R.F. Liu, X.W. Lu, The inertia and energy of the distance matrix of a connected graph, Linear Algebra Appl. 467 (2015) 29–39.
  * [20] H.Q. Lin, J.L. Shu, Y.R. Wu, G.L. Yu, Spectral radius of strongly connected digraphs, Discrete Math. 312 (2012) 3663–3669.
  * [21] H.Q. Lin, J.L. Shu, The distance spectral radius of digraphs, Discrete Applied Math. 161 (2013) 2537–2543.
  * [22] H.Q. Lin, W.H. Yang, H.L. Zhang, J.L. Shu, Distance spectral radius of digraphs with given connectivity, Discrete Math. 312 (2012) 1849–1856.
  * [23] Chia-an Liu, Chih-wen Weng, Spectral radius of bipartite graphs, arXiv:1402.5621v1 [math.CO] 23 Feb 2014.
  * [24] Z.Z. Liu, On spectral radius of the distance matrix, Appl. Anal. Discrete Math. 4 (2010) 269–277.
  * [25] O. Rojo, E. Lenes, A sharp upper bound on the incidence energy of graphs in terms of connectivity, Linear Algebra Appl. 438 (2013) 1485–1493.
  * [26] R. Xing, B. Zhou and J. Li, On the distance signless Laplacian spectral radius of graphs, Linear and Multilinear Algebra, 62 (2014) 1377–1387.
  * [27] M.L. Ye, Y.Z. Fan, D. Liang, The least eigevalue of graphs with given connectivity, Linear Algebra Appl. 430 (2009) 1375–1379.
  * [28] M.L. Ye, Y.Z. Fan, H.F. Wang, Maximizing signless Laplacian or adjacency spctral radius of graphs subject to fixed connectivity, Linear Algebra Appl. 433 (2010) 1180–1186.
  * [29] X.L. Zhang, The inertia and energy of the distance matrix of complete $k$-partite graphs, Linear Algebra Appl. 450 (2014) 108–120.


# Kinetic Exchange Income Distribution Models with Saving Propensities:
Inequality Indices and Self-Organised Poverty Lines

Sanjukta Paul<EMAIL_ADDRESS>Satyendra Nath Bose National Centre
for Basic Sciences, Block-JD, Salt Lake, Kolkata-700106, India.  Sudip
Mukherjee<EMAIL_ADDRESS>Department of Physics, Barasat Government
College, Kolkata 700124, India.  Saha Institute of Nuclear Physics, Kolkata
700064, India.  Bijin Joseph<EMAIL_ADDRESS>St. Xaviers College,
Mumbai 400001, India.  Asim Ghosh<EMAIL_ADDRESS>Department of
Physics, Raghunathpur College, Raghunathpur, Purulia 723133, India.  Bikas K.
Chakrabarti<EMAIL_ADDRESS>Saha Institute of Nuclear Physics,
Kolkata 700064, India.  Economic Research Unit, Indian Statistical Institute,
Kolkata 700108, India.

###### Abstract

We report the numerical results for the steady state income or wealth
distribution $P(m)$ and the resulting inequality measures (Gini $g$ and
Kolkata $k$ indices) in the kinetic exchange models of market dynamics. We
study the variations of $P(m)$ and of the indices $g$ and $k$ with the saving
propensity $\lambda$ of the agents, with two different kinds of trade (kinetic
exchange) dynamics. One, where the exchange occurs between randomly chosen
pairs of agents, other where one of the agents in the chosen pair is the
poorest of all and the other agent is randomly picked up from the rest (where,
in the steady state, a self-organized poverty level or SOPL appears). These
studies have also been made for two different kinds of saving behaviors. One
where each agent has the same value of $\lambda$ (constant over time) and the
other where $\lambda$ for each agent can take two values (0 and 1) and changes
randomly maintaining a fraction of time $\rho(<1)$ of choosing $\lambda=1$. We
also study the nature of distributions $P(m)$ and values of the inequality
indices ($g$ and $k$) and the SOPL as $\lambda$ and $\rho$ varies. We find
that the inequality decreases with increasing savings ($\lambda$).

##  I Introduction

The kinetic theory of gases, more than a century old and the first successful
classical many-body theory of condensed matter physics, has recently been
applied in econophysics and sociophysics (see e.g., sinha2010econophysics ;
chakrabarti2006econophysics ) in the modelling of different socio-economic
contexts. These two-body exchange dynamics studies have been extensively
developed in the context of modeling income or wealth distributions in a
society (see e.g., yakovenko2009colloquium ; chakrabarti2013econophysics ;
pareschi2013interacting . Further extensions of these kinetic exchange models
for social opinion formation studies, see e.g., sen2014sociophysics .

In generic kinetic exchange models of income or wealth distributions in a
society, one studies a system of $N$ agents who interact among themselves
through two-agent money ($m$) conserving stochastic trade (scattering)
processes, where each one saves a fraction $\lambda$ of their money or wealth
at each trade (exchange) or instant of time chakraborti2000statistical ;
chatterjee2004pareto . The resulting steady state distributions $P(m)$ of
money, for different values of the saving propensities $\lambda$ are compared
with the available data (see e.g., chakrabarti2013econophysics ;
chatterjee2007kinetic ). One can also study the effect of modification in the
kinetic exchange dynamics such that one of the agents in any chosen pair
participating in the trading (or scattering) process has the lowest money or
wealth at that point of time, while the other agent is selected randomly from
the rest of the population, with no constraint in the value of money
possessed. pianegonda2003wealth ; ghosh2011threshold . Alternatively, one can
also choose the pair of agents based on their total wealth, such that one of
them has money below an arbitrarily chosen poverty-line and the other one,
selected randomly from the whole population can have any value of money. The
kinetic exchange dynamics is continued until no agent is left with money below
a new Self-Organized Poverty-Line or SOPL ghosh2011threshold  (see also
iglesias2010simple ; chakrabarti2021development ). Then by varying $\lambda$,
it is investigated whether the SOPL can be shifted upwards.

The resulting inequalities can be measured here by determining the Most
Probable Income (MPI), given by the location of maximum value of the
distribution $P(m)$, or by the location of the SOPL, below which $P(m)=0$,
together with the determination of the values of Gini ($g$) and Kolkata ($k$)
indices (see e.g., chakrabarti2021development ; banerjee2020inequality ). Both
the indices, Gini (oldest and most popular one) and Kolkata (introduced in
ghosh2014inequality , see banerjee2020inequality  for a recent review), are
based on the Lorenz curve or function (see chakrabarti2021development ;
banerjee2020inequality ) $L(x)$, giving the cumulative fraction
($L=\int_{0}^{m}mP(m)dm$/ $[\int_{0}^{\infty}mP(m)dm]$) of (total accumulated)
income or wealth possessed by the fraction
($x=\int_{0}^{m}P(m)dm/[\int_{0}^{\infty}P(m)dm]$) of the population, when
counted from the poorest to the richest (see Fig. 1).

If the income (wealth) of every agent is identical, then $L(x)$ will be a
linear function represented by the diagonal (in Fig. 1) passing through the
origin. This diagonal defined by $L(x)=x$, is called the equality line. The
Gini coefficient ($g$) is given by the area between the Lorenz curve $L(x)$
and the equality line (normalized the area under the equality line): $g$ = 0
corresponds to equality and $g$ = 1 corresponds to extreme inequality. The
Kolkata index or $k$-index is given by the ordinate value $k$ of the
intersecting point of the Lorenz curve and the diagonal perpendicular to the
equality line. By construction, (see Fig. 1) $1-L(k)=k$, that $k$ fraction of
wealth is being possessed by ($1-k$) fraction of the richest population. As
such, it gives a quantitative generalization of the approximately established
(phenomenological) 80–20 law of Pareto (see e.g., banerjee2020inequality ),
indicating that typically about $80\%$ wealth is possessed by only $20\%$ of
the richest population in any economy. Now defining the complementary Lorenz
function $L^{c}(x)\equiv[1-L(x)]$, one gets $k$ as its (nontrivial) fixed
point (while Lorenz function $L(x)$ itself has trivial fixed points at $x$ = 0
and 1). As such, $k$ = 0.5 corresponds to complete equality and $k$ = 1
corresponds to extreme inequality. As an example, both $g$ and $k$ may be
exactly calculated or estimated in the well known case of Gibbs distribution
(normalized) $P(m)=\exp(-m)$: With
$x=\int_{0}^{m}\exp(-m^{\prime})dm^{\prime}=1-\exp(-m)$, giving $m=-\ln(1-x)$,
and $L=\int_{0}^{m}m^{\prime}\exp(-m^{\prime})dm^{\prime}$ =
$1-(m+1)\exp(-m)$, giving $L(x)=$ $1-(1-x)[1-\ln(1-x)]$. As the area under the
equality line is 1/2, the Gini index $g=$ $2\int_{0}^{1}L(x)dx=1/2$ and the
Kolkata index $k$ for this Gibbs (exponential) distribution is given by the
self-consistent equation $1-k=L(k)$ or $1-2k=(1-k)[\ln(1-k)]$, giving $k\simeq
0.68$.

Figure 1: The Lorenz curve $L(x)$ represents the fraction of overall income or
wealth assumed by the bottom $x\%$ fraction of the people. The Gini
coefficient is the ratio of the area that lies between the line of equality
and Lorenz curve over the total area under the line of equality (Gini index
$g=2s$). The complementary Lorenz function $L^{c}(x)\equiv 1-L(x)$ function is
represented by the green line. The $k$ index is the ordinate value of the
intersecting point of the Lorenz curve and the diagonal perpendicular to the
equality line. Therefore, the index value $k$ implies that $k$ fraction of
poorest people possess only $1-k$ fraction of the total income.

In this paper we numerically study the variations of income or wealth
distribution $P(m)$ generated from the kinetic exchange models described below
(section II) and extract the variations in the values of Gini $g$ and Kolkata
$k$ indices with the saving propensity $\lambda$ of the agents, with two
different kinds of trade or (kinetic) exchange dynamics (see e.g.,
sinha2020econophysics  for a pedagogic to the simulations of kinetic exchange
models). First, where the exchange occurs among randomly chosen pairs of
agents (where the most probable income in the steady state increases with
increasing saving propensity $\lambda$) and second, where one of the agents or
traders in the chosen pair is the poorest one at that point of time (trade,
exchange or scattering) while the other one is randomly picked up from the
rest (where, in the steady state, a self-organized minimum poverty level or
SOPL of income or wealth appears). These studies have also been done for two
different kinds of saving behaviors. First, where each agent has the same
value of $\lambda$ (constant over time) and varies from zero (exactly soluble;
Gibbs limit) to values of $\lambda$ infinitesimally smaller than unity (where
dynamics stops). Second where $\lambda$ for each agent can take two values,
zero or unity, and it changes randomly over time or trade, with the fraction
$\rho(<1)$ of time any agent chooses $\lambda=1$. Along with the nature of
steady state distributions $P(m)$, we have studied the variations in the
values of the inequality indices ($g$ and $k$) and the location of the Most
Probable Income or wealth (MPI) or the Self-Organized Poverty Line (SOPL, if
any) of income or wealth as the saving propensity $\lambda$ of the agents
(fixed over time) and as the time fraction $\rho$ of choosing the saving
propensity $\lambda=1$ over the other choice $\lambda=0$.

The rest of the paper is organized as follows. In section II, we describe the
kinetic-exchange model of trade between the agents followed by calculation of
wealth distribution and inequality indices obtained through Monte Carlo
simulations by invoking different kinds of kinetic exchange dynamics. In
section III we summarize our work and conclude with useful discussions.

##  II Models and Simulation Results

In this section, we will discuss the numerical studies of the kinetic exchange
models of income distribution (among agents or traders having saving
propensities $\lambda$), employing two kinds of dynamics. One is for the
straightforward randomly chosen pair-wise money conserving kinetic exchange
process (with distributions having most probable income or MPI ), and the
other is for similar money conserving kinetic exchange between the agents of a
pair, where one agent always has the lowest income and the other one is chosen
randomly from the rest (with the resulting distributions having self-organized
poverty line or SOPL). The agents are considered to have the same (and fixed
over time) saving propensities $\lambda$ (values in the range 0 to $1_{-}$) in
one case and in the other case every agent has a choice of $\lambda$ between 0
and 1, with the average fraction $\rho$ (maximum value $1_{-}$) of choosing
$\lambda=1$. The resulting income distributions are characterized by the
values of MPI or SOPL (whichever applicable) and of the inequality indices
Gini ($g$) and Kolkata ($k$), introduced earlier.

We performed numerical simulations with fixed number of agents $N$ and total
money $M=N$ for both the models. In our simulation, one Monte Carlo step is
equivalent to $N$ pairwise exchanges. We take $N=1000$ agents and total money
$M=N=1000$, initially distributed over all the agents uniformly. The steady
state distribution is measured over $10^{3}$ Monte Carlo time steps after
relaxing $10^{6}$ Monte Carlo time steps for equilibration.

Figure 2: The pure kinetic exchange dynamics: (a) The steady state income
distributions P(m) for different saving propensity $\lambda$ are shown in the
plot. (Inset) The same distributions are shown in semi-log scale indicating an
exponential nature of the tail end of the distributions. (b) The variation of
Kolkata index ($k$), Gini index ($g$) and Most Probable Income (MPI) are shown
against fixed saving propensity $\lambda$ (maximum value of $\lambda$ is
$1_{-}$).

###  II.1 Uniform saving income exchange models and inequality indices

In this model, we consider a conserved system where total money $M$ and total
agents $N$ are fixed. Each agent i possesses money $m_{i}(t)$ at a time t and
in any interaction, a pair of agents i and j exchange their money such that
their total money is conserved. For fixed saving propensity $\lambda$ of the
agents, the exchange of money between two randomly chosen pairs can be
expressed as

$\begin{split}m_{i}(t+1)&=\lambda
m_{i}(t)+\epsilon_{ij}((1-\lambda)(m_{i}(t)+m_{j}(t)))\\\ m_{j}(t+1)&=\lambda
m_{j}(t)+(1-\epsilon_{ij})((1-\lambda)(m_{i}(t)+m_{j}(t)))\end{split}$ (1)

where $0\leq\epsilon_{ij}\leq 1$ is a random fraction varying in every
interaction.

The steady state income distribution $P(m)$ as a function of money for fixed
saving propensity $\lambda$ are shown in Fig. 2(a). For $\lambda=0$, the
steady state follows a Gibbs distribution and Most Probable Income (MPI)
distribution is at MPI= 0. MPI per agent shifts from m = 0 to m = 1 as
$\lambda\to 1$. Furthermore, the plot in semi-log (as shown in Fig. 2(a)
inset) indicates an exponential nature for the tail end of the distribution.

In plot 2(b), we show the variation of Kolkata index ($k$), Gini index ($g$)
and Most Probable Income (MPI) against saving propensity $\lambda$. The Gini
coefficient value diminishes from $0.5$ to $0$ as $\lambda$ approaches from
$0$ to $1$. Similarly $k$-index value reduces from $0.68$ to $0.5$ as
$\lambda$ approaches from $0$ to $1$.

###  II.2 Self-organized minimum poverty line model and inequality indices

Here we consider a model where one of the agents in the chosen pair is
necessarily the poorest at that point of time and the other one is randomly
chosen from the rest (where, in the steady state, a self-organized minimum
poverty level or SOPL appears). The exchange of money will follow the same
rule as described by Eqn. 1.

In Fig. 3(a), the steady state income distribution $P(m)$ for different
$\lambda$ values are shown and the same distributions are shown in semi-log
scale in the inset indicating an exponential nature of the tail end of the
distributions. In Fig. 3(b), the variation of Kolkata index ($k$), Gini index
($g$) and Self-Organized Poverty-Line or SOPL are shown against saving
propensity $\lambda$. The figure indicates that inequality of the distribution
diminishing as $\lambda\to 1$ and also Self-Organized Poverty-Line or SOPL is
rising to 1 as $\lambda\to 1$.

Figure 3: Self-Organized Poverty Line model: (a) Steady state income
distribution $P(m)$ for fixed saving propensity $\lambda$ are shown. (Inset)
The same distributions are shown in semi-log scale indicating an exponential
nature of the tail end of the distributions. (b) The variation of Kolkata
index ($k$), Gini index ($g$) and location of the Self-Organized Poverty Line
(SOPL) are shown against fixed saving propensity $\lambda$ (maximum value of
$\lambda=1_{-}$).

###  II.3 Indices for pure kinetic exchange model of two choices of $\lambda$

Here we consider the same exchange dynamics as described in subsection II.1,
the only difference being that each agent has two choices of $\lambda$ over
time. In our study, the agents can take the saving propensity either 1 (with
probability $\rho$) or 0 (with probability $1-\rho$) over time.

In Fig. 4(a), the steady state income distribution $P(m)$ is shown for
different probability $\rho$. We observe that the most probable income (MPI)
occurs at $m=0$, and the semi-log plots of the distributions indicate the
exponential nature of the tail end of the distribution (see inset of Fig.
4(a)). The Kolkata index ($k$) and Gini index ($g$) rise slowly against $\rho$
(see Fig. 4(b)).

Figure 4: The pure kinetic exchange model of two choices of $\lambda$. (a)
Steady state income distribution $P(m)$ for fixed saving propensity $\lambda$
are shown. (Inset) The same distributions are shown in semi-log scale
indicating an exponential nature of the tail end of the distributions. (b) The
variation of Kolkata index ($k$) and Gini index ($g$) are shown against the
probability for taking $\lambda=1$ i.e. $\rho$ (maximum value of
$\rho=1_{-}$).

###  II.4 Self-organized minimum poverty line model: Indices for two choices
of $\lambda$

As before, we consider the same dynamics as described in subsectionII.2 but
the difference is that each agent has two choices of $\lambda$ over time. In
our study, the agents can take the saving propensity either 1 (with
probability $\rho$) or 0 (with probability $1-\rho$) over time. In Fig. 5(a),
the steady state income distribution $P(m)$ is shown for different probability
$\rho$. The semi-log plots of the distributions indicate the exponential
nature of the distribution (see inset of Fig. 5(a)). The variation of Kolkata
index ($k$) and Gini index ($g$) and Self-Organized Poverty-Line or SOPL are
shown against $\rho$ in Fig. 5(b). A very slow increasing trend of the
inequality indices with $\rho$ can be observed here. Also SOPL of the
distribution slowly decreases against $\rho$.

Figure 5: Self-organized minimum poverty line model for two choices of saving
propensity: (a) The steady state income distribution $P(m)$ for fixed saving
propensity $\lambda$ are shown. (Inset) The same distributions are shown in
semi-log scale indicating an exponential nature of the tail end of the
distributions.. (b) The variation of Kolkata index ($k$), Gini index ($g$) and
Self-Organized Poverty-Line or SOPL are shown against fixed saving propensity
$\lambda$. A very slow increasing trend of the inequality indices and a slow
decreasing trend of SOPL against $\rho$ can be observed here (maximum value of
$\rho=1_{-}$).

##  III Summary & Discussion

We have studied here numerically the variations of income or wealth
distribution $P(m)$ generated from the kinetic exchange models described below
and extracted the variations in the values of Gini $g$ and Kolkata $k$ indices
with the saving propensity $\lambda$ of the agents, with two different kinds
of trade or (kinetic) exchange dynamics. First, where the exchange occurs
among randomly chosen pairs of agents (where the most probable income in the
steady state increases with increasing saving propensity $\lambda$) and
second, where one of the agents or traders in the chosen pair is the poorest
one at that point of time (trade, exchange or scattering) while the other one
is randomly picked up from the rest (where, in the steady state, a self-
organized minimum poverty level or SOPL of income or wealth appears). These
studies have also been made for two different kinds of saving behaviors.
First, where each agent has the same value of $\lambda$ (constant over time)
that varies from zero (exactly soluble; Gibbs limit) to values infinitesimally
smaller than unity (where dynamics stops). Second, where $\lambda$ for each
agent can take two values, zero and unity, and it changes randomly over time
or trade, with the fraction $\rho(<1)$ of time any agent chooses $\lambda=1$.
Along with the nature of steady state distributions $P(m)$, we have studied
the variations in the values of the inequality indices ($g$ and $k$) and the
location of the Most Probable Income (MPI) or the Self-Organized Poverty Line
(SOPL, if any) of income or wealth as the saving propensity $\lambda$ of the
agents (fixed over time) and as the time fraction $\rho$ of choosing the
saving propensity $\lambda=1$ over the other choice $\lambda=0$.

As shown in Figs. 2-5, the most-probable income or MPI (where $P(m)$ is
highest) or the self-organized poverty line, the SOPL (below which $P(m)=0$
and usually the MPI coincides with the SOPL) increases with increasing saving
propensity or $\lambda$. Generally speaking, in all these fixed saving
propensity cases (see Figs. 2 and 3), the income or wealth inequalities, as
measured by the index values of Gini $g$ and Kolkata $k$ (= 0.5 and $\simeq$
0.68 respectively, in the pure kinetic exchange or Gibbs case, discussed
analytically in the Introduction) decreases with increasing saving propensity
($\lambda$) of the agents. This encouraging observation from kinetic exchange
models may have important economic policy implications.

## acknowledgments

BKC is thankful to the Indian National Science Academy for their Senior
Scientist Research Grant. BJ is grateful to the Saha Institute of Nuclear
Physics for the award of their Undergraduate Associateship.

## References

  * (1) Sitabhra Sinha, Arnab Chatterjee, Anirban Chakraborti, and Bikas K Chakrabarti.  Econophysics: an introduction.  John Wiley & Sons, 2010.
  * (2) Bikas K Chakrabarti, Anirban Chakraborti, and Arnab Chatterjee.  Econophysics and sociophysics: trends and perspectives.  John Wiley & Sons, 2006.
  * (3) Victor M Yakovenko and J Barkley Rosser Jr.  Colloquium: Statistical mechanics of money, wealth, and income.  Reviews of modern physics, 81(4):1703, 2009.
  * (4) Bikas K Chakrabarti, Anirban Chakraborti, Satya R Chakravarty, and Arnab Chatterjee.  Econophysics of income and wealth distributions.  Cambridge University Press, 2013.
  * (5) Lorenzo Pareschi and Giuseppe Toscani.  Interacting multiagent systems: kinetic equations and Monte Carlo methods.  OUP Oxford, 2013.
  * (6) Parongama Sen and Bikas K Chakrabarti.  Sociophysics: an introduction.  Oxford University Press, 2014.
  * (7) Anirban Chakraborti and Bikas K Chakrabarti.  Statistical mechanics of money: how saving propensity affects its distribution.  The European Physical Journal B-Condensed Matter and Complex Systems, 17(1):167–170, 2000.
  * (8) Arnab Chatterjee, Bikas K Chakrabarti, and SS Manna.  Pareto law in a kinetic model of market with random saving propensity.  Physica A: Statistical Mechanics and its Applications, 335(1-2):155–163, 2004.
  * (9) Arnab Chatterjee and Bikas K Chakrabarti.  Kinetic exchange models for income and wealth distributions.  The European Physical Journal B, 60(2):135–149, 2007.
  * (10) Salete Pianegonda, Jose Rroberto Iglesias, Guillermo Abramson, and JL Vega.  Wealth redistribution with conservative exchanges.  Physica A: Statistical Mechanics and its Applications, 322:667–675, 2003.
  * (11) Asim Ghosh, Urna Basu, Anirban Chakraborti, and Bikas K Chakrabarti.  Threshold-induced phase transition in kinetic exchange models.  Physical Review E, 83(6):061130, 2011.
  * (12) Jose Rroberto Iglesias.  How simple regulations can greatly reduce inequality.  arXiv:1007.0461; Science & Culture, 76:437–443, 2010.
  * (13) Bikas K Chakrabarti and Antika Sinha.  Development of econophysics: A biased account and perspective from kolkata.  Entropy, 23(2):254, 2021.
  * (14) Suchismita Banerjee, Bikas K Chakrabarti, Manipushpak Mitra, and Suresh Mutuswami.  Inequality measures: The kolkata index in comparison with other measures.  Frontiers in Physics, 8:562182, 2020.
  * (15) Asim Ghosh, Nachiketa Chattopadhyay, and Bikas K Chakrabarti.  Inequality in societies, academic institutions and science journals: Gini and k-indices.  Physica A: Statistical Mechanics and its Applications, 410:30–34, 2014.
  * (16) Antika Sinha, Sudip Mukherjee, and Bikas K Chakrabarti.  Econophysics through computation.  arXiv:2001.04188; Journal of Physics Through Computation, 3(1):1–54, 2020.