POWERS OF CIRCULANTS IN BOTTLENECK ALGEBRA

Consider the powers of a square matrix A of order n in bottleneck alge bra, where addition and multiplication are replaced by the max and min operations. The powers are periodic, starting from a certain power A( K). The smallest such K is called the exponent of A, and the length of the period is called the index of A. Cechlarova has characterized the matrices of index 1. Here we consider the case where A is a circulant matrix. We show that a circulant A is idempotent (exponent and period equal to 1) if and only if the set of positions of those entries of t he first row that exceed any constant forms a group under addition mod ule n (positions are indexed from 0 to n - 1). The exponent of a circu lant of order n does not exceed n - 1, and this bound is best possible . The index of a circulant of order n is d/d', where d = gcd(n,j(2) - j(1),..., j(t) - j(1)), d' = gcd(d, j(1)), and {j(1),...,j(t)} is the set of positions of the maximal elements in the first row. When the in dex is 1, we say that the circulant is strongly stable; this happens i f and only if d divides ii, and this fact is shown to be equivalent to the result of Cechlarova for the case of circulant matrices. One of t he powers A(k), k greater than or equal to K, is idempotent, and conse quently all of these powers have the ''dovetailing'' property that in each row, the elements of each size are equally spaced between the lar ger elements. (C) Elsevier Science Inc., 1997.