Invertible Matrices over Idempotent Semirings

By an idempotent semiring we mean a commutative semiring $(S,+, \cdot)$ with zero $0$ and identity $1$ such that $x+x = x = x^2$ for all $x \in S$ . In 1963, D.E. Rutherford showed that a square matrix $A$ over an idempotent semiring $S$ of 2 elements is invertible over $S$ if and only if $A$ 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 $A$ over an idempotent semiring $S$ is invertible over $S$ if and only if the product of any two elements in the same column [row] is 0 and the sum of all elements in each row[column] is $1$.