A Note on the Superoptimal Matrix Algebra Operators

We study the superoptimal Frobenius operators in several matrix vector spaces and in particular in the circulant algebra, by emphasizing both the algebraic and geometric properties. More specifically we prove a series of "negative" results that explain why this approximation procedure is not competitive with the optimal Frobenius approximation, although it could be used for regularization purposes.     

Matrices which commute with doubly stochastic matrices

The set doubly stochastic matrices which commute with the doubly stochastic matrices of any particular given rank is determined.     

Matrices which commute with doubly stochastic matrices

The set doubly stochastic matrices which commute with the doubly stochastic matrices of any particular given rank is determined.     

Stochastic matrices over cones

The notion of a stochastic operator in an ordered Banach space is specialized to a finite dimensional ordered real vector space. The classical limit theorems are obtained, and an application is made to non-homogeneous Markov chains. Finally, groups of nonnegative matrices are discussed.     

The doubly stochastic matrix equations x:aty= A and X Aty=t

For a doubly stochastic matrix A, each of the equations x:a^ty= A and X A^ty=^t is shown to have doubly stochastic solutions X and Y if and only if A lies in a subgroup of the semigroup of all doubly stochastic matrices of a given order. All elements of this semigroup which are left regular, right regular, or intra-regular are identified.     

Stochastic matrices over cones

The notion of a stochastic operator in an ordered Banach space is specialized to a finite dimensional ordered real vector space. The classical limit theorems are obtained, and an application is made to non-homogeneous Markov chains. Finally, groups of nonnegative matrices are discussed.     

Permanents of doubly stochastic matrices with fixed zero pattern

The doubly stochastic matrices with a given zero pattern which are closest in Euclidean norm to J_nn, the matrix with each entry equal to 1/n, are identified. If the permanent is restricted to matrices having a given zero pattern confined to one row or to one column, the permanent achieves a local minimum at those matrices with that zero pattern which are closest to J_nn. This need no longer be true if the zeros lie in more than one row or column.     

Some results on symplectic matrices

The principal results are that if A is an integral matrix such that AA^T is symplectic then A = CQ, where Q is a permutation matrix and C is symplectic; and that if A is a hermitian positive definite matrix which is symplectic, and B is the unique hermitian positive definite pth.root of A, where p is a positive integer, then B is also symplectic.     

Some results on symplectic matrices

The principal results are that if A is an integral matrix such that AA^T is symplectic then A = CQ, where Q is a permutation matrix and C is symplectic; and that if A is a hermitian positive definite matrix which is symplectic, and B is the unique hermitian positive definite pth.root of A, where p is a positive integer, then B is also symplectic.     

Eigenvector matrices of symmetric tridiagonals

Summary A simple test is given for determining whether a given matrix is the eigenvector matrix of an (unknown) unreduced symmetric tridiagonal matrix. A list of known necessary conditions is also provided. A lower bound on the separation between eigenvalues of tridiagonals follows from our Theorem 3.Dedicated to Professor F.L. Bauer on the occasion of his 60th birthdayThe first author gratefully acknowledges support from ONR Contract N00014-76-C-0013     

Comparisons of regular splittings of matrices

Summary In this article, new comparison theorems for regular splittings of matrices are derived. In so doing, the initial results of Varga in 1960 on regular splittings of matrices, and the subsequent unpublished results of Wonicki in 1973 on regular splittings of matrices, will be seen to be special cases of these new comparison theorems.Dedicated to Fritz Bauer on the occasion of his 60th birthdayResearch supported in part by the Air Force Office of Scientific Research, and by the Department of Energy     

Spectral methods with sparse matrices

Summary Spectral methods employ global polynomials for approximation. Hence they give very accurate approximations for smooth solutions. Unfortunately, for Dirichlet problems the matrices involved are dense and have condition numbers growing asO(N ⁴) for polynomials of degree N in each variable. We propose a new spectral method for the Helmholtz equation with a symmetric and sparse matrix whose condition number grows only asO(N ²). Certain algebraic spectral multigrid methods can be efficiently used for solving the resulting system. Numerical results are presented which show that we have probably found the most effective solver for spectral systems.     

QR factorization of Toeplitz matrices

Summary This paper presents a new algorithm for computing theQR factorization of anm×n Toeplitz matrix inO(mn) operations. The algorithm exploits the procedure for the rank-1 modification and the fact that both principal (m–1)×(n–1) submatrices of the Toeplitz matrix are identical. An efficient parallel implementation of the algorithm is possible.     

LU decompositions of generalized diagonally dominant matrices

Summary Using the simple vehicle ofM-matrices, the existence and stability ofLU decompositions of matricesA which can be scaled to diagonally dominant (possibly singular) matrices are investigated. Bounds on the growth factor for Gaussian elimination onA are derived. Motivation for this study is provided in part by applications to solving homogeneous systems of linear equationsAx=0, arising in Markov queuing networks, input-output models in economics and compartmental systems, whereA or –A is an irreducible, singularM-matrix.This paper extends earlier work by Funderlic and Plemmons and by Varga and Cai.Research sponsored by the Applied Mathematical Sciences Research Program, Office of Energy Research, U.S. Department of Energy under contract W-7405-eng-26 with the Union Carbide CorporationResearch supported in part by the National Science Foundation under Grant No. MCS 8102114Research supported in part by the U.S. Army Research Office under contract no. DAAG 29-81-k-0132     

On a new class of elementary matrices

Summary A new class of elementary matrices, a block-generalisation of plane rotations, is presented and the application in constructing quadratically convergent block diagonalisation algorithms of Jacobi type is discussed.     

Fast inversion algorithms of Toeplitz-plus-Hankel matrices

Summary The paper deals with the problems of fast inversion of matricesA=T+H, whereT is Toeplitz andH is Hankel. Several algorithms are presented and compared, among them algorithms working for arbitrary strongly nonsingular matricesA=T+H.     

Optimal cycles in doubly weighted graphs and approximation of bivariate functions by univariate ones

Summary The problem of finding optimal cycles in a doubly weighted directed graph (Problem A) is closely related to the problem of approximating bivariate functions by the sum of two univariate functions with respect to the supremum norm (Problem B). The close relationship between Problem A and Problem B is detected by the characterization (7.4) of the distance dist (f, t) of Problem B.In Part 1 we construct an algorithm for Problem A where the essential role is played by the minimal lengthsy _j(k) defined by (2.3). If weight functiont1 then the minimum of Problem A is computed by equality (2.4). Ift1 then the minimum is obtained by a binary search procedure, Algorithm 3.In Part 2 we construct our algorithms for solving Problem B by following exactly the ideas of Part 1. By Algorithm 4 we compute the minimal pseudolengthsh _k(y, M) defined by (7.5). If weight functiont1 then the infimum dist(f,t) of Problem B is obtained by equality (7.12) which is closely related to (2.4). Ift1 we compute the infimum dist(f,t) by the binary search procedure Algorithm 5.Additionally, Algorithm 4 leads to a constructive proof of the existence of continuous optimal solutions of Problem B (see Theorem 7.1e) which is already known in caset1 but unknown in caset1.Interesting applications to the steady-state behaviour of industrial processes with interference (Sect. 3) and the solution of integral equations (Problem C) are included.Supported by Deutsche Forschungsgemeinschaft Grant No. GO 270/3     

A note on optimal block-scaling of matrices

Summary After pointing out that two recent results on optimal blockscaling are equivalent, a new short and simple proof of both results is given.Dedicated to Prof. Dr. F.L. Bauer on the occasion of his 60th birthday     

Tchebychev acceleration technique for large scale nonsymmetric matrices

Summary The acceleration by Tchebychev iteration for solving nonsymmetric eigenvalue problems is dicussed. A simple algorithm is derived to obtain the optimal ellipse which passes through two eigenvalues in a complex plane relative to a reference complex eigenvalue. New criteria are established to identify the optimal ellipse of the eigenspectrum. The algorithm is fast, reliable and does not require a search for all possible ellipses which enclose the spectrum. The procedure is applicable to nonsymmetric linear systems as well.