On the multiplicity of the eigenvalues of a graph

Given a graph G with characteristic polynomial ϕ(t), we consider the ML-decomposition ϕ(t) = q ₁(t)q ₂(t)² ... q _m (t)^m, where each q _i (t) is an integral polynomial and the roots of ϕ(t) with multiplicity j are exactly the roots of q _j (t). We give an algorithm to construct the polynomials q _i (t) and describe some relations of their coefficients with other combinatorial invariants of G. In particular, we get new bounds for the energy E(G) = |λ_i| of G, where λ₁, λ₂, ..., λ_n are the eigenvalues of G (with multiplicity). Most of the results are proved for the more general situation of a Hermitian matrix whose characteristic polynomial has integral coefficients. This work was done during a visit of the second named author to UNAM.     

Matrices associated with arithmetical functions

Let f be an arithmetical function and S={x ₁,x ₂,…,x_n } a set of distinct positive integers. Denote by [f(x_i ,x_j }] the n×n matrix having f evaluated at the greatest common divisor (x_i ,x_j ) of x_i , and x_j as its i j-entry. We will determine conditions on f that will guarantee the matrix [f(x_i ,x_j )] is positive definite and, in fact, has properties similar to the greatest common divisor (GCD) matrix

[(x_i ,x_j )] where f is the identity function. The set S is gcd-closed if (x_i ,x_j )∈S for 1≤ i j ≤ n. If S is gcd-closed, we calculate the determinant and (if it is invertible) the inverse of the matrix [f(x_i ,x_j )]. Among the examples of determinants of this kind are H. J. S. Smith's determinant det[(i,j)].     

Multiplicative isometries on the Smirnov class

We show that T is a surjective multiplicative (but not necessarily linear) isometry from the Smirnov class on the open unit disk, the ball, or the polydisk onto itself, if and only if there exists a holomorphic automorphism Φ such that T(f)=f ○ Φ for every class element f or T(f) = [`(f<sup>°</sup> [`(j)] )]\overline {f^\circ \bar \varphi } for every class element f, where the automorphism Φ is a unitary transformation in the case of the ball and Φ(z ₁, ..., z _n ) = (l₁ z_i1 ,...,l_n z_in )(\lambda _1 z_{i_1 } ,...,\lambda _n z_{i_n } ) for |λ _j | = 1, 1 ≤ j ≤ n, and (i ₁; ..., i _n )is some permutation of the integers from 1through n in the case of the n-dimensional polydisk.     

Approximation of elements of a generalized Orlicz sequence space by nonlinear, singular kernels

Let l be a generalized Orlicz sequence space generated by a modular (x) = ∑_{i − 0}^∞ _i(¦t_i¦), X = (t_i), with s-convex functions _i, 0 < s 1, and let K_w,j: R₊ → R₊ for j=0,1,2,…, w ε Wwhere is an abstract set of indices. Assuming certain singularity assumptions on the nonlinear kernel K_w,j and setting T_wx = ((T_wx)_i)_{i = 0}^∞, with (T_wx)_i = ∑_{j = 0}ⁱ K_{w,i − j}(¦t_j¦) for x = (t_j), convergence results: T_wx → x in l are obtained (both modular convergence and norm convergence), with respect to a filter of subsets of the set .     

Positivity and conditional positivity of Loewner matrices

We give elementary proofs of the fact that the Loewner matrices [\fracf(p_i) - f (p_j)p_i-p_j]{[\frac{f(p_i) - f (p_j)}{p_i-p_j}]} corresponding to the function f(t) = t ^r on (0, ∞) are positive semidefinite, conditionally negative definite, and conditionally positive definite, for r in [0, 1], [1, 2], and [2, 3], respectively. We show that in contrast to the interval (0, ∞) the Loewner matrices corresponding to an operator convex function on (−1, 1) need not be conditionally negative definite.     

The bandwidth problem for graphs and matrices—a survey

The bandwidth problem for a graph G is to label its n vertices v_i with distinct integers f(v_i) so that the quantity max{| f(v_i) ? f(v_i)| : (v_i v_j) ∈ E(G)} is minimized. The corresponding problem for a real symmetric matrix M is to find a symmetric permutation M' of M so that the quantity max{| i ? j| : m'_ij ≠ 0} is minimized. This survey describes all the results known to the authors as of approximately August 1981. These results include the effect on bandwidth of local operations such as refinement and contraction of graphs, bounds on bandwidth in terms of other graph invariants, the bandwidth of special classes of graphs, and approximate bandwidth algorithms for graphs and matrices. The survey concludes with a brief discussion of some problems related to bandwidth.     

Non-induced isomorphisms of matrix rings

We give examples of distinct integersi, j, and ringsT for which the matrix ringsM _i (T) andM _j (T) are isomorphic as rings, but for which the free modules _T T ⁽ⁱ⁾ and _T T ⁽ⁱ⁾ are non-isomorphic asT-modules.     

Admissibility of the natural estimator of the mean of a Gaussian process

Let {X(t): t [a, b]} be a Gaussian process with mean μ L₂[a, b] and continuous covariance K(s, t). When estimating μ under the loss ∫_a^b ( (t)−μ(t))² dt the natural estimator X is admissible if K is unknown. If K is known, X is minimax with risk ∫_a^b K(t, t) dt and admissible if and only if the three by three matrix whose entries are K(t_i, t_j) has a determinant which vanishes identically in t_i [a, b], i = 1, 2, 3.     

Quasi-periodic solutions for the general semilinear Duffing equations with asymmetric nonlinearity and oscillating potential

In this paper,we prove the existence of quasi-periodic solutions and the boundedness of all the solutions of the general semilinear quasi-periodic differential equation x′′+ax~+-bx~-=G_x(x,t)+f (t),where x~+=max{x,0},x~-=max{-x,0},a and b are two different positive constants,f(t) is C~(39) smooth in t,G(x,t)is C~(35) smooth in x and t,f (t) and G(x,t) are quasi-periodic in t with the Diophantine frequency ω=(ω_1,ω_2),and D_x~iD_t~jG(x,t) is bounded for 0≤i+j≤35.     

A note on the stability of Jordan triple higher ring derivations

In the present paper, we establish the stability and the superstability of a functional inequality corresponding to the functional equation fn（xyx） = ∑i＋j＋k=n fi（x）fj （y）fk（x）. In addition, we take account of the problem of Jacobson radical ranges for such functional inequality.     

Padé-type approximants with orthogonal generating polynomials

The interpolation of the function x → 1/(1 ? xt) generating the series f(t) = ∑^∞_{i = 0}c_itⁱ at the zeros of an orthogonal polynomial with respect to a distribution d α satisfying some conditions will give us a process for accelerating the convergence of f_n(t) = ∑ⁿ_{i = 0}c_itⁱ. Then, we shall see that the polynomial of best approximation of x → 1/(1 ? xt) over some interval or its development in Chebyshev polynomials T_n or U_n are only particular cases of the main theorem.At last, we shall show that all these processes accelerate linear combinations with positive coefficients of totally monotonic and oscillating sequences.     

Sets of Double and Triple Weights of Trees

Let T be a weighted tree with n leaves numbered by the set {1, . . . , n}. Let D _{i, j} (T) be the distance between the leaves i and j. Let D_i,j,k(T) = \frac12(D_i,j(T)+D_j,k(T)+D_i,k(T)){{D_{i,j,k}(T) = \frac{1}{2}(D_{i,j}(T)+D_{j,k}(T)+D_{i,k}(T))}} . We will call such numbers “triple weights” of the tree. In this paper, we give a characterization, different from the previous ones, for sets indexed by 2-subsets of a n-set to be double weights of a tree. By using the same ideas, we find also necessary and sufficient conditions for a set of real numbers indexed by 3-subsets of an n-set to be the set of the triple weights of a tree with n leaves. Besides we propose a slight modification of Saitou-Nei’s Neighbour-Joining algorithm to reconstruct trees from the data D _{i, j} .     

Permanence and global stability in a Lotka-Volterra predator-prey system with delays

Consider the permanence and global asymptotic stability of models governed by the following Lotka-Volterra-type system:

, with initial conditions

x_i(t) = φ_i(t) ≥ o, t ≤ t₀, and φ_i(t₀) > 0. 1 ≤ i ≤n

. We define x₀(t) = x_n+1(t)≡0 and suppose that φ_i(t), 1 ≤ i ≤ n, are bounded continuous functions on [t₀, + ∞) and γ_i, α_i, c_i > 0,γ_i,j ≥ 0, for all relevant i,j.Extending a technique of Saito, Hara and Ma[1] for n = 2 to the above system for n ≥ 2, we offer sufficient conditions for permanence and global asymptotic stability of the solutions which improve the well-known result of Gopalsamy.     

Convex polytopes without triangular faces

LetP be a convexd-polytope without triangular 2-faces. Forj=0,…,d−1 denote byf _j(P) the number ofj-dimensional faces ofP. We prove the lower boundf _j(P)≥f _j(C _d) whereC _d is thed-cube, which has been conjectured by Y. Kupitz in 1980. We also show that for anyj equality is only attained for cubes. This result is a consequence of the far-reaching observation that such polytopes have pairs of disjoint facets. As a further application we show that there exists only one combinatorial type of such polytopes with exactly 2d+1 facets.     

Hyponormal Toeplitz Operators on the Weighted Bergman Space

Consider j = f +[`(g)]\varphi = f + \overline {g}, where f and g are polynomials, and let T_jT_{\varphi} be the Toeplitz operators with the symbol j\varphi. It is known that if T_jT_{\varphi} is hyponormal then |f￠(z)|² 3 |g￠(z)|²|f'(z)|^{2} \geq |g'(z)|^{2} on the unit circle in the complex plane. In this paper, we show that it is also a necessary and sufficient condition under certain assumptions. Furthermore, we present some necessary conditions for the hyponormality of T_jT_{\varphi} on the weighted Bergman space, which generalize the results of I. S. Hwang and J. Lee.     

Majorization of polynomials on the plane

We prove that for every χ[−1, 1] and every real algebraic polynomial f of degree n such that |f(t): 1 on [−1, 1], the following inequality takes place on the complex plane |f(x+iy)||T_n(1+iy)|,−∞y∞ where T_n is the Tchebycheff polynomial. This implies easily Vladimir Markov inequality.     

A Reflexivity Result Concerning Banach Space Operators with a Multiply Connected Spectrum

We consider a multiply connected domain Ω which is obtained by removing n closed disks which are centered at λ _j with radius r _j for j = 1, . . . , n from the unit disk. We assume that T is a bounded linear operator on a separable reflexive Banach space whose spectrum contains ∂Ω and does not contain the points λ₁, λ₂, . . . , λ _n , and the operators T and r _j (T − λ _j I)⁻¹ are polynomially bounded. Then either T has a nontrivial hyperinvariant subspace or the WOT-closure of the algebra {f(T) : f is a rational function with poles off [`(W)]{\overline\Omega}} is reflexive.     

A new class of symmetric polynomials defined in terms of tableaux

A new class of symmetric polynomials in n variables z = (z₁,…, z_n), denoted t_λ(z), and labelled by partitions λ = [λ₁ … λ_n] is defined in terms of standard tableaux (equivalently, in terms of Gel'fand-Weyl patterns of the general linear group GL(n,C)). The t_λ(z) are shown to be a -basis of the ring of all symmetric polynomials in n variables. In contrast to the usual basis sets such as the Schur functions e_λ(z), which are homogeneous polynomials in the z_i, the t_λ(z) are inhomogeneous. This property is reflected in the fact that the t_λ(z) are a natural basis for the expansion of certain (inhomogeneous) symmetric polynomials constructed from rising factorials. This and several other properties of the t_λ(z) are proved. Two generalizations of the t_λ(z) are also given. The first generalizes the t_λ(z) to a 1-parameter family of symmetric polynomials, T_λ(α; z), where α is an arbitrary parameter. The T_λ(α; z) are shown to possess properties similar to those of the t_λ(z). The second generalizes the t_λ(z) to a class of skew-tableau symmetric polynomials, t_λ/μ(z), for which only a few preliminary results are given.     

Divisibility of matrices associated with multiplicative functions

Let S={x₁,…,x_n} be a set of n distinct positive integers. For x,y∈S and y<x, we say the y is a greatest-type divisor of x in S if y∣x and it can be deduced that z=y from y∣z,z∣x,z<x and z∈S. For x∈S, let G_S(x) denote the set of all greatest-type divisors of x in S. For any arithmetic function f, let (f(x_i,x_j)) denote the n×n matrix having f evaluated at the greatest common divisor (x_i,x_j) of x_i and x_j as its i,j-entry and let (f[x_i,x_j]) denote the n×n matrix having f evaluated at the least common multiple [x_i,x_j] of x_i and x_j as its i,j-entry. In this paper, we assume that S is a gcd-closed set and . We show that if f is a multiplicative function such that (f∗μ)(d)∈Z whenever and f(a)|f(b) whenever a|b and a,b∈S and (f(x_i,x_j)) is nonsingular, then the matrix (f(x_i,x_j)) divides the matrix (f[x_i,x_j]) in the ring M_n(Z) of n×n matrices over the integers. As a consequence, we show that (f(x_i,x_j)) divides (f[x_i,x_j]) in the ring M_n(Z) if (f∗μ)(d)∈Z whenever and f is a completely multiplicative function such that (f(x_i,x_j)) is nonsingular. This confirms a conjecture of Hong raised in 2004.     

Clustering of linearly interacting diffusions and universality of their long-time limit distribution

Let K⊂ℝ ^d (d≥ 1) be a compact convex set and Λ a countable Abelian group. We study a stochastic process X in K ^Λ, equipped with the product topology, where each coordinate solves a SDE of the form dX _i (t) = ∑ _j a(j−i) (X _j (t) −X _i (t))dt + σ (X _i (t))dB _i (t). Here a(·) is the kernel of a continuous-time random walk on Λ and σ is a continuous root of a diffusion matrix w on K. If X(t) converges in distribution to a limit X(∞) and the symmetrized random walk with kernel a _S (i) = a(i) + a(−i) is recurrent, then each component X _i (∞) is concentrated on {x∈K : σ(x) = 0 and the coordinates agree, i.e., the system clusters. Both these statements fail if a _S is transient. Under the assumption that the class of harmonic functions of the diffusion matrix w is preserved under linear transformations of K, we show that the system clusters for all spatially ergodic initial conditions and we determine the limit distribution of the components. This distribution turns out to be universal in all recurrent kernels a _S on Abelian groups Λ. Received: 10 May 1999 / Revised version: 18 April 2000 / Published online: 22 November 2000