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 (Edit: Gerry and Ryan below have explained how this is easily done.)
example, that the dimension is even.
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?
Best Answer
One can get arithmetic progressions as truth sets, as in Joel's comment. Pick non-negative integers $a$ and $b$, pick a finite group $G$ which has at least one representation of degree $a$. Then there is a formula expression the statement "the vector space is a $G$-module which is a sum of irreducible representations of degree $a$ and exactly $b$ trivial summands".
Later: For example, the irreps of $G=(\mathbb Z_3\times\mathbb Z_3)\rtimes\mathbb Z_3$ have degree 1 and 3. It is generated by two elements which have cube equal to the identity, and which commute with their commutator. For example, if we want dimensions to be divisible by $3$, we can say:
$(\exists A,B)(A^3=B^3=[A,[A,B]]=[B,[A,B]]=I \wedge \neg(\exists v,\lambda,\mu)(Av=\lambda v\wedge Bv=\mu v))$
(uppercase letters are matrices, lowercase letters are vectors, greek letters are scalars, and commutators are group commutators) A model for this is a $G$ which does not have one-dimensional submodules. This works for other prime values of $3$.
Later: A vector space $V$ has a structure of $M_n(k)$-module iff $n\mid\dim V$. This can also be written in the language and it is much simpler that the first example!