PaperlayerView exact revision on arXiv

Source-linked AI summary

Hermitian adjacency matrix of digraphs and mixed graphs

Krystal Guo, Bojan Mohar

arXiv:1505.01321v1math.CO

TL;DR

Spectral results for digraphs are sparse because standard adjacency choices lose either symmetry or broad applicability. The paper uses a Hermitian adjacency matrix that supports directed and mixed graphs, then develops its spectral theory and consequences, including cospectral constructions and classifications for small H-eigenvalues.

  • Problem

    Eigenvalue results for digraphs are sparse because the usual adjacency matrix is nonsymmetric, while the skew-symmetric alternative applies only to oriented graphs.

  • Method

    The paper develops basic spectral theory for a Hermitian adjacency matrix whose entries encode one-way arcs with ±i and digons with 1, extending to mixed graphs.

  • Results

    The paper establishes real eigenvalues and interlacing, studies spectral-radius differences, derives spectral bounds and spectrum-preserving operations, and classifies digraphs with H-eigenvalues in (−α, α) for 0 ≤ α ≤ √3.

  • Takeaways & Limitations

    Hermitian spectra retain enough structure to yield combinatorial bounds, characterize small-spectrum digraphs, and expose extensive cospectrality despite unintuitive behavior.

  • Takeaways & Limitations

    There is no apparent bound on diameter in terms of the number of distinct H-eigenvalues, since strongly connected digraphs can have constantly many distinct eigenvalues and unbounded diameter.

Abstract

from arXiv · show

The paper gives a thorough introduction to spectra of digraphs via its Hermitian adjacency matrix. This matrix is indexed by the vertices of the digraph, and the entry corresponding to an arc from $x$ to $y$ is equal to the complex unity $i$ (and its symmetric entry is $-i$) if the reverse arc $yx$ is not present. We also allow arcs in both directions and unoriented edges, in which case we use $1$ as the entry. This allows to use the definition also for mixed graphs. This matrix has many nice properties; it has real eigenvalues and the interlacing theorem holds for a digraph and its induced subdigraphs. Besides covering the basic properties, we discuss many differences from the properties of eigenvalues of undirected graphs and develop basic theory. The main novel results include the following. Several surprising facts are discovered about the spectral radius; some consequences of the interlacing property are obtained; operations that preserve the spectrum are discussed -- they give rise to an incredible number of cospectral digraphs; for every $0\leα\le\sqrt{3}$, all digraphs whose spectrum is contained in the interval $(-α,α)$ are determined.

1 Introduction

The paper motivates the Hermitian adjacency matrix as a way to recover useful spectral properties for digraphs while accommodating directed and mixed edges. It develops basic theory, including spectral-radius phenomena, interlacing consequences, cospectrality, and classifications of digraphs with small H-eigenvalues.

  • Motivation: Eigenvalue results for digraphs are sparse because no associated matrix had clearly captured interesting combinatorial properties while preserving real eigenvalues.The ordinary adjacency matrix is nonsymmetric, while the skew-symmetric alternative applies only to oriented graphs.
  • Hermitian adjacency matrix: The Hermitian adjacency matrix is Hermitian and retains useful undirected-graph properties, including eigenvalue interlacing for induced subdigraphs.Its entries encode one-way arcs with i and −i, while digons use 1; the definition also extends to mixed graphs.
  • Basic theory: The paper studies spectral-radius behavior and shows that several properties inherited from Perron–Frobenius theory can fail for Hermitian adjacency matrices.In particular, the spectral radius can equal the absolute value of the smallest eigenvalue rather than the largest eigenvalue.
  • Interlacing consequences: Interlacing yields spectral bounds for the maximum independent set and maximum acyclic subgraphs of oriented graphs.These consequences are developed in the paper’s treatment of interlacing.
  • Cospectral digraphs: Spectrum-preserving switching operations generate many cospectral digraphs; orientations of an undirected graph of order n usually contain up to 2^n non-isomorphic mutually cospectral digraphs.The paper also discusses why cospectral pairs are not rare.

2 Definitions

This section defines digraphs, mixed graphs, and their Hermitian adjacency matrices, then establishes the real, orthogonally diagonalizable H-spectrum and related notation.

  • Digraphs and underlying graphs: A digraph is a finite vertex set together with ordered pairs called arcs; a pair containing both opposite arcs is a digon.The underlying graph replaces directed adjacency by an undirected edge between incident vertices.
  • Mixed graphs: Mixed graphs allow both directed and undirected edges, with undirected edges represented as digons in the paper’s digraph framework.Thus mixed graphs are treated through the same Hermitian adjacency construction.
  • Hermitian adjacency matrix: The Hermitian adjacency entry is 1 for a digon, i for a one-way arc u→v, −i for the reverse orientation, and 0 otherwise.The multigraph version combines undirected-edge and directed-arc multiplicities in the entry a + bi − ci.
  • H-spectrum: Because H is Hermitian, all H-eigenvalues are real and H has n pairwise orthogonal eigenvectors, making it unitarily similar to a diagonal matrix.The multiset of these eigenvalues is the H-spectrum.
  • Spectral notation: The eigenvalues are ordered decreasingly as λ1(X) ≥ λ2(X) ≥ ··· ≥ λn(X), and H-cospectral digraphs have identical characteristic polynomials.The section also introduces the characteristic polynomial and the min-max formula for λj(X).

3 Basic properties

The paper develops coefficient, walk, and structural tools for the Hermitian spectrum of digraphs. These tools connect characteristic-polynomial data to underlying-graph structure and yield spectral invariance and eigenvector criteria.

  • Characteristic polynomial: The coefficient of t^(n−2) in φ(H(X), t) is −e, where e is the number of edges in the underlying graph.This follows because the diagonal entries of H^2 equal vertex degrees in the underlying graph.
  • Characteristic polynomial: Characteristic-polynomial coefficients can be expressed through basic subgraphs of the underlying graph, whose components are edges or cycles satisfying an even directed-edge condition.The resulting Sachs-type expansion sums contributions over basic subgraphs.
  • Spectral invariance: If a digon is a cut-edge of the underlying graph, replacing it by either single orientation leaves the H-spectrum unchanged.This gives a concrete spectrum-preserving operation.
  • Walks and traces: Entries of H(X)^k are weighted sums over length-k walks in the underlying graph, with walk weights given by products of Hermitian adjacency entries.The walk formulation is used to express tr(H(X)^3) through triangle subdigraphs.
  • Walks and traces: The trace of H(X)^3 is determined by induced triangle types with an even number of non-digon arcs, because odd-arc contributions cancel.Figure 1 lists the non-isomorphic triangle types used in this calculation.
  • Eigenvectors and structure: The all-ones vector is an eigenvector of H(X) exactly when the symmetric subgraph G(X) is regular and the asymmetric subdigraph D(X) is eulerian.G(X) contains the digons, while D(X) contains arcs not belonging to digons.

4 Interlacing

The paper develops eigenvalue interlacing for Hermitian adjacency matrices and applies it to induced subdigraphs, vertex partitions, and spectral bounds. These tools yield constraints on eigenvalue signs, transitive tournaments, and quotient matrices.

  • Induced subdigraphs: The eigenvalues of any induced subdigraph interlace those of the digraph.This follows from the principal-submatrix interlacing theorem for Hermitian matrices.
  • Eigenvalue signs: A digraph containing m vertices with no digons has at least ⌈m/2⌉ non-negative and ⌊m/2⌋ non-positive H-eigenvalues.The argument uses symmetry of the eigenvalues of the corresponding principal submatrix and interlacing.
  • Eigenvalue signs: If X has an independent set of size α, then η+(X) ≥ α and η−(X) ≥ α.Interlacing supplies at least α non-negative and α non-positive H-eigenvalues.
  • Transitive tournaments: An oriented graph attains the stated spectral-radius bound exactly when it is switching-equivalent to the transitive tournament T_n.The result gives a characterization of equality for the bound on oriented graphs.
  • Transitive tournaments: If X contains an induced subdigraph switching-equivalent to T_m, then λ1(H(X)) is bounded below by the corresponding tournament value.Consequently, sufficiently large m are excluded when the largest H-eigenvalue is fixed.
  • Quotient matrices: Eigenvalues of a quotient matrix interlace those of H(X), and equitable partitions transfer quotient eigenvalues to H(X) with at least the same multiplicity.These statements extend to digraphs with multiple edges.

5 Spectral radius

The paper studies the spectral radius of the Hermitian adjacency matrix, highlighting that its largest eigenvalue can behave differently from the spectral radius. It proves a maximum-degree bound and characterizes equality for weakly connected digraphs.

  • Differences from undirected graphs: The largest H-eigenvalue need not be simple or largest in magnitude: a strongly connected 3-vertex digraph has eigenvalues {1^(2), −2}.Thus the spectral radius can be attained by a negative eigenvalue rather than λ1.
  • Bound and equality: ρ(X) ≤ ∆(Γ(X)) for every digraph, including digraphs with multiple edges.For weakly connected X, equality requires a ∆(Γ(X))-regular underlying graph and one of two four-part vertex structures.
  • Bound and equality: When equality holds, vertices can be partitioned into V1, V−1, Vi, and V−i with either digon-only parts and cross-part arcs or independent parts with specified digon and arc patterns.These are the two cases in Theorem 5.1.
  • Bound and equality: The equality structures produce an eigenvector with eigenvalue ±k when the underlying graph is k-regular.The vector assigns values from {1, −1, i, −i} according to the four vertex parts.
  • Differences from undirected graphs: Unlike undirected graphs, a digraph can have spectral radius smaller than the minimum degree of its underlying graph.The cited example has eigenvalues ±√3 and 0 while its underlying graph has minimum degree 2.

Digraphs with spectrum {−(n −1), 1(n−1)}

The paper identifies K′3 and K′4 as the only non-trivial digraphs with spectrum {−(n−1), 1(n−1)}, establishing an extreme negative-eigenvalue case. It also develops constructions and bounds showing how far spectral radius can diverge from the largest eigenvalue.

  • Characterization: K′3 and K′4 are the only non-trivial digraphs whose H-spectrum has one large negative eigenvalue and n−1 small positive eigenvalues.Their spectra are reported as {−2, 1(2)} and {−3, 1(3)}, respectively.
  • Characterization: The complete classification for spectrum {−(n−1), (−1)(n−1)} includes only K1, K2, T2, K′3, and K′4.T2 is the oriented K2.
  • Proof strategy: For n≥3, matching characteristic-polynomial coefficients forces the underlying graph of any classified digraph to be complete.The coefficient of t^(n−2) determines that Γ(X) has the same number of edges as Kn.
  • Large negative eigenvalues: The family X(a,b) is analyzed through an equitable partition into X, Y, and Z, reducing part of the eigenvalue calculation to a quotient matrix.The quotient characteristic polynomial factors as (t−1)(t^2+t−2ab).
  • Large negative eigenvalues: The Cartesian product adds H-eigenvalues pairwise, so n-fold products of X produce spectra with ρ(X^n)=3^n and λ1(X^n)=n.This construction makes the gap between spectral radius and largest eigenvalue grow with n.
  • Spectral-radius bounds: For every digraph, the spectral radius is bounded by the spectral radius of its underlying graph, and the principal inequalities in Theorem 5.6 are tight.The proof decomposes H into the digon matrix A and non-digon matrix L.

6 H-Eigenvalues symmetric about 0

The paper studies when H-eigenvalues are symmetric about 0, proving several sufficient conditions while showing that bipartiteness and orientation are not necessary. A simple combinatorial characterization remains unknown.

  • Sufficient conditions: If the underlying graph Γ(X) is bipartite, then the H-eigenvalues of X are symmetric about 0.This extends the familiar bipartite spectral symmetry condition to the Hermitian adjacency setting.
  • Counterexamples: The converse of the bipartite condition fails: fC3 has symmetric H-eigenvalues despite having a non-bipartite underlying graph.Its eigenvalues include ±3 and 0.
  • Sufficient conditions: Every oriented graph has an H-spectrum symmetric about 0.The proof uses the fact that iH is skew-symmetric with purely imaginary eigenvalues and has a characteristic polynomial with real coefficients.
  • Counterexamples: Order-4 examples show that spectral symmetry can occur in digraphs that are neither oriented nor bipartite.Computationally, exactly seven H-cospectral classes with symmetric spectra were found at order 4; one contains 15 non-isomorphic digraphs with underlying graph K4.
  • Sufficient conditions: If every odd cycle of Γ(X) contains an even number of digons, then the H-spectrum is symmetric about 0.This condition generalizes the bipartite and oriented-graph sufficient conditions.
  • Open boundary: A simple combinatorial characterization of digraphs with H-eigenvalues symmetric about 0 is not known.The order-4 computational results demonstrate the diversity of such examples but do not provide a general characterization.

7 C∗-algebra of a digraph

The paper contrasts Hermitian spectra with the adjacency-matrix diameter relationship and constructs an infinite family showing that few H-eigenvalues do not bound diameter. It also analyzes necklace digraphs through a polynomial identity to determine their spectrum.

  • Diameter and distinct eigenvalues: The modified directed cycle f C4 has exactly two distinct H-eigenvalues, while its underlying graph has diameter 2.It is obtained from a directed cycle by reversing one arc.
  • Necklace digraphs: For every n ≥3, the necklace digraph Nn satisfies the Hermitian-matrix identity H3 = 4H.The proof reduces the verification to pairs of vertices at underlying-graph distances 1 and 3, since other entries of H3 vanish.
  • Necklace digraphs: The H-spectrum of Nn is {0^(n), 2^(n), −2^(n)}.The identity H3 = 4H gives the distinct eigenvalues 0, 2, and −2; trace calculations determine each multiplicity as n.
  • Diameter and distinct eigenvalues: An infinite family of digraphs has diameters tending to infinity while each graph has only three distinct H-eigenvalues.This shows that the adjacency-matrix diameter bound does not carry over to the Hermitian adjacency matrix.

8 Cospectrality

The paper develops spectrum-preserving operations for digraphs and shows that H-cospectrality can conceal substantial structural differences. It characterizes several cospectral families, including graphs sharing complete-graph or cycle spectra and examples with different connectivity.

  • Structural consequences: H-cospectral digraphs can have different connectivity: one example is strongly connected, one weakly connected but not strongly connected, and one not weakly connected.The three digraphs have the same characteristic polynomial.
  • Spectrum-preserving operations: Local reversal preserves H-cospectrality when the cut δ(S) contains no digons.The proof uses a diagonal matrix with entries −1 on S and +1 outside S, making the transformed matrices similar.
  • Spectrum-preserving operations: Four-way switching preserves the H-spectrum for any admissible four-partition of the vertex set.The operation is implemented by a diagonal similarity transformation whose diagonal entries are in {±1, ±i}.
  • Cospectral classes: For each n, precisely n non-isomorphic digraphs share the H-spectrum of Kn: Kn and Ya,n−a for a = 1, …, n−1.This contrasts with the undirected case, where complete graphs are determined by their spectrum.
  • Cycle cospectrality: Every orientation of an odd cycle is H-cospectral with every other orientation, while even-cycle orientations reduce to two local-reversal classes.For even n, the spectra of Dn and eCn are distinct.

9 Digraphs with small spectral radius

The section characterizes digraphs with tightly bounded Hermitian eigenvalues using interlacing and small induced subdigraphs. It also identifies structural boundaries where finiteness or diameter control fails.

  • General classification: Interlacing reduces the classification of small-spectral-radius digraphs to constraints on their induced subdigraphs.The proof examines all digraphs on three vertices and excludes triangles, high-degree vertices, long paths, and long cycles.
  • Eigenvalues in {−1, 1}: H-eigenvalues restricted to {−1, 1} characterize digraphs whose underlying graph is a disjoint union of edges.Equivalently, every component is a single arc, a digon, or an isolated vertex.
  • General classification: For spectral radius below √3, each underlying component is a path of length at most 3, C4 with a specified orientation pattern, or one of two strongly connected digraphs with two digons.The C4 cases are represented by three digraphs, including the oriented C4 and two strongly connected variants.
  • Bounds and scope: There are infinitely many weakly connected digraphs with all H-eigenvalues in (−2, 2), while finiteness is established for the stricter interval (−√3, √3).The text suggests, but does not establish, that the same finiteness property may hold for every α with 0 ≤ α < 2.

10 Examples

The examples use computation and skew-circulant methods to obtain Hermitian spectra for small digraphs, reversed directed cycles, and transitive tournaments. They also identify explicit cospectrality and eigenvalue formulas.

  • Small digraphs: Sage computations enumerate adjacency and Hermitian spectra for all isomorphism classes of digraphs on 2 through 6 vertices.The resulting data are presented in tables for comparison between the two matrix choices.
  • Directed cycles: Reversing one arc of a directed cycle produces eC_n, which is A-cospectral with D_n when n is odd.The paper computes H-eigenvalues of eC_n using skew-circulant matrix results.
  • Skew-circulant matrices: For symmetric coefficients a_k = a_{n−k}, Corollary 10.3 gives explicit skew-circulant eigenvalues, with separate formulas for odd and even n.The even case includes an additional contribution from the middle coefficient.
  • Directed cycles: The H-eigenvalues of eC_n are given explicitly by a sine formula derived from the skew-circulant representation.The calculation applies Corollary 10.3 to the coefficient vector with a_1 = a_{n−1} = 1.
  • Transitive tournaments: Transitive tournaments are modeled by H_n = H(T_n), and their eigenvalues follow from treating the associated matrix as skew-symmetric and skew-circulant.The paper gives separate expressions for odd and even n.
Loading 1505.01321v1…