The Restricted Numerical Range

A directed graph and its restricted numerical range.

Collaborators

Consider an unweighted directed graph (digraph) on n vertices. Setting w_{ij} = 1 if i j is an edge and 0 otherwise, the Laplacian matrix is defined by equation (1).

In the (undirected) graph case, which is to say i → j if and only if j → i, the eigenvalues of the graph Laplacian have been used to characterize graphs and have applications to data mining, image processing, Markov chain mixing, chromatic numbers, and much more. There has been far less success in the study of the digraph spectra, however, mainly due to the asymmetry of the Laplacian. There are some results, but most consider the adjacency matrix or the symmetrized Laplacian.

A value which often appears in fundamental theorems about graphs is the algebraic connectivity, defined simply as the second smallest eigenvalue of the graph Laplacian. The spectrum of a digraph Laplacian is generally complex, though, so care must be taken. In Algebraic connectivity of directed graphs, Wu defines the algebraic connectivity of a digraph by (2), where e is the all ones vector. He shows this definition extends many fundamental theorems about graphs to digraphs, and it remains one of the most useful quantities related to a digraph.

Motivated in part by its close connection to Wu's algebraic connectivity, we developed in On the restricted numerical range of the Laplacian matrix for digraphs the novel notion of the restricted numerical range (RNR) of a digraph Laplacian, which we define as (3).

Notably, the RNR is a convex set in the complex plane whose minimum real part is equal to the algebraic connectivity. The definition is clearly also motivated by the usual numerical range, which is known to capture information about both the eigenvalues and eigenspaces of a matrix. Since L(e) = 0 for any digraph, the restriction can be viewed as removing unspecific information from the usual numerical range. The remaining information, read as shape of of the RNR, can be enough to fully characterize the digraph structure:

Many digraphs have the same spectrum as some of the digraphs listed above, underscoring what makes the RNR so powerful and exciting: the ability to characterize digraphs that are not characterized by their spectrum. Regarding the usual numerical range as a generalized spectrum, we suspect that all digraphs characterized by their spectrum are also characterized by their RNR, making the RNR a more robust tool for this purpose. We also suspect, though, that a proof of this result will be highly non-trivial.

Having characterized all degenerate polygonal RNRs (singletons and lines), in the sequel On digraphs with polygonal restricted numerical range we provide computational methods for finding polygonal digraphs and show that they can be partitioned into three classes: 

Future research includes this class of pseudo-normal digraphs and the subclass of restricted-normal digraphs that are not directed joins, the aim being complete characterizations.

A digraph with its RNR. Notably, the RNR is not a polygon.

A non-polygonal digraph

A directed cycle on 6 vertices. Its RNR forms a pentagon.

A normal digraph

A digraph with its RNR. Notably, it is a polygon.

A restricted-normal digraph

A digraph with its RNR. Notably, it is a polygon.

A psuedo-normal digraph

Students:

I have several questions related to the above that are particularly well-suited for students looking forward to graduate degrees in mathematics or related fields, as this topic bridges the gap between tangible structural properties of graphs and abstract spectral properties of matrices. Some familiarity with linear algebra would be all that is required, as the digraph theory and other background could be learned as we go. If you have a strong interest in graph theory or matrix theory, I may have just the project for you!