Derivatives for antisymmetric tensor powers and perturbation bounds

In an earlier paper (R. Bhatia, T. Jain, Higher order derivatives and perturbation bounds for determinants, Linear Algebra Appl. 431 (2009) 2102-2108) we gave formulas for derivatives of all orders for the map that takes a matrix to its determinant. In this paper we continue that work, and find expressions for the derivatives of all orders for the antisymmetric tensor powers and for the coefficients of the characteristic polynomial. We then evaluate norms of these derivatives, and use them to obtain perturbation bounds.     

Singularity, Wielandt’s lemma and singular values

In this study, some upper and lower bounds for singular values of a general complex matrix are investigated, according to singularity and Wielandt’s lemma of matrices. Especially, some relationships between the singular values of the matrix A and its block norm matrix are established. Based on these relationships, one may obtain the effective estimates for the singular values of large matrices by using the lower dimension norm matrices. In addition, a small error in Piazza (2002) [G. Piazza, T. Politi, An upper bound for the condition number of a matrix in spectral norm, J. Comput. Appl. Math. 143 (1) (2002) 141-144] is also corrected. Some numerical experiments on saddle point problems show that these results are simple and sharp under suitable conditions.     

Sharp bounds on the spectral radius of a nonnegative matrix

We give upper and lower bounds for the spectral radius of a nonnegative matrix using its row sums and characterize the equality cases if the matrix is irreducible. Then we apply these bounds to various matrices associated with a graph, including the adjacency matrix, the signless Laplacian matrix, the distance matrix, the distance signless Laplacian matrix, and the reciprocal distance matrix. Some known results in the literature are generalized and improved.     

Bounds for the signless Laplacian energy

The energy of a graph G is the sum of the absolute values of the eigenvalues of the adjacency matrix of G. The Laplacian (respectively, the signless Laplacian) energy of G is the sum of the absolute values of the differences between the eigenvalues of the Laplacian (respectively, signless Laplacian) matrix and the arithmetic mean of the vertex degrees of the graph. In this paper, among some results which relate these energies, we point out some bounds to them using the energy of the line graph of G. Most of these bounds are valid for both energies, Laplacian and signless Laplacian. However, we present two new upper bounds on the signless Laplacian which are not upper bounds for the Laplacian energy.     

Theorems on Schur complement of block diagonally dominant matrices and their application in reducing the order for the solution of large scale linear systems

We firstly consider the block dominant degree for I-(II-)block strictly diagonally dominant matrix and their Schur complements, showing that the block dominant degree for the Schur complement of an I-(II-)block strictly diagonally dominant matrix is greater than that of the original grand block matrix. Then, as application, we present some disc theorems and some bounds for the eigenvalues of the Schur complement by the elements of the original matrix. Further, by means of matrix partition and the Schur complement of block matrix, based on the derived disc theorems, we give a kind of iteration called the Schur-based iteration, which can solve large scale linear systems though reducing the order by the Schur complement and the numerical example illustrates that the iteration can compute out the results faster.     

New upper solution bounds of the discrete algebraic Riccati matrix equation

In this note, we present upper matrix bounds for the solution of the discrete algebraic Riccati equation (DARE). Using the matrix bound of Theorem 2.2, we then give several eigenvalue upper bounds for the solution of the DARE and make comparisons with existing results. The advantage of our results over existing upper bounds is that the new upper bounds of Theorem 2.2 and Corollary 2.1 are always calculated if the stabilizing solution of the DARE exists, whilst all existing upper matrix bounds might not be calculated because they have been derived under stronger conditions. Finally, we give numerical examples to demonstrate the effectiveness of the derived results.     

Backward errors for eigenvalue and singular value decompositions

Summary. We present bounds on the backward errors for the symmetric eigenvalue decomposition and the singular value decomposition in the two-norm and in the Frobenius norm. Through different orthogonal decompositions of the computed eigenvectors we can define different symmetric backward errors for the eigenvalue decomposition. When the computed eigenvectors have a small residual and are close to orthonormal then all backward errors tend to be small. Consequently it does not matter how exactly a backward error is defined and how exactly residual and deviation from orthogonality are measured. Analogous results hold for the singular vectors. We indicate the effect of our error bounds on implementations for eigenvector and singular vector computation. In a more general context we prove that the distance of an appropriately scaled matrix to its orthogonal QR factor is not much larger than its distance to the closest orthogonal matrix. Received July 19, 1993     

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].     

Computation of eigenpair partial derivatives by Rayleigh–Ritz procedure

Based on Rayleigh–Ritz procedure, a new method is proposed for a few eigenpair partial derivatives of large matrices. This method simultaneously computes the approximate eigenpairs and their partial derivatives. The linear systems of equations that are solved for eigenvector partial derivatives are greatly reduced from the original matrix size. And the left eigenvectors are not required. Moreover, errors of the computed eigenpairs and their partial derivatives are investigated. Hausdorff distance and containment gap are used to measure the accuracy of approximate eigenpair partial derivatives. Error bounds on the computed eigenpairs and their partial derivatives are derived. Finally numerical experiments are reported to show the efficiency of the proposed method.     

Some necessary and some sufficient trace inequalities for Euclidean distance matrices

In this article, we use known bounds on the smallest eigenvalue of a symmetric matrix and Schoenberg's theorem to provide both necessary as well as sufficient trace inequalities that guarantee a matrix D is a Euclidean distance matrix, EDM. We also provide necessary and sufficient trace inequalities that guarantee a matrix D is an EDM generated by a regular figure.     

Some closer bounds of Perron root basing on generalized Perron complement

This paper is concerned with the bounds of the Perron root ρ(A) of a nonnegative irreducible matrix A. Two new methods utilizing the relationship between the Perron root of a nonnegative irreducible matrix and its generalized Perron complements are presented. The former method is efficient because it gives the bounds for ρ(A) only by calculating the row sums of the generalized Perron complement P_t(A/A[α]) or even the row sums of submatrices A[α],A[β],A[α,β] and A[β,α]. And the latter gives the closest bounds (just in this paper) of ρ(A). The results obtained by these methods largely improve the classical bounds. Numerical examples are given to illustrate the procedure and compare it with others, which shows that these methods are effective.     

Bounds for the zeros of polynomials from matrix inequalities - II

In this article, we present new bounds for the zeros of polynomials depending on some estimates for the spectral norms and the spectral radii of the square and the cube of the Frobenius companion matrix.     

Bounds for norms of the matrix inverse and the smallest singular value

In the first part, we obtain two easily calculable lower bounds for ‖A^-1‖, where ‖·‖ is an arbitrary matrix norm, in the case when A is an M-matrix, using first row sums and then column sums. Using those results, we obtain the characterization of M-matrices whose inverses are stochastic matrices. With different approach, we give another easily calculable lower bounds for ‖A^-1‖_∞ and ‖A^-1‖₁ in the case when A is an M-matrix. In the second part, using the results from the first part, we obtain our main result, an easily calculable upper bound for ‖A^-1‖₁ in the case when A is an SDD matrix, thus improving the known bound. All mentioned norm bounds can be used for bounding the smallest singular value of a matrix.     

Generalized block Lanczos methods for large unsymmetric eigenproblems

Generalized block Lanczos methods for large unsymmetric eigenproblems are presented, which contain the block Arnoldi method, and the block Arnoldi algorithms are developed. The convergence of this class of methods is analyzed when the matrix A is diagonalizable. Upper bounds for the distances between normalized eigenvectors and a block Krylov subspace are derived, and a priori theoretical error bounds for Ritz elements are established. Compared with generalized Lanczos methods, which contain Arnoldi's method, the convergence analysis shows that the block versions have two advantages: First, they may be efficient for computing clustered eigenvalues; second, they are able to solve multiple eigenproblems. However, a deep analysis exposes that the approximate eigenvectors or Ritz vectors obtained by general orthogonal projection methods including generalized block methods may fail to converge theoretically for a general unsymmetric matrix A even if corresponding approximate eigenvalues or Ritz values do, since the convergence of Ritz vectors needs more sufficient conditions, which may be impossible to satisfy theoretically, than that of Ritz values does. The issues of how to restart and to solve multiple eigenproblems are addressed, and some numerical examples are reported to confirm the theoretical analysis. Received July 7, 1994 / Revised version received March 1, 1997     

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.     

Improvement on the bound of Hermite matrix polynomials

In this paper, we introduce an improved bound on the 2-norm of Hermite matrix polynomials. As a consequence, this estimate enables us to present and prove a matrix version of the Riemann-Lebesgue lemma for Fourier transforms. Finally, our theoretical results are used to develop a novel procedure for the computation of matrix exponentials with a priori bounds. A numerical example for a test matrix is provided.     

Some necessary and some sufficient trace inequalities for Euclidean distance matrices

In this article, we use known bounds on the smallest eigenvalue of a symmetric matrix and Schoenberg's theorem to provide both necessary as well as sufficient trace inequalities that guarantee a matrix D is a Euclidean distance matrix, EDM . We also provide necessary and sufficient trace inequalities that guarantee a matrix D is an EDM generated by a regular figure.     

Bounds on the inverses of nonnegative triangular matrices with monotonicity properties

Some bounds on the entries and on the norm of the inverse of triangular matrices with nonnegative and monotone entries are found. All the results are obtained by exploiting the properties of the fundamental matrix of the recurrence relation which generates the sequence of the entries of the inverse matrix. One of the results generalizes a theorem contained in a recent article of one of the authors about Toeplitz matrices.     

Variance bounds, with an application to norm bounds for commutators

Murthy and Sethi [M.N. Murthy, V.K. Sethi, Sankhya Ser. B 27 (1965) 201-210] gave a sharp upper bound on the variance of a real random variable in terms of the range of values of that variable. We generalise this bound to the complex case and, more importantly, to the matrix case. In doing so, we make contact with several geometrical and matrix analytical concepts, such as the numerical range, and introduce the new concept of radius of a matrix.We also give a new and simplified proof for a sharp upper bound on the Frobenius norm of commutators recently proven by Böttcher and Wenzel [A. Böttcher, D. Wenzel, The Frobenius norm and the commutator, Linear Algebra Appl. 429 (2008) 1864-1885] and point out that at the heart of this proof lies exactly the matrix version of the variance we have introduced. As an immediate application of our variance bounds we obtain stronger versions of Böttcher and Wenzel’s upper bound.     

The energy of random graphs

In 1970s, Gutman introduced the concept of the energy E(G) for a simple graph G, which is defined as the sum of the absolute values of the eigenvalues of G. This graph invariant has attracted much attention, and many lower and upper bounds have been established for some classes of graphs among which bipartite graphs are of particular interest. But there are only a few graphs attaining the equalities of those bounds. We however obtain an exact estimate of the energy for almost all graphs by Wigner’s semi-circle law, which generalizes a result of Nikiforov. We further investigate the energy of random multipartite graphs by considering a generalization of Wigner matrix, and obtain some estimates of the energy for random multipartite graphs.