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 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.