Finding Well-Conditioned Similarities to Block-Diagonalize Nonsymmetric Matrices Is NP-Hard

Given an upper triangular matrix A ∈ R^n×n and a tolerance τ, we show that the problem of finding a similarity transformation G such that G⁻¹AG is block diagonal with the condition number of G being at most τ is NP-hard. Let ƒ(n) be a polynomial in n. We also show that the problem of finding a similarity transformation G such that G⁻¹AG is block-diagonal with the condition number of G being at most ƒ(n) times larger than the smallest possible is NP-hard.     

Numerical radius and zero pattern of matrices

Let A be an n×n complex matrix and r be the maximum size of its principal submatrices with no off-diagonal zero entries. Suppose A has zero main diagonal and x is a unit n-vector. Then, letting ‖A‖ be the Frobenius norm of A, we show that

|〈Ax,x〉^|2?(1−1/2r−1/2n)‖A^‖2.     

Doubly stochastic matrices with some equal diagonal sums

Let A be doubly stochastic, and let τ₁,…,τ_m be m mutually disjoint zero diagonals in A, 1?m?n-1. E. T. H. Wang conjectured that if every diagonal in A disjoint from each τ_k (k=1,…,m) has a constant sum, then all entries in A off the m zero diagonals τ_k are equal to (n?m)^-1. Sinkhorn showed the conjecture to be correct. In this paper we generalize this result for arbitrary doubly stochastic zero patterns.     

Commuting extensions and cubature formulae

Based on a novel point of view on 1-dimensional Gaussian quadrature, we present a new approach to d-dimensional cubature formulae. It is well known that the nodes of 1-dimensional Gaussian quadrature can be computed as eigenvalues of the so-called Jacobi matrix. The d-dimensional analog is that cubature nodes can be obtained from the eigenvalues of certain mutually commuting matrices. These are obtained by extending (adding rows and columns to) certain noncommuting matrices A₁,...,A_d, related to the coordinate operators x₁,...,x_d, in R^d. We prove a correspondence between cubature formulae and “commuting extensions” of A₁,...,A_d, satisfying a compatibility condition which, in appropriate coordinates, constrains certain blocks in the extended matrices to be zero. Thus, the problem of finding cubature formulae can be transformed to the problem of computing (and then simultaneously diagonalizing) commuting extensions. We give a general discussion of existence and of the expected size of commuting extensions and briefly describe our attempts at computing them.     

On the Determinant of a Uniformly Distributed Complex Matrix

We derive the joint density for the singular values of a random complex matrix A uniformly distributed on ||A||_F = 1 This joint density allows us to obtain the conditional expectation of det(A^HA) = |det A|² given the smallest singular value. This result has been used by Shub and Smale in their analysis of the complexity of Bezout′s theorem.     

Doubly stochastic matrices which have certain diagonals with constant sums

Let A be an n×n doubly stochastic matrix and suppose that 1?m?n?1. Let τ₁,…,τ_m be m mutually disjoint zero diagonals in A, and suppose that every diagonal of A disjoint from τ₁,…,τ_m has a constant sum. Then aall entries of A off the m zero diagonals have the value (n?m)^?1. This verifies a conjecture of E.T. Wang.     

The Inertia Set of Nonnegative Symmetric Sign Pattern with Zero Diagonal

The inertia set of a symmetric sign pattern A is the set i(A) = {i(B) | B = B ^T ∈ Q(A)}, where i(B) denotes the inertia of real symmetric matrix B, and Q(A) denotes the sign pattern class of A. In this paper, a complete characterization on the inertia set of the nonnegative symmetric sign pattern A in which each diagonal entry is zero and all off-diagonal entries are positive is obtained. Further, we also consider the bound for the numbers of nonzero entries in the nonnegative symmetric sign patterns A with zero diagonal that require unique inertia.     

Sine transform based preconditioners for elliptic problems

We consider applying the preconditioned conjugate gradient (PCG) method to solving linear systems Ax = b where the matrix A comes from the discretization of second-order elliptic operators with Dirichlet boundary conditions. Let (L + Σ)Σ⁻¹(L^t + Σ) denote the block Cholesky factorization of A with lower block triangular matrix L and diagonal block matrix Σ. We propose a preconditioner M = (Lˆ + Σˆ)Σˆ⁻¹(Lˆ^t + Σˆ) with block diagonal matrix Σˆ and lower block triangular matrix Lˆ. The diagonal blocks of Σˆ and the subdiagonal blocks of Lˆ are respectively the optimal sine transform approximations to the diagonal blocks of Σ and the subdiagonal blocks of L. We show that for two-dimensional domains, the construction cost of M and the cost for each iteration of the PCG algorithm are of order O(n² log n). Furthermore, for rectangular regions, we show that the condition number of the preconditioned system M⁻¹A is of order O(1). In contrast, the system preconditioned by the MILU and MINV methods are of order O(n). We will also show that M can be obtained from A by taking the optimal sine transform approximations of each sub-block of A. Thus, the construction of M is similar to that of Level-1 circulant preconditioners. Our numerical results on two-dimensional square and L-shaped domains show that our method converges faster than the MILU and MINV methods. Extension to higher-dimensional domains will also be discussed. © 1997 John Wiley & Sons, Ltd.     

Quadratic matrix polynomials with a parameter

In this paper we examine matrix polynomials of the form L(λ) = Aλ² + εBλ + C in which ε is a parameter and A, B, C are positive definite. This arises in a natural way in the study of damped vibrating systems. The main results are concerned with the generic case in which det L(λ) has at least 2n − 1 distinct zeros for all ε ϵ [0, ∞). The values of ε at which there is a multiple zero of det L(λ) are of major interest in this analysis. The dependence of first degree factors of L(λ) on ε is also discussed.     

The combinatorial interpretation of the Jacobi identity from Lie algebras

Many enumeration problems concerning sequences emerge as special cases of the combinatorial interpretation of the identity tr log(I ? B) = log det(I ? B), where B is a matrix over the ring of formal power series with zero constant term. The identity is obtained from the well-known formula of Jacobi, namely, det(e^A) = e^tr(A). The problems include the derangement problem, the Simon Newcomb problem, the Smirnov problem, the Ménage problem, and their various generalizations. A conjecture is obtained for the enumeration of sequences with no increasing p runs.     

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.     

Thin Hessenberg pairs

A square matrix is called Hessenberg whenever each entry below the subdiagonal is zero and each entry on the subdiagonal is nonzero. Let V denote a nonzero finite-dimensional vector space over a field K. We consider an ordered pair of linear transformations A:V→V and A^∗:V→V which satisfy both (i) and (ii) below.

(i)

There exists a basis for V with respect to which the matrix representing A is Hessenberg and the matrix representing A^∗ is diagonal.

(ii)

There exists a basis for V with respect to which the matrix representing A is diagonal and the matrix representing A^∗ is Hessenberg.

We call such a pair a thin Hessenberg pair (or TH pair). This is a special case of a Hessenberg pair which was introduced by the author in an earlier paper. We investigate several bases for V with respect to which the matrices representing A and A^∗ are attractive. We display these matrices along with the transition matrices relating the bases. We introduce an “oriented” version of called a TH system. We classify the TH systems up to isomorphism.     

Nonnegative matrices with power invariant zero patterns

If A is a nonsingular M-matrix, the elements of the sequence {A^?k} all have the same zero pattern. Using the Drazin inverse, we show that a similar zero pattern invariance property holds for a class of matrices which is larger than the generalized M-matrices.     

A conforming decomposition theorem,a piecewise linear theorem of the alternative,and scalings of matrices satisfying lower and upper bounds

A scaling of a nonnegative matrixA is a matrixXAY ^?1, whereX andY are nonsingular, nonnegative diagonal matrices. Some condition may be imposed on the scaling, for example, whenA is square,X=Y or detX=detY. We characterize matrices for which there exists a scaling that satisfies predetermined upper and lower bound. Our principal tools are a piecewise linear theorem of the alternative and a theorem decomposing a solution of a system of equations as a sum of minimal support solutions which conform with the given solutions.     

G-matrices,J-orthogonal matrices,and their sign patterns

A real matrix A is a G-matrix if A is nonsingular and there exist nonsingular diagonal matrices D₁ and D₂ such that A^?T = D₁AD₂, where A^?T denotes the transpose of the inverse of A. Denote by J = diag(±1) a diagonal (signature) matrix, each of whose diagonal entries is +1 or ?1. A nonsingular real matrix Q is called J-orthogonal if Q^TJQ = J. Many connections are established between these matrices. In particular, a matrix A is a G-matrix if and only if A is diagonally (with positive diagonals) equivalent to a column permutation of a J-orthogonal matrix. An investigation into the sign patterns of the J-orthogonal matrices is initiated. It is observed that the sign patterns of the G-matrices are exactly the column permutations of the sign patterns of the J-orthogonal matrices. Some interesting constructions of certain J-orthogonal matrices are exhibited. It is shown that every symmetric staircase sign pattern matrix allows a J-orthogonal matrix. Sign potentially J-orthogonal conditions are also considered. Some examples and open questions are provided.     

LU decomposition of M-matrices by elimination without pivoting

It is shown that if A or ?A is a singular M-matrix satisfying the generalized diagonal dominance condition y^TA?0 for some vector y? 0, then A can be factored into A = LU by a certain elimination algorithm, where L is a lower triangular M-matrix with unit diagonal and U is an upper triangular M-matrix. The existence of LU decomposition of symmetric permutations of A and for irreducible M-matrices and symmetric M-matrices follow as colollaries. This work is motivated by applications to the solution of homogeneous systems of linear equations Ax = 0, where A or ?A is an M-matrix. These applications arise, e.g., in the analysis of Markov chains, input-output economic models, and compartmental systems. A converse of the theorem metioned above can be established by considering the reduced normal form of A.     

A generalization of the fast LUP matrix decomposition algorithm and applications

We show that any m × n matrix A, over any field, can be written as a product, LSP, of three matrices, where L is a lower triangular matrix with l's on the main diagonal, S is an m × n matrix which reduces to an upper triangular matrix with nonzero diagonal elements when the zero rows are deleted, and P is an n × n permutation matrix. Moreover, L, S, and P can be found in O(m^α?1n) time, where the complexity of matrix multiplication is O(m^α). We use the LSP decomposition to construct fast algorithms for some important matrix problems. In particular, we develop O(m^α?1n) algorithms for the following problems, where A is any m × n matrix: (1) Determine if the system of equations $\text{A}\text{x}\text{=}\text{b}$ (where $\text{b}$ is a column vector) has a solution, and if so, find one such solution. (2) Find a generalized inverse, $\text{A}{}^1$, of A (i.e., $\text{AA}{}^1\text{A = A}$). (3) Find simultaneously a maximal independent set of rows and a maximal independent set of columns of A.     

On a conjecture of Kippenhahn about the characteristic polynomial of a pencil generated by two Hermitian matrices. I

Let A be an n × n complex matrix, and write A = H + iK, where i² = ?1 and H and K are Hermitian matrices. The characteristic polynomial of the pencil xH + yK is f(x, y, z) = det(zI ? xH ? yK). Suppose f(x, y, z) is factored into a product of irreducible polynomials. Kippenhahn [5, p. 212] conjectured that if there is a repeated factor, then there is a unitary matrix U such that U^?1AU is block diagonal. We prove that if f(x, y, z) has a linear factor of multiplicity greater than n?3, then H and K have a common eigenvector. This may be viewed as a special case of Kippenhahn’s conjecture.     

Invariant sets of arcs in network flow problems

This paper considers sets of arcs A = A⁺ ∪A⁻ in a network which have the property that for every max flow, the sum of the flows on the arcs A⁺ minus the sum of the flows on the arcs A⁻ is equal to a fixed constant. We show that minimal invariant sets always arise from cuts (not necessarily min cuts) in a natural way. These results are applied to matrices with given row and column sums to generalize a result of Brualdi and Ross.     

Quasi-diagonal C1-algebras

We consider perturbations of C¹-algebras by compact operators. We show that if A is a separable liminal algebra of operators on a separable Hilbert space, then it is a subalgebra of a compact perturbation of a block diagonal algebra.