Codes and noncommutative stochastic matrices (Q1959746)

An \(n\times n\) matrix \(S\) over a skew field is called stochastic if \(Se=e\) for the column vector \(e=~^{t}(1\;1\dots 1)\). In the commutative case it is well known that \(S\) also has a left (row) eigenvector \(f\) for the eigenvalue \(1\); in the generic case we can take \(f=(f_1,\dots,f_n)\) where \(f_i\) is the determinant of the matrix obtained by deleting the \(i\)th row and \(i\)th column of \(I-S\). The authors' aim in the present paper is to generalize these results to the noncommutative case. Suppose that \(S\) is generic (its entries are noncommuting variables subject ony to the condition \(Se=e\)). Let \(M_{i}\) be the set of paths from \(i\) to \(i\) in the complete digraph on \(\{1,2,\dots,n\}\). Then \(M_{i}\) is a free monoid whose basis \(C_{i}\) is a prefix code. Let \(P_{i}\) be the set of proper prefixes of \(C_{i}\) (the paths starting at \(i\) and not passing through \(i\) again). Then \(P_{i}\) can be identified with a noncommutative power series equal to the sum of the words in \(P_{i}\). The reciprocal \(P_{i}^{-1}\) of this power series can be evaluated in the free field generated by the entries of \(S\), and the row vector \((P_1^{-1},\dots,P_n^{-1})\) is the required left eigenvector for \(S\). The proof of these facts requires various subsiduary results about matrices over skew fields and automata. The second half of the paper deals with related results on unambiguous automata (= representations of free monoids by monoids consisting of \(n\times n\) matrices over \(\mathbb{Q}\) with all entries equal to \(0\) or \(1\)). An appendix shows how some of the results can be obtained using a theory of quasideterminants.