Does the truth of any statement of real matrix algebra stabilize in sufficiently high dimensions?

Question

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?

Answer 1

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!

Answer 2

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.

Answer 3

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$.)

Answer 4

Fix an integer $n$. The dimension of a vector space $V$ is divisible by $n$ iff $V$ can be given the structure of a representation of the discrete Heisenberg group $H_n$ with central charge $1$. This is the Stone-von Neumann theorem. The multiplication table of $H_n$ is a finite length statement in our language, which is true in $n \mathbb Z$ and false otherwise.

Answer 5

One way to get the squares, as Victor asked in a comment, is the following: a simple module over $\mathfrak{sl}_2\oplus\mathfrak{sl}_2$ is of the form $V_n\otimes V_m$ (where $V_n$ is the $\mathfrak{sl}_2$-module of dimension $n+1$), and this has a submodule (for $\mathfrak{sl}_2$ acting diagonally) of dimension one exactly when $n=m$.

Answer 6

Here's an idea. I think it works, but it should be checked by people who understand representation theory better than I do. It's inspired by the reference given in Ito's answer to Ricky Demer's question, but since I don't really understand the reference, I can't tell whether it's the same construction or not.

We can express the statement (for fixed $k$): there are $k$ projection matrices $P_1$, $P_2$, $\ldots$, $P_k$ so that $\sum_j P_j = I$. Now, suppose we have a polynomial, say $Q(x,y,z) = \sum_{j=1}^k x^{\alpha_j} y^{\beta_j} z^{\gamma_j}$ (here, I'm using 3 variables only to reduce the number of subscripts). I want to claim that we can find a set whose truth set takes on values $x^{\alpha_m} + y^{\beta_m} + z^{\gamma_m} + Q(x,y,z)$ for $x \neq y \neq z$, where $\alpha_m = \max_j \alpha_j$, etc. First, we say our space is the sum of $k+3$ subspaces by finding $k+3$ projection matrices as above. Now, we say the first space has dimension $x^{\alpha_m}$ by representing it as a module over $\mathfrak{sl}_2^{\alpha_m}$, with appropriate submodules acting diagonally, as suggested by Mariano and Victor. We should be able to write down similar equations which show that the $j+3$'rd space has dimension $x^{\alpha_j} y^{\beta_j} z^{\gamma_j}$, for some $x$, $y$, $z$. Now, we want to require that the $x$ appearing in the $j+3$'rd space is the same as the $x$ appearing in the first space. I want to do this by saying that there's a subspace of the $j+3$'rd space which is also a module over $\mathfrak{sl}_2^{\alpha_j}$, and that there's an involution between the first subspace and this subspace of the $j+3$'rd space which preserves this module structure.

I think this will work ... could people check it?

If it does work, it shows the question is undecidable, because we can use the same structure to get a diophantine equation ... keep the first three projection matrices the same, find new projection matrices for the rest of the space, and write down equations which give a different polynomial.

UPDATE 2:

I misunderstood Victor's question. I'll leave the comments I wrote anyway.

(1) I imposed the condition $x\neq y \neq z$ because I was worried that if $x=y$, you could somehow use a space of dimension $x^{\max(\alpha_j, \beta_j)}$ rather than $x^{\alpha_j + \beta_j}$. But I think I was being stupid.

(2) A term $k x^\alpha y^\beta$ can be composed by adding $k$ terms, each one being $x^\alpha y^\beta$. Is this what you were asking?

(3) The first three spaces was for showing the problem is undecideable. We have two polynomials with coefficients in $Z^+$, $Q_1(x_1 \ldots x_3)$ and $Q_2(x_1 \ldots, x_3)$, and we want to know if there is a solution to $Q_1 = Q_2$ in the positive integers. Now, we do the above construction twice, with completely new variables except for the first three projectors $P_1$, $P_2$, and $P_3$. We use to these make sure the $x$ we substitute in $Q_1$ are equal to the x we substitute in $Q_2$. On further thought, we don't need these, either.

Answer 7

Over an arbitrary field, you can decide whether $n$ is even or odd by testing whether there exists a matrix $A$ such that $\pm 1$ are not its eigenvalues and $A$ is conjugate to $A^{-1}$ (yes for even, no for odd).

Answer 8

What about the following easy-looking statement:

for every $n\times n$ matrix, one has $\det(A^T-A)=0$,

which is true if $n$ is odd, but false if $n$ is even ?