In 2020, Cameron et al. introduced the restricted numerical range of a digraph (directed graph) as a tool for characterizing digraphs and studying their algebraic connectivity.
In particular, digraphs with a restricted numerical range of a single point, a horizontal line segment, and a vertical line segment were characterized as $k$-imploding stars, directed joins of bidirectional digraphs, and regular tournaments, respectively.
In this article, we extend these results by investigating digraphs whose restricted numerical range is a convex polygon in the complex plane.
We provide computational methods for identifying these polygonal digraphs and show that these digraphs can be broken into three disjoint classes: normal, restricted-normal, and pseudo-normal digraphs, all of which are closed under the digraph complement.
We prove sufficient conditions for normal digraphs and show that the directed join of two normal digraphs results in a restricted-normal digraph.
Also, we prove that directed joins are the only restricted-normal digraphs when the order is square-free or twice a square-free number.
Finally, we provide methods to construct restricted-normal digraphs that are not directed joins for all orders that are neither square-free nor twice a square-free number.

numerical range; directed graph; Laplacian; algebraic connectivity

05C20, 05C50, 15A18, 15A60, 51-08

§ INTRODUCTION

Let $\mathbb{G}$ denote the set of finite simple unweighted digraphs.
For each $\Gamma\in\mathbb{G}$, we have $\Gamma=(V,E)$, where $V$ is the vertex set, $E\subseteq V\times V$ is the edge set, and $(i,j)\in E$ if and only if $i\neq j$ and there is an edge from vertex $i$ to vertex $j$.
The order of $\Gamma$ is equal to $\abs{V}$; when $\abs{V}=0$, we refer to $\Gamma$ as the null digraph.

Given $\Gamma\in\mathbb{G}$ of order $n$, we denote the out-degree of the vertex $i\in V$ by $d^{+}(i)$, which is equal to the number of edges of the form $(i,j)\in E$.
Similarly, we denote the in-degree of the vertex $i\in V$ by $d^{-}(i)$, which is equal to the number of edges of the form $(j,i)\in E$.
After indexing the vertex set as $V=\{1,2,\ldots,n\}$, we define the Laplacian matrix of $\Gamma$ by $L=[l_{ij}]_{i,j=1}^{n}$, where

\[
l_{ij} = \begin{cases} d^{+}(i) & \text{if $i=j$} \\ -a_{ij} & \text{if $i\neq j$} \end{cases}
\]

and $A = [a_{ij}]_{i,j=1}^{n}$ is the adjacency matrix of $\Gamma$, that is, $a_{ij} = 1$ if $(i,j)\in E$ and $a_{ij} = 0$ otherwise. We use subscript notation to indicate the particular digraph when it is unclear from the surrounding context, for example, $d_{\Gamma}^{+}(i)$ denotes the out-degree of vertex $i$ in digraph $\Gamma$.

In general, the numerical range (or field of values) of a complex matrix $A\in\mathbb{C}^{n\times n}$ is defined as follows [10, 16]:

\[
W(A) = \left\{\mathbf{x}^{*}A\mathbf{x}\colon~\mathbf{x}\in\mathbb{C}^{n},~\norm{\mathbf{x}}=1\right\},
\]

where $\norm{\cdot}$ denotes the Euclidean norm on complex vectors.
For our purposes, we are interested in the restricted numerical range of the Laplacian matrix, which we define by

\[
W_{r}(L) = \left\{ \mathbf{x}^{*}L\mathbf{x}\colon~\mathbf{x}\in\mathbb{C}^{n},~\mathbf{x}\perp\mathbf{e},~\norm{\mathbf{x}}=1\right\},
\]

where $\mathbf{e}$ is the all ones vector of dimension $n$.
Clearly $W_{r}(L)=\emptyset$ when $n=1$.
If the dimension is unclear from context, we use the notation $\mathbf{e}^{n}$.
When convenient, we may refer to $W_{r}(L)$ as the restricted numerical range of a digraph, and mix the notation $W_{r}(L)$ with $W_{r}(\Gamma)$.

The definition of the restricted numerical range is motivated by its close connection to the algebraic connectivity for digraphs as defined in [14].
Indeed, let $\Gamma\in\mathbb{G}$ have order $n$ and let $L$ be the Laplacian matrix of $\Gamma$.
Then, the algebraic connectivity of $\Gamma$ is defined by

\[
\alpha(\Gamma) = \min_{\mathbf{x}\in\mathcal{S}}\mathbf{x}^{T}L\mathbf{x},
\]

\[
\mathcal{S} = \left\{\mathbf{x}\in\mathbb{R}^{n}\colon~\mathbf{x}\perp\mathbf{e},~\norm{\mathbf{x}}=1\right\}.
\]

Another related and useful quantity is

\[
\beta(\Gamma) = \max_{\mathbf{x}\in\mathcal{S}}\mathbf{x}^{T}L\mathbf{x}.
\]

We summarize this connection and other basic properties below.
Note thate we define a restrictor matrix of order $n$ as an $n\times(n-1)$ orthonormal matrix whose columns are orthogonal to $\mathbf{e}$.
If $n=1$, then the restrictor matrix is an empty matrix, that is, a matrix where the number of columns is zero.
Also, we use $\conj{\Gamma}$ to denote the complement digraph of $\Gamma$, that is, the digraph whose edge set consists exactly of those directed edges not in $\Gamma$.

Let $\Gamma\in\mathbb{G}$ have order $n$ and let $L$ be the Laplacian matrix of $\Gamma$.
Also, let $Q$ be a restrictor matrix of order $n$.
Then, the following properties hold.

* The restricted numerical range satisfies $W_{r}(L)=W(Q^{*}LQ)$.

* The set $W_{r}(L)$ is invariant under re-ordering of the vertices of $\Gamma$.

* The eigenvalues of $L$ are contained in $W_{r}(L)$, except (possibly) for the zero eigenvalue associated with the eigenvector $\mathbf{e}$.

* The minimum real part of $W_{r}(L)$ is equal to $\alpha(\Gamma)$ and the maximum real part of $W_{r}(L)$ is equal to $\beta(\Gamma)$.

* Let $\conj{L}$ denote the Laplacian matrix of the complement digraph. Then, $W_{r}(\conj{L}) = n - W_{r}(L)$.

For (i)–(iv), see <cit.>.
For (v), note that $\conj{L} = \left(nI - \mathbf{e}\mathbf{e}^{T}\right) - L$.

\begin{align*}
W_{r}(\conj{L}) &= W(Q^{*}\conj{L}Q) \\
&= W(nI - Q^{*}LQ) \\
&= n - W(Q^{*}LQ),
\end{align*}

by <cit.>.

Next, we summarize the known characterizations of digraphs using the restricted numerical range.
Note that the directed join of digraphs $\Gamma = (V,E)$ and $\Gamma'=(V',E')$, where $V\cap V'=\emptyset$, is defined by

\[
\Gamma\djoin\Gamma' = \left(V\sqcup V',E\sqcup E'\sqcup\left\{(i,j)\colon~i\in V,j\in V'\right\}\right),
\]

and $E_{n}$ and $K_{n}$ denote the empty and complete digraph of order $n$, respectively.

Let $\Gamma\in\mathbb{G}$ have order $n$  and let $L$ be the Laplacian matrix of $\Gamma$.
Then, the following characterizations hold:

* $\Gamma$ is a dicycle (directed cycle) of order $n$ if and only if $W_{r}(L)$ is a complex polygon with vertices

\[
\left\{1-e^{\iu 2\pi j/n}\colon j=1,\ldots,n-1\right\},
\]

where $\iu$ denotes the imaginary unit.

* $\Gamma$ is a $k$-imploding star, that is, $\Gamma = E_{n-k}\djoin K_{k}$ for some $k\in\{0,1,\ldots,n\}$, if and only if $W_{r}(L)$ is a single point.
Moreover, the numerical value of this point is $k$.

* $\Gamma$ is a regular tournament if and only if $W_{r}(L)$ is a vertical line segment. Moreover, $n$ is odd and this vertical line segment has real part $n/2$.

* $\Gamma$ is a directed join of two bidirectional digraphs, where one may be the null digraph, if and only if $W_{r}(L)$ is a horizontal line segment. Moreover, this line segment lies on the non-negative portion of the real axis.

For (i), see <cit.>; for (ii), see <cit.>; for (iii), see <cit.>; for (iv), see <cit.>.

Note that parts (ii)–(iv) of Theorem <ref> completely describe all digraphs with a restricted numerical range as a degenerate polygon, that is, a point or a line segment in the complex plane.
In this article, we extend these results to include digraphs whose restricted numerical range is a non-degenerate convex polygon in the complex plane.
Throughout, we refer to digraphs whose restricted numerical range is a degenerate or non-degenerate convex polygon in the complex plane as polygonal.

Partial motivation for studying polygonal digraphs comes from their application to synchronization theory.
Indeed, consider the parameter $\mu(L)$, which is defined as the supremum of the set of real numbers $\mu$ such that $U(L-\mu I) + (L^{T}-\mu I)U$ is positive semi-definite for some irreducible symmetric zero sum matrix $U$ with non-positive off-diagonal entries.
In [15], it is shown that $\mu(L)$ is a measure of how well the topology of the associated coupled network is amenable to synchronization.
In particular, the larger $\mu(L)$ is, the easier it is to synchronize the network.
The following proposition extends the result in <cit.>.
Note that $\sigma(\cdot)$ denotes the multi-set of eigenvalues for a given square complex matrix.

Let $\Gamma\in\mathbb{G}$ have order $n$ and let $L$ be the Laplacian matrix of $\Gamma$.
If $\Gamma$ is polygonal, then $\alpha(\Gamma) = \mu(L)$.

By <cit.>, it follows that

\[
\alpha(\Gamma)\leq \mu(L)\leq\min_{\lambda\in\sigma(Q^{*}LQ)}\re{\lambda},
\]

where $Q$ is a restrictor matrix of order $n$.
Since $\Gamma$ is polygonal, $W_{r}(L)$ is a convex polygon whose vertices, by Proposition <ref> (i) and <cit.>, are eigenvalues of $Q^{*}LQ$.

\[
\alpha(\Gamma) = \min_{\lambda\in\sigma(Q^{*}LQ)}\re{\lambda}.
\]

In [1], the value

\[
\min_{\lambda\in\sigma(Q^{*}LQ)}\re{\lambda}
\]

is called the generalized algebraic connectivity of $\Gamma$ and it is shown that this value reflects the expected asymptotic convergence rate of cooperative consensus-based algorithms in an asymmetric network represented by $\Gamma$.
Hence, our investigation of polygonal digraphs will help identify networks for which the algebraic connectivity $\alpha(\Gamma)$, the generalized algebraic connectivity from [1], and the synchronization parameter $\mu(L)$ from [15] are equal.

In addition, our study of polygonal digraphs will help identify digraphs for which the algebraic connectivity satisfies $\alpha(\Gamma)=0$ if and only if $\Gamma$ has multiple terminal strongly connected components, see Proposition <ref>.
Ideally, this result would hold for all digraphs since $\alpha(\Gamma)$ is a generalization of Fiedler's algebraic connectivity for undirected graphs [3] and the number of terminal strongly connected components in a digraph is equal to the algebraic (and geometric) multiplicity of the zero eigenvalue of the corresponding Laplacian matrix [12].
However, as illustrated by Figure 1, this result is not in general true for all digraphs.
Indeed, Figure <ref> shows a digraph that has only one terminal strongly connected component, yet its algebraic connectivity is zero.
Note that the digraph is shown on the left with the restricted numerical range on the right, and the eigenvalues of $Q^{*}LQ$ are displayed using the star symbol.
The digraph vertices are not labeled since, by Proposition <ref>, the restricted numerical range is invariant under re-ordering of the vertices.

Note that given any $\Gamma=(V,E)\in\mathbb{G}$ we can partition the vertices as $V=V_{1}\sqcup V_{2}\sqcup\cdots\sqcup V_{k}$, where for each $i=1,\ldots,k$, the subdigraph induced by $V_{i}$ is strongly connected, that is, there exists a directed path between all pairs of vertices in $V_{i}$.
Also, we say that the subdigraph induced by $V_{i}$ is terminal provided that for all $u\in V_{i}$ and $v\in V_{j}$, where $i\neq j$, the edge $(u,v)$ does not exist in $E$.

Let $\Gamma\in\mathbb{G}$ have order $n$ be polygonal.
Then, $\alpha(\Gamma)=0$ if and only if $\Gamma$ has multiple terminal strongly connected components.

As noted in the proof of Proposition <ref>, since $\Gamma$ is polygonal, $W_{r}(L)$ is a convex polygon whose vertices are eigenvalues of $Q^{*}LQ$, which are also eigenvalues of $L$.
Moreover, by Geršgorin's circle theorem (see for example [7]), the eigenvalues of $L$ are contained in the disk centered at $\max_{i\in V}d^{+}(i)$ with radius $\max_{i\in V}d^{+}(i)$.
Hence, $L$ cannot have purely imaginary eigenvalues, and it follows that $0$ is the minimum real part of $W_{r}(L)$ if and only if the origin of the complex plane is a corner of $W_{r}(L)$.
Therefore, Proposition <ref> (iv) and <cit.> imply that $\alpha(\Gamma)=0$ if and only if $0$ is an eigenvalue of $Q^{*}LQ$, that is, $0$ is an eigenvalue of $L$ with multiplicity greater than $1$.

non-poly-zero-alphay min=-1,y max=1,x min=-0.000001
A digraph with zero algebraic connectivity and one isolated strongly connected component.

Before proceeding, note that our definitions for algebraic connectivity, restricted numerical range, and polygonal digraphs, along with our results from Proposition <ref> (i)–(iv), Proposition <ref>, and Proposition <ref> hold for finite simple digraphs with positive weights.
Although, in this article, we focus on unweighted digraphs.

§ COMPUTING POLYGONAL DIGRAPHS

Let $\Gamma\in\mathbb{G}$ have order $n$ and let $L$ be the Laplacian matrix of $\Gamma$.
By Proposition <ref>, the restricted numerical range of $\Gamma$ can be computed as the numerical range of $Q^{*}LQ$, where $Q$ is a restrictor matrix of order $n$.
The computation of the numerical range of a general complex matrix $B$ is well-established in the literature and relies on the fact that since $W(B)$ is convex, as proved by Toeplitz and Hausdorff [5, 13], the boundary of $W(B)$ can be approximated by convex polygons determined by supporting lines of $W(B)$ [9, 10, 16].
Note that a supporting line of a curve is a line that contains a point on the curve but does not separate any two points on the curve.

§.§ Supporting Lines Check

Using Johnson's algorithm [9], we compute the restricted numerical range of a digraph $\Gamma\in\mathbb{G}$ by setting $B = Q^{*}LQ$, where $L$ is the Laplacian matrix of $\Gamma$ and $Q$ is a restrictor matrix of order $n$.
Once $W_{r}(L)$ is computed we can determine if $\Gamma$ is polygonal by checking whether $W_{r}(L)$ is equal to the convex hull of the eigenvalues of $B$, which we denote by $\conv{\sigma(B)}$.
In general, given a finite set $S$ contained in a real or complex vector space, the convex hull $\conv{S}$ is the set of all convex combinations of elements from $S$.
Alternatively, $\conv{S}$ can be characterized as the intersection of all convex sets containing $S$, so it is the smallest closed convex set containing $S$ [6].

If we are only interested in whether $W(B)=\conv{\sigma(B)}$, for a given $B\in\mathbb{C}^{n\times n}$, then we need not compute the numerical range $W(B)$.
Indeed, since $\conv{\sigma(B)}\subseteq W(B)$, it suffices to check that every edge of $\conv{\sigma(B)}$ is a supporting line of $W(B)$.
To this end, let $v_{1},\ldots,v_{k}$ denote the vertices of $\conv{\sigma(A)}$ ordered in the counter-clockwise direction.
Then, for each $j\in\{1,\ldots,k\}$, define the direction

\[
d_{j} = \frac{v_{j+1}-v_{j}}{\abs{v_{j+1}-v_{j}}}
\]

and note that the $j$th edge of $\conv{\sigma(B)}$ can be written as

\[
v_{j}v_{j+1} = \left\{v_{j} + td_{j}\colon 0\leq t\leq \abs{v_{j+1}-v_{j}} \right\},
\]

where it is assumed that $v_{k+1}=v_{1}$.

For each $j\in\{1,\ldots,k\}$, let $\theta_{j}\in[0,2\pi)$ be such that

\begin{equation}\label{eq:theta}
e^{\iu\theta_{j}} = \iu\cdot\conj{d_{j}},
\end{equation}

and define

\[
\hat{v}_{j} = e^{\iu\theta_{j}}v_{j}
\]

as the vertices of the rotated convex hull $\conv{\sigma\left(e^{\iu\theta_{j}}B\right)}$.
Based on how $\theta_{j}$ is defined, it is clear that the $j$th edge of this rotated convex hull,

\[
\hat{v}_{j}\hat{v}_{j+1} = \left\{e^{\iu\theta_{j}}v_{j} + te^{\iu\theta_{j}}d_{j}\colon 0\leq t\leq\abs{v_{j+1}-v_{j}}\right\},
\]

can be formed from the edge $v_{j}v_{j+1}$ by first rotating it to the real axis (pointing in the positive direction) and then rotating $90$ degrees in the counter-clockwise direction.
Hence, the edge $\hat{v}_{j}\hat{v}_{j+1}$ is a vertical line segment whose real part is equal to the maximum real part of $\conv{\sigma\left(e^{\iu\theta_{j}}B\right)}$.
If the edge $\hat{v}_{j}\hat{v}_{j+1}$ is also a supporting line of $W(e^{\iu\theta_{j}}B)$, then it follows that $\re{e^{\iu\theta_{j}}v_{j}}$ must equal the maximum real part of $W(e^{\iu\theta_{j}}B)$, which is well-known
(see for example [9]) to equal the maximum real eigenvalue of the Hermitian part of the matrix $e^{\iu\theta_{j}}B$.

Since $W(B)=\conv{\sigma(B)}$ if and only if $W(e^{\iu\theta}B)=\conv{\sigma\left(e^{\iu\theta}B\right)}$, for all $\theta\in[0,2\pi)$, the above discussion leads to an efficient algorithm for determining if a digraph $\Gamma\in\mathbb{G}$ is polygonal.
Indeed, see Algorithm <ref>, noting that $H(B) = \left(B+B^{*}\right)/2$ is the Hermitian part of the matrix $B$.

Algorithm to determine if $\Gamma$ is a polygonal digraph.

I. Let $B=Q^{*}LQ$, where $Q$ is a restrictor matrix of order $n$.
II. Let $v_{1},\ldots,v_{k},v_{k+1}$, where $v_{k+1}=v_{1}$, denote the vertices of $\conv{\sigma(B)}$.
III. Let $\epsilon$ be some pre-determined tolerance.
IV. If $k=1$, then there is only one real eigenvalue in the convex hull. Perform the following check:
$\lambda_{\textrm{max}}\left(H(B)\right) > \lambda_{\textrm{min}}\left(H(B)\right) + \epsilon$
Return False
Return True
V. If $k>1$, then perform the following checks:
Define $e^{\iu\theta_{j}}$ as in (<ref>)
$\lambda_{\textrm{max}}\left(H(e^{\iu\theta_{j}}B)\right) > \re{e^{\iu\theta_{j}}v_{j}} + \epsilon$
Return False
Return True

§.§ Survey of Polygonal Digraphs

Using the Nauty software [11], we are able to generate all non-isomorphic digraphs of order $n$.
For each digraph $\Gamma$, we can use Algorithm <ref> to determine if $\Gamma$ is polygonal.
We can further speed up this process by noting that Proposition <ref>(v) implies that $W_{r}(L)$ is a complex polygon if and only if $W_{r}(\conj{L})$ is a complex polygon.
Hence, to generate the set of polygonal digraphs, we only need to search through (about) half of the non-isomorphic digraphs of order $n$ and then add complements as necessary.
Code that implements this process in Python and C is available at <https://github.com/trcameron/polygonal-digraphs>.
After running this code, we identified $3,~9,~29,~97,~395,~2185,$ and $18930$ polygonal digraphs on $2,~3,~4,~5,~6,~7,$ and $8$ vertices, respectively.

Furthermore, the polygonal digraphs can be split into three classes.
In class 1, the Laplacian matrix is normal; we refer to these as normal digraphs.
It is worth noting that <cit.> implies that if $L$ is normal then $Q^{*}LQ$ is normal for any restrictor matrix $Q$ of order $n$.
In class 2, the Laplacian matrix is not normal but $Q^{*}LQ$ is normal; we refer to these as restricted-normal digraphs.
Finally, in class 3, neither the Laplacian matrix nor $Q^{*}LQ$ is normal but $W_{r}(L)$ is still a complex polygon; we refer to these as pseudo-normal digraphs.
Figure <ref> provides an example from each class.

/my/graphic options/tall preset

case1x min=0.3,y min=-1,y max=1

case2y min=-1,y max=1

Examples from each class of polygonal digraphs.

In Table <ref>, the number of polygonal digraphs in each class is shown for orders $n=2,\ldots,8$.
Not surprisingly, there are no pseudo-normal digraphs until $n\geq 6$.
Indeed, if $W(B)=\conv{\sigma(B)}$ for some $n\times n$ complex matrix $B$, where $n\leq 4$, then it is known that $B$ must be normal [8].
Since $Q^{*}LQ$ is a square matrix of size one less than the size of $L$, the above observation follows immediately.

n     Normal Digraphs     Restricted-Normal Digraphs     Pseudo-Normal Digraphs

2     2     1     0

3     5     4     0

4     15     14     0

5     47     50     0

6     214     179     2

7     1375     766     44

8     14182     4349     399

Number of polygonal digraphs in each class.

We conclude this section with Proposition <ref>, which shows that not only are polygonal digraphs, in general, closed under the digraph complement, but the individual classes are also closed under the digraph complement.

Let normal, restricted-normal, and pseudo-normal digraphs be referred to as class $1$, $2$, and $3$, respectively.
Also, let $\Gamma\in\mathbb{G}$ have order $n$.
Then, $\Gamma$ is in class $c\in\{1,2,3\}$ if and only if its complement $\conj{\Gamma}$ is in class $c$.

Let $\Gamma$ and $\conj{\Gamma}$ be complementary digraphs of order $n$ with Laplacian matrices $L$ and $\conj{L}$, respectively.
Note that

\[
\conj{L} = \left(n I - \mathbf{e}\mathbf{e}^{T}\right)-L.
\]

Clearly $\mathbf{e}$ is an eigenvector of both $L$ and $\conj{L}$ corresponding to the zero eigenvalue.
Furthermore, for any $\mathbf{v}$ that is orthogonal to $\mathbf{e}$, the eigenvalue-eigenvector equation $L\mathbf{v}=\lambda\mathbf{v}$ holds if and only if $\conj{L}\mathbf{v} = \left(n-\lambda\right)\mathbf{v}$ holds.
Therefore, by Grone <cit.>, $L$ is normal if and only if $\conj{L}$ is normal, which implies that $\Gamma$ is normal if and only if $\conj{\Gamma}$ is normal.

Now, let $Q$ be a restrictor matrix of order $n$.

\[
Q^{*}\conj{L}Q = n I - Q^{*}LQ.
\]

Hence, $Q^{*}LQ$ is normal if and only if $Q^{*}\conj{L}Q$ is normal, which implies that $\Gamma$ is restricted-normal if and only if $\conj{\Gamma}$ is restricted-normal.

Finally, by Proposition <ref>(v), it follows that $W_{r}(L)$ is a complex polygon if and only if $W_{r}\left(\conj{L}\right)$ is a complex polygon.
Therefore, $\Gamma$ is pseudo-normal if and only if $\conj{\Gamma}$ is pseudo-normal.

§ ANALYZING POLYGONAL DIGRAPHS

In this section, we analyze the structure of polygonal digraphs from the normal and restricted-normal classes.
In particular, we prove sufficient conditions for normal digraphs and show that the directed join of two normal digraphs results in a restricted-normal digraph.
Also, we prove that directed joins are the only restricted-normal digraphs when the order is square-free or twice a square-free number.
Finally, we provide a construction for restricted-normal digraphs that are not directed joins for all orders that are neither square-free nor twice a square-free number.

§.§ Normal Digraphs

It is easy enough to construct a normal digraph.
For instance, any dicycle will suffice as illustrated in Figure <ref>; more generally, any digraph whose Laplacian is a circulant matrix, possibly after re-ordering the vertices, will also suffice.
Consider, for example, the digraph in Figure <ref> whose plane embedding has $60^{\circ}$ rotational symmetry.
Given a certain ordering of the vertices, the Laplacian matrix $L$ can be written as a circulant matrix and is, therefore, normal.

circ-normaly min=-2,y max=2
A normal digraph with circulant Laplacian matrix.

Let $\Gamma=(V,E)\in\mathbb{G}$ be a normal digraph with Laplacian matrix $L$.
By <cit.>, we have

\[
\norm{\mathbf{e}^{T}L}  = \norm{L\mathbf{e}} = 0,
\]

which implies that the column sums of $L$ are all zero.
Hence $\Gamma$ must be balanced, that is, $d^{+}(i)=d^{-}(i)$ for all $i\in V$.
Figure <ref> shows a digraph that is balanced but does not have a normal Laplacian, which is evident from the shape of its restricted numerical range.

bal-non-normaly min=-1.7,y max=1.7
A balanced non-normal digraph.

Therefore, the balanced property is, not surprisingly, weaker than the normal property for digraphs.
Nevertheless, the restricted numerical range of balanced digraphs is extremely well behaved under certain operations as described in Proposition <ref>.
Note that the bidirectional join of digraphs $\Gamma=\left(V,E\right)$ and $\Gamma' = \left(V',E'\right)$, where $V\cap V'=\emptyset$, is defined by

\[
\Gamma\bdjoin\Gamma' = \left(V\sqcup V',E\sqcup E'\sqcup\left\{(i,j),~(j,i)\colon i\in V, j\in V'\right\}\right)
\]

and the disjoint union is defined by

\[
\Gamma\sqcup\Gamma' = \left(V\sqcup V',E\sqcup E'\right).
\]

Also, we use $I_{k}$ to denote the $k\times k$ identity matrix, and $J_{k_{1}\times k_{2}}$ to denote the $k_{1}\times k_{2}$ all ones matrix.

Let $\Gamma_{1},\Gamma_{2}\in\mathbb{G}$ be balanced digraphs of order $n_{1}$ and $n_{2}$, respectively.

* $W_{r}\left(\Gamma_{1}\sqcup\Gamma_{2}\right) = \conv{W_{r}(\Gamma_{1})\cup W_{r}(\Gamma_{2})\cup\{0\}}$

* $W_{r}\left(\Gamma_{1}\djoin\Gamma_{2}\right) =  \conv{\left(W_{r}(\Gamma_{1})+n_{2}\right)\cup W_{r}(\Gamma_{2})\cup\{n_{2}\}}$

* $W_{r}\left(\Gamma_{1}\bdjoin\Gamma_{2}\right) = \conv{\left(W_{r}(\Gamma_{1})+n_{2}\right)\cup\left(W_{r}(\Gamma_{2})+n_{1}\right)\cup\{n_{1}+n_{2}\}}.$

Let $L_{1}$ and $L_{2}$ denote the Laplacian matrix of $\Gamma_{1}$ and $\Gamma_{2}$, respectively.
Also, let $Q_{1}$ and $Q_{2}$ be restrictor matrices of order $n_{1}$ and $n_{2}$, respectively.
Finally, define

\[
Q = \begin{bmatrix} Q_{1} & 0 & -\frac{n_{2}}{\sqrt{n_{2}^{2}n_{1}+n_{1}^{2}n_{2}}}\mathbf{e}^{n_{1}} \\ 0 & Q_{2} & \frac{n_{1}}{\sqrt{n_{2}^{2}n_{1}+n_{1}^{2}n_{2}}}\mathbf{e}^{n_{2}} \end{bmatrix}
\]

as a restrictor matrix of order $n=n_{1}+n_{2}$.

* The Laplacian matrix of $\Gamma_{1}\sqcup\Gamma_{2}$, possibly after re-ordering the vertices, can be written as

\[
L = \begin{bmatrix} L_{1} & 0 \\ 0 & L_{2}\end{bmatrix}.
\]

Since both $\Gamma_{1}$ and $\Gamma_{2}$ are balanced, one can readily verify that

\[
Q^{*}LQ = \begin{bmatrix} Q_{1}^{*}L_{1}Q_{1} & 0 & 0 \\ 0 & Q_{2}^{*}L_{2}Q_{2} & 0 \\ 0 & 0 & 0\end{bmatrix}.
\]

Now, by <cit.> and Proposition <ref>(i), it follows that

\[
W_{r}(L) = \conv{W_{r}(L_{1})\cup W_{r}(L_{2})\cup\{0\}}.
\]

* The Laplacian matrix of $\Gamma_{1}\djoin\Gamma_{2}$, possibly after re-ordering the vertices, can be written as

\[
L = \begin{bmatrix} L_{1}+n_{2}I_{n_{1}}& -J_{n_{1}\times n_{2}} \\ 0 & L_{2}\end{bmatrix}.
\]

Since both $\Gamma_{1}$ and $\Gamma_{2}$ are balanced, one can readily verify that

\[
Q^{*}LQ = \begin{bmatrix} Q_{1}^{*}L_{1}Q_{1}+n_{2}I_{n_{1}-1} & 0 & 0 \\ 0 & Q_{2}^{*}L_{2}Q_{2} & 0 \\ 0 & 0 & n_{2}\end{bmatrix}.
\]

By <cit.> and Proposition <ref>, it follows that

\[
W_{r}(L) = \conv{\left(W_{r}(L_{1})+n_{2}\right)\cup W_{r}(L_{2})\cup\{n_{2}\}}.
\]

* The Laplacian matrix of $\Gamma_{1}\bdjoin\Gamma_{2}$, possibly after re-ordering the vertices, can be written as

\[
L = \begin{bmatrix} L_{1}+n_{2}I_{n_{1}} & -J_{n_{1}\times n_{2}} \\ -J_{n_{2}\times n_{1}} & L_{2}+n_{1}I_{n_{2}}\end{bmatrix}.
\]

Since both $\Gamma_{1}$ and $\Gamma_{2}$ are balanced, one can readily verify that

\[
Q^{*}LQ = \begin{bmatrix} Q_{1}^{*}L_{1}Q_{1} + n_{2}I_{n_{1}-1} & 0 & 0 \\ 0 & Q_{2}^{*}L_{2}Q_{2} + n_{1}I_{n_{2}-1} & 0 \\ 0 & 0 & n_{1}+n_{2}\end{bmatrix}.
\]

By <cit.> and Proposition <ref>, it follows that

\[
W_{r}(L) = \conv{\left(W_{r}(L_{1})+n_{2}\right)\cup\left(W_{r}(L_{2})+n_{1}\right)\cup\{n_{1}+n_{2}\}}.
\]

Clearly, Proposition <ref> holds for normal digraphs $\Gamma_{1}$ and $\Gamma_{2}$ since they are also balanced.
In this case, the proof of Proposition <ref> implies that $Q^{*}LQ$ is normal for each Laplacian matrix $L$ of $\Gamma_{1}\circ\Gamma_{2}$, where $\circ\in\{\sqcup,\djoin,\bdjoin\}$.
Since the disjoint union and bidirectional join of two balanced digraphs are also balanced, Theorem <ref> implies that $\Gamma_{1}\sqcup\Gamma_{2}$ and $\Gamma_{1}\bdjoin\Gamma_{2}$ are both normal.
Therefore, Proposition <ref> provides an easy way to construct normal digraphs from other normal digraphs in a way that the changes to the restricted numerical range are extremely well behaved.

Let $\Gamma\in\mathbb{G}$ have order $n$ and Laplacian matrix $L$.
Also, let $Q$ be a restrictor matrix of order $n$.
Then, $\Gamma$ is balanced if and only if $\mathbf{e}^{T}LQ=0$.

If $\Gamma$ is balanced, then $\mathbf{e}^{T}L=0$ and the result is trivial.
Conversely, suppose that $\mathbf{e}^{T}LQ=0$.
Let $\mathbf{q}_{1},\ldots,\mathbf{q}_{n-1}$ denote the columns of $Q$.
Since the entries of $\mathbf{e}^{T}L$ must sum to zero, it follows that $\mathbf{e}^{T}L$ is orthogonal to $\mathbf{e}$.
Hence, there exist scalars $c_{1},\ldots,c_{n-1}$ such that

\[
\mathbf{e}^{T}L = c_{1}\mathbf{q}_{1}^{T} + \cdots + c_{n-1}\mathbf{q}_{n-1}^{T}
\]

and it follows that

\[
\mathbf{e}^{T}LQ = \left[c_{1}^{2},\ldots,c_{n-1}^{2}\right]^{T}.
\]

Therefore, $\mathbf{e}^{T}LQ=0$ forces $c_{1}=\cdots=c_{n-1}=0$, that is, $\mathbf{e}^{T}L=0$, which implies that $\Gamma$ is balanced.

Let $\Gamma\in\mathbb{G}$ have order $n$ and Laplacian matrix $L$.
Also, let $Q$ be a restrictor matrix of order $n$.
Then, $L$ is normal if and only if $Q^{*}LQ$ is normal and $\Gamma$ is balanced.

Define $\hat{Q}$ to be the $n\times n$ orthonormal matrix whose first $(n-1)$ columns are equal to the columns of $Q$ and whose last column is equal to $\mathbf{e}/\sqrt{n}$.

\[
\hat{Q}^{*}L\hat{Q} = \begin{bmatrix} Q^{*}LQ & 0 \\ \frac{1}{\sqrt{n}}\mathbf{e}^{T}LQ & 0\end{bmatrix},
\]

which, by <cit.>, is normal if and only if $Q^{*}LQ$ is normal and $\mathbf{e}^{T}LQ = 0$.
By Lemma <ref>, $\mathbf{e}^{T}LQ=0$ if and only if $\Gamma$ is balanced.
Therefore, $\hat{Q}^{*}L\hat{Q}$ is normal if and only if $Q^{*}LQ$ is normal and $\Gamma$ is balanced.

We conclude this section by providing another method for constructing normal digraphs that cannot be described as a disjoint union or bidirectional join of two (non-null) normal digraphs.
To this end, consider the following result.

Let $\Gamma=(V,E)\in\mathbb{G}$ have order $n$ and adjacency matrix $A=[a_{ij}]_{i,j=1}^{n}$.
Then $\Gamma$ is normal if and only if $\Gamma$ is balanced and

\begin{equation}\label{eq:nrml-identity}
\left(a_{ij} - a_{ji}\right)\left(d^{+}(j)-d^{+}(i)\right) = \sum_{k\neq i,j}\left(a_{ik}a_{jk} - a_{ki}a_{kj}\right),
\end{equation}

for all $i\neq j\in V$.

Let $L$ be the Laplacian matrix of $\Gamma$.
By <cit.>, it follows that $L$ is normal if and only if

\[
\langle L\mathbf{e}_{i},L\mathbf{e}_{j}\rangle = \langle L^{T}\mathbf{e}_{i},L^{T}\mathbf{e}_{j}\rangle,
\]

for all $i,j\in V$, where $\mathbf{e}_{i}$ denotes the $i$th column of $I_{n}$.
Note that

\[
\langle L\mathbf{e}_{i},L\mathbf{e}_{j}\rangle
\begin{cases}
d^{+}(i)^{2} + d^{-}(i) & \text{if $i=j$,} \\
-d^{+}(i)a_{ij} - d^{+}(j)a_{ji} + \sum_{k\neq i,j}a_{ki}a_{kj} & \text{if $i\neq j$,}
\end{cases}
\]

\[
\langle L^{T}\mathbf{e}_{i},L^{T}\mathbf{e}_{j}\rangle
\begin{cases}
d^{+}(i)^{2} + d^{+}(i) & \text{if $i=j$,} \\
-d^{+}(i)a_{ji} - d^{+}(j)a_{ij} + \sum_{k\neq i,j}a_{ik}a_{jk} & \text{if $i\neq j$.}
\end{cases}
\]

Therefore, $L$ is normal if and only if $d^{+}(i)=d^{-}(i)$ for all $i\in V$ and

\[
\left(a_{ij}-a_{ji}\right)\left(d^{+}(j) - d^{+}(i)\right) = \sum_{k\neq i,j}\left(a_{ik}a_{jk}-a_{ki}a_{kj}\right),
\]

for all $i\neq j\in V$.

Given a graph $\Gamma = \left(V,E\right)$, we define the twin splitting of a vertex $v\in V$ as the process in which a copy of $v$ is created, denoted $v'$, such that $v$ and $v'$ are twins, that is, $(u,v)\in E$ if and only if $(u,v')\in E$ and $(v,u)\in E$ if and only if $(v',u)\in E$.
Note that the digraph in Figure <ref> can be constructed by performing a twin splitting on two non-adjacent vertices from a dicycle of order $4$.
It is worth emphasizing that altering the digraph in this way preserves the balanced property but destroys normality.
Indeed, let $i$ and $j$ be vertices in Figure <ref> such that $i$ points at $j$, $i$ has a twin, and $j$ does not have a twin.
It follows that the left side of (<ref>) is equal to $1$ and the right side of (<ref>) is equal to $0$, which confirms that the digraph in Figure <ref> is not normal.

It turns out that we can restore the normality of the digraph in Figure <ref> by adding a new vertex that is bidirectionally joined onto all the twin vertices, as in Figure <ref>.
This process is generalized in Theorem <ref>.

/my/graphic options/tall preset

Dicycle of Order 4

Twin Splitting

Restoring Normality

Twin splitting and restoration of normality.

Let $\Gamma=(V,E)\in\mathbb{G}$ be a dicycle of order $n\geq 4$, where $n$ is even.
Starting at any vertex in $V$, construct $\Gamma'$ by performing a twin splitting on every other vertex in the dicycle.
Also, let $\Gamma''$ be constructed from $\Gamma'$ by adding a new vertex that is bidirectionally joined to all the twin vertices in $\Gamma'$.
Then, $\Gamma'$ is a balanced digraph that is not normal and $\Gamma''$ is a normal digraph.

Let $\Gamma' = (V',E')$ and note that $\abs{V'} = 3n/2$, where $n$ vertices have twins and the other $n/2$ vertices don't have twins.
Consider the partition of the set of vertices

\[
V' = T\sqcup V'\setminus{T},
\]

where $T$ is the set of vertices with twins and $V'\setminus{T}$ is the set of vertices without twins.
Note that

\[
d_{\Gamma'}^{+}(i) = d_{\Gamma'}^{-}(i) = 1,
\]

for all $i\in T$ and

\[
d_{\Gamma'}^{+}(i) = d_{\Gamma'}^{-}(i) = 2,
\]

for all $i\in V'\setminus{T}$.
Therefore, the digraph $\Gamma'$ is clearly balanced.
Furthermore, for each vertex $i\in T$, there exists a vertex $j\in V'\setminus{T}$ such that $a_{ij}=1$ and $a_{ji}=0$, that is, vertex $i$ points at vertex $j$ and vertex $j$ does not point at vertex $i$.

\[
\left(a_{ij}-a_{ji}\right)\left(d^{+}(j)-d^{+}(i)\right) = 1.
\]

Since $i$ and $j$ don't point at any of the same vertices, and no vertex points at both $i$ and $j$, we have

\[
\sum_{k\neq i,j}\left(a_{ik}a_{jk} - a_{ki}a_{kj}\right) = 0,
\]

and it follows that (<ref>) does not hold; hence, $\Gamma'$ is not normal.

Now, let $\Gamma'' = (V'',E'')$ and consider the partition of the set of vertices

\[
V'' = T\sqcup V'\setminus{T}\sqcup\{v\},
\]

where $v$ is bidirectionally joined onto all vertices in $T$.

\[
d_{\Gamma''}^{+}(i) = d_{\Gamma''}^{-}(i) = 2,
\]

for all $i\in T\sqcup V'\setminus{T}$.

\[
d_{\Gamma''}^{+}(v) = d_{\Gamma''}^{-}(v) = \abs{T},
\]

and it follows that $\Gamma''$ is balanced.
It is also clear that (<ref>) holds for all $i\in T$ and $j\in V'\setminus{T}$ since those vertices have the same out-degree and $a_{ik}a_{jk}=a_{ki}a_{kj}=0$ for all $k\neq i,j$.

If $i,j\in T$, then the vertices have the same out-degree and there exists $k,k'\neq i,j$ such that $a_{ik}a_{jk}=1$ and $a_{k'i}a_{k'j}=1$.
Also, the vertex $v$ satisfies $a_{iv}a_{jv}=a_{vi}a_{vj}=1$, and for all other $k\neq i,j$, we have $a_{ik}=a_{jk}=a_{ki}a_{kj}=0$.
Hence, the terms on the right side of (<ref>) sum to zero.
A similar result holds for vertices $i,j\in V'\setminus{T}$ and for $j=v,i\neq v$.
Therefore, both sides of (<ref>) are equal to zero for all $i,j\in V$, and it follows that $\Gamma''$ is normal.

§.§ Restricted-Normal Digraphs

Let $\Gamma_{1}$ and $\Gamma_{2}$ be normal digraphs of order $n_{1}$ and $n_{2}$, respectively.
Then, from the proof of Proposition <ref>, it follows that $Q^{*}LQ$ is normal, where $L$ is the Laplacian matrix of $\Gamma_{1}\djoin\Gamma_{2}$ and $Q$ is a restrictor matrix of order $n=n_{1}+n_{2}$.
Moreover, by Theorem <ref>, it follows that $L$ is not normal since $\Gamma_{1}\djoin\Gamma_{2}$ is not balanced.
Therefore, the directed join of two normal digraphs results in a restricted-normal digraph as illustrated in Figure <ref>.
Moreover, by Proposition <ref>, the directed join of two normal digraphs is the only restricted-normal digraph that can be described by a directed join of two digraphs.

Let $\Gamma_{1},\Gamma_{2}\in\mathbb{G}$ have order $n_{1}$ and $n_{2}$, respectively.
Then, $\Gamma_{1}\djoin\Gamma_{2}$ is a restricted-normal digraph if and only if $\Gamma_{1}$ and $\Gamma_{2}$ are normal digraphs.

Let $L_{1}$ and $L_{2}$ denote the Laplacian matrix of $\Gamma_{1}$ and $\Gamma_{2}$, respectively.
Also, let $Q_{1}$ and $Q_{2}$ be restrictor matrices of order $n_{1}$ and $n_{2}$, respectively.
Finally, define

\[
Q = \begin{bmatrix} Q_{1} & 0 & -\frac{n_{2}}{\sqrt{n_{2}^{2}n_{1}+n_{1}^{2}n_{2}}}\mathbf{e}^{n_{1}} \\ 0 & Q_{2} & \frac{n_{1}}{\sqrt{n_{2}^{2}n_{1}+n_{1}^{2}n_{2}}}\mathbf{e}^{n_{2}} \end{bmatrix}
\]

as a restrictor matrix of order $n=n_{1}+n_{2}$.
The Laplacian matrix of $\Gamma_{1}\djoin\Gamma_{2}$, possibly after re-ordering the vertices, can be written as

\[
L = \begin{bmatrix} L_{1} + n_{2}I_{n_{1}} & -J_{n_{1}\times n_{2}} \\ 0 & L_{2} \end{bmatrix}.
\]

Now, one can readily verify that

\[
Q^{*}LQ = \begin{bmatrix}Q_{1}^{*}L_{1}Q_{1} + n_{2}I_{n_{1}-1} & 0 & 0 \\ 0 & Q_{2}^{*}L_{2}Q_{2} & 0 \\ \frac{-n_{2}}{\sqrt{n_{2}^{2}n_{1}+n_{1}^{2}n_{2}}}\left(\mathbf{e}^{n_{1}}\right)^{T}L_{1}Q_{1} & \frac{n_{1}}{\sqrt{n_{2}^{2}n_{1}+n_{1}^{2}n_{2}}}\left(\mathbf{e}^{n_{2}}\right)^{T}L_{2}Q_{2} & n_{2} \end{bmatrix}.
\]

By <cit.>, $Q^{*}LQ$ is normal if and only if $Q_{1}^{*}L_{1}Q_{1}$ and $Q_{2}^{*}L_{2}Q_{2}$ are normal and $\left(\mathbf{e}^{n_{1}}\right)^{T}L_{1}Q_{1}=0$ and $\left(\mathbf{e}^{n_{2}}\right)^{T}L_{2}Q_{2}=0$.
Furthermore, by Lemma <ref>, $\left(\mathbf{e}^{n_{1}}\right)^{T}L_{1}Q_{1}=0$ and $\left(\mathbf{e}^{n_{2}}\right)^{T}L_{2}Q_{2}=0$ if and only if $\Gamma_{1}$ and $\Gamma_{2}$ are balanced.
Thus, by Theorem <ref>, $Q^{*}LQ$ is normal if and only if $L_{1}$ and $L_{2}$ are normal.

Let $\Gamma = (V,E)\in\mathbb{G}$ have order $n$.
If $n$ is square-free or $n=2m$, where $m$ is square-free, it turns out that $\Gamma$ is restricted-normal if and only if it is a directed join.
To help understand this result, we define the imbalance of vertex $i\in V$ by

\[
\iota(i) = d^{+}(i) - d^{-}(i).
\]

Let $\Gamma=(V,E)\in\mathbb{G}$ be a digraph of order $n$ that is not balanced.
Then, $\Gamma$ is a directed join of two balanced digraphs if and only if

\begin{equation}\label{eq:imb-djoin}
\end{equation}

for all $i,j\in V$.

Suppose that $\Gamma=\Gamma_{1}\djoin\Gamma_{2}$, where $\Gamma_{1} = (V_{1},E_{1})$ and $\Gamma_{2} = (V_{2},E_{2})$ are balanced digraphs.
Then, the imbalance of vertex $i\in V=V_{1}\sqcup V_{2}$ satisfies

\[
\iota(i) = \begin{cases} \abs{V_{2}} & \text{if $i\in V_{1}$} \\ -\abs{V_{1}} & \text{if $i\in V_{2}$} \end{cases}.
\]

\[
\iota(i)-\iota(j) = \begin{cases}-n & \text{if $i\in V_{2}$ and $j\in V_{1}$} \\ 0 & \text{if $i,j\in V_{1}$ or $i,j\in V_{2}$} \\ n & \text{if $i\in V_{1}$ and $j\in V_{2}$} \end{cases},
\]

and it follows that $n\mid\left(\iota(i)-\iota(j)\right)$, for all $i,j\in V$.

Conversely, suppose that $n\mid(\left(\iota(i)-\iota(j)\right)$, for all $i,j\in V$.
Since $\abs{\iota(i)}\leq(n-1)$ for all $i\in V$, it follows that

\begin{equation}\label{eq:imb-djoin1}
\iota(i)-\iota(j)\in\{-n,0,n\},
\end{equation}

for all $i,j\in V$.
Since $\Gamma$ is not balanced and the sum of imbalances over all vertices is zero, there exists a vertex $u\in V$ such that $\iota(u)>0$ and there exists a vertex $v\in V$ such that $\iota(v)<0$.
Thus, (<ref>) implies that $\iota(u)-\iota(v)=n$, and we can partition the vertex set as $V=V_{1}\sqcup V_{2}$, where $\iota(i)=\iota(u)$ for all $i\in V_{1}$ and $\iota(i)=\iota(v)$ for all $i\in V_{2}$.
Summing imbalances, we have

\[
\iota(u)\abs{V_{1}} + \iota(v)\abs{V_{2}} = \iota(u)\abs{V_{1}} + (\iota(u)-n)\abs{V_{2}} = 0,
\]

which implies that $\iota(u)=\abs{V_{2}}$ and $(\iota(u)-n)=-\abs{V_{1}}$.

Note that the sum of the imbalances in $V_{2}$ is equal to the total out-degree minus the total in-degree of the vertices in $V_{2}$, which is also equal to the number of edges pointing from $V_{2}$ to $V_{1}$ minus the number of edges pointing from $V_{1}$ to $V_{2}$.
Since the sum of the imbalances in $V_{2}$ is equal to $-\abs{V_{1}}\abs{V_{2}}$, it follows that there are no edges pointing from $V_{2}$ to $V_{1}$ and there is an edge pointing from every vertex in $V_{1}$ to all vertices in $V_{2}$.
Hence, $\Gamma$ is a directed join of two digraphs: $\Gamma_{1} = (V_{1},E_{1})$ and $\Gamma_{2} = (V_{2},E_{2})$.
Finally, note that the imbalance of each vertex in $V$ would be zero if all edges pointing from $V_{1}$ to $V_{2}$ were removed; thus, $\Gamma_{1}$ and $\Gamma_{2}$ are balanced.

Lemma <ref> shows that directed joins of balanced digraphs can be identified by their vertex imbalances.
The connection between this result and restricted-normal digraphs will be made using the following propositions.
First, note that given a restrictor matrix $Q$ of order $n$, we denote

\begin{equation}\label{eq:projector}
P = QQ^{*} = I - \frac{1}{n}\mathbf{e}\mathbf{e}^{T}
\end{equation}

as the unique projector whose image space is $\mathbf{e}^{\perp}$ and kernel space is $\spn{\mathbf{e}}$.

Let $\Gamma=(V,E)\in\mathbb{G}$ have order $n$ and Laplacian matrix $L$.
Then, $Q^{*}LQ$ is normal if and only if $PL$ is normal.

Let $Q$ be a restrictor matrix of order $n$.
Then, by <cit.>, $Q^{*}LQ$ is normal if and only if

\begin{equation}\label{eq:nrml-proj-p1}
\langle Q^{*}LQ\mathbf{x},Q^{*}LQ\mathbf{y}\rangle = \langle Q^{*}L^{T}Q\mathbf{x},Q^{*}L^{T}Q\mathbf{y}\rangle,
\end{equation}

for all $\mathbf{x},\mathbf{y}\in\mathbb{C}^{n-1}$.
Since $Q$ is a bijection between $\mathbb{C}^{n-1}$ and $\mathbf{e}^{\perp}$, it follows that (<ref>) holds for all $\mathbf{x},\mathbf{y}\in\mathbb{C}^{n-1}$ if and only if

\begin{equation}\label{eq:nrml-proj-p2}
\langle Q^{*}L\mathbf{x},Q^{*}L\mathbf{y}\rangle = \langle Q^{*}L^{T}\mathbf{x},Q^{*}L^{T}\mathbf{y}\rangle,
\end{equation}

for all $\mathbf{x},\mathbf{y}\in\mathbf{e}^{\perp}$.
Using the projector $P$ from (<ref>), we can re-write (<ref>) as

\[
\langle PL\mathbf{x},L\mathbf{y}\rangle = \langle PL^{T}\mathbf{x},L^{T}\mathbf{y}\rangle.
\]

Furthermore, since the image space of $L^{T}$ is equal to $\mathbf{e}^{\perp}$, it follows that $Q^{*}LQ$ is normal if and only if

\begin{equation}\label{eq:nrml-proj-p3}
\langle PL\mathbf{x},L\mathbf{y}\rangle = \langle L^{T}\mathbf{x},L^{T}\mathbf{y}\rangle,
\end{equation}

for all $\mathbf{x},\mathbf{y}\in\mathbf{e}^{\perp}$.
Note that $\langle PL\mathbf{x},L\mathbf{y}\rangle = \langle PL\mathbf{x},PL\mathbf{y}\rangle$; hence, (<ref>) holds for all $\mathbf{x},\mathbf{y}\in\mathbf{e}^{\perp}$ if and only if

\[
\langle PL\mathbf{x},PL\mathbf{y}\rangle = \langle L^{T}P\mathbf{x},L^{T}P\mathbf{y}\rangle
\]

for all $\mathbf{x},\mathbf{y}\in\mathbb{C}^{n}$, that is, if and only if $PL$ is normal.

Let $\Gamma=(V,E)\in\mathbb{G}$ have order $n$ and Laplacian matrix $L$.
Then, for any $k\in V$, $\Gamma$ is restricted-normal if and only if $\Gamma$ is not balanced and

\begin{equation}\label{eq:rnrm-identity}
\frac{\left(\iota(i)-\iota(k)\right)\left(\iota(j)-\iota(k)\right)}{n} = \langle L(\mathbf{e}_{i}-\mathbf{e}_{k}),L(\mathbf{e}_{j}-\mathbf{e}_{k})\rangle -  \langle L^{T}(\mathbf{e}_{i}-\mathbf{e}_{k}),L^{T}(\mathbf{e}_{j}-\mathbf{e}_{k})\rangle,
\end{equation}

for all $i,j\in V\setminus{\{k\}}$.

Let $\left\{\mathbf{x}_{i}\right\}_{i\in\alpha}$ be a basis for $\mathbf{e}^{\perp}$, where $\alpha$ is an arbitrary index set of cardinality $(n-1)$.
Also, let $P$ be the projector from (<ref>).
Then, one can readily verify that (<ref>) implies that $Q^{*}LQ$ is normal if and only if

\[
\langle PL\mathbf{x}_{i},L\mathbf{x}_{j}\rangle = \langle L^{T}\mathbf{x}_{i},L^{T}\mathbf{x}_{j}\rangle,
\]

for all $i,j\in\alpha$.
Furthermore, the set $\left\{\mathbf{e}_{i}-\mathbf{e}_{k}\right\}_{i\in V\setminus{\{k\}}}$ clearly forms a basis for $\mathbf{e}^{\perp}$, which implies that $Q^{*}LQ$ is normal if and only if

\[
\langle PL(\mathbf{e}_{i}-\mathbf{e}_{k}),L(\mathbf{e}_{j}-\mathbf{e}_{k})\rangle = \langle L^{T}(\mathbf{e}_{i}-\mathbf{e}_{k}),L^{T}(\mathbf{e}_{j}-\mathbf{e}_{k})\rangle,
\]

for all $i,j\in V\setminus{\{k\}}$.
Since $P=I - \frac{1}{n}\mathbf{e}\mathbf{e}^{T}$, it follows that $Q^{*}LQ$ is normal if and only if (<ref>) holds, for all $i,j\in V\setminus{\{k\}}$.
By Theorem <ref>, $\Gamma$ is restricted-normal if and only if $\Gamma$ is not balanced and (<ref>) holds, for all $i,j\in V\setminus{\{k\}}$.

We are now ready to prove that if $n$ is square-free or $n=2m$, where $m$ is square-free, then the only restricted-normal digraphs are directed joins.

Let $\Gamma\in\mathbb{G}$ have order $n$, where $n$ is square-free or $n=2m$ with $m$ square-free.
If $\Gamma$ is a restricted-normal digraph, then $\Gamma$ is a directed join of normal digraphs.

Suppose that $\Gamma = (V,E)$ is restricted-normal and has Laplacian  matrix $L$.
Then, by Proposition <ref>, $\Gamma$ is not balanced and

\begin{equation}\label{eq:sqfree-rnrml1}
\frac{\left(\iota(i)-\iota(j)\right)^{2}}{n} = \norm{L(\mathbf{e}_{i}-\mathbf{e}_{j})}^{2} - \norm{L^{T}(\mathbf{e}_{i}-\mathbf{e}_{j})}^{2},
\end{equation}

for all $i,j\in V$.
Since the right side of (<ref>) is integer valued, we have $n\mid\left(\iota(i)-\iota(j)\right)^{2}$, for all $i,j\in V$.
Furthermore, if $n$ is square-free, then we have $n\mid\left(\iota(i)-\iota(j)\right)$, for all $i,j\in V$, and it follows from Lemma <ref> that $\Gamma$ is a directed join.
Moreover, since $\Gamma$ is restricted-normal, Proposition <ref> implies that $\Gamma$ is a directed join of normal digraphs.

Let $L=[l_{ij}]_{i,j=1}^{n}$ denote the Laplacian matrix of $\Gamma$.
Then, the right side of (<ref>) can be written as

\begin{align*}
\norm{L(\mathbf{e}_{i}-\mathbf{e}_{j})}^{2} - \norm{L^{T}(\mathbf{e}_{i}-\mathbf{e}_{j})}^{2} &= \sum_{k=1}^{n}\left(l_{ki}-l_{kj}\right)^{2} - \left(l_{ik}-l_{jk}\right)^{2} \\
&= \sum_{k=1}^{n}\left(l_{ki}^{2}-l_{ik}^{2}\right) + \left(l_{jk}^{2}-l_{kj}^{2}\right) - 2\left(l_{ki}l_{kj}-l_{ik}l_{jk}\right) \\
&=-\iota(i) - \iota(j) - 2\sum_{k=1}^{n}\left(l_{ki}l_{kj}-l_{ik}l_{jk}\right).
\end{align*}

Therefore, (<ref>) can be re-written as

\begin{equation}\label{eq:sqfree-rnrml2}
\frac{\left(\iota(i)-\iota(j)\right)^{2}}{n} = -\left(\iota(i)+\iota(j)\right) - 2\sum_{k=1}^{n}\left(l_{ki}l_{kj}-l_{ik}l_{jk}\right).
\end{equation}

Now, suppose that $n=2m$, where $m$ is square-free.

\[
2\mid n\mid\left(\iota(i)-\iota(j)\right)^{2},
\]

which implies that $2\mid\left(\iota(i)-\iota(j)\right)$.
Thus, we have $2\mid\left(\iota(i)+\iota(j)\right)$, and it follows that there exists an integer $s$ such that $2s=\left(\iota(i)+\iota(j)\right)$.
Therefore, we can re-write (<ref>) as

\[
\frac{\left(\iota(i)-\iota(j)\right)^{2}}{2m} = -2s - 2\sum_{k=1}^{n}\left(l_{ki}l_{kj}-l_{ik}l_{jk}\right),
\]

that is,

\[
\frac{\left(\iota(i)-\iota(j)\right)^{2}}{4m} = -s - \sum_{k=1}^{n}\left(l_{ki}l_{kj}-l_{ik}l_{jk}\right).
\]

Hence, $m\mid\left(\iota(i)-\iota(j)\right)^{2}/4$, which implies that $m\mid\left(\iota(i)-\iota(j)\right)/2$, that is, $n\mid\left(\iota(i)-\iota(j)\right)$.
Therefore, if $\Gamma$ is restricted-normal and $n=2m$, where $m$ is square-free, then $n\mid\left(\iota(i)-\iota(j)\right)$, for all $i,j\in V$, and Lemma <ref> implies that $\Gamma$ is a directed join.
Moreover, since $\Gamma$ is restricted-normal, Proposition <ref> implies that $\Gamma$ is a directed join of normal digraphs.

According to Theorem <ref>, $n=8$ is the smallest possible order for which there could exist restricted-normal digraphs that are not directed joins.
In fact, $48$ of the $4349$ restricted-normal digraphs of order $8$ (see Table <ref>) are not directed joins.
For example, consider the digraph in Figure <ref>, which is clearly not a directed join based on the imbalances of its vertices, Proposition <ref>, and Lemma <ref>.

rnrml-non-djoiny min=-1.3,y max=1.3
A restricted-normal digraph of order $8$ that is not a directed join.

In what follows, we provide a construction for restricted-normal digraphs, where the order is neither square-free nor twice a square-free number, that are not directed joins.
To this end, we make use of the following lemma which shows that restricted-normal digraphs have Laplacian matrices with a particular left-eigenvector structure.

Let $\Gamma\in\mathbb{G}$ have order $n$ and Laplacian matrix $L$.
Then, $\Gamma$ is a restricted-normal digraph if and only if $\Gamma$ is not balanced and there exist orthogonal eigenvectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n-1}\in\mathbf{e}^{\perp}$ for $L^{T}$.

Let $P$ be the projector from (<ref>).
By Theorem <ref> and Proposition <ref>, $\Gamma$ is restricted-normal if and only if $\Gamma$ is not balanced and $PL$ is normal.
Furthermore, by <cit.>, $PL$ is normal if and only if there exists orthogonal eigenvectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n-1},\mathbf{u}_{n}\in\mathbb{C}^{n}$ for $L^{T}P$.
Without loss of generality, we assume that $\mathbf{u}_{n}=\mathbf{e}$.
Hence, $\mathbf{u}_{1},\ldots,\mathbf{u}_{n-1}\in\mathbf{e}^{\perp}$ are orthogonal eigenvectors of $L^{T}$, and the result follows.

Next, we provide a construction for restricted-normal digraphs of order $n^{2}$, where $n\geq 3$, that are not directed joins.
Note that we use $J_{k}$ to denote the $k\times k$ all ones matrix.

Let $\Gamma\in\mathbb{G}$ have order $n^{2}$, where $n\geq 3$, and adjacency matrix

\[
A = \begin{bmatrix} & I_{n} & \cdots & I_{n} \\ J_{n}-I_{n} & & & \\ \vdots & & & \\ J_{n}-I_{n} \end{bmatrix},
\]

where all blank entries are zero.
Then, $\Gamma$ is a restricted-normal digraph that is not a directed join.

Note that the Laplacian matrix of $\Gamma$ is equal to

\[
L = (n-1)I_{n^{2}} - A.
\]

Let $\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\in\mathbb{C}^{n}$ satisfy

\[
\left(J_{n}-I_{n}\right)\mathbf{x}_{1} = \mathbf{e}^{n}
\mathbf{x}_{2}+\cdots+\mathbf{x}_{n}=\mathbf{e}^{n}.
\]

Then, the vector $\mathbf{x} = \left[\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\right]^{T}$ satisfies $A\mathbf{x} = \mathbf{e}^{n^{2}}$.
Hence, every vector in the null space of $A^{T}$ is orthogonal to $\mathbf{e}^{n^{2}}$.
Furthermore, the nullity of $A^{T}$ is equal to $n(n-2)$, which implies the existence of $n(n-2)$ orthogonal eigenvectors for $L^{T}$, corresponding to the eigenvalue $(n-1)$, that are perpendicular to $\mathbf{e}^{n^{2}}$.

Now, let $\mathbf{x}_{1},\ldots,\mathbf{x}_{n}\in\mathbb{C}^{n}$ be selected so that $\mathbf{x} = \left[\mathbf{x}_{1},\cdots,\mathbf{x}_{n}\right]^{T}$ is an eigenvector for $A^{T}$ corresponding to a non-zero eigenvalue $\lambda$.

\begin{equation}\label{eq:rnrm-ndjoin1}
A^{T}\mathbf{x} =
\begin{bmatrix} (J_{n}-I_{n})\mathbf{x}_{2} + \cdots + (J_{n}-I_{n})\mathbf{x}_{n} \\ \mathbf{x}_{1} \\ \vdots \\ \mathbf{x}_{1} \end{bmatrix}
\lambda
\begin{bmatrix} \mathbf{x}_{1} \\ \mathbf{x}_{2} \\ \vdots \\ \mathbf{x}_{n} \end{bmatrix},
\end{equation}

which implies that $\mathbf{x}_{2}=\cdots=\mathbf{x}_{n} = \lambda^{-1}\mathbf{x}_{1}$ and

\begin{equation}\label{eq:rnrm-ndjoin2}
(J_{n}-I_{n})\mathbf{x}_{1} = \frac{\lambda^{2}}{n-1}\mathbf{x}_{1}.
\end{equation}

Hence, $\mathbf{x}_{1}$ is an eigenvector of $(J_{n}-I_{n})$.

Note that $(J_{n}-I_{n})$ is a symmetric matrix with eigenvalues

\[
\lambda_{1}=(n-1),\lambda_{2}=-1,\ldots,\lambda_{n}=-1
\]

and corresponding orthogonal eigenvectors that we denote by $\mathbf{v}_{1},\ldots,\mathbf{v}_{n}$.
Also, (<ref>) and (<ref>) imply that

\[
\mu_{2k-1}=+\sqrt{(n-1)\lambda_{k}},~\mu_{2k}=-\sqrt{(n-1)\lambda_{k}}
\]

are eigenvalues of $A^{T}$ with corresponding orthogonal eigenvectors

\[
\mathbf{u}_{2k-1} = \begin{bmatrix}\mu_{2k-1}\mathbf{v}_{k} \\ \mathbf{v}_{k} \\ \vdots \\ \mathbf{v}_{k} \end{bmatrix},
~\mathbf{u}_{2k} = \begin{bmatrix}\mu_{2k}\mathbf{v}_{k} \\ \mathbf{v}_{k} \\ \vdots \\ \mathbf{v}_{k} \end{bmatrix},
\]

for $k=1,2,\ldots,n$.

Since $\mathbf{v}_{1}$ is a constant multiple of $\mathbf{e}^{n}$, it follows that $\mathbf{u}_{2},\ldots,\mathbf{u}_{2n}$ are perpendicular to $\mathbf{e}^{n^{2}}$.
Furthermore, $\mathbf{u}_{2},\ldots,\mathbf{u}_{2n}$ are in the column space of $A$, so these vectors are orthogonal to every null vector of $A^{T}$.
Therefore, there are $n^{2}-1$ orthogonal eigenvectors of $L^{T}$ that are perpendicular to $\mathbf{e}^{n^{2}}$, and Lemma <ref> implies that $\Gamma$ is restricted-normal.
Furthermore, since $\Gamma$ is clearly not balanced and its imbalances don't satisfy (<ref>), Proposition <ref> and Lemma <ref> imply that $\Gamma$ is not a directed join.

Next, we use the Kronecker product to construct new restricted-normal digraphs of order $nk$, where $k\geq 1$, from old restricted-normal digraphs of order $n$.

Let $\Gamma=(V,E)\in\mathbb{G}$ be a restricted-normal digraph of order $n$ with adjacency matrix $A$.
For $k\geq 1$, the digraph $\hat{\Gamma}=(\hat{V},\hat{E})\in\mathbb{G}$ associated with the adjacency matrix $A\otimes J_{k}$ is a restricted-normal digraph of order $nk$.
Furthermore, $\hat{\Gamma}$ is a directed join if and only if $\Gamma$ is a directed join.

Note that the Laplacian matrix of $\Gamma$ can be written as $L = D - A$, where $D=\diag\left(d^{+}(1),\ldots,d^{+}(n)\right)$.
Also, the vertex set of $\hat{\Gamma}$ can be written as $\hat{V} = \left\{i_{j}\colon~i\in V,~j=1,\ldots,k\right\}$ and the Laplacian matrix of $\hat{\Gamma}$ is equal to

\[
\hat{L} = k\left(D\otimes I_{k}\right) - \left(A\otimes J_{k}\right).
\]

Since the imbalance of vertex $i_{j}\in\hat{V}$ is equal to the corresponding column sum of $\hat{L}$, we have

\begin{equation}\label{eq:rnrm-tprod1}
\iota_{\hat{\Gamma}}(i_{j}) = kd_{\Gamma}^{+}(i) - kd_{\Gamma}^{-}(i) = k\cdot\iota_{\Gamma}(i),
\end{equation}

for all $i\in V$ and $j=1,\ldots,k$.

Now, since $\Gamma$ is a restricted-normal digraph, Lemma <ref> implies that there exist orthogonal eigenvectors $\mathbf{u}_{1},\ldots,\mathbf{u}_{n-1}$ for $L^{T}$ that are perpendicular to $\mathbf{e}^{n}$.
Therefore, for $i=1,\ldots,n-1$, we have

\begin{align*}
\hat{L}^{T}\left(\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right) &= k\left(D^{T}\otimes I_{k}\right)\left(\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right) - \left(A^{T}\otimes J_{k}\right)\left(\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right) \\
&= k\left(D^{T}\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right) - k\left(A^{T}\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right) \\
&= k\left(L^{T}\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right) \\
\end{align*}

where $\lambda_{i}$ is the eigenvalue of $L^{T}$ corresponding to the eigenvector $\mathbf{u}_{i}$.
It follows from the mixed-product property of Kronecker producst that the eigenvectors $\left(\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right)$ are orthogonal, for $i=1,\ldots,n-1$, and are perpendicular to $\mathbf{e}^{nk}=\left(\mathbf{e}^{n}\otimes\mathbf{e}^{k}\right)$.

Next, let $\mathbf{v}_{1},\ldots,\mathbf{v}_{k-1}$ denote the orthogonal eigenvectors of $J_{k}$ corresponding to the zero eigenvalue.
Also, let $\mathbf{e}_{1},\ldots,\mathbf{e}_{n}$ denote the column vectors of $I_{n}$, which are eigenvectors of $D^{T}$ corresponding to the eigenvalues $d^{+}(1),\ldots,d^{+}(n)$, respectively.
Then, for $i'=1,\ldots,n$ and $j=1,\ldots,k-1$, we have

\begin{align*}
\hat{L}^{T}\left(\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right) &= k\left(D^{T}\otimes I_{k}\right)\left(\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right) - \left(A^{T}\otimes J_{k}\right)\left(\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right) \\
&= k\left(D^{T}\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right) - \left(A^{T}\mathbf{e}_{i'}\otimes J_{k}\mathbf{v}_{j}\right) \\
&=k\left(d^{+}(i')\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right) - \left(A^{T}\mathbf{e}_{i'}\otimes 0\right) \\
&= kd^{+}(i')\left(\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right).
\end{align*}

Again, by the mixed-product property of Kronecker products, it follows that the eigenvectors $\left(\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right)$ are orthogonal, for $i'=1,\ldots,n$ and $j-1,\ldots,k-1$, and are perpendicular to $\mathbf{e}^{nk}$.
Moreover, since $\mathbf{v}_{1},\ldots,\mathbf{v}_{k-1}$ are perpendicular to $\mathbf{e}^{k}$, it follows that the eigenvectors

\[
\left(\mathbf{u}_{i}\otimes\mathbf{e}^{k}\right),~\left(\mathbf{e}_{i'}\otimes\mathbf{v}_{j}\right)
\]

are orthogonal, for $i=1,\ldots,n-1$, $i'=1,\ldots,n$, and $j=1,\ldots,k-1$.

Therefore, there are $nk-1$ orthogonal eigenvectors of $\hat{L}^{T}$ that are perpendicular to $\mathbf{e}^{nk}$, and Lemma <ref> implies that $\hat{\Gamma}$ is restricted-normal.
Furthermore, by (<ref>), Proposition <ref>, and Lemma <ref>, $\Gamma$ is a directed join if and only if $\hat{\Gamma}$ is a directed join.

We conclude this section by noting that the digraph in Figure <ref> along with Theorems <ref>,  <ref>, and <ref> imply that there exist restricted-normal digraphs that are not directed joins if and only if the order is neither square-free nor twice a square-free number.
Indeed, the natural numbers can be partitioned into square-free and non-square-free numbers.
Furthermore, the non-square-free numbers can be partitioned into the forms $kn^{2}$ and $4k$, where $n\geq 3$ and $k\geq 1$ is square-free.
Note that every number of the form $4k$ can be written as $8$ times an odd square-free number or twice an even square-free number.
All restricted-normal digraphs with an order that is square-free or twice a square-free number are directed joins by Theorem <ref>.
For all other possible orders a restricted-normal
digraph that is not a directed join can be constructed
either by using
Theorem <ref> and Theorem <ref>, in the case
of order $kn^{2}$ with $n\geq 3$ and $k\geq 1$ square-free, or by using
Figure <ref> and Theorem <ref>,
in the case of order $8k$ where $k\geq 1$ is an odd square-free number.

§ CONCLUSION

The restricted numerical range is a novel tool for characterizing digraphs and studying their algebraic connectivity.
In [2], digraphs with a restricted numerical range as a degenerate polygon, that is, a point or a line segment, are completely  described.
In this article, we extended these results to include digraphs whose restricted numerical range is a non-degenerate convex polygon in the complex plane.
We refer to digraphs whose restricted numerical range is a degenerate or non-degenerate convex polygon in the complex plane as polygonal.

In Section <ref>, we gave computational methods for finding polygonal digraphs, and showed that these digraphs can be partitioned into three classes: normal, restricted-normal, and pseudo-normal digraphs, all of which are closed under the digraph complement.
In Section <ref>, we noted that normal digraphs include any digraph whose Laplacian matrix can be written as a circulant matrix.
Moreover, Proposition <ref> and Theorem <ref> show that both the disjoint union and the bidirectional join of two normal digraphs results in another normal digraph.
Also, Theorem <ref> provides a method for constructing normal digraphs that cannot be described as the disjoint union or bidirectional join of two (non-null) normal digraphs.

Proposition <ref> and Theorem <ref> also show that the directed join of two normal digraphs results in a restricted-normal digraph.
Moreover, Theorem <ref> shows that when the order is square-free or twice a square-free number, the only restricted-normal digraphs are directed joins of two normal digraphs.
Finally, Figure <ref> along with Theorems <ref> and <ref> provide a construction for restricted-normal digraphs that are not directed joins when the order is neither square-free nor twice a square-free number.

Future research includes further investigation of the subclass of restricted-normal digraphs that are not directed joins and the class of pseudo-normal digraphs.

[1]
M. M. Asadi, M. Khosravi, A. G. Aghdam, and S. Blouin, Generalized algebraic connectivity for asymmetric networks, in 2016 American
Control Conference (ACC), 2016, pp. 5531–5536.

[2]
T. R. Cameron, M. D. Robertson, and A. Wiedemann, On the restricted
numerical range of the laplacian matrix for digraphs, Linear Multilinear
Algebra, 69 (2020), pp. 840–854.

[3]
M. Fiedler, Algebraic connectivity of graphs, Czechoslovak Mathematical Journal, 23 (1973), pp. 298-305.

[4]
R. Grone, C. R. Johnson, E. M. Sa, and H. Wolkowicz, Normal
matrices, Linear Alg. Appl., 87 (1987), pp. 213–225.

[5]
F. Hausdorff, Wertvorrat einer bilinearform, Math Z., 3 (1919),
pp. 314–316.

[6]
R. A. Horn and C. R. Johnson, Topics in Matrix Analysis, Cambridge
University Press, New York, NY, 1991.

[7]
R. A. Horn and C. R. Johnson, Matrix Analysis, Cambridge
University Press, New York, NY, 2nd ed., 2013.

[8]
C. R. Johnson, Normality and the numerical range, Linear Algebra
Appl., 15 (1976), pp. 89–94.

[9]
C. R. Johnson, Numerical determination of the field of values of a
complex matrix, SIAM J. Num. Analysis, 15 (1978), pp. 595–602.

[10]
R. Kippenhahn, Über den wertevorrat einer matrix, Math. Nachr.,
6 (1951), pp. 193–228.

[11]
B. D. McKay and A. Piperno, Practical Graph Isomorphism, II, J.
Symbolic Computation, 60 (2013), pp. 94–112.

[12]
I. Mirzaev and J. Gunawardena, Laplacian dynamics on general graphs, Bull. Math. Biol., 75 (2013), pp. 2118–2149.

[13]
O. Toeplitz, Das algebraische analogon zu einern satze von
fejér, Math Z., 2 (1918), pp. 187–197.

[14]
C. W. Wu, Algebraic connectivity of directed graphs, Linear
Multilinear Algebra, 53 (2005), pp. 203–223.

[15]
C. W. Wu, On a matrix inequality and its application to the
synchronization in coupled chaotic systems, in Complex Computing-Networks,
İ. C. Göknar and L. Sevgi (eds.), Springer-Verlag, Berlin,
Heidelberg, 2006, pp. 279–287.

[16]
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 [10].