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.     

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

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.     

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.     

A new graph parameter related to bounded rank positive semidefinite matrix completions

The Gram dimension $\mathrm{gd}(G)$ of a graph $G$ is the smallest integer $k\ge 1$ such that any partial real symmetric matrix, whose entries are specified on the diagonal and at the off-diagonal positions corresponding to edges of $G$ , can be completed to a positive semidefinite matrix of rank at most $k$ (assuming a positive semidefinite completion exists). For any fixed $k$ the class of graphs satisfying $\mathrm{gd}(G) \le k$ is minor closed, hence it can be characterized by a finite list of forbidden minors. We show that the only minimal forbidden minor is $K_{k+1}$ for $k\le 3$ and that there are two minimal forbidden minors: $K_5$ and $K_{2,2,2}$ for $k=4$ . We also show some close connections to Euclidean realizations of graphs and to the graph parameter $\nu ^=(G)$ of van der Holst (Combinatorica 23(4):633–651, 2003). In particular, our characterization of the graphs with $\mathrm{gd}(G)\le 4$ implies the forbidden minor characterization of the 3-realizable graphs of Belk (Discret Comput Geom 37:139–162, 2007) and Belk and Connelly (Discret Comput Geom 37:125–137, 2007) and of the graphs with $\nu ^=(G) \le 4$ of van der Holst (Combinatorica 23(4):633–651, 2003).     

On common monic divisors having a given canonical diagonal form for matrix polynomials

Under certain restrictions we give a condition for the existence of common monic divisors having a given diagonal form for nonsingular matrix polynomials, and we propose a method of finding them. Translated fromMatematicheskie Metody i Fiziko-Mekhanicheskie Polya, No. 37, 1994, pp. 28–32.