Inverses of banded matrices

We establish a correspondence between the vanishing of a certain set of minors of a matrix A and the vanishing of a related set of minors of A^×1. In particular, inverses of banded matrices are characterized. We then use our results to find patterns for Toeplitz matrices with banded inverses. Finally we give an interesting determinant formula for inverses of banded matrices, and show that in general a “banded partial” matrix may be completed in a unique way to give a banded inverse of the same bandwidth.     

Inverses of banded and k-Hessenberg matrices

Results are obtained on the elements of the inverses of banded and k-Hessenberg matrices. These generalize known results on tridiagonal and Hessenberg matrices.     

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.     

Spectral approximation of banded Laurent matrices with localized random perturbations

This paper explores the relationship between the spectra of perturbed infinite banded Laurent matricesL(a)+K and their approximations by perturbed circulant matricesC _n (a)+P _n KP _n for largen. The entriesK _jk of the perturbation matrices assume values in prescribed sets _jk at the sites (j, k) of a fixed finite setE, and are zero at the sites (j, k) outsideE. WithK ^E denoting the ensemble of these perturbation matrices, it is shown that

A piecewise approach to piecewise approximation

Tensor-product B-spline surfaces offer a convenient means for representing a set of bivariate data, especially if many surface evaluations are required. This is because the compact support property of the tensor-product spline allows the spline value to be obtained in a time that is (almost) independent of the number of coefficients used to define the surface. The main calculation is the precomputation involved in fitting the data and this can be impractically large if there are many spline coefficients to be calculated. Since the surface produced may be evaluated locally and efficiently, it would be advantageous to exploit local properties in order to fit the data in a piecewise manner. An algorithm to do this is presented.     

Inverses of quasi-tridiagonal matrices

Discretizations in various types of problems lead to quasi-tridiagonal matrices. In this paper, the inverse of a (nonsingular) quasi-tridiagonal matrix is obtained. In addition, a necessary and sufficient condition for a block matrix to have a quasi-tridiagonal inverse is derived.     

Inverses of Boolean matrices

For a Boolean matrix A, a g-inverse of A is a Boolean matrix G satisfying AGA=A, and a Vagner inverse is a g-inverse which in addition satisfies GAG=G. We give algorithms for finding all g-inverses, all Vagner inverses, and all of several other types of inverses including Moore-Penrose inverses. We give a criterion for a Boolean matrix to be regular, and criteria for the various types of inverse to exist. We count the numbers of Boolean matrices having Moore-Penrose and related types of inverses.     

Inverses of -distance matrices of a tree

The determinant and the inverse of the distance matrix of a tree have been investigated in the literature, following the classical formulas due to Graham and Pollak for the determinant, and due to Graham and Lovász for the inverse. We consider two q-analogs of the distance matrix of a tree and obtain formulas for the inverses of the two distance matrices. Yan and Yeh have previously obtained expressions for the determinants of the two distance matrices. Some related results are proved.     

On a class of matrices generated by certain generalized permutation matrices and applications

ABSTRACT

In this paper, we study a particular class of matrices generated by generalized permutation matrices corresponding to a subgroup of some permutation group. As applications, we first present a technique from which we can get closed formulas for the roots of many families of polynomial equations with degree between 5 and 10, inclusive. Then, we describe a tool that shows how to find solutions to Fermat's last theorem and Beal's conjecture over the square integer matrices of any dimension. Finally, simple generalizations of some of the concepts in number theory to integer square matrices are presented.     

A fuzzy clustering based technique for piecewise affine approximation of a class of nonlinear systems

In recent years piecewise affine (PWA) modeling has developed as an attractive tool for the approximation of various complex nonlinear systems. In spite of the wide application of PWA modeling, the optimal approximation of a continuous time nonlinear system with scalar functions by the minimum number of affine systems has not been addressed properly in literature. This paper deals with a fuzzy clustering based approach for the optimal PWA approximation of a class of continuous time nonlinear systems. The technique is based on the trade-off between increasing the approximation accuracy of the various nonlinear functions and simplifying the approximation by the minimum number of subsystems. As an application, the technique is utilized to obtain a PWA approximation of the glucose regulation system. Numerical simulations depicted that, for a given number of subsystems, the derived glucose regulation model provides an optimal approximation of the original nonlinear system. The model also provided some biological insight about the interactions involved in glucose regulation.     

A factorization theorem for banded matrices

In this paper we prove a factorization theorem for strictly m-banded totally positive matrices. We show that such a matrix is a product of m one-banded matrices with positive entries.     

Convergence of cubic piecewise function

In this paper we construct a piecewise cubic polynomial function for approximation of a class of functions. From application point of view an explicit representation of the function is obtained. The convergence of constructed function has been discussed. The proofs of the results are simpler and shorter.     

An invariant deflation for lower banded matrices

Using an eigenvector of a complex matrix A, a unitary matrix U is constructed, so that U^HAU deflates A, and this deflation preserves some special structural properties of A, e.g., the Hessenberg form, the lower banded structure, and the symmetry (in case A is real).     

Coalescing points for eigenvalues of banded matrices depending on parameters with application to banded random matrix functions

Numerical Algorithms - In this work, we develop and implement new numerical methods to locate generic degeneracies (i.e., isolated parameters’ values where the eigenvalues coalesce) of banded...     

The structured distance to normality of banded Toeplitz matrices

Spectral properties of normal (2k+1)-banded Toeplitz matrices of order n, with k≤⌊ n/2⌋, are described. Formulas for the distance of (2k+1)-banded Toeplitz matrices to the algebraic variety of similarly structured normal matrices are presented.     

On spline approximation for a class of integral equations. I: Galerkin and collocation methods with piecewise polynomials

We consider the numerical solution of a class of one-dimensional non-compact integral equations by Galerkin and collocation methods and their iterated variants, using piecewise polynomials as basis functions. In particular, we obtain new results for the stability of the approximation methods, without any restriction on the norm of the integral operators. Furthermore, we extend results of Chandler and Graham^4,6 concerning error estimates and superconvergence to a more general class of operators.     

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.     

The retraction algorithm for factoring banded symmetric matrices

Let A be an n × n symmetric matrix of bandwidth 2m + 1. The matrix need not be positive definite. In this paper we will present an algorithm for factoring A which preserves symmetry and the band structure and limits element growth in the factorization. With this factorization one may solve a linear system with A as the coefficient matrix and determine the inertia of A, the number of positive, negative, and zero eigenvalues of A. The algorithm requires between 1/2nm² and 5/4nm² multiplications and at most (2m + 1)n locations compared to non‐symmetric Gaussian elimination which requires between nm² and 2nm² multiplications and at most (3m + 1)n locations. Our algorithm reduces A to block diagonal form with 1 × 1 and 2 × 2 blocks on the diagonal. When pivoting for stability and subsequent transformations produce non‐zero elements outside the original band, column/row transformations are used to retract the bandwidth. To decrease the operation count and the necessary storage, we use the fact that the correction outside the band is rank‐1 and invert the process, applying the transformations that would restore the bandwidth first, followed by a modified correction. This paper contains an element growth analysis and a computational comparison with LAPACKs non‐symmetric band routines and the Snap‐back code of Irony and Toledo. Copyright © 2007 John Wiley & Sons, Ltd.