On tropical matrices of small factor rank

The notion of the factor rank of tropical matrices is considered. We construct a linear-time algorithm that either finds a full-rank 3 × 3 submatrix of a given matrix A or concludes that the factor rank of A is less than 3. We show that there exist matrices of factor rank 4 whose 4 × 4 submatrices are all rank deficient.