Lower bounds for the spectral norm of digraphs

Let D be a digraph with n vertices and sigma(1) (D) >= sigma(2) (D) >= ... >= sigma(n) (D) the singular values of the adjacency matrix A of D. The spectral norm of D is sigma(1) (D) and the trace norm of D is parallel to D parallel to(*) = Sigma(n)(i=1) sigma(i) (D). In this paper we find lower bounds for the spectral norm of a digraph in terms of the structure of the digraph. Moreover, we introduce the concept of almost regular digraphs (extension of the well known almost regular graphs), and show that the lower bounds are attained precisely in almost regular digraphs. When we apply this theory to graphs, we recover well known lower bounds for the spectral radius of graphs. Also, we give a new upper bound for the trace norm of a digraph. Moreover, we determine the digraphs for which this bound is sharp: sink-source complete bipartite digraphs or symmetric balanced incomplete block designs (BIBD). (C) 2021 Elsevier Inc. All rights reserved.

Automated summary

This paper explores the spectral and trace norms of digraphs, providing lower bounds and introducing the concept of almost regular digraphs. It also gives new upper bounds for the trace norm of digraphs and identifies the digraphs for which these bounds are optimal, such as sink-source complete bipartite digraphs or symmetric balanced incomplete block designs.