Transitive closure and related semiring properties via eliminants (Q1089083): Difference between revisions

Let \((S,+,\cdot)\) be a semiring such that \((S,+)\) is a commutative semigroup with neutral 0 and (S,\(\cdot)\) is a semigroup with neutral e, and assume (1) \(0a=a0=0\) for all \(a\in S\). Semirings of this kind, mostly those with idempotent addition, have become valuable tools, e.g. for various ''path problems'', in the theory of languages and in data flow analysis. In this context, solutions of the equations (2) \(x=ax+e=xa+e\) in S and (3) \(X=AX+E=XA+E\) in the semiring \(M_ n(S)\) of \(n\times n\)- matrices over S are of importance, and the literature deals with numerous methods to obtain a (suitable) solution of (3) for some \(A\in M_ n(S)\), mostly by the aid of solutions of (2) for several elements \(a\in S\). In particular, each equation (3) is solvable iff each equation (2) is, but uniqueness of the latter does not imply uniqueness of the former [cf. e.g. \textit{B. Mahr}, Ann. Discrete Math. 19, 229-256 (1984; Zbl 0567.16025) and references given there]. The paper deals only with semirings S such that each equation (2) has solutions and denotes one of them by \(a^*\). Depending on that choice, the ''eliminant'' \(| A|\) of a matrix \(A\in M_ n(S)\) is defined and a corresponding theory developed, which has some resemblance to the linear algebraic concept of determinants. By the aid of these eliminants, for each \(A\in M_ n(S)\) a matrix \(A^*\) is defined which is a solution of (3). Three algorithms - clearly depending on \(a^*\) in S - are given and shown to produce \(A^*\), e.g. that of McNaughton and Yamada which is similar to the Gauss-Jordan elimination method for inverting matrices in linear algebra. Moreover, for systems of equations \(x_{\nu}=a_{\nu 1}x_ 1+...+a_{\nu n}x_ n+b_{\nu}\) in S one solution \((x_ 1,...,x_ n)\) is directly given by one eliminant for each \(x_{\nu}\), and similarly for an equation \(X=XA+B\) in \(M_ n(S).\) Important remark: It is claimed that all this can be applied to a semiring S obtained from the field \(({\mathbb{R}},+,\cdot)\) of real numbers by adjoining one element \(\infty\), defining \(a^*=1/(1-a)\) for \(1\neq a\in {\mathbb{R}}\) and \(1^*=\infty^*=\infty\). This fails to be true. The reason is that (1) is essential for the theory of eliminants, but \(0\infty =\infty 0=0\) contradicts the distributive law, e.g. \((1+(-1))\infty =0\neq 1\infty +(-1)\infty =\infty\).