Determinant of the distance matrix of a tree with matrix weights

Let T be a tree with n vertices and let D be the distance matrix of T. According to a classical result due to Graham and Pollack, the determinant of D is a function of n, but does not depend on T. We allow the edges of T to carry weights, which are square matrices of a fixed order. The distance matrix D of T is then defined in a natural way. We obtain a formula for the determinant of D, which involves only the determinants of the sum and the product of the weight matrices.     

On Euclidean distance matrices

If A is a real symmetric matrix and P is an orthogonal projection onto a hyperplane, then we derive a formula for the Moore-Penrose inverse of PAP. As an application, we obtain a formula for the Moore-Penrose inverse of an Euclidean distance matrix (EDM) which generalizes formulae for the inverse of a EDM in the literature. To an invertible spherical EDM, we associate a Laplacian matrix (which we define as a positive semidefinite n × n matrix of rank n − 1 and with zero row sums) and prove some properties. Known results for distance matrices of trees are derived as special cases. In particular, we obtain a formula due to Graham and Lovász for the inverse of the distance matrix of a tree. It is shown that if D is a nonsingular EDM and L is the associated Laplacian, then D⁻¹ − L is nonsingular and has a nonnegative inverse. Finally, infinitely divisible matrices are constructed using EDMs.     

Inverse of the distance matrix of a block graph

A connected graph G, whose 2-connected blocks are all cliques (of possibly varying sizes) is called a block graph. Let D be its distance matrix. By a theorem of Graham, Hoffman and Hosoya, we have det(D)?≠?0. We give a formula for both the determinant and the inverse, D ^?1 of D.     

Fast Algorithms with Preprocessing for Matrix-Vector Multiplication Problems

In this paper the problem of complexity of multiplication of a matrix with a vector is studied for Toeplitz, Hankel, Vandermonde, and Cauchy matrices and for matrices connected with them (i.e., for transpose, inverse, and transpose to inverse matrices). The proposed algorithms have complexities of at most O(n log²n) flops and in a number of cases they improve the known estimates. In these algorithms, in a separate preprocessing phase, are singled out all the actions on the preparation of a given matrix which aimed at the reduction of the complexity of the second stage of computations directly connected with multiplication by an arbitrary vector. Effective algorithms for computing the Vandermonde determinant and the determination of a Cauchy matrix are given.     

A simple proof of Graham and Pollak's theorem

Graham and Pollak [Bell System Tech. J. 50 (1971) 2495-2519] obtained a beautiful formula on the determinant of distance matrices of trees, which is independent of the structure of the trees. In this paper we give a simple proof of Graham and Pollak's result.     

Algebraic properties of Manin matrices 1

We study a class of matrices with noncommutative entries, which were first considered by Yu.I. Manin in 1988 in relation with quantum group theory. They are defined as “noncommutative endomorphisms” of a polynomial algebra. More explicitly their defining conditions read: (1) elements in the same column commute; (2) commutators of the cross terms are equal: [M_ij,M_kl]=[M_kj,M_il] (e.g. [M₁₁,M₂₂]=[M₂₁,M₁₂]). The basic claim is that despite noncommutativity many theorems of linear algebra hold true for Manin matrices in a form identical to that of the commutative case. Moreover in some examples the converse is also true, that is, Manin matrices are the most general class of matrices such that linear algebra holds true for them. The present paper gives a complete list and detailed proofs of algebraic properties of Manin matrices known up to the moment; many of them are new. In particular we provide complete proofs that an inverse to a Manin matrix is again a Manin matrix and for the Schur formula for the determinant of a block matrix; we generalize the noncommutative Cauchy–Binet formulas discovered recently arXiv:0809.3516, which includes the classical Capelli and related identities. We also discuss many other properties, such as the Cramer formula for the inverse matrix, the Cayley–Hamilton theorem, Newton and MacMahon–Wronski identities, Plücker relations, Sylvester's theorem, the Lagrange–Desnanot–Lewis Carroll formula, the Weinstein–Aronszajn formula, some multiplicativity properties for the determinant, relations with quasideterminants, calculation of the determinant via Gauss decomposition, conjugation to the second normal (Frobenius) form, and so on and so forth. Finally several examples and open question are discussed. We refer to [A. Chervov, G. Falqui, Manin matrices and Talalaev's formula, J. Phys. A 41 (2008) 194006; V. Rubtsov, A. Silantiev, D. Talalaev, Manin matrices, elliptic commuting families and characteristic polynomial of quantum gl_n elliptic Gaudin model, in press] for some applications in the realm of quantum integrable systems.     

On unimodular graphs

We study graphs whose adjacency matrices have determinant equal to 1 or −1, and characterize certain subclasses of these graphs. Graphs whose adjacency matrices are totally unimodular are also characterized. For bipartite graphs having a unique perfect matching, we provide a formula for the inverse of the corresponding adjacency matrix, and address the problem of when that inverse is diagonally similar to a nonnegative matrix. Special attention is paid to the case that such a graph is unicyclic.     

A disjoint idempotent decomposition for linear combinations produced from two commutative tripotent matrices and its applications

A square matrix A of order n is said to be tripotent if A ³?=?A. In this note, we give a nine-term disjoint idempotent decomposition for the linear combination of two commutative tripotent matrices and their products. Using the decomposition, we derive some closed-form formulae for the eigenvalues, determinant, rank, trace, power, inverse and group inverse of the linear combinations. In particular, we show that the linear combinations of two commutative tripotent elements and their products can produce 3⁹?=?19,683 tripotent elements.     

基于两类切比雪夫多项式的循环矩阵行列式的计算

利用多项式因式分解的逆变换,结合循环矩阵和切比雪夫多项式的特殊结构,首先研究第三类和第四类切比雪夫多项式的通项公式,并给出第三类、第四类切比雪夫多项式的关于行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式的显式表达式,最后给出算法实施步骤.     

Additive results for the Drazin inverse of block matrices and applications

In this paper, we consider the Drazin inverse of a sum of two matrices and derive additive formulas under conditions weaker than those used in some recent papers on the subject. As a corollary we get the main results from the paper of Yang and Liu [H. Yang, X. Liu, The Drazin inverse of the sum of two matrices and its applications, J. Comput. Appl. Math. 235 (2011) 1412-1417]. As an application we give some new representations for the Drazin inverse of a block matrix.     

Identities for minors of the Laplacian, resistance and distance matrices

It is shown that if L and D are the Laplacian and the distance matrix of a tree respectively, then any minor of the Laplacian equals the sum of the cofactors of the complementary submatrix of D, up to sign and a power of 2. An analogous, more general result is proved for the Laplacian and the resistance matrix of any graph. A similar identity is proved for graphs in which each block is a complete graph on r vertices, and for q-analogues of such matrices of a tree. Our main tool is an identity for the minors of a matrix and its inverse.     

包含切比雪夫多项式的循环矩阵行列式的计算

行首加r尾r右循环矩阵和行尾加r首r左循环矩阵是两种特殊类型的矩阵,这篇论文中就是利用多项式因式分解的逆变换这一重要的技巧以及这类循环矩阵漂亮的结构和切比雪夫多项式的特殊的结构,分别讨论了第一类、第二类切比雪夫多项式的关于行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式,从而给出了行首加r尾r右循环矩阵和行尾加r首r左循环矩阵的行列式显式表达式.这些显式表达式与切比雪夫多项式以及参数r有关.这一问题的应用背景主要在循环编码,图像处理等信息理论方面.     

New inversion formulas for matrices classified in terms of their distance from Toeplitz matrices

The problem of solving linear equations, or equivalently of inverting matrices, arises in many fields. Efficient recursive algorithms for finding the inverses of Toeplitz or displacement-type matrices have been known for some time. By introducting a way of characterizing matrices in terms of their “distance” from being Toeplitz, a natural extension of these algorithms is obtained. Several new inversion formulas for the representation of the inverse of non-Toeplitz matrices are also presented.     

Completely normal matrices

Normal matrices in which all submatrices are normal are said to be completely normal. We characterize this class of matrices, determine the possible inertias of a particular completely normal matrix, and show that real matrices in this class are closed under (general) Schur complementation. We provide explicit formulas for the Moore–Penrose inverse of a completely normal matrix of size at least four. A result on irreducible principally normal matrices is derived as well.     

Inversion of conjugate-Toeplitz matrices and conjugate-Hankel matrices

The inverses of conjugate-Toeplitz (CT) and conjugate-Hankel (CH) matrices can be expressed by the Gohberg–Heinig type formula. We obtain an explicit inverse formula of CT matrix. Similarly, the formula and the decomposition of the inverse of a CH matrix are provided. Also the stability of the inverse formulas of CT and CH matrices are discussed. Examples are provided to verify the feasibility of the algorithms.     

可逆矩阵的高次伴随矩阵

用数学归纳法推出了可逆矩阵的高次伴随矩阵的公式,并结合可逆矩阵的基本公式得出了可逆矩阵的高次伴随矩阵的行列式和逆矩阵,给出了可逆矩阵的高次伴随矩阵的特征值和特征向量的表示公式,最后讨论了若干个可逆矩阵的乘积的高次伴随矩阵.     

Torsion formulas for signed graphs

Following our recent exposition on the algebraic foundations of signed graphs, we introduce bond (circuit) basis matrices for the tension (flow) lattices of signed graphs, and compute the torsions of such matrices and Laplacians. We present closed formulas for the torsions of the incidence matrix, the Laplacian, bond basis matrices, and circuit basis matrices. These formulas show that the torsions of all such matrices are powers of 2, and so imply that the matroids of signed graphs are representable over any field of characteristic not 2. A notable feature of using torsion is that the Matrix-Tree formula for ordinary graphs and Zaslavsky’s formula for unbalanced signed graphs are unified into one Matrix-Basis formula in terms of the torsion of its Laplacian matrix, rather than in terms of its determinant, which vanishes for an ordinary graph unless one row is deleted from the incidence matrix.     

Properties of Hadamard product of inverse M‐matrices

This paper concerns with the properties of Hadamard product of inverse M‐matrices. Structures of tridiagonal inverse M‐matrices and Hessenberg inverse M‐matrices are analysed. It is proved that the product A ○ A^T satisfies Willoughby's necessary conditions for being an inverse M‐matrix when A is an irreducible inverse M‐matrix. It is also proved that when A is either a Hessenberg inverse M‐matrix or a tridiagonal inverse M‐matrix then A ○ A^T is an inverse M‐matrix. Based on these results, the conjecture that A ○ A^T is an inverse M‐matrix when A is an inverse M‐matrix is made. Unfortunately, the conjecture is not true. Copyright © 2004 John Wiley Sons, Ltd.     

Biorthogonal Polynomial Bases and Vandermonde-like Matrices

This article considers a family of Gram matrices of pairs of bases of a finite dimensional vector space of polynomials with respect to certain indefinite inner products. Such a family includes all the generalized confluent Vandermonde matrices relative to any polynomial basis, like the Chebyshev-Vandermonde matrices, for example. Using the biorthogonality of pairs of bases with respect to a divided difference functional, properties of matrices and functionals, as well as interpolation formulas are obtained. I show that the computation of the inverse of a Vandermonde-like matrix is essentially equivalent to the computation of the partial fractions decompositions of a set of rational functions with a common denominator. I also explain why the various Chebyshev-Vandermonde matrices are the simplest generalizations of the classic Vandermonde matrices and describe a simple algorithm for the computation of their inverses, which requires a number of multiplications of the order of 3N².     

Distributions of eigenvalues and inertias of some block Hermitian matrices consisting of orthogonal projectors

A complex square matrix A is called an orthogonal projector if A ²?=?A?=?A*, where A* is the conjugate transpose of A. In this article, we first give some formulas for calculating the distributions of real eigenvalues of a linear combination of two orthogonal projectors. Then, we establish various expansion formulas for calculating the inertias, ranks and signatures of some 2?×?2 and 3?×?3, as well as k?×?k block Hermitian matrices consisting of two orthogonal projectors. Many applications of the formulas are presented in characterizing interval distributions of numbers of eigenvalues, and nonsingularity of these block Hermitian matrices. In addition, necessary and sufficient conditions are given for various equalities and inequalities of these block Hermitian matrices to hold.