Nonsymmetric Toeplitz matrices that commute with tridiagonal matrices

Translated from Matematicheskie Zametki, Vol. 55, No. 5, pp. 69–79, May, 1994.     

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.     

On inverses and eigenpairs of periodic tridiagonal Toeplitz matrices with perturbed corners

In this paper, we derive explicit determinants, inverses and eigenpairs of periodic tridiagonal Toeplitz matrices with perturbed corners of Type I. The Mersenne numbers play an important role in these explicit formulas derived. Our main approaches include clever uses of the Schur complement and matrix decomposition with the Sherman-Morrison-Woodbury formula. Besides, the properties of Type II matrix can be also obtained, which benefits from the relation between Type I and II matrices. Lastly, we give three algorithms for these basic quantities and analyze them to illustrate our theoretical results.     

Stability of Gaussian elimination without pivoting on tridiagonal Toeplitz matrices

Using the simple vehicle of tridiagonal Toeplitz matrices, the question of whether one must pivot during the Gauss elimination procedure is examined. An exact expression for the multipliers encountered during the elimination process is given. It is then shown that for a prototype Helmholtz problem, one cannot guarantee that elimination without pivoting is stable.     

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.     

Toeplitz matrices with Toeplitz inverses revisited

A necessary and sufficient condition derived by Huang and Cline for a nonsingular Toeplitz matrix to have a Toeplitz inverse is shown to hold under more general hypotheses than indicated by them.     

Inversion of tridiagonal matrices

Summary This paper presents a simple algorithm for inverting nonsymmetric tridiagonal matrices that leads immediately to closed forms when they exist. Ukita's theorem is extended to characterize the class of matrices that have tridiagonal inverses.Journal Paper No. J-10137 of the Iowa Agriculture and Home Economics Experiment Station, Ames, Iowa. Project 1669, Partial support by National Institutes of Health, Grant GM 13827     

On tridiagonal conjugate-normal matrices

Conjugate-normal matrices play the same role in the theory of unitary congruences as conventional normal matrices do with respect to unitary similarities. Naturally, the properties of both matrix classes are fairly similar up to the distinction between the congruence and similarity. However, in certain respects, conjugate-normal matrices differ substantially from normal ones. Our goal in this paper is to indicate one of such distinctions. It is shown that none of the familiar characterizations of normal matrices having the irreducible tridiagonal form has a natural counterpart in the case of conjugate-normal matrices.     

Band matrices with Toeplitz inverses

It is shown that a square band matrix H=(h_ij) with h_ij=0 for j? i>r and i?j>s, where r+s is less than the order of the matrix, has a Toeplitz inverse if and only if it has a special structure characterized by two polynomials of degrees r and s, respectively.     

Toeplitz matrices with banded inverses

Given a Toeplitz matrix T with banded inverse [i.e., (T^?1)_ij=0 for j?i>p], we show that the elements of T can be expressed in terms of the roots of a polynomial. Then, using properties we have previously established, we generalize this result appropriately to allow singular T and show that the converse also holds. Finally, we give a sufficient condition for the decay of the elements of T as one moves away from the diagonal.     

Almost commuting matrices

It is shown that if A and B are n × n complex matrices with $\text{A = A}{}^1\text{and}\text{∥AB ? BA∥</}\text{2?}{}^2\text{(n ? 1)}$, then there exist n × n matrices A′ and B′ with $\text{A′ = A′}{}^1\text{such that}\text{A′B′ = B′A′}\text{and}\text{∥A ? A′∥? ?, ∥B ? B′∥? ?}$.     

Essentially commuting Hankel and Toeplitz operators

We characterize when a Hankel operator and a Toeplitz operator have a compact commutator.     

On tridiagonal matrices unitarily equivalent to normal matrices

In this article the unitary equivalence transformation of normal matrices to tridiagonal form is studied.It is well-known that any matrix is unitarily equivalent to a tridiagonal matrix. In case of a normal matrix the resulting tridiagonal inherits a strong relation between its super- and subdiagonal elements. The corresponding elements of the super- and subdiagonal will have the same absolute value.In this article some basic facts about a unitary equivalence transformation of an arbitrary matrix to tridiagonal form are firstly studied. Both an iterative reduction based on Krylov sequences as a direct tridiagonalization procedure via Householder transformations are reconsidered. This equivalence transformation is then applied to the normal case and equality of the absolute value between the super- and subdiagonals is proved. Self-adjointness of the resulting tridiagonal matrix with regard to a specific scalar product is proved. Properties when applying the reduction on symmetric, skew-symmetric, Hermitian, skew-Hermitian and unitary matrices and their relations with, e.g., complex symmetric and pseudo-symmetric matrices are presented.It is shown that the reduction can then be used to compute the singular value decomposition of normal matrices making use of the Takagi factorization. Finally some extra properties of the reduction as well as an efficient method for computing a unitary complex symmetric decomposition of a normal matrix are given.     

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.     

A communication-less parallel algorithm for tridiagonal Toeplitz systems

Diagonally dominant tridiagonal Toeplitz systems of linear equations arise in many application areas and have been well studied in the past. Modern interest in numerical linear algebra is often focusing on solving classic problems in parallel. In McNally [Fast parallel algorithms for tri-diagonal symmetric Toeplitz systems, MCS Thesis, University of New Brunswick, Saint John, 1999], an m processor Split & Correct algorithm was presented for approximating the solution to a symmetric tridiagonal Toeplitz linear system of equations. Nemani [Perturbation methods for circulant-banded systems and their parallel implementation, Ph.D. Thesis, University of New Brunswick, Saint John, 2001] and McNally (2003) adapted the works of Rojo [A new method for solving symmetric circulant tri-diagonal system of linear equations, Comput. Math. Appl. 20 (1990) 61–67], Yan and Chung [A fast algorithm for solving special tri-diagonal systems, Computing 52 (1994) 203–211] and McNally et al. [A split-correct parallel algorithm for solving tri-diagonal symmetric Toeplitz systems, Internat. J. Comput. Math. 75 (2000) 303–313] to the non-symmetric case. In this paper we present relevant background from these methods and then introduce an m processor scalable communication-less approximation algorithm for solving a diagonally dominant tridiagonal Toeplitz system of linear equations.