Infinite triangular matrices, q-Pascal matrices, and determinantal representations

We use basic properties of infinite lower triangular matrices and the connections of Toeplitz matrices with generating-functions to obtain inversion formulas for several types of q-Pascal matrices, determinantal representations for polynomial sequences, and identities involving the q-Gaussian coefficients. We also obtain a fast inversion algorithm for general infinite lower triangular matrices.     

Accurate computations with Said-Ball-Vandermonde matrices

A generalization of the Vandermonde matrices which arise when the power basis is replaced by the Said-Ball basis is considered. When the nodes are inside the interval (0,1), then those matrices are strictly totally positive. An algorithm for computing the bidiagonal decomposition of those Said-Ball-Vandermonde matrices is presented, which allows us to use known algorithms for totally positive matrices represented by their bidiagonal decomposition. The algorithm is shown to be fast and to guarantee high relative accuracy. Some numerical experiments which illustrate the good behaviour of the algorithm are included.     

An inverse eigenvalue problem for periodic Jacobi matrices in Minkowski spaces

The spectral properties of periodic Jacobi matrices in Minkowski spaces are studied. An inverse problem for these matrices is investigated, and necessary and sufficient conditions under which the problem is solvable are presented. Uniqueness results are also discussed, and an algorithm to construct the solutions and illustrative examples is provided.     

Solving inverse eigenvalue problems via Householder and rank-one matrices

A brief and practical algorithm is introduced to solve symmetric inverse eigenvalue problems, which we call HROU algorithm. The algorithm is based on Householder transformations and rank one updating. We give some basic properties and the computational amount and develop sensitivity analysis of HROU algorithm. Furthermore, we develop HROU algorithm into a multi-level and adaptive one, named MLAHROU, to solve symmetric nonnegative inverse eigenvalue problems. New sufficient conditions to ensure symmetric nonnegative matrices and symmetric M-matrices are given. Many numerical examples are given to verify our theory, compare with existing results and show the efficiency of our algorithms.     

Normal forms in matrix spaces

For the groupGL(m, C)xGL(n, C) acting on the space ofmxn matrices over C, we introduce a class of subgroups which we call admissible. We suggest an algorithm to reduce an arbitrary matrix to a normal form with respect to an action of any admissible group. This algorithm covers various classification problems, including the wild problem of bringing a pair of matrices to normal form by simultaneous similarity. The classical left, right, two-sided and similarity transformations turns out to be admissible. However, the stabilizers of known normal forms (Smith's, Jordan's), generally speaking, are not admissible, and this obstructs inductive steps of our algorithm. This is the reason that we introduce modified normal forms for classical actions.Partially supported by Israel Science Foundation     

An algorithm for determining if the inverse of a strictly diagonally dominant Stieltjes matrix is strictly ultrametric

Summary It was recently shown that the inverse of a strictly ultrametric matrix is a strictly diagonally dominant Stieltjes matrix. On the other hand, as it is well-known that the inverse of a strictly diagonally dominant Stieltjes matrix is a real symmetric matrix with nonnegative entries, it is natural to ask, conversely, if every strictly diagonally dominant Stieltjes matrix has a strictly ultrametric inverse. Examples show, however, that the converse is not true in general, i.e., there are strictly diagonally dominant Stieltjes matrices in ^n×n (for everyn3) whose inverses are not strictly ultrametric matrices. Then, the question naturally arises if one can determine which strictly diagonally dominant Stieltjes matrices, in ^n×n (n3), have inverses which are strictly ultrametric. Here, we develop an algorithm, based on graph theory, which determines if a given strictly diagonally dominant Stieltjes matrixA has a strictly ultrametric inverse, where the algorithm is applied toA and requires no computation of inverse. Moreover, if this given strictly diagonally dominant Stieltjes matrix has a strictly ultrametric inverse, our algorithm uniquely determines this inverse as a special sum of rank-one matrices.Research supported by the National Science FoundationResearch supported by the Deutsche Forschungsgemeinschaft     

An algorithm for addressing the real interval eigenvalue problem

In this paper we present an algorithm for approximating the range of the real eigenvalues of interval matrices. Such matrices could be used to model real-life problems, where data sets suffer from bounded variations such as uncertainties (e.g. tolerances on parameters, measurement errors), or to study problems for given states.The algorithm that we propose is a subdivision algorithm that exploits sophisticated techniques from interval analysis. The quality of the computed approximation and the running time of the algorithm depend on a given input accuracy. We also present an efficient C++ implementation and illustrate its efficiency on various data sets. In most of the cases we manage to compute efficiently the exact boundary points (limited by floating point representation).     

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.     

Unitary matrix digraphs and minimum semidefinite rank

For an undirected simple graph G, the minimum rank among all positive semidefinite matrices with graph G is called the minimum semidefinite rank (msr) of G. In this paper, we show that the msr of a given graph may be determined from the msr of a related bipartite graph. Finding the msr of a given bipartite graph is then shown to be equivalent to determining which digraphs encode the zero/nonzero pattern of a unitary matrix. We provide an algorithm to construct unitary matrices with a certain pattern, and use previous results to give a lower bound for the msr of certain bipartite graphs.     

Characterizations of inverse M-matrices with special zero patterns

In this paper, we provide some characterizations of inverse M-matrices with special zero patterns. In particular, we give necessary and sufficient conditions for k-diagonal matrices and symmetric k-diagonal matrices to be inverse M-matrices. In addition, results for triadic matrices, tridiagonal matrices and symmetric 5-diagonal matrices are presented as corollaries.     

Principal minors, Part II: The principal minor assignment problem

The inverse problem of finding a matrix with prescribed principal minors is considered. A condition that implies a constructive algorithm for solving this problem will always succeed is presented. The algorithm is based on reconstructing matrices from their principal submatrices and Schur complements in a recursive manner. Consequences regarding the overdeterminancy of this inverse problem are examined, leading to a faster (polynomial time) version of the algorithmic construction. Care is given in the MATLAB^® implementation of the algorithms regarding numerical stability and accuracy.     

The centro-invertible matrix: A new type of matrix arising in pseudo-random number generation

This paper defines a new type of matrix (which will be called a centro-invertible matrix) with the property that the inverse can be found by simply rotating all the elements of the matrix through 180 degrees about the mid-point of the matrix. Centro-invertible matrices have been demonstrated in a previous paper to arise in the analysis of a particular algorithm used for the generation of uniformly-distributed pseudo-random numbers.An involutory matrix is one for which the square of the matrix is equal to the identity. It is shown that there is a one-to-one correspondence between the centro-invertible matrices and the involutory matrices. When working in modular arithmetic this result allows all possible k by k centro-invertible matrices with integer entries modulo M to be enumerated by drawing on existing theoretical results for involutory matrices.Consider the k by k matrices over the integers modulo M. If M takes any specified finite integer value greater than or equal to two then there are only a finite number of such matrices and it is valid to consider the likelihood of such a matrix arising by chance. It is possible to derive both exact expressions and order-of-magnitude estimates for the number of k by k centro-invertible matrices that exist over the integers modulo M. It is shown that order (√N) of the N=M^(k2) different k by k matrices modulo M are centro-invertible, so that the proportion of these matrices that are centro-invertible is order (1/√N).     

Even and odd diagonals in doubly stochastic matrices

The existence of even or odd diagonals in doubly stochastic matrices depends on the number of positive elements in the matrix. The optimal general lower bound in order to guarantee the existence of such diagonals is determined, as well as their minimal number for given number of positive elements. The results are related to the characterization of even doubly stochastic matrices in connection with Birkhoff's algorithm.     

Detecting hyperbolic and definite matrix polynomials

Hyperbolic or more generally definite matrix polynomials are important classes of Hermitian matrix polynomials. They allow for a definite linearization and can therefore be solved by a standard algorithm for Hermitian matrices. They have only real eigenvalues which can be characterized as minmax and maxmin values of Rayleigh functionals, but there is no easy way to test if a given polynomial is hyperbolic or definite or not. Taking advantage of the safeguarded iteration which converges globally and monotonically to extreme eigenvalues we obtain an efficient algorithm that identifies hyperbolic or definite polynomials and enables the transformation to an equivalent definite linear pencil. Numerical examples demonstrate the efficiency of the approach.     

Canonical forms for normal matrices that commute with their complex conjugate

We consider the class of normal complex matrices that commute with their complex conjugate. We show that such matrices are real orthogonally similar to a canonical direct sum of 1-by-1 and certain 2-by-2 matrices. A canonical form for quasi-real normal matrices is obtained as a special case. We also exhibit a special form of the spectral theorem for normal matrices that commute with their conjugate.     

Construction and nonnegativity of sign idempotent sign pattern matrices

In this paper, we modify Eschenbach’s algorithm for constructing sign idempotent sign pattern matrices so that it correctly constructs all of them. We find distinct classes of sign idempotent sign pattern matrices that are signature similar to an entrywise nonnegative sign pattern matrix. Additionally, if for a sign idempotent sign pattern matrix A there exists a signature matrix S such that SAS is nonnegative, we prove such S is unique up to multiplication by -1 if the signed digraph D(A) is not disconnected.     

Geršgorin type theorems for quaternionic matrices

This paper aims to set an account of the left eigenvalue problems for real quaternionic (finite) matrices. In particular, we will present the Geršgorin type theorems for the left (and right) eigenvalues of square quaternionic matrices. We shall conclude the paper with examples showing and summarizing some differences between complex matrices and quaternionic matrices and right and left eigenvalues of quaternionic matrices.     

Dominant matrices and max algebra

We study the class of so-called totally dominant matrices in the usual algebra and in the max algebra in which the sum is the maximum and the multiplication is usual. It turns out that this class coincides with the well known class of positive matrices having positive the determinants of all 2×2 submatrices. The closure of this class is closed not only with respect to the usual but also with respect to the max multiplication. Further properties analogous to those of totally positive matrices are proved and some connections to Monge matrices are mentioned.