No Access

Linearizing the word problem in (some) free fields

Konrad Schrempf

Fakultät für Mathematik, Universität Wien, Oskar-Morgenstern-Platz 1, 1090 Wien, Austria

https://doi.org/10.1142/S0218196718500546Cited by:2 (Source: Crossref)

Abstract

We describe a solution of the word problem in free fields (coming from non-commutative polynomials over a commutative field) using elementary linear algebra, provided that the elements are given by minimal linear representations. It relies on the normal form of Cohn and Reutenauer and can be used more generally to (positively) test rational identities. Moreover, we provide a construction of minimal linear representations for the inverse of nonzero elements.

Communicated by J.-E. Pin

Keywords:

AMSC: 16K40, 03B25, 16S10, 15A22

References

1. S. A. Amitsur , Rational identities and applications to algebra and geometry, J. Algebra 3 (1966) 304–359. Web of Science, Google Scholar
2. A. S. Amitsur and J. Levitzki , Minimal identities for algebras, Proc. Amer. Math. Soc. 1 (1950) 449–463. Web of Science, Google Scholar
3. G. W. Anderson , Convergence of the largest singular value of a polynomial in independent Wigner matrices, Ann. Probab. 41(3B) (2013) 2103–2181. Web of Science, Google Scholar
4. S. T. Belinschi, T. Mai and R. Speicher , Analytic subordination theory of operator-valued free additive convolution and the solution of a general random matrix problem, J. Reine Angew. Math. 732 (2017) 21–53. Web of Science, Google Scholar
5. G. M. Bergman , The diamond lemma for ring theory, Adv. Math. 29(2) (1978) 178–218. Web of Science, Google Scholar
6. J. Berstel and C. Reutenauer , Noncommutative Rational Series with Applications, Encyclopedia of Mathematics and its Applications, Vol. 137 (Cambridge University Press, Cambridge, 2011). Google Scholar
7. A. Cardon and M. Crochemore , Détermination de la représentation standard d’une série reconnaissable, RAIRO Inform. Théor. 14(4) (1980) 371–379. Web of Science, Google Scholar
8. P. M. Cohn , Generalized rational identities, in Ring Theory (Academic Press, New York, 1972), pp. 107–115. Google Scholar
9. P. M. Cohn , Free Rings and Their Relations, 2nd edn. London Mathematical Society Monographs, Vol. 19 (Academic Press, Inc. London, 1985). Google Scholar
10. P. M. Cohn , Skew Fields: Theory of general division rings, Encyclopedia of Mathematics and its Applications, Vol. 57 (Cambridge University Press, Cambridge, 1995). Google Scholar
11. P. M. Cohn , Further Algebra and Applications (Springer, London, 2003). Google Scholar
12. P. M. Cohn , Free Ideal Rings and Localization in General Rings, New Mathematical Monographs, Vol. 3 (Cambridge University Press, Cambridge, 2006). Google Scholar
13. P. M. Cohn and C. Reutenauer , A normal form in free fields, Canad. J. Math. 46(3) (1994) 517–531. Web of Science, Google Scholar
14. P. M. Cohn and C. Reutenauer , On the construction of the free field, Internat. J. Algebra Comput. 9(3-4) (1999) 307–323, dedicated to the memory of Marcel-Paul Schützenberger. Link, Web of Science, Google Scholar
15. M. Fliess , Matrices de Hankel, J. Math. Pures Appl. (9) 53 (1974) 197–222. Google Scholar
16. E. Fornasini and G. Marchesini , On the problems of constructing minimal realizations for two-dimensional filters, IEEE Trans. Pattern Anal. Mach. Intell. 2(2) (1980) 172–176. Web of Science, Google Scholar
17. M. Fortin and C. Reutenauer , Commutative/noncommutative rank of linear matrices and subspaces of matrices of low rank, Sém. Lothar. Combin. 52 (2004) 12 pp. Google Scholar
18. I. Gelfand, S. Gelfand, V. Retakh and R. L. Wilson , Quasideterminants, Adv. Math. 193(1) (2005) 56–141. Web of Science, Google Scholar
19. J. W. Helton, S. A. McCullough and V. Vinnikov , Noncommutative convexity arises from linear matrix inequalities, J. Funct. Anal. 240(1) (2006) 105–191. Web of Science, Google Scholar
20. G. Higman , The units of group-rings, Proc. London Math. Soc. (2) 46 (1940) 231–248. Google Scholar
21. R. E. Kalman, P. L. Falb and M. A. Arbib , Topics in Mathematical System Theory (McGraw-Hill, New York, 1969). Google Scholar
22. C. Reutenauer , Inversion height in free fields, Selecta Math. (N.S.) 2(1) (1996) 93–109. Google Scholar
23. M. L. Roberts , Endomorphism rings of finitely presented modules over free algebras, J. London Math. Soc. (2) 30(2) (1984) 197–209. Google Scholar
24. A. Salomaa and M. Soittola , Automata-Theoretic aspects of Formal Power Series, Texts and Monographs in Computer Science (Springer-Verlag, New York, 1978). Google Scholar
25. M. P. Schützenberger , On the definition of a family of automata, Inform. Control 4 (1961) 245–270. Google Scholar
26. J. Volčič , Matrix coefficient realization theory of noncommutative rational functions, J. Algebra 499 (2018) 397–437. Web of Science, Google Scholar