Power convergent Boolean matrices
type: Item
instance of: scholarly article
title: Power convergent Boolean matrices
zbMATH Open document ID: 0773.15006
DOI: 10.1016/0024-3795(93)90323-G
author: D. A. Gregory
author: Norman J. Pullman
author: S. J. Kirkland
published in: Linear Algebra and its Applications
publication date: 1993-05-16T00:00:00Z
review text: Binary Boolean matrices, i.e. matrices whose entries are 0 or 1 and \(1+1=1\), are considered. If \(A,B\) are binary matrices of the same size, then we write \(A\geq B\) if the inequality holds entrywise. An \(n\times n\) binary matrix \(A\) is limit dominating if its powers converge to a limit \(L\) and \(A\geq L\). Limit dominating matrices can be regarded as generalizations of the transitive matrices (\(A\geq A^ 2\)) and the idempotent matrices (\(A=A^ 2\)). It is shown that if \(A\) is limit dominating, then the power limit \(L\) can be found immediately from \(A\). Moreover, the residual matrix \(N=A\setminus L\) is nilpotent and \(A^ k=L+N^ k\) for all positive integers \(k\). Using the Frobenius normal form, upper and lower attainable bounds for the index of convergence \(k(A)\) (the first \(k\) such that \(A^ k=L\)) are obtained. It is also shown that a binary matrix \(A\) is idempotent if and only if it is limit dominating and the number of nonzero diagonal blocks in its Frobenius normal form equals its column rank. A natural generalization for limit dominating matrices with entries from an arbitrary finite Boolean algebra is given.
Mathematics Subject Classification ID: 15B33
Mathematics Subject Classification ID: 05B20
zbMATH DE Number: 166249
zbMATH Keywords: limit dominating matrices
zbMATH Keywords: Boolean matrices
zbMATH Keywords: transitive matrices
zbMATH Keywords: idempotent matrices
zbMATH Keywords: Frobenius normal form
zbMATH Keywords: index of convergence
zbMATH Keywords: finite Boolean algebra
reviewed by: Vladimir Fleischer
MaRDI profile type: Publication
cites work: Combinatorial matrix theory
cites work: Primes in the semigroup of Boolean matrices
cites work: Idempotent Boolean matrices
cites work: Q3958592
cites work: Boolean spectral theory
cites work: A Property of Infinite Products of Boolean Matrices
cites work: On the graphs of finite idempotent Boolean relation matrices
cites work: A construction for idempotent binary relations
description: scientific article; zbMATH DE number 166249