The Cayley Method and the Inverse Eigenvalue Problem for Toeplitz Matrices

Despite the fact that symmetric Toeplitz matrices can have arbitrary eigenvalues, the numerical construction of such a matrix having prescribed eigenvalues remains to be a challenge. A two-step method using the continuation idea is proposed in this paper. The first step constructs a centro-symmetric Jacobi matrix with the prescribed eigenvalues in finitely many steps. The second step uses the Cayley transform to integrate flows in the linear subspace of skew-symmetric and centro-symmetric matrices. No special geometric integrators are needed. The convergence analysis is illustrated for the case of n = 3. Numerical examples are presented.     

Circulant preconditioners for discrete ill-posed Toeplitz systems

Circulant preconditioners are commonly used to accelerate the rate of convergence of iterative methods when solving linear systems of equations with a Toeplitz matrix. Block extensions that can be applied when the system has a block Toeplitz matrix with Toeplitz blocks also have been developed. This paper is concerned with preconditioning of linear systems of equations with a symmetric block Toeplitz matrix with symmetric Toeplitz blocks that stem from the discretization of a linear ill-posed problem. The right-hand side of the linear systems represents available data and is assumed to be contaminated by error. These kinds of linear systems arise, e.g., in image deblurring problems. It is important that the preconditioner does not affect the invariant subspace associated with the smallest eigenvalues of the block Toeplitz matrix to avoid severe propagation of the error in the right-hand side. A perturbation result indicates how the dimension of the subspace associated with the smallest eigenvalues should be chosen and allows the determination of a suitable preconditioner when an estimate of the error in the right-hand side is available. This estimate also is used to decide how many iterations to carry out by a minimum residual iterative method. Applications to image restoration are presented.     

Zur Bestimmung der Eigenwerte schiefsymmetrischer Matrizen

Summary Givens's method of reducing a symmetric matrix to Jacobi form works equally well for skew symmetric matrices. The author shows how the eigenvalues of the resulting skew-symmetric Jacobi matrix are obtained with the aid of the Quotient Difference Algorithm [2]. The theory of continued fractions allows the QD-table for the negative squares of the eigenvalues to be set up direct, which considerably reduces computing time.      

Spectrum of a Jacobi matrix with exponentially growing matrix elements

A Jacobi matrix with an exponential growth of its elements and the corresponding symmetric operator are considered. It is proved that the eigenvalue problem for some self-adjoint extension of this operator in some Hilbert space is equivalent to the eigenvalue problem of the Sturm-Liouville operator with a discrete self-similar weight. An asymptotic formula for the distribution of eigenvalues is obtained.     

An eigenvalue localization theorem for pentadiagonal symmetric Toeplitz matrices

We express the eigenvalues of a pentadiagonal symmetric Toeplitz matrix as the zeros of explicitly given rational functions.     

On the optimal computation of a set of symmetric and persymmetric bilinear forms

A special class $\text{T}$ⁿ of n×n matrices is described, which has tensor rank n over the real field. A tensor base for general symmetric, persymmetric, both symmetric and persymmetric matrices and Toeplitz symmetric matrices can be defined in terms of the tensor bases of $\text{T}$^l for some different values of l. It is proved that both symmetric and persymmetric n×n matrices and Toeplitz symmetric n×n matrices have tensor rank $\text{[}\text{(n+1)}{}^2\text{4}\text{]}$ and 2n?2, respectively, in the real field.     

Condition Numbers for Structured Least Squares Problems

This paper studies the normwise perturbation theory for structured least squares problems. The structures under investigation are symmetric, persymmetric, skewsymmetric, Toeplitz and Hankel. We present the condition numbers for structured least squares. AMS subject classification (2000) 15A18, 65F20, 65F25, 65F50     

广义Jacobi矩阵的逆特征问题

本文主要讨论广义Jacobi阵及多个特征对的广义Jacobi阵逆特征问题.通过相似变换将广义Jacobi阵变换为三对角对称矩阵,其特征不变、特征向量只作线性变换,再应用前人理论求得广义Jacobi阵元素ai,|bi|,|ci|有唯一解的充要条件及其具体表达式.     

On some structured inverse eigenvalue problems

This work deals with various finite algorithms that solve two special Structured Inverse Eigenvalue Problems (SIEP). The first problem we consider is the Jacobi Inverse Eigenvalue Problem (JIEP): given some constraints on two sets of reals, find a Jacobi matrix J (real, symmetric, tridiagonal, with positive off-diagonal entries) that admits as spectrum and principal subspectrum the two given sets. Two classes of finite algorithms are considered. The polynomial algorithm which is based on a special Euclid–Sturm algorithm (Householder's terminology) and has been rediscovered several times. The matrix algorithm which is a symmetric Lanczos algorithm with a special initial vector. Some characterization of the matrix ensures the equivalence of the two algorithms in exact arithmetic. The results of the symmetric situation are extended to the nonsymmetric case. This is the second SIEP to be considered: the Tridiagonal Inverse Eigenvalue Problem (TIEP). Possible breakdowns may occur in the polynomial algorithm as it may happen with the nonsymmetric Lanczos algorithm. The connection between the two algorithms exhibits a similarity transformation from the classical Frobenius companion matrix to the tridiagonal matrix. This result is used to illustrate the fact that, when computing the eigenvalues of a matrix, the nonsymmetric Lanczos algorithm may lead to a slow convergence, even for a symmetric matrix, since an outer eigenvalue of the tridiagonal matrix of order n − 1 can be arbitrarily far from the spectrum of the original matrix. This revised version was published online in August 2006 with corrections to the Cover Date.     

On the Convergence of Cyclic Jacobi Methods

In a cyclic Jacobi method for calculating the eigenvalues andeigenvectors of a symmetric matrix, the pivots are chosen inany fixed cyclic order. It is not known in theory whether convergenceto the solution is always obtained, although convergence hasbeen proved subject to a restriction on the angle of rotationabout each pivot (Henrici, 1958). Now we report an actual computercalculation where a cyclic Jacobi method failed, due to computerrounding errors, so in practice the angle restriction may beneeded. A new bound for the angle restriction is given thatis less severe than the one proposed originally.     

Symmetric Gaussian elimination for cauchy-type matrices with application to positive definite Toeplitz matrices

The problem of solving linear equations with a Toeplitz matrix appears in many applications. Often is positive definite but ill-conditioned with many small eigenvalues. In this case fast and superfast algorithms may show a very poor behavior or even break down. In recent papers the transformation of a Toeplitz matrix into a Cauchy-type matrix is proposed. The resulting new linear equations can be solved in operations using standard pivoting strategies which leads to very stable fast methods also for ill-conditioned systems. The basic tool is the formulation of Gaussian elimination for matrices with low displacement rank. In this paper, we will transform a Hermitian Toeplitz matrix into a Cauchy-type matrix by applying the Fourier transform. We will prove some useful properties of and formulate a symmetric Gaussian elimination algorithm for positive definite . Using the symmetry and persymmetry of we can reduce the total costs of this algorithm compared with unsymmetric Gaussian elimination. For complex Hermitian , the complexity of the new algorithm is then nearly the same as for the Schur algorithm. Furthermore, it is possible to include some strategies for ill-conditioned positive definite matrices that are well-known in optimization. Numerical examples show that this new algorithm is fast and reliable. Received March 24, 1995 / Revised version received December 13, 1995     

Properties of the inverses of a set of band matrices

Those regions where the elements of the inverse of a Toeplitz matrix of band width four and order nalternate in sign are determined. A similar result concerning the elements of the inverse of a commonly occurring symmetric positive definite Toeplitz matrix of band width five and order nis extended to cover the case when the first and last rows of the matrix are modified through a change in the boundary conditions of the associated application. A method for economically obtaining the infinity norm of the pent-diagonal symmetric positive definite Toeplitz matrix is then derived.     

Moments of the Hermitian Matrix Jacobi Process

In this paper, we compute the expectation of traces of powers of the Hermitian matrix Jacobi process for a large enough but fixed size. To proceed, we first derive the semi-group density of its eigenvalues process as a bilinear series of symmetric Jacobi polynomials. Next, we use the expansion of power sums in the Schur polynomial basis and the integral Cauchy–Binet formula in order to determine the partitions having nonzero contributions after integration. It turns out that these are hooks of bounded weight and the sought expectation results from the integral of a product of two Schur functions with respect to a generalized beta distribution. For special values of the parameters on which the matrix Jacobi process depends, the last integral reduces to the Cauchy determinant and we close the paper with the investigation of the asymptotic behavior of the resulting formula as the matrix size tends to infinity.     

Bounds for the extremal eigenvalues of a class of symmetric tridiagonal matrices with applications

We consider a class of symmetric tridiagonal matrices which may be viewed as perturbations of Toeplitz matrices. The Toeplitz structure is destroyed since two elements on each off-diagonal are perturbed. Based on a careful analysis, we derive sharp bounds for the extremal eigenvalues of this class of matrices in terms of the original data of the given matrix. In this way, we also obtain a lower bound for the smallest singular value of certain matrices. Some numerical results indicate that our bounds are extremely good.     

Every Matrix is a Product of Toeplitz Matrices

We show that every \(n\,\times \,n\) matrix is generically a product of \(\lfloor n/2 \rfloor + 1\) Toeplitz matrices and always a product of at most \(2n+5\) Toeplitz matrices. The same result holds true if the word ‘Toeplitz’ is replaced by ‘Hankel,’ and the generic bound \(\lfloor n/2 \rfloor + 1\) is sharp. We will see that these decompositions into Toeplitz or Hankel factors are unusual: We may not, in general, replace the subspace of Toeplitz or Hankel matrices by an arbitrary \((2n-1)\)-dimensional subspace of \({n\,\times \,n}\) matrices. Furthermore, such decompositions do not exist if we require the factors to be symmetric Toeplitz or persymmetric Hankel, even if we allow an infinite number of factors.     

The relation between the Jacobi algorithm and inverse iteration and a Jacobi algorithm based on elementary reflections

It is shown that the cyclic Jacobi algorithm for the computation of eigenvalues of a symmetric matrix behaves asymptotically like inverse iteration with Rayleigh Quotient shift (RQI). The asymptotic expression for the transformation matrix is used to develop a new Jacobi algorithm which uses elementary reflections (Householder transformations) instead of rotations. The new algorithm has the same asymptotic behaviour, but each sweep needs half the number of arithmetic operations and has one level of looping less than the traditional one. Numerical tests of an APL implementation are reported.     

Quadratic convergence of scaled matrices in Jacobi method

Summary. A quadratic convergence bound for scaled Jacobi iterates is proved provided the initial symmetric positive definite matrix has simple eigenvalues. The bound is expressed in terms of the off-norm of the scaled initial matrix and the minimum relative gap in the spectrum. The obtained result can be used to predict the stopping moment in the two-sided and especially in the one-sided Jacobi method. Received October 31, 1997 / Revised version received March 8, 1999 / Published online July 12, 2000     

Spectral functions for real symmetric Toeplitz matrices

We derive separate spectral functions for the even and odd spectra of a real symmetric Toeplitz matrix, which are given by the roots of those functions. These are rational functions, also commonly referred to as secular functions. Two applications are considered: spectral evolution as a function of one parameter and the computation of eigenvalues.     

On inverse eigenvalue problems for block Toeplitz matrices with Toeplitz blocks

We propose an algorithm for solving the inverse eigenvalue problem for real symmetric block Toeplitz matrices with symmetric Toeplitz blocks. It is based upon an algorithm which has been used before by others to solve the inverse eigenvalue problem for general real symmetric matrices and also for Toeplitz matrices. First we expose the structure of the eigenvectors of the so-called generalized centrosymmetric matrices. Then we explore the properties of the eigenvectors to derive an efficient algorithm that is able to deliver a matrix with the required structure and spectrum. We have implemented our ideas in a Matlab code. Numerical results produced with this code are included.     

Exact formulae and matrix-less eigensolvers for block banded symmetric Toeplitz matrices

Precise asymptotic expansions for the eigenvalues of a Toeplitz matrix \(T_n(f)\), as the matrix size n tends to infinity, have recently been obtained, under suitable assumptions on the associated generating function f. A restriction is that f has to be polynomial, monotone, and scalar-valued. In this paper we focus on the case where \(\mathbf {f}\) is an \(s\times s\) matrix-valued trigonometric polynomial with \(s\ge 1\), and \(T_n(\mathbf {f})\) is the block Toeplitz matrix generated by \(\mathbf {f}\), whose size is \(N(n,s)=sn\). The case \(s=1\) corresponds to that already treated in the literature. We numerically derive conditions which ensure the existence of an asymptotic expansion for the eigenvalues. Such conditions generalize those known for the scalar-valued setting. Furthermore, following a proposal in the scalar-valued case by the first author, Garoni, and the third author, we devise an extrapolation algorithm for computing the eigenvalues of banded symmetric block Toeplitz matrices with a high level of accuracy and a low computational cost. The resulting algorithm is an eigensolver that does not need to store the original matrix, does not need to perform matrix-vector products, and for this reason is called matrix-less. We use the asymptotic expansion for the efficient computation of the spectrum of special block Toeplitz structures and we provide exact formulae for the eigenvalues of the matrices coming from the \(\mathbb {Q}_p\) Lagrangian Finite Element approximation of a second order elliptic differential problem. Numerical results are presented and critically discussed.