Take multi-sorted first-order logic with equality, complex scalars, 1xn vectors, nx1 vectors, nxn matrices, addition and multiplication for each pair of sorts they make sense for, and hermitian transpose (which is conjugation on scalars). Is it decidable what sentences are [true for all n]? (there are 4 sorts, what sentences are true simultaneously for all n)


(For each particular n, it is decidable by interpreting in a real ordered field.)


What if we also add real scalars and ≤ for them?



Decidability of matrix algebra
The second problem (where real scalar variables and the comparison relation are also allowed) is equivalent to the first problem. Here is a standard argument showing this:


* A complex scalar variable z can be restricted to real values by requiring $z=\bar{z}$.
* The comparison x≤y can be replaced by $\exists z.\ x+z\bar{z}=y$, where z is a fresh complex scalar variable.


Back to the original question, the following paper may be related (or even answer your question) but I do not have enough knowledge to understand the content completely. Mihai Putinar: [Undecidability in a Free \*-Algebra](https://scholar.google.com/scholar?hl=en&q=Putinar+Undecidability+Free+Algebra), preprint, April 2007, <https://www.ima.umn.edu/sites/default/files/2165.pdf> ([Wayback Machine](https://web.archive.org/web/20220709100927/https://www.ima.umn.edu/sites/default/files/2165.pdf)).


