More bounds for elgenvalues using traces

Let the n × n complex matrix A have complex eigenvalues λ₁,λ₂,…λ_n. Upper and lower bounds for Σ(Reλ_i)² are obtained, extending similar bounds for Σ|λ_i|² obtained by Eberlein (1965), Henrici (1962), and Kress, de Vries, and Wegmann (1974). These bounds involve the traces of A¹A, B², C², and D², where $\text{B}\text{=}\text{1}\text{2}\text{(}\text{A}\text{+}\text{A}{}^1\text{)}$, $\text{C}\text{=}\text{1}\text{2}\text{(}\text{A}\text{?}\text{A}{}^1\text{) /i}$, and $\text{D}\text{=}\text{AA}{}^1\text{?}\text{A}{}^1\text{A}$, and strengthen some of the results in our earlier paper “Bounds for eigenvalues using traces” in Linear Algebra and Appl. [12].     

The bounds of restricted isometry constants for low rank matrices recovery

This paper discusses conditions under which the solution of linear system with minimal Schatten-p norm, 0 < p ? 1, is also the lowest-rank solution of this linear system. To study this problem, an important tool is the restricted isometry constant (RIC). Some papers provided the upper bounds of RIC to guarantee that the nuclear-norm minimization stably recovers a low-rank matrix. For example, Fazel improved the upper bounds to δ _4r ^A < 0.558 and δ _3r ^A < 0.4721, respectively. Recently, the upper bounds of RIC can be improved to δ _2r ^A < 0.307. In fact, by using some methods, the upper bounds of RIC can be improved to δ _2r ^A < 0.4931 and δ _2r ^A < 0.309. In this paper, we focus on the lower bounds of RIC, we show that there exists linear maps A with δ _2r ^A > 1/√2 or δ _r ^A > 1/3 for which nuclear norm recovery fail on some matrix with rank at most r. These results indicate that there is only a little limited room for improving the upper bounds for δ _2r ^A and δ _r ^A . Furthermore, we also discuss the upper bound of restricted isometry constant associated with linear maps A for Schatten p (0 < p < 1) quasi norm minimization problem.     

Some lower bounds for the spectral radius of matrices using traces

Let A be an n×n matrix with eigenvalues λ₁,λ₂,…,λ_n, and let m be an integer satisfying rank(A)?m?n. If A is real, the best possible lower bound for its spectral radius in terms of m, trA and trA² is obtained. If A is any complex matrix, two lower bounds for are compared, and furthermore a new lower bound for the spectral radius is given only in terms of trA,trA²,‖A‖,‖A^∗A-AA^∗‖,n and m.     

Lower bounds for the minimum eigenvalue of Hadamard product of an M-matrix and its inverse

For the Hadamard product A ° A⁻¹ of an M-matrix A and its inverse A⁻¹, we give new lower bounds for the minimum eigenvalue of A ° A⁻¹. These bounds are strong enough to prove the conjecture of Fiedler and Markham [An inequality for the Hadamard product of an M-matrix and inverse M-matrix, Linear Algebra Appl. 101 (1988) 1-8].     

New perturbation bounds for the W-weighted Drazin inverse

The constructive perturbation bounds for the W-weighted Drazin inverse are derived by two approaches in this paper. One uses the matrixG = [(A+E)W]^l?(AW)^l, whereA, E ∈ C ^mxn ,W ∈ C ^nxm ,l = max Ind(AW), Ind[(A + E)W]. The other uses a technique proposed by G. Stewart and based on perturbation theory for invariant subspaces of a matrix. The new approaches to develop perturbation bounds for W-weighted Drazin inverse of a matrix extend the previous results in [19, 29, 31, 36, 42, 44]. Several examples which indicate the sharpness of the new perturbation bounds are presented.     

Pertubation bounds for the definite generalized eigenvalue problem

Let A and B be Hermitian matrices, and let c(A, B) = inf{|x^H(A + iB)x|:6 = 1}. The eigenvalue problem Ax = λBx is called definite if c(A, B)>0. It is shown that a definite problem has a complete system of eigenvectors and that its eigenvalues are real. Under pertubations of A and B, the eigenvalues behave like the eigenvalues of a Hermitian matrix in the sense that there is a 1-1 pairing of the eigenvalues with the perturbed eigenvalues and a uniform bound for their differences (in this case in the chordal metric). Pertubation bounds are also developed for eigenvectors and eigenspaces.     

Some closer bounds of Perron root basing on generalized Perron complement

This paper is concerned with the bounds of the Perron root ρ(A) of a nonnegative irreducible matrix A. Two new methods utilizing the relationship between the Perron root of a nonnegative irreducible matrix and its generalized Perron complements are presented. The former method is efficient because it gives the bounds for ρ(A) only by calculating the row sums of the generalized Perron complement P_t(A/A[α]) or even the row sums of submatrices A[α],A[β],A[α,β] and A[β,α]. And the latter gives the closest bounds (just in this paper) of ρ(A). The results obtained by these methods largely improve the classical bounds. Numerical examples are given to illustrate the procedure and compare it with others, which shows that these methods are effective.     

Some refined bounds for the perturbation of the orthogonal projection and the generalized inverse

In this paper, we consider the perturbation of the orthogonal projection and the generalized inverse for an n × n matrix A and present some perturbation bounds for the orthogonal projections on the rang spaces of A and A^?, respectively. A combined bound for the orthogonal projection on the rang spaces of A and A^? is also given. The proposed bounds are sharper than the existing ones. From the combined bounds of the orthogonal projection on the rang spaces of A and A^?, we derived new perturbation bounds for the generalized inverse, which always improve the existing ones. The combined perturbation bound for the orthogonal projection and the generalized inverse is also given. Some numerical examples are given to show the advantage of the new bounds.     

Improving the bounds of the multiplicity conjecture: The codimension 3 level case

The Multiplicity Conjecture (MC) of Huneke and Srinivasan provides upper and lower bounds for the multiplicity of a Cohen-Macaulay algebra A in terms of the shifts appearing in the modules of the minimal free resolution (MFR) of A. All the examples studied so far have lead to conjecture (see [J. Herzog, X. Zheng, Notes on the multiplicity conjecture. Collect. Math. 57 (2006) 211-226] and [J. Migliore, U. Nagel, T. Römer, Extensions of the multiplicity conjecture, Trans. Amer. Math. Soc. (preprint: math.AC/0505229) (in press)]) that, moreover, the bounds of the MC are sharp if and only if A has a pure MFR. Therefore, it seems a reasonable-and useful-idea to seek better, if possibly ad hoc, bounds for particular classes of Cohen-Macaulay algebras.In this work we will only consider the codimension 3 case. In the first part we will stick to the bounds of the MC, and show that they hold for those algebras whose h-vector is that of a compressed algebra.In the second part, we will (mainly) focus on the level case: we will construct new conjectural upper and lower bounds for the multiplicity of a codimension 3 level algebra A, which can be expressed exclusively in terms of the h-vector of A, and which are better than (or equal to) those provided by the MC. Also, our bounds can be sharp even when the MFR of A is not pure.Even though proving our bounds still appears too difficult a task in general, we are already able to show them for some interesting classes of codimension 3 level algebras A: namely, when A is compressed, or when its h-vector h(A) ends with (…,3,2). Also, we will prove our lower bound when h(A) begins with (1,3,h₂,…), where h₂≤4, and our upper bound when h(A) ends with (…,h_c−1,h_c), where h_c−1≤h_c+1.     

Cones and error bounds for linear iterations

Consider an ordered Banach space with a cone of positive elementsK and a norm ∥·∥. Let [a,b] denote an order-interval; under mild conditions, ifx*∈[a,b] then $$||x * - \tfrac{1}{2}(a + b)|| \leqslant \tfrac{1}{2}||b - a||.$$ This inequality is used to generate error bounds in norm, which provide on-line exit criteria, for iterations of the type $$x_r = Ax_{r - 1} + a,A = A^ + + A^ - ,$$ whereA ⁺ andA ^? are bounded linear operators, withA ⁺ K ?K andA ^? K ? ?K. Under certain conditions, the error bounds have the form $$\begin{gathered} ||x * - x_r || \leqslant ||y_r ||,y_r = (A^ + - A^ - )y_{r - 1} , \hfill \\ ||x * - x_r || \leqslant \alpha ||\nabla x_r ||, \hfill \\ ||x * - \tfrac{1}{2}(x_r + x_{r - 1} )|| \leqslant \tfrac{1}{2}||\nabla x_r ||. \hfill \\ \end{gathered} $$ These bounds can be used on iterative methods which result from proper splittings of rectangular matrices. Specific applications with respect to certain polyhedral cones are given to the classical Jacobi and Gauss-Seidel splittings.     

Singular initial data and uniform global bounds for the hyper-viscous Navier-Stokes equation with periodic boundary conditions

In the hyper-viscous Navier-Stokes equations of incompressible flow, the operator A=−Δ is replaced by A_α,a,b≡aA^α+bA for real numbers α,a,b with α?1 and b?0. We treat here the case a>0 and equip A (and hence A_α,a,b) with periodic boundary conditions over a rectangular solid Ω⊂Rn. For initial data in Lp(Ω) with α?n/(2p)+1/2 we establish local existence and uniqueness of strong solutions, generalizing a result of Giga/Miyakawa for α=1 and b=0. Specializing to the case p=2, which holds a particular physical relevance in terms of the total energy of the system, it is somewhat interesting to note that the condition α?n/4+1/2 is sufficient also to establish global existence of these unique regular solutions and uniform higher-order bounds. For the borderline case α=n/4+1/2 we generalize standard existing (for n=3) “folklore” results and use energy techniques and Gronwall's inequality to obtain first a time-dependent H^α-bound, and then convert to a time-independent global exponential H^α-bound. This is to be expected, given that uniform bounds already exist for n=2,α=1 ([6, pp. 78-79]), and the folklore bounds already suggest that the α?n/4+1/2 cases for n?3 should behave as well as the n=2 case. What is slightly less expected is that the n?3 cases are easier to prove and give better bounds, e.g. the uniform bound for n?3 depends on the square of the data in the exponential rather than the fourth power for n=2. More significantly, for α>n/4+1/2 we use our own entirely semigroup techniques to obtain uniform global bounds which bootstrap directly from the uniform L²-estimate and are algebraic in terms of the uniform L²-bounds on the initial and forcing data. The integer powers on the square of the data increase without bound as α↓n/4+1/2, thus “anticipating” the exponential bound in the borderline case α=n/4+1/2. We prove our results for the case a=1 and b=0; the general case with a>0 and b?0 can be recovered by using norm-equivalence. We note that the hyperviscous Navier-Stokes equations have both physical and numerical application.     

Upper bounds for the order of an additive basis obtained by removing a finite subset of a given basis

Let A be an additive basis of order h and X be a finite nonempty subset of A such that the set A?X is still a basis. In this article, we give several upper bounds for the order of A?X in function of the order h of A and some parameters related to X and A. If the parameter in question is the cardinality of X, Nathanson and Nash already obtained some of such upper bounds, which can be seen as polynomials in h with degree (|X|+1). Here, by taking instead of the cardinality of X the parameter defined by , we show that the order of A?X is bounded above by . As a consequence, we deduce that if X is an arithmetic progression of length ?3, then the upper bounds of Nathanson and Nash are considerably improved. Further, by considering more complex parameters related to both X and A, we get upper bounds which are polynomials in h with degree only 2.     

Combinatorial bounds on Hilbert functions of fat points in projective space

We study Hilbert functions of certain non-reduced schemes A supported at finite sets of points in , in particular, fat point schemes. We give combinatorially defined upper and lower bounds for the Hilbert function of A using nothing more than the multiplicities of the points and information about which subsets of the points are linearly dependent. When N=2, we give these bounds explicitly and we give a sufficient criterion for the upper and lower bounds to be equal. When this criterion is satisfied, we give both a simple formula for the Hilbert function and combinatorially defined upper and lower bounds on the graded Betti numbers for the ideal I_A defining A, generalizing results of Geramita et al. (2006) [16]. We obtain the exact Hilbert functions and graded Betti numbers for many families of examples, interesting combinatorially, geometrically, and algebraically. Our method works in any characteristic.     

Perturbation bounds for the Cholesky andQR factorizations

LetA, A+E be Hermitian positive definite matrices. Suppose thatA=LL ^H andA+E=(L+G)(L+G)^H are the Cholesky factorizations ofA andA+E, respectively. In this paper lower bounds and upper bounds on |G|/|L| in terms of |E|/|A| are given. Moreover, perturbation bounds are given for the QR factorization of a complexm ×n matrixA of rankn.This research was supported by the National Science Foundation of China and the Department of Mathematics of Linköping University in Sweden.     

Lower bounds on the minimum average distance of binary codes

Let β(n,M) denote the minimum average Hamming distance of a binary code of length n and cardinality M. In this paper we consider lower bounds on β(n,M). All the known lower bounds on β(n,M) are useful when M is at least of size about 2ⁿ⁻¹/n. We derive new lower bounds which give good estimations when size of M is about n. These bounds are obtained using a linear programming approach. In particular, it is proved that lim_n→∞β(n,2n)=5/2. We also give a new recursive inequality for β(n,M).     

Heat kernel bounds and desingularizing weights

We study the parabolic operator ∂_t−Δ_x+V(t,x), in d?1, with a potential V=V+−V−,V±?0 assumed to be from a parabolic Kato class, and obtain two-sided Gaussian bounds on the associated heat kernel. The constraints on the Kato norms of V⁺ and V⁻ are completely asymmetric, as they should be. Further improvements to our heat kernel bounds are obtained in the case of time-independent potentials.If V has singularities of the type ±c|x|⁻² with a suitably small constant c, we obtain new lower and (sharp) upper weighted heat kernel bounds. The rate of growth of the weights depends (explicitly) on the constant c. The standard bounds and methods (estimates in L^p-spaces without desingularizing weights) fail for singular potentials.     

Computing bounds for the probability of the union of events by different methods

Let A ₁,??,A _n be arbitrary events. The underlying problem is to give lower and upper bounds on the probability P(A ₁?????A _n ) based on $P(A_{i_{1}}\cap\cdots\cap A_{i_{k}})$ , 1??i ₁<?<i _k ??n, where k=1,??,d, and d??n (usually d?n) is a certain integer, called the order of the problem or the bound. Most bounding techniques fall in one of the following two main categories: those that use (hyper)graph structures and the ones based on binomial moment problems. In this paper we compare bounds from the two categories with each other, in particular the bounds yielded by univariate and multivariate moment problems are compared with Bukszár??s hypermultitree bounds. In the comparison we considered several numerical examples, most of which have important practical applications, e.g., the approximation of the values of multivariate cumulative distribution functions or the calculation of network reliability. We compare the bounds based on how close they are to the real value and the time required to compute them, however, the problems arising in the implementations of the methods as well as the limitations of the usability of the bounds are also illustrated.     

Gaussian bounds for degenerate parabolic equations

Let A be a real symmetric, degenerate elliptic matrix whose degeneracy is controlled by a weight w in the A₂ or QC class. We show that there is a heat kernel Wt(x,y) associated to the parabolic equation wut=divA∇u, and Wt satisfies classic Gaussian bounds:

     

New lower bounds for Hopcroft's problem

We establish new lower bounds on the complexity of the following basic geometric problem, attributed to John Hopcroft: Given a set ofn points andm hyperplanes in $\mathbb{R}^d $ , is any point contained in any hyperplane? We define a general class ofpartitioning algorithms, and show that in the worst case, for allm andn, any such algorithm requires time Ω(n logm + n ^2/3m^2/3 + m logn) in two dimensions, or Ω(n logm + n ^5/6m^1/2 + n^1/2m^5/6 + m logn) in three or more dimensions. We obtain slightly higher bounds for the counting version of Hopcroft's problem in four or more dimensions. Our planar lower bound is within a factor of 2O(log^*(n+m)) of the best known upper bound, due to Matou?ek. Previously, the best known lower bound, in any dimension, was Ω(n logm + m logn). We develop our lower bounds in two stages. First we define a combinatorial representation of the relative order type of a set of points and hyperplanes, called amonochromatic cover, and derive lower bounds on its size in the worst case. We then show that the running time of any partitioning algorithm is bounded below by the size of some monochromatic cover. As a related result, using a straightforward adversary argument, we derive aquadratic lower bound on the complexity of Hopcroft's problem in a surprisingly powerful decision tree model of computation.     

Improved bounds for the Laplacian energy of Bethe trees

For k, d?2, a Bethe tree is a rooted tree with k levels which the root vertex has degree d, the vertices from level 2 to k-1 have degree d+1 and the vertices at the level k are pendent vertices. So et al, using a theorem by Ky Fan have obtained both upper and lower bounds for the Laplacian energy of bipartite graphs. We shall employ the above mentioned theorem to obtain new and improved bounds for the Laplacian energy in the case of Bethe trees.