ISSN 1855-3966 (printed edn.), ISSN 1855-3974 (electronic edn.)
ARS MATHEMATICA CONTEMPORANEA 24 (2024) #P3.10
https://doi.org/10.26493/1855-3974.3227.fd5
(Also available at http://amc-journal.eu)
Spectra of signed graphs and
related oriented graphs
Zoran Stanić *
Faculty of Mathematics, University of Belgrade,
Studentski trg 16, 11 000 Belgrade, Serbia
Received 14 September 2023, accepted 23 April 2024, published online 6 September 2024
Abstract
For every oriented graph G′, there exists a bipartite signed graph Ḣ such that the spec-
trum of Ḣ contains the full information about the spectrum of the skew adjacency ma-
trix of G′. This allows us to transfer some problems concerning the skew eigenvalues of
oriented graphs to the framework of signed graphs, where the theory of real symmetric
matrices can be employed. In this paper, we continue the previous research by relating
the characteristic polynomials, eigenspaces and the energy of G′ to those of Ḣ . Simul-
taneously, we address some open problems concerning the skew eigenvalues of oriented
graphs.
Keywords: Oriented graph, signed graph, eigenvalues, characteristic polynomial, eigenspaces, en-
ergy.
Math. Subj. Class. (2020): 05C20, 05C22, 05C50
1 Introduction
For a finite simple undirected graph G = (V,E), an oriented graph G′ is a pair (G, σ′),
where σ′ is the edge orientation satisfying σ′(ij) ∈ {i, j}, for every ij ∈ E. Similarly, a
signed graph Ġ is a pair (G, σ̇), where σ̇ is the edge signature satisfying σ̇(ij) ∈ {+1,−1},
for every ij ∈ E. In both cases, G is referred to as the underlying graph. The order n is the
number of vertices of G. The edge set of G′ consists of oriented edges, where the edge ij
is oriented from i to j if σ′(ij) = j; this is designated by i → j (or j ← i). The edge set
of Ġ consists of positive and negative edges.
*The research is supported by the Science Fund of the Republic of Serbia; grant number 7749676: Spectrally
Constrained Signed Graphs with Applications in Coding Theory and Control Theory – SCSG-ctct.
E-mail address: zstanic@matf.bg.ac.rs (Zoran Stanić)
cb This work is licensed under https://creativecommons.org/licenses/by/4.0/
2 Ars Math. Contemp. 24 (2024) #P3.10
The skew adjacency matrix SG′ = (sij) of G′ is the n × n matrix such that sij = 0
if ij is not an edge of G′, sij = 1 if i → j, and sij = −1 otherwise. This matrix
is skew symmetric and differs from the adjacency matrix of G′ whose (i, j)-entry is 0
whenever i ← j. The characteristic polynomial, the eigenvalues and the spectrum of SG′
are known as the skew characteristic polynomial, the skew eigenvalues, the skew spectrum
of G′, respectively. To easy language and be consistent with the forthcoming terminology
for signed graphs, in this article we omit the prefix ‘skew’. The spectrum of G′ consists
of purely imaginary numbers, the non-zero eigenvalues come as complex conjugates, and
thus the rank of SG′ is even. Also, S
⊺
G′SG′ = −S2G′ .
The adjacency matrix AĠ of Ġ is obtained from the standard (0, 1)-adjacency matrix
of G by reversing the sign of all edges mapped to −1 by σ̇. By the characteristic poly-
nomial, the eigenvalues and the spectrum of Ġ we mean the characteristic polynomial, the
eigenvalues and the spectrum of AĠ, respectively. Since AĠ is symmetric, its eigenvalues
are real.
An r-cube or a hypercube Qr is the r-regular graph of order 2r with vertex set {0, 1}r
(all possible binary r-tuples) in which two vertices are adjacent if and only if they differ
in exactly one coordinate. Accordingly, an oriented (resp. signed) r-cube is an oriented
(signed) graph underlined by Qr. If Γ is either an oriented graph or a signed graph, then its
energy E(Γ) is the sum of modulus of its eigenvalues.
It follows from [19] that every oriented graph G′ is related to a bipartite signed graph Ḣ
in such a way that the spectrum of Ḣ contains the full information about the spectrum of G′.
All necessary details about this relation are given in the next section. This means that the
theory of spectra of oriented graphs is strongly connected to the theory of spectra of signed
graphs, and that many problems concerning spectral parameters of oriented graphs can be
transferred to the framework of signed graphs, where the entire theory of real symmetric
matrices can be employed. In this way, some known results on oriented graphs are proved
in an elementary way [19], some open problems are resolved [15] and some known results
concerning signed graphs are transferred to the context of oriented graphs [18].
In this article we continue the research by expressing the coefficients of the character-
istic polynomial of G′ in terms of the coefficients of the characteristic polynomial of Ḣ .
We also generate the eigenspaces of G′ on the basis of the eigenvectors of Ḣ and relate
the energies of both graphs. The results on characteristic polynomials and energies are of
particular interest since they address some open problems posed in literature. The results
on eigenspaces are followed by an immediate application in the engineering domain.
Section 2 contains additional terminology and notation, along with a short review of re-
sults of [19]. In particular, oriented graphs are related to signed graphs in the forthcoming
Theorem 2.1. Some comments and results that arise directly from this theorem are given
in Section 3. Characteristic polynomials, eigenspaces and energies are considered in Sec-
tions 4–6, respectively. Some notes on particular (oriented or signed) hypercubes are given
in Section 7.
2 Preliminaries
We say that an oriented or a signed graph is connected, regular, or bipartite if the same
holds for its underlying graph. Similarly, a matching (or a perfect matching) refers to the
matching in the underlying graph.
Two oriented (resp. signed) graphs with the same underlying graph are switching equiv-
Z. Stanić: Spectra of signed graphs and related oriented graphs 3
alent if there is a subset U of the vertex set V , such that one of them is obtained by reversing
the orientation (sign) of every edge located between U and V \ U . In matrix terminology,
G′1 and G
′
2 are switching equivalent if there exists a diagonal matrix S with±1 on the main
diagonal, such that SG′2 = S
−1SG′1S, and similarly for signed graphs. S is referred to as
the switching matrix. Observe that the spectrum remains unchanged under the switching
operation.
We say that an oriented even cycle C ′2ℓ is oriented uniformly if by traversing along the
cycle we pass through an odd (resp. even) number of edges oriented in the route direction
for ℓ odd (even), where the ‘route direction’ refers to any of two possible directions: clock-
wise or counterclockwise. A canonical orientation in a bipartite graph G is the orientation
which orients all the edges from one colour class to the other. Clearly, in this orientation
every cycle is oriented uniformly.
A cycle Ċ in a signed graph is positive if the product of its edge signs σ̇(Ċ) is 1.
Otherwise, it is negative. A signed graph is said to be homogeneous if all edges have the
same sign, e.g., if its edge set is empty. It is balanced if it switches to its underlying graph;
equivalently, it does not contain negative cycles. The negation −Ġ of a signed graph is
obtained by reversing the sign of every edge of Ġ. Observe that if Ġ is bipartite, then it is
switching equivalent to −Ġ and they share the same spectrum.
We proceed with results of [19]. The signature σ̇ is associated with the orientation σ′
(and also Ġ is associated with G′) if
σ̇(ik)σ̇(jk) = siksjk holds for every pair of edges ik and jk. (2.1)
Being associated is a symmetric relation. We write σ̇ ∼ σ′ to indicate that σ̇ and σ′ are
mutually associated. The following results hold: If σ̇ ∼ σ′, then −S2G′ = A2Ġ. For a
graph G and an orientation σ′, there exists a signature σ̇ associated with σ′ if and only if G
is bipartite.
The next result gives a crucial relation between the spectrum of an oriented graph and
the spectrum of a related signed graph. If G′ is an oriented graph, then its bipartite dou-
ble bd(G′) is the oriented graph whose skew adjacency matrix is the Kronecker product
Sbd(G′) = AK2 ⊗ SG′ , where K2 is the complete graph with 2 vertices. This defini-
tion extends the definition of a bipartite double of an ordinary graph, where bd(G) has
Abd(G) = AK2 ⊗ AG as the adjacency matrix. Evidently, if G underlies G′, then bd(G)
underlies bd(G′). In our notation, exponents denote multiplicities of the eigenvalues.
Theorem 2.1. Let G′ = (G, σ′) be an oriented graph with rank(SG′) = 2k. The following
statements hold true:
(i) If G′ is bipartite and σ̇ ∼ σ′, then ±iλ1,±iλ2, . . . ,±iλk, 0(n−2k) are the eigen-
values of G′ if and only if ±λ1,±λ2, . . . ,±λk, 0(n−2k) are the eigenvalues of Ġ =
(G, σ̇).
(ii) If G′ is non-bipartite, H ′ = (bd(G), σ′′) is a bipartite double of G′ and σ̇ ∼
σ′′, then ±iλ1,±iλ2, . . . ,±iλk, 0(n−2k) are the eigenvalues of G′ if and only if
(±λ1)(2), (±λ2)(2), . . . , (±λk)(2), 0(2n−4k) are the eigenvalues of Ḣ = (bd(G), σ̇).
Therefore, G′ is related to a bipartite signed graph whose spectrum gives the full infor-
mation on the spectrum of G′. If G′ is bipartite, a required signed graph is its associate.
If G′ is non-bipartite, then a required signed graph is associated with bd(G′). One may
4 Ars Math. Contemp. 24 (2024) #P3.10
Figure 1: An infinite family of oriented graphs G′ and signed graphs Ġ such that −S2G′ =
A2
Ġ
. Negative edges are dashed.
notice that item (ii) of the previous theorem covers the bipartite case in the sense that, if G′
is bipartite, then bd(G′) consists of two copies of G′ and Ḣ also has two identical copies,
each associated with G′. However, this would lead to unnecessary complicating, as there
is no need to deal with a bipartite double if G′ is already bipartite. Thus, the bipartite case
is separated in item (i) of the same theorem.
3 Comments to Theorem 2.1
In the bipartite case, G′ is associated with Ġ if and only if it is associated with −Ġ.
Hence, G′ actually has two associates (with the same spectrum). Similarly, Ġ is associ-
ated with G′ if and only if it is associated with the oriented graph obtained by reversing the
orientation of every edge of G′. Again, Ġ has two associates which share the same spec-
trum. Henceforth, when we say ‘let Ġ be a signed graph associated with G′’ (or something
similar), we always mean that Ġ is allowed to take any of the two options (that differ up to
negation).
We have pointed out in the previous section that−S2G′ = A2Ġ holds whenever G
′ and Ġ
are associated. However, this identity is not exclusively reserved for associated graphs. For
example, Figure 1 illustrates infinite families of graphs that are not mutually associated
in the sense of the equality (2.1) (since they are non-bipartite), but satisfy the previous
matrix identity. In this case, they share the same underlying graph, but the identity can
occur even if they do not. In fact, the identity occurs if and only if for every pair i, j of
vertices, −s(2)ij = a
(2)
ij holds, where an exponent indicates that we deal with the entry of
matrix square. This leads to the following result.
Theorem 3.1. If an oriented graph G′ and a signed graph Ġ are defined on the same vertex
set, then −S2G′ = A2Ġ holds if and only if for every pair of vertices i, j∣∣{k : (i→ k∧j → k)∨(i← k∧j ← k)}∣∣−∣∣{k : (i→ k∧j ← k)∨(i← k∧j → k)}∣∣
in G′ is equal to ∣∣{k : σ̇(ik)σ̇(jk) = 1}∣∣− ∣∣{k : σ̇(ik)σ̇(jk) = −1}∣∣
in Ġ.
Z. Stanić: Spectra of signed graphs and related oriented graphs 5
To demonstrate an application of Theorem 2.1, we deduce a known result. Observe
that a bipartite canonically oriented graph is associated with a homogeneous signed graph,
necessarily switching equivalent to its underlying graph, and so sharing the spectrum with
it. Since bipartite oriented graphs are switching equivalent if and only if associated signed
graphs are switching equivalent (where the equivalence is realized by the same switch-
ing matrix), we deduce the following result (conjectured in [7], and proved in [3]): If
±iλ1,±iλ2, . . . ,±iλn are the skew eigenvalues of a bipartite oriented graph G′ = (G, σ′),
then the eigenvalues of G are ±λ1,±λ2, . . . ,±λn if and only if G′ switches to a canoni-
cally oriented graph.
Here are more details on the cycle structure of Ḣ of Theorem 2.1(ii). It will be used in
the forthcoming sections.
Theorem 3.2. Let G′ and Ḣ be as in Theorem 2.1(ii). For every odd cycle C ′ of G′, the
signed cycle Ċ of Ḣ associated with bd(C ′) is negative.
Proof. If the vertices of C ′, labelled in the natural order, are 1, 2, . . . , ℓ, then the vertices
of its bipartite double bd(C ′) are divided into the colour classes, say A = {a1, a2, . . . , aℓ}
and B{b1, b2, . . . , bℓ}, the edges of bd(C ′) are a1b2, b2a3, a3b4, . . . , bℓ−1aℓ, aℓb1,
b1a2, . . . , aℓ−1bℓ, bℓa1, and these edges inherit the orientation from G′ in the sense that
i→ j implies ai → bj and bi → aj .
Now, if the edges of G′ are oriented in the route direction, so are the edges of bd(G′).
In this case, the edges of the associated signed cycle Ċ alternate in sign, which in particular
means that Ċ is negative (as it counts exactly ℓ negative edges and ℓ is odd) and the edges
aibj and biaj differ in sign (again, since ℓ is odd). If the edges of G′ are not oriented in
the route direction, then C ′ is obtained from the previous cycle by reversing the orientation
of some edges. The desired conclusion follows since changing the orientation of a single
edge ij changes the orientation of both aibj and biaj (in bd(C ′)) and changes the sign of
both aibj and biaj (in Ċ), so it does not change the signature of Ċ.
Corollary 3.3. Let G′ and Ḣ be as in Theorem 2.1(ii). Then Ḣ is unbalanced and bd(G′)
contains a cycle that is not oriented uniformly.
Proof. The first statement follows from the previous theorem. The second one follows
from an easy observation that a negative cycle in Ḣ corresponds to a cycle in bd(G′) that
is not oriented uniformly.
4 Characteristic polynomials
Here are relations between the coefficients of the characteristic polynomials.
Theorem 4.1. If
∑n
i=0 six
n−i is the characteristic polynomial of an oriented graph G′,
then si = 0 for i odd and si ≥ 0 for i even. If G′ is bipartite and
∑⌊n/2⌋
i=0 a2ix
n−2i is the
characteristic polynomial of an associated signed graph, then
a2i = (−1)is2i. (4.1)
If G′ is non-bipartite and
∑n
i=0 a2ix
n−2i is the characteristic polynomial of Ḣ (where Ḣ
is as in the formulation of Theorem 2.1(ii)), then
6 Ars Math. Contemp. 24 (2024) #P3.10
a2i = (−1)i
min{i,n−i}∑
ℓ = −min{i, n − i}
i ≡ ℓ (mod 2)
si−ℓsi+ℓ. (4.2)
Proof. Under the assumptions of Theorem 2.1, the characteristic polynomial of the skew
adjacency matrix of G′ is
xn + s1x
n−1 + · · ·+ sn−1x+ sn = xn−2k(x2 + λ21)(x2 + λ22) · · · (x2 + λ2k). (4.3)
We immediately obtain si = 0 for i odd (since si is the ith elementary symmetric polyno-
mial in eigenvalues), and si ≥ 0 for i even.
If G′ is bipartite, then the characteristic polynomial of an associated signed graph reads∑⌊n/2⌋
i=0 a2ix
n−2i = xn−2k(x2 − λ21)(x2 − λ22) · · · (x2 − λ2k), which yields that even coef-
ficients alternate in sign, and |a2i| = s2i. This implies the equality (4.1).
If G′ is non-bipartite, then the characteristic polynomial of Ḣ is
n∑
i=0
a2ix
n−2i =
(
xn−2k(x2 − λ21)(x2 − λ22) · · · (x2 − λ2k)
)2
.
Comparing it with (4.3), we arrive at
a2i = (−1)i
min{i,n−i}∑
ℓ=−min{i,n−i}
si−ℓsi+ℓ,
but we know that odd coefficients under the sum are zero, so the summation reduces to
even coefficients, which leads to (4.2).
For 2i ≤ n, we note that the formula (4.2) is simplified to
a2i = (−1)i
i∑
ℓ=0
s2ℓs2(i−ℓ).
We visualize this in the following example.
Example 4.2. Let G′ be the oriented graph with 10 vertices illustrated in Figure 1. The
coefficients of its characteristic polynomial are (s0, s2, . . . , s10) = (1, 15, 60, 92, 48, 0).
The coefficients of the characteristic polynomial of Ḣ of Theorem 2.1(ii) are
(a0, a2, . . . , a20) = (1,−30, 345,−1984, 6456,−12480, 14224,−8832, 2304, 0, 0).
Say, 345 = a4 = s0s4 + s22 + s4s0 = 60 + 225 + 60 or −8832 = a14 = (−1)7(s10s4 +
s8s6 + s6s8 + s4s10) = 0− 2 · 92 · 48 + 0, as in Theorem 4.1.
We recall that a basic figure in a graph is a disjoint union of edges and cycles. If∑n
i=0 aix
i is the characteristic polynomial of the adjacency matrix of a signed graph Ġ =
(G, σ̇), then from [4]
ai =
∑
B∈Bi
(−1)p(B)σ̇(B)2|c(B)|,
Z. Stanić: Spectra of signed graphs and related oriented graphs 7
where Bi is the set of basic figures on i vertices in G, p(B) is the number of components of
B, c(B) is the set of cycles in B and σ̇(B) =
∏
Ċ∈c(B) σ̇(Ċ). This result can be extended
to oriented graphs on the basis of Theorems 2.1 and 4.1. However, this has already been
performed in [5, pages 4516–4517] and [9, Theorem 2.3], and so we just refer the reader to
these references. It is worth mentioning that these results address the research problem of
[1, Section 6], asking for an interpretation of the coefficients si in terms of G′.
We conclude this section by the following observation. If the characteristic polynomials
of G (the underlying graph), Ġ = (G, σ̇) (a signed graph) and G′ = (G, σ′) (an oriented
graph) are
∑n
i=0 ai(G)x
n−i,
∑n
i=0 ai(Ġ)x
n−i and
∑n
i=0 si(G
′)xn−i, respectively, then
ai(G) = ai(Ġ) = si(G
′) (mod 2), for 1 ≤ i ≤ n, as AG = AĠ = SG′ (mod 2). Since
si(G
′) = 0 for i odd, this in particular means that ai(G) and ai(Ġ) are even, whenever i is
odd. Moreover, we have the following consequence.
Theorem 4.3. For a graph G, let Ġ (resp. G′) consist of all signed graphs (oriented graphs)
having G as the underlying graph. If there is at least one Γ ∈ {G} ∪ Ġ ∪ G′, such that the
determinant of Γ is odd, then G, all signed graphs of Ġ and all oriented graphs of G′ are
non-singular (i.e. their determinant is non-zero).
Proof. This result follows from the previous observation applied to a0(G), a0(Ġ) and
s0(G
′). Indeed, if for example a0(Ġ) is odd, then a0(Ġ) = a0(G) = 1 (mod 2), and
the same holds for the elements of Ġ ∪ G′ in the role of G.
5 Eigenspaces
Let E(λ) and E(−λ) be the eigenspaces of eigenvalues λ ( ̸= 0) and−λ of a bipartite signed
graph Ġ, and E(iλ), E(−iλ) the eigenspaces of iλ and −iλ belonging to the spectrum of
an associated oriented graph G′. Then E(iλ) ∪ E(−iλ) is spanned (in Cn) by the union
of bases of E(λ) and E(−λ). Indeed, since −S2G′ = A2Ġ, the eigenspace of λ
2 for A2
Ġ
coincides with the eigenspace of−λ2 for S2, and thus the former eigenspace is spanned by
the union of eigenbases of λ and −λ (for AĠ), and the latter one is spanned by the union
of eigenbases of iλ and −iλ (for SG′ ). By the same reasoning, if 0 is an eigenvalue of Ġ,
then it has the same eigenspace for Ġ and G′. However, we can say more.
We first note the following, probably known, result. If x is an eigenvector associated
with the eigenvalue λ (̸= 0) of a bipartite signed graph Ġ, then by negating the entries on
one colour class, we get an eigenvector associated with −λ. Indeed, with an appropriate
vertex labelling, the adjacency matrix has the form
AĠ =
(
O B
B⊺ O
)
(5.1)
If x =
(
x1
x2
)
, then AĠ
(
−x1
x2
)
=
(
Bx2
−B⊺x1
)
= −λ
(
−x1
x2
)
, as desired. If AĠ has
no the previous form, the eigenvectors are permutationally equal, and the result follows.
Henceforth, we assume that the adjacency matrix of a bipartite signed graph is as in (5.1).
Theorem 5.1. Let xj =
(
x1
x2
)
and x−j =
(
−x1
x2
)
be eigenvectors associated with dis-
tinct eigenvalues λj and −λj of a bipartite signed graph Ġ, and let, with a consistent
vertex labelling, G′ be an associated oriented graph. Then xj + ix−j and xj − ix−j are
eigenvectors associated with iλj and −iλj .
8 Ars Math. Contemp. 24 (2024) #P3.10
Proof. If the adjacency matrix of Ġ has the form (5.1), then the skew adjacency matrix
of G′ is SG′ =
(
O B
−B⊺ O
)
. Indeed, in the adjacency matrix of the underlying graph
G, B has no negative entries, and reversing the sign of an edge uv changes the sign of both
auv, avu in AĠ and both suv, svu in SG′ .
We compute
SG′(xj ± ix−j) =
(
Bx2
−B⊺x1
)
± i
(
Bx2
B⊺x1
)
=
(
λjx1
−λjx2
)
± i
(
λjx1
λjx2
)
= ± iλj
((
x1
x2
)
± i
(
−x1
x2
))
= ±iλj(xj ± ix−j),
as desired.
The previous theorem tells us that, in the bipartite case, the eigenspaces of iλj and−iλj
of G′ contain vectors of the form
yij =
(
x1
x2
)
+ i
(
−x1
x2
)
and y−ij = yij =
(
x1
x2
)
− i
(
−x1
x2
)
,
respectively. Conversely, if these eigenvectors are given, then the eigenvectors associated
with λj and −λj of Ġ are easily computed. We proceed with the non-bipartite case.
Theorem 5.2. Let G′ be a non-bipartite oriented graph and y and y eigenvectors as-
sociated with the eigenvalues iλj and −iλj , respectively. Then the pair
(
y
y
)
,
(
y
−y
)
(resp.
(
y
y
)
,
(
y
−y
)
) is associated with iλj (resp. −iλj) in the bipartite double bd(G′),
where Sbd(G′) =
(
0 1
1 0
)
⊗ SG′ . Let Ḣ be a signed graph associated with bd(G′), and
k the multiplicity of λj in the spectrum of Ḣ . The first (resp. second) pair is spanned by
xjℓ + ix−jℓ (resp. xjℓ − ix−jℓ), for 1 ≤ ℓ ≤ k, where xjℓ and x−jℓ span the eigenspaces
of λj and −λj , respectively.
Proof. Since Sbd(G′) is the tensor product, the eiegnvectors of iλj for bd(G′) are (1, 1)⊺⊗
y and (1,−1)⊺ ⊗ y, and similarly for −iλj . This establishes the proof of the first part of
the statement.
By Theorem 5.1, the eigenvectors of iλj for bd(G′) are xjℓ + ix−jℓ, for 1 ≤ ℓ ≤ k.
They are obviously linearly independent (because xjℓ and x−jℓ are). Since the multiplicity
of iλj in the spectrum of bd(G′) is k (cf. Theorem 2.1(ii)), its geometric multiplicity is at
most k and the desired conclusion follows.
We proceed with an application in control theory. The following differential equation
is the standard model of multi-agent single-input linear control systems:
dx
dt
= Mx+ bu, (5.2)
where the scalar u = u(t) is the control input, M ∈ Rn × Rn and x,b ∈ Rn. The system
is controllable if for any x⋆ and time t⋆, there exists a control function u(t), 0 ≤ t ≤ t⋆,
Z. Stanić: Spectra of signed graphs and related oriented graphs 9
such that the solution of the differential equation gives x⋆ = x(t⋆) irrespective of x(0).
There are many controllable criteria, one of which is the Popov-Belevitch-Hautus Test to
be found in any of [6, 11]. Accordingly, the system is controllable if and only if there is no
z ∈ Cn \ {0} such that z∗M = λz∗ and z∗b = 0, where ∗ denotes the complex conjugate.
Theorem 5.3. Let A be the adjacency matrix of a bipartite signed graph and S the skew
adjacency matrix of an associated oriented graph. If the system (5.2) with M = A is
controllable, then it is controllable with M = S.
Proof. Since the system with M = A is controllable, we have x⊺b ̸= 0 for every eigen-
vector of A. Moreover A has no repeated eigenvalues. Indeed, if x1 and x2 are linearly
independent eigenvectors associated with the same eigenvalue, with x⊺1b = b1 ̸= 0 and
x⊺2b = b2 ̸= 0, then (b2x1 − b1x2)⊺b = 0.
As z∗S = λz∗ is equivalent to Sz = λz, and z is an eigenvector for S if and only if z∗
is an eigenvector for the same matrix, we have to show that for every eigenvector y of S,
y∗b = 0 holds.
Since A and S share the same eigenspace for 0, the claim holds for eigenvectors asso-
ciated with 0 (if any). Every eigenvector associated with iλj has the form z(xj + ix−j),
where z = z1 + iz2 ̸= 0, and xj and x−j are as in the formulation of Theorem 5.1. As
before, we may take x⊺jb = b1 ̸= 0 and x
⊺
−jb = b2 ̸= 0. Then
(z(xj + ix−j))
∗b =
(
z1xj − z2x−j + i(z1x−j + z2xj)
)∗
b
=(z1xj − z2x−j)⊺b− i(z1x−j + z2xj)⊺b
= z1b1 − z2b2 + i(z1b2 + z2b1).
Equating with 0, we obtain z1 = b2b1 z2 and z2 = −
b2
b1
z1, which leads to the impossible
scenario z1 = z2 = 0. Hence, the system with M = S is controllable.
6 Energy
We start with the following result concerning signed graphs. There is a similar result for
oriented graphs reported in [1].
Theorem 6.1. Let E(Ġ) be the energy of a signed graph Ġ having n vertices, m edges,
average vertex degree d = 2mn and eigenvalues λ1, λ2, . . . , λn. Then√√√√2(m+ (n
2
)( n∏
i=1
|λi|
) 2
n
)
≤ E(Ġ) ≤ n
√
d. (6.1)
Both equalities hold if and only if Ġ is either edgeless or has exactly two distinct eigenval-
ues and these eigenvalues are equal in absolute value.
Proof. The proof of inequalities of (6.1) is an imitation of the proof of [1, Theorem 2.5]
(concerning oriented graphs). Namely, both follow from the next chain of inequalities and
10 Ars Math. Contemp. 24 (2024) #P3.10
equalities:
2
(
m+
(
n
2
)( n∏
i=1
|λi|
) 2
n
)
≤
n∑
i=1
|λi|2 + 2
∑
1≤i<j≤n
|λi||λj | =
( n∑
i=1
|λi|
)2
≤n
n∑
i=1
|λi|2 = 2mn = n2d.
To clarify, the first inequality in above chain follows from the inequality between the geo-
metric mean and the arithmetic mean, in our case:
( n∏
i=1
|λi|
) 2
n
= n(n−1)
√√√√ n∏
i=1
|λi|2(n−1) = n(n−1)
√ ∏
1≤i<j≤n
(|λi||λj |)2
≤
2
∑
1≤i<j≤n |λi||λj |
n(n− 1)
.
The second inequality in the chain is a consequence of the Cauchy-Schwarz inequality.
Consider now the equality cases. The first equality in (6.1) holds if and only if |λi||λj |
is a constant for every i ̸= j. This occurs if either λi = 0, for all i, or λi = ±λj ̸= 0,
for all i ̸= j. The second equality holds if and only if (|λ1|, |λ2|, . . . , |λn|) is a constant
vector (possibly zero). Hence, both inequalities hold if and only if Ġ is as in the statement
formulation.
We observe that, in the particular case of graphs, the equalities in (6.1) are attained if
and only if G a disjoint union of either isolated vertices or isolated edges. In the ‘signed’
case, there are many other examples. All of them are regular with an even number of
vertices, say 2n, and a symmetric spectrum of the form [λn, (−λ)n]. These signed graphs
belong to the class of strongly regular signed graphs in the sense of definition of [13];
we note in passing that this definition generalizes the concept of strongly regular graphs.
Considering the minimal polynomial, we deduce that the common vertex degree is equal to
λ2. Therefore, λ is the square root of an integer. Disconnected examples are not of interest,
since each of them is a disjoint union of connected ones. We know from [14] that a signed
r-cube without positive quadrangles has the spectrum
[√
r
2r−1
, (−
√
r)2
r−1]
. There are
no other examples for λ ≤
√
3. Signed graphs with spectrum [2n, (−2)n] are completely
determined in [10, 16] (see also [12]). For those with [
√
5
n
, (−
√
5)n], see [17]. Some
other constructions can be found in [8]. We also remark that all signed line graphs with the
required spectrum are constructed in [16].
Observe next that the upper bound (6.1) does not depend on the eigenvalues of Ġ. This,
in particular, means that it simultaneously holds for a signed graph Ġ and its underlying
graph G. According to the previous discussion, in the connected case, this bound is simul-
taneously attained for Ġ and G if and only if G ∼= K1 or G ∼= K2; so, in exactly two simple
cases, and in both Ġ switches to G. For the remaining connected signed graphs that attain
this bound, their underlying graphs do not attain it. This leads to an assumption that the en-
ergy of a signed graph could often be larger than the energy of its underlying graph. In this
context we have experimented with a large number of connected graphs having small order,
or small number of edges (i.e., obtained by inserting few edges to a tree), or large number
of edges (i.e., obtained by deleting few edges of a complete graph). Our conclusions are
Z. Stanić: Spectra of signed graphs and related oriented graphs 11
Figure 2: The signed graph Ġ with 7.814 ≈ E(Ġ) < E(G) ≈ 7.996.
summarized as follows: E(G) = E(Ġ) holds if Ġ switches to G, or G is non-bipartite
and Ġ switches to −G. (For example, the latter occurs for every unicyclic graph with an
odd cycle). We have encountered hundreds of examples in which E(G) < E(Ġ). An ex-
ample in which E(G) > E(Ġ) is illustrated in Figure 2. Motivated by these experiments,
we formulate the following problems.
Problem 6.2. Determine graphs G such that E(G) ≤ E((G, σ̇)) holds for every signature σ̇
defined on the edge set of G.
Problem 6.3. Determine (or, at least, characterize) signed graphs Ġ with E(Ġ) < E(G).
We proceed with oriented graphs. If G′ is associated with Ġ, then E(G′) = E(Ġ), by
Theorem 2.1(i). If Ḣ is as in Theorem 2.1(ii), then E(G′) = E(Ḣ)2 . Accordingly, if the
underlying graph G is regular of degree r, then E(G′) = n
√
r (the upper bound (6.1))
if and only if G′ has exactly two eigenvalues (complex conjugates); this is established
in [1], as well. Some examples are constructed in the mentioned reference. Here we note
that the search on regular oriented graphs attaining the upper bound (6.1) is reduced to
the search on signed graphs with the same spectral property: An associate of a bipartite
signed graph with E(Ġ) = n
√
r has the required spectral property, and if it figures as a
bipartite double, then a corresponding constituent has the same property. In this context it
is worth mentioning that, on the basis of the results of [10, 16], all oriented graphs with n
vertices and spectrum [i2n/2, (−i2)n/2] are determined in [15] (their energy attains 2n);
they include infinite families of both bipartite and non-bipartite oriented graphs. More
examples can be extracted from known signed graphs with two eigenvalues obtained in the
foregoing references.
We also observe that an oriented graph shares the energy with its underlying graph G
whenever it is associated with a balanced signed graph. In this context, we point out that,
due to Corollary 3.3, Ḣ of Theorem 2.1(ii) is never balanced. It also shares the energy
with G whenever it is associated with a signed graph that switches to −G.
This section is concluded with the following result. A conference matrix A is an n× n
matrix with diagonal entries 0 and off-diagonal entries ±1, satisfying A⊺A = (n− 1)I .
Theorem 6.4. An oriented graph G′ (resp. a signed graph Ġ) with n vertices attains
E(G′) = n
√
n− 1 (E(Ġ) = n
√
n− 1) if and only if its adjacency matrix is the skew-
symmetric conference matrix (symmetric conference matrix).
Proof. If E(G′) = n
√
n− 1, by Theorems 2.1(ii) and 6.1, G′ is regular of degree n − 1
and its spectrum is
[
i
√
n− 1n/2,−(i
√
n− 1)n/2
]
. Considering the minimal polynomial
of AG′ , we obtain A2G′ = (n−1)I , which means that AG′ is a skew-symmetric conference
12 Ars Math. Contemp. 24 (2024) #P3.10
matrix. Conversely, if AG′ is a skew-symmetric conference matrix then, by definition, we
have A2G′ = (n− 1)I , which gives E(G′) = n
√
n− 1.
The proof for Ġ is analogous.
The previous result addresses the open problem (6) of [1, Section 6] related to the
existence of skew-symmetric conference matrices that do not give the maximum energy of
the corresponding oriented graph. It also partially addresses the problem (2) of the same
reference related to determination of oriented graphs with maximum energy, as it gives their
characterization via the matrix structure. However, their determination remains a difficult
research problem, since it is equivalent to the complete determination of skew-symmetric
conference matrices.
7 Notes on hypercubes
Due to [22, Theorem 2.1(iv)] (see also [21, Theorem 2]) a signed graph is balanced if its
cycle basis has all positive cycles. Since the induced quadrangles of a signed r-cube contain
a cycle basis, we arrive at the following result.
Lemma 7.1 (cf. [22, Theorem 2.1(iv)]). For r ≥ 2, a signed r-cube Q̇r is balanced if and
only if it has no negative quadrangles.
In [2, 3, 20], the authors gave several algorithms which iteratively construct an oriented
r-cube such that its energy is either equal to the energy of the underlying graph or attains
the upper bound (6.1). (This upper bound reduces to n
√
r.) These algorithms are useful
since they give explicit orientations for which the previous settings occur. In this context
we offer the following contribution (see also the text below the theorem).
Theorem 7.2. The following statements hold true:
(i) A signed r-cube without negative quadrangle is associated with an oriented r-cube
whose energy is equal to the energy of its underlying r-cube.
(ii) A signed r-cube is associated with an oriented r-cube whose energy attains the upper
bound of (6.1) if and only if it has no positive quadrangle.
Proof. (i): If every quadrangle (if any) in Q̇r is positive then Q̇r is balanced, by Lemma 7.1,
and therefore it switches to the underlying graph Qr. Consequently, Q̇r and Qr have the
same energy. By Theorem 2.1, Q̇r shares the energy with an associated oriented cube, and
the result follows.
(ii): Since a signed graph and an associated oriented graph share the same energy, it
is sufficient to show that the energy n
√
r is exclusive to a signed cube without positive
quadrangles. First, such a cube has this energy (as mentioned in the previous section).
Conversely, assume that, for r ≥ 3, a signed r-cube with the adjacency matrix A has a
positive quadrangle, say uvwz (where the vertices are in the natural order). It follows that
the (u,w)-entry of A2 is 2, and so A2 is not a multiple of the identity matrix, but then the
spectrum of A deviates the equality condition of Theorem 6.1, as follows by considering
the minimal polynomial.
In other words, to construct an oriented r-cube whose energy is E(Qr) (resp. n
√
r),
it is sufficient to take any signed r-cube without negative quadrangle (without positive
quadrangle), and construct an oriented associate.
Z. Stanić: Spectra of signed graphs and related oriented graphs 13
ORCID iDs
Zoran Stanić https://orcid.org/0000-0002-4949-4203
References
[1] C. Adiga, R. Balakrishnan and W. So, The skew energy of a digraph, Linear Algebra Appl.
432 (2010), 1825–1835, doi:10.1016/j.laa.2009.11.034, https://doi.org/10.1016/
j.laa.2009.11.034.
[2] A. Anuradha and R. Balakrishnan, Skew spectrum of the Cartesian product of an oriented
graph with an oriented hypercube, in: R. B. Bapat, S. J. Kirkland, K. M. Prasad and S. Pun-
tanen (eds.), Combinatorial Matrix Theory and Generalized Inverses of Matrices, Springer,
New Delhi, pp. 1–12, 2013, doi:10.1007/978-81-322-1053-5\ 1, https://doi.org/10.
1007/978-81-322-1053-5_1.
[3] A. Anuradha, R. Balakrishnan, X. Chen, X. Li, H. Lian and W. So, Skew spectra of oriented
bipartite graphs, Electron. J. Comb. 20 (2013), Paper 18, 12 pp., doi:10.37236/3331, https:
//doi.org/10.37236/3331.
[4] F. Belardo and S. K. Simić, On the Laplacian coefficients of signed graphs, Linear Algebra
Appl. 475 (2015), 94–113, doi:10.1016/j.laa.2015.02.007, https://doi.org/10.1016/
j.laa.2015.02.007.
[5] M. Cavers, S. M. Cioabă, S. Fallat, D. A. Gregory, W. H. Haemers, S. J. Kirkland, J. J.
McDonald and M. Tsatsomeros, Skew-adjacency matrices of graphs, Linear Algebra Appl.
436 (2012), 4512–4529, doi:10.1016/j.laa.2012.01.019, https://doi.org/10.1016/
j.laa.2012.01.019.
[6] C.-T. Chen, Linear System Theory and Design, Oxford University Press, New York, 1998.
[7] D. Cui and Y. Hou, On the skew spectra of Cartesian products of graphs, Electron. J. Comb. 20
(2013), Paper 19, 13 pp., doi:10.37236/2864, https://doi.org/10.37236/2864.
[8] G. R. W. Greaves and Z. Stanić, Signed (0, 2)-graphs with few eigenvalues and a symmetric
spectrum, J. Comb. Des. 30 (2022), 332–353, doi:10.1002/jcd.21828, https://doi.org/
10.1002/jcd.21828.
[9] Y. Hou and T. Lei, Characteristic polynomials of skew-adjacency matrices of oriented graphs,
Electron. J. Comb. 18 (2011), Paper 156, 12 pp., doi:10.37236/643, https://doi.org/
10.37236/643.
[10] Y. Hou, Z. Tang and D. Wang, On signed graphs with just two distinct adjacency eigenvalues,
Discrete Math. 342 (2019), 111615, 8 pp., doi:10.1016/j.disc.2019.111615, https://doi.
org/10.1016/j.disc.2019.111615.
[11] J. Klamka, Controllability of Dynamical Systems, volume 48 of Mathematics and its Applica-
tions (East European Series), Kluwer Academic Publishers Group, Dordrecht; PWN—Polish
Scientific Publishers, Warsaw, 1991.
[12] J. McKee and C. Smyth, Integer symmetric matrices having all their eigenvalues in the in-
terval [−2, 2], J. Algebra 317 (2007), 260–290, doi:10.1016/j.jalgebra.2007.05.019, https:
//doi.org/10.1016/j.jalgebra.2007.05.019.
[13] Z. Stanić, On strongly regular signed graphs, Discrete Appl. Math. 271 (2019), 184–190, doi:
10.1016/j.dam.2019.06.017, https://doi.org/10.1016/j.dam.2019.06.017.
[14] Z. Stanić, A decomposition of signed graphs with two eigenvalues, Filomat 34 (2020), 1949–
1957, doi:10.2298/FIL2006949S, https://doi.org/10.2298/FIL2006949S.
14 Ars Math. Contemp. 24 (2024) #P3.10
[15] Z. Stanić, Oriented graphs whose skew spectral radius does not exceed 2, Linear Algebra Appl.
603 (2020), 359–367, doi:10.1016/j.laa.2020.06.018, https://doi.org/10.1016/j.
laa.2020.06.018.
[16] Z. Stanić, Spectra of signed graphs with two eigenvalues, Appl. Math. Comput. 364 (2020),
124627, 9 pp., doi:10.1016/j.amc.2019.124627, https://doi.org/10.1016/j.amc.
2019.124627.
[17] Z. Stanić, Signed graphs with two eigenvalues and vertex degree five, Ars Math. Contemp. 22
(2022), Paper No. 10, 13 pp., doi:10.26493/1855-3974.2329.97a, https://doi.org/10.
26493/1855-3974.2329.97a.
[18] Z. Stanić, Some relations between the skew spectrum of an oriented graph and the spectrum
of certain closely associated signed graphs, Rev. Un. Mat. Argentina 63 (2022), 41–50, doi:
10.33044/revuma.1914, https://doi.org/10.33044/revuma.1914.
[19] Z. Stanić, Relations between the skew spectrum of an oriented graph and the spectrum of an
associated signed graph, Linear Algebra Appl. 676 (2023), 241–250, doi:10.1016/j.laa.2023.
07.015, https://doi.org/10.1016/j.laa.2023.07.015.
[20] G.-X. Tian, On the skew energy of orientations of hypercubes, Linear Algebra Appl.
435 (2011), 2140–2149, doi:10.1016/j.laa.2011.04.007, https://doi.org/10.1016/
j.laa.2011.04.007.
[21] T. Zaslavsky, Characterizations of signed graphs, J. Graph Theory 5 (1981), 401–406, doi:
10.1002/jgt.3190050409, https://doi.org/10.1002/jgt.3190050409.
[22] T. Zaslavsky, Signed graphs, Discrete Appl. Math. 4 (1982), 47–74, doi:10.1016/
0166-218X(82)90033-6, https://doi.org/10.1016/0166-218X(82)90033-6.