1 Introduction↩︎

A signed digraph (or briefly sidigraph) is a pair \(S = (D, \sigma)\), where \(D = (\mathcal{V}, \mathcal{A})\) is the underlying digraph and \(\sigma : \mathcal{A} \to \{-1, 1\}\) is a sign function. All our sidigraphs are simple i.e., free from loops and parallel signed arcs. An arc from a vertex \(u\) to a vertex \(v\) is denoted by \(uv\). An arc \(uv\) is said to be positive or negative according as \(\sigma(uv) = +1\) or \(\sigma(uv) = -1\). The sign of a sidigraph \(S\) is defined as the product of the signs of all its arcs. The sign of a sub sidigraph \(H\) of sidigraph \(S\) is the restriction of the sign function to \(H\). A sidigraph is said to be all-positive (or all-negative) if each of its arc is positive (or negative). In a digraph \(D\), a directed path of order \(k\) is denoted by \(\overrightarrow{P}_k\), consists of \(k\) vertices say \(v_1, v_2, \dots, v_k\) and arcs \(v_1v_2, v_2v_3,\dots, v_{k-1}v_k\). In a digraph \(D\), a directed cycle of order \(k\) is denoted by \(\overrightarrow{C}_k\), consists of \(k\) vertices say \(v_1, v_2, \dots, v_k\) and arcs \(v_1v_2, v_2v_3,\dots, v_{k-1}v_k, v_kv_1\). The underlying graph \(G\) of a digraph \(D\) is obtained by removing direction of each arc of \(D\) and replacing each directed cycle of length \(2\) by an edge in \(G\). Moreover, if \(P_k\) is path in underlying graph \(G\) of digraph \(D\) but is not the directed path \(\overrightarrow{P}_k\) in \(D\), we call it a semi-directed path. Also, if \(C_k\) is cycle in underlying graph \(G\) of digraph \(D\) but is not the directed cycle \(\overrightarrow{C}_k\) in \(D\), we call it a semi directed cycle. A digraph \(D\) is said to be weakly connected, if its underlying graph \(G\) is connected. A digraph \(D\) is said to be strongly connected if for every pair \(u,v\) of its vertices, there is a directed path from \(u\) to \(v\) and a directed path from \(v\) to \(u\). Clearly, every strongly connected digraph is also weakly connected but not conversely. A weakly connected digraph \(D\) is said to be unicyclic digraph or unicyclic semi digraph according it has one directed cycle of order \(k\ge 2\) or one semi directed cycle of order \(k\ge 3\). A digraph \(D\) is said to be bicyclic digraph if it has two directed cycles each with order at least two and at most one semi directed cycle of order \(k\ge 3\). For example see Figures \(3,4,5\) and [1]. A sidigraph \(S=(D(\mathcal{V}, \mathcal{A}),\sigma)\) is said to be weakly or strongly connected if its underlying digraph \(D\) is weakly or strongly connected. A sidigraph \(S\) is said to be unicyclic or bicyclic if its underlying digraph \(D\) is unicyclic or bicyclic. A directed cycle (semi directed cycle) in a sidigraph is said to be positive or negative according as its sign is positive or negative respectively. A sidigraph is said to be balanced if each of its directed cycle and semi directed cycle is positive. A positive directed cycle of order \(n\) is denoted by \(C_n^+\), and a negative directed cycle of order \(n\) is denoted by \(C_n^{-}\).
Let \(S\) be a sidigraph of order \(n\) with vertices \(v_1, v_2, \dots, v_n\). Then the adjacency matrix of \(S\), denoted by \(A(S) = [a_{ij}]_{n \times n}\), is a square matrix of order \(n\) with \(a_{ij}=\sigma(v_i, v_j)\) if there is an arc from \(v_i\) to \(v_j\) and zero, otherwise. The characteristic polynomial of \(A(S)\), \(\phi_{A(S)}(\lambda) = \det(A(S) - \lambda I_n)\) is known as the characteristic polynomial of \(S\) and the eigenvalues of \(A(S)\) are known as the eigenvalues of \(S\). A signed graph or sigraph \(\Sigma\) is a pair \(\Sigma=(G(\mathcal{V},\mathcal{E}),\sigma)\), where \(\sigma:\mathcal{E}\rightarrow\{-1,+1\}\) is a sign function. A sidigraph \(S\) is said to be symmetric if, for every arc \(uv \in \mathcal{A}(S)\), the arc \(vu \in \mathcal{A(S)}\) also exists with the same sign, where \(u, v \in \mathcal{V}(S)\). There exists a one-to-one correspondence between sigraphs and symmetric sidigraphs given by \(\Sigma \longleftrightarrow \overleftrightarrow{\Sigma}\), where \(\overleftrightarrow{\Sigma}\) denotes the sidigraph obtained from sigraph \(\Sigma\) with the same vertex set as that of the sigraph \(\Sigma\) and each signed edge in \(\Sigma\) is replaced by a pair of symmetric arcs \(uv\) and \(vu\), both carrying the same sign as that of the edge \(uv\). Under this correspondence, a sigraph can be identified with a symmetric sidigraph. For a vertex \(u\) in a digraph \(D\), the outdegree \(d^+(u)\) is the number of arcs leaving \(u\), and the indegree \(d^-(u)\) is the number of arcs entering \(u\). The indegree and outdegree in sidigraph are those of its underlying digraph.
Let \(S=(D(\mathcal{A},\mathcal{V}),\sigma)\) be a sidigraph and \(Y \subset \mathcal{V}\). Switching \(S\) by \(Y\) is the sidigraph obtained from \(S\) by changing signs of all arcs between \(Y\) and \(\mathcal{V}\setminus Y\). For switching in sigraphs see [2]. The switched sidigraph thus obtained is denoted by \(S^Y\). Note that switching is an equivalence relation on the signings of digraph and its equivalence classes are known as switching classes. An alternative way to define switching is by means of a function \(\chi:\mathcal{V}\rightarrow \{-1,+1\}\) such that \(\sigma^{\chi}(uv)=\chi(u)\sigma(uv)\chi(v)\). In terms of matrices if \(A\) is the adjacency matrix of a sidigraph \(S\) and \(A^{\chi}\) be the adjacency matrix of switched sidigraph \(S^{\chi}\), then \(A^{\chi}=M^{-1}AM\), where \(M\) is the signature matrix (i.e., the diagonal matrix with diagonal entries from the set \(\{-1,+1\}\)) with \(M_{ii}=\chi(v_i)\). Note that \(M=M^T=M^{-1}\). Two sidigraphs are said to be switching isomorphic if one is isomorphic to switching of other. For example in undirected case see [2].
The singular values of a sidigraph \(S\) are singular values of its adjacency matrix \(A\) i.e., the positive square roots of eigenvalues of \(AA^T\). If a sidigraph \(S\) of order \(n\) has \(k\le n\) distinct singular \(\sigma_1, \sigma_2, \dots, \sigma_k\) values with respective multiplicities \(m_1, m_2, \dots, m_k\), then we write the singular values as \(\sigma_1^{(m_1)}, \sigma_2^{(m_2)}, \dots, \sigma_k^{(m_k)}\). Throughout, we assume the order of singular values as \(\sigma_1(S)\ge\sigma_2(S)\ge \dots \ge\sigma_n(S)\ge0\). The singular value \(\sigma_1(S)\) is called the spectral norm of \(S\). The trace norm of a sidigraph \(S\) with singular values \(\sigma_1(S), \sigma_2(S), \dots, \sigma_n(S)\) is denoted by \(\|A\|_*\) and is defined as \[\|A\|_*=\sum_{i=1}^{n}\sigma_i(S).\] The notion of energy in sigraphs was given by Germina et al. [3] and they defined the energy of a sigraph as the sum of absolute values of sigraph eigenvalues. The concept of energy was extended to sidigraphs by Pirzada and Bhat  [4] and they defined the energy of a sidigraph as the sum of absolute values of real parts of sidigraph eigenvalues. It is clear that for sigraphs trace norm becomes the energy. Agudelo, Rada [5] obtained lower bounds for the trace norm of digraphs. Agudelo, Peña and Rada obtained the extremal values of trace norm over oriented trees. For more on trace norm and energy see [6]–[13]. In this paper, we study the energy of sidigraphs by using trace norm definition.
By \(\mathcal{T}(n),~\mathcal{U}(n)~ \text{and}~ \mathcal{B}(n)\), we respectively denote the set of directed trees, unicyclic digraphs and bicyclic digraphs of order \(n\). Let \(\overrightarrow{K}_{p,q}\) denote the directed complete bipartite digraph with partite sets say \(P=\{u_1,u_2,\dots,u_p\}\) and \(Q=v_1,v_2,\dots, v_q\) and \(\mathcal{A}({K}_{p,q})=\{u_iv_j:i=1,2,\dots, p ~~\text{and}~~ j=1,2,\dots,q\}\). The rest of the paper is oragnized as follows. It is shown that like in signed trees, given a directed tree \(T\) on \(n\) vertices, all signed directed trees on \(T\) has same singular values and hence same trace norm. We also show that unlike eigenvalues, given a unicyclic or bicyclic digraph, all signed digraphs on it has same singular values. This gives families of switching non-isomorphic sidigraphs with same singular values and same trace norm. We characterize sidigraphs with rank one and as an application of this result, we obtain a lower bound for the trace norm of sidigraphs and characterize the extremal sidigraphs. Problems for future research are also given at the end.

2 Preliminaries↩︎

In this section we recall some known results that will be used in sequel. We also present a few results on switching and singular values of sidigraphs.
The following result is known as the interlacing property of singular values.

A vertex \(v\) in a digraph is said to be a sink or source vertex if \(d^+(v)=0\) or \(d^-(v)=0\) respectively. A digraph is said to be sink-source if each of its vertex is either a sink or a source vertex. The following result holds in this direction.

Proof. Given a directed tree \(T\in\mathcal{T}(n)\), let \(\mathcal{S}(T)\) denote the collection of all signed directed trees on \(T\). We will show that any signed directed tree \(K\in \mathcal{S}(T)\) is switching equivalent to \(T\), the all positive directed tree. Let the \(n\) vertices of \(K\) be \(v_{1}, v_{2}, \dots, v_{n}\). Define \(\chi(v_{1}) = 1\) and \(\chi(v_{i}) =\) sign of semi directed path from \(v_{1}\) to \(v_{i}\) in \(K\). Then \(K^{\chi}\) is the all positive signed directed tree \(T\). Accordingly, \[M^{-1}A(K)M = A(T),\] where \(M=\text{diag}(\chi(v_1),\chi(v_2),\dots,\chi(v_n))\) is the signature matrix. Clearly, \(A(K)\) and \(A(T)\) have the same singular values.

Proof. Let \(S\) be sidigraph of order \(n\ge 2\) and let it has a cycle \(\overrightarrow{C}_k\) of order \(k\) with cyclic vertices being \(v_1,v_2,\dots,v_k\), where \(2\le k\le n\). Then for any switching function \(\chi\) on \(S\), \(\text{sgn}_{S^{\chi}}(\overrightarrow{C}_k)=\text{sgn}_{S}(\overrightarrow{C}_k)(\chi(v_1))^2(\chi(v_2))^2\dots(\chi(v_k))^2=\text{sgn}_{S}(\overrightarrow{C}_k)\), where \(\text{sgn}_{S}(\overrightarrow{C}_k)\) stands for sign of \(\overrightarrow{C}_k\) in \(S\). A similar proof holds for semi directed cycle.

Recall that a sidigraph is said to be empty or discrete if its has no arc. The following result follows from singular value decomposition of a matrix.

We note that in general signing does not preserve the singular values. For example, the singular values of the digraph shown in Figure 1 are \(2,\sqrt{2},\sqrt{2}, 0\). If we change sign of arc \(v_1v_2\) from positive to negative, the resulting sidigraph has singular values \(\sqrt{2+\sqrt{2}},\sqrt{2+\sqrt{2}},\sqrt{2-\sqrt{2}},\sqrt{2-\sqrt{2}}\).

3 Invariance of singular values under signing↩︎

We begin this section with examples which also provide motivation for our results.

From examples \(3.3\) and \(3.4\), we see that \(\widehat{C}_n\) and \(\widehat{C}_n^{-}\) do not have all the singular values same.

As in example [4] Example 2.5, we see that eigenvalues of positive and negative directed cycle of order \(n\ge 2\) are different. In the next result, we show that given a unicyclic digraph, say \(U\) of order \(n\), all sidigraphs on \(U\) have the same singular values.

Proof. Let \(U \in \mathcal{U}(n)\) and \(\mathcal{S}(U)\) be the collection of all sidigraphs on \(U\). Clearly, \(|\mathcal{S}(U)| = 2^{n}\). We show for any two sidigraphs \(S_1, S_2\in \mathcal{S}(U)\), there exist signature matrices \(M_1\) and \(M_2\) such that \(M_1A(S_1)M_2=A(S_2)\). Let \[\mathcal{S}^{+}(U) = \{S \in \mathcal{S}(U) : S \text{ is balanced}\}\] and \[\mathcal{S}^{-}(U) = \{S \in \mathcal{S}(U) : S \text{ is unbalanced}\}.\]

Claim 1: Each element \(X \in \mathcal{S}^{+}(U)\) is switching equivalent to \(U\).

Claim 2: Each element \(Y \in \mathcal{S}^{-}(U)\) is switching equivalent to \(U^{-}\), where \(U^{-}\) is the sidigraph on \(U\) with exactly one negative cyclic arc and all other arcs are positive.

Proof of claim 1: Let \(v_{1}, v_{2}, \dots, v_{k}, v_{k+1}, \dots, v_{n}\) be the vertices of \(X\) such that the first \(k\ge 2\) vertices are cyclic vertices. Then there exists a switching function \(\chi\) on vertices such that \(X \setminus \{v_{1}v_{2}\}\) is all positive directed tree. Since switching preserves the sign of cycles, we see that under switching \(\chi\), the cyclic arc \(v_{1}v_{2}\) is also positive and hence \(X^{\chi} = U\). Claim 2 follows by same argument. Thus we see \(\mathcal{S}(U)\) has two switching classes; let these be \([U]\) and \([U^{-}]\).

If \(S_{1}, S_{2} \in [U]\), then \(S_{1}\) and \(S_{2}\) are switching equivalent and so there exists a signature matrix, say \(M_{1}\), such that \(M_{1}^{-1}A(S_{1})M_{1} = A(S_{2})\). In this case, \(S_{1}\) and \(S_{2}\) have the same singular values. The same argument applies when \(S_{1}, S_{2} \in [U^-]\). Next, let \(S_{1} \in [U]\) and \(S_{2} \in [U^{-}]\). Without loss of generality, we assume \(S_{1} = U\) and \(S_{2} = U^{-}\). Assume arc \(v_{1}v_{2}\) in \(U^{-}\) is negative and all other arcs are positive. We want to find signature matrices \(M_{1}\) and \(M_{2}\) such that \[M_{1}A(S_{1})M_{2} = A(S_{2}).\]

For \((i,j)\) such that \(v_iv_j\in \mathcal{A}(S_1)\) (arc from \(v_i\) to \(v_j\)), we have \[(M_1 A(S_1) M_2)_{i,j} = (M_1 A(U) M_2)_{i,j} = (M_1)_{i,i} (A(U))_{i,j} (M_2)_{j,j} = (M_1)_{i,i} (M_2)_{j,j}.\] For \(M_1 A(S_1) M_2 = A(S_2)\) to hold, we set \((M_1)_{1,1} = 1\) and \((M_2)_{2,2} = -1\). For \((i,j)=(1,2)\) as arc \(v_1 v_2\) is negative, we have \[(M_1)_{1,1} (A(U))_{1,2} (M_2)_{2,2} = (1)(1)(-1) = -1 = (A(S_2))_{1,2}.\] Keeping the values of \((M_1)_{1,1}\) and \((M_2)_{2,2}\) into consideration, for \((i,j)\neq(1,2)\) and \(v_iv_j\in \mathcal{A}(S_1)\), we define \((M_1)_{i,i} = (M_2)_{j,j} \in \{ -1, 1 \}\). Moreover, if \(v_p\) is a sink or source vertex, we take \((M_1)_{p,p} = (M_2)_{p,p}\) while keeping \((M_1)_{1,1}=1=-(M_2)_{2,2}\) into consideration. It is clear that \(M_1 A(S_1) M_2 = A(S_2)\) is satisfied.

Now \(A(S_2){A^T(S_2)}=(M_1A(S_1)M_2)(M_1A(S_1)M_2)^T={M_1}^{-1}A(S_1){A^T(S_1)} M_1\), as \({M_1}^T={M_1}^{-1}\) and \({M_2}^{-1}=M_2\).
Therefore the matrices \(A(S_2){A^T(S_2)}\) and \(A(S_1){A^T(S_1)}\) are similar by a signature matrix and hence they have same eigenvalues and also are positive semi definite. We see \(A(S_1)\) and \(A(S_2)\) have the same singular values. This completes the proof.

We next give an example in support of Theorem \(3.5\).

We next show that given a bicyclic digraph \(B\in\mathcal{B}(n)\), all sidigraphs on \(B\) have same singular values.

Let \(\mathcal{B}_1(n)\) denote the set of bicyclic digraphs on \(n\) vertices in which the two cycles say \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\) share a common vertex. For such a digraph without non cyclic vertices and arcs see Figure 3. Let \(\mathcal{B}_2(n)\) denote the set of bicyclic digraphs on \(n\) vertices in which two cycles are vertex disjoint. For such a digraph without non cyclic vertices see Figure \(4\). Let \(\mathcal{B}_3(n)\) denote the set of bicyclic digraphs on \(n\) vertices in which two cycles share a directed path. For such a digraph without non cyclic vertices see Figure 5. Clearly \(\mathcal{B}(n)=\mathcal{B}_1(n)\cup \mathcal{B}_2(n)\cup\mathcal{B}_3(n)\).

Proof. Let \(B\in\mathcal{B}(n)\). Three cases arise here depending on \(B\in \mathcal{B}_1(n)\) or \(B\in \mathcal{B}_2(n)\) or \(B\in \mathcal{B}_3(n)\).
Case 1. We first assume that \(B\in \mathcal{B}_1(n)\). Assume two cycles in \(B\) be \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\) such that \(\overrightarrow{C}_1\) has \(k\) directed arcs \(v_1v_2,v_2v_3, \dots, v_kv_1\) and \(\overrightarrow{C}_2\) has \(l\) directed arcs \(v_1v_{k+1}, v_{k+1}v_{k+2}, \dots, v_{k+l-1}v_1\). Let \(\mathcal{S}_1(B)\) be the collection of all sidigraphs on \(B\). As in theorem \(3.5\), it is easy to see that \(\mathcal{S}_1(B)\) has atmost four switching classes based on the signs of the two cycles \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\). We denote these switching classes as \([B], [B^{-+}], [B^{+-}] ~\text{and}~ [B^{--}]\), where \(B\) is all-positive digraph, \(B^{-+}\) is the sidigraph on \(B\) with arc \(v_1v_2\) negative and all other arcs positive so that \(\overrightarrow{C}_1\) is negative and \(\overrightarrow{C}_2\) is positive, \(B^{+-}\) is the sidigraph on \(B\) with cyclic arc \(v_1v_{k+1}\) negative and all other arcs positive so that \(\overrightarrow{C}_1\) is positive and \(\overrightarrow{C}_2\) is negative, \(B^{--}\) is the sidigraph on \(B\) with arcs \(v_1v_2\) and \(v_1v_{k+1}\) negative and all other arcs positive so that both cycles \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\) are negative. We note that for some digraph \(B\), the switching classes \([B^{-+}]\) and \([B^{+-}]\) of \(\mathcal{S}_1(B)\) can be identical. For example take \(B\) as the digraph shown in Figure \(3\) such that it has no non-cyclic vertex and both cycles are of same order.
Let \(S_1, S_2\in \mathcal{S}_1(B)\). We show that there exist signature matrices \(M_1\) and \(M_2\) such that \(M_1 A(S_1) M_2 = A(S_2)\). Noting that switching is an equivalence relation, we consider the following three subcases.
Subcase 1.1. When \(S_1\in[B]\) and \(S_2\in [B^{-+}]\). Without loss of generality, we assume \(S_1=B\) and \(S_2=B^{-+}\). We want to find signature matrices \(M_1\) and \(M_2\) such that \[M_1 A(S_1) M_2 = A(S_2)\] For \((i,j)\) such that \(v_iv_j\in \mathcal{A}(S_1)\) (arc from \(v_i\) to \(v_j\)), we have \[(M_1 A(S_1) M_2)_{i,j} = (M_1 A(B) M_2)_{i,j} = (M_1)_{i,i} (A(B))_{i,j} (M_2)_{j,j} = (M_1)_{i,i} (M_2)_{j,j}.\] For \(M_1 A(S_1) M_2 = A(S_2)\) to hold, we set \((M_1)_{1,1} = 1\) and \((M_2)_{2,2} = -1\). For \((i,j)=(1,2)\), we have \[(M_1)_{1,1} (A(B))_{1,2} (M_2)_{2,2} = (1)(1)(-1) = -1 = (A(S_2))_{1,2}.\] Keeping \((M_1)_{1,1}\) and \((M_2)_{2,2}\) into consideration, for \((i,j)\neq(1,2)\) and \(v_iv_j\in \mathcal{A}(S_1)\), we define \((M_1)_{i,i} = (M_2)_{j,j} \in \{ -1, 1 \}\). Moreover, if \(v_p\) is a sink or source vertex, we take \((M_1)_{p,p} = (M_2)_{p,p}\) while keeping \((M_1)_{1,1}=1=-(M_2)_{2,2}\) into consideration. It is clear that \(M_1 A(S_1) M_2 = A(S_2)\) is satisfied.

Subcase 1.2. When \(S_1\in [B]\) and \(S_2\in [B^{--}]\). We assume \(S_1=B\) and \(S_2=B^{--}\). Proceeding as in subcase \(1.1\), we define \((M_1)_{1,1}=1\), \((M_2)_{2,2}=-1=(M_2)_{k+1,k+1}\). Keeping this into consideration, for arc \(v_iv_j\in \mathcal{A}(S_1)\), \((i,j)\neq (1,2),(1,k+1)\), we define \((M_1)_{i,i}=(M_2)_{j,j}\). In case some vertex, say \(v_p\) is sink or source, then we define \((M_1)_{p,p}=(M_2)_{p,p}\). With these \(M_1\) and \(M_2\), the subcase \(1.2\) follows.
Subcase 1.3. \(S_1\in [B]\) and \(S_2\in [B^{-+}]\) follows similarly.
Using transitivity of switching operation on \(\mathcal{S}_(B)\), the result follows in case 1.

Case 2. Let \(B\in \mathcal{B}_2(n)\) and let \(\mathcal{S}_2(B)\) denote the set of sidigraphs on \(B\). As in case \(1\), there are at most four switching classes of \(\mathcal{S}_2(B)\) depending on the signings of cycles \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\) and the proof follows on similar lines as in case \(1\).

Case 3. When \(B\in \mathcal{B}_3(n)\). In this case, the two directed cycles \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\) share a common directed path \(\overrightarrow{P}_k\) of length \(k\ge 1\). Let the vertices on \(P_k\) be \(v_1,v_2,\dots,v_k\). Let \(\mathcal{S}_3(B)\) denote the set of sidigraphs on \(B\). There are at most four switching classes in this case as well depending on the signs of cycles \(\overrightarrow{C}_1\) and \(\overrightarrow{C}_2\). We denote these switching classes by \([\theta(+,+)]\), \([\theta(-,+)]\), \([\theta(+,-)]\) and \([\theta(-,-)]\), where \(\theta(+,+)\) denote the all positive sidigraph on \(B\), \(\theta(+,-)\) is sidigraph with arc \(v_kw_1\) negative and all other arcs positive, \(\theta(-,+)\) denote the sidigraph on \(B\) with arc \(v_ku_1\) negative and all other arcs positive and \(\theta(-,-)\) denote the sidigraph on \(B\) with arc \(v_1v_2\) negative and all other arcs positive. The remaining proof follows as in case \(1\).

4 A lower bound for the trace norm of sidigraphs↩︎

The rank of a sidigraph \(S\) is the number of positive singular values of its adjacency matrix. For digraphs, the singular values and rank have been studied in [6], [16]. In [17], the authors produce classification of sidigraphs with rank \(2,3\) but considered a different matrix namely Eisenstein matrix. Our matrix is the usual adjacency matrix here. We first provide characterization of sidigraphs with rank one and use this to study the equality case in lower bound for the trace norm of sidigraphs. From here onwards we assume our sidigraphs have no isolated vertices. The following result characterizes sidigraphs with rank \(1\).

Proof. For \(n=2\), the possible sidigraphs are \((\overrightarrow{P}_{2}, \sigma)\) and \((\overrightarrow{C}_{2}, \sigma)\). As singular values of \((\overrightarrow{P}_{2}, \sigma)\) are \(1,0\) and those of \((\overrightarrow{C}_{2}, \sigma)\) are \(1^{(2)}\). Therefore, \((\overrightarrow{P}_{2}, \sigma)\) is the only sidigraph on two vertices with rank \(1\).
Assume \(S=(D(\mathcal{V},\mathcal{A}), \sigma)\) has \(n\ge 3\) vertices and \(Rank(S)=1\) .
Claim 1. \(S\) cannot have two signed arcs of the form \(uv\),\(vw\) where \(\{u,v,w\} \subset \mathcal{V}\).
Proof of claim 1. Suppose sidigraph \(S\) has arcs of the form \(uv\), \(vw\), where \(u\ne v\ne w\). Then, the possible induced subsidigraphs of \(S\) on vertices \(\{u,v,w\}\) are \((\overrightarrow{P}_{3}, \sigma)\), \((\overrightarrow{C}_{3}, \sigma)\), \((\overleftrightarrow K_3, \sigma)\), \((D_1, \sigma)\),
\((D^{T}_1, \sigma)\), \((D_2, \sigma)\), \((D_3, \sigma)\), \((D_4, \sigma)\), \((D_5,\sigma)\) and \((D^{T}_5,\sigma)\) where \(D_1,D_2,D_3, D_4\) and \(D_5\) are shown in Figure. 5. Note that the singular values of \((\overrightarrow{P}_{3}, \sigma)\) are \(\{1^{(2)},0\}\); the singular values of \((\overrightarrow{C}_{3}, \sigma)\) are \(\{1^{(3)}\}\); the singular values of \((\overleftrightarrow K_3, \sigma)\) are \(\{2,1^{(2)}\}\); the singular values of \((D_1, \sigma)\) and \((D^{T}_1, \sigma)\) are \(\{\sqrt{2},1,0\}\); the singular values of \((D_2, \sigma)\) are \(\{\sqrt{\frac{3+\sqrt{5}}{2}},\sqrt{\frac{3-\sqrt{5}}{2}},0\}\); the singular values of \(D_3\) are \(\{\sqrt{\frac{3+\sqrt{5}}{2}},1,\sqrt{\frac{3-\sqrt{5}}{2}}\}\); the singular values of \(D_4\) are \(\{1.8019,1.2470,0.4450\}\) and the singular values of \((D_5,\sigma)\) or \((D^{T}_5,\sigma)\) are \(\sqrt{3}, 1 ,0\). It is easy to see that all sidigraphs on \(D_3\) and \(D_4\) have three positive singular values. By interlacing of singular values Lemma \(2.1\), the sidigraph \(S\) has at least two positive singular values and hence \(\text{Rank}(S)\ge2\), which is a contradiction. This proves the claim.
Hence each vertex of \(D\) is either a sink or a source vertex and so by Lemma \(2.2\), \(D\) is bipartite. Assume the partite sets of \(D\) have cardinality \(p\) and \(q\) so that \(p+q=n\).
Claim 2. The underlying digraph \(D\) of \(S\) is not a proper subdigraph of \(\overrightarrow K_{p,q}\).
Proof of claim 2. If \(D\) is a proper subdigraph of \(\overrightarrow K_{p,q}\) with partite sets \(V_1=\{v_1,v_2,\cdots,v_p\}\) and \(V_2=\{u_1,u_2,\cdots,u_q\}\), then some vertex of \(V_1\) is not adjacent to some vertex of \(V_2\) say arc \(v_1u_1\notin\mathcal{A}(S)\). Since \(u_1\) is not an isolated vertex, therefore for some \(v_i\), where \(i=2,3,\dots,n\) say \(v_2\), \(v_2u_1\in \mathcal{A}(S)\). Then the rows indexed by \(v_1\) and \(v_2\) of the adjacency matrix \(A(S)\) of \(S\) are linearly independent and hence \(Rank(S)\) is at least \(2\). This proves \(D=\overrightarrow K_{p,q}\) with \(p+q=n\). Therefore, the underlying digraph \(D\) of \(S\) is \(\overrightarrow K_{p,q}\) with \(p+q=n\).
Claim 3. \(S=(\overrightarrow K_{p,q},\sigma)\) does not contain subsidigraph \(\overrightarrow K_{2,2}\) with negative sign.
Proof of claim 3. If \(S\) contain \(\overrightarrow K_{2,2}\) with negative sign, then \(A(S)\) has a submatrix of order \(2\) with entries from\(\{-1,+1\}\) and having odd number of \(-1\)’s. It is easy to see that such a submatrix has two positive singular values and consequently by interlacing property, \(S\) has at least two positive singular values and hence \(\text{Rank}(S)\ge 2\). This proves the claim \(3\).
Conversely, if \(S = (\overrightarrow{K}_{p,q}, \sigma)\) not containing \((\overrightarrow{K}_{2,2}, \sigma)\) as a subsidigraph with the negative sign, then all \(2\times 2\) minors are zero and hence all minors of order greater than \(2\) of \(A(S)\) are also zero. So, Rank (S)=1.

In the next result, we obtain a lower bound for the trace norm of sidigraphs in terms of number of vertices and arcs.

Proof. Let \(A\) be the adjacency matrix and \(\sigma_1(S), \sigma_2(S), \dots,\sigma_n(S)\) be the singular values of \(S\). We have the Frobenius norm \[\|S\|_F^2=\sum_{i,j} |a_{ij}|^2 = m.\] Also, \(\|S\|_F^2=\sum_{i=1}^n \sigma_i^2(S)\) and \(\prod_{i=1}^n \sigma_i(S) = |\det S|\).

We have \[\begin{align} \|S\|_*^2&=\Big(\sum_i \sigma_i(S)\Big)^2\\ &=\sum_i \sigma_i(S)^2 + 2\sum_{i<j} \sigma_i(S)\sigma_j(S)\\ &= \|S\|_F^2 + 2\sum_{i<j} \sigma_i(S)\sigma_j(S) \\ &= m + 2\sum_{i<j} \sigma_i(S)\sigma_j(S). \end{align}\]

By AM–GM inequality applied to the \(\binom{n}{2}\) products, we have \[\begin{align} \frac{1}{\binom{n}{2}}\sum_{i<j} \sigma_i(S) \sigma_j(S)\; &\ge\; \Bigg(\prod_{i<j} \sigma_i(S) \sigma_j(S)\Bigg)^{\!1/\binom{n}{2}}\\ &= \Big( \prod_{i=1}^n \sigma_i(S) \Big)^{\!(n-1)/\binom{n}{2}}\\ &= |\det S|^{\,2/n}. \end{align}\]

Therefore, \[\|S\|_* \;\ge\; \sqrt{\,m + n(n-1)\,|\det S|^{2/n}}.\]

Assume the equality holds in \((4.1)\), then equality hold in AM–GM inequality applied on the collection \(\{\sigma_i(S) \sigma_j(S) : 1\le i<j\le n\}\), gives \(\sigma_i(S)\sigma_j(S)= c \quad \text{for all } i<j\).
Two cases arise here.
Case 1. If \(\sigma_1(S)\sigma_2(S) > 0\), then \(\sigma_1(S)=\sigma_2(S)=\dots=\sigma_n(S)>0\). By singular value decomposition, there exists a real orthogonal matrix \(W\) such that \[\begin{align} A &= \sigma_1(S)W \\ \text{or}~~~~[A]_{ij} &= \sigma_1(S)[W]_{ij} \\ \text{or}~~~~\sum_{j=1}^n [A]^{2}_{ij} &= \sigma_1(S)^{2} \sum_{j=1}^{n}[W]^{2}_{ij} = \sigma_1(S)^{2} \\ \text{or}~~~~d_i^{+} &= \sigma_1(S)^{2} \quad \text{for~~all}~ i=1,2,\dots,n. \\ \text{Also},~~~~\sum_{i=1}^{n}[A]_{ij}^{2} &= \sigma_1(S)^{2}\sum_{i=1}^{n}[W]_{ij} \\ \text{which gives}~~~~d_j^{-} &= \sigma_1(S)^{2} \quad \text{for~~all}~ j=1,2,\dots,n. \end{align}\]

Therefore, \[d_i^{+}=d_{i}^{-}=\sigma_1^{2}(S)= d,~say \quad \text{for~~all}~ i=1,2,\dots,n\] and hence underlying digraph \(D\) of \(S\) is regular.

Case 2. If \(\sigma_1(S) > 0\), \(\sigma_2(S)=0\) then \(\sigma_2(S)=\sigma_3(S)=\dots=\sigma_n(S)=0\). Therefore, \(\text{Rank}(S)=1\). By Theorem \(4.1\), \(S = (\overrightarrow{K}_{p,q}, \sigma)\) not containing those \((\overrightarrow{K}_{2,2}, \sigma)\) having negative sign.

Conversely, if \(S = (\overrightarrow{K}_{p,q}, \sigma)\) not containing those \((\overrightarrow{K}_{2,2}, \sigma)\), then by Theorem \(4.1\), \(\text{Rank}(S)=1\) and so \(S\) has only one positive singular value. Recall that sum of singular values is equal to the number of arcs, we see \(\sigma_1(S)=\sqrt{pq}\) and \(\sigma_i(S)=0\) for \(i=2,3,\dots,n\). It is easy to see both sides of \((4.1)\) are equal to \(\sqrt{pq}\).
If \(\sigma_1(S) = \sigma_2(S) =\dots = \sigma_n(S)= \sqrt{d}\) and underlying digraph \(D\) of \(S\) is \(d-\)regular. It is easy to see that both sides of \((4.1)\) are equal to \(n\sqrt{d}\). This completes the proof.

In the next result, as a consequence of Theorem \(4.2\), we determine signed directed trees with minimum trace norm.

Proof. Let \(T\in (\mathcal{T}(n), \sigma)\). By Theorem \(4.2\), we see that \[\|T\|_* \;\geq\; \sqrt{\,(n-1) \;+\; n(n-1)\, |\det T|^{2/n}} \,\ge \sqrt{n-1}.\] We note that \((\overrightarrow{K}_{p,q}, \sigma)\) is a signed directed tree if and only if \(p=1\) and \(q=n-1\) or \(p=n-1\) and \(q=1\). The result follows.

5 Concluding remarks and future directions↩︎

We see from Theorem \(4.2\) that if a signed digraph \(S\) with atleast one arc, has all singular values \(\sigma_i(S)\), \(i=1,2,\dots,n\) equal. Then \(S\) must be \(regular\) with regularity say \(d\ge 1\) and \(\sigma_i(S)=\sqrt{d}\). At this moment, we are not able to determine sidigraphs whose underlying digraphs are \(d\) regular and have all singular values positive and equal to \(\sqrt{d}\). So, we conclude this paper with the following problem for future study.

The research of M. A. Bhat is supported by NBHM project No. 02011/42
/2025/NBHM(RP)/R&DII/16567 and by SERB-DST grant with File No. MTR/2023/000201.

References↩︎