A further remark on the logarithmic derivatives of a square matrix

It is well-known that the logarithmic derivativeμ[A] of a square matrixA has its value no less than the maximum real partp of the eigenvalues ofA and there exist matricesA such thatμ[A] >p with respect to any norm inCⁿ. The purpose of this note is to show thatμ[A] can be made equal top for some operator norm inCⁿ if and only if those eigenvalues ofA with maximum real part are simple roots of the minimal polynomials forA.     

On the sequence of powers of a stochastic matrix with large exponent

We consider the class of primitive stochastic n×n matrices A, whose exponent is at least (n²−2n+2)/2+2. It is known that for such an A, the associated directed graph has cycles of just two different lengths, say k and j with k>j, and that there is an α between 0 and 1 such that the characteristic polynomial of A is λⁿ−αλ^n−j−(1−α)λ^n−k. In this paper, we prove that for any mn, if α1/2, then A^m+k−A^m_∞A^m−1w^T_∞, where 1 is the all-ones vector and w^T is the left-Perron vector for A, normalized so that w^T1=1. We also prove that if jn/2, n31 and , then A^m+j−A^m_∞A^m−1w^T_∞ for all sufficiently large m. Both of these results lead to lower bounds on the rate of convergence of the sequence A^m.     

On the Empirical Distribution of Eigenvalues of a Class of Large Dimensional Random Matrices

A stronger result on the limiting distribution of the eigenvalues of random Hermitian matrices of the form A + XTX*, originally studied in Mar enko and Pastur, is presented. Here, X(N × n), T(n × n), and A(N × N) are independent, with X containing i.i.d. entries having finite second moments, T is diagonal with real (diagonal) entries, A is Hermitian, and n/N → c > 0 as N → ∞. Under additional assumptions on the eigenvalues of A and T, almost sure convergence of the empirical distribution function of the eigenvalues of A + XTX* is proven with the aid of Stieltjes transforms, taking a more direct approach than previous methods.     

Complex Roots of a Random Algebraic Polynomial

This paper, for any constantK, provides an exact formula for the average density of the distribution of the complex roots of equation η₀ + η₁z + η₂z² + ··· + η_{n − 1}z^{n − 1} = Kwhere η_j = a_j + ib_jand {a_j}^{n − 1}_{j = 0}and {b_j}^{n − 1}_{j = 0}are sequences of independent identically and normally distributed random variables andKis a complex number withKas its real and imaginary parts. The case of real roots of the above equation with real coefficients andK,z Ris well known. Further we obtain the limiting behaviour of this distribution function asntends to infinity.     

Asymptotic expansions of the distributions of some test statistics for Gaussian ARMA processes

Let {X_t} be a Gaussian ARMA process with spectral density f_θ(λ), where θ is an unknown parameter. The problem considered is that of testing a simple hypothesis H:θ = θ₀ against the alternative A:θ ≠ θ₀. For this problem we propose a class of tests , which contains the likelihood ratio (LR), Wald (W), modified Wald (MW) and Rao (R) tests as special cases. Then we derive the χ² type asymptotic expansion of the distribution of T up to order n⁻¹, where n is the sample size. Also we derive the χ² type asymptotic expansion of the distribution of T under the sequence of alternatives A_n: θ = θ₀ + /√n, ε > 0. Then we compare the local powers of the LR, W, MW, and R tests on the basis of their asymptotic expansions.     

Laws of large numbers for classes of functions

Let (X, , P) be a probability space and _n, n ≥ 1, a sequence of classes of measurable complex-valued functions on (X, , P). Under a weak metric entropy condition on _n and sup {g_∞: g _n}, Glivenko-Cantelli theorems are established for the classes _n with respect to the probability measure P; i.e., lim_{n → ∞} sup_{g n} ∫ g(dP_n − dP) = 0 a.s. The result is applied to kernel density estimation and a law of the logarithm is derived for the maximal deviation between a kernel density estimator and its expected value, improving upon and generalizing the recent results of W. Stute (Ann. Probab. 10 (1982), 414–422). This result is also used to derive improved rates of uniform convergence for the empirical characteristic function.     

The greedy coloring is a bad probabilistic algorithm

Given a graph G and an ordering p of its vertices, denote by A(G, p) the number of colors used by the greedy coloring algorithm when applied to G with vertices ordered by p. Let , , Δ be positive constants. It is proved that for each n there is a graph G_n such that the chromatic number of G_n is at most n, but the probability that A(G_n, p) < (1 − )n/log₂ n for a randomly chosen ordering p is O(n^−Δ).     

Centres of Convex Sets inLMetrics

It is shown that for each convex bodyARⁿthere exists a naturally defined family _AC(Sⁿ⁻¹) such that for everyg _A, and every convex functionf: R→Rthe mappingy∫_Sⁿ⁻¹ f(g(x)−y, x) dσ(x) has a minimizer which belongs toA. As an application, approximation of convex bodies by balls with respect toL^pmetrics is discussed.     

Commutative Extended Complex Numbers and Connected Trigonometry

In order to construct an extension of the complex numbers, we consider an n-dimensional commutative algebra generated by the n vectors 1, e, ..., eⁿ⁻¹ where the fundamental element satisfies the basic relation eⁿ = −1. These spaces can be classified according to the values of n: prime number, power of a prime number, general number. The question of the invertibility leads to the definition of a pseudo-norm for which the triangle inequality is not satisfied (the n = 1, 2 cases excepted). When one tries to pass from the polar form the cartesian one, one obtains functions generalizing the usual circular and hyperbolic functions and their inverse. The extended sine and hyperbolic sine functions thus constructed satisfy a determinantal-type relation and they lay the foundation of a new trigonometry for which summation and derivative formulas are given. An extended 2π quantity is defined as the periodicity of the generalized circular functions. This formalism is applied to solve the nth order differential equations (∑ⁿ⁻¹_i=1 (∂n/∂φⁿ_i) ± ω) ƒ(φ) = 0. As a further application, the solutions of the n-laplacian operator are derived.     

The Central Limit Theorem for Free Additive Convolution

Let {X_n}^∞_n=1be a sequence of free, identically distributed random variables with common distributionμ. Then there exist sequences {B_n}^∞_n=1and {A_n}^∞_n=1of positive and real numbers, respectively, such that sequence of random variables[formula]converges in distribution to the semicircle law if and only if the function[formula]is slowly varying in Karamata's sense. In other words, the free domain of attraction of the semicircle law coincides with the classical domain of attraction of the Gaussian. We prove an analogous result for normal domains of attraction in the sense of Linnik.     

The Fine Structure of the n-Widths of H-Spaces in Lq(−1, 1)

The n-widths of the unit ball A_p of the Hardy space H^p in L_q( −1, 1) are determined asymptotically. It is shown that for 1 ≤ q < p ≤∞ there exist constants k₁ and k₂ such that [formula]≤ d_n(A_p, L_q(−1, 1)),dⁿ(A_p, L_q(−1, 1)), δ_n(A_p, L_q(−1, 1))[formula]where d_n, dⁿ, and δ_n denote the Kolmogorov, Gel′fand and linear n-widths, respectively. This result is an improvement of estimates previously obtained by Burchard and Höllig and by the author.     

On the convergence of averaging Hermite interpolators

We investigate two sequences of polynomial operators, H_{2n − 2}(A₁,f; x) and H_{2n − 3}(A₂,f; x), of degrees 2n − 2 and 2n − 3, respectively, defined by interpolatory conditions similar to those of the classical Hermite-Féjer interpolators H_{2n − 1}(f, x). If H_{2n − 2}(A₁,f; x) and H_{2n − 3}(A₂,f; x) are based on the zeros of the jacobi polynomials P_n^(α,β)(x), their convergence behaviour is similar to that of H_{2n − 1}(f;, x). If they are based on the zeros of (1 − x²)T_{n − 2}(x), their convergence behaviour is better, in some sense, than that of H_{2n − 1}(f, x).     

Sharp inequalities for convolution-type operators

Let μ be a probability measure on [− a, a], a > 0, and let x₀ε[− a, a], f ε Cⁿ([−2a, 2a]), n 0 even. Using moment methods we derive best upper bounds to ¦∫_−a^a ([f(x₀ + y) + f(x₀ − y)]/2) μ(dy) − f(x₀)¦, leading to sharp inequalities that are attainable and involve the second modulus of continuity of f⁽ⁿ⁾ or an upper bound of it.     

Simultaneous similarity of matrices

In this paper we solve completely and explicitly the long-standing problem of classifying pairs of n × n complex matrices (A, B) under the simultaneous similarity (TAT⁻¹, TBT⁻¹). Roughly speaking, the classification decomposes to a finite number of steps. In each step we consider an open algebraic set ⁰_n,2,r,π M_n × M_n (M_n = the set of n × n complex-valued matrices). Here r and π are two positive integers. Then we construct a finite number of rational functions ø₁,…,ø_s in the entries of A and B whose values are constant on all pairs similar in _n,2,r,π to (A, B). The values of the functions ø_i(A, B), I = 1,…, s, determine a finite number (at most κ(n, 2, r)) of similarity classes in _n,2,r,π. Let S_n be the subspace of complex symmetric matrices in M_n. For (A, B) ε S_n × S_n we consider the similarity class (TAT^t, TBT^t), where T ranges over all complex orthogonal matrices. Then the characteristic polynomial |λI − (A + xB)| determines a finite number of similarity classes for almost all pairs (A, B) ε S_n × S_n.     

Maximum likelihood estimation of a change-point in the distribution of independent random variables: General multiparameter case

In a sequence ofn independent random variables the pdf changes fromf(x, 0) tof(x, 0 + δv_n⁻¹) after the firstnλ variables. The problem is to estimateλ (0, 1 ), where 0 and δ are unknownd-dim parameters andv_n → ∞ slower thann^1/2. Let_n denote the maximum likelihood estimator (mle) ofλ. Analyzing the local behavior of the likelihood function near the true parameter values it is shown under regularity conditions that ifn_n²(− λ) is bounded in probability asn → ∞, then it converges in law to the timeT_(δjδ)^1/2 at which a two-sided Brownian motion (B.M.) with drift1/2(δ′Jδ)^1/2ton(−∞, ∞) attains its a.s. unique minimum, whereJ denotes the Fisher-information matrix. This generalizes the result for small change in mean of univariate normal random variables obtained by Bhattacharya and Brockwell (1976,Z. Warsch. Verw. Gebiete37, 51–75) who also derived the distribution ofT_μ forμ > 0. For the general case an alternative estimator is constructed by a three-step procedure which is shown to have the above asymptotic distribution. In the important case of multiparameter exponential families, the construction of this estimator is considerably simplified.     

Randomized online graph coloring

We study the problem of coloring graphs in an online manner. The only known deterministic online graph coloring algorithm with a sublinear performance function was found by [9.], 319–325). Their algorithm colors graphs of chromatic number χ with no more than (2χn)/log^* n colors, where n is the number of vertices. They point out that the performance can be improved slightly for graphs with bounded chromatic number. For three-chromatic graphs the number of colors used, for example, is O(n log log log n/log log n). We show that randomization helps in coloring graphs online. We present a simple randomized online algorithm to color graphs with expected number of colors O(2^χχ²n^{(χ−2)/(χ−1)}(log n)^1/(χ−1)). For three-colorable graphs the expected number of colors our algorithm uses is . All our algorithms run in polynomial time. It is interesting to note that our algorithm compares well with the best known polynomial time offline algorithms. For instance, the best polynomial time algorithm known for three-colorable graphs, due to [4.] pp. 554–562). We also prove a lower bound of Ω((1/(χ − 1))((log n/(12(χ + 1))) − 1)^χ−1) for the randomized model. No lower bound for the randomized model was previously known. For bounded χ, our result improves even the best known lower bound for the deterministic case: Ω((log n/log log n)^χ−1), due to Noga Alon (personal communication, September 1989).     

Integral Equations and Operator Theory

A complex number λ is an extended eigenvalue of an operator A if there is a nonzero operator X such that AX = λ XA. We characterize the set of extended eigenvalues, which we call extended point spectrum, for operators acting on finite dimensional spaces, finite rank operators, Jordan blocks, and C₀ contractions. We also describe the relationship between the extended eigenvalues of an operator A and its powers. As an application, we show that the commutant of an operator A coincides with that of Aⁿ, n ≥ 2, n ∈ N if the extended point spectrum of A does not contain any n–th root of unity other than 1. The converse is also true if either A or A^* has trivial kernel.     

Some Asymptotic Formulae for Gaussian Distributions

This paper considers asymptotic expansions of certain expectations which appear in the theory of large deviation for Gaussian random vectors with values in a separable real Hilbert space. A typical application is to calculation of the “tails” of distributions of smooth functionals,p(r)=P{Φ(r⁻¹ξ)0},r→∞, e.g., the probability that a centered Gaussian random vector hits the exterior of a large sphere surrounding the origin. The method provides asymptotic formulae for the probability itself and not for its logarithm in a situation, where it is natural to expect thatp(r)=c′r^D exp{−c″r²}. Calculations are based on a combination of the method of characteristic functionals with the Laplace method used to find asymptotics of integrals containing a fast decaying function with “small” support.     

Some extensions of the Kantorovich inequality and statistical applications

Kantorovich gave an upper bound to the product of two quadratic forms, (X′AX) (X′A⁻¹X), where X is an n-vector of unit length and A is a positive definite matrix. Bloomfield, Watson and Knott found the bound for the product of determinants |X′AX| |X′A⁻¹X| where X is n × k matrix such that X′X = I_k. In this paper we determine the bounds for the traces and determinants of matrices of the type X′AYY′A⁻¹X, X′B²X(X′BCX)⁻¹ X′C²X(X′BCX)⁻¹ where X and Y are n × k matrices such that X′X = Y′Y = I_k and A, B, C are given matrices satisfying some conditions. The results are applied to the least squares theory of estimation.     

A note on the perturbation bound of the Drazin inverse

A perturbation bound for the Drazin inverse A^D with Ind(A+E)=1 has recently been developed. However, those upper bounds are not satisfied since it is not tight enough. In this paper, a sharper upper bounds for ||(A+E)^#−A^D|| with weaker conditions is derived. That new bound is also a generalization of a new general upper bound of the group inverse. We also derive a new expression of the Drazin inverse (A+E)^D with Ind(A+E)>1 and the corresponding upper bound of ||(A+E)^D−A^D|| in a special case. Numerical examples are given to illustrate the sharpness of the new bounds.