Search

A promising approach to solving sparse systems of equations involves creating an augmented system that is symmetric quasi-definite. The attraction of this approach stems from being able to use powerful algorithms and efficient data structures that have been developed for sparse positive definite systems. In this article, bounds are derived for the condition number of the Schur complements that emerge when symmetric Gaussian elimination is applied to these quasi-definite matrices. An application of these bounds to solving regularized linear least squares problems is discussed. For the corresponding linear systems, the bounds may be used to justify a reordering based solely on sparsity preservation considerations.

Symmetric quasi-definite matrices arise in numerous applications, notably in interior point methods in mathematical programming. Several authors have derived various properties of these matrices. This article provides a list of some previously known properties and adds a number of others that are believed to be new.

It is well known that for any distinct real numbers $\lambda_{1},\ldots, \lambda_{n}$ there exists a doubly symmetric (i.e., symmetric and persymmetric or, equivalently, symmetric and centrosymmetric) tridiagonal real $n \times n$ matrix $T$ with the $\lambda$'s as its eigenvalues. Such a matrix can be constructed finitely using only arithmetic operations and square roots. We prove in this paper that the analogous assertions hold for any distinct complex numbers $\lambda_{1}, \ldots, \lambda_{n}$ with $T$ being a complex matrix. It follows that any complex $n \times n$ matrix with distinct eigenvalues is similar to a doubly symmetric tridiagonal matrix. The condition that the eigenvalues be distinct is essential: we show that the tridiagonal form above does not exist or is trivial (depending on the Jordan structure imposed) if $\lambda_1 = \lambda_2 = \lambda_3 = 0$.

The polar decomposition of a square matrix is a major step toward the singular value decomposition, and is an important device in its own right. Singular values of a matrix $A$, being the eigenvalues for a matrix closely related to $A$, generally cannot be computed by a finite process if only arithmetic operations and radicals are allowed. However, this consideration alone does not prove that the polar decomposition is not finitely computable. The problem of finite computability of the polar decomposition is not settled in this paper, but we do show it to be equivalent to the following simpler-looking problem. Suppose $f$ is a real polynomial of degree $ n > 4$, and all the roots of $f$ are distinct positive numbers. Denote by $g$ a polynomial of the same degree whose zeros are the positive square roots of the zeros of $f$. Can this polynomial $g$ always be computed finitely for a given polynomial $f$? In the Appendix we discuss one nontrivial situation where the polar decomposition can indeed be computed finitely.

In this paper, a QR-like algorithm, called the con-QR algorithm, for computing the Youla form of a general complex matrix is presented. The Youla form is an analog of the Schur form where unitary congruences instead of unitary similarities are employed. We introduce a set of invariants of a unitary congruence transformation which are called coneigenvalues, and discuss their condition. Finally, the practical value of the Youla form is discussed.

After the paper cited in the title [George and Ikramov, SIAM J. Matrix Anal. Appl., 17 (1996), pp. 348--354] was sent to the printer, the authors succeeded in finding a way to show that the answer to the title question is no. This brief note contains a proof of the result.