The inverses of Toeplitz band matrices

The elements of the inverse of a Toeplitz band matrix are given in terms ofthe solution of a difference equation. The expression for these elements is a quotient of determinants whose orders depend the number of nonzero superdiagonals but not on the order of the matrix. Thus, the formulae are particularly simple for lower triangular and lower Hessenberg Toeplitz matrices. When the number of nonzero superdiagonals is small, sufficient conditions on the solution of the abovementioned difference equation can be given to ensure that the inverse matrix is positive. If the inverse is positive, the row sums can be expressed in terms of the solution of the difference equation.     

Efficiently computing the permanent and Hafnian of some banded Toeplitz matrices

We present a new efficient method for computing the permanent and Hafnian of certain banded Toeplitz matrices. The method covers non-trivial cases for which previous known methods do not apply. The main idea is to use the elements of the first row and column, which determine the entire Toeplitz matrix, to construct a digraph in which certain paths correspond to permutations that the permanent and Hafnian count. Since counting paths can be done efficiently, the permanent and Hafnian for those matrices is easily obtainable.     

Shift permutation invariance in linear random factor models

The objective of this paper is to consider shift invariance, a specific type of exchangeability, of random factors in linearmodels. The randomfactors are described via their covariance matrices and it is shown that shift invariance implies circular Toeplitz covariancematrices and marginally shift invariance implies block circular Toeplitz covariance matrices. In order to get interpretable linear models reparametrization is performed. It is shown that by putting restrictions on the spectrum of the shift invariant covariance matrices natural reparametrization conditions for the corresponding factors are obtained which then, among others, can be used to obtain unique parametrizations under shift invariance.      

A sufficient condition for a non-negative matrix to have non-negative determinant

It is shown that a matrix with non-negative entries has non-negative determinant if in each row the elements decrease, by steadily smaller amounts, as one proceeds (in either direction) away from the main diagonal. This condition suffices to establish non- negativity of the determinant for certain matrices to which the familiar Minkowski- Hadamard-Ostrowski dominance conditions do not apply. In the symmetric case it provides a sufficient condition for non-negative definiteness. This may be applied to establish the positive definiteness of certain real symmetric Toeplitz matrices.     

On zero-pattern invariant properties of structured matrices

It is interesting that inverse M-matrices are zero-pattern (power) invariant. The main contribution of the present work is that we characterize some structured matrices that are zero-pattern (power) invariant. Consequently, we provide necessary and sufficient conditions for these structured matrices to be inverse M-matrices. In particular, to check if a given circulant or symmetric Toeplitz matrix is an inverse M-matrix, we only need to consider its pattern structure and verify that one of its principal submatrices is an inverse M-matrix.     

Multivariate Polynomials,Duality, and Structured Matrices

We first review the basic properties of the well known classes of Toeplitz, Hankel, Vandermonde, and other related structured matrices and reexamine their correlation to operations with univariate polynomials. Then we define some natural extensions of such classes of matrices based on their correlation to multivariate polynomials. We describe the correlation in terms of the associated operators of multiplication in the polynomial ring and its dual space, which allows us to generalize these structures to the multivariate case. Multivariate Toeplitz, Hankel, and Vandermonde matrices, Bezoutians, algebraic residues, and relations between them are studied. Finally, we show some applications of this study to rootfinding problems for a system of multivariate polynomial equations, where the dual space, algebraic residues, Bezoutians, and other structured matrices play an important role. The developed techniques enable us to obtain a better insight into the major problems of multivariate polynomial computations and to improve substantially the known techniques of the study of these problems. In particular, we simplify and/or generalize the known reduction of the multivariate polynomial systems to the matrix eigenproblem, the derivation of the Bézout and Bernshtein bounds on the number of the roots, and the construction of multiplication tables. From the algorithmic and computational complexity point, we yield acceleration by one order of magnitude of the known methods for some fundamental problems of solving multivariate polynomial systems of equations.     

BANDED TOEPLITZ PRECONDITIONERS FOR TOEPLITZ MATRICES FROM SINC METHODS

We give general expressions, analyze algebraic properties and derive eigenvalue bounds for a sequence of Toeplitz matrices associated with the sinc discretizations of various orders of differential operators. We demonstrate that these Toeplitz matrices can be satisfactorily preconditioned by certain banded Toeplitz matrices through showing that the spectra of the preconditioned matrices are uniformly bounded. In particular, we also derive eigenvalue bounds for the banded Toeplitz preconditioners. These results are elementary in constructing high-quality structured preconditioners for the systems of linear equations arising from the sinc discretizations of ordinary and partial differential equations, and are useful in analyzing algebraic properties and deriving eigenvalue bounds for the corresponding preconditioned matrices. Numerical examples are given to show effectiveness of the banded Toeplitz preconditioners.     

Distribution of Eigenvalues of Real Symmetric Palindromic Toeplitz Matrices and Circulant Matrices

Consider the ensemble of real symmetric Toeplitz matrices, each independent entry an i.i.d. random variable chosen from a fixed probability distribution p of mean 0, variance 1, and finite higher moments. Previous investigations showed that the limiting spectral measure (the density of normalized eigenvalues) converges weakly and almost surely, independent of p, to a distribution which is almost the standard Gaussian. The deviations from Gaussian behavior can be interpreted as arising from obstructions to solutions of Diophantine equations. We show that these obstructions vanish if instead one considers real symmetric palindromic Toeplitz matrices, matrices where the first row is a palindrome. A similar result was previously proved for a related circulant ensemble through an analysis of the explicit formulas for eigenvalues. By Cauchy’s interlacing property and the rank inequality, this ensemble has the same limiting spectral distribution as the palindromic Toeplitz matrices; a consequence of combining the two approaches is a version of the almost sure Central Limit Theorem. Thus our analysis of these Diophantine equations provides an alternate technique for proving limiting spectral measures for certain ensembles of circulant matrices. A. Massey’s current address: Department of Mathematics, UCLA, Los Angeles, CA 90095, USA. e-mail: amassey3102@math.ucla.edu.     

Block LU-factorization of confluent Vandermonde matrices

In this note we show that an asymptotically fast algorithm may be designed in order to realize a block LU-factorization of confluent Vandermonde matrices. This result is based on a displacement structure satisfied by confluent Vandermonde matrices and on factorizations of the block elements in terms of triangular Toeplitz matrices.     

Interlacing and degree conditios for invariat polynomials

It is well known that the invariant factors of a polynomial matrix interlace with ihose of one of its submatrices. If we restrict the degrees of the entries of our matrices in some prescribed way then the invariant factors of such matrices and submatrices satisfy other conditions that may be predicted and, in some cases, even completely described. That is the kind of problem we deal with Our main result is a sort of interlacing theorem for row proper matrices. Convexity and majorization also enter into play.     

Sign Regular Matrices of Order Two

A matrix is called sign regular of order k if every minor of order i has the same sign for each i = 1,2,<, k . If an m × n matrix is sign regular of order k for k = min { m,n } then it is called sign regular. This paper studies some properties of sign regular matrices of order two. Remarkable properties are proved when the row sums of these matrices form a monotone vector.     

Multilevel regularization for image deblurring problems

We consider the de-blurring problem of noisy and blurred signals/images in the case of space invariant point spread functions. The use of appropriate boundary conditions leads to linear systems with structured coefficient matrices related to space invariant operators like Toeplitz, circulants, trigonometric matrix algebras etc. We combine an algebraic multigrid (which is designed ad hoc for structured matrices) with the low-pass projectors typical of the classical geometrical multigrid for elliptic partial differential equations. The smoother is any iterative regularizing method, while the projector is chosen in order to maintain the same algebraic structure at each recursion level and having a low-pass filter property, which is very useful in order to reduce the noise effects. In this way, we obtain a better restored image with a flatter restoration error curve and also in less time than the auxiliary method used as smoother. (© 2008 WILEY-VCH Verlag GmbH & Co. KGaA, Weinheim)     

块Toeplitz方程组的快速块Gauss-Seidel迭代算法

本文研究块Toeplitz方程组的块Gauss-Seidel迭代算法。我们首先讨论了块三角Toeplitz矩阵的一些性质,然后给出了求解块三角Toeplitz矩阵逆的快速算法,由此而得到了求解块Toeplitz方程组的快速块Gauss-Seidel迭代算法,最后证明了当系数矩阵为对称正定和H-矩阵时该方法都收敛,数值例子验证了方法的收敛性。     

Spectral asymptotics for Kac–Murdock–Szegő matrices

Szeg?’s First Limit Theorem provides the limiting statistical distribution of the eigenvalues of large Toeplitz matrices. Szeg?’s Second (or Strong) Limit Theorem for Toeplitz matrices gives a second order correction to the First Limit Theorem, and allows one to calculate asymptotics for the determinants of large Toeplitz matrices. In this paper we survey results extending the First and Second Limit Theorems to Kac–Murdock–Szeg? (KMS) matrices. These are matrices whose entries along the diagonals are not necessarily constants, but modeled by functions. We clarify and extend some existing results, and explain some apparently contradictory results in the literature.     

Some extensions of Hankel and Toeplitz matrices

New necessary and sufficient conditions are given for a nonsingular matrix to have Hankel or Toeplitz form. Two generalizations, termed conjugate-Toeplitz and Leslie-Toeplitz matrices, are introduced A number of properties of Toeplitz matrices are shown to carry over to these extensions     

Tensor properties of multilevel Toeplitz and related matrices

A general proposal is presented for fast algorithms for multilevel structured matrices. It is based on investigation of their tensor properties and develops the idea recently introduced by Kamm and Nagy in the block Toeplitz case. We show that tensor properties of multilevel Toeplitz matrices are related to separation of variables in the corresponding symbol, present analytical tools to study the latter, expose truncation algorithms preserving the structure, and report on some numerical results confirming advantages of the proposal.     

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.     

Asymptotic properties of the QR factorization of banded Hessenberg–Toeplitz matrices

We consider Givens QR factorization of banded Hessenberg–Toeplitz matrices of large order and relatively small bandwidth. We investigate the asymptotic behaviour of the R factor and Givens rotation when the order of the matrix goes to infinity, and present some interesting convergence properties. These properties can lead to savings in the computation of the exact QR factorization and give insight into the approximate QR factorizations of interest in preconditioning. The properties also reveal the relation between the limit of the main diagonal elements of R and the largest absolute root of a polynomial. Copyright © 2005 John Wiley & Sons, Ltd.     

Properties of a symbol of a type of elements in simple field

We obtain some properties of a symbol of a type of elements in simple field of positive characteristic as well as connected with it functions and matrices which elements are expressed by a symbol of a type. Besides we obtain the method of finding minimal invariant subsets of the multiplicative group of the simple field.