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.     

Multiplicative Decompositions and Frequency of Vanishing of Nonnegative Submartingales

In this paper, we establish a multiplicative decomposition formula for nonnegative local martingales and use it to characterize the set of continuous local submartingales Y of the form Y = N + A, where the measure dA is carried by the set of zeros of Y. In particular, we shall see that in the set of all local submartingales with the same martingale part in the multiplicative decomposition, these submartingales are the smallest ones. We also study some integrability questions in the multiplicative decomposition and interpret the notion of saturated sets in the light of our results.      

Universality of local eigenvalue statistics for some sample covariance matrices

We consider random, complex sample covariance matrices X*X, where X is a p × N random matrix with i.i.d. entries of distribution μ. It has been conjectured that both the distribution of the distance between nearest neighbor eigenvalues in the bulk and that of the smallest eigenvalues become, in the limit N → ∞, → 1, the same as that identified for a complex Gaussian distribution μ. We prove these conjectures for a certain class of probability distributions μ. © 2004 Wiley Periodicals, Inc.     

Non-white Wishart ensembles

We consider non-white Wishart ensembles , where X is a p×N random matrix with i.i.d. complex standard Gaussian entries and Σ is a covariance matrix, with fixed eigenvalues, close to the identity matrix. We prove that the largest eigenvalue of such random matrix ensembles exhibits a universal behavior in the large-N limit, provided Σ is “close enough” to the identity matrix. If not, we identify the limiting distribution of the largest eigenvalues, focusing on the case where the largest eigenvalues almost surely exit the support of the limiting Marchenko-Pastur's distribution.     

Asymptotic Behavior of the Maximum of Sums of I.I.D. Random Variables along Monotone Blocks

Let {X_i, Y_i}_i=1,2,... be an i.i.d. sequence of bivariate random vectors with P(Y₁ = y) = 0 for all y. Put M_n(j) = max_0≤k≤n-j (X_k+1 + ... X_k+j)I_k,j, where I_k,k+j = I{Y_k+1 < ⋯ < Y_k+j} denotes the indicator function for the event in brackets, 1 ≤ j ≤ n. Let L_n be the largest index l ≤ n for which I_k,k+l = 1 for some k = 0, 1, ..., n - l. The strong law of large numbers for “the maximal gain over the longest increasing runs,” i.e., for M_n(L_n) has been recently derived for the case where X₁ has a finite moment of order 3 + ε, ε > 0. Assuming that X₁ has a finite mean, we prove for any a = 0, 1, ..., that the s.l.l.n. for M(L_n - a) is equivalent to EX ₁ ^3+a I{X₁ > 0} < ∞. We derive also some new results for the a.s. asymptotics of L_n. Bibliography: 5 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 311, 2004, pp. 179–189.     

Poisson convergence of eigenvalues of circulant type matrices

We consider the point processes based on the eigenvalues of the reverse circulant, symmetric circulant and k-circulant matrices with i.i.d. entries and show that they converge to a Poisson random measures in vague topology. The joint convergence of upper ordered eigenvalues and their spacings follow from this. We extend these results partially to the situation where the entries are come from a two sided moving average process.     

Solving linear programs with finite precision: I. Condition numbers and random programs

We define a condition number (A,b,c) for a linear program min x s.t. Ax=b,x0 and give two characterizations via distances to degeneracy and singularity. We also give bounds for the expected value, as well as for higher moments, of log (A,b,c) when the entries of A,b and c are i.i.d. random variables with normal distribution. This work has been substantially funded by a grant from the Research Grants Council of the Hong Kong SAR (project number CityU 1085/02P)     

The Probability that a Random Real Gaussian Matrix haskReal Eigenvalues, Related Distributions, and the Circular Law

LetAbe annbynmatrix whose elements are independent random variables with standard normal distributions. Girko's (more general) circular law states that the distribution of appropriately normalized eigenvalues is asymptotically uniform in the unit disk in the complex plane. We derive the exact expected empirical spectral distribution of the complex eigenvalues for finiten, from which convergence in the expected distribution to the circular law for normally distributed matrices may be derived. Similar methodology allows us to derive a joint distribution formula for the real Schur decomposition ofA. Integration of this distribution yields the probability thatAhas exactlykreal eigenvalues. For example, we show that the probability thatAhas all real eigenvalues is exactly 2^{−n(n−1)/4}.     

± sign pattern matrices that allow orthogonality

A sign pattern A is a ± sign pattern if A has no zero entries. A allows orthogonality if there exists a real orthogonal matrix B whose sign pattern equals A. Some sufficient conditions are given for a sign pattern matrix to allow orthogonality, and a complete characterization is given for ± sign patterns with n − 1 ⩽ N₋(A) ⩽ n + 1 to allow orthogonality.     

The distance spectrum of a tree

Let T be a tree with line graph T*. Define K = 2I + A(T*), where A denotes the adjacency matrix. Then the eigenvalues of -2K^?1 interlace the eigenvalues of the distance matrix D. This permits numerous results about the spectrum of K to be transcribed for the less tractable D.     

The computation of isotropic vectors

We describe algorithms to compute isotropic vectors for matrices with real or complex entries. These are unit vectors b satisfying b ^* Ab = 0. For real matrices the algorithm uses only the eigenvectors of the symmetric part corresponding to the extreme eigenvalues. For complex matrices, we first use the eigenvalues and eigenvectors of the Hermitian matrix K = (A − A ^*)/2i. This works in many cases. In case of failure we use the Hermitian part H or a combination of eigenvectors of H and K. We give some numerical experiments comparing our algorithms with those proposed by R. Carden and C. Chorianopoulos, P. Psarrakos and F. Uhlig.     

Bounds for the Entries of Matrix Functions with Applications to Preconditioning

Let A be a symmetric matrix and let f be a smooth function defined on an interval containing the spectrum of A. Generalizing a well-known result of Demko, Moss and Smith on the decay of the inverse we show that when A is banded, the entries of f(A)are bounded in an exponentially decaying manner away from the main diagonal. Bounds obtained by representing the entries of f(A)in terms of Riemann-Stieltjes integrals and by approximating such integrals by Gaussian quadrature rules are also considered. Applications of these bounds to preconditioning are suggested and illustrated by a few numerical examples.     

Null ideals and spanning ranks of matrices,II

Suppose R is an integral domain and A ∈ M _{n × n}(R) \{O}. If D is a spanning rank partner of A, then precisely one of the following three relationships holds: N _A = N _D N _A = XN _D or XN _A = N _D. Here X is an indeterminate and N _A(N _D) denotes the null ideal of A(D) in R[X]. There are easy examples of A and D for which N _A = N _D and N _A = XN _D. In this paper, we give an example where XN _A = N _D. We give sharper versions of the theorem for n ≤ 4.     

Asymptotic Expansions in Non-central Limit Theorems for Quadratic Forms

We consider quadratic forms of the type

Integrally Closed Domains,Minimal Polynomials,and Null Ideals of Matrices

Abstract

We show that every element of the integral closure D′ of a domain D occurs as a coefficient of the minimal polynomial of a matrix with entries in D. This answers affirmatively a question of Brewer and Richman, namely, if integrally closed domains are characterized by the property that the minimal polynomial of every square matrix with entries in D is in D[x]. It follows that a domain D is integrally closed if and only if for every matrix A with entries in D the null ideal of A, N _D (A)?=?{f?∈?D[x]?∣?f(A)?=?0} is a principal ideal of D[x].     

The Isotropic Semicircle Law and Deformation of Wigner Matrices

We analyze the spectrum of additive finite‐rank deformations of N × N Wigner matrices H. The spectrum of the deformed matrix undergoes a transition, associated with the creation or annihilation of an outlier, when an eigenvalue d_i of the deformation crosses a critical value ± 1. This transition happens on the scale . We allow the eigenvalues d_i of the deformation to depend on N under the condition . We make no assumptions on the eigenvectors of the deformation. In the limit N → ∞, we identify the law of the outliers and prove that the nonoutliers close to the spectral edge have a universal distribution coinciding with that of the extremal eigenvalues of a Gaussian matrix ensemble. A key ingredient in our proof is the isotropic local semicircle law, which establishes optimal high‐probability bounds on where m(z) is the Stieltjes transform of Wigner's semicircle law and v , w are arbitrary deterministic vectors.© 2013 Wiley Periodicals, Inc.     

Jensen matrix inequalities and direct sums

Let A, X and Y be n-by-n complex matrices such that A is positive semi-definite and X, Y are contractions. We prove that if f is an increasing convex function on [0, ∞) such that f(0) ≤ 0, then the eigenvalues of f(|X*AY|) are dominated by those of X*f(A)X⊕Y* f(A)Y. Several related results are considered.     

Unit integer quadratic binary programming

This paper presents an efficient method of computing $\text{?′}{}_{\mathrm{<mtext>max</mtext>}}\text{=}\text{max}\text{Y}\text{Y}{}^{\mathrm{<mtext>T</mtext>}}\text{AY}$, where Y is an N-dimensional vector of ±1 entries and A is a real symmetric matrix. The ratio of number of computations required by this method to that by the direct method is approximately ($\text{3}\text{2N}$), where the direct method corresponds to computing Y^TAY for all possible Y and then finding the maximum from these. This problem has important applications in operations research, matrix theory, signal processing, communication theory, control theory, and others. Some of these are discussed in this paper.     

Three- and Four-Dimensional Einstein-like Manifolds and Homogeneity

The aim of this paper is to study three- and four-dimensional Einstein-like Riemannian manifolds which are Ricci-curvature homogeneous, that is, have constant Ricci eigenvalues. In the three-dimensional case, we present the complete classification of these spaces while, in the four-dimensional case, this classification is obtained in the special case where the manifold is locally homogeneous. We also present explicit examples of four-dimensional locally homogeneous Riemannian manifolds whose Ricci tensor is cyclic-parallel (that is, are of type A) and has distinct eigenvalues. These examples are invalidating an expectation stated by F. Podestá and A. Spiro, and illustrating a striking contrast with the three-dimensional case (where this situation cannot occur). Finally, we also investigate the relation between three- and four-dimensional Einstein-like manifolds of type A and D'Atri spaces, that is, Riemannian manifolds whose geodesic symmetries are volume-preserving (up to sign).     

No eigenvalues outside the support of the limiting empirical spectral distribution of a separable covariance matrix

We consider a class of matrices of the form , where X_n is an n×N matrix consisting of i.i.d. standardized complex entries, is a nonnegative definite square root of the nonnegative definite Hermitian matrix A_n, and B_n is diagonal with nonnegative diagonal entries. Under the assumption that the distributions of the eigenvalues of A_n and B_n converge to proper probability distributions as , the empirical spectral distribution of C_n converges a.s. to a non-random limit. We show that, under appropriate conditions on the eigenvalues of A_n and B_n, with probability 1, there will be no eigenvalues in any closed interval outside the support of the limiting distribution, for sufficiently large n. The problem is motivated by applications in spatio-temporal statistics and wireless communications.