Sign-nonsingular matrices and matrices with unbalanced determinant in symmetrised semirings

The operations ⊕ and ⊗ are defined by a ⊕ b = max{a, b}, a ⊗ b = a + b over the set of reals extended by -∞. The columns a⁽¹⁾, . . . , a⁽ⁿ⁾ of an n × n matrix A are said to be linearly dependent in max-algebra if ∑^⊕_j∈Uλj⊗a ^(j)=∑^⊕_j∈vλj⊗a ^(j) holds for some λ₁, . . . , λ_n ∈ R; U, V ≠ ∅ U ∩ V = ∅ U ∪ V = {1, . . ., n}. We prove that there is a close relationship between sign-nonsingular (SNS) (0, 1, -1) matrices and matrices with unbalanced determinant in symmetrised semirings. Given a matrix A we then show how to construct a (0, 1, -1) matrix à such that A has columns linearly dependent in max-algebra if and only if à is not SNS. Also, it follows that if the system A ⊗ x = B ⊗ x has a nontrivial solution then C̃ is not SNS, where C = AΘB (here Θ stands for the subtraction in the symmetrised semiring). As another corollary we have a new, independent proof that the problems of checking whether a matrix is SNS and that of deciding whether a digraph contains a cycle of even length, are polynomially equivalent.