The Worst-Case GMRES for Normal Matrices

We study the convergence of GMRES for linear algebraic systems with normal matrices. In particular, we explore the standard bound based on a min-max approximation problem on the discrete set of the matrix eigenvalues. This bound is sharp, i.e. it is attainable by the GMRES residual norm. The question is how to evaluate or estimate the standard bound, and if it is possible to characterize the GMRES-related quantities for which this bound is attained (worst-case GMRES). In this paper we completely characterize the worst-case GMRES-related quantities in the next-to-last iteration step and evaluate the standard bound in terms of explicit polynomials involving the matrix eigenvalues. For a general iteration step, we develop a computable lower and upper bound on the standard bound. Our bounds allow us to study the worst-case GMRES residual norm as a function of the eigenvalue distribution. For hermitian matrices the lower bound is equal to the worst-case residual norm. In addition, numerical experiments show that the lower bound is generally very tight, and support our conjecture that it is to within a factor of 4/π of the actual worst-case residual norm. Since the worst-case residual norm in each step is to within a factor of the square root of the matrix size to what is considered an “average” residual norm, our results are of relevance beyond the worst case. This revised version was published online in July 2006 with corrections to the Cover Date.     

A fast and accurate algorithm for solving linear systems associated with a class of negative matrix

A class of negative matrices including Vandermonde-like matrices tends to be extremely ill-conditioned, and linear systems associated with this class of matrices appear in the polynomial interpolation problems. In this article, we present a fast and accurate algorithm with $O(n^2)$ complexity to solve the linear systems whose coefficient matrices belong to the class of negative matrix. We show that the inverse of any such matrix is generated in a subtraction-free manner. Consequently, the solutions of linear systems associated with the class of negative matrix are accurately determined by parameterization matrices of coefficient matrices, and a pleasantly componentwise forward error is provided to illustrate that each component of the solution is computed to high accuracy. Numerical experiments are performed to confirm the claimed high accuracy.     

On the computation of the Smith normal form of compound matrices

Compound matrices are encountered in many fields such as Matrix Theory, Systems Theory, Control Theory, etc. In the present paper we develop an efficient algorithm computing the Smith normal form of compound matrices. This algorithm is based on a new theorem establishing an equivalence relation between the Smith normal form of the compounds of a given matrix and the compounds of the Smith normal form of the given matrix. This revised version was published online in June 2006 with corrections to the Cover Date.     

When is a matrix unitary or Hermitian plus low rank?

Hermitian and unitary matrices are two representatives of the class of normal matrices whose full eigenvalue decomposition can be stably computed in quadratic computing complexity once the matrix has been reduced, for instance, to tridiagonal or Hessenberg form. Recently, fast and reliable eigensolvers dealing with low‐rank perturbations of unitary and Hermitian matrices have been proposed. These structured eigenvalue problems appear naturally when computing roots, via confederate linearizations, of polynomials expressed in, for example, the monomial or Chebyshev basis. Often, however, it is not known beforehand whether or not a matrix can be written as the sum of a Hermitian or unitary matrix plus a low‐rank perturbation. In this paper, we give necessary and sufficient conditions characterizing the class of Hermitian or unitary plus low‐rank matrices. The number of singular values deviating from 1 determines the rank of a perturbation to bring a matrix to unitary form. A similar condition holds for Hermitian matrices; the eigenvalues of the skew‐Hermitian part differing from 0 dictate the rank of the perturbation. We prove that these relations are linked via the Cayley transform. Then, based on these conditions, we identify the closest Hermitian or unitary plus rank k matrix to a given matrix A, in Frobenius and spectral norm, and give a formula for their distance from A. Finally, we present a practical iteration to detect the low‐rank perturbation. Numerical tests prove that this straightforward algorithm is effective.     

The unitary completion and QR iterations for a class of structured matrices

We consider the problem of completion of a matrix with a specified lower triangular part to a unitary matrix. In this paper we obtain the necessary and sufficient conditions of existence of a unitary completion without any additional constraints and give a general formula for this completion. The paper is mainly focused on matrices with the specified lower triangular part of a special form. For such a specified part the unitary completion is a structured matrix, and we derive in this paper the formulas for its structure. Next we apply the unitary completion method to the solution of the eigenvalue problem for a class of structured matrices via structured QR iterations.

     

The difference between doubly nonnegative and completely positive matrices

The convex cone of n×n completely positive (CP) matrices and its dual cone of copositive matrices arise in several areas of applied mathematics, including optimization. Every CP matrix is doubly nonnegative (DNN), i.e., positive semidefinite and component-wise nonnegative, and it is known that, for n4 only, every DNN matrix is CP. In this paper, we investigate the difference between 5×5 DNN and CP matrices. Defining a bad matrix to be one which is DNN but not CP, we: (i) design a finite procedure to decompose any n×n DNN matrix into the sum of a CP matrix and a bad matrix, which itself cannot be further decomposed; (ii) show that every bad 5×5 DNN matrix is the sum of a CP matrix and a single bad extreme matrix; and (iii) demonstrate how to separate bad extreme matrices from the cone of 5×5 CP matrices.     

Sign reversing and matrix classes

The concept of sign reversing is a useful tool to characterize certain matrix classes in linear complementarity problems. In this paper, we characterize the sign-reversal set of an arbitrary square matrixM in terms of the null spaces of the matricesI–⁁+⁁M, where ⁁ is a diagonal matrix such that 0⁁I. These matrices are used to characterize the membership ofM in the classes P₀, P, and the class of column-sufficient matrices. A simple proof of the Gale and Nikaido characterization theorem for the membership in P is presented.We also study the class of diagonally semistable matrices. We prove that this class is contained properly in the class of sufficient matrices. We show that to characterize the diagonally semistable property is equivalent to solving a concave Lagrangian dual problem. For 2×2 matrices, there is no duality gap between a primal problem and its Lagrangian problem. Such a primal problem is motivated by the definition of column sufficiency.The author would like to thank Professor Richard W. Cottle for his helpful comments on earlier versions of this paper. The author would also like to thank an anonymous referee for numerous helpful comments on this paper.     

On two particular cases of solving the normal Hankel problem

The normal Hankel problem is one of characterizing all the complex matrices that are normal and Hankel at the same time. The matrix classes that can contain normal Hankel matrices admit a parameterization by real 2 × 2 matrices with determinant one. Here, the normal Hankel problem is solved in the case where the characteristic matrix of a given class is an order two Jordan block for the eigenvalue 1 or ?1.     

Williamson matrices up to order 59

A recent result of Schmidt has brought Williamson matrices back into the spotlight. In this article, a new algorithm is introduced to search for hard to find Williamson matrices. We find all nonequivalent Williamson matrices of odd order n up to n = 59. It turns out that there are none for n = 35, 47, 53, 59 and it seems that the Turyn class may be the only infinite class of these matrices.      

On the representability of totally unimodular matrices on bidirected graphs

We present a polynomial time algorithm to construct a bidirected graph for any totally unimodular matrix B by finding node-edge incidence matrices Q and S such that QB=S. Seymour’s famous decomposition theorem for regular matroids states that any totally unimodular (TU) matrix can be constructed through a series of composition operations called k-sums starting from network matrices and their transposes and two compact representation matrices B₁,B₂ of a certain ten element matroid. Given that B₁,B₂ are binet matrices we examine the k-sums of network and binet matrices. It is shown that thek-sum of a network and a binet matrix is a binet matrix, but binet matrices are not closed under this operation for k=2,3. A new class of matrices is introduced, the so-called tour matrices, which generalise network, binet and totally unimodular matrices. For any such matrix there exists a bidirected graph such that the columns represent a collection of closed tours in the graph. It is shown that tour matrices are closed under k-sums, as well as under pivoting and other elementary operations on their rows and columns. Given the constructive proofs of the above results regarding the k-sum operation and existing recognition algorithms for network and binet matrices, an algorithm is presented which constructs a bidirected graph for any TU matrix.     

Hadamard matrices of small order and Yang conjecture

We show that 138 odd values of n<10000 for which a Hadamard matrix of order 4n exists have been overlooked in the recent handbook of combinatorial designs. There are four additional odd n=191, 5767, 7081, 8249 in that range for which Hadamard matrices of order 4n exist. There is a unique equivalence class of near‐normal sequences NN(36), and the same is true for NN(38) and NN(40). This means that the Yang conjecture on the existence of near‐normal sequences NN(n) has been verified for all even n⩽40, but it still remains open. © 2010 Wiley Periodicals, Inc. J Combin Designs 18: 254–259, 2010     

On tridiagonal matrices unitarily equivalent to normal matrices

In this article the unitary equivalence transformation of normal matrices to tridiagonal form is studied.It is well-known that any matrix is unitarily equivalent to a tridiagonal matrix. In case of a normal matrix the resulting tridiagonal inherits a strong relation between its super- and subdiagonal elements. The corresponding elements of the super- and subdiagonal will have the same absolute value.In this article some basic facts about a unitary equivalence transformation of an arbitrary matrix to tridiagonal form are firstly studied. Both an iterative reduction based on Krylov sequences as a direct tridiagonalization procedure via Householder transformations are reconsidered. This equivalence transformation is then applied to the normal case and equality of the absolute value between the super- and subdiagonals is proved. Self-adjointness of the resulting tridiagonal matrix with regard to a specific scalar product is proved. Properties when applying the reduction on symmetric, skew-symmetric, Hermitian, skew-Hermitian and unitary matrices and their relations with, e.g., complex symmetric and pseudo-symmetric matrices are presented.It is shown that the reduction can then be used to compute the singular value decomposition of normal matrices making use of the Takagi factorization. Finally some extra properties of the reduction as well as an efficient method for computing a unitary complex symmetric decomposition of a normal matrix are given.     

On a recursive inverse eigenvalue problem

Let s ₁, ..., s _n be arbitrary complex scalars. It is required to construct an n × n normal matrix A such that s _i is an eigenvalue of the leading principal submatrix A _i , i = 1, 2, ..., n. It is shown that, along with the obvious diagonal solution diag(s ₁, ..., s _n ), this problem always admits a much more interesting nondiagonal solution A. As a rule, this solution is a dense matrix; with the diagonal solution, it shares the property that each submatrix A _i is itself a normal matrix, which implies interesting connections between the spectra of the neighboring submatrices A _i and A _{i + 1}.     

The DJL Conjecture for CP Matrices over Special Inclines

Drew, Johnson, and Loewy conjectured that for n ≥ 4, the CP-rank of every n × n completely positive real matrix is at most [n²/4]. While this conjecture has recently been disproved for completely positive real matrices, we show that this conjecture is true for n × n completely positive matrices over certain special types of inclines. In addition, we prove an incline version of Markham's theorems which gives sufficient conditions for completely positive matrices over special inclines to have triangular factorizations.     

Out-of-band quasiseparable matrices

We study structured matrices which consist of a band part and quasiseparable parts below and upper the band. We extend algorithms known for quasiseparable matrices, i.e. for the case when the band consists of the main diagonal only, to a wider class of matrices. The matrices which we consider may be treated as an usual quasiseparable matrices with larger orders of generators. Hence one can apply the methods developed for usual quasiseparable matrices and obtain various linear complexity O(N) algorithms. However in this case the coefficients in N in the complexity estimates turns out to be quite large. In this paper we use the structure more accurately by division of the matrix into three parts in which the middle part is the band instead of diagonal as it is used for usual quasiseparable matrices. This approach allows to use better the structure of the matrix in order to improve the coefficients in N in the complexity estimates for the algorithms. This method works for algorithms which keep invariant the structure.     

A minimal residual method for linear polynomials in unitary matrices

A minimal residual method, called MINRES-N2, that is based on the use of unconventional Krylov subspaces was previously proposed by the authors for solving a system of linear equations Ax = b with a normal coefficient matrix whose spectrum belongs to an algebraic second-degree curve Γ. However, the computational scheme of this method does not cover matrices of the form A = αU + βI, where U is an arbitrary unitary matrix; for such matrices, Γ is a circle. Systems of this type are repeatedly solved when the eigenvectors of a unitary matrix are calculated by inverse iteration. In this paper, a modification of MINRES-N2 suitable for linear polynomials in unitary matrices is proposed. Numerical results are presented demonstrating the significant superiority of the modified method over GMRES as applied to systems of this class.     

Low-rank perturbations of symmetric matrices and their condensed forms under unitary congruences

The method MINRES-CN was earlier proposed by the authors for solving systems of linear equations with conjugate-normal coefficient matrices. It is now shown that this method is also applicable even if the coefficient matrix, albeit not conjugate-normal, is a low-rank perturbation of a symmetric matrix. If the perturbed matrix is still conjugate-normal, then, starting from some iteration step, the recursion underlying MINRES-CN becomes a three-term relation. These results are proved in terms of matrix condensed forms with respect to unitary congruences.     

Permutation Matrices, Wreath Products, and the Distribution of Eigenvalues

We consider a class of random matrix ensembles which can be constructed from the random permutation matrices by replacing the nonzero entries of the n×n permutation matrix matrix with M×M diagonal matrices whose entries are random Kth roots of unity or random points on the unit circle. Let X be the number of eigenvalues lying in a specified arc I of the unit circle, and consider the standardized random variable (X–E[X])/(Var(X))^1/2. We show that for a fixed set of arcs I ₁,...,I _N , the corresponding standardized random variables are jointly normal in the large n limit, and compare the covariance structures which arise with results for other random matrix ensembles.