On completions of symmetric and antisymmetric block diagonal partial matrices

A partial matrix is a matrix where only some of the entries are given. We determine the maximum rank of the symmetric completions of a symmetric partial matrix where only the diagonal blocks are given and the minimum rank and the maximum rank of the antisymmetric completions of an antisymmetric partial matrix where only the diagonal blocks are given.     

Cyclic and diagonal products on a matrix

We unify the theory of cyclic and diagonal products of elements of matrices. We obtain some new results on diagonal similarity, diagonal equivalence, complete reducibility and total support.     

Cuts, matrix completions and graph rigidity

This paper brings together several topics arising in distinct areas: polyhedral combinatorics, in particular, cut and metric polyhedra; matrix theory and semidefinite programming, in particular, completion problems for positive semidefinite matrices and Euclidean distance matrices; distance geometry and structural topology, in particular, graph realization and rigidity problems. Cuts and metrics provide the unifying theme. Indeed, cuts can be encoded as positive semidefinite matrices (this fact underlies the approximative algorithm for max-cut of Goemans and Williamson) and both positive semidefinite and Euclidean distance matrices yield points of the cut polytope or cone, after applying the functions 1/π arccos(.) or √. When fixing the dimension in the Euclidean distance matrix completion problem, we find the graph realization problem and the related question of unicity of realization, which leads to the question of graph rigidity. Our main objective here is to present in a unified setting a number of results and questions concerning matrix completion, graph realization and rigidity problems. These problems contain indeed very interesting questions relevant to mathematical programming and we believe that research in this area could yield to cross-fertilization between the various fields involved.     

Multiple roots of diagonal multiples of a square matrix

We find conditions on an n-square matrix A, over a field F of characteristic ≠2, that are equivalent to the following property: for any n-diagonal D over F, the matrix DA has a multiple eigenvalue (or multiple permanental root). Further results of a combinatorial flavour are given in the same direction. We also prove a new criterion for the irreducibility of square matrices.     

Bounds on the diagonal elements of a unitary matrix

It was shown by A. Horn that the diagonal elements of a unitary n×n matrix satisfy a set of linear inequalities (Theorem I). We give a simple proof of this result, and we show that the diagonal elements satisfy additional linear inequalities (Theorem II) if the matrix is also symmetric.     

Bounds for eigenvalues and singular values of matrix completions

Bounds are given for eigenvalues of hermitian completions of partial hermitian matrices, and for singular values of completions of partial block triangular matrices.     

The inertia of a Hermitian matrix having prescribed diagonal blocks

For i=1,…,m let H_i be an n_i×n_i Hermitian matrix with inertia In(H_i)= (π_i, ν_i, δ_i). We characterize in terms of the π_i, ν_i, δ_i the range of In(H) where H varies over all Hermitian matrices which have a block decomposition H= (X_ij)_{i, j=1,…, m} in which X_ij is n_i×n_j and X_ii=H_i.     

The diagonal hypergraph of a matrix (bipartite graph)

Let A be an n x n matrix of 0's and 1's (a bipartite graph). The diagonal hypergraph of A is the hypergraph whose vertices correspond to the 1's (edges) of A and whose edges correspond to the positive diagonals (1-factors) of A. The numerical invariants of this hypergraph are investigated.     

Rank-preserving module maps

In this paper, we characterize rank one preserving module maps on a Hilbert C^*-module and study its applications on free probability theory.     

A probing method for computing the diagonal of a matrix inverse

The computation of some entries of a matrix inverse arises in several important applications in practice. This paper presents a probing method for determining the diagonal of the inverse of a sparse matrix in the common situation when its inverse exhibits a decay property, i.e. when many of the entries of the inverse are small. A few simple properties of the inverse suggest a way to determine effective probing vectors based on standard graph theory results. An iterative method is then applied to solve the resulting sequence of linear systems, from which the diagonal of the matrix inverse is extracted. The results of numerical experiments are provided to demonstrate the effectiveness of the probing method. Copyright © 2011 John Wiley & Sons, Ltd.     

Rank-preserving extensions of band matrices

Existence and uniqueness problems are studied for extensions of a band matrix R such that the rank of the extension does not exceed the maximum of the ranks of the submatrices in the band of R. Applications are given to positive semidefinite extensions and extensions of lower-triangular matrices to contractions or to unitary matrices.     

Rank-preserving extensions of band matrices

Existence and uniqueness problems are studied for extensions of a band matrix R such that the rank of the extension does not exceed the maximum of the ranks of the submatrices in the band of R. Applications are given to positive semidefinite extensions and extensions of lower-triangular matrices to contractions or to unitary matrices.     

A trace inequality for M-matrices and the symmetrizability of a real matrix by a positive diagonal matrix

The question of whether a real matrix is symmetrizable via multiplication by a diagonal matrix with positive diagonal entries is reduced to the corresponding question for M-matrices and related to Hadamard products. In the process, for a nonsingular M-matrix A, it is shown that tr(A^-1A^T) ? n, with equality if and only if A is symmetric, and that the minimum eigenvalue of A^-1 ° A is ? 1 with equality in the irreducible case if and only if A is positive diagonally symmetrizable.     

The approximation characteristic of diagonal matrix in probabilistic setting

In this paper, the approximation characteristic of a diagonal matrix in probabilistic and average case settings is investigated. And the asymptotic degree of the probabilistic linear (n,δ)$(n,\delta )$-width and p$p$-average linear n$n$-width of diagonal matrix M$M$ are determined.     

Block diagonal dominance of matrix and spectral inclusion regions

Suppose that comlex matrix A or order n is partitioned as where the diagonal submatrices A_(ⅱ) are square of order n_i(1≤i≤N) .If each A_(ⅱ)is nonsingular and satisfies sum from (j=1 j≠i) to N(‖A_(ij)~(-1)A_(ij)‖≤1),1≤i≤N. thon A is called quasi-block diagonally domfnant. Specially, if strictly inequality in(2) is valid for all 1≤i≤N then A is called quasi-block strictly diagonally dominant. If strict inequality in (2) is valid for at least one i (1≤i≤N) and     

Fast algorithms for placing large entries along the diagonal of a sparse matrix

Solving a sparse system of linear equations Ax=b is one of the most fundamental operations inside any circuit simulator. The equations/rows in the matrix A are often rearranged/permuted before factorization and applying direct or iterative methods to obtain the solution. Permuting the rows of the matrix A so that the entries with large absolute values lie on the diagonal has several advantages like better numerical stability for direct methods (e.g., Gaussian elimination) and faster convergence for indirect methods (such as the Jacobi method). Duff (2009) [3] has formulated this as a weighted bipartite matching problem (the MC64 algorithm). In this paper we improve the performance of the MC64 algorithm with a new labeling technique which improves the asymptotic complexity of updating dual variables from O(|V|+|E|) to O(|V|), where |V| is the order of the matrix A and |E| is the number of non-zeros. Experimental results from using the new algorithm, when benchmarked with both industry benchmarks and UFL sparse matrix collection, are very promising. Our algorithm is more than 60 times faster (than Duff’s algorithm) for sparse matrices with at least a million non-zeros.     

On interdependence between invariant factors of a block-triangular matrix and its diagonal blocks

Mathematical Notes - The interdependence between the invariant factors of a block-triangular matrix and its diagonal blocks is established under some constraints on its canonical diagonal form.     

A note on constructing a symmetric matrix with specified diagonal entries and eigenvalues

A finite step algorithm is given such that for any two vectorsa, R ⁿ witha majorized by , it computes a symmetric matrixH R ^{n x n} with the elements ofa and as its diagonal entries and eigenvalues, respectively.Supported in part by NSF grant CCR-9308399.Supported in part by China State Major Key Project for Basic Researches.