Upper bounds on the independence and the clique covering number

New upper bounds for the independence number and for the clique covering number of a graph are given in terms of the rank, respectively the eigenvalues, of the adjacency matrix. We formulate a conjecture concerning an upper bound of the clique covering number. This upper bound is related to an old conjecture of Alan J. Hoffman which is shown to be false. Key words: adjacency matrix, eigenvalues, independence number, clique covering number. AMS classification: 05C.     

On graphs whose Laplacian matrices have distinct integer eigenvalues

In this paper, we investigate graphs for which the corresponding Laplacian matrix has distinct integer eigenvalues. We define the set S_i,n to be the set of all integers from 0 to n, excluding i. If there exists a graph whose Laplacian matrix has this set as its eigenvalues, we say that this set is Laplacian realizable. We investigate the sets S_i,n that are Laplacian realizable, and the structures of the graphs whose Laplacian matrix has such a set as its eigenvalues. We characterize those i < n such that S_i,n is Laplacian realizable, and show that for certain values of i, the set S_i,n is realized by a unique graph. Finally, we conjecture that S_n,n is not Laplacian realizable for n ≥ 2 and show that the conjecture holds for certain values of n. © 2005 Wiley Periodicals, Inc. J Graph Theory     

On eigenvalues and equivalent transformation of trigonometric matrices

This paper discusses some issues related to trigonometric matrices arising from the design of finite impulse response (FIR) digital filters. A conjecture on the eigenvalues of a trigonometric matrix is posed with a partial proof given. A new result is also presented on the related equivalent transformation of this trigonometric matrix into a diagonal matrix.     

On 3rd and 4th moments of finite upper half plane graphs

Terras [A. Terras, Fourier Analysis on Finite Groups and Applications, Cambridge Univ. Press, 1999] gave a conjecture on the distribution of the eigenvalues of finite upper half plane graphs. This is known as a finite analogue of Sato–Tate conjecture. There are several modified versions of them. In this paper, we show that this conjecture is not correct in its original form (i.e., Conjecture 1.1). This is shown for the calculations of the 3rd and 4th moments of the distribution of the eigenvalues. We remark that a weaker version of the conjecture (i.e., Conjecture 1.2) may still hold.     

Spectra of Some Interesting Combinatorial Matrices Related to Oriented Spanning Trees on a Directed Graph

The Laplacian of a directed graph G is the matrix L(G) = O(G) –, A(G) where A(G) is the adjaceney matrix of G and O(G) the diagonal matrix of vertex outdegrees. The eigenvalues of G are the eigenvalues of A(G). Given a directed graph G we construct a derived directed graph D(G) whose vertices are the oriented spanning trees of G. Using a counting argument, we describe the eigenvalues of D(G) and their multiplicities in terms of the eigenvalues of the induced subgraphs and the Laplacian matrix of G. Finally we compute the eigenvalues of D(G) for some specific directed graphs G. A recent conjecture of Propp for D(H _n ) follows, where H _n stands for the complete directed graph on n vertices without loops.     

Eigenvalues of the matching derangement graph

In this paper, we derive a formula for the eigenvalues of the matching derangement graph. The formula gives an insight regarding the alternating sign conjecture for the eigenvalues of the matching derangement graph. In particular, we show that the alternating sign property holds for certain partitions.     

Some notes on distribution of Hecke eigenvalues for Maass cusp forms

In this paper, we get some results on the distribution of Hecke eigenvalues for Maass cusp forms. We consider the diagonal version of Sato–Tate conjecture, a central limit theorem, and a quantitative result on the Ramanujan conjecture.     

Some inequalities and asymptotic formulas for eigenvalues on Riemannian manifolds

In this paper, we establish sharp inequalities for four kinds of classical eigenvalues in bounded domains of Riemannian manifolds. We also obtain the Weyl-type asymptotic formulas for the eigenvalues of the buckling and clamped plate problems in bounded domains of Riemannian manifolds. In addition, we give a negative answer to the Payne conjecture for the one-dimensional case.     

An Open Problem: Accumulation of Nonreal Eigenvalues of Indefinite Sturm–Liouville Operators

In this note we conjecture that the eigenvalues of singular indefinite Sturm–Liouville operators accumulate to the real axis whenever the eigenvalues of the corresponding definite Sturm–Liouville operator accumulate to the bottom of the essential spectrum from below.     

A Counterexample to the “Hot Spots” Conjecture on Nested Fractals

Although the “hot spots” conjecture was proved to be false on some classical domains, the problem still generates a lot of interests on identifying the domains that the conjecture hold. The question can also be asked on fractal sets that admit Laplacians. It is known that the conjecture holds on the Sierpinski gasket and its variants. In this note, we show surprisingly that the “hot spots” conjecture fails on the hexagasket, a typical nested fractal set. The technique we use is the spectral decimation method of eigenvalues of Laplacian on fractals.     

Eigenvalue computation for unitary rank structured matrices

In this paper we describe how to compute the eigenvalues of a unitary rank structured matrix in two steps. First we perform a reduction of the given matrix into Hessenberg form, next we compute the eigenvalues of this resulting Hessenberg matrix via an implicit QR-algorithm. Along the way, we explain how the knowledge of a certain ‘shift’ correction term to the structure can be used to speed up the QR-algorithm for unitary Hessenberg matrices, and how this observation was implicitly used in a paper due to William B. Gragg. We also treat an analogue of this observation in the Hermitian tridiagonal case.     

基于矩阵幂运算的重特征值存在性定理

对于判断矩阵重特征值的存在性问题,运用“若λ是矩阵A的特征值,则入“是Ak的特征值”这一性质,通过矩阵的迹与特征值的关系,得到了实数域上矩阵重特征值的存在性定理并给出了证明．定理实现了“由矩阵幂运算来判断矩阵重特征值的存在性”这样一个计算过程,对讨论矩阵特征值问题具有一定的启示意义．     

The eigenvalues of Kac's master equation

In this paper we derive formulae for the eigenvalues and spectral gap of the master equation for general collision kernels. We prove a conjecture of Mark Kac's on the existence of a spectral gap independent of the number of particles. We relate the eigenvalues to the “nonlinear” eigenvalues that occur in the exact solutions of model Boltzmann equations due to M. Ernst. Received: 30 November 2001; in final form: 26 March 2002/Published online: 2 December 2002     

Estimates of eigenvalues of the Laplacian by a reduced number of subsets

Chung–Grigor’yan–Yau’s inequality describes upper bounds of eigenvalues of the Laplacian in terms of subsets (“input”) and their volumes. In this paper we will show that we can reduce “input” in Chung–Grigor’yan–Yau’s inequality in the setting of Alexandrov spaces satisfying CD(0,∞). We will also discuss a related conjecture for some universal inequality among eigenvalues of the Laplacian.     

Some Interlacing Results for the Eigenvalues of Distance-regular graphs

In this paper we study the absolute values of non-trivial eigenvalues of a distance-regular graph and find that these usually have large absolute value. We also give a motivation concerning a conjecture of Bannai and Ito.     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

On the zeros of d-symmetric d-orthogonal polynomials

In this paper, we give some properties of the zeros of d-symmetric d-orthogonal polynomials and we localize these zeros on (d+1) rays emanating from the origin. We apply the obtained results to some known polynomials. In particular, we partially solve the conjecture about the zeros of the Humbert polynomials stated by Milovanovi? and Dordevi? [G.V. Milovanovi?, G.B. Dordevi?, On some properties of Humbert's polynomials, II, Ser. Math. Inform. 6 (1991) 23-30]. A study of the eigenvalues of a particular banded Hessenberg matrix is done.     

Numerical enclosure for multiple eigenvalues of an Hermitian matrix whose graph is a tree

In this paper we consider a numerical enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. If an Hermitian matrix A whose graph is a tree has multiple eigenvalues, it has the property that matrices which are associated with some branches in the undirected graph of A have the same eigenvalues. By using this property and interlacing inequalities for Hermitian matrices, we show an enclosure method for multiple eigenvalues of an Hermitian matrix whose graph is a tree. Since we do not generally know whether a given matrix has exactly a multiple eigenvalue from approximate computations, we use the property of interlacing inequalities to enclose some eigenvalues including multiplicities.In this process, we only use the enclosure of simple eigenvalues to enclose a multiple eigenvalue by using a computer and interval arithmetic.     

Geodesic spheres and two-point homogeneous spaces

In the Osserman conjecture and in the isoparametric conjecture it is stated that two-point homogeneous spaces may be characterized via the constancy of the eigenvalues of the Jacobi operator or the shape operator of geodesic spheres, respectively. These conjectures remain open, but in this paper we give complete positive results for similar statements about other symmetric endomorphism fields on small geodesic spheres. In addition, we derive more characteristic properties for this class of spaces by using other properties of small geodesic spheres. In particular, we study Riemannian manifolds with (curvature) homogeneous geodesic spheres. Supported by the Akademie der Naturforscher Leopoldina.     

On the energy and spectral properties of the He matrix of hexagonal systems

The He matrix, put forward by He and He in 1989, is designed as a means for uniquely representing the structure of a hexagonal system (= benzenoid graph). Observing that the He matrix is just the adjacency matrix of a pertinently weighted inner dual of the respective hexagonal system, we establish a number of its spectral properties. Afterwards, we discuss the number of eigenvalues equal to zero of the He matrix of a hexagonal system. Moreover, we obtain a relation between the number of triangles and the eigenvalues of the He matrix of a hexagonal system. Finally, we present an upper bound on the He energy of hexagonal systems.