ARTICLE PREPRINT
On the restricted numerical range of the Laplacian matrix for
digraphs
T. R. Camerona , M. D. Robertsonb , and A. WiedemanncaPenn State Behrend, Erie, PA, USA; b Undergraduate Research; c Davidson College,
Davidson, NC, USA
ARTICLE HISTORY
Compiled March 19, 2020
ABSTRACTIn this article, we present the restricted numerical for the Laplacian matrix of adirected graph (digraph). We motivate our interest in the restricted numerical range
by its close connection to the algebraic connectivity of a digraph. Moreover, we showthat the restricted numerical range can be used to characterize digraphs, some ofwhich are not determined by their Laplacian spectrum. Finally, we identify a newclass of digraphs that are characterized by having a real restricted numerical range.
KEYWORDS
numerical range; directed graph; Laplacian; algebraic connectivity
AMS CLASSIFICATION
05C20, 05C50, 15A18, 15A60

1. Introduction
Spectral graph theory has a long and interesting history which intersects the seminal
works on the algebraic connectivity, i.e., the second smallest eigenvalue of the graphLaplacian [7,10]. Furthermore, the eigenvalues of the graph Laplacian have been used
to characterize graphs and have applications to data mining, image processing, mixingof Markov chains, chromatic numbers, and much more [16–18,20,21,24]. However, there
has been far less success in the study of the spectra of directed graphs, which is mainly
due to the asymmetry of the associated matrices [15,18].
While there are some results on the spectra of digraphs, see [5] and the references
therein, these results are specific to the adjacency matrix or the (symmetric) Laplacianmatrix for strongly connected digraphs as defined in [8]. A few notable exceptions are
the results in [2,6,22], which apply to the (asymmetric) Laplacian matrix for digraphs.
In this article, we develop a novel approach for characterizing digraphs using the
restricted numerical range of the Laplacian matrix. Until now, the numerical range
has played only a minor role in graph theory, where it has been used to develop
eigenvalue bounds, study the essential spectrum of the Laplace operator, and to model
uncertainty curves in spectral graph theory [1,9,19]. We will show that, in fact, thea trc5475@psu.edu
c alwiedemann@davidson.edu

restricted numerical range of the Laplacian matrix is teeming with information about
the underlying digraph. In particular, in Section 2, we demonstrate that the algebraic
connectivity of a digraph can easily be obtained from its restricted numerical range.
In Section 3, we classify several digraphs that are characterized by their restrictednumerical range but not their Laplacian spectrum. Furthermore, in Section 4, we
identify a new class of digraphs that are characterized by having a real restrictednumerical range.

2. The Laplacian Matrix and the Restricted Numerical Range
In this section, we define the Laplacian matrix for digraphs and its restricted numerical
range. We motivate our interest in the restricted numerical range by illustrating its
connection to the algebraic connectivity of a digraph and using it to characterize theempty, complete, and cycle digraphs.
2.1. The Laplacian Matrix for Digraphs
Let G denote the set of finite simple unweighted digraphs. For each Γ ∈ G, we have
Γ = (V, E), where V = {1, 2, . . . , n} is the vertex set and E ⊆ V × V is the edge set,and (i, j) ∈ E if and only if there is an edge from i to j.
Given Γ ∈ G, we denote the out-degree of the vertex i ∈ V by d+ (i), which is equal
to the number of edges of the form (i, j) ∈ E. Similarly, we denote the in-degree of thevertex i ∈ V by d− (i), which is equal to the number of edges of the form (j, i) ∈ E.
We define the out-degree matrix as the diagonal matrix D whose ith diagonal entry
is equal to d+ (i), for all i = 1, . . . , n. In addition, we define the adjacency matrix
as the (0, 1) matrix A = [aij ]ni,j=1 , where aij = 1 if and only if the edge (i, j) ∈ E.
Furthermore, we define the Laplacian matrix of Γ by
L = D − A.
Let Γ = (V, E) ∈ G and let V 0 ⊆ V . Then, we define the induced subgraph Γ0 of
Γ as the digraph with vertex set V 0 and edge set E 0 = E ∩ (V 0 × V 0 ). A subgraphof Γ is strongly connected if for each pair of vertices i, j ∈ V 0 , either i = j or there
is a directed path from i to j and a directed path from j to i. A strongly connectedcomponent of Γ is a maximal strongly connected subgraph.
A digraph Γ can be uniquely decomposed into strongly connected components.
Also, the Laplacian matrix, possibly after re-ordering the vertices, can be written in
Frobenius normal form [4]:


L1 L12 · · ·
L2 · · ·

L=
..

.


L1r
L2r 

..  ,. (1)

Lrwhere the blocks Lk are irreducible matrices that correspond to the strongly connectedcomponents Γk of Γ. Let Vk denote the vertex set of the strongly connected component
Γk . Then, the (i, j) entry of the (0, −1) submatrix Lkl , 1 ≤ k < l ≤ r, is equal to −1
if and only if there is an edge from i ∈ Vk to j ∈ Vl .
2

2.2. The Restricted Numerical Range
In general, the numerical range (field of values) of a complex matrix A is defined asfollows [13,23]:
W (A) = {x∗ Ax : x ∈ Cn , kxk = 1} .
For our purposes, we are interested in the restricted numerical range of the Laplacianmatrix, which we define by
Wr (L) = {x∗ Lx : x ⊥ e, kxk = 1} ,where e is the all ones vector. Note that e is an eigenvector of L associated with thezero eigenvalue. For simplicity, we often reference Wr (L) as the restricted numerical
range of a digraph.
Our definition of the restricted numerical range is motivated by its close connection
to the algebraic connectivity for digraphs as defined in [22]. Indeed, let Γ ∈ G and let
L be the Laplacian matrix of Γ. Then, the algebraic connectivity of Γ is defined byα(Γ) = min xT Lx,
x∈S

where
S = {x ∈ Rn : x ⊥ e, kxk = 1} .
Another related and useful quantity isβ(Γ) = max xT Lx.
x∈S

We summarize this connection and other basic properties below. For the remainderof this section, let Q be a real n × (n − 1) orthonormal matrix whose columns are
orthogonal to e.
Proposition 2.1. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, thefollowing properties hold.
(i) The restricted numerical range satisfies Wr (L) = W (QT LQ).
(ii) The set Wr (L) is invariant under re-ordering of the vertices of Γ.
(iii) The eigenvalues of L are contained in Wr (L), except for the zero eigenvalue
associated with the eigenvector e.
(iv) The minimum real part of Wr (L) is equal to α(Γ), and the maximum real partof Wr (L) is equal to β(Γ).
Proof.
(i) This result follows directly from the fact that Q acts as a length preserving
bijection between Cn−1 and the vectors in Cn that are orthogonal to e.
(ii) The re-ordering of the vertices of Γ corresponds to a permutation matrix P suchthat P T LP is the Laplacian matrix of the re-ordered digraph. Furthermore, P Q
is a real n × (n − 1) orthonormal matrix with columns orthogonal to e. Therefore,
Wr (L) = W (QT P T LP Q) = Wr (P T LP ).
3

(iii) Since e is an eigenvector of L associated with the zero eigenvalue, we have

 T
  T

Q LQ QT Lê
Q LQ 0[Q ê] L[Q ê] = T= T,ê LQ êT Lê
ê LQ 0T√
where ê = e/ n. Therefore, the eigenvalues of L are the union of the eigenvaluesof QT LQ and the zero eigenvalue associated with the eigenvector e. The result
follows from noting that Wr (L) contains the eigenvalues of QT LQ.
(iv) By [13,23, Theorem 9], the minimum and maximum real parts of Wr (L) is equal
to the minimum and maximum eigenvalues, respectively, of the symmetric partof QT LQ. These values are attained in Wr (L) by the associated eigenvectors of
the symmetric part of QT LQ. The result follows since these eigenvectors can betaken to be real.

2.3. Examples
In Figure 1, the empty and complete digraph on 6 vertices are shown. It is clear thatboth the empty
are determined by their Laplacian spectrum, and complete digraphswith σ(L) = 0(n) and σ(L) = 0, n(n−1) , respectively, where the exponent denotes
the algebraic multiplicity of the eigenvalue. We use these results to show that both theempty and complete digraphs are characterized by their restricted numerical range.
3

2

4

3

1

5

2

4

6

1

5

6

Figure 1. Empty and complete digraph on 6 vertices.

Theorem 2.2. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, Γ is anempty digraph if and only if Wr (L) = {0}.
Proof. Suppose that Γ is an empty digraph. Then, x∗ Lx = 0 for all x ∈ Cn and it
follows that Wr (L) = {0}.
Conversely, suppose that Wr (L) = {0}. Then, it follows that σ(L) = 0(n) and,
therefore, Γ is an empty digraph.
Theorem 2.3. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, Γ is acomplete digraph if and only if Wr (L) = {n}.
Proof. Suppose that Γ is a complete digraph. Then, L is a symmetric matrix with
spectrum σ(L) = 0, n(n−1) . It follows that the eigenvectors of L associated withthe eigenvalue n form an orthonormal basis for the subspace of vectors in Cn that areorthogonal to e. Hence, Wr (L) = {n}.
Conversely, suppose that Wr (L) = {n}. Then, it follows that σ(L) = 0, n(n−1)
and, therefore, Γ is a complete digraph.
4

Next, consider a directed cycle, as shown on 6 vertices in Figure 2. In what follows,
we show that the directed cycle is characterized by its Laplacian spectrum
and its√
restricted numerical range. Throughout, we denote the imaginary unit −1 by i.
3

2

4

1

5

6

Figure 2. Directed cycle on 6 vertices.

Theorem 2.4. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, Γ is a directed
cycle if and only ifnoσ(L) = 1 − ei2πj/n : j = 0, 1, . . . , n − 1 .
(2)
Proof. Suppose that Γ is a directed cycle. Then, possibly after re-ordering the vertices,
L is a circulant matrix whose first column vector is equal to [1, 0, . . . , 0, −1]T . As acirculant matrix with first column vector defined above, it is well-known that the
eigenvalues of L satisfy (2), e.g., see [11, Section 2.2].
Conversely, suppose that the eigenvalues of L satisfy (2). In what follows, we showthat L = I − A, where A is the adjacency matrix of Γ. Therefore,noσ(A) = ei2πj/n : j = 0, 1, . . . , n − 1 .
and it follows from [3, Theorem 2.2.20] that A has index of cyclicity equal to n. Hence,Γ is a directed cycle.
For the sake of contradiction, suppose that d+ (i) = 0 for some i ∈ V . Then, L canbe written in the Frobenius normal form (1) as
L1 L12 · · ·
L2 · · ·

L=
..

.


L1r
L2r 

..  ,. 
0

where, for each k = 1, . . . , r − 1, Lk is an irreducible non-singular M -matrix. Hence,by [3, Theorem 6.2.3 (N38)], L−1
k exists, is non-negative, and is irreducible. Also, by the
Perron-Frobenius theorem [3, Theorem 2.1.4], the spectral radius ρ(L−1k ) is a simple−1
eigenvalue of Lk . Now, let Lk denote the block with eigenvalue
λ = 1 − ei2π/n ,−1which is the smallest, in magnitude, non-zero eigenvalue of L. Then, ρ(L−1k ) = |λ|−1must be an eigenvalue of Lk , which contradicts the eigenvalues of L satisfying (2).
Therefore, d+ (i) 6= 0 for all i ∈ V . Furthermore, since tr (L) = n, we have d+ (i) = 1
for all i ∈ V . Hence, L = I − A, and the result follows.

5

In Lemma 2.5, we show that the normality of L implies the normality of QT LQ.
Note that the converse of this result does not hold. Then, in Theorem 2.6, we provethat a directed cycle is characterized by its restricted numerical range.
Lemma 2.5. Let L be the Laplacian matrix of any Γ ∈ G. If L is normal, then QT LQ
is normal.
Proof. Suppose that L is a normal matrix. Then, L has an orthonormal eigenvector
basis for Cn . Since e is always √an eigenvector of L, we denote this eigenvector basisby {v1 , . . . , vn }, where vn = e/ n. It follows that for each j = 1, . . . , n − 1 there is aunique xj ∈ Cn−1 such that Qxj = vj . Hence, {x1 , . . . , xn−1 } forms an orthonormal
basis for Cn−1 , where each xj is an eigenvector of QT LQ. Therefore, QT LQ is normal.
Theorem 2.6. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, Γ is a directed
cycle if and only if Wr (L) is the complex polygon with verticesno
1 − ei2πj/n : j = 1, . . . , n − 1 .

(3)

Proof. Suppose that Γ is a directed cycle on n vertices. Then, L is a circulant matrix
with eigenvalues that satisfy (2). Furthermore, as a circulant matrix, it is well-known
that the Fourier matrix provides a unitary diagonalization of L, e.g., see [11, Section2.2]. Therefore, L is a normal matrix and, by Lemma 2.5, it follows that QT LQ is anormal matrix. As a normal matrix, it follows that W (QT LQ) is equal to the convex
hull of σ(QT LQ) [13,23, Theorem 3], where σ(QT LQ) is equal to the set in (3).
Conversely, suppose that W (QT LQ) is the complex polygon with vertices in (3).
By [13,23, Theorem 13], the vertices of this complex polygon are the eigenvalues of
QT LQ. Therefore, σ(L) satisfies (2), and it follows from Theorem 2.4 that Γ is adirected cycle.
We conclude this section with a corollary that follows from Theorems 2.2, 2.3, 2.6
and Proposition 2.1 (iv.). We prove the converse of parts (i.) and (ii.) in Section 3.
Corollary 2.7. Let Γ ∈ G.
(i) If Γ is an empty digraph, thenα(Γ) = β(Γ) = 0.
(ii) If Γ is a complete digraph, thenα(Γ) = β(Γ) = n.
(iii) If Γ is a directed cycle, thenα(Γ) = 1 − Re ei2π/n
and

(
2

β(Γ) =
1 − Re eiπ(n−1)/n6

if n is even,
if n is odd.

3. Digraphs with Singleton Restricted Numerical Range
In the previous section, we saw that the empty and complete digraphs have a singleton
restricted numerical range. In this section, we characterize the class of digraphs thathave a singleton restricted numerical range. Furthermore, we show that this class ofdigraphs can be completely described by a directed join.
Definition 3.1. The directed join of the digraphs Γ = (V, E) and Γ0 = (V 0 , E 0 ) isdefined byΓ ∨ Γ0 = V ∪ V 0 , E ∪ E 0 ∪ (i, j) : i ∈ V, j ∈ V 0 .
Note that we allow Γ or Γ0 to be the null digraph (zero vertices), in which case thedirected join is a trivial operation that does not change the digraph of largest order.
We define a k-imploding star on n vertices, for k ∈ {0, 1, . . . , n}, by the directed joinEn−k ∨ Kk , where En−k is an empty digraph (zero edges) on (n − k) vertices and Kk
is a complete digraph on k vertices. Examples of 1-imploding and 2-imploding stars
on 6 vertices are shown in Figure 3.
2

2

3
5

6

1

3

1
6

4
5

4

Figure 3. Examples of 1-imploding (left) and 2-imploding (right) stars on 6 vertices.

Theorem 3.2. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, Γ is a
k-imploding star if and only if Wr (L) = {k}.
Proof. Suppose that Γ is a k-imploding star. Then, possibly after re-ordering thevertices, L can be written in the form



T

n
X

L = kI − e ej  ,

j=n−k+1

where I is the identity matrix and ej is the jth standard basis vector for Rn . Letx ∈ Cn be orthogonal to e. Then,x∗ Lx = x∗ kx − e 

n
X

T 

ej  x = kx∗ x.

j=n−k+1

It immediately follows that Wr (L) = {k}.
√Conversely, suppose that Wr (L) = {k}. In addition, let x = (ei − ej ) / 2, for some7

1 ≤ i < j ≤ n. Then, since x is orthogonal to e, we havek = xT Lx
1= (ei − ej )T (Lei − Lej )2
1= (lii + ljj − lij − lji ),2where L = [lij ]ni,j=1 . Hence,
2k = lii + ljj − lij − lji(4)for all 1 ≤ i < j ≤ n. Also, since α(Γ) = β(Γ) = k, it follows from [22, Lemma 8] thatd+ (i) = k −d− (i),n−1

for all vertices i ∈ V . Since lii = d+ (i) must be an integer and k is an integer, we havelii ∈ {k − 1, k} for all i = 1, . . . , n.
Now, let s be a non-negative
 integer such that lii = k, s times, and lii = (k − 1),(n − s) times. Since σ(L) = 0, k (n−1) , the trace of L gives us
ks + (k − 1)(n − s) = k(n − 1),from which it follows that s = (n − k). Therefore, we can re-order the vertices suchthat lii = k, for 1 ≤ i ≤ (n − k), and lii = (k − 1), for (n − k + 1) ≤ i ≤ n. Hence, after
this re-ordering of vertices, we can write the Laplacian matrix in the form
L11 L12L=,
L21 L22
where L11 is a (n − k) × (n − k) matrix whose diagonal entries are equal to k, and L22
is a k × k matrix whose diagonal entries are equal to (k − 1). If (n − k + 1) ≤ i < j ≤ n,then (4) implies that
2k = 2(k − 1) − lij − lji ,from which it follows that lij = lji = −1. Hence, L22 is the Laplacian matrix of Kk
and L21 is a zero matrix. Furthermore, applying (4) to vertices 1 ≤ i < j ≤ (n − k),gives us L11 = kI. Hence, every entry in L12 is equal to −1, and it follows that Γ is a
k-imploding star.
By Theorem 3.2, we know that every k-imploding star is in the class of digraphs witha singleton restricted numerical range. In fact, Theorem 3.3 implies that k-implodingstars are the only digraphs in this class. Before proving this result, note that, since L
is real, Wr (L) is symmetric with respect to the real axis and, hence, we only need toconsider real singleton restricted numerical ranges. Also, note that the complement of
the digraph Γ = (V, E) is defined as the digraph Γ = (V, E), whereE = {(i, j) ∈ V × V : (i, j) ∈/ E} .
8

Theorem 3.3. Let Γ ∈ G and let L be the Laplacian matrix of Γ. If Wr (L) = {k} forsome k ∈ R, then k must be an integer between 0 and n (inclusive). Therefore, Γ is a
k-imploding star.
Proof. As a general M -matrix, the real part of every eigenvalue of L is non-negative [3,Theorem 6.4.6(E11)]. Since k must be an eigenvalue of L, it follows that k ≥ 0.
For any Γ ∈ G, by [22, Lemma 4], we haveα(Γ) = n − β(Γ).
Also, β(Γ) must be non-negative; otherwise, the Laplacian spectrum of Γ would lie inthe left-half of the complex plane, which would contradict [3, Theorem 6.4.6(E11)].
Therefore, k = α(Γ) ≤ n.
Now, suppose that 0 ≤ k ≤ n is not an integer. Since α(Γ) = β(Γ) = k, it follows
from [22, Lemma 8] thatd+ (i) = k −d− (i),n−1

for all vertices i ∈ V . Since the ith diagonal element of L is equal to d+ (i), which must
be an integer, the graph Laplacian can be written in the following form
L = bkcI − A,√
where A = [aij ]ni,j=1 is the adjacency matrix of Γ. Let x = (ei − ej ) / 2. Since x is
orthogonal to e, it follows thatk = bkc − xT Ax

aii + ajj − aij − aji= bkc −2

aij + aji= bkc −.
2
Note that the above equation is a contradiction if either aij = aji = 0 or aij = aji = 1.
Therefore, aij = 1 or aji = 1, but not both, for all 1 ≤ i < j ≤ n; hence, Γ is atournament digraph. Furthermore, since the sum of the entries of L must equal zero,
we know that
bkc =

n−1
.
2

Hence, n must be an odd integer andd+ (i) = d− (i) =

n−1
,
2

for all i ∈ V . Therefore, Γ is a regular tournament digraph for which it is well-known,e.g., see [5, Section 8], that its adjacency matrix, possibly after re-ordering the vertices,can be written as
A = P + P 2 + · · · + P bkc ,9where P is the permutation matrix corresponding to the permutation (2, 3, . . . , n, 1).
Therefore, L is a circulant matrix whose eigenvalues satisfy


bkc 


s
X
i2πj/nσ(L) = bkc −: j = 0, 1, . . . , n − 1 ,
e


s=1

which contradicts Wr (L) lying entirely on the real line.
In the proof of Theorem 3.3, we saw that if α(Γ) = β(Γ) is not an integer, then Γmust be a regular tournament digraph. In particular, the following result clearly holds.
Corollary 3.4. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then Γ is a regular
tournament digraph if and only if n is odd and Wr (L) is a vertical line segment withreal part equal to n/2.
Moreover, from the proofs of Theorems 3.2 and 3.3, we have the following result,which implies the converse of parts (i.) and (ii.) of Corollary 2.7.
Corollary 3.5. Let Γ ∈ G. Then, α(Γ) = β(Γ) if and only if Γ is a k-imploding staror a regular tournament digraph. In particular, Γ is a k-imploding star if and only ifα(Γ) = β(Γ) = k ∈ {0, 1, . . . , n},and Γ is a regular tournament digraph if and only if n is odd andα(Γ) = β(Γ) =n.
2Finally, it is worth noting that for 1 ≤ k ≤ (n − 2), a k-imploding star is
not characterized by its Laplacian spectrum. Indeed, by simply removing an edgeof the form (i, j) ∈ V (En−k ) × V (Kk ) and replacing it by an edge of the form(i, j) ∈ V (En−k ) × V (En−k ), we obtain a cospectral digraph that is not isomorphic toEn−k ∨ Kk . For example, consider the digraph in Figure 4, which is cospectral but
not isomorphic to the 1-imploding star.
2
3
6

1

4
5
Figure 4. Digraph that is cospectral but not isomorphic to the 1-imploding star.

The above example raises the question: Are there digraphs that are characterized
by their Laplacian spectrum, but are not characterized by their restricted numerical
range? We suspect the answer to this question is no, which would make the restrictednumerical range a more robust tool for characterizing digraphs. For instance, by theelliptical range theorem [14], the restricted numerical range of a digraph on 3 vertices
is an ellipse with foci equal to the eigenvalues of the Laplacian not associated withe. Thus, if two digraphs on 3 vertices are characterized by their Laplacian spectrum,
then they must be characterized by their restricted numerical range.
104. Digraphs with Real Restricted Numerical Range
In the previous section, we characterized the class of digraphs that have a singleton
restricted numerical range. In this section, we extend that characterization to include
all digraphs with a real restricted numerical range. Note that every digraph in G on 1 or
2 vertices is a k-imploding star and, therefore, must have a real restricted numerical
range. Hence, we may assume that we are working with digraphs with at least 3
vertices. In Theorem 4.2, we show that the digraphs with real restricted numerical
range are balanced in the following sense.
Definition 4.1. A directed digraph Γ ∈ G with at least 3 vertices is called 3-balanced
if for any three distinct vertices i, j, k ∈ V , we haveaij + ajk + aki = aik + akj + aji ,(5)

where A = [aij ]ni,j=1 is the adjacency matrix of Γ.
Theorem 4.2. Let Γ ∈ G have at least 3 vertices and let L be the Laplacian matrixof Γ. Then, Wr (L) ⊂ R if and only if Γ is 3-balanced.
Proof. Let N = {1, 2, . . . , n} and k ∈ N . Then, for all i ∈ N \{k}, define xi = ei −ek .
First, we show that x∗ Lx ∈ R for all x ∈ Cn such that x ⊥ e if and only if
xTi Lxj = xTj Lxi ,(6)

for all i, j ∈ N \ {k}. Indeed, note that if (6) fails for some i, j ∈ N \ {k}, then(xi + ixj )∗ L (xi + ixj ) = xTi Lxi + ixTi Lxj − ixTj Lxi + xTj Lxj ∈/ R.
To see that (6) is sufficient, note that {xi }i∈N \{k} forms a basis for the subspace of
vectors in Cn that are orthogonal to e. Therefore, for each x ∈ Cn such that x ⊥ e,
we haveXx=
ci xi ,i∈N \{k}where the ci are complex scalars for i ∈ N \ {k}. Hence, if (6) holds, thenXx∗ Lx =

ci cj xTi Lxj

i,j∈N \{k}=Xi|ci |2 xTi Lxi +X(ci cj + ci cj ) xTi Lxj ∈ R,

i<jwhere c denotes the complex conjugate of the complex scalar c.
With (6) established, the result follows from noting that, for each i, j ∈ N \ {k}, wehave
xTi Lxj = lij − lik − lkj + lkk and xTj Lxi = lji − ljk − lki + lkk .

11

As an example, consider the digraphs in Figure 5. Note that both digraphs are 3balanced. Hence, by Theorem 4.2, it follows that both digraphs have a real restrictednumerical range. Moreover, note that both digraphs possess a structure very similar
to the k-imploding stars shown in Figure 3. In particular, they are the directed joinof two bidirectional digraphs.
2

2

3
5

6

1

3

1
6

4
5

4

Figure 5. Digraphs with real restricted numerical range.

It turns out that all 3-balanced digraphs possess this structure. Before proving thisresult, we note that a digraph is 3-balanced if and only if its reversal is 3-balanced,
where the reversal of a digraph is obtained by reversing the orientation of all the edges
in the original digraph. Also, a digraph is said to be bidirectional if it is equal to its
reversal.
Theorem 4.3. Let Γ ∈ G have at least 3 vertices. Then, Γ is 3-balanced if and only
if Γ is the directed join of two disjoint bidirectional digraphs in G.
Proof. Suppose that Γ = (V, E) can be written as the directed join
Γ = S ∨ T,where S = (Vs , Es ) and T = (Vt , Et ) are disjoint bidirectional digraphs. Let i, j, k ∈ V .
Note that (5) holds if i, j, k all belong to either Vs or Vt . Therefore, since a graph is
3-balanced if and only if its reversal is 3 balanced, we may assume that i, j ∈ Vs andk ∈ Vt . In this case, aij = aji , aik = ajk , and aki = akj , which implies that (5) holds.
Thus, Γ is a 3-balanced digraph.
Conversely, suppose that Γ is 3-balanced. In what follows, we use induction on thenumber of vertices to show that Γ must be the directed join of two disjoint bidirectionaldigraphs in G. The base case, where Γ has exactly 3 vertices, is readily verified.
Suppose that the result holds for all 3-balanced digraphs on n ≥ 3 vertices. Let Γ
be a 3-balanced digraph on (n + 1) vertices. Furthermore, let Γ0 be the subgraph ofΓ formed from the vertex set V 0 = {1, 2, . . . , n}. By the induction hypothesis, there
exists disjoint bidirectional digraphs S 0 = (Vs0 , Es0 ) and T 0 = (Vt0 , Et0 ) such thatΓ0 = S 0 ∨ T 0 .


Let k = (n + 1) and define
S = (Vs0 ∪ {k}, E ∩ ((Vs0 ∪ {k}) × (Vs0 ∪ {k})))andT = (Vt0 ∪ {k}, E ∩ ((Vt0 ∪ {k}) × (Vt0 ∪ {k}))) .
12

We split the induction step into two cases: First, when there is an edge from every
vertex in Vs0 to k; second, where there is a vertex in Vs0 that does not connect to k.
Note that if S 0 is null, then S contains only the vertex k. Furthermore, in order for Γto be 3-balanced it follows that either Γ = T or Γ = S ∨ T 0 . Similarly, if T 0 is null,then T contains only the vertex k and either Γ = S or Γ = S 0 ∨ T . Therefore, during
the induction step, we may assume that both S 0 and T 0 are not null.
Consider the first case, i.e., (i, k) ∈ E for all i ∈ Vs0 . If there is an i ∈ Vs0 suchthat both (i, k) ∈ E and (k, i) ∈ E, i.e., the edge (i, k) is bidirectional, then everyedge of the form (j, k) ∈ E, where j ∈ Vs0 , must be bidirectional. Otherwise, there
exists a bidirectional edge (i, k) ∈ E and a non-bidirectional edge (j, k) ∈ E, wherei, j ∈ Vs0 , and it follows that the vertices i, j, k violate (5). Hence, if the edge (i, k) is
bidirectional for some i ∈ Vs0 , then S must be a bidirectional digraph. In this case,(k, j) ∈ E and (j, k) ∈/ E for all j ∈ Vt0 . Indeed, if there exists a j ∈ Vt0 for which(k, j) ∈/ E or (j, k) ∈ E, then for any i ∈ Vs0 , the vertices i, j, k violate (5). Therefore,Γ = S ∨ T 0 , where S and T 0 are disjoint bidirectional digraphs.
Assume that each edge (i, k) ∈ E, where i ∈ Vs0 is not bidirectional. Then, T must
be a bidirectional digraph. Otherwise, there exists a non-bidirectional edge (j, k) ∈ Eor (k, j) ∈ E, where j ∈ Vt0 , and for any i ∈ Vs0 the vertices i, j, k violate (5). Therefore,Γ = S 0 ∨ T , where S 0 and T are disjoint bidirectional digraphs.
Consider the second case, i.e., there is an i ∈ Vs0 such that (i, k) ∈/ E. Then,(k, j) ∈ E for all j ∈ Vt0 . Otherwise, if there exists a j ∈ Vt0 such that (k, j) ∈/ E, thenthe vertices i, j, k violate (5). Furthermore, S must be a bidirectional digraph. Indeed,suppose for some i ∈ V there exists an edge (i, k) ∈ E which is not bidirectional.
Then, for any j ∈ Vt0 , the vertices i, j, k violate (5). Therefore, Γ = S ∨ T 0 , where S
0
and T are disjoint bidirectional digraphs.
Corollary 4.4. Let Γ ∈ G and let L be the Laplacian matrix of Γ. Then, Wr (L) ⊂ R
if and only if Γ is the directed join of two disjoint bidirectional digraphs in G.

5. Conclusion
The restricted numerical range of the Laplacian matrix is a novel tool for characterizing
digraphs and studying their algebraic connectivity. In Theorem 3.2 and Corollary 3.4,
we showed that k-imploding stars and regular tournament digraphs are characterized
by their restricted numerical range. Furthermore, in Corollary 3.5, we showed thatboth the k-imploding stars and regular tournament digraphs are determined by their
algebraic connectivity, i.e., α and β values. Finally, in Theorem 4.2, we identified a newclass of digraphs that are characterized by having a real restricted numerical range.
Note that the restricted numerical range has the practical advantage of avoiding
the eigenvalue computation of the potentially defective Laplacian matrix. Instead,the boundary of the numerical range is approximated using complex polygons whose
vertices are determined by the eigenvectors of a Hermitian matrix [12]. Moreover, thek-imploding stars offer an infinite number of digraphs that are characterized by theirrestricted numerical range, but are not characterized by their Laplacian spectrum.
Future research includes the relationship between digraphs that are characterized bytheir Laplacian spectrum and those that are characterized by their restricted numerical
range. Also, we are interested in digraphs with a restricted numerical range that is
a complex polygon and digraphs that have negative algebraic connectivity, i.e., theirrestricted numerical range intersects the left half of the complex plane.
13References[1] M. Balti, Non self-adjoint laplacians on a directed graph, Filomat, 31 (2017), pp. 5671–
5683.
[2] F. Bauer, Normalized graph Laplacians for directed graphs, Linear Algebra Appl., 436(2012), pp. 4193–4222.
[3] A. Berman and R. J. Plemmons, Nonnegative Matrices in the Mathematical Sciences,
SIAM, Philadelphia, PA, 1994.
[4] R. Brualdi and H. Ryser, Combinatorial Matrix Theory, Cambridge University Press,
United Kingdom, 1991.
[5] R. A. Brualdi, Spectra of digraphs, Linear Algebra Appl., 432 (2010), pp. 2181–2213.
[6] T. R. Cameron, A. N. Langville, and H. C. Smith, On the graph Laplacian andthe rankability of data, Linear Algebra Appl., 588 (2020), pp. 81–100.
[7] J. Cheeger, A lower bound for the smallest eigenvalue of the Laplacian, Problems in
Analysis, (1970), pp. 195–199.
[8] F. R. K. Chung, Laplacians and the Cheeger inequality for directed graphs, Ann. Comb.,
9 (2005), pp. 1–19.
[9] W. Erb, Shapes of uncertainty in spectral graph theory. arXiv:1909.10865.
[10] M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23(1973), pp. 298–305.
[11] R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge University Press, New
York, NY, 2nd ed., 2013.
[12] C. R. Johnson, Numerical determination of the field of values of a complex matrix,
SIAM J. Num. Analysis, 15 (1978), pp. 595–602.
[13] R. Kippenhahn, Über den wertevorrat einer matrix, Math. Nachr., 6 (1951), pp. 193–228.
[14] C. K. Li, A simple proof of the elliptical range theorem, Proc. Amer. Math. Soc., 124(1996), pp. 1985–1986.
[15] Y. Li, X. Wu, and A. Lu, Analysis of spectral space properties of directed graphs using
matrix perturbation theory with application in graph partition, in 2015 IEEE International
Conference on Data Mining, IEEE, 2015, pp. 847–852.
[16] X. Liu and S. Wang, Laplacian spectral characterizations of some graph products, Linear
Algebra Appl., 437 (2012), pp. 1749–1759.
[17] B. Mohar, Some applications of Laplace eigenvalues of graphs, in Graph Symmetry:
Algebraic Methods and Applications, Springer, 1997, pp. 225–275.
[18] D. A. Spielman, Spectral graph theory and its applications, in Proceedings of the 48th
Annual IEEE Symposium on Foundations of Computer Science, IEEE, 2007, pp. 29–38.
[19] M. Tajarrod and T. Sistani, Numerical range of simple graphs and some bounds fortheir eigenvalues, J. Math. Ext., 12 (2018), pp. 21–37.
[20] E. R. van Dam and W. Haemers, Which graphs are determined by their spectrum?,
Linear Algebra Appl., 373 (2003), pp. 241–272.
, Developments on spectral characterizations of graphs, Discrete Math., 309 (2009),[21]
pp. 576–586.
[22] C. W. Wu, Algebraic connectivity of directed graphs, Linear Multilinear Algebra, 53(2005), pp. 203–223.
[23] P. F. Zachlin and M. E. Hochstenbach, On the numerical range of a matrix, Linear
Multilinear Algebra, 56 (2008), pp. 185–225. English translation of [13], with comments
and corrections.
[24] Y. Zhang, X. Liu, and X. Yong, Which wheel graphs are determined by their Laplacian
spectra?, Comput. Math. Appl., 58 (2009), pp. 1887–1890.

14