Does the truth of any statement of real matrix algebra stabilize in sufficiently high dimensions?
The irreducible, finite-dimensional complex representations of the Lie algebra $\mathfrak{sl}_2 \oplus \mathfrak{sl}_2$ are all of the form $V \otimes W$, where $V$ and $W$ are irreducible representations of $\mathfrak{sl}_2$; both $V$ and $W$ may have any dimension (and there is a unique representation of each dimension, not that it matters). If we require that neither copy of $\mathfrak{sl}_2$ act trivially, then $\dim(V \otimes W)$ is necessarily a composite integer. In particular, $n$ is prime if and only if $\mathbb{C}^n$ does not admit such a representation of this Lie algebra.
Note that $\mathfrak{sl}_2$ is spanned linearly by three elements with well-known Lie brackets, so a representation of $\mathfrak{sl}_2$ can be given by six matrices and fifteen commutator relations; specifying that one copy is nontrivial is a matter of specifying that one of the pairs of three does not consist of all zero matrices.
Later: Using representations of $\mathfrak{sl}_2$, we can refer to the dimension of a vector space: let $V$ have an irreducible representation of $\mathfrak{sl}_2$, as expressed by operators $e, f, h$ with the usual relations. Then if $ev = 0$, the weight $l$ as in $hv = lv$ uniquely determines the dimension.
Here is an elaboration on the ideas in Mariano's second post and Victor's comments under it and elsewhere, inspired by one of Peter Shor's comments to the question itself.
We can say that a vector space $V$ is a direct sum of (a specified number) $k$ subspaces if there are $k$ orthogonal idempotent matrices $P_i = P_i^2$ such that $\sum_{i = 1}^k P_i = I$. Moreover, using this construction we can speak of the subspaces themselves, as the images of the $P_i$.
We can say that $V$ is a tensor product of (a specified number) $k$ spaces $W_1, \dots, W_k$ by asking that it admit an irreducible representation of $\mathfrak{sl}_2^{\oplus k}$, say with generators $e_i, f_i, h_i$ in the usual notation. Suppose more generally that we have expressed $V = \bigotimes W_i \oplus V_0$, where $V_0$ has "reference" dimension $n$ as expressed above. Then we can say that the $W_i$ all have dimension equal to that of $V_0$ by testing highest weights in $V$. In summary: given $n$, we can express $n^k$ for any $k$ in terms of representation theory.
Let $f \in \mathbb{N}[x_1, \dots, x_r]$ be any polynomial, $f(x) = \sum a_{i_1, \dots, i_r} x_1^{i_1} \dots x_r^{i_r}$; we can say that $N = f(n_1, \dots, n_r)$ if $\mathbb{C}^N$ can be written as a direct sum of subspaces $W_{i_1, \dots, i_r}$, each of which is the direct sum of $a_{i_1, \dots, i_r}$ copies of the tensor product $(\mathbb{C}^{n_1})^{i_1} \otimes \dots \otimes (\mathbb{C}^{n_r})^{i_r}$.
Finally, if $f, g \in \mathbb{N}[x_0, x_1, \dots, x_r]$, we can say that $f(n, x_1, \dots, x_r) = g(n, x_1, \dots, x_r)$ is solvable in positive integers $x_1, \dots, x_r$ if we have a vector space $V$ expressible as an above such decomposition for both $f(n, \bullet)$ and $g(n, \bullet)$.
As an example, if we want to compute the diophantine set $S$ defined by $x_0 x_1 + x_2 - x_0^2 x_1$, we ask for a direct sum decomposition of $\mathbb{C}^N$ into subspaces $V_0, W$; of $W$ into a direct sum of $W_1, W_2, U$; and of $U$ into into $V_0 \otimes W_1 \oplus W_2$ and $V_0^{\otimes 2} \otimes W_1$. Then $n = \dim V_0$ is in $S$.
Thus, for any diophantine set $S$, there is a formula in matrix algebra with one free variable, representing a projection matrix onto a subspace of dimension $n$, which has an interpretation in some $\mathbb{C}^N$ if and only if $n \in S$. This is not really the same as showing that $S$ is a "truth set", though.
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!
As per my comment: you can definitely decide whether $n$ is even or odd, since it is if and only if $n$ is even that $A^2 = -I$ has a solution in an $n \times n$ real matrix $A$.
Here is how you can detect even complex dimension. If we have Hermitian conjugation, we can define a Hermitian matrix to be one $H$ such that $H^* = H$; any one is diagonalizable (with real eigenvalues, not that it matters). One can say that $H$ has distinct eigenvalues: if $Hv = \lambda v$ and $Hw = \lambda w$, then $v = \mu w$ for some $\mu$. Then $n$ is even if and only if there is a Hermitian matrix $H$ with distinct eigenvalues and a matrix $A$ such that for every eigenvector $v$ of $H$ we have an eigenvector $w$, with different eigenvalue, such that $Av = w$ and $Aw = -v$. (This describes $A$ as having the matrix $\bigl(\vcenter{\overset{\begin{smallmatrix} 0 & \;-I \end{smallmatrix}}{\begin{smallmatrix} I & \;\hphantom{-}0 \end{smallmatrix}}}\bigr)$, written in the eigenbasis of $H$.)