Invertible Matrices over Idempotent Semirings

Abstract

By an idempotent semiring we mean a commutative semiring  with zero and identity such that for all . In 1963, D.E. Rutherford showed that a square matrix over an idempotent semiring of  elements is invertible over if and only if is a permutation matrix. By making use of C. Reutenauer and H. Straubing's theorems, we extend this result to an idempotent semiring as follows: A square matrix over an idempotent semiring  is invertible over if and only if the product of any two elements in the same column [row] is and the sum of all elements in each row [column] is .