Number theory of matrix semigroups

Unlike factorization theory of commutative semigroups which are well-studied, very little literature exists describing factorization properties in noncommutative semigroups. Perhaps the most ubiquitous noncommutative semigroups are semigroups of square matrices and this article investigates the factorization properties within certain subsemigroups of M_n(Z), the semigroup of n×n matrices with integer entries. Certain important invariants are calculated to give a sense of how unique or non-unique factorization is in each of these semigroups.     

The Perron-Frobenius Theorem Revisited

An extension of the Perron-Frobenius Theorem is presented in the much more general setting of indecomposable semigroups of nonnegative matrices. Many features of the original theorem including the existence of a fixed positive vector, a block-monomial form, and spectral stability properties hold simultaneously for these semigroups. The paper is largely self-contained and the proofs are elementary. The classical theorem and some related results follow as corollaries.     

Binary positive semidefinite matrices and associated integer polytopes

We consider the positive semidefinite (psd) matrices with binary entries, along with the corresponding integer polytopes. We begin by establishing some basic properties of these matrices and polytopes. Then, we show that several families of integer polytopes in the literature—the cut, boolean quadric, multicut and clique partitioning polytopes—are faces of binary psd polytopes. Finally, we present some implications of these polyhedral relationships. In particular, we answer an open question in the literature on the max-cut problem, by showing that the rounded psd inequalities define a polytope.     

Row reduced matrices and annihilator semigroups 1

Throughout we are discussing matrices with entries from a field K. It was first proved in [1] that a product of row reduced matrices is row reduced. This means that the set of row reduced matrices in any matrix ring form a semigroup. It is also the case that every matrix A ? M_n(K)has the property that it has the same right annihilator as its row reduced form, and distinct row reduced matrice have distinct right annihilators. Let R be a ring. Motivated by these observations, we call a multiplicative semigroup S in R a right annihilator semigroup for R if every element in R has the same right annihilator as exactly one element in S. Reasoning that row reduced matrices are very important we study semigroups that share their formal properties. Ultimately we would like to know all right annihilator semigroups in M_n(K).This seems to be a formidable task. Here we determine all right annihila-tor semigroups in M₃(K) up to a change of basis, that is conjugation.     

Recognizing Helly Edge-Path-Tree graphs and their clique graphs

We present a unifying procedure for recognizing intersection graphs of Helly families of paths in a tree and their clique graphs. The Helly property makes it possible to look at these recognition problems as variants of the Graph Realization Problem, namely, the problem of recognizing Edge-Path-Tree matrices. Our result heavily relies on the notion of pie introduced in [M.C. Golumbic, R.E. Jamison, The edge intersection graphs of paths in a tree, Journal of Combinatorial Theory, Series B 38 (1985) 8-22] and on the observation that Helly Edge-Path-Tree matrices form a self-dual class of Helly matrices. Coupled to the notion of reduction presented in the paper, these facts are also exploited to reprove and slightly refine some known results for Edge-Path-Tree graphs.     

正互反矩阵一致性的一个充要条件

<正> 层次分析法是一种实用的多维决策方法。在这种分析法中将一个复杂的无结构问题按照属性的不同把它的元素分成若干组,形成互不相交的层次,上一层次的元素对相邻的下一层次     

Positive one-parameter semigroups on ordered banach spaces

In this review we describe the basic structure of positive continuous one-parameter semigroups acting on ordered Banach spaces. The review is in two parts.First we discuss the general structure of ordered Banach spaces and their ordered duals. We examine normality and generation properties of the cones of positive elements with particular emphasis on monotone properties of the norm. The special cases of Banach lattices, order-unit spaces, and base-norm spaces, are also examined.Second we develop the theory of positive strongly continuous semigroups on ordered Banach spaces, and positive weak^*-continuous semigroups on the dual spaces. Initially we derive analogues of the Feller-Miyadera-Phillips and Hille-Yosida theorems on generation of positive semigroups. Subsequently we analyse strict positivity, irreducibility, and spectral properties, in parallel with the Perron-Frobenius theory of positive matrices.     

Free orthodox semigroups and free bands with inverse transversals

It is well known that the subclass of inverse semigroups and the subclass of completely regular semigroups of the class of regular semigroups form the so called e-varieties of semigroups. However, the class of regular semigroups with inverse transversals does not belong to this variety. We now call this class of semigroups the ist-variety of semigroups, and denote it by IST. In this paper, we consider the class of orthodox semigroups with inverse transversals, which is a special ist-variety and is denoted by OIST. Some previous results given by Tang and Wang on this topic are extended. In particular, the structure of free bands with inverse transversals is investigated. Results of McAlister, McFadden, Blyth and Saito on semigroups with inverse transversals are hence generalized and enriched.     

A small note on the scaling of symmetric positive definite semiseparable matrices

In this paper we will adapt a known method for diagonal scaling of symmetric positive definite tridiagonal matrices towards the semiseparable case. Based on the fact that a symmetric, positive definite tridiagonal matrix satisfies property A, one can easily construct a diagonal matrix such that has the lowest condition number over all matrices , for any choice of diagonal matrix . Knowing that semiseparable matrices are the inverses of tridiagonal matrices, one can derive similar properties for semiseparable matrices. Here, we will construct the optimal diagonal scaling of a semiseparable matrix, based on a new inversion formula for semiseparable matrices. Some numerical experiments are performed. In a first experiment we compare the condition numbers of the semiseparable matrices before and after the scaling. In a second numerical experiment we compare the scalability of matrices coming from the reduction to semiseparable form and matrices coming from the reduction to tridiagonal form. *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). The scientific responsibility rests with the authors. The second author participates in the SCCM program, Gates 2B, Stanford University, CA, USA and is also partially supported by the NSF. The first author visited the second one with a grant by the Fund for Scientific Research–Flanders (Belgium).     

Property of right units of complete semigroups of binary relations defined by finite XI-semilattices of unions

We study properties of right units of complete semigroups of binary relations defined by finite XI-semilattices of unions.     

A short proof of the Arendt-Chernoff-Kato theorem

We give a short new proof of the Arendt-Chernoff-Kato theorem, which characterizes generators of positive C ₀ semigroups in order unit spaces. The proof avoids half-norms and subdifferentials and is based on a sufficient condition for an operator to have positive inverse, which is new even for matrices.     

交换矩阵半群的可约性

首先分别给出单生矩阵半群或者摹群不可约、不可分解以及完全可约的充分必要条件,其次讨论一般域上矩阵半群的可约性的一些条件,最后特别地讨论实数域上矩阵半群的可约性,完全确定了实数域上对称和反对称矩阵组成的不可约交换矩阵半群.     

Cone-transitive matrix semigroups

Semigroups of matrices (over an ordered field) with non-negative entries are considered. A complete characterization is obtained for the semigroups which are minimal transitive on the positive (or non-negative) cone of the underlying vector space. Consequently, an explicit form for the semigroups sharply transitive on the cone is derived.     

Cone-transitive matrix semigroups

Semigroups of matrices (over an ordered field) with non-negative entries are considered. A complete characterization is obtained for the semigroups which are minimal transitive on the positive (or non-negative) cone of the underlying vector space. Consequently, an explicit form for the semigroups sharply transitive on the cone is derived.     

Multidimensional matrices uniquely recovered by their lines

We provide a method to determine if a q-ary multidimensional matrix is lonesum or not by using properties of line sums of lonesum multidimensional matrices. In particular, we establish a graphic method that uses edge-colored graphs to determine if a binary multidimensional matrix is lonesum or not. We also provide two methods to determine if a q-ary multidimensional matrix is lonestructure or not. The first one uses properties of line structures of lonestructure multidimensional matrices and the second one uses edge-colored directed multigraphs.     

矩阵逆半群

讨论矩阵逆半群的一些基本性质, 证明矩阵逆半群的幂等元集是有限布尔格的子半格, 从而证明等秩矩阵逆半群是群, 然后完全确定二级矩阵逆半群的结构：一个二级矩阵逆半群或者同构于二级线性群,或者同构于二级线性群添加一个零元素,或者是交换线性群的有限半格, 或者满足其他一些性质; 对于由某些二级矩阵构成的集合, 我们给出了它们成为矩阵逆半群的充分必要条件.     

A class of semigroups regularized in space and time

We consider α-times integrated C-regularized semigroups, which are a hybrid between semigroups regularized in space (C-semigroups) and integrated semigroups regularized in time. We study the basic properties of these objects, also in absence of exponential boundedness. We discuss their generators and establish an equivalence theorem between existence of integrated regularized semigroups and well-posedness of certain Cauchy problems. We investigate the effect of smoothing regularized semigroups by fractional integration.     

On tridiagonal matrices unitarily equivalent to normal matrices

In this article the unitary equivalence transformation of normal matrices to tridiagonal form is studied.It is well-known that any matrix is unitarily equivalent to a tridiagonal matrix. In case of a normal matrix the resulting tridiagonal inherits a strong relation between its super- and subdiagonal elements. The corresponding elements of the super- and subdiagonal will have the same absolute value.In this article some basic facts about a unitary equivalence transformation of an arbitrary matrix to tridiagonal form are firstly studied. Both an iterative reduction based on Krylov sequences as a direct tridiagonalization procedure via Householder transformations are reconsidered. This equivalence transformation is then applied to the normal case and equality of the absolute value between the super- and subdiagonals is proved. Self-adjointness of the resulting tridiagonal matrix with regard to a specific scalar product is proved. Properties when applying the reduction on symmetric, skew-symmetric, Hermitian, skew-Hermitian and unitary matrices and their relations with, e.g., complex symmetric and pseudo-symmetric matrices are presented.It is shown that the reduction can then be used to compute the singular value decomposition of normal matrices making use of the Takagi factorization. Finally some extra properties of the reduction as well as an efficient method for computing a unitary complex symmetric decomposition of a normal matrix are given.     

Spectral Analysis of Selfadjoint Jacobi Matrices with Periodically Modulated Entries

This paper deals with the spectral analysis of a class of selfadjoint unbounded Jacobi matrices J with modulated entries. The entries have the form of smooth sequences that increase to infinity multiplied by proper periodic sequences. For this class criteria for pure absolute continuity of the spectrum or its discreteness, and the asymptotics of generalized eigenvectors of J, are given. Some examples illustrating the stability zones of spectral structure are presented.