This question is related to this recent but currently unanswered MO question of Ricky Demer, where it arose as a comment.

Consider the structure $R^n$ consisting of $n\times n$ matrices over the reals $\mathbb{R}$, $n$-dimensional row vectors, column vectors and real scalars, with the ordered field structure on the scalars. Thus, we can add and multiply matrices; we can multiply anything by a scalar; we can multiply matrices by vectors (on the suitable side); and we can add and multiply vectors of the suitable shape.

The corresponding *matrix algebra* language has four
variable sorts - scalars, matrices, row vectors and column
vectors - together with the rules for forming terms so that
these expressions make sense in any $R^n$. In this
language, you can quantify over matrices, vectors and
scalars, form equations (and inequalities with the
scalars), but you cannot quantify over the dimension. The
idea is that an assertion in this language can be
interpreted in any dimension, one $R^n$ at a time. You have to make assertions that do not refer to the dimension; the
language is making assertions about matrices and vectors in
some fixed but unspecified dimension.

My question is whether truth in this real matrix algebra obeys a 0-1 law as the dimension increases, that is:

Question.Is every statement in the matrix algebra language either eventually true or eventually false in $R^n$ for all sufficiently large dimensions $n$?

To give some trivial examples:

- the statement asserting matrix commutativity $\forall A,B\, AB=BA$ is true in dimension $1$ but false in all higher dimensions.
- the statement that the dimension is at least 17, or at most 25, or an odd number less than 1000, are all expressible, since you can quantify over enough vectors and the assertions that they are independent or that they span are expressible. The truth values of these statements all stabilize in sufficiently high dimension.
- the assertion that a particular real number is an eigenvalue for a matrix is expressible.

~~But it isn't clear to me how one could express, for
example, that the dimension is even.~~ (Edit: Gerry and Ryan below have explained how this is easily done.)

In the previous question, Ricky inquired whether there is a decision procedure to determine which assertions of matrix algebra are true for all $n$. For any particular $n$, then Tarski's theorem on the decidability of real-closed fields shows that the theory of the structure $R^n$ is decidable: when $n$ is fixed, we may translate any statement about matrices and vectors into statements about real numbers by talking about the components. (We may also add to the language the functions that map a matrix or vector to the value of any particular entry, as well as $det(A)$ etc.)

If my question here has a positive answer, and the stabilizing bound is computable from the formula, then this would provide an affirmative answer to Ricky's question, since we could just determine truth in a large enough $R^n$.

Lastly, I don't think it will fundamentally change the problem to work in the complex field, since the corresponding structure $C^n$ with complex matrices and vectors is interpretable in $R^n$. For example, I think we could freely refer to complex eigenvalues.

**Edit.** The real case was quickly dispatched by Gerry and Ryan, below. Let us therefore consider the complex case. So we have for each dimension $n$ the structure $C^n$ with $n\times n$ matrices, row vectors, column vectors and complex scalars. The question is: Does the truth of every statement of matrix algebra stabilize in $C^n$ for sufficiently large $n$?

Ricky proposed that we add Hermitian transpose (conjugation on scalars) to the language. This would would also allow us to refer to the real scalars. If we expand the language so that we are able to define the class of real matrices and vectors, however, then we can still express Gerry's and Ryan's solutions for a negative answer here.

**Edit 2.** As in the comments, let us say that the *truth set* of a formula $\phi$ in the language is the set of $n$ for which $\phi$ is true in dimension $n$. These truth sets form a Boolean algebra, closed under finite differences. Which sets of natural numbers are realizable as truth sets? (Note that there are only countably many truth sets.) And how does it depend on the field?

16more comments