Cumulants for Random Matrices as Convolutions on the Symmetric Group,II

In a previous paper we defined some “cumulants of matrices” which naturally converge toward the free cumulants of the limiting non commutative random variables when the size of the matrices tends to infinity. Moreover these cumulants satisfied some of the characteristic properties of cumulants whenever the matrix model was invariant under unitary conjugation. In this paper we present the fitting cumulants for random matrices whose law is invariant under orthogonal conjugation. The symplectic case could be carried out in a similar way.     

An algebraic construction of k-balanced multiwavelets via the lifting scheme

Multiwavelets have been revealed to be a successful generalization within the context of wavelet theory. Recently Lebrun and Vetterli have introduced the concept of “balanced” multiwavelets, which present properties that are usually absent in the case of classical multiwavelets and do not need the prefiltering step. In this work we present an algebraic construction of biorthogonal multiwavelets by means of the well-known “lifting scheme”. The flexibility of this tool allows us to exploit the degrees of freedom left after satisfying the perfect reconstruction condition in order to obtain finite k-balanced multifilters with custom-designed properties which give rise to new balanced multiwavelet bases. All the problems we deal with are stated in the framework of banded block recursive matrices, since simplified algebraic conditions can be derived from this recursive approach. This revised version was published online in June 2006 with corrections to the Cover Date.     

The Limiting Spectral Measure for Ensembles of Symmetric Block Circulant Matrices

Given an ensemble of N×N random matrices, a natural question to ask is whether or not the empirical spectral measures of typical matrices converge to a limiting spectral measure as N→∞. While this has been proved for many thin patterned ensembles sitting inside all real symmetric matrices, frequently there is no nice closed form expression for the limiting measure. Further, current theorems provide few pictures of transitions between ensembles. We consider the ensemble of symmetric m-block circulant matrices with entries i.i.d.r.v. These matrices have toroidal diagonals periodic of period m. We view m as a “dial” we can “turn” from the thin ensemble of symmetric circulant matrices, whose limiting eigenvalue density is a Gaussian, to all real symmetric matrices, whose limiting eigenvalue density is a semi-circle. The limiting eigenvalue densities f _m show a visually stunning convergence to the semi-circle as m→∞, which we prove. In contrast to most studies of patterned matrix ensembles, our paper gives explicit closed form expressions for the densities. We prove that f _m is the product of a Gaussian and a certain even polynomial of degree 2m?2; the formula is the same as that for the m×m Gaussian Unitary Ensemble (GUE). The proof is by derivation of the moments from the eigenvalue trace formula. The new feature, which allows us to obtain closed form expressions, is converting the central combinatorial problem in the moment calculation into an equivalent counting problem in algebraic topology. We end with a generalization of the m-block circulant pattern, dropping the assumption that the m random variables be distinct. We prove that the limiting spectral distribution exists and is determined by the pattern of the independent elements within an m-period, depending not only on the frequency at which each element appears, but also on the way the elements are arranged.     

To Solving Multiparameter Problems of Algebra. 4. The AB-Algorithm and its Applications

The paper continues the investigation of methods for factorizing q-parameter polynomial matrices and considers their applications to solving multiparameter problems of algebra. An extension of the AB-algorithm, suggested earlier as a method for solving spectral problems for matrix pencils of the form A - λB, to the case of q-parameter (q ≥ 1) polynomial matrices of full rank is proposed. In accordance with the AB-algorithm, a finite sequence of q-parameter polynomial matrices such that every subsequent matrix provides a basis of the null-space of polynomial solutions of its transposed predecessor is constructed. A certain rule for selecting specific basis matrices is described. Applications of the AB-algorithm to computing complete polynomials of a q-parameter polynomial matrix and exhausting them from the regular spectrum of the matrix, to constructing irreducible factorizations of rational matrices satisfying certain assumptions, and to computing “free” bases of the null-spaces of polynomial solutions of an arbitrary q-parameter polynomial matrix are considered. Bibliography: 7 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 127–143.     

Extension of Karmarkar's algorithm onto convex quadratically constrained quadratic problems

Convex quadratically constrained quadratic problems are considered. It is shown that such problems can be transformed to aconic form. The feasible set of the conic form is the intersection of a direct product of standard quadratic cones intersected with a hyperplane (the analogue of a simplex), and a linear subspace. For a problem of such form, the analogue of Karmarkar's projective transformation and logarithmic barrier function are built. This allows us to extend “word by word” the method of Karmarkar for LP to QCQP and allows us to obtain a similar polynomial worst-case bound for the number of iterations.     

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 .     

Direct and Inverse Eigenvalue Problems for Diagonal-Plus-Semiseparable Matrices

In this paper we study both direct and inverse eigenvalue problems for diagonal-plus-semiseparable (dpss) matrices. In particular, we show that the computation of the eigenvalues of a symmetric dpss matrix can be reduced by a congruence transformation to solving a generalized symmetric definite tridiagonal eigenproblem. Using this reduction, we devise a set of recurrence relations for evaluating the characteristic polynomial of a dpss matrix in a stable way at a linear time. This in turn allows us to apply divide-and-conquer eigenvalue solvers based on functional iterations directly to dpss matrices without performing any preliminary reduction into a tridiagonal form. In the second part of the paper, we exploit the structural properties of dpss matrices to solve the inverse eigenvalue problem of reconstructing a symmetric dpss matrix from its spectrum and some other informations. Finally, applications of our results to the computation of a QR factorization of a Cauchy matrix with real nodes are provided.     

An approach to solving multiparameter algebraic problems

An approach to solving the following multiparameter algebraic problems is suggested: (1) spectral problems for singular matrices polynomially dependent on q≥2 spectral parameters, namely: the separation of the regular and singular parts of the spectrum, the computation of the discrete spectrum, and the construction of a basis that is free of a finite regular spectrum of the null-space of polynomial solutions of a multiparameter polynomial matrix; (2) the execution of certain operations over scalar and matrix multiparameter polynomials, including the computation of the GCD of a sequence of polynomials, the division of polynomials by their common divisor, and the computation of relative factorizations of polynomials; (3) the solution of systems of linear algebraic equations with multiparameter polynomial matrices and the construction of inverse and pseudoinverse matrices. This approach is based on the so-called ΔW-q factorizations of polynomial q-parameter matrices and extends the method for solving problems for one- and two-parameter polynomial matrices considered in [1–3] to an arbitrary q≥2. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 191–246. Translated by V. N. Kublanovskaya.     

An approach to solving nonlinear algebraic systems. 2

New methods of solving nonlinear algebraic systems in two variables are suggested, which make it possible to find all zero-dimensional roots without knowing initial approximations. The first method reduces the solution of nonlinear algebraic systems to eigenvalue problems for a polynomial matrix pencil. The second method is based on the rank factorization of a two-parameter polynomial matrix, allowing, us to compute the GCD of a set of polynomials and all zero-dimensional roots of the GCD. Bibliography: 10 titles. Translated by V. N. Kublanovskaya Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 71–96     

The condition number of real Vandermonde, Krylov and positive definite Hankel matrices

Summary. We show that the Euclidean condition number of any positive definite Hankel matrix of order may be bounded from below by with , and that this bound may be improved at most by a factor . Similar estimates are given for the class of real Vandermonde matrices, the class of row-scaled real Vandermonde matrices, and the class of Krylov matrices with Hermitian argument. Improved bounds are derived for the case where the abscissae or eigenvalues are included in a given real interval. Our findings confirm that all such matrices – including for instance the famous Hilbert matrix – are ill-conditioned already for “moderate” order. As application, we describe implications of our results for the numerical condition of various tasks in Numerical Analysis such as polynomial and rational i nterpolation at real nodes, determination of real roots of polynomials, computation of coefficients of orthogonal polynomials, or the iterative solution of linear systems of equations. Received December 1, 1997 / Revised version received February 25, 1999 / Published online 16 March 2000     

The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

Interpretations of some parameter dependent generalizations of classical matrix ensembles

Two types of parameter dependent generalizations of classical matrix ensembles are defined by their probability density functions (PDFs). As the parameter is varied, one interpolates between the eigenvalue PDF for the superposition of two classical ensembles with orthogonal symmetry and the eigenvalue PDF for a single classical ensemble with unitary symmetry, while the other interpolates between a classical ensemble with orthogonal symmetry and a classical ensemble with symplectic symmetry. We give interpretations of these PDFs in terms of probabilities associated to the continuous Robinson-Schensted-Knuth correspondence between matrices, with entries chosen from certain exponential distributions, and non-intersecting lattice paths, and in the course of this probability measures on partitions and pairs of partitions are identified. The latter are generalized by using Macdonald polynomial theory, and a particular continuum limit – the Jacobi limit – of the resulting measures is shown to give PDFs related to those appearing in the work of Anderson on the Selberg integral, and also in some classical work of Dixon. By interpreting Andersons and Dixons work as giving the PDF for the zeros of a certain rational function, it is then possible to identify random matrices whose eigenvalue PDFs realize the original parameter dependent PDFs. This line of theory allows sampling of the original parameter dependent PDFs, their Dixon-Anderson-type generalizations and associated marginal distributions, from the zeros of certain polynomials defined in terms of random three term recurrences.Supported by the Australian Research Council     

The eigenvalues and eigenvectors of finite, low rank perturbations of large random matrices

We consider the eigenvalues and eigenvectors of finite, low rank perturbations of random matrices. Specifically, we prove almost sure convergence of the extreme eigenvalues and appropriate projections of the corresponding eigenvectors of the perturbed matrix for additive and multiplicative perturbation models.The limiting non-random value is shown to depend explicitly on the limiting eigenvalue distribution of the unperturbed random matrix and the assumed perturbation model via integral transforms that correspond to very well-known objects in free probability theory that linearize non-commutative free additive and multiplicative convolution. Furthermore, we uncover a phase transition phenomenon whereby the large matrix limit of the extreme eigenvalues of the perturbed matrix differs from that of the original matrix if and only if the eigenvalues of the perturbing matrix are above a certain critical threshold. Square root decay of the eigenvalue density at the edge is sufficient to ensure that this threshold is finite. This critical threshold is intimately related to the same aforementioned integral transforms and our proof techniques bring this connection and the origin of the phase transition into focus. Consequently, our results extend the class of ‘spiked’ random matrix models about which such predictions (called the BBP phase transition) can be made well beyond the Wigner, Wishart and Jacobi random ensembles found in the literature. We examine the impact of this eigenvalue phase transition on the associated eigenvectors and observe an analogous phase transition in the eigenvectors. Various extensions of our results to the problem of non-extreme eigenvalues are discussed.     

On estimates of the spectrum of a linear operator

The paper is concerned with new approaches to the analysis of spectra of linear operators. New algorithms are proposed to calculate the coefficients of the minimal polynomial of a matrix; they are based on the well-known Krylov’s method, SSA decomposition, and the “Caterpillar” method of recurrent translation. The extension obtained is capable of dealing with matrices of infinite order; this has great value in solving queuing problems. Results from numerical experiments for matrices of various orders are given.     

体上代数矩阵的素有理标准形与特征值

本文应用最小中心多项式给出了体上代数矩阵的素有理标准形与初等因子组的构造，由此得到体上代数矩阵相似的充要条件以及相似于一个对角矩阵的充要条件．本文还讨论了体上矩阵的左、右特征值的构造与性质．     

Schubert polynomials of types A--D

Schubert polynomials of type B, C, and D have been described first by S. Billey and M. Haiman [BH] using a combinatorial method. In this paper we give a unified algebraic treatment of Schubert polynomials of types A–D in the style of the Lascoux–Schützenberger theory in type A, i.e. Schubert polynomials are generated by the application of sequences of divided difference operators to “top polynomials”. The use of the creation operators for Q-Schur and P-Schur functions allows us to give: (1) simple and natural forms of the “top polynomials”, (2) formulas for the easy computation with all divided differences, (3) recursive structures, and (4) simplified derivations of basic properties. Received: 23 July 1998     

The mathematics of eigenvalue optimization

 Optimization problems involving the eigenvalues of symmetric and nonsymmetric matrices present a fascinating mathematical challenge. Such problems arise often in theory and practice, particularly in engineering design, and are amenable to a rich blend of classical mathematical techniques and contemporary optimization theory. This essay presents a personal choice of some central mathematical ideas, outlined for the broad optimization community. I discuss the convex analysis of spectral functions and invariant matrix norms, touching briefly on semidefinite representability, and then outlining two broader algebraic viewpoints based on hyperbolic polynomials and Lie algebra. Analogous nonconvex notions lead into eigenvalue perturbation theory. The last third of the article concerns stability, for polynomials, matrices, and associated dynamical systems, ending with a section on robustness. The powerful and elegant language of nonsmooth analysis appears throughout, as a unifying narrative thread. Received: December 4, 2002 / Accepted: April 22, 2003 Published online: May 28, 2003 Key Words.  eigenvalue optimization – convexity – nonsmooth analysis – duality – semidefinite program – subdifferential – Clarke regular – chain rule – sensitivity – eigenvalue perturbation – partly smooth – spectral function – unitarily invariant norm – hyperbolic polynomial – stability – robust control – pseudospectrum – H _∞ norm Mathematics Subject Classification (2000): 90C30, 15A42, 65F15, 49K40     

Satisficing search versus aspiration adaptation in sales competition: experimental evidence

In a duopoly market, aspiration levels express how much sellers want to earn given their expectations about the other’s behavior. We augment the sellers’ decision task by eliciting their profit aspiration. In a first experimental phase, whenever satisficing is not possible, sales choices, point beliefs, or aspiration levels have to be adapted. This allows us to compare “aspiration-based satisficing” to “aspiration adaptation”. In a second phase, testing the absorption of satisficing, participants are free to select non-satisficing sales profiles. The results reveal that most participants are satisficers who, in line with aspiration adaptation theory, tend to adjust aspiration levels and to keep sales behavior nearly unchanged.     

Limit Distributions of Eigenvalues for Random Block Toeplitz and Hankel Matrices

Block Toeplitz and Hankel matrices arise in many aspects of applications. In this paper, we will research the distributions of eigenvalues for some models and get the semicircle law. Firstly we will give trace formulas of block Toeplitz and Hankel matrix. Then we will prove that the almost sure limit g_T^(m)\gamma_{T}^{(m)} (g_H^(m))(\gamma_{H}^{(m)}) of eigenvalue distributions of random block Toeplitz (Hankel) matrices exist and give the moments of the limit distributions where m is the order of the blocks. Then we will prove the existence of almost sure limit of eigenvalue distributions of random block Toeplitz and Hankel band matrices and give the moments of the limit distributions. Finally we will prove that g_T^(m)\gamma_{T}^{(m)} (g_H^(m))(\gamma_{H}^{(m)}) converges weakly to the semicircle law as m→∞.     

Application of the pseudo-spectral method to 2D eigenvalue problems in elasticity

A pseudo-spectral approach to 2D vibrational problems arising in linear elasticity is considerede using differentiation matrices. The governing partial differential equations and associated boundary conditions on regular domains can be translated into matrix eigenvalue problems. Accurate results are obtained to the precision expected in spectral-type methods. However, we show that it is necessary to apply an additional “pole” condition to deal with ther=0 coordinate singularity arising in the case of a 2D disc.