Construction of a Jacobi matrix from spectral data

A proof is given for the existence and uniqueness of a correspondence between two pairs of sequences {a},{b} and {ω},{μ}, satisfying b_i>0 for i=1,…,n?1 and ω₁<μ₁<?<μ_n?1<ω_n, under which the symmetric Jacobi matrices J(n,a,b) and J(n?1,a,b) have eigenvalues {ω} and {μ} respectively. Here J(m,a,b) is symmetric and tridiagonal with diagonal elements a_i (i=1,…,m) and off diagonal elements b_i (i=1,…,m?1). A new concise proof is given for the known uniqueness result. The existence result is new.     

Inverses and eigenpairs of tridiagonal Toeplitz matrix with opposite-bordered rows

In this paper, tridiagonal Toeplitz matrix (type I, type II) with opposite-bordered rows are introduced. Main attention is paid to calculate the determinants, the inverses and the eigenpairs of these matrices. Specifically, the determinants of an $n\times n$ tridiagonal Toeplitz matrix with opposite-bordered rows can be explicitly expressed by using the $(n-1)$th Fibonacci number, the inversion of the tridiagonal Toeplitz matrix with opposite-bordered rows can also be explicitly expressed by using the Fibonacci numbers and unknown entries from the new matrix. Besides, we give the expression of eigenvalues and eigenvectors of the tridiagonal Toeplitz matrix with opposite-bordered rows. In addition, some algorithms are presented based on these theoretical results. Numerical results show that the new algorithms have much better computing efficiency than some existing algorithms studied recently.     

Numerically stable deflation of hessenberg and symmetric tridiagonal matrices

While numerically stable techniques have been available for deflating a fulln byn matrix, no satisfactory finite technique has been known which preserves Hessenberg form. We describe a new algorithm which explicitly deflates a Hessenberg matrix in floating point arithmetic by means of a sequence of plane rotations. When applied to a symmetric tridiagonal matrix, the deflated matrix is again symmetric tridiagonal. Repeated deflation can be used to find an orthogonal set of eigenvectors associated with any selection of eigenvalues of a symmetric tridiagonal matrix.     

A Low-Complexity Divide-and-Conquer Method for Computing Eigenvalues and Eigenvectors of Symmetric Band Matrices

A framework for an efficient low-complexity divide-and-conquer algorithm for computing eigenvalues and eigenvectors of an n × n symmetric band matrix with semibandwidth b n is proposed and its arithmetic complexity analyzed. The distinctive feature of the algorithm—after subdivision of the original problem into p subproblems and their solution—is a separation of the eigenvalue and eigenvector computations in the central synthesis problem. The eigenvalues are computed recursively by representing the corresponding symmetric rank b(p–1) modification of a diagonal matrix as a series of rank-one modifications. Each rank-one modifications problem can be solved using techniques developed for the tridiagonal divide-and-conquer algorithm. Once the eigenvalues are known, the corresponding eigenvectors can be computed efficiently using modified QR factorizations with restricted column pivoting. It is shown that the complexity of the resulting divide-and-conquer algorithm is O (n ² b ²) (in exact arithmetic).This revised version was published online in October 2005 with corrections to the Cover Date.     

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.     

Solution of the Problem of Optimal Diagonal Scaling for Quasireal Hermitian Positive-Definite 3×3 Matrices

The paper completely solves the problem of optimal diagonal scaling for quasireal Hermitian positive-definite matrices of order 3. In particular, in the most interesting irreducible case, it is demonstrated that for any matrix C from the class considered there is a uniquely determined optimally scaled matrix D ₀ ^* CD₀ of one of the four canonical types. Formulas for the entries of the diagonal matrix D₀ are presented, as well as formulas for the eigenvalues and eigenvectors of D ₀ ^* CD₀ and for the optimal condition number of C, which is equal to k(D ₀ ^* CD₀). The optimality of the Jacobi scaling is analyzed. Bibliography: 10 titles. __________ Translated from Zapiski Nauchnykh Seminarov POMI, Vol. 309, 2004, pp. 84–126.     

$$\mathcal $$ working precision inverses for symmetric tridiagonal Toeplitz matrices with $$\mathcal O(1)$$O(1) floating point calculations

A well known numerical task is the inversion of large symmetric tridiagonal Toeplitz matrices, i.e., matrices whose entries equal a on the diagonal and b on the extra diagonals (\(a, b\in \mathbb R\)). The inverses of such matrices are dense and there exist well known explicit formulas by which they can be calculated in \(\mathcal O(n^2)\). In this note we present a simplification of the problem that has proven to be rather useful in everyday practice: If \(\vert a\vert > 2\vert b\vert \), that is, if the matrix is strictly diagonally dominant, its inverse is a band matrix to working precision and the bandwidth is independent of n for sufficiently large n. Employing this observation, we construct a linear time algorithm for an explicit tridiagonal inversion that only uses \(\mathcal O(1)\) floating point operations. On the basis of this simplified inversion algorithm we outline the cornerstones for an efficient parallelizable approximative equation solver.     

An implicit QR algorithm for symmetric semiseparable matrices

The QR algorithm is one of the classical methods to compute the eigendecomposition of a matrix. If it is applied on a dense n × n matrix, this algorithm requires O(n³) operations per iteration step. To reduce this complexity for a symmetric matrix to O(n), the original matrix is first reduced to tridiagonal form using orthogonal similarity transformations. In the report (Report TW360, May 2003) a reduction from a symmetric matrix into a similar semiseparable one is described. In this paper a QR algorithm to compute the eigenvalues of semiseparable matrices is designed where each iteration step requires O(n) operations. Hence, combined with the reduction to semiseparable form, the eigenvalues of symmetric matrices can be computed via intermediate semiseparable matrices, instead of tridiagonal ones. The eigenvectors of the intermediate semiseparable matrix will be computed by applying inverse iteration to this matrix. This will be achieved by using an O(n) system solver, for semiseparable matrices. A combination of the previous steps leads to an algorithm for computing the eigenvalue decompositions of semiseparable matrices. Combined with the reduction of a symmetric matrix towards semiseparable form, this algorithm can also be used to calculate the eigenvalue decomposition of symmetric matrices. The presented algorithm has the same order of complexity as the tridiagonal approach, but has larger lower order terms. Numerical experiments illustrate the complexity and the numerical accuracy of the proposed method. Copyright © 2005 John Wiley & Sons, Ltd.     

Nearness results for real tridiagonal 2‐Toeplitz matrices

In this article, we extend the results for Toeplitz matrices obtained by Noschese, Pasquini, and Reichel. We study the distance d, measured in the Frobenius norm, of a real tridiagonal 2‐Toeplitz matrix T to the closure of the set formed by the real irreducible tridiagonal normal matrices. The matrices in , whose distance to T is d, are characterized, and the location of their eigenvalues is shown to be in a region determined by the field of values of the operator associated with T, when T is in a certain class of matrices that contains the Toeplitz matrices. When T has an odd dimension, the eigenvalues of the closest matrices to T in are explicitly described. Finally, a measure of nonnormality of T is studied for a certain class of matrices T. The theoretical results are illustrated with examples. In addition, known results in the literature for the case in which T is a Toeplitz matrix are recovered.     

Noncirculant Toeplitz matrices all of whose powers are Toeplitz

Let a, b and c be fixed complex numbers. Let M _n (a, b, c) be the n × n Toeplitz matrix all of whose entries above the diagonal are a, all of whose entries below the diagonal are b, and all of whose entries on the diagonal are c. For 1 ⩽ k ⩽ n, each k × k principal minor of M _n (a, b, c) has the same value. We find explicit and recursive formulae for the principal minors and the characteristic polynomial of M _n (a, b, c). We also show that all complex polynomials in M _n (a, b, c) are Toeplitz matrices. In particular, the inverse of M _n (a, b, c) is a Toeplitz matrix when it exists.     

Computation of exact inertia and inclusions of eigenvalues (singular values) of tridiagonal (bidiagonal) matrices

This report may be considered as a non-trivial extension of an unpublished report by William Kahan (Accurate Eigenvalues of a symmetric tri-diagonal matrix, Technical Report CS 41, Computer Science Department, Stanford University, 1966). His interplay between matrix theory and computer arithmetic led to the development of algorithms for computing accurate eigenvalues and singular values. His report is generally considered as the precursor for the development of IEEE standard 754 for binary arithmetic. This standard has been universally adopted by virtually all PC, workstation and midrange hardware manufactures and tens of billions of such machines have been produced. Now we use the features in this standard to improve the original algorithm.In this paper, we describe an algorithm in floating-point arithmetic to compute the exact inertia of a real symmetric (shifted) tridiagonal matrix. The inertia, denoted by the integer triplet (π, ν, ζ), is defined as the number of positive, negative and zero eigenvalues of a real symmetric (or complex Hermitian) matrix and the adjective exact refers to the eigenvalues computed in exact arithmetic. This requires the floating-point computation of the diagonal matrix D of the LDL^t factorization of the shifted tridiagonal matrix T − τI with +∞ and −∞ rounding modes defined in IEEE 754 standard. We are not aware of any other algorithm which gives the exact answer to a numerical problem when implemented in floating-point arithmetic in standard working precisions. The guaranteed intervals for eigenvalues are obtained by bisection or multisection with this exact inertia information. Similarly, using the Golub-Kahan form, guaranteed intervals for singular values of bidiagonal matrices can be computed. The diameter of the eigenvalue (singular value) intervals depends on the number of shifts with inconsistent inertia in two rounding modes. Our algorithm not only guarantees the accuracy of the solutions but is also consistent across different IEEE 754 standard compliant architectures. The unprecedented accuracy provided by our algorithms could be also used to debug and validate standard floating-point algorithms for computation of eigenvalues (singular values). Accurate eigenvalues (singular values) are also required by certain algorithms to compute accurate eigenvectors (singular vectors).We demonstrate the accuracy of our algorithms by using standard matrix examples. For the Wilkinson matrix, the eigenvalues (in IEEE double precision) are very accurate with an (open) interval diameter of 6 ulps (units of the last place held of the mantissa) for one of the eigenvalues and lesser (down to 2 ulps) for others. These results are consistent across many architectures including Intel, AMD, SGI and DEC Alpha. However, by enabling IEEE double extended precision arithmetic in Intel/AMD 32-bit architectures at no extra computational cost, the (open) interval diameters were reduced to one ulp, which is the best possible solution for this problem. We have also computed the eigenvalues of a tridiagonal matrix which manifests in Gauss-Laguerre quadrature and the results are extremely good in double extended precision but less so in double precision. To demonstrate the accuracy of computed singular values, we have also computed the eigenvalues of the Kac₃₀ matrix, which is the Golub-Kahan form of a bidiagonal matrix. The tridiagonal matrix has known integer eigenvalues. The bidiagonal Cholesky factor of the Gauss-Laguerre tridiagonal is also included in the singular value study.     

The Minimum Rank of a 3 × 3 Partial Block Matrix

After recalling the definition and some basic properties of finite hypergroups—a notion introduced in a recent paper by one of the authors—several non-trivial examples of such hypergroups are constructed. The examples typically consist of n n×n matrices, each of which is an appropriate polynomial in a certain tri-diagonal matrix. The crucial result required in the construction is the following: ‘let A be the matrix with ones on the super-and sub-diagonals, and with main diagonal given by a ₁…a _n which are non-negative integers that form either a non-decreasing or a symmetric unimodal sequence; then A_k =P_k (A) is a non-negative matrix, where p_k denotes the characteristic polynomial of the top k× k principal submatrix of A, for k=1,…,n. The matrices A_k as well as the eigenvalues of A, are explicitly described in some special cases, such as (i) a_i =0 for all ior (ii) a_i =0 for i<n and a_n =1. Characters ot finite abelian hypergroups are defined, and that naturally leads to harmonic analysis on such hypergroups.     

A nonsymmetric matrix with integer eigenvalues

A nonsymmetric N?×?N matrix with elements as certain simple functions of N distinct real or complex numbers r ₁, r ₂, …, r_N is presented. The matrix is special due to its eigenvalues???the consecutive integers 0,1,2, …, N?1. Theorems are given establishing explicit expressions of the right and left eigenvectors and formulas for recursive calculation of the right eigenvectors. A special case of the matrix has appeared in sampling theory where its right eigenvectors, if properly normalized, give the inclusion probabilities of the conditional Poisson sampling design.     

Inverses of tridiagonal Toeplitz and periodic matrices with applications to mechanics

The linear algebraic equation Ax = b with tridiagonal coefficient matrix of A is solved by the analytical matrix inversion. An explicit formula is known if A is a Toeplitz matrix. New formulas are presented for the following cases: (1) A is of Toeplitz type except that A(1, 1) and A(n, n) are different from the remaining diagonal elements. (2) A is p-periodic (p > 1), by which is meant that in each of the three bands of A a group of p elements is periodically repeated. (3) The tridiagonal matrix A is composed of periodic submatrices of different periods. In cases (2) and(3) the problem of matrix inversion is reduced to a second-order difference equation with periodic coefficients. The solution is based on Floquet's theorem. It is shown that for p = 1 the formulae found for periodic matrices reduce to special forms valid for Toeplitz matrices. The results are applied to problems of elastostatics and of vibration theory.     

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.     

Twisted factorization of a banded matrix

The twisted factorization of a tridiagonal matrix T plays an important role in inverse iteration as featured in the MRRR algorithm. The twisted structure simplifies the computation of the eigenvector approximation and can also improve the accuracy. A tridiagonal twisted factorization is given by T=M _k Δ _k N _k where Δ _k is diagonal, M _k ,N _k have unit diagonals, and the k-th column of M _k and the k-th row of N _k correspond to the k-th column and row of the identity, that is . This paper gives a constructive proof for the existence of the twisted factorizations of a general banded matrix A. We show that for a given twist index k, there actually are two such factorizations. We also investigate the implications on inverse iteration and discuss the role of pivoting.      

Doubly stochastic matrices which have certain diagonals with constant sums

Let A be an n×n doubly stochastic matrix and suppose that 1?m?n?1. Let τ₁,…,τ_m be m mutually disjoint zero diagonals in A, and suppose that every diagonal of A disjoint from τ₁,…,τ_m has a constant sum. Then aall entries of A off the m zero diagonals have the value (n?m)^?1. This verifies a conjecture of E.T. Wang.     

Homotopy method for the numerical solution of the eigenvalue problem of self-adjoint partial differential operators

GivenA ₁, the discrete approximation of a linear self-adjoint partial differential operator, the smallest few eigenvalues and eigenvectors ofA ₁ are computed by the homotopy (continuation) method. The idea of the method is very simple. From some initial operatorA ₀ with known eigenvalues and eigenvectors, define the homotopyH(t)=(1–t)A ₀+tA₁, 0t1. If the eigenvectors ofH(t ₀) are known, then they are used to determine the eigenpairs ofH(t ₀+dt) via the Rayleigh quotient iteration, for some value ofdt. This is repeated untilt becomes 1, when the solution to the original problem is found. A fundamental problem is the selection of the step sizedt. A simple criterion to selectdt is given. It is shown that the iterative solver used to find the eigenvector at each step can be stabilized by applying a low-rank perturbation to the relevant matrix. By carrying out a small part of the calculation in higher precision, it is demonstrated that eigenvectors corresponding to clustered eigenvalues can be computed to high accuracy. Some numerical results for the Schrödinger eigenvalue problem are given. This algorithm will also be used to compute the bifurcation point of a parametrized partial differential equation.Dedicated to Herbert Bishop Keller on the occasion of his 70th birthdayThe work of this author was in part supported by RGC Grant DAG93/94.SC30.The work of this author was in part supported by NSF Grant DMS-9403899.     

Interrelations between eigenvalues and diagonal entries of Hermitian matrices implying their block diagonality

Let A=(a_ij) _i,j ⁿ =1 be a Hermitian matrix and let denote its eigenvalues. If , k<n, then A is known to be block diagonal. We show that this result easily follows from the Cauchy interlacing theorem, generalize it by introducing a convex strictly monotone function f(t), and prove that in the positivedefinite case, the matrix diagonal entries can be replaced by the diagonal entries of a Schur complement. Bibliography: 4 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 229, 1995, pp. 153–158. Translated by L. Yu. Kolotilina.     

On factorization of the Fibonacci and Lucas numbers using tridiagonal determinants

The aim of this paper is to give new results about factorizations of the Fibonacci numbers F _n and the Lucas numbers L _n . These numbers are defined by the second order recurrence relation a _n+2 = a _n+1+a _n with the initial terms F ₀ = 0, F ₁ = 1 and L ₀ = 2, L ₁ = 1, respectively. Proofs of theorems are done with the help of connections between determinants of tridiagonal matrices and the Fibonacci and the Lucas numbers using the Chebyshev polynomials. This method extends the approach used in [CAHILL, N. D.—D’ERRICO, J. R.—SPENCE, J. P.: Complex factorizations of the Fibonacci and Lucas numbers, Fibonacci Quart. 41 (2003), 13–19], and CAHILL, N. D.—NARAYAN, D. A.: Fibonacci and Lucas numbers as tridiagonal matrix determinants, Fibonacci Quart. 42 (2004), 216–221].