The Z-eigenvalues of a symmetric tensor and its application to spectral hypergraph theory

Guoyin Li, Liqun Qi, Gaohang Yu

Research output: Journal article publicationJournal articleAcademic researchpeer-review

81 Citations (Scopus)

Abstract

In this paper, using variational analysis and optimization techniques, we examine some fundamental analytic properties of Z-eigenvalues of a real symmetric tensor with even order. We first establish that the maximum Z-eigenvalue function is a continuous and convex function on the symmetric tensor space and so provide formulas of the convex conjugate function and ε-subdifferential of the maximum Z-eigenvalue function. Consequently, for an mth-order N-dimensional tensor A, we show that the normalized eigenspace associated with maximum Z-eigenvalue function is ρth-order Hölder stable at A with ρ=1m(3m-3)n-1-1. As a by-product, we also establish that the maximum Z-eigenvalue function is always at least ρth-order semismooth at A. As an application, we introduce the characteristic tensor of a hypergraph and show that the maximum Z-eigenvalue function of the associated characteristic tensor provides a natural link for the combinatorial structure and the analytic structure of the underlying hypergraph. Finally, we establish a variational formula for the second largest Z-eigenvalue for the characteristic tensor of a hypergraph and use it to provide lower bounds for the bipartition width of a hypergraph. Some numerical examples are also provided to show how one can compute the largest/second-largest Z-eigenvalue of a medium size tensor, using polynomial optimization techniques and our variational formula.
Original languageEnglish
Pages (from-to)1001-1029
Number of pages29
JournalNumerical Linear Algebra with Applications
Volume20
Issue number6
DOIs
Publication statusPublished - 1 Dec 2013

Keywords

  • Characteristic tensor
  • Maximum Z-eigenvalue
  • Polynomial optimization
  • Semismoothness
  • Spectral graph theory
  • Symmetric tensor

ASJC Scopus subject areas

  • Algebra and Number Theory
  • Applied Mathematics

Cite this