A (square) integer matrix which doesn't diagonalize over $\mathbb{Z}$ also doesn't diagonalize over some $\mathbb{Z}/p^{k}$

Question

Motivated by a series of recent Twitter polls by Daniel Litt, we ask (and answer, since the issue doesn't seem to have previously been addressed on this site) the following natural question:

Given a natural $\text{d}$, a $\text{d}\times\text{d}$ matrix $A$ with integer entries, and a commutative ring $\mathbb{E}$, say that $A$ diagonalizes over $\mathbb{E}$ if there exists a matrix $F\in\text{GL}_{\text{d}}\left(\mathbb{E}\right)$ with $F^{-1}AF$ diagonal (over $\mathbb{E}$). Clearly if $A$ diagonalizes over $\mathbb{Z}$, then it diagonalizes over every $\mathbb{E}$.

Question: If $A$ doesn't diagonalize over $\mathbb{Z}$, must there there exist a prime $p$ and natural $k$ such that $A$ also doesn't diagonalize over $\mathbb{Z}/p^{k}$?

Answer 1

$\require{AMScd}$Think of $A$ as a $\mathbb{Z}$-linear map $\mathbb{Z}^{\text{d}}\overset{A}{\to}\mathbb{Z}^{\text{d}}$ as per the standard basis of $\mathbb{Z}^{\text{d}}$. As we will be interested in taking the kernels of $A$ and of related maps, we will henceforth very explicitly denote the$\pmod{p^{k}}$ reduction of $A$ as $\mathbb{Z}/p^{k}\otimes_{\mathbb{Z}}A$ wherever we consider it. Otherwise, where $A$ appears in isolation, it can and should be assumed to be over $\mathbb{Z}$.

---

In general, given a $\text{d}\times\text{d}$ matrix $A$, there are three possible cases:

Case I: $A$'s characteristic polynomial doesn't split into (not necessarily distinct) linear factors over $\mathbb{Z}$.

By Gauss's lemma, $A$'s characteristic polynomial then doesn't split into linear factors over $\mathbb{Q}$. By Chebotarev's density theorem(!!), there then exists a prime $p$ such that $\mathbb{Z}/p\otimes_{\mathbb{Z}}A$'s characteristic polynomial (which is inherited from $\mathbb{Z}$) also doesn't split into linear factors over $\mathbb{Z}/p$. In particular, $\mathbb{Z}/p\otimes_{\mathbb{Z}}A$ must not diagonalize over $\mathbb{Z}/p$.

(Implicitly using that $A$'s characteristic polynomial is a similarity-invariant thereof and the characteristic polynomial of a diagonal matrix manifestly splits into linear factors.)

Case II: $A$'s characteristic polynomial does split into (not necessarily distinct) linear factors over $\mathbb{Z}$, with (distinct) roots $\lambda_{0},\dots,\lambda_{\text{n}-1}$ of respective multiplicities $e_{0},\dots,e_{\text{n}-1}>0$, but $$\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\ \not\simeq\ 0$$ (where $\lambda_{\text{j}}-A$ is shorthand for $\lambda_{\text{j}}$ times the $\text{d}\times\text{d}$ identity matrix minus $A$ and the components $\text{ker}\left(\lambda_{\text{j}}-A\right)\overset{\text{inc.}_{\text{j}}}{\to}\mathbb{Z}^{\text{d}}$ are the canonical kernel inclusions).

By the classification of finitely generated $\mathbb{Z}$-modules, there exists $p$ such that $$\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\ \not\simeq\ 0\text{;}$$ given such $p$ denote by $L$ the largest natural such that $p^{L}$ divides a nonzero diagonal entry of the $\mathbb{Z}$-Smith normal form of some $\lambda_{\text{j}}-A$. We claim that $\mathbb{Z}/p^{\text{d}L+1}\otimes_{\mathbb{Z}}A$ does not diagonalize over $\mathbb{Z}/p^{\text{d}L+1}$.

Indeed, consider the commutative diagram \begin{CD}\bigoplus_{\text{j}\colon\text{n}}\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{ker}\left(\lambda_{\text{j}}-A\right) @>\left(\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}>> \mathbb{Z}/p\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}} @>\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{pro.}>> \mathbb{Z}/p\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\\ @V\bigoplus_{\text{j}\colon\text{n}}\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{can.}^{L+1}_{\text{j}}VV @V\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{red.}V\simeq V @V\exists !VV\\ \bigoplus_{\text{j}\colon\text{n}}\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right) @>\left(\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}>> \mathbb{Z}/p\otimes_{\mathbb{Z}}\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}} @>\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{pro.}^{L+1}>> \mathbb{Z}/p\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\left(\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right) \end{CD} where:

• The components $$\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\text{inc.}^{L+1}_{\text{j}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}$$ are the analogous canonical kernel inclusions (not in general the same as $\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\text{inc.}_{\text{j}}$!).
• The maps $$\mathbb{Z}^{\text{d}}\ \overset{\text{pro}.}{\to}\ \text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)$$ $$\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\ \overset{\text{pro.}^{L+1}}{\to}\ \text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\left(\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right)$$ are the canonical cokernel morphisms (so that the rows of the diagram are themselves cokernel projections, by that $\mathbb{Z}/p\otimes_{\mathbb{Z}}-$ canonically preserves $\bigoplus_{\text{j}\colon\text{n}}$ and cokernels).
• The biproductands $$\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\text{can.}^{L+1}_{\text{j}}}{\to}\ \text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)$$ are the canonical kernel-to-kernel-of-tensor-product maps.
• The map $$\mathbb{Z}^{\text{d}}\ \overset{\text{red.}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}$$ is the canonical$\pmod{p^{L+1}}$ reduction map (which becomes an isomorphism upon the application of $\mathbb{Z}/p\otimes_{\mathbb{Z}}$).

By the construction of $L$, every element of $\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\subseteq\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}$ is equivalent$\pmod{p}$ to the$\pmod{p^{L+1}}$-reduction of an element of $\text{ker}\left(\lambda_{\text{j}}-A\right)\subseteq\mathbb{Z}^{\text{d}}$. It follows that the images of the maps $$\bigoplus_{\text{j}\colon\text{n}}\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}$$ $$\bigoplus_{\text{j}\colon\text{n}}\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\left(\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p\otimes_{\mathbb{Z}}\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}$$ are identified by the isomorphism $\mathbb{Z}/p\otimes\text{red.}$. In particular, the map $$\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\ \overset{\exists!}{\to}\ \mathbb{Z}/p\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\left(\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right)$$ from the above diagram is itself an isomorphism, so that by assumption $$\mathbb{Z}/p\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\left(\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right)\ \not\simeq\ 0\text{.}$$

Now suppose (for the sake of contradiction to this last non-isomorphism) that $\mathbb{Z}/p^{\text{d}L+1}\otimes_{\mathbb{Z}}A$ did diagonalize over $\mathbb{Z}/p^{\text{d}L+1}$, specifically with (not necessarily distinct) diagonal entries $\left(\beta_{\text{i}}\in\mathbb{Z}/p^{\text{d}L+1}\right)_{\text{i}\colon\text{d}}$. Manifestly, $$\text{coker}\left(\bigoplus_{\text{i}\colon\text{d}}\text{ker}\left(\beta_{\text{i}}-\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}A\right)\ \overset{\left(\text{inc.}'_{\text{i}}\right)_{\text{i}\colon\text{d}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right)\ \simeq\ 0\text{,}$$ (where the components $$\text{ker}\left(\beta_{\text{i}}-\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}A\right)\ \overset{\text{inc.}'_{\text{i}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}$$ are yet again the relevant canonical kernel inclusions). Each $\beta_{\text{i}}$ must (by the same argument as in Case I) be a root of $\mathbb{Z}/p^{\text{d}L+1}\otimes_{\mathbb{Z}}A$'s characteristic polynomial in $\mathbb{Z}/p^{\text{d}L+1}$, so must agree with some $\lambda_{\text{j}}$$\pmod{p^{L+1}}$. Thus there is a surjection $$0\ \simeq\ \text{coker}\left(\bigoplus_{\text{i}\colon\text{d}}\text{ker}\left(\beta_{\text{i}}-\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}A\right)\ \overset{\left(\text{inc.}'_{\text{i}}\right)_{\text{i}\colon\text{d}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right)\ \twoheadrightarrow\ \text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\left(\lambda_{\text{j}}-A\right)\right)\ \overset{\left(\text{inc.}^{L+1}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}/p^{L+1}\otimes_{\mathbb{Z}}\mathbb{Z}^{\text{d}}\right)\text{,}$$ the desired contradiction.

Case III: $A$'s characteristic polynomial does split into (not necessarily distinct) linear factors over $\mathbb{Z}$, with (distinct) roots $\lambda_{0},\dots,\lambda_{\text{n}-1}$ of respective multiplicities $e_{0},\dots,e_{\text{n}-1}>0$, and $$\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\ \simeq\ 0$$ (with the same notation as in Case II).

Observe that $\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}$ is in any case injective, since for any $\left(v_{\text{j}}\right)_{\text{j}\colon\text{n}}\in\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\right)$, $$\left(\lambda_{\text{n}-1}-A\right)\cdots\left(\lambda_{\text{j}'+1}-A\right)\left(\lambda_{\text{j}'-1}-A\right)\cdots\left(\lambda_{0}-A\right)\text{inc.}\left(\left(v_{\text{j}}\right)_{\text{j}\colon\text{n}}\right)\ =\ \underbrace{\left(\lambda_{\text{n}-1}-\lambda_{\text{j}'}\right)\cdots\left(\lambda_{\text{j}'+1}-\lambda_{\text{j}'}\right)\left(\lambda_{\text{j}'-1}-\lambda_{\text{j}'}\right)\cdots\left(\lambda_{0}-\lambda_{\text{j}'}\right)}_{>\ 0}\text{inc.}_{\text{j}'}\left(v_{\text{j}'}\right)$$ for all $\text{j}'\colon\text{n}$. I.e., $\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}$ is in this case an isomorphism. As each $\text{ker}\left(\lambda_{\text{j}}-A\right)$ is a free $\mathbb{Z}$-module (being a sub-$\mathbb{Z}$-module of $\mathbb{Z}^{\text{d}}$), a $\mathbb{Z}$-basis of $\mathbb{Z}^{\text{d}}$ in which $\mathbb{A}$ diagonalizes can be constructed by choosing a $\mathbb{Z}$-basis for each of its biproductands and taking their collective image under $\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}$.

---

TL;DR: in Case I and Case II, $A$'s failure to diagonalize over $\mathbb{Z}$ is inherited over some $\mathbb{Z}/p^{k}$. In Case III, $A$ does diagonalize over $\mathbb{Z}$. As the three cases span the space of possibilities (and are mutually exclusive), the claim follows. $\blacksquare$

Answer 2

Here's a much shorter means by which to handle the long step of the other answer (i.e., fitting Case II into the classification), albeit dependent upon the axiom of countable choice and without the effective bound of the more involved argument. Maintaining its notation,

Claim: If $A$'s characteristic polynomial splits into (not necessarily distinct) linear factors over $\mathbb{Z}$, with (distinct) roots $\lambda_{0},\dots,\lambda_{\text{n}-1}$ of respective multiplicities $e_{0},\dots,e_{\text{n}-1}>0$, and if for all primes $p$ and naturals $k$ the matrix $A$ diagonalizes over each $Z/p^{\text{k}}$, then $$\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\ \simeq\ 0\text{.}$$ (The original claim in Case II being the contrapositive.)

Proof: If $A$ diagonalizes over each $\mathbb{Z}/p^{\text{k}}$, then by König's lemma (applied separately to each prime $p$) it diagonalizes over each $\hat{\mathbb{Z}}_{p}$. As each $\hat{\mathbb{Z}}_{p}\otimes_{\mathbb{Z}}-$ is exact, it follows that $$\hat{\mathbb{Z}}_{p}\otimes_{\mathbb{Z}}\text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-A\right)\ \overset{\left(\text{inc.}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \mathbb{Z}^{\text{d}}\right)\ \simeq\ \text{coker}\left(\bigoplus_{\text{j}\colon\text{n}}\text{ker}\left(\lambda_{\text{j}}-\hat{\mathbb{Z}}_{p}\otimes_{\mathbb{Z}}A\right)\ \overset{\left(\hat{\text{inc.}}_{\text{j}}\right)_{\text{j}\colon\text{n}}}{\to}\ \hat{\mathbb{Z}}_{p}^{\text{d}}\right)\ \simeq\ 0$$ for all primes $p$. The claim is now immediate from the classification of finitely generated $\mathbb{Z}$-modules. (Note that we have implicitly used that the roots of $A$'s characteristic polynomial over each $\hat{\mathbb{Z}}_{p}$ agrees with the roots of the same over $\mathbb{Z}$.) $\Box$