Power convergent Boolean matrices (Q1208302)

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.