Eigenvector sensitivity under general and structured perturbations of tridiagonal Toeplitz‐type matrices

The sensitivity of eigenvalues of structured matrices under general or structured perturbations of the matrix entries has been thoroughly studied in the literature. Error bounds are available, and the pseudospectrum can be computed to gain insight. Few investigations have focused on analyzing the sensitivity of eigenvectors under general or structured perturbations. This paper discusses this sensitivity for tridiagonal Toeplitz and Toeplitz‐type matrices.     

Singular, nonsingular, and bounded rank completions of ACI-matrices

An affine column independent matrix is a matrix whose entries are polynomials of degree at most 1 in a number of indeterminates where no indeterminate appears with a nonzero coefficient in two different columns. A completion is a matrix obtained by giving values to each of the indeterminates. Affine column independent matrices are more general than partial matrices where each entry is either a constant or a distinct indeterminate. We determine when the rank of all completions of an affine column independent matrix is bounded by a given number, generalizing known results for partial matrices. We also characterize the square partial matrices over a field all of whose completions are nonsingular. The maximum number of free entries in such matrices of a given order is determined as well as the partial matrices with this maximum number of free entries.     

The Sylvester–Kac matrix space

The Sylvester–Kac matrix is a tridiagonal matrix with integer entries and integer eigenvalues that appears in a variety of applicative problems. We show that it belongs to a four dimensional linear space of tridiagonal matrices that can be simultaneously reduced to triangular form. We name this space after the matrix.     

The study of Jacobi and cyclic Jacobi matrix eigenvalue problems using Sturm-Liouville theory

We study the eigenvalues of matrix problems involving Jacobi and cyclic Jacobi matrices as functions of certain entries. Of particular interest are the limits of the eigenvalues as these entries approach infinity. Our approach is to use the recently discovered equivalence between these problems and a class of Sturm-Liouville problems and then to apply the Sturm-Liouville theory.     

Properties and preservers of the pseudospectrum

The interplay between the algebraic and analytic properties of a matrix and the geometric properties of its pseudospectrum is investigated. It is shown that one can characterize Hermitian matrices, positive semi-definite matrices, orthogonal projections, unitary matrices, etc. in terms of the pseudospectrum. Also, characterizations are given to maps on matrices leaving invariant the pseudospectrum of the sum, difference, or product of matrix pairs. It is shown that such a map is always a unitary similarity transform followed by some simple operations such as adding a constant matrix, taking the matrix transpose, or multiplying by a scalar in {1,-1}.     

A note on structured pseudospectra

In this note, we study the notion of structured pseudospectra. We prove that for Toeplitz, circulant, Hankel and symmetric structures, the structured pseudospectrum equals the unstructured pseudospectrum. We show that this is false for Hermitian and skew-Hermitian structures. We generalize the result to pseudospectra of matrix polynomials. Indeed, we prove that the structured pseudospectrum equals the unstructured pseudospectrum for matrix polynomials with Toeplitz, circulant, Hankel and symmetric structures. We conclude by giving a formula for structured pseudospectra of real matrix polynomials. The particular type of perturbations used for these pseudospectra arise in control theory.     

Permanents of special classes of doubly stochastic matrices

We identify the doubly stochastic matrices with at least one zero entry which are closest in the Euclidean norm to J_n, the matrix with each entry equal to 1/n, and we show that at these matrices the permanent function has a relative minimum when restricted to doubly stochastic matrices having zero entries.     

The shifted number system for fast linear algebra on integer matrices

The shifted number system is presented: a method for detecting and avoiding error producing carries during approximate computations with truncated expansions of rational numbers. Using the shifted number system the high-order lifting and integrality certification techniques of Storjohann 2003 for polynomial matrices are extended to the integer case. Las Vegas reductions to integer matrix multiplication are given for some problems involving integer matrices: the determinant and a solution of a linear system can be computed with about the same number of bit operations as required to multiply together two matrices having the same dimension and size of entries as the input matrix. The algorithms are space efficient.     

A law of large numbers for finite‐range dependent random matrices

We consider random Hermitian matrices in which distant above‐diagonal entries are independent but nearby entries may be correlated. We find the limit of the empirical distribution of eigenvalues by combinatorial methods. We also prove that the limit has an algebraic Stieltjes transform by an argument based on dimension theory of Noetherian local rings. © 2008 Wiley Periodicals, Inc.     

INERTIA SETS OF SYMMETRIC SIGN PATTERN MATRICES

1　IntroductionIn qualitative and combinatorial matrix theory,we study properties ofa matrix basedon combinatorial information,such as the signs of entries in the matrix.A matrix whoseentries are from the set{ + ,-,0 } is called a sign pattern matrix ( or sign pattern,or pat-tern) .We denote the setof all n× n sign pattern matrices by Qn.For a real matrix B,sgn( B) is the sign pattern matrix obtained by replacing each positive( respectively,negative,zero) entry of B by+ ( respectively,-,0 )…     

Calculating the Lyapunov exponent for generalized linear systems with exponentially distributed elements of the transition matrix

A stochastic dynamic system of second order is considered. The system evolution is described by a dynamic equation with a stochastic transition matrix, which is linear in the idempotent algebra with operations of maximum and addition. It is assumed that some entries of the matrix are zero constants and all other entries are mutually independent and exponentially distributed. The problem considered is the computation of the Lyapunov exponent, which is defined as the average asymptotic rate of growth of the state vector of the system. The known results related to this problem are limited to systems whose matrices have zero off-diagonal entries. In the cases of matrices with a zero row, zero diagonal entries, or only one zero entry, the Lyapunov exponent is calculated using an approach which is based on constructing and analyzing a certain sequence of one-dimensional distribution functions. The value of the Lyapunov exponent is calculated as the average value of a random variable determined by the limiting distribution of this sequence.     

Spectra,pseudospectra, and localization for random bidiagonal matrices

There has been much recent interest, initiated by work of the physicists Hatano and Nelson, in the eigenvalues of certain random, non‐Hermitian, periodic tridiagonal matrices and their bidiagonal limits. These eigenvalues cluster along a “bubble with wings” in the complex plane, and the corresponding eigenvectors are localized in the wings, delocalized in the bubble. Here, in addition to eigenvalues, pseudospectra are analyzed, making it possible to treat the nonperiodic analogues of these random matrix problems. Inside the bubble, the resolvent norm grows exponentially with the dimension. Outside, it grows subexponentially in a bounded region that is the spectrum of the infinite‐dimensional operator. Localization and delocalization correspond to resolvent matrices whose entries exponentially decrease or increase, respectively, with distance from the diagonal. This article presents theorems that characterize the spectra, pseudospectra, and numerical range for the four cases of finite bidiagonal matrices, infinite bidiagonal matrices (“stochastic Toeplitz operators”), finite periodic matrices, and doubly infinite bidiagonal matrices (“stochastic Laurent operators”). © 2001 John Wiley & Sons, Inc.     

Diagonal scaling in eigenvalue localization for the Schur complement

Geršgorin theorem is a well-known result in eigenvalue localization area. In this paper, using diagonal scaling method, we obtain more Geršgorin-type localizations for the eigenvalues of the Schur complement using the entries of the original matrix instead of the entries of the Schur complement. We deal with classes of matrices with some form of diagonal dominance. (© 2013 Wiley-VCH Verlag GmbH & Co. KGaA, Weinheim)     

Pseudospectra of rectangular matrices

Pseudospectra of rectangular matrices vary continuously withthe matrix entries, a feature that eigenvalues of these matricesdo not have. Some properties of eigenvalues and pseudospectraof rectangular matrices are explored, and an efficient algorithmfor the computation of pseudospectra is proposed. Applicationsare given in (square) eigenvalue computation (Lanczos iteration),square pseudospectra approximation (Arnoldi iteration), controltheory (nearest uncontrollable system) and game theory.     

Isospectral flow method for nonnegative inverse eigenvalue problem with prescribed structure

The nonnegative inverse eigenvalue problem is that given a family of complex numbers λ={λ₁,…,λ_n}, find a nonnegative matrix of order n with spectrum λ. This problem is difficult and remains unsolved partially. In this paper, we focus on its generalization that the reconstructed nonnegative matrices should have some prescribed entries. It is easy to see that this new problem will come back to the common nonnegative inverse eigenvalue problem if there is no constraint of the locations of entries. A numerical isospectral flow method which is developed by hybridizing the optimization theory and steepest descent method is used to study the reconstruction. Moreover, an error estimate of the numerical iteration for ordinary differential equations on the matrix manifold is presented. After that, a numerical method for the nonnegative symmetric inverse eigenvalue problem with prescribed entries and its error estimate are considered. Finally, the approaches are verified by the numerical test results.     

Large families of laplacian isospectral graphs

Two graphs are isomorphic only if they are Laplacian isospectral, that is, their Laplacian matrices share the same multiset of eigenvalues. Large families of nonisomorphic Laplacian isospectral graphs are exhibited for which the common multiset of eigenvalues consists entirely of integers.     

Generalization of Mirsky’s theorem on diagonals and eigenvalues of matrices

Mirsky proved that, for the existence of a complex matrix with given eigenvalues and diagonal entries, the obvious necessary condition is also sufficient. We generalize this theorem to matrices over any field and provide a short proof. Moreover, we show that there is a unique companion-matrix-type solution for this problem.     

Numerical methods for ordinary differential equations on matrix manifolds

In recent years differential systems whose solutions evolve on manifolds of matrices have acquired a certain relevance in numerical analysis. A classical example of such a differential system is the well-known Toda flow. This paper is a partial survey of numerical methods recently proposed for approximating the solutions of ordinary differential systems evolving on matrix manifolds. In particular, some results recently obtained by the author jointly with his co-workers will be presented. We will discuss numerical techniques for isospectral and isodynamical flows where the eigenvalues of the solutions are preserved during the evolution and numerical methods for ODEs on the orthogonal group or evolving on a more general quadratic group, like the symplectic or Lorentz group. We mention some results for systems evolving on the Stiefel manifold and also review results for the numerical solution of ODEs evolving on the general linear group of matrices.     

The fan-pall imbedding theorem over formally real fields

The converse of the Cauchy interlacing theorem, relating eigenvalues of a symmetric real matrix and eigenvalues of a principal submatrix, first proved by Fan and Pall, is extended to the case of symmetric matrices with entries in an arbitrary formally real field.