The group-theoretic complexity of subsemigroups of boolean matrices

We find the group-theoretic complexity of many subsemigroups of the semigroup B_n of n × n Boolean matrices, including Hall matrices, reflexive matrices, fully indecomposable matrices, upper triangular matrices, row-rank-n matrices, and others.     

The class of m-EP and m-normal matrices

The well-known classes of EP matrices and normal matrices are defined by the matrices that commute with their Moore–Penrose inverse and with their conjugate transpose, respectively. This paper investigates the class of m-EP matrices and m-normal matrices that provide a generalization of EP matrices and normal matrices, respectively, and analyses both of them for their properties and characterizations.     

A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

REPRINT OF: A quasiseparable approach to five-diagonal CMV and Fiedler matrices

Recent work in the characterization of structured matrices in terms of characteristic polynomials of principal submatrices is furthered in this paper. Some classical classes of matrices with quasiseparable structure include tridiagonal (related to real orthogonal polynomials) and banded matrices, unitary Hessenberg matrices (related to Szegö polynomials), and semiseparable matrices, as well as others. Hence working with the class of quasiseparable matrices provides new results which generalize and unify classical results.Previous work has focused on characterizing (H,1)-quasiseparable matrices, matrices with order-one quasiseparable structure that are also upper Hessenberg. In this paper, the authors introduce the concept of a twist transformation, and use such transformations to explain the relationship between (H,1)-quasiseparable matrices and the subclass of (1,1)-quasiseparable matrices (without the upper Hessenberg restriction) which are related to the same systems of polynomials. These results generalize the discoveries of Cantero, Fiedler, Kimura, Moral and Velázquez of five-diagonal matrices related to Horner and Szegö polynomials in the context of quasiseparable matrices.     

On the finiteness property for rational matrices

We analyze the periodicity of optimal long products of matrices. A set of matrices is said to have the finiteness property if the maximal rate of growth of long products of matrices taken from the set can be obtained by a periodic product. It was conjectured a decade ago that all finite sets of real matrices have the finiteness property. This “finiteness conjecture” is now known to be false but no explicit counterexample is available and in particular it is unclear if a counterexample is possible whose matrices have rational or binary entries. In this paper, we prove that all finite sets of nonnegative rational matrices have the finiteness property if and only if pairs of binary matrices do and we state a similar result when negative entries are allowed. We also show that all pairs of 2×2 binary matrices have the finiteness property. These results have direct implications for the stability problem for sets of matrices. Stability is algorithmically decidable for sets of matrices that have the finiteness property and so it follows from our results that if all pairs of binary matrices have the finiteness property then stability is decidable for nonnegative rational matrices. This would be in sharp contrast with the fact that the related problem of boundedness is known to be undecidable for sets of nonnegative rational matrices.     

A geometric treatment of generalized inverses and semigroups of nonnegative matrices

The purpose of this paper is to provide a unified treatment from the geometric viewpoint of the following closely related aspects of nonnegative matrices: nonnegative matrices with nonnegative generalized inverses of various kinds; nonnegative rank factorization; regular elements, Green's relations, and maximal subgroups of the semigroups of nonnegative matrices, stochastic matrices, column stochastic matrices, and doubly stochastic matrices.     

Inversion of polynomial and rational matrices

The inversion of polynomial and rational matrices is considered. For regular matrices, three algorithms for computing the inverse matrix in a factored form are proposed. For singular matrices, algorithms of constructing pseudoinverse matrices are considered. The algorithms of inversion of rational matrices are based on the minimal factorization which reduces the problem to the inversion of polynomial matrices. A class of special polynomial matrices is regarded whose inverse matrices are also polynomial matrices. Inversion algorithms are applied to the solution of systems with polynomial and rational matrices. Bibliography: 3 titles. Translated by V. N. Kublanovskaya. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 202, 1992, pp. 97–109.     

Pascal矩阵的一种显式分解

本文引入了两种广义Pascal矩阵凡,P_n,k,Q_n,k以及两种广义Pascal函数矩阵O_n,k[x,y],Q_n,k[x,y],证明了Pascal矩阵能够表示成(0,1)-Jordan矩阵的乘积而且Pascal函数矩阵能分解成双对角矩阵的乘积.     

On some properties of circulant matrices

A class Σ of matrices is studied which contains, as special subclasses, p-circulant matrices (p ? 1), Toeplitz symmetric matrices and the inverses of some special tridiagonal matrices. We give a necessary and sufficient condition in order that matrices of Σ commute with each other and are closed with respect to matrix product.     

Generalized Hankel matrices of Markov parameters and their applications to control problems

The concept of Hankel matrices of Markov parameters associated with two polynomials is generalized for matrices. The generalized Hankel matrices of Markov parameters are then used to develop methods for testing the relative primeness of two matrices A and B, for determining stability and inertia of a matrix, and for constructing a class of matrices C such that A + C has a desired spectrum. Neither the method of construction of the generalized Hankel matrices nor the methods developed using these matrices require explicit computation of the characteristic polynomial of A (or of B).     

Monotone positive stable matrices

The class of real matrices which are both monotone (inverse positive) and positive stable is investigated. Such matrices, called N-matrices, have the well-known class of nonsingular M-matrices as a proper subset. Relationships between the classes of N-matrices, M-matrices, nonsingular totally nonnegative matrices, and oscillatory matrices are developed. Conditions are given for some classes of matrices, including tridiagonal and some Toeplitz matrices, to be N-matrices.     

On orthostochastic, unistochastic and qustochastic matrices

We introduce qustochastic matrices as the bistochastic matrices arising from quaternionic unitary matrices by replacing each entry with the square of its norm. This is the quaternionic analogue of the unistochastic matrices studied by physicists. We also introduce quaternionic Hadamard matrices and quaternionic mutually unbiased bases (MUB). In particular we show that the number of MUB in an n-dimensional quaternionic Hilbert space is at most 2n+1. The bound is attained for n=2. We also determine all quaternionic Hadamard matrices of size n?4.     

An Implicit Q Theorem for Hessenberg-like Matrices

The implicit Q theorem for Hessenberg matrices is a widespread and powerful theorem. It is used in the development of, for example, implicit QR algorithms to compute the eigendecomposition of Hessenberg matrices. Moreover it can also be used to prove the essential uniqueness of orthogonal similarity transformations of matrices to Hessenberg form. The theorem is also valid for symmetric tridiagonal matrices, proving thereby also in the symmetric case its power. Currently there is a growing interest to so-called semiseparable matrices. These matrices can be considered as the inverses of tridiagonal matrices. In a similar way, one can consider Hessenberg-like matrices as the inverses of Hessenberg matrices. In this paper, we formulate and prove an implicit Q theorem for the class of Hessenberg-like matrices. We introduce the notion of strongly unreduced Hessenberg-like matrices and also a method for transforming matrices via orthogonal transformations to this form is proposed. Moreover, as the theorem is valid for Hessenberg-like matrices it is also valid for symmetric semiseparable matrices. The research was partially supported by the Research Council K.U.Leuven, project OT/00/16 (SLAP: Structured Linear Algebra Package), by the Fund for Scientific Research–Flanders (Belgium), projects G.0078.01 (SMA: Structured Matrices and their Applications), G.0176.02 (ANCILA: Asymptotic aNalysis of the Convergence behavior of Iterative methods in numerical Linear Algebra), G.0184.02 (CORFU: Constructive study of Orthogonal Functions) and G.0455.0 (RHPH: Riemann-Hilbert problems, random matrices and Padé-Hermite approximation), and by the Belgian Programme on Interuniversity Poles of Attraction, initiated by the Belgian State, Prime Minister’s Office for Science, Technology and Culture, project IUAP V-22 (Dynamical Systems and Control: Computation, Identification & Modelling). This research was partially supported by by MIUR, grant number 2004015437 (third author). The scientific responsibility rests with the authors.     

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.     

Term-rank,permanent, and rook-polynomial preservers

Characterizations are obtained of those linear operators on the m × n matrices over an arbitrary semiring that preserve term rank. We also present characterizations of permanent and rook-polynomial preserving operators on matrices over certain types of semirings. Our results apply to many combinatorially interesting algebraic systems, including nonnegative integer matrices, matrices over Boolean algebras, and fuzzy matrices.     

The least-squares method for matrices dependent on parameters

Some algorithms are suggested for constructing pseudoinverse matrices and for solving systems with rectangular matrices whose entries depend on a parameter in polynomial and rational ways. The cases of one- and two-parameter matrices are considered. The construction of pseudoinverse matrices are realized on the basis of rank factorization algorithms. In the case of matrices with polynomial occurrence of parameters, these algorithms are the ΔW-1 and ΔW-2 algorithms for one- and two-parameter matrices, respectively. In the case of matrices with rational occurrence of parameters, these algorithms are the irreducible factorization algorithms. This paper is a continuation of the author's studies of the solution of systems with one-parameter matrices and an extension of the results to the case of two-parameter matrices with polynomial and rational entries. Bibliography: 12 titles. Translated fromZapiski Nauchnykh Seminarov POMI, Vol. 219, 1994, pp. 176–185. This work was supported by the Russian Foundation of Fundamental Research (grant 94-01-00919). Translated by V. N. Kublanovskaya.     

k-广义Hermite矩阵

本文给出了k-广义(反)Hermite矩阵的概念,研究了它的性质及其与k-广义酉矩阵之间的联系,推广了酉矩阵和(反)Hermite矩阵的相应结果.     

The point spectra for certain classes of operators in B(ℓ p )

In a recent paper [5] Maddox determined the point spectrum of the Cesaro matrices of order >0, considered as series-to-series operators. In this paper we obtain the point spectrum for the Endl generalized Hausdorff matrices, the Hausdorff matrices, and for a wide class of generalized Hausdorff matrices, which include the Endl and ordinary Hausdorff matrices as special cases. We also obtain point spectrum results for a wide class of weighted mean matrices. Since the Cesaro matrices are examples of Hausdorff matrices, our results contain the corresponding theorems of Maddox as special cases.     

Complement total unimodularity

A {0, 1} matrix U is defined to be complement totally unimodular (c.t.u.) if U as well as all matrices derived from U by certain complement operations are totally unimodular. Two decompositions of minimal violation matrices of total unimodularity are utilized to characterize the letter matrices by c.t.u. matrices. In addition properties of c.t.u. matrices are presented.     

Orbit matrices of Hadamard matrices and related codes

In this paper we introduce the notion of orbit matrices of Hadamard matrices with respect to their permutation automorphism groups and show that under certain conditions these orbit matrices yield self-orthogonal codes. As a case study, we construct codes from orbit matrices of some Paley type I and Paley type II Hadamard matrices. In addition, we construct four new symmetric (100,45,20) designs which correspond to regular Hadamard matrices, and construct codes from their orbit matrices. The codes constructed include optimal, near-optimal self-orthogonal and self-dual codes, over finite fields and over ${\mathbb{Z}}_4$.