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.     

Outlier Eigenvalues for Deformed I.I.D. Random Matrices

We consider a square random matrix of size N of the form A + Y where A is deterministic and Y has i.i.d. entries with variance 1/N. Under mild assumptions, as N grows the empirical distribution of the eigenvalues of A + Y converges weakly to a limit probability measure β on the complex plane. This work is devoted to the study of the outlier eigenvalues, i.e., eigenvalues in the complement of the support of β. Even in the simplest cases, a variety of interesting phenomena can occur. As in earlier works, we give a sufficient condition to guarantee that outliers are stable and provide examples where their fluctuations vary with the particular distribution of the entries of Y or the Jordan decomposition of A. We also exhibit concrete examples where the outlier eigenvalues converge in distribution to the zeros of a Gaussian analytic function. © 2016 Wiley Periodicals, Inc.     

Covering Arrays of Strength Three

A covering array of size N, degree k, order v and strength t is a k × N array with entries from a set of v symbols such that in any t × N subarray every t × 1 column occurs at least once. Covering arrays have been studied for their applications to drug screening and software testing. We present explicit constructions and give constructive upper bounds for the size of a covering array of strength three.     

Extended genus of torsion-free finitely generated nilpotent groups of class two

The extended genus of a nilpotent group N is the set of isomorphism classes of nilpotent groups M, not necessarily finitely generated, such that the p-localizations M _p , N _p are isomorphic for all primes p. In this article, for any torsion-free finitely generated nilpotent group N of nilpotency class 2, the extended genus of N is analyzed by assigning to each of its members a sequence of triads of matrices with rational entries, generalizing the sequential representation which has been exploited elsewhere in the case when N is abelian. This approach allows, among other things, to obtain examples of groups in the ordinary (Mislin) genus of N     

Frieze patterns for punctured discs

We construct frieze patterns of type D _N with entries which are numbers of matchings between vertices and triangles of corresponding triangulations of a punctured disc. For triangulations corresponding to orientations of the Dynkin diagram of type D _N , we show that the numbers in the pattern can be interpreted as specialisations of cluster variables in the corresponding Fomin-Zelevinsky cluster algebra. This is generalised to arbitrary triangulations in an appendix by Hugh Thomas.     

An algorithm for finding optimal integration lattices of composite order

In this paper we describe a search algorithm that can be used to determine good lattices of orderN whenN=N _L N _R has two nontrivial integer factors. This algorithm is based on relationships between an integer latticeA _R of orderN _R and its various sublattices all of orderN. Using this we have determined all four dimensional good lattices of order 599 or less. Our list has 23 entries.This work was supported by the Applied Mathematical Sciences Subprogram of the Office of Energy Research, U.S. Department of Energy, under Contract W-31-109-Eng-38, and by the Norwegian Council for Humanities and Science.     

Smallest singular value of a random rectangular matrix

We prove an optimal estimate of the smallest singular value of a random sub‐Gaussian matrix, valid for all dimensions. For an N × n matrix A with independent and identically distributed sub‐Gaussian entries, the smallest singular value of A is at least of the order √N ? √n ? 1 with high probability. A sharp estimate on the probability is also obtained. © 2009 Wiley Periodicals, Inc.     

Polynomial time perfect sampling algorithm for two‐rowed contingency tables

This paper proposes a polynomial time perfect (exact) sampling algorithm for 2 × n contingency tables. The algorithm is based on monotone coupling from the past (monotone CFTP) algorithm. The expected running time is bounded by O(n³ lnN) where n is the number of columns and N is the total sum of all entries. © 2005 Wiley Periodicals, Inc. Random Struct. Alg., 2006     

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].     

Prewavelet approximations for a system of boundary integral equations for plates with free edges on polygons

We consider the plate equation in a polygonal domain with free edges. Its resolution by boundary integral equations is considered with double layer potentials whose variational formulation was given in Reference 25. We approximate its solution (u, (∂u/∂n)) by the Galerkin method with approximated spaces made of piecewise polynomials of order 2 and 1 for, respectively, u and (∂u/∂n). A prewavelet basis of these subspaces is built and equivalences between some Sobolev norms and discrete ones are established in the spirit of References 14, 16, 30 and 31. Further, a compression procedure is presented which reduces the number of nonzero entries of the stiffness matrix from O(N²) to O(N log N), where N is the size of this matrix. We finally show that the compressed stiffness matrices have a condition number uniformly bounded with respect to N and that the compressed Galerkin scheme converges with the same rate than the Galerkin one. © 1998 B. G. Teubner Stuttgart—John Wiley & Sons, Ltd.     

Elastodynamical Scattering by N Parallel Half-Planes in IR3

Linear boundary value problems of elasticity describe the propagation of time- harmonic waves outside of N parallel half-plane shaped cracks in the Euclidian 3-space. Equivalent systems involving 6N Wiener-Hopf equations are obtained for first, second and third kind conditions simultaneously. To find explicit solutions, complex-valued matrix functions with nonrational entries, are to be factorized in a generalized manner. This is done for two double-knife screen crack problems in Part II. Problems for waves in acoustics, hydro-and electrodynamics with an analogous geometry for rigid walls, or perfectly conducting metallic sheets, are contained in the problems formulated above: In Part II, for pure Dirichlet-, or Neumann conditions, the corresponding (reduced) Wiener-Hopf operator is seen to be invertible by an operator Neumann series for all distances (≠ 0) between the N half-planes Σm.     

Singularities of Solutions to Quadratic Vector Equations on the Complex Upper Half‐Plane

Let S be a positivity‐preserving symmetric linear operator acting on bounded functions. The nonlinear equation with a parameter z in the complex upper half‐plane ? has a unique solution m with values in ?. We show that the z‐dependence of this solution can be represented as the Stieltjes transforms of a family of probability measures v on ?. Under suitable conditions on S , we show that v has a real analytic density apart from finitely many algebraic singularities of degree at most 3. Our motivation comes from large random matrices. The solution m determines the density of eigenvalues of two prominent matrix ensembles: (i) matrices with centered independent entries whose variances are given by S and (ii) matrices with correlated entries with a translation‐invariant correlation structure. Our analysis shows that the limiting eigenvalue density has only square root singularities or cubic root cusps; no other singularities occur.© 2016 Wiley Periodicals, Inc.     

± 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.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.     

The largest eigenvalue of small rank perturbations of Hermitian random matrices

We compute the limiting eigenvalue statistics at the edge of the spectrum of large Hermitian random matrices perturbed by the addition of small rank deterministic matrices. We consider random Hermitian matrices with independent Gaussian entries M _ij ,i≤j with various expectations. We prove that the largest eigenvalue of such random matrices exhibits, in the large N limit, various limiting distributions depending on both the eigenvalues of the matrix and its rank. This rank is also allowed to increase with N in some restricted way. An erratum to this article is available at .     

Factorization of analytic functions by means of Koenig's theorem and Toeplitz computations

Summary. By providing a matrix version of Koenig's theorem we reduce the problem of evaluating the coefficients of a monic factor r(z) of degree h of a power series f(z) to that of approximating the first h entries in the first column of the inverse of an Toeplitz matrix in block Hessenberg form for sufficiently large values of n. This matrix is reduced to a band matrix if f(z) is a polynomial. We prove that the factorization problem can be also reduced to solving a matrix equation for an matrix X, where is a matrix power series whose coefficients are Toeplitz matrices. The function is reduced to a matrix polynomial of degree 2 if f(z) is a polynomial of degreeN and . These reductions allow us to devise a suitable algorithm, based on cyclic reduction and on the concept of displacement rank, for generating a sequence of vectors that quadratically converges to the vector having as components the coefficients of the factor r(z). In the case of a polynomial f(z) of degree N, the cost of computing the entries of given is arithmetic operations, where is the cost of solving an Toeplitz-like system. In the case of analytic functions the cost depends on the numerical degree of the power series involved in the computation. From the numerical experiments performed with several test polynomials and power series, the algorithm has shown good numerical properties and promises to be a good candidate for implementing polynomial root-finders based on recursive splitting strategies. Applications to solving spectral factorization problems and Markov chains are also shown. Received September 9, 1998 / Revised version received November 14, 1999 / Published online February 5, 2001     

The Spectral Theory of Upper Triangular Matrices with Entries in a Banach Algebra

Assume that T is an upper triangular square matrix with entries in a unital Banach algebra. The main question studied here is: Under what conditions on the entries in T is it true that the spectrum of T is the union of the spectra of the diagonal entries of T? Also some results are proved concerning the Fredholm theroy of matrices with operator entries.     

Closed geodesics in compact nilmanifolds

We study the density of closed geodesics property on 2-step nilmanifolds Γ\N, where N is a simply connected 2-step nilpotent Lie group with a left invariant Riemannian metric and Lie algebra ?, and Γ is a lattice in N. We show the density of closedgeodesics property holds for quotients of singular, simply connected, 2-step nilpotent Lie groups N which are constructed using irreducible representations of the compact Lie group SU(2). Received: 8 November 2000 / Revised version: 9 April 2001     

Inverse problem for N × N hyperbolic systems on the plane and the N-wave interactions

We study regiorously the solvability of the direct and inverse problems associated with Ψ_x–JΨ_y = QΨ,(x,y) ∈ ?², where (i) Ψ is an N × N-matrix-valued function on ?² (N ≦ 2), (ii) J is a constant, real, diagonal N × N matrix with entries, J₁ > J₂ > …? > J_N and (iii) Q is off-diagonal with rapidly decreasing (Schwartz) component functions. In particular we show that the direct problem is always solvable and give a small norm condition for the solvability of the inverse problem. In the particular case that Q is skew Hermitian the inverse problem is solvable without the small norm assumption. Furthermore we show how these results can be used to solve certain Cauchy problems for the associated nonlinear evolution equations. For concreteness we consider the N-wave interactions and show that if a certain norm of Q(x, y, 0) is smallor if Q(x, y, 0) is skew Hermitian the N-wave interations equation has a unique global solution.