Some improvements for two-sided bounds on the inverse of diagonally dominant tridiagonal matrices

In this paper, we obtain lower and upper bounds for the entries of the inverses of diagonally dominant tridiagonal matrices. First of all we derive the bounds for off-diagonal elements of the inverse as a function of the diagonal ones, then we improve the two-sided bounds for the diagonal entries obtaining sharper lower and upper bounds for all the elements of the inverse.     

On diagonal-Schur complements of block diagonally dominant matrices

It is known that the diagonal-Schur complements of strictly diagonally dominant matrices are strictly diagonally dominant matrices [J.Z. Liu, Y.Q. Huang, Some properties on Schur complements of H-matrices and diagonally dominant matrices, Linear Algebra Appl. 389 (2004) 365-380], and the same is true for nonsingular H-matrices [J.Z. Liu, J.C. Li, Z.T. Huang, X. Kong, Some properties of Schur complements and diagonal-Schur complements of diagonally dominant matrices, Linear Algebra Appl. 428 (2008) 1009-1030]. In this paper, we research the properties on diagonal-Schur complements of block diagonally dominant matrices and prove that the diagonal-Schur complements of block strictly diagonally dominant matrices are block strictly diagonally dominant matrices, and the same holds for generalized block strictly diagonally dominant matrices.     

Doubly stochastic matrices of trees

In this paper, we obtain sharp upper and lower bounds for the smallest entries of doubly stochastic matrices of trees and characterize all extreme graphs which attain the bounds. We also present a counterexample to Merris’ conjecture on relations between the smallest entry of the doubly stochastic matrix and the algebraic connectivity of a graph in [R. Merris, Doubly stochastic graph matrices II, Linear Multilinear Algebr. 45 (1998) 275–285].     

Eigenvalues for infinite matrices

This paper is concerned with the problem of determining the location of eigenvalues for diagonally dominant infinite matrices; upper and lower bounds for eigenvalues are established. For tridiagonal matrices, a numerical procedure for improving the bounds is given, and the approximation of the eigenvectors is also discussed. The techniques are illustrated for the solution of the well-known Mathieu's equation.     

On the inverses of general tridiagonal matrices

In this work, the sign distribution for all inverse elements of general tridiagonal H-matrices is presented. In addition, some computable upper and lower bounds for the entries of the inverses of diagonally dominant tridiagonal matrices are obtained. Based on the sign distribution, these bounds greatly improve some well-known results due to Ostrowski (1952) 23, Shivakumar and Ji (1996) 26, Nabben (1999) [21] and [22] and recently given by Peluso and Politi (2001) 24, Peluso and Popolizio (2008) 25 and so forth. It is also stated that the inverse of a general tridiagonal matrix may be described by 2n-2 parameters ( and ) instead of 2n+2 ones as given by El-Mikkawy (2004) 3, El-Mikkawy and Karawia (2006) 4 and Huang and McColl (1997) 10. According to these results, a new symbolic algorithm for finding the inverse of a tridiagonal matrix without imposing any restrictive conditions is presented, which improves some recent results. Finally, several applications to the preconditioning technology, the numerical solution of differential equations and the birth-death processes together with numerical tests are given.     

The inverse positivity of perturbed tridiagonal M-matrices

A well-known property of an M-matrix M is that the inverse is element-wise non-negative, which we write as M^-1?0. In this paper, we consider element-wise perturbations of non-symmetric tridiagonal M-matrices and obtain sufficient bounds on the perturbations so that the non-negative inverse persists. These bounds improve the bounds recently given by Kennedy and Haynes [Inverse positivity of perturbed tridiagonal M-matrices, Linear Algebra Appl. 430 (2009) 2312-2323]. In particular, when perturbing the second diagonals (elements (l,l+2) and (l,l-2)) of M, these sufficient bounds are shown to be the actual maximum allowable perturbations. Numerical examples are given to demonstrate the effectiveness of our estimates.     

Subdirect sums of P(P0)-matrices and totally nonnegative matrices

In this paper, the problem of when the sub-direct sum of two strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix is studied. In particular, it is shown that the subdirect sum of overlapping principal submatrices of strictly diagonally dominant P-matrices is a strictly diagonally dominant P-matrix. It is also established that the 2-subdirect sum of two totally nonnegative matrices is a totally nonnegative matrix under some conditions. It is obtained that a partial totally nonnegative matrix, whose graph of the specified entries is a monotonically labeled 2-chordal graph, has a totally nonnegative completion. Finally, a positive answer to the question (IV) in Fallat and Johnson [Shaun M. Fallat, C.R. Johnson, J.R. Torregrosa, A.M. Urbano, P-matrix completions under weak symmetry assumptions, Linear Algebra Appl. 312 (2000) 73-91] is given for P₀-matrices.     

Inversion of general tridiagonal matrices

In the current work, the authors present a symbolic algorithm for finding the inverse of any general nonsingular tridiagonal matrix. The algorithm is mainly based on the work presented in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] and [M.E.A. El-Mikkawy, A fast algorithm for evaluating nth order tridiagonal determinants, J. Comput. Appl. Math. 166 (2004) 581–584]. It removes all cases where the numeric algorithm in [Y. Huang, W.F. McColl, Analytic inversion of general tridiagonal matrices, J. Phys. A 30 (1997) 7919–7933] fails. The symbolic algorithm is suited for implementation using Computer Algebra Systems (CAS) such as MACSYMA, MAPLE and MATHEMATICA. An illustrative example is given.     

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.     

A note on preconditional diagonally dominant matrices

This note points out that the main results of [Appl. Math. Comput. 114 (2000) 255] is not true. We show that (1) Theorem 2.1 in [Appl. Math. Comput. 114 (2000) 255] is well known, (2) There are no nonsingular matrices satisfying the sufficient conditions for ensuring diagonally dominance given in Theorem 3.1, and (3) Theorem 4.1 for preconditioning p-cyclic matrices is not true. We also prove that p-cyclic matrices can be column diagonally preconditioned, with a special row permutation if required, to be row diagonally dominant under some assumptions.     

Accurate solutions of diagonally dominant tridiagonal linear systems

In this paper, we settle Higham’s conjecture for the LU factorization of diagonally dominant tridiagonal matrices. We establish a strong componentwise perturbation bound for the solution of a diagonally dominant tridiagonal linear system, independent of the traditional condition number of the coefficient matrix. We then accurately and efficiently solve the linear system by the GTH-like algorithm without pivoting, as suggested by the perturbation result.     

Bounds for the infinity norm of the inverse for certain M- and H-matrices

The paper presents new two-sided bounds for the infinity norm of the inverse for the so-called PM-matrices, which form a subclass of the class of nonsingular M-matrices and contain the class of strictly diagonally dominant matrices. These bounds are shown to be monotone with respect to the underlying partitioning of the index set, and the equality cases are analyzed. Also an upper bound for the infinity norm of the inverse of a PH-matrix (whose comparison matrix is a PM-matrix) is derived. The known Ostrowski, Ahlberg–Nilson–Varah, and Mora?a bounds are shown to be special cases of the upper bound obtained.     

Convergence of generalized AOR iterative method for linear systems with strictly diagonally dominant matrices

In this paper, some improvements on Darvishi and Hessari [On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Appl. Math. Comput. 176 (2006) 128–133] are presented for bounds of the spectral radius of _lω,r$l_{\omega ,r}$, which is the iterative matrix of the generalized AOR (GAOR) method. Subsequently, some new sufficient conditions for convergence of GAOR method will be given, which improve some results of Darvishi and Hessari [On convergence of the generalized AOR method for linear systems with diagonally dominant coefficient matrices, Appl. Math. Comput. 176 (2006) 128–133].     

Relative eigenvalue and singular value perturbations of scaled diagonally dominant matrices

The paper derives improved relative perturbation bounds for the eigenvalues of scaled diagonally dominant Hermitian matrices and new relative perturbation bounds for the singular values of symmetrically scaled diagonally dominant square matrices. The perturbation result for the singular values enlarges the class of well-behaved matrices for accurate computation of the singular values. AMS subject classification (2000)  65F15     

New lower bounds on eigenvalue of the Hadamard product of an M-matrix and its inverse

Some new lower bounds for the minimum eigenvalue of the Hadamard product of an M-matrix and its inverse are given. These bounds improve the results of [H.B. Li, T.Z. Huang, S.Q. Shen, H. Li, Lower bounds for the minimum eigenvalue of Hadamard product of an M-matrix and its inverse, Linear Algebra Appl. 420 (2007) 235-247].     

Minimum rank problems

A graph describes the zero-nonzero pattern of a family of matrices, with the type of graph (undirected or directed, simple or allowing loops) determining what type of matrices (symmetric or not necessarily symmetric, diagonal entries free or constrained) are described by the graph. The minimum rank problem of the graph is to determine the minimum among the ranks of the matrices in this family; the determination of maximum nullity is equivalent. This problem has been solved for simple trees [P.M. Nylen, Minimum-rank matrices with prescribed graph, Linear Algebra Appl. 248 (1996) 303-316, C.R. Johnson, A. Leal Duarte, The maximum multiplicity of an eigenvalue in a matrix whose graph is a tree, Linear and Multilinear Algebra 46 (1999) 139-144], trees allowing loops [L.M. DeAlba, T.L. Hardy, I.R. Hentzel, L. Hogben, A. Wangsness. Minimum rank and maximum eigenvalue multiplicity of symmetric tree sign patterns, Linear Algebra Appl. 418 (2006) 389-415], and directed trees allowing loops [F. Barioli, S. Fallat, D. Hershkowitz, H.T. Hall, L. Hogben, H. van der Holst, B. Shader, On the minimum rank of not necessarily symmetric matrices: a preliminary study, Electron. J. Linear Algebra 18 (2000) 126-145]. We survey these results from a unified perspective and solve the minimum rank problem for simple directed trees.     

The kth lower bases of primitive non-powerful signed digraphs

In [J. Shao, L. You, H. Shan, Bound on the bases of irreducible generalized sign pattern matrices, Linear Algebra Appl. 427 (2007) 285-300], the authors extended the concept of the base from powerful sign pattern matrices to non-powerful irreducible sign pattern matrices. Recently, the kth local bases and the kth upper bases, which are generalizations of the bases, of primitive non-powerful signed digraphs were introduced. In this paper, we introduce a new parameter called the kth lower bases of primitive non-powerful signed digraphs and obtain some bounds for it. For some cases, the bounds we obtain are best possible and the extremal signed digraphs are characterized, respectively. Moreover, we show that there exist “gaps” in the kth lower bases set of primitive non-powerful signed digraphs.     

论几类广义严格对角占优矩阵

1引言 设A=（a_η）∈Cm~(3n),若存在正对角阵D.使得AD为严格对角占优矩阵，则A称为广义严格对角占优矩阵，记作A∈SGDDM.     

On weak generalized positive subdefinite matrices and the linear complementarity problem

In this article, we present a weaker version of the class of generalized positive subdefinite matrices introduced by Crouzeix and Komlósi [J.P. Crouzeix and S. Komlósi, The Linear Complementarity Problem and the Class of Generalized Positive Subdefinite Matrices, Applied Optimization, Vol. 59, Kluwer, Dordrecht, 2001, pp. 45–63], which is new in the literature, and obtain some properties of weak generalized positive subdefinite (WGPSBD) matrices. We show that this weaker class of matrices is also captured by row-sufficient matrices introduced by Cottle et al. [R.W. Cottle, J.S. Pang, and V. Venkateswaran, Sufficient matrices and the linear complementarity problem, Linear Algebra Appl. 114/115 (1989), pp. 231–249] and show that for WGPSBD matrices under appropriate assumptions, the solution set of a linear complementarity problem is the same as the set of Karush–Kuhn–Tucker-stationary points of the corresponding quadratic programming problem. This further extends the results obtained in an earlier paper by Neogy and Das [S.K. Neogy and A.K. Das, Some properties of generalized positive subdenite matrices, SIAM J. Matrix Anal. Appl. 27 (2006), pp. 988–995].     

On the stability of the cyclic reduction without back substitution for tridiagonal systems

Componentwise error analysis for a modification of the cyclic reduction without back substitution for a tridiagonal system is presented. We consider relative roundoff errors and equivalent perturbations, so the main supposition is that all the data is nonzero. First, backward analysis for the computation of each component of the solution in separate is presented. Bounds on the relative equivalent perturbations are obtained depending on two constants. From these bounds it is easy to obtain a componentwise forward error analysis. Then the two constants are defined for some special classes of matrices, i.e. diagonally dominant (row or column), symmetric positive definite, totally nonnegative andM-matrices, and it is shown that the bounds for these classes of matrices are small.The author was supported by Grants MM-211/92 and MM-434/94 from the National Scientific Research Fund of the Bulgarian Ministry of Education and Science.