Permanent Semigroups

A permanent semigroup is a semigroup of n × n matrices on which the permanent function is multiplicative. If the underlying ring is an infinite integral domain with characteristic p > n or characteristic 0 we prove that any permanent semigroup consists of matrices with at most one nonzero diagonal. The same result holds if the ring is a finite field with characteristic p > n and at least n²+n elements. We also consider the Kronecker product of permanent semigroups and show that the Kronecker product of permanent semigroups is a permanent semigroup if and only if the pennanental analogue of the formula for the determinant of a Kronecker product of two matrices holds. This latter result holds even when the matrix entries are from a commutative ring with unity.     

Rational realization of the minimum ranks of nonnegative sign pattern matrices

A sign pattern matrix (or nonnegative sign pattern matrix) is a matrix whose entries are from the set {+,?, 0} ({+, 0}, respectively). The minimum rank (or rational minimum rank) of a sign pattern matrix A is the minimum of the ranks of the matrices (rational matrices, respectively) whose entries have signs equal to the corresponding entries of A. Using a correspondence between sign patterns with minimum rank r ≥ 2 and point-hyperplane configurations in R^r?1 and Steinitz’s theorem on the rational realizability of 3-polytopes, it is shown that for every nonnegative sign pattern of minimum rank at most 4, the minimum rank and the rational minimum rank are equal. But there are nonnegative sign patterns with minimum rank 5 whose rational minimum rank is greater than 5. It is established that every d-polytope determines a nonnegative sign pattern with minimum rank d + 1 that has a (d + 1) × (d + 1) triangular submatrix with all diagonal entries positive. It is also shown that there are at most min{3m, 3n} zero entries in any condensed nonnegative m × n sign pattern of minimum rank 3. Some bounds on the entries of some integer matrices achieving the minimum ranks of nonnegative sign patterns with minimum rank 3 or 4 are established.     

Hermitian positive semidefinite matrices whose entries are 0 or 1 in Modulus

We show that a matrix is a Hermitian positive semidefinite matrix whose nonzero entries have modulus 1 if and only if it is similar to a direct sum of all I's matrices and a 0 matrix via a unitary monomial similarity. In particular, the only such nonsingular matrix is the identity matrix and the only such irreducible matrix is similar to an all l's matrix by means of a unitary diagonal similarity. Our results extend earlier results of Jain and Snyder for the case in which the nonzero entries (actually) equal 1. Our methods of proof, which reiy on the so called principal submatrix rank property, differ from the approach used by Jain and Snyder.     

Convergence Properties of Dikin’s Affine Scaling Algorithm for Nonconvex Quadratic Minimization

We study convergence properties of Dikins affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported.     

The elementary divisor theory over the Hurwitz order of integral quaternions

There exists a diagonal form with certain divisibility conditions for matrices over the Hurwitz order of integral quaternions under unimodular equivalence. The diagonal entries are uniquely determined up to similarity. Given two such diagonal forms, where the diagonal entries are similar by pairs, the matrices prove to be ummodularly equivalent, whenever the rank of the matrices is creater than one.     

Zero-Term Ranks of Real Matrices and Their Preservers

Zero-term rank of a matrix is the minimum number of lines (rows or columns) needed to cover all the zero entries of the given matrix. We characterize the linear operators that preserve zero-term rank of the m× nreal matrices. We also obtain combinatorial equivalent condition for the zero-term rank of a real matrix.     

On the eigenvalues of double band matrices

We consider matrices containing two diagonal bands of positive entries. We show that all eigenvalues of such matrices are of the form rζ, where r is a nonnegative real number and ζ is a pth root of unity, where p is the period of the matrix, which is computed from the distance between the bands. We also present a problem in the asymptotics of spectra in which such double band matrices are perturbed by banded matrices.     

Computing singular values of diagonally dominant matrices to high relative accuracy

For a (row) diagonally dominant matrix, if all of its off-diagonal entries and its diagonally dominant parts (which are defined for each row as the absolute value of the diagonal entry subtracted by the sum of the absolute values of off-diagonal entries in that row) are accurately known, we develop an algorithm that computes all the singular values, including zero ones if any, with relative errors in the order of the machine precision. When the matrix is also symmetric with positive diagonals (i.e. a symmetric positive semi-definite diagonally dominant matrix), our algorithm computes all eigenvalues to high relative accuracy. Rounding error analysis will be given and numerical examples will be presented to demonstrate the high relative accuracy of the algorithm.

     

Multiplicative properties of generalized matrix functions

We consider scalar-valued matrix functions for n×n matrices A=(a_ij) defined by Where G is a subgroup of S_n the group of permutations on n letters, and χ is a linear character of G. Two such functions are the permanent and the determinant. A function (1) is multiplicative on a semigroup S of n×n matrices if d(AB)=d(A)d(B) AB∈S.

With mild restrictions on the underlying scalar ring we show that every element of a semigroup containing the diagonal matrices on which (1) is multiplicative can have at most one nonzero diagonal(i.e., diagonal with all nonzero entries)and conversely, provided that χ is the principal character(χ≡1).     

INERTIA SETS OF SYMMETRIC SIGN PATTERN MATRICES

1　IntroductionIn qualitative and combinatorial matrix theory,we study properties ofa matrix basedon combinatorial information,such as the signs of entries in the matrix.A matrix whoseentries are from the set{ + ,-,0 } is called a sign pattern matrix ( or sign pattern,or pat-tern) .We denote the setof all n× n sign pattern matrices by Qn.For a real matrix B,sgn( B) is the sign pattern matrix obtained by replacing each positive( respectively,negative,zero) entry of B by+ ( respectively,-,0 )…     

Cycles of Nonzero Elements in Low Rank Matrices

Dedicated to the memory of Paul Erdős We consider the problem of finding some structure in the zero-nonzero pattern of a low rank matrix. This problem has strong motivation from theoretical computer science. Firstly, the well-known problem on rigidity of matrices, proposed by Valiant as a means to prove lower bounds on some algebraic circuits, is of this type. Secondly, several problems in communication complexity are also of this type. The special case of this problem, where one considers positive semidefinite matrices, is equivalent to the question of arrangements of vectors in euclidean space so that some condition on orthogonality holds. The latter question has been considered by several authors in combinatorics [1, 4]. Furthermore, we can think of this problem as a kind of Ramsey problem, where we study the tradeoff between the rank of the adjacency matrix and, say, the size of a largest complete subgraph. In this paper we show that for an real matrix with nonzero elements on the main diagonal, if the rank is o(n), the graph of the nonzero elements of the matrix contains certain cycles. We get more information for positive semidefinite matrices. Received September 9, 1999 RID="*" ID="*" Partially supported by grant A1019901 of the Academy of Sciences of the Czech Republic and by a cooperative research grant INT-9600919/ME-103 from the NSF (USA) and the MŠMT (Czech Republic).     

Semigroup of matrices acting on the max-plus projective space

We investigate the action of semigroups of d×d matrices with entries in the max-plus semifield on the max-plus projective space. Recall that semigroups generated by one element with projectively bounded image are projectively finite and thus contain idempotent elements.In terms of orbits, our main result states that the image of a minimal orbit by an idempotent element of the semigroup with minimal rank has at most d! elements. Moreover, each idempotent element with minimal rank maps at least one orbit onto a singleton.This allows us to deduce the central limit theorem for stochastic recurrent sequences driven by independent random matrices that take countably many values, as soon as the semigroup generated by the values contains an element with projectively bounded image.     

Convergence Properties of Dikin’s Affine Scaling Algorithm for Nonconvex Quadratic Minimization

We study convergence properties of Dikin’s affine scaling algorithm applied to nonconvex quadratic minimization. First, we show that the objective function value either diverges or converges Q-linearly to a limit. Using this result, we show that, in the case of box constraints, the iterates converge to a unique point satisfying first-order and weak second-order optimality conditions, assuming the objective function Hessian Q is rank dominant with respect to the principal submatrices that are maximally positive semidefinite. Such Q include matrices that are positive semidefinite or negative semidefinite or nondegenerate or have negative diagonals. Preliminary numerical experience is reported.     

Continued fractions associated with the Newton-Padé table

Summary We discuss first the block structure of the Newton-Padé table (or, rational interpolation table) corresponding to the double sequence of rational interpolants for the data{(z _k, h(z_k)} _k =0. (The (m, n)-entry of this table is the rational function of type (m,n) solving the linearized rational interpolation problem on the firstm+n+1 data.) We then construct continued fractions that are associated with either a diagonal or two adjacent diagonals of this Newton-Padé table in such a way that the convergents of the continued fractions are equal to the distinct entries on this diagonal or this pair of diagonals, respectively. The resulting continued fractions are generalizations of Thiele fractions and of Magnus'sP-fractions. A discussion of an some new results on related algorithms of Werner and Graves-Morris and Hopkins are also given.Dedicated to the memory of Helmut Werner (1931–1985)     

Linear preservers of minimal rank

It is proved that a linear transformation on the vector space of upper triangular matrices that maps the set of matrices of minimal rank 1 into itself, and either has the analogous property with respect to matrices of full minimal rank, or is bijective, is a triangular equivalence, or a flip about the south-west north-east diagonal followed by a triangular equivalence. The result can be regarded as an analogue of Marcus–Moyls theorem in the context of triangular matrices.     

An extension of a theorem of Kaplansky

A theorem of Kaplansky asserts that a semigroup of matrices with entries from a field whose members all have singleton spectra is triangularizable. Indeed, Kaplansky’s Theorem unifies well-known theorems of Kolchin and Levitzki on simultaneous triangularizability of semigroups of unipotent and nilpotent matrices, respectively. First, for a division ring D of characteristic zero whose center intersects its multiplicative commutator group in a finite group, we prove that the counterpart of Kolchin’s Theorem over D implies that of Kaplansky’s Theorem over D. Next, we note that this proof, when adjusted in the setting of fields, provides a new and simple proof of Kaplansky’s Theorem over fields of characteristic zero. We show that if Kaplansky’s Theorem holds over a division ring D, which is for instance the case over general fields, then a generalization of Kaplansky’s Theorem holds over D, and in particular over general fields.     

Semigroups generated by a group and an idempotent

It is well known that the semigroup of all transformations on a finite set X of order n is generated by its group of units, the symmetric group, and any idempotent of rank n ? 1. Similarly, the symmetric inverse semigroup on X is generated by its group of units and any idempotent of rank n ? 1 while the analogous result is true for the semigroup of all n × n matrices over a field.

In this paper we begin a systematic study of the structure of a semigroup S generated by its group G of units and an idempotent ? . The first section consists of preliminaries while the second contains some general results which provide the setting for those which follow.

In the third section we shall investigate the situation where G is a permutation group on a set X of order n and ? is an idempotent of rank n ? 1. In particular, we shall show that any such semigroup S is regular. Furthermore we shall determine when S is an inverse or orthodox semigroup or completely regular semigroup.

The fourth section deals with a special case, that in which G is cyclic. The fifth, and last, deals with the situation where G is dihedral. In both cases, the resulting semigroup has a particularly delicate structure which is of interest in its own right. Both situations are replete with interesting combinatorial gems.

The author was led to the results of this paper by considering the output of a computer program he was writing for generating and analyzing semigroups.     

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.     

A minimal completion of (0, 1)-matrices without total support

In this paper, we provide a method to complete a (0, 1)-matrix without total support via the minimal doubly stochastic completion of doubly substochastic matrices and show that the size of the completion is determined by the maximum diagonal sum or the term rank of the given (0, 1)-matrix.     

Analysis of incomplete factorizations for a nine-point approximation to a convection–diffusion model problem

We study the stability of zero-fill incomplete LU factorizations of a nine-point coefficient matrix arising from a high-order compact discretisation of a two-dimensional constant-coefficient convection–diffusion problem. Nonlinear recurrences for computing entries of the lower and upper triangular matrices are derived and we show that the sequence of diagonal entries of the lower triangular factor is unconditionally convergent. A theoretical estimate of the limiting value is derived and we show that this estimate is a good predictor of the computed value. The unconditional convergence of the diagonal sequence of the lower triangular factor to a positive limit implies that the incomplete factorization process never encounters a zero pivot and that the other diagonal sequences are also convergent. The characteristic polynomials associated with the lower and upper triangular solves that occur during the preconditioning step are studied and conditions for the stability of the triangular solves are derived in terms of the entries of the tridiagonal matrices appearing in the lower and upper subdiagonals of the block triangular system matrix and a triplet of parameters which completely determines the solution of the nonlinear recursions. Results of ILU-preconditioned GMRES iterations and the effects of orderings on their convergence are also described.