# Counting core sets in matrix rings over finite fields

Roswitha Rissner  Department of Mathematics
University of Klagenfurt
Universitätsstraße 65-67
9020 Klagenfurt am Wörthersee
Austria<EMAIL_ADDRESS>and  Nicholas J. Werner  Department of
Mathematics
Computer and Information Science
SUNY at Old Westbury
Old Westbury
NY 11568
USA<EMAIL_ADDRESS>
###### Abstract.

Let $R$ be a commutative ring and $M_{n}(R)$ be the ring of $n\times n$
matrices with entries from $R$. For each $S\subseteq M_{n}(R)$, we consider
its (generalized) null ideal $N(S)$, which is the set of all polynomials $f$
with coefficients from $M_{n}(R)$ with the property that $f(A)=0$ for all
$A\in S$. The set $S$ is said to be core if $N(S)$ is a two-sided ideal of
$M_{n}(R)[x]$. It is not known how common core sets are among all subsets of
$M_{n}(R)$. We study this problem for $2\times 2$ matrices over
$\mathbb{F}_{q}$, where $\mathbb{F}_{q}$ is the finite field with $q$
elements. We provide exact counts for the number of core subsets of each
similarity class of $M_{2}(\mathbb{F}_{q})$. While not every subset of
$M_{2}(\mathbb{F}_{q})$ is core, we prove that as $q\to\infty$, the
probability that a subset of $M_{2}(\mathbb{F}_{q})$ is core approaches 1.
Thus, asymptotically in $q$, almost all subsets of $M_{2}(\mathbb{F}_{q})$ are
core.

###### Key words and phrases:

Null ideal, matrix, integer-valued polynomial

###### 2020 Mathematics Subject Classification:

16S50, 15A15, 15B33, 13F20

This research was funded in part by the Austrian Science Fund (FWF)
[10.55776/DOC78]. For open access purposes, the authors have applied a CC BY
public copyright license to any author-accepted manuscript version arising
from this submission.

##  1\. Introduction

It is well known that an element $a$ of a commutative ring $R$ is a root of a
polynomial $f\in R[x]$ if and only if $x-a$ divides $f$. However, this need
not hold when $R$ is noncommutative. Given polynomials $f,g\in R[x]$, let $fg$
denote their product in $R[x]$. If $R$ is noncommutative, then evaluation at a
ring element $a\in R$ need not define a multiplicative map $R[x]\to R$; that
is, it may happen that $(fg)(a)\neq f(a)g(a)$. For example, let $K$ be a field
and let $M_{n}(K)$ be the ring of $n\times n$ matrices with entries from $K$.
Take $A$ and $B$ to be two non-commuting matrices in $M_{n}(K)$ and set
$f(x)=x-A$ and $g(x)=x-B$. Then, $(fg)(x)=x^{2}-(A+B)x+AB$, and
$(fg)(A)=-BA+AB\neq 0$, but $f(A)g(A)=0$. Observe that this is an example for
a polynomial that is divisible by $x-A$ but does not vanish on $A$. The
characterization of the polynomials that vanish on an element or a set of
elements of a noncommutative ring, therefore, poses a challenge.

We study the set of polynomials with matrix coefficients that vanish on a set
of square matrices. Let $R$ be a commutative ring. Given $S\subseteq
M_{n}(R)$, the _null ideal_ of $S\subseteq M_{n}(R)$ is defined as

$N(S)=\\{f\in M_{n}(R)[x]\mid f(A)=0\text{ for all }A\in S\\}.$ (1.1)

Throughout, we assume that the variable $x$ commutes with all elements in
$M_{n}(R)$ and that polynomials are evaluated from the right, as is a common
convention in the literature (cf. [14, §16]). It is easily verified that
$N(S)$ is a left ideal of $M_{n}(R)[x]$. It may, however, fail to be a right
ideal as the example above demonstrates for $N(\\{A\\})$.

######  Definition 1.1.

We call a set $S\subseteq M_{n}(R)$ _core_ if its null ideal is a two-sided
ideal of $M_{n}(R)$, and _noncore_ otherwise.

The purpose of this paper is to study null ideals and core sets in
$M_{2}(\mathbb{F}_{q})$, where $\mathbb{F}_{q}$ denotes the finite field with
$q$ elements. Originally, null ideals of matrices are a notion in classical
linear algebra, where they describe the set of all polynomials with
coefficients from a field $K$ that vanish on a matrix in $M_{n}(K)$.
Transferring the concept to the setting of a commutative ring $R$ instead of a
field $K$ already adds complexity as the polynomial ring $R[x]$ is in general
not a principal ideal domain anymore. Determining the generators of $\\{f\in
R[x]\mid f(S)=0\\}$ for a subset $S\subseteq M_{n}(R)$ is the subject of
research in the past decades, see e.g. [3, 4, 5, 11, 13, 17].

The study of null ideals is also strongly motivated by their connection to
integer-valued polynomials. Originally a notion associated to commutative ring
theory (see [6, 7] for a thorough treatment on the topic), mathematicians have
begun to study integer-valued polynomials over noncommutative rings in recent
years [8, 9, 10, 15, 18, 19, 22, 23]. The connection to null ideals in the
sense of this paper is the following: for a subset $S\subseteq M_{n}(R)$, we
want to study

$\operatorname{Int}(S,M_{n}(R)):=\\{f\in M_{n}(K)[x]\mid f(S)\subseteq
M_{n}(R)\\},$

where $R$ is a commutative integral domain and $K$ its quotient field. As the
evaluation map $M_{n}(K)[x]\to M_{n}(K)$ is not a ring homomorphism anymore,
it may happen that $\operatorname{Int}(S,M_{n}(R))$ is not a ring (w.r.t. the
usual addition and multiplication of polynomials). It is, however, known that
$\operatorname{Int}(S,M_{n}(R))$ is a ring if and only if the image of $S$ in
$M_{n}(R/aR)$ is a core set for all nonzero $a\in R$; see [24, Section 2] for
details. Hence, one way to characterize subsets $S$ for which
$\operatorname{Int}(S,M_{n}(R))$ is a ring is to characterize the core subsets
of residue rings of $M_{n}(R)$.

Recently, the second author studied null ideals in the general setting as
defined above in (1.1) with a particular focus on $2\times 2$ and $3\times 3$
matrices over a field [20, 24]. It is easy to see that any matrix ring
$M_{n}(R)$ with $n\geq 2$ will contain both core subsets and noncore subsets.
As mentioned above, a singleton set $\\{A\\}\subseteq M_{n}(R)$ may fail to be
core. On the other hand, both the empty set and $M_{n}(R)$ itself are core.
Less trivially, if $S\subseteq M_{n}(R)$ consists of scalar matrices, then
evaluation of polynomials at elements of $S$ behaves as in the ordinary
commutative setting, and $S$ is always core in this case. More generally, the
full similarity class of a matrix $A$ is always core [24, Proposition 3.1].
The article [24] includes a full algorithmic characterization of the core
subsets of $M_{2}(\mathbb{F}_{q})$, and some partial results on core subsets
in $M_{n}(\mathbb{F}_{q})$ with $n\geq 3$ are given in [20, 24].

A natural question which arises is: how common are core sets? Working in
$M_{n}(K)$, where $K$ is a field, we would like to determine (or at least
bound) the probability that a randomly selected subset of $M_{n}(K)$ is core.
In this paper, we accomplish this goal for $M_{2}(\mathbb{F}_{q})$. We
determine exact counts for the number of core subsets in each similarity class
of $M_{2}(\mathbb{F}_{q})$, and using this we show that as $q\to\infty$, the
probability that a randomly chosen subset of $M_{2}(\mathbb{F}_{q})$ is core
tends to $1$. Thus, asymptotically in $q$, almost all subsets of
$M_{2}(\mathbb{F}_{q})$ are core.

A concise summary of our main results follows.

###  1.1. Results

In this paper, we present counts for the core subsets of
$M_{2}(\mathbb{F}_{q})$ where $\mathbb{F}_{q}$ denotes the finite field of
cardinality $q$. We identify $\mathbb{F}_{q}$ with the field of scalar
matrices in $M_{2}(\mathbb{F}_{q})$, so that $\mathbb{F}_{q}\subseteq
M_{2}(\mathbb{F}_{q})$. Following [24] our approach is to first enumerate all
core subsets of each minimal polynomial class of $M_{2}(\mathbb{F}_{q})$. For
a polynomial $m\in\mathbb{F}_{q}[x]$, we set $\mathcal{C}(m)$ to be the set of
matrices in $M_{2}(\mathbb{F}_{q})$ whose minimal polynomial is $m$, and we
call this the minimal polynomial class of $m$. For $2\times 2$ matrices,
minimal polynomial classes coincide with similarity classes. That is, $A$,
$B\in\mathcal{C}(m)$ if and only if $A$ and $B$ are
$\operatorname{GL_{2}(\mathbb{F}_{q})}2$-conjugates. Consequently, we will use
the terms “minimal polynomial class” and “similarity class” interchangeably.

The minimal polynomials of matrices in $M_{2}(\mathbb{F}_{q})$ can be
categorized based on their factorization in $\mathbb{F}_{q}[x]$ into
irreducible polynomials. We distinguish four types of polynomials: linear
polynomials, quadratic irreducible polynomials, split quadratic polynomials
with a repeated root (i.e., those of the form $(x-a)^{2}$), and split
quadratic polynomials with distinct roots (those of the form $(x-a)(x-b)$ with
$a\neq b$). We call these types LIN, IRR, SQR, and SQD, respectively. Given a
minimal polynomial class $\mathcal{C}$ in $M_{2}(\mathbb{F}_{q})$, we will say
that $\mathcal{C}$ is LIN, IRR, SQR, or SQD, depending on the type of the
polynomial corresponding to $\mathcal{C}$.

In Theorems 1, 2, and 3 we give exact counts for the number of (non)core
subsets within each of the four types of minimal polynomial classes. Moreover,
in Proposition 2.7 we provide the size of each class, and the number of such
classes in $M_{2}(\mathbb{F}_{q})$. See Table 1 for a summary of these counts.
Note that we consider the empty set to be core.

For a quadratic minimal polynomial class $\mathcal{C}$, it is known [24,
Theorem 5.14] that a nonempty subset $S\subseteq\mathcal{C}$ is core if and
only if there exist $A$, $B\in S$ such that $A-B$ is invertible. Thus, for
IRR, SQR, and SQD classes, the number of noncore subsets equals the number of
subsets $S$ with the property that $A-B$ is singular for all $A$, $B\in S$
(cf. Corollaries 3.3 and 4.8). This condition is very similar to the one used
to define the regular graph of a matrix ring; see [1, 2, 16, 21] for recent
work on this topic. Hence, our results may be of interest to researchers
studying such graphs.

class type | # classes | size of class | # noncore subsets in class
---|---|---|---
LIN | $q$ | $1$ | 0
IRR | $\binom{q}{2}$ | $q^{2}-q$ | $q^{2}-q$
SQR | $q$ | $q^{2}-1$ | $(q+1)(2^{q-1}-1)$
SQD | $\binom{q}{2}$ | $q^{2}+q$ | $(q+1)(2^{q+1}-q-2)$
Table 1. Counts of noncore subsets in minimal polynomial classes

Subsets $S$ which are not contained in a single minimal polynomial class can
be partitioned into the subsets $S_{i}=S\cap\mathcal{C}(m_{i})$, one for each
minimal polynomial $m_{i}$ that occurs among the matrices in $S$. In that
respect, the following results from [24] play a crucial role:

  1. (1)

Unions of core sets are again core ([24, Proposition 3.1]).

  2. (2)

Subsets $S_{i}$ of type LIN are core (as they contain at most one element,
which is in the center of $M_{2}(\mathbb{F}_{q})$).

  3. (3)

If $S$ is core, then each $S_{i}$ of type IRR or SQR is core ([24, Corollary
5.2, Proposition 5.12]).

In light of these observations, we make the following definition.

######  Definition 1.2.

We call a set $S\subseteq M_{2}(\mathbb{F}_{q})$ _purely core_ if
$S\cap\mathcal{C}$ is core for all minimal polynomial classes $\mathcal{C}$.

Any purely core set is core, because unions of core sets are always core. It
is, however, possible that $S$ is core even though some $S\cap\mathcal{C}$ is
noncore. For this to occur, $\mathcal{C}$ must be an SQD class. Examples of
such behavior can be found in Example 2.2 and Section 6.

The counts presented in Table 1 can be used to enumerate all the purely core
subsets of $M_{2}(\mathbb{F}_{q})$. While there exist core sets that are not
purely core, we show in Section 5 that the number of such sets is small in
comparison to the number of purely core sets (see Theorem 4). Furthermore,
asymptotically, almost all subsets of $M_{2}(\mathbb{F}_{q})$ are purely core
(and hence are core):

######  Theorem 5.

  1. (1)

As $q\to\infty$, almost all subsets of $M_{2}(\mathbb{F}_{q})$ are purely
core. That is, as $q\to\infty$,

$\dfrac{\phantom{x}\\#\\{\text{purely core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}\phantom{x}}{\\#\\{\text{subsets of
$M_{2}(\mathbb{F}_{q})$}\\}}\to 1.$

  2. (2)

As $q\to\infty$, almost all core subsets of $M_{2}(\mathbb{F}_{q})$ are purely
core. That is, as $q\to\infty$,

$\dfrac{\phantom{x}\\#\\{\text{purely core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}\phantom{x}}{\\#\\{\text{core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}}\to 1.$

  3. (3)

As $q\to\infty$, almost all subsets of $M_{2}(\mathbb{F}_{q})$ are core. That
is, as $q\to\infty$,

$\dfrac{\phantom{x}\\#\\{\text{core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}\phantom{x}}{\\#\\{\text{subsets of
$M_{2}(\mathbb{F}_{q})$}\\}}\to 1.$

In the last section, we present some examples to demonstrate that counting
core subsets that are not purely core quickly becomes a challenging task, even
for small $q$.

##  2\. Preliminaries, Sizes of Similarity Classes, and the Irreducible Cases

In this section, we first collect a number of notations and results that will
be used frequently in the rest of the paper. We also provide proofs for the
number of each type of minimal polynomial class listed in Table 1, as well as
the size of each class. Finally, we prove Theorem 1, which enumerates the
number of core subsets of $\mathcal{C}(m)$ when $m$ is irreducible.

Given $S\subseteq M_{2}(\mathbb{F}_{q})$, let $\phi_{S}$ be the monic least
common multiple in $\mathbb{F}_{q}[x]$ of all the minimal polynomials of the
matrices in $S$. Since $M_{2}(\mathbb{F}_{q})$ is finite, such a polynomial is
guaranteed to exist. Note that if $S=\varnothing$, then $\phi_{S}=1$. The
polynomial $\phi_{S}$ is always an element of $N(S)$. Furthermore, it is shown
in [24, Theorem 4.4] that $S$ is core if and only if $N(S)$ contains no
polynomial of degree less than $\deg\phi_{S}$. Equivalently, $S$ is core if
and only if each polynomial in $N(S)$ is divisible by $\phi_{S}$. We also
obtain the following characterization of noncore subsets in quadratic minimal
polynomial classes.

######  Lemma 2.1.

Let $\mathcal{C}$ be either an IRR, SQR, or SQD class, and let
$S\subseteq\mathcal{C}$ be nonempty. Then, $S$ is noncore if and only if
$N(S)$ contains a polynomial of degree $1$.

###### Proof.

Under the stated hypotheses, $\phi_{S}$ has degree 2. Hence, $N(S)$ is not
generated (as a two-sided ideal of $M_{2}(\mathbb{F}_{q})[x])$ by $\phi_{S}$
if and only if $N(S)$ contains a linear polynomial. ∎

This lemma allows us to describe some examples of core and noncore subsets.

######  Example 2.2.

Let $A_{1}=\big{[}\begin{smallmatrix}1&0\\\ 0&0\end{smallmatrix}\big{]}$,
$A_{2}=\big{[}\begin{smallmatrix}1&1\\\ 0&0\end{smallmatrix}\big{]}$, and
$A_{3}=\big{[}\begin{smallmatrix}0&0\\\ 0&1\end{smallmatrix}\big{]}$. Let
$S_{1}=\\{A_{1},A_{2}\\}$ and $S_{2}=\\{A_{1},A_{3}\\}$. Then, all three
matrices are in the SQD class $\mathcal{C}(x(x-1))$, and
$\phi_{S_{1}}(x)=\phi_{S_{2}}(x)=x(x-1)$. The null ideal $N(S_{1})$ contains
the polynomial $\big{[}\begin{smallmatrix}0&1\\\
0&0\end{smallmatrix}\big{]}x$, and so $S_{1}$ is noncore by Lemma 2.1.
However, we can prove that $S_{2}$ is core. Suppose that $N(S_{2})$ contains
$\alpha x+\beta$, where $\alpha,\beta\in M_{2}(\mathbb{F}_{q})$. Then, $\alpha
A_{1}+\beta=0=\alpha A_{3}+\beta$, which implies that $\alpha(A_{1}-A_{3})=0$.
Since $A_{1}-A_{3}$ is invertible, we see that $\alpha=0$, and hence $\beta=0$
as well. Consequently, $N(S_{2})$ contains no linear polynomials, and so
$S_{2}$ is core.

Now, let $S_{0}=\left\\{\big{[}\begin{smallmatrix}0&0\\\
0&0\end{smallmatrix}\big{]},\big{[}\begin{smallmatrix}1&0\\\
0&1\end{smallmatrix}\big{]}\right\\}$, let $S^{\prime}$ be any subset of
$\mathcal{C}(x(x-1))$, and let $T=S_{0}\cup S^{\prime}$. Then,
$\phi_{T}(x)=x(x-1)$. Since $T$ contains the scalar matrices in $S_{0}$,
$N(T)$ contains no linear polynomials. Indeed if, $\alpha x+\beta\in N(T)$,
then evaluation at the zero matrix shows that $\beta=0$, and evaluation at the
identity matrix then yields $\alpha=0$. Thus, $T$ is core, even though
$S^{\prime}$ may be chosen to be noncore.

Building off of Lemma 2.1, we provide a number of equivalent conditions for
subsets of a quadratic minimal polynomial class to be core. For a subset $S$
of an SQD class, the property of being core can be described in terms of
certain left ideals of $M_{2}(\mathbb{F}_{q})$ that we call the
$\mathcal{L}$-modules of $S$.

######  Definition 2.3 (see [24, Definition 6.2]).

Let $\mathcal{C}((x-a)(x-b))$ be an SQD class, and let
$S\subseteq\mathcal{C}((x-a)(x-b))$. The $\mathcal{L}$-modules of $S$ are

$\displaystyle\mathcal{L}(S,a)$ $\displaystyle=\\{\alpha\in
M_{2}(\mathbb{F}_{q})\mid\alpha(x-a)\in N(S)\\}\text{ and }$
$\displaystyle\mathcal{L}(S,b)$ $\displaystyle=\\{\alpha\in
M_{2}(\mathbb{F}_{q})\mid\alpha(x-b)\in N(S)\\}.$

######  Proposition 2.4.

Let $m\in\mathbb{F}_{q}[x]$ be a monic quadratic polynomial and let
$S\subseteq\mathcal{C}(m)$ be nonempty.

  1. (1)

[24, Corollary 5.9(2)] If $m$ is IRR, then $S$ is core if and only if $|S|\geq
2$.

  2. (2)

[24, Theorem 5.14] If $m$ is SQR or SQD, then $S$ is core if and only if there
exists $A$, $B\in S$ such that $A-B$ is invertible.

  3. (3)

[24, Proposition 6.4(3)] Assume $m(x)=(x-a)(x-b)$ is SQD. Then, $S$ is core if
and only if $\mathcal{L}(S,a)=\mathcal{L}(S,b)=\\{0\\}$.

Let $m_{1}$, …, $m_{t}$ be all of the possible minimal polynomials of matrices
in $M_{2}(\mathbb{F}_{q})$. As noted in the introduction, any subset
$S\subseteq M_{2}(\mathbb{F}_{q})$ admits a decomposition
$S=\bigcup_{i=1}^{t}(S\cap\mathcal{C}(m_{i}))$, and $S$ is said to be purely
core if $S\cap\mathcal{C}(m_{i})$ is core for each $i$. Example 2.2
demonstrates that not all core sets are purely core. If $S$ is such a set,
then $S$ must have a nonempty intersection with some SQD class. Put
differently, if we ignore SQD classes, then sets are core if and only if they
are purely core.

######  Proposition 2.5.

Let $\mathcal{C}=\mathcal{C}_{1}\cup\cdots\cup\mathcal{C}_{k}$ be a union of
minimal polynomial classes in $M_{2}(\mathbb{F}_{q})$ such that
$\mathcal{C}_{i}$ is not SQD for all $1\leq i\leq k$. Then, a subset of
$\mathcal{C}$ is core if and only if it is purely core.

###### Proof.

The reverse implication is trivial. For the forward implication, let
$S\subseteq\mathcal{C}$ be core. Then, $S=S_{1}\cup\cdots\cup S_{k}$, where
$S_{i}=S\cap\mathcal{C}_{i}$ for each $i$. Fix $j$ between $1$ and $k$. If
$\mathcal{C}_{j}$ is LIN, then all subsets of $\mathcal{C}_{j}$ are core. If
$\mathcal{C}_{j}$ is IRR or SQR, then $S_{j}$ must be core by [24, Corollary
5.4] or [24, Proposition 5.12], respectively. Thus, $S_{i}$ is core for all
$1\leq i\leq k$, and therefore $S$ is purely core. ∎

Next, we count the number of each type (LIN, IRR, SQR, or SQD) of minimal
polynomial class in $M_{2}(\mathbb{F}_{q})$, and determine the size of each
class. These results are not new, but they were not readily available in the
literature, so we provide short proofs for the sake of completeness.

######  Lemma 2.6.

The polynomial ring $\mathbb{F}_{q}[x]$ contains $q$ monic linear polynomials,
$(q^{2}-q)/2$ monic irreducible quadratic polynomials, $q$ SQR polynomials,
and $(q^{2}-q)/2$ SQD polynomials.

###### Proof.

The polynomials in LIN, SQR, or SQD classes are determined by their roots.
Hence there are $q$ linear polynomials, and $q$ SQR polynomials. In the SQD
case, there are $\binom{q}{2}=(q^{2}-q)/2$ such polynomials, which correspond
to the subsets of $\mathbb{F}_{q}$ of size 2\. Since $\mathbb{F}_{q}[x]$
contains $q^{2}$ monic polynomials of degree 2, this leaves
$q^{2}-q-(q^{2}-q)/2=(q^{2}-q)/2$ monic quadratic irreducible polynomials. ∎

######  Proposition 2.7.

Let $\mathcal{C}$ be a minimal polynomial class in $M_{2}(\mathbb{F}_{q})$.

  1. (1)

If $\mathcal{C}$ is LIN, then $|\mathcal{C}|=1$.

  2. (2)

If $\mathcal{C}$ is IRR, then $|\mathcal{C}|=q^{2}-q$.

  3. (3)

If $\mathcal{C}$ is SQR, then $|\mathcal{C}|=q^{2}-1$.

  4. (4)

If $\mathcal{C}$ is SQD, then $|\mathcal{C}|=q^{2}+q$.

###### Proof.

Part (1) is trivial. For the degree 2 cases, assume that
$\mathcal{C}=\mathcal{C}(m)$, where $m$ is a monic quadratic polynomial in
$\mathbb{F}_{q}[x]$, and let $A\in M_{2}(\mathbb{F}_{q})$ have minimal
polynomial $A$. Then, $\mathcal{C}$ is equal to the similarity class of $A$.
Since this class is the orbit of $A$ under the conjugation action of
$\operatorname{GL_{2}(\mathbb{F}_{q})}2$, this means that
$|\mathcal{C}|=|\operatorname{GL_{2}(\mathbb{F}_{q})}2|/|\operatorname{cent}(A)|$,
where
$\operatorname{cent}(A)=\\{U\in\operatorname{GL_{2}(\mathbb{F}_{q})}2\mid
U^{-1}AU=A\\}$ is the centralizer of $A$. As
$|\operatorname{GL_{2}(\mathbb{F}_{q})}2|=(q^{2}-1)(q^{2}-q)$, it suffices to
calculate $|\operatorname{cent}(A)|$ in each case.

The minimal polynomial of $A$ equals the characteristic polynomial of $A$, so
by [12, Corollary 4.4.18] $\operatorname{cent}(A)$ is equal to the unit group
of the ring $\mathbb{F}_{q}[A]$. If $\mathcal{C}$ is IRR, then
$\mathbb{F}_{q}[A]$ is a field of order $q^{2}$,
$|\operatorname{cent}(A)|=q^{2}-1$, and $|\mathcal{C}|=q^{2}-q$. When
$\mathcal{C}$ is SQR,

$\mathbb{F}_{q}[A]\cong\mathbb{F}_{q}[x]/(x^{2})\cong\big{\\{}\big{[}\begin{smallmatrix}a&b\\\
0&a\end{smallmatrix}\big{]}\mid a,b\in\mathbb{F}_{q}\big{\\}},$

with $|\operatorname{cent}(A)|=q(q-1)$ and $|\mathcal{C}|=q^{2}-1$. Finally,
if $\mathcal{C}$ is SQD, then
$\mathbb{F}_{q}[A]\cong\mathbb{F}_{q}\times\mathbb{F}_{q}$, so
$|\operatorname{cent}(A)|=(q-1)^{2}$ and $|\mathcal{C}|=q(q+1)$. ∎

When $m$ is an irreducible polynomial, it is not hard to determine the number
of core subsets of $\mathcal{C}(m)$.

######  Theorem 1.

Let $m$ be an irreducible polynomial of degree at most $2$.

  1. (1)

If $m$ is linear, then $\mathcal{C}(m)$ contains $2$ core subsets.

  2. (2)

If $m$ is quadratic, then $\mathcal{C}(m)$ contains $q^{2}-q$ noncore subsets.

###### Proof.

If $m(x)=x-a$ with $a\in\mathbb{F}_{q}$, then $\mathcal{C}(m)=\\{a\\}$. This
is a subset of the center of $M_{2}(\mathbb{F}_{q})$ and hence core, cf. [24,
Lemma 3.3].

Let $m$ be quadratic irreducible and $S\subseteq\mathcal{C}(m)$. By
Proposition 2.4(1), $S$ is core if and only if $|S|\geq 2$. Since
$|\mathcal{C}(m)|=q^{2}-q$ by Proposition 2.7(2), $\mathcal{C}(m)$ contains
$q^{2}-q$ singleton sets which are exactly the noncore subsets. ∎

In the next two sections, we will focus on counting noncore subsets of SQR
classes and SQD classes. Dealing with SQR classes is straightforward, but SQD
classes require a more detailed analysis and make frequent use of the
$\mathcal{L}$-modules from Definition 2.3.

##  3\. SQR polynomials

Consider an SQR class $\mathcal{C}((x-a)^{2})$, where $a\in\mathbb{F}_{q}$.
Matrices in $\mathcal{C}((x-a)^{2})$ are in bijective correspondence with
matrices in $\mathcal{C}(x^{2})$ via the translation $A\to A+a$, and this
mapping preserves core subsets [24, Proposition 3.4]. Thus, to determine the
number of core subsets of $\mathcal{C}((x-a)^{2})$, it suffices to work in
$\mathcal{C}(x^{2})$.

######  Definition 3.1.

In $\mathcal{C}(x^{2})$, we define the following subclasses of matrices.

  * •

$T_{0}=\left\\{\big{[}\begin{smallmatrix}0&a\\\
0&0\end{smallmatrix}\big{]}\mid a\neq 0\right\\}$

  * •

$T_{0}^{\prime}=\left\\{\big{[}\begin{smallmatrix}0&0\\\
a&0\end{smallmatrix}\big{]}\mid a\neq 0\right\\}$

  * •

For each $\lambda\in\mathbb{F}_{q}^{\times}$,
$T_{\lambda}=\left\\{\Big{[}\begin{smallmatrix}a&\phantom{xx}\lambda a\\\
-\lambda^{-1}a&\phantom{xx}-a\end{smallmatrix}\Big{]}\,\,\middle|\,\,a\neq
0\right\\}$

We let
$\mathscr{P}=\\{T_{0},T_{0}^{\prime}\\}\cup\\{T_{\lambda}\mid\lambda\neq 0\\}$
be the collection of all of the above subclasses.

######  Proposition 3.2.

  1. (1)

For all $T\in\mathscr{P}$, $|T|=q-1$.

  2. (2)

The sets in $\mathscr{P}$ form a partition of $\mathcal{C}(x^{2})$.

  3. (3)

For all $A$, $B\in\mathcal{C}(x^{2})$, $A-B$ is singular if and only if there
exists $T\in\mathscr{P}$ such that $A,B\in T$.

  4. (4)

Let $S\subseteq\mathcal{C}(x^{2})$. Then, $S$ is noncore if and only if $S$ is
a nonempty subset of some $T\in\mathscr{P}$.

###### Proof.

(1) Each set in $\mathscr{P}$ consists of the nonzero scalar multiples of a
single matrix. Explicitly,
$T_{0}=\mathbb{F}_{q}^{\times}\cdot\big{[}\begin{smallmatrix}0&1\\\
0&0\end{smallmatrix}\big{]}$,
$T_{0}^{\prime}=\mathbb{F}_{q}^{\times}\cdot\big{[}\begin{smallmatrix}0&0\\\
1&0\end{smallmatrix}\big{]}$, and
$T_{\lambda}=\mathbb{F}_{q}^{\times}\cdot\big{[}\begin{smallmatrix}1&\lambda\\\
-\lambda^{-1}&-1\end{smallmatrix}\big{]}$. Thus, each set in $\mathscr{P}$ has
cardinality $q-1$.

(2) Let $\mathcal{U}=\bigcup_{T\in\mathscr{P}}T$ be the union of all the sets
in $\mathscr{P}$. Given $S$, $T\in\mathscr{P}$ such that $S\neq T$, it is
clear that $S\cap T=\varnothing$. Thus,
$|\mathcal{U}|=(q+1)(q-1)=|\mathcal{C}(x^{2})|$.

(3) $(\Leftarrow)$ Assume that matrices $A$ and $B$ are contained in the same
set $T\in\mathscr{P}$. Since elements of $T$ are scalar multiples of one
another, we have $B=cA$ for some nonzero $c\in\mathbb{F}_{q}$. Thus,
$A-B=(1-c)B$, which is singular because $B$ is singular.

($\Rightarrow$) We prove the contrapositive. Assume that $A$ and $B$ do not
lie in the same subclass of $\mathcal{C}(x^{2})$. Since all elements of
$\mathcal{C}(x^{2})$ are conjugate, there exists
$U\in\operatorname{GL_{2}(\mathbb{F}_{q})}2$ such that
$U^{-1}AU=\big{[}\begin{smallmatrix}0&1\\\ 0&0\end{smallmatrix}\big{]}$. Since
$A-B$ is invertible if and only if $U^{-1}(A-B)U$ is invertible, we may assume
without loss of generality that $A=\big{[}\begin{smallmatrix}0&1\\\
0&0\end{smallmatrix}\big{]}$ and that $B\notin T_{0}$. If $B\in
T_{0}^{\prime}$, then $A-B$ is clearly invertible. If $B\in T_{\lambda}$, then
$A-B$ has determinant $-\lambda^{-1}a$ for some nonzero $a$, and hence is
invertible. In all cases, we achieve the desired result.

(4) The empty set is core, so assume that $S\neq\varnothing$. By Proposition
2.4(2), $S$ is noncore if and only if $A-B$ is singular for all $A$, $B\in S$.
By part (3), this holds if and only if $S\subseteq T$ for some
$T\in\mathscr{P}$. ∎

######  Theorem 2.

Each SQR class in $M_{2}(\mathbb{F}_{q})$ contains $(q+1)(2^{q-1}-1)$ noncore
subsets.

###### Proof.

Let $\mathcal{C}$ be an SQR class in $M_{2}(\mathbb{F}_{q})$. As noted at the
start of Section 3, the number of noncore subsets of $\mathcal{C}$ is the same
as the number of noncore subsets of $\mathcal{C}(x^{2})$. By Proposition
3.2(4), the noncore subsets of $\mathcal{C}(x^{2})$ are exactly the nonempty
subsets of the subclasses introduced in Definition 3.1. There are $q+1$ such
subclasses, each of size $q-1$. Hence, $\mathcal{C}(x^{2})$ contains
$(q+1)(2^{q-1}-1)$ noncore subsets. ∎

Via Proposition 2.4(2), we can restate Theorem 2 in terms of subsets where the
difference of each pair of matrices is singular.

######  Corollary 3.3.

Let $m$ be an SQR polynomial. Then, $\mathcal{C}(m)$ contains
$(q+1)(2^{q-1}-1)$ subsets $S$ with the property that $A-B$ is singular for
all $A$, $B\in S$.

##  4\. SQD polynomials

Among the four types of minimal polynomial classes (LIN, IRR, SQR, and SQD),
the SQD classes are the most difficult in which to count core subsets. When
$\mathcal{C}$ is an SQR class, Proposition 3.2 shows that we can partition
$\mathcal{C}$ in such a way that noncore subsets are easy to identify. We are
not able to obtain such a clean decomposition in an SQD class. However, by
using $\mathcal{L}$-modules, we can define a useful collection of noncore
subsets of an SQD class. Recall that for a subset
$S\subseteq\mathcal{C}((x-a)(x-b))$ of an SQD class, the $\mathcal{L}$-modules
of $S$ are

$\displaystyle\mathcal{L}(S,a)$ $\displaystyle=\\{\alpha\in
M_{2}(\mathbb{F}_{q})\mid\alpha(x-a)\in N(S)\\}\text{ and }$
$\displaystyle\mathcal{L}(S,b)$ $\displaystyle=\\{\alpha\in
M_{2}(\mathbb{F}_{q})\mid\alpha(x-b)\in N(S)\\}.$

######  Definition 4.1.

Let $\mathcal{C}=\mathcal{C}((x-a)(x-b))$ be an SQD class. For each
$A\in\mathcal{C}$, we define

$\displaystyle\mathcal{B}(A,a)$
$\displaystyle:=\\{B\in\mathcal{C}\mid\mathcal{L}(\\{A,B\\},a)\neq 0\\}\text{
and }$ $\displaystyle\mathcal{B}(A,b)$
$\displaystyle:=\\{B\in\mathcal{C}\mid\mathcal{L}(\\{A,B\\},b)\neq 0\\}.$

We call these the _$\mathcal{B}$ -sets_ for $A$.

In Lemma 4.4 and Proposition 4.7 below, we prove that each $\mathcal{B}$-set
is noncore and has size $q$. By [24, Corollary 5.9], any subset of an SQD
class of size at least $q+1$ is core. Hence, $\mathcal{B}$-sets are noncore
subsets of maximal size in an SQD class. In Theorem 3, $\mathcal{B}$-sets will
be used to describe all of the noncore subsets of the SQD class
$\mathcal{C}((x-a)(x-b))$. Since these $\mathcal{B}$-sets are defined in terms
of $\mathcal{L}$-modules, we require more precise knowledge of these
structures. First, we show that the nonzero $\mathcal{L}$-modules in
$M_{2}(\mathbb{F}_{q})$ can be indexed by using linear subspaces and row
vectors in $\mathbb{F}_{q}^{2}$.

######  Definition 4.2.

Let $v=\langle v_{1},v_{2}\rangle$ be a row vector in $\mathbb{F}_{q}^{2}$. We
define

$\mathcal{L}_{v}=\mathcal{L}_{\langle
v_{1},v_{2}\rangle}:=\left\\{\begin{bmatrix}v_{1}y&v_{2}y\\\
v_{1}z&v_{2}z\end{bmatrix}\,\,\middle|\,\,y,z\in\mathbb{F}_{q}\right\\}.$

######  Lemma 4.3.

  1. (1)

For all $v\in\mathbb{F}_{q}^{2}$, $\mathcal{L}_{v}$ is a left ideal of
$M_{2}(\mathbb{F}_{q})$. When $v\neq 0$, $\mathcal{L}_{v}$ is a minimal left
ideal of $M_{2}(\mathbb{F}_{q})$.

  2. (2)

For all $v$, $w\in\mathbb{F}_{q}^{2}$, $\mathcal{L}_{v}=\mathcal{L}_{w}$ if
and only if $v$ and $w$ are nonzero scalar multiples of one another.

  3. (3)

If $L$ is a minimal left ideal of $M_{2}(\mathbb{F}_{q})$, then either
$L=\mathcal{L}_{\langle 0,1\rangle}$ or $L=\mathcal{L}_{\langle
1,\lambda\rangle}$ for some $\lambda\in\mathbb{F}_{q}$.

###### Proof.

(1) Each set $\mathcal{L}_{v}$ is easily seen to be a left ideal of
$M_{2}(\mathbb{F}_{q})$. When $v\neq 0$, $\mathcal{L}_{v}$ is nonzero and
proper, and hence must be a minimal left ideal of $M_{2}(\mathbb{F}_{q})$.

(2) $(\Rightarrow)$ The result is trivial if $v=0$ or $w=0$. So, assume that
$v=\langle v_{1},v_{2}\rangle$ and $w=\langle w_{1},w_{2}\rangle$ are both
nonzero, and that $\mathcal{L}_{v}=\mathcal{L}_{w}$. Taking $y=1$ and $z=0$ in
the definition of $\mathcal{L}_{w}$, we see that
$\big{[}\begin{smallmatrix}w_{1}&w_{2}\\\ 0&0\end{smallmatrix}\big{]}\in
L_{w}=L_{v}$. Hence, $w_{1}=\lambda v_{1}$ and $w_{2}=\lambda v_{2}$ for some
nonzero $\lambda\in\mathbb{F}_{q}$.

$(\Leftarrow$) Assume that $v$, $w\in\mathbb{F}_{q}^{2}$ and $w=\lambda v$ for
some nonzero $\lambda\in\mathbb{F}_{q}$. Given $A\in\mathcal{L}_{v}$, we
clearly have $\lambda A\in\mathcal{L}_{w}$. But, $\mathcal{L}_{w}$ is a left
ideal, so $A=\tfrac{1}{\lambda}(\lambda A)\in\mathcal{L}_{w}$. Thus,
$\mathcal{L}_{v}\subseteq\mathcal{L}_{w}$. The proof that
$\mathcal{L}_{w}\subseteq\mathcal{L}_{v}$ is similar.

(3) Note that the left ideals of $M_{2}(\mathbb{F}_{q})$ correspond to
subspaces of $\mathbb{F}_{q}^{2}$. Explicitly, in any left ideal $L$, the rows
of $L$ comprise a subspace of $\mathbb{F}_{q}^{2}$. Conversely, given a
subspace $V$ of $\mathbb{F}_{q}^{2}$, the set of matrices in
$M_{2}(\mathbb{F}_{q})$ whose rows are vectors in $V$ forms a left ideal. In
particular, the minimal left ideals of $M_{2}(\mathbb{F}_{q})$ are in one-to-
one correspondence with the linear subspaces of $\mathbb{F}_{q}^{2}$. There
are $q+1$ such subspaces, namely, $\mathcal{L}_{\langle 0,1\rangle}$ and
$\mathcal{L}_{\langle 1,\lambda\rangle}$ for $\lambda\in\mathbb{F}_{q}$. The
result follows. ∎

Next, we prove some basic properties about $\mathcal{B}$-sets and their
relation to $\mathcal{L}$-modules.

######  Lemma 4.4.

Let $\mathcal{C}=\mathcal{C}((x-a)(x-b))$ be an SQD class and let
$A\in\mathcal{C}$.

  1. (1)

$\mathcal{L}(\\{A\\},a)=\mathcal{L}_{v}$ for some $v\in\\{\langle
0,1\rangle\\}\cup\\{\langle 1,\lambda\rangle\mid\lambda\in\mathbb{F}_{q}\\}$.
In particular, there are $q+1$ possibilities for this $\mathcal{L}$-module.

  2. (2)

$\mathcal{B}(A,a)=\\{B\in\mathcal{C}\mid\mathcal{L}(\\{B\\},a)=\mathcal{L}(\\{A\\},a)\\}$.
Thus, for all $A$, $B\in\mathcal{C}$, $\mathcal{B}(A,a)=\mathcal{B}(B,a)$ if
and only if $\mathcal{L}(\\{A\\},a)=\mathcal{L}(\\{B\\},a)$.

  3. (3)

$\mathcal{B}(A,a)$ is noncore.

  4. (4)

Let $U\in\operatorname{GL_{2}(\mathbb{F}_{q})}2$. Then,
$\mathcal{B}(U^{-1}AU,a)=U^{-1}\mathcal{B}(A,a)U$.

Moreover, each of the above statements holds when $\mathcal{B}(A,a)$ is
replaced with $\mathcal{B}(A,b)$.

###### Proof.

(1) By [24, Lemma 6.3(1)] $\mathcal{L}(\\{A\\},a)$ is nonzero and is a minimal
left ideal of $M_{2}(\mathbb{F}_{q})$. The result now follows from Lemma
4.3(3).

(2) By part (1), there exists a nonzero $v\in\mathbb{F}_{q}^{2}$ such that
$\mathcal{L}(\\{A\\},a)=\mathcal{L}_{v}$. Take $B\in\mathcal{B}(A,a)$. Then
$\mathcal{L}(\\{A,B\\},a)\neq\\{0\\}$ and
$\mathcal{L}(\\{A,B\\},a)\subseteq\mathcal{L}(\\{A\\},a)$ which implies that
$\mathcal{L}(\\{A,B\\},a)=\mathcal{L}_{v}$. Since
$\mathcal{L}(\\{A,B\\},a)\subseteq\mathcal{L}(\\{B\\},a)$ also holds and
$\mathcal{L}(\\{B\\},a)$ is a minimal left ideal, it follows
$\mathcal{L}(\\{B\\},a)=\mathcal{L}_{v}$. Conversely, if $C\in\mathcal{C}$
with $\mathcal{L}(\\{C\\},a)=\mathcal{L}_{v}$, then
$\mathcal{L}(\\{C\\},a)=\mathcal{L}_{v}=\mathcal{L}(\\{A\\},a)$, and all of
these modules are nonzero. Thus, $\mathcal{L}(\\{A,C\\},a)\neq\\{0\\}$ and
$C\in\mathcal{B}(A,a)$.

(3) Let $S=\mathcal{B}(A,a)$ and let $\alpha\in\mathcal{L}(\\{A\\},a)$ be
nonzero. By (2), $\alpha\in\mathcal{L}(\\{B\\},a)$ for all $B\in S$. Thus,
$\alpha(x-a)\in N(S)$ and $S$ is noncore by Lemma 2.1.

(4) Let $B\in U^{-1}\mathcal{B}(A,a)U$. Then, $B=U^{-1}CU$ for some
$C\in\mathcal{B}(A,a)$. By part (2), we have

$\mathcal{L}(\\{A\\},a)=\mathcal{L}(\\{C\\},a)=\mathcal{L}(\\{UBU^{-1}\\},a).$

By [24, Lemma 6.3(2)],
$\mathcal{L}(\\{UBU^{-1}\\},a)=U\mathcal{L}(\\{B\\},a)U^{-1}$. This further
implies that $\mathcal{L}(\\{B\\},a)=\mathcal{L}(\\{U^{-1}AU\\},a)$. Hence,
$B\in\mathcal{B}(U^{-1}AU,a)$ and
$U^{-1}\mathcal{B}(A,a)U\subseteq\mathcal{B}(U^{-1}AU,a)$. The proof of the
reverse inclusion is similar. ∎

The next example demonstrates one way to visualize $\mathcal{B}$-sets in an
SQD class, and how they can be used to count noncore subsets.

######  Example 4.5.

Let $\mathcal{C}=\mathcal{C}(x(x+1))$ in $M_{2}(\mathbb{F}_{2})$. Then,
$\mathcal{C}$ consists of the following six matrices:

$\displaystyle A_{1}$ $\displaystyle=\big{[}\begin{smallmatrix}0&0\\\
0&1\end{smallmatrix}\big{]},\quad A_{2}=\big{[}\begin{smallmatrix}0&1\\\
0&1\end{smallmatrix}\big{]},\quad A_{3}=\big{[}\begin{smallmatrix}0&0\\\
1&1\end{smallmatrix}\big{]},$ $\displaystyle A_{4}$
$\displaystyle=\big{[}\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}\big{]},\quad A_{5}=\big{[}\begin{smallmatrix}1&1\\\
0&0\end{smallmatrix}\big{]},\quad A_{6}=\big{[}\begin{smallmatrix}1&0\\\
1&0\end{smallmatrix}\big{]}.$

Computing $\mathcal{B}(A,0)$ and $\mathcal{B}(A,1)$ as $A$ runs along
$\mathcal{C}$, we find that $|\mathcal{B}(A,0)|=|\mathcal{B}(A,1)|=2$ and
$\mathcal{B}(A,0)\cap\mathcal{B}(A,1)=\\{A\\}$. We can represent this
situation pictorially in Figure 1. In that picture, each oval corresponds to a
$\mathcal{B}$-set, and the associated $\mathcal{L}$-module is shown alongside
the $\mathcal{B}$-set.

$\big{[}\begin{smallmatrix}0&0\\\
0&1\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}0&0\\\
1&1\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}0&1\\\
0&1\end{smallmatrix}\big{]}$ $\mathcal{B}(A_{1},0)$
---
$\mathcal{L}(-,0)=\mathcal{L}_{\langle 1,0\rangle}$
$\mathcal{B}(A_{1},1)$
---
$\mathcal{L}(-,1)=\mathcal{L}_{\langle 0,1\rangle}$
$\big{[}\begin{smallmatrix}0&1\\\
0&1\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}1&0\\\
1&0\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}0&0\\\
0&1\end{smallmatrix}\big{]}$ $\mathcal{B}(A_{2},0)$
---
$\mathcal{L}(-,0)=\mathcal{L}_{\langle 1,1\rangle}$
$\mathcal{B}(A_{2},1)$
---
$\mathcal{L}(-,1)=\mathcal{L}_{\langle 0,1\rangle}$
$\big{[}\begin{smallmatrix}0&0\\\
1&1\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}0&0\\\
0&1\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}1&1\\\
0&0\end{smallmatrix}\big{]}$ $\mathcal{B}(A_{3},0)$
---
$\mathcal{L}(-,0)=\mathcal{L}_{\langle 1,0\rangle}$
$\mathcal{B}(A_{3},1)$
---
$\mathcal{L}(-,1)=\mathcal{L}_{\langle 1,1\rangle}$
$\big{[}\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}1&1\\\
0&0\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}1&0\\\
1&0\end{smallmatrix}\big{]}$ $\mathcal{B}(A_{4},0)$
---
$\mathcal{L}(-,0)=\mathcal{L}_{\langle 0,1\rangle}$
$\mathcal{B}(A_{4},1)$
---
$\mathcal{L}(-,1)=\mathcal{L}_{\langle 1,0\rangle}$
$\big{[}\begin{smallmatrix}1&1\\\
0&0\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}0&0\\\
1&1\end{smallmatrix}\big{]}$ $\mathcal{B}(A_{5},0)$
---
$\mathcal{L}(-,0)=\mathcal{L}_{\langle 0,1\rangle}$
$\mathcal{B}(A_{5},1)$
---
$\mathcal{L}(-,1)=\mathcal{L}_{\langle 1,1\rangle}$
$\big{[}\begin{smallmatrix}1&0\\\
1&0\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}0&1\\\
0&1\end{smallmatrix}\big{]}$$\big{[}\begin{smallmatrix}1&0\\\
0&0\end{smallmatrix}\big{]}$ $\mathcal{B}(A_{6},0)$
---
$\mathcal{L}(-,0)=\mathcal{L}_{\langle 1,1\rangle}$
$\mathcal{B}(A_{6},1)$
---
$\mathcal{L}(-,1)=\mathcal{L}_{\langle 1,0\rangle}$
Figure 1. $\mathcal{B}$-sets for matrices in $\mathcal{C}(x(x+1))\subseteq
M_{2}(\mathbb{F}_{2})$

There is a great deal of symmetry present in this picture. Note that there are
three nonzero $\mathcal{L}$-modules in $M_{2}(\mathbb{F}_{2})$. Each
$\mathcal{L}$-module occurs four times in the Figure 1, twice corresponding to
$\mathcal{B}$-sets for the root 0, and twice corresponding to
$\mathcal{B}$-sets for the root 1. We can also use this picture to identify
and count noncore subsets of $\mathcal{C}$. For instance, if $A$,
$B\in\mathcal{C}$ with $A-B$ singular, then
$B\in\mathcal{B}(A,0)\cup\mathcal{B}(A,1)$. However, if
$B\in\mathcal{B}(A,0)\setminus\\{A\\}$ and
$C\in\mathcal{B}(A,1)\setminus\\{A\\}$, then $B-C$ is invertible. This
suggests that each noncore subset of $\mathcal{C}$ is contained in a
$\mathcal{B}$-set. Moreover, each $\mathcal{B}$-set is noncore by Lemma
4.4(3). There are six unique $\mathcal{B}$-sets—three of the form
$\mathcal{B}(-,0)$ and three of the form $\mathcal{B}(-,1)$—which account for
all of the noncore subsets of $\mathcal{C}$ of size 2. Along with the six
singleton subsets, we see that there are 12 noncore subsets of $\mathcal{C}$.

The behavior seen in Example 4.5 is typical of SQD classes in
$M_{2}(\mathbb{F}_{q})$. Ultimately, we will prove that noncore subsets in an
SQD class are contained in $\mathcal{B}$-sets, and the symmetry among
$\mathcal{B}$-sets can be illustrated as in Figure 1. The next several results
build up the theory required to prove these claims.

######  Lemma 4.6.

Let $\mathcal{C}=\mathcal{C}((x-a)(x-b))$ be an SQD class in
$M_{2}(\mathbb{F}_{q})$.

  1. (1)

For all $A\in\mathcal{C}$, $\mathcal{B}(A,a)\cap\mathcal{B}(A,b)=\\{A\\}$.

  2. (2)

For all $A\in\mathcal{C}$, $|\mathcal{B}(A,a)|=|\mathcal{B}(A,b)|=q$.

  3. (3)

Let $A$, $B\in\mathcal{C}$. If $B-A$ is singular, then
$B\in\mathcal{B}(A,a)\cup\mathcal{B}(A,b)$.

  4. (4)

Let $A\in\mathcal{C}$. If $B\in\mathcal{B}(A,a)\setminus\\{A\\}$ and
$C\in\mathcal{B}(A,b)\setminus\\{A\\}$, then $B-C$ is invertible.

  5. (5)

$\mathcal{C}$ contains $q+1$ distinct $\mathcal{B}$-sets of the form
$\mathcal{B}(-,a)$, which comprise a partition of $\mathcal{C}$. The analogous
result holds for $\mathcal{B}$-sets of the form $\mathcal{B}(-,b)$.

###### Proof.

(1) Let $A\in\mathcal{C}$ and suppose that there exists
$B\in\mathcal{B}(A,a)\cap\mathcal{B}(A,b)$ such that $B\neq A$. Then,
$\mathcal{L}(\\{A,B\\},a)\neq\\{0\\}$ and
$\mathcal{L}(\\{A,B\\},b)\neq\\{0\\}$. This contradicts [24, Lemma 6.3(4)].
Hence, no such $B$ exists.

(2) By Lemma 4.4(4), all of the $\mathcal{B}$-sets $\mathcal{B}(A,a)$ are
conjugate as $A$ runs through $\mathcal{C}$. Thus, we may assume without loss
of generality that $A=\big{[}\begin{smallmatrix}a&0\\\
0&b\end{smallmatrix}\big{]}$. It is straightforward to check that
$\mathcal{L}(\\{A\\},a)=\mathcal{L}_{\langle 1,0\rangle}$ and
$\mathcal{L}(\\{A\\},b)=\mathcal{L}_{\langle 0,1\rangle}$, and so

$\mathcal{B}(A,a)=\left\\{\big{[}\begin{smallmatrix}a&0\\\
c&b\end{smallmatrix}\big{]}\,\,\middle|\,\,c\in\mathbb{F}_{q}\right\\}\text{
and }\mathcal{B}(A,b)=\left\\{\big{[}\begin{smallmatrix}a&c\\\
0&b\end{smallmatrix}\big{]}\,\,\middle|\,\,c\in\mathbb{F}_{q}\right\\}.$ (4.1)

Thus, $|\mathcal{B}(A,a)|=q=|\mathcal{B}(A,b)|$.

(3) As in part (2), we may assume that $A=\big{[}\begin{smallmatrix}a&0\\\
0&b\end{smallmatrix}\big{]}$. Let $B=\big{[}\begin{smallmatrix}t&y\\\
z&w\end{smallmatrix}\big{]}\in\mathcal{C}$ be such that $B-A$ is not
invertible. Since $B\in\mathcal{C}$, we have
$t+w=\operatorname{tr}(B)=\operatorname{tr}(A)=a+b$ and $tw-
yz=\det(B)=\det(A)=ab$. Hence, $w-b=a-t$ and $yz=tw-ab=t(a+b-t)-ab$ hold. A
routine calculation now shows that $\det(B-A)=(t-a)(a-b)$. Since $\mathcal{C}$
is SQD, $a\neq b$. So, in order for $B-A$ to be singular, we must have $t=a$.
This forces $w=b$ and either $y=0$ or $z=0$. From Equation (4.1), we see that
$B\in\mathcal{B}(A,a)\cup\mathcal{B}(A,b)$.

(4) Once again, we may assume that $A=\big{[}\begin{smallmatrix}a&0\\\
0&b\end{smallmatrix}\big{]}$. Given $B\in\mathcal{B}(A,a)\setminus\\{A\\}$ and
$C\in\mathcal{B}(A,a)\setminus\\{A\\}$, by (4.1), we see that
$B-C=\big{[}\begin{smallmatrix}0&c\\\ d&0\end{smallmatrix}\big{]}$ for some
nonzero $c$, $d\in\mathbb{F}_{q}$. Thus, $B-C$ is invertible.

(5) Every matrix $A\in\mathcal{C}$ is contained in the $\mathcal{B}$-set
$\mathcal{B}(A,a)$ which is a set of size $q$ by part (2). For two matrices
$A$, $B\in\mathcal{C}$, it holds that $\mathcal{B}(A,a)=\mathcal{B}(B,a)$ if
and only if $\mathcal{L}(\\{A\\},a)=\mathcal{L}(\\{B\\},a)$ by Lemma 4.4(2).
From Lemma 4.4(1), we know that there are $q+1$ possible choices for
$\mathcal{L}(\\{A\\},a)$. Thus, $\mathcal{C}$ contains $q+1$ distinct
$\mathcal{B}$-sets $\mathcal{B}(-,a)$; note that these sets form a partition
of $\mathcal{C}$, because $|\mathcal{C}|=q^{2}+q$ by Proposition 2.7(4).
Likewise, $\mathcal{C}$ contains $q+1$ distinct $\mathcal{B}$-sets
$\mathcal{B}(-,b)$, which also partition the class. ∎

######  Proposition 4.7.

Let $\mathcal{C}=\mathcal{C}((x-a)(x-b))$ be an SQD class in
$M_{2}(\mathbb{F}_{q})$.

  1. (1)

For all $A\in\mathcal{C}$, if $S\subseteq\mathcal{B}(A,a)$ and
$S\neq\varnothing$, then $S$ is noncore.

  2. (2)

Let $S\subseteq\mathcal{C}$ be noncore. If $A\in S$, then
$S\subseteq\mathcal{B}(A,a)$ or $S\subseteq\mathcal{B}(A,b)$.

  3. (3)

Let $S\subseteq\mathcal{C}$ be nonempty. Then, $S$ is noncore if and only if,
for each $A\in S$, $S\subseteq\mathcal{B}(A,a)$ or
$S\subseteq\mathcal{B}(A,b)$.

  4. (4)

Assume that $S\subseteq\mathcal{C}$ is noncore and $|S|\geq 2$. Then, for each
$A\in S$, either $S\subseteq\mathcal{B}(A,a)$ or $S\subseteq\mathcal{B}(A,b)$,
and these cases are mutually exclusive.

###### Proof.

(1) Fix $A\in\mathcal{C}$ and let $S$ be a nonempty subset of
$\mathcal{B}(A,a)$. Let $\alpha\in\mathcal{L}(\\{A\\},a)$ be nonzero. Then,
for each $B\in S$, $\alpha(B-a)=0$. Thus, the polynomial $\alpha(x-a)$ is in
$N(S)$, and $N(S)$ is noncore by Lemma 2.1.

(2) Let $A\in S$. Since $S$ is noncore, $B-C$ is singular for all $B$, $C\in
S$ by Proposition 2.4(2). In particular, $B-A$ is singular for each $B\in S$.
By Lemma 4.6(3), $S\subseteq\mathcal{B}(A,a)\cup\mathcal{B}(A,b)$. However, by
Lemma 4.6(4), $S$ must be entirely contained in either $\mathcal{B}(A,a)$ or
$\mathcal{B}(A,b)$.

(3) This follows from (1) and (2).

(4) Let $A\in S$ and consider $T=S\setminus\\{A\\}$. If $T$ contains both a
matrix $B\in\mathcal{B}(A,a)$ and a matrix $C\in\mathcal{B}(A,b)$, then $B-C$
is invertible by Lemma 4.6(4). Then, $S$ is core by Proposition 2.4(2), a
contradiction. Note that the assumption $|S|\geq 2$ is necessary here, since
$\mathcal{B}(A,a)\cap\mathcal{B}(A,b)=\\{A\\}$. ∎

######  Theorem 3.

Each SQD class in $M_{2}(\mathbb{F}_{q})$ contains $(q+1)(2^{q+1}-q-2)$
noncore subsets.

###### Proof.

Let $S\subseteq\mathcal{C}$ be noncore. Assume first that $|S|\geq 2$. By
Proposition 4.7(4), $S$ is a subset of either some $\mathcal{B}(-,a)$ or some
$\mathcal{B}(-,b)$, but not both. From Lemma 4.6(2), we know that each
$\mathcal{B}$-set has size $q$, and hence contains $2^{q}-(q+1)$ subsets of
cardinality at least 2. By Lemma 4.6(5), there are $q+1$ $\mathcal{B}$-sets of
the form $\mathcal{B}(-,a)$, and $q+1$ of the form $\mathcal{B}(-,b)$. Thus,
there are $2(q+1)(2^{q}-(q+1))$ possible choices for $S$ when $|S|\geq 2$.

Finally, each singleton subset of $\mathcal{C}$ is noncore, and there are
$q^{2}+q$ such subsets. Thus, in total, the number of noncore subsets of
$\mathcal{C}$ is equal to

$q^{2}+q+2(q+1)(2^{q}-(q+1))=(q+1)(2^{q+1}-q-2).\qed$

As in an SQR class, we can use Proposition 2.4(2) to give an interpretation of
Theorem 3 that is independent of core sets.

######  Corollary 4.8.

Let $m$ be an SQD polynomial. Then, $\mathcal{C}(m)$ contains
$(q+1)(2^{q+1}-q-2)$ subsets $S$ with the property that $A-B$ is singular for
all $A$, $B\in S$.

##  5\. Asymptotic Results

Our results so far allow us to determine the number of purely core subsets in
$M_{2}(\mathbb{F}_{q})$. This still leaves the matter of core sets that are
not purely core. In this section, we show that the number of such core sets is
always small in comparison to the number of purely core sets. Moreover, as
$q\to\infty$, we prove that almost all subsets of $M_{2}(\mathbb{F}_{q})$ are
purely core. We begin by establishing some inequalities related to the
probability that a subset of an SQD class is core.

######  Lemma 5.1.

For all $x\geq 1$, $\Big{(}1-\dfrac{1}{4^{x}}\Big{)}^{-x}<1+\dfrac{1}{2^{x}}$.

###### Proof.

It suffices to prove that $-x\ln(1-\tfrac{1}{4^{x}})<\ln(1+\tfrac{1}{2^{x}})$
for all $x\geq 1$. Applying the Taylor series expansions for $\ln(1-t)$ and
$\ln(1+t)$, we obtain the equivalent inequality

$x\sum_{n=1}^{\infty}\dfrac{1}{n}\Big{(}\dfrac{1}{4^{x}}\Big{)}^{n}<\sum_{n=1}^{\infty}(-1)^{n+1}\dfrac{1}{n}\Big{(}\dfrac{1}{2^{x}}\Big{)}^{n}.$
(5.1)

Note that for a fixed $x$, both series converge because $|\tfrac{1}{4^{x}}|<1$
and $|\tfrac{1}{2^{x}}|<1$. So, to establish (5.1), it is enough to show that
for each odd integer $n\geq 1$,

$x\left(\dfrac{1}{n}\left(\dfrac{1}{4^{x}}\right)^{n}+\dfrac{1}{n+1}\left(\dfrac{1}{4^{x}}\right)^{n+1}\right)<\dfrac{1}{n}\left(\dfrac{1}{2^{x}}\right)^{n}-\dfrac{1}{n+1}\left(\dfrac{1}{2^{x}}\right)^{n+1}.$

Adding $\tfrac{1}{n+1}(\tfrac{1}{2^{x}})^{n+1}$ to both sides of this
inequality and then multiplying by $(4^{x})^{n}$ produces

$x\left(\dfrac{1}{n}+\dfrac{1}{n+1}\left(\dfrac{1}{4^{x}}\right)\right)+\dfrac{1}{n+1}\cdot(2^{x})^{n-1}<\dfrac{1}{n}\cdot(2^{x})^{n}.$
(5.2)

If $n=1$, then (5.2) is satisfied since

$x\left(1+\dfrac{1}{2}\left(\dfrac{1}{4^{x}}\right)\right)+\dfrac{1}{2}\leq\dfrac{9}{8}x+\dfrac{1}{2}<2^{x}.$

If $n\geq 2$, then (5.2) is satisfied since the left-hand side is less than
$\tfrac{1}{n}\left(x(1+\tfrac{1}{4^{x}}\right)+(2^{x})^{n-1})$, and

$x\left(1+\dfrac{1}{4^{x}}\right)\leq\dfrac{5}{4}x<2^{x}.$

This gives

$x\left(1+\dfrac{1}{4^{x}}\right)+(2^{x})^{n-1}\leq\dfrac{5}{4}x+(2^{x})^{n-1}<(2^{x})^{n-1}+(2^{x})^{n-1}=(2^{x})^{n}.$

∎

######  Lemma 5.2.

Let $\rho=1-\dfrac{(q+1)(2^{q+1}-q-2)}{2^{q^{2}+q}}$.

  1. (1)

$\rho$ is the probability that a subset of an SQD class is core.

  2. (2)

For all $q\geq 2$, we have $\rho>1-\dfrac{1}{2^{q^{2}-q}}$.

  3. (3)

Let $q\geq 2$ and let $k=(q^{2}-q)/2$. Then,
$\dfrac{1}{\rho^{k}}-1<\dfrac{1}{2^{k}}$.

###### Proof.

(1) This is a consequence of Proposition 2.7(4) and Theorem 3.

(2) The inequality holds when $q=2$. For $q\geq 3$, we have

$(q+1)(2^{q+1}-q-2)<(q+1)\cdot 2^{q+1}\leq 2^{2q},$

and the result follows.

(3) By part (2), $\rho>1-\dfrac{1}{4^{k}}$ for all $q\geq 2$. Thus, by Lemma
5.1,

$\dfrac{1}{\rho^{k}}-1<\Big{(}1-\dfrac{1}{4^{k}}\Big{)}^{-k}-1<\dfrac{1}{2^{k}},$

as desired. ∎

######  Theorem 4.

Let $k=(q^{2}-q)/2$. Let $c$ be the number of purely core subsets of
$M_{2}(\mathbb{F}_{q})$, and let $c^{\prime}$ be the number of core subsets of
$M_{2}(\mathbb{F}_{q})$ that are not purely core. Then,
$c^{\prime}<\Big{(}\dfrac{1}{2^{k}}\Big{)}c$.

###### Proof.

Let $\mathcal{C}_{0}$ be the union of all the minimal polynomial classes in
$M_{2}(\mathbb{F}_{q})$ that are not SQD, and let $\mathcal{C}_{1}$, …,
$\mathcal{C}_{k}$ be all of the SQD minimal polynomial classes. Assume that
$S\subseteq M_{2}(\mathbb{F}_{q})$ is core, but not purely core. Then,

$S=S_{0}\cup S_{1}\cup\cdots\cup S_{k},$

where $S_{i}=S\cap\mathcal{C}_{i}$ for each $0\leq i\leq k$; $S_{0}$ is core;
and $S_{j}$ is noncore for at least one $j$ such that $1\leq j\leq k$. Let
$\mathcal{D}=\mathcal{C}_{1}\cup\cdots\cup\mathcal{C}_{k}$ and let
$T=S_{1}\cup\cdots\cup S_{k}$.

Let $c_{0}$ be the number of purely core subsets of $\mathcal{C}_{0}$, and let
$d$ be the number of purely core subsets of $\mathcal{D}$. Then, $c=c_{0}d$
and $d/2^{|\mathcal{D}|}=\rho^{k}$, where $\rho$ is the probability that a
subset of a single SQD class is core. Since $S_{0}$ is core and
$\mathcal{C}_{0}$ consists entirely of non-SQD classes, $S_{0}$ is purely core
by Proposition 2.5. So, $c_{0}$ is also equal to the number of possible
choices for $S_{0}$.

Now, the number of possibilities for $T$ depends on the choice of $S_{0}$.
However, by assumption, $T$ is not purely core. Thus, the number of
possibilities for $T$ is always bounded above by $2^{|\mathcal{D}|}-d$. So,
$c^{\prime}\leq c_{0}(2^{|\mathcal{D}|}-d)$. Putting everything together, we
obtain

$\displaystyle\dfrac{c^{\prime}}{c}\leq\dfrac{c_{0}(2^{|\mathcal{D}|}-d)}{c_{0}d}=\dfrac{2^{|\mathcal{D}|}-d}{d}=\dfrac{1}{\rho^{k}}-1.$

The theorem now follows from Lemma 5.2(3). ∎

######  Theorem 5.

  1. (1)

As $q\to\infty$, almost all subsets of $M_{2}(\mathbb{F}_{q})$ are purely
core. That is, as $q\to\infty$,

$\dfrac{\phantom{x}\\#\\{\text{purely core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}\phantom{x}}{\\#\\{\text{subsets of
$M_{2}(\mathbb{F}_{q})$}\\}}\to 1.$

  2. (2)

As $q\to\infty$, almost all core subsets of $M_{2}(\mathbb{F}_{q})$ are purely
core. That is, as $q\to\infty$,

$\dfrac{\phantom{x}\\#\\{\text{purely core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}\phantom{x}}{\\#\\{\text{core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}}\to 1.$

  3. (3)

As $q\to\infty$, almost all subsets of $M_{2}(\mathbb{F}_{q})$ are core. That
is, as $q\to\infty$,

$\dfrac{\phantom{x}\\#\\{\text{core subsets of
$M_{2}(\mathbb{F}_{q})$}\\}\phantom{x}}{\\#\\{\text{subsets of
$M_{2}(\mathbb{F}_{q})$}\\}}\to 1.$

###### Proof.

(1) Let $\mathcal{C}_{1}$, $\mathcal{C}_{2}$, $\mathcal{C}_{2}$, and
$\mathcal{C}_{4}$ be, respectively, the union of all LIN, IRR, SQR, and SQD
classes in $M_{2}(\mathbb{F}_{q})$. For each $1\leq i\leq 4$, let $c_{i}$ be
the number of purely core subsets in $\mathcal{C}_{i}$, and let $c$ be the
total number of purely core subsets of $M_{2}(\mathbb{F}_{q})$. Then,
$c=c_{1}c_{2}c_{3}c_{4}$. From the counts in Table 1,

$\displaystyle c_{1}$ $\displaystyle=2^{q},$ $\displaystyle c_{2}$
$\displaystyle=(2^{q^{2}-q}-(q^{2}-q))^{(q^{2}-q)/2},$ $\displaystyle c_{3}$
$\displaystyle=(2^{q^{2}-1}-(q+1)(2^{q+1}-1))^{q},\text{ and}$ $\displaystyle
c_{4}$ $\displaystyle=(2^{q^{2}+q}-(q+1)(2^{q+1}-q-2))^{(q^{2}-q)/2}.$

Asymptotically,

$c_{2}\sim 2^{(q^{2}-q)(q^{2}-q)/2},\quad c_{3}\sim
2^{q^{3}-q},\quad\text{and}\quad c_{4}\sim 2^{(q^{2}+q)(q^{2}-q)/2}.$

Since
$q+\tfrac{1}{2}(q^{2}-q)^{2}+(q^{3}-q)+\tfrac{1}{2}(q^{2}+q)(q^{2}-q)=q^{4}$,
we see that $c/(2^{q^{4}})\to 1$ as $q\to\infty$. This proves the assertion as
$|M_{2}(\mathbb{F}_{q})|=q^{4}$.

(2) Define $c$ and $c^{\prime}$ as in Theorem 4. Then,
$c/(c+c^{\prime})=1/(1+c^{\prime}/c)$ and this tends to 1 as $q\to\infty$ by
Theorem 4.

(3) This follows from (1). ∎

##  6\. Examples of Core Sets that are Not Purely Core

The matrix ring $M_{2}(\mathbb{F}_{q})$ always contains subsets that are core,
but not purely core. Theorem 4 shows that the proportion of core sets that are
not purely core is always small. Nevertheless, it would be useful to enumerate
such sets. In this section, we present some examples to illustrate that—even
in a case where $q$ is small—this can be a difficult problem.111Additionally,
program code computing the numbers in these examples based on the algorithm
provided in [24] to determine core sets is available on the ArXiv page of this
paper.

By Proposition 2.5, any core subset of $M_{2}(\mathbb{F}_{q})$ that is not
purely core must have a noncore intersection with at least one SQD class. When
$q=2$, there is only one SQD class, so it is feasible to completely count all
of these core sets. As Example 6.3 below shows, even in this simple setting
the calculation involves a rather careful analysis of the situation.

######  Lemma 6.1.

Let $S\subseteq\mathcal{C}((x-a)(x-b))$ be a noncore subset of an SQD class in
$M_{2}(\mathbb{F}_{q})$.

  1. (1)

[24, Lemma 6.3(3)] If $|S|=1$, then both $\mathcal{L}(S,a)$ and
$\mathcal{L}(S,b)$ are nonzero.

  2. (2)

[24, Lemma 6.3(4)] If $|S|\geq 2$, then exactly one of $\mathcal{L}(S,a)$ or
$\mathcal{L}(S,b)$ is zero.

  3. (3)

If $\mathcal{L}(S,a)=\\{0\\}$, then $x-b$ divides each polynomial in $N(S)$.
Likewise, if $\mathcal{L}(S,b)=\\{0\\}$, then $x-a$ divides each polynomial in
$N(S)$.

  4. (4)

$\mathcal{C}((x-a)(x-b))$ contains $(q+1)(2^{q}-q-1)$ subsets $T$ such that
$\mathcal{L}(T,a)=\\{0\\}$ and $\mathcal{L}(T,b)\neq\\{0\\}$. Similarly, there
are $(q+1)(2^{q}-q-1)$ subsets $T$ with $\mathcal{L}(T,a)\neq\\{0\\}$ and
$\mathcal{L}(T,b)=\\{0\\}$.

###### Proof.

(3) By [24, Proposition 6.4(2)], any polynomial $f\in N(S)$ can be written as

$f(x)=g(x)(x-a)(x-b)+\alpha_{1}(x-a)+\alpha_{2}(x-b),$

where $g(x)\in M_{2}(\mathbb{F}_{q})[x]$, $\alpha_{1}\in\mathcal{L}(S,a)$, and
$\alpha_{2}\in\mathcal{L}(S,b)$. Thus, if $\mathcal{L}(S,a)=\\{0\\}$, then
$\alpha_{1}=0$ and $x-b$ divides $f$. Likewise, $x-a$ divides $f$ when
$\mathcal{L}(S,b)=\\{0\\}$.

(4) Let $T\subseteq\mathcal{C}((x-a)(x-b))$ be such that
$\mathcal{L}(T,a)=\\{0\\}$ but $\mathcal{L}(T,b)\neq\\{0\\}$. Then, $T$ is
noncore by Proposition 2.4(3), and by part (1), $|T|\geq 2$. By Proposition
4.7(4), $T\subseteq\mathcal{B}(A,b)$ for some $A\in T$. But, by Lemma 4.6
parts (2) and (5), $|\mathcal{B}(A,b)|=q$ and there are $q+1$ possibilities
for $\mathcal{B}(A,b)$. Since $T$ cannot be the empty set or a singleton set,
there are $(q+1)(2^{q}-q-1)$ possibilities for $T$. ∎

Throughout the remainder of this section, let $\phi_{S}$ denote the least
common multiple of all polynomials which occur as minimal polynomial of one of
the matrices in $S$. Recall the following facts mentioned at the start of
Section 2.

######  Fact 6.2.

Let $S\subseteq M_{2}(\mathbb{F}_{q})$. The following are equivalent:

  1. (1)

$S$ is core.

  2. (2)

$N(S)$ is generated (as a two-sided ideal) by $\phi_{S}$.

  3. (3)

$N(S)$ does not contain a polynomials of degree less than the degree of
$\phi_{S}$.

  4. (4)

If $f$ is the minimal polynomial of a matrix in $S$, then $f$ divides each
polynomial in $N(S)$.

######  Example 6.3.

We compute the number of core subsets of $M_{2}(\mathbb{F}_{2})$ that are not
purely core. Since we already know how to enumerate purely core subsets, this
allows us to give an exact count of the number of core subsets of
$M_{2}(\mathbb{F}_{2})$. Table 2 lists all of the minimal polynomial classes
in $M_{2}(\mathbb{F}_{2})$, along with the number of core and noncore subsets
in each class.

polynomial |  size of class |  # core subsets in class |  # noncore subsets in class
---|---|---|---
$x$ |  1 |  2 |  0
$x+1$ |  1 |  2 |  0
$x^{2}+x+1$ |  2 |  2 |  2
$x^{2}$ |  3 |  5 |  3
$(x+1)^{2}$ |  3 |  5 |  3
$x(x+1)$ |  6 |  52 |  12
Table 2. Minimal polynomial classes in $M_{2}(\mathbb{F}_{2})$

Assume that $S\subseteq M_{2}(\mathbb{F}_{2})$ is core, but is not purely
core. Let $\mathcal{C}_{0}$ be the union of all the non-SQD minimal polynomial
classes in $M_{2}(\mathbb{F}_{2})$. By Proposition 2.5, we can write
$S=S_{0}\cup T$, where $S_{0}\subseteq\mathcal{C}_{0}$ is nonempty and core,
and $T\subseteq\mathcal{C}(x(x+1))$ is noncore. According to Fact 6.2,
$N(S_{0})$ is a principal two-sided ideal of $M_{2}(\mathbb{F}_{2})[x]$. Let
$\phi_{0}\in\mathbb{F}_{q}[x]$ be the monic generator of $N(S_{0})$. We first
argue that either $x\mid\phi_{0}$ or $(x+1)\mid\phi_{0}$. Suppose that neither
$x$ nor $x+1$ divides $\phi_{0}$. Then, $\phi_{0}(x)=x^{2}+x+1$ and
$\phi_{S}(x)=x(x+1)(x^{2}+x+1)$. Since $T$ is noncore, there exists a linear
polynomial $f\in N(T)$, and $f\cdot\phi_{0}$ is an element of $N(S)$ of degree
less than $\deg\phi_{S}$. This contradicts the fact that $S$ is core, see Fact
6.2.

Thus, at least one of $x$ or $x+1$ divides $\phi_{0}$. From here, we will
break the problem into three cases, depending on which factors of $x(x+1)$
divide $\phi_{0}$.

Case 1: $x\mid\phi_{0}$, but $(x+1)\nmid\phi_{0}$
In this case,
$S_{0}\cap\big{(}\mathcal{C}(x+1)\cup\mathcal{C}((x+1)^{2})\big{)}=\varnothing$.
Indeed, if this intersection were core but nonempty, then $x+1$ would divide
$\phi_{0}$ by Fact 6.2; and if the intersection were noncore, then $S_{0}$
would be noncore by Proposition 2.5. Similar reasoning shows that
$S_{0}\cap\big{(}\mathcal{C}(x)\cup\mathcal{C}(x^{2})\big{)}$ is core and
nonempty, and $S_{0}\cap\mathcal{C}(x^{2}+x+1)$ is core (but may be empty).
Thus, the number of possibilities for $S_{0}$ is $(2\cdot 5-1)\cdot 2=18$.

Note that $\phi_{S}=\phi_{0}\cdot(x+1)$. Since $T$ is noncore at least one of
$\mathcal{L}(T,0)$ or $\mathcal{L}(T,1)$ is nonzero according to Proposition
2.4(3). Suppose that $\mathcal{L}(T,0)\neq\\{0\\}$. Then, since $x$ divides
$\phi_{0}$, we see that $\alpha\phi_{0}\in N(S)$ for any nonzero
$\alpha\in\mathcal{L}(T,0)$, which is a contradiction to $S$ being core, cf.
Fact 6.2. So, $T$ is such that $\mathcal{L}(T,0)=\\{0\\}$ and
$\mathcal{L}(T,1)\neq\\{0\\}$. By Lemma 6.1(4), there are 3 possibilities for
$T$. Hence, there are $54=18\cdot 3$ possibilities for $S$ in Case 1.

Case 2: $x\nmid\phi_{0}$, but $(x+1)\mid\phi_{0}$
Proceeding as in Case 1, we see that there are 54 choices for $S$ in this
case.

Case 3: $x\mid\phi_{0}$ and $(x+1)\mid\phi_{0}$
This time, $S_{0}\cap\big{(}\mathcal{C}(x)\cup\mathcal{C}(x^{2})\big{)}$ must
be core and nonempty;
$S_{0}\cap\big{(}\mathcal{C}(x+1)\cup\mathcal{C}((x+1)^{2})\big{)}$ must be
core and nonempty; and $S_{0}\cap\mathcal{C}(x^{2}+x+1)$ is core (but may be
empty). So, there are $9\cdot 9\cdot 2=162$ possibilities for $S_{0}$. Since
$x(x+1)$ divides $\phi_{0}$, each element of $T$ is killed by $\phi_{0}$.
Thus, $T$ can be any noncore subset of $\mathcal{C}(x(x+1))$, of which there
are 12. Hence, in this case there are $1944=162\cdot 12$ choices for $S$.

Combining these three cases, we see that there are $54+54+1944=2052$ core
subsets of $M_{2}(\mathbb{F}_{2})$ that are not purely core. Since there are
$2^{3}\cdot 5^{2}\cdot 52=10400$ purely core subsets, we conclude that
$M_{2}(\mathbb{F}_{2})$ contains exactly 12452 core subsets.

In the next two examples, we consider what happens when more than one SQD
class is involved in the construction of core sets that are not purely core.
For situations in which multiple SQD classes are present, we have found it
useful to organize the available information by using graphs. Given
$S\subseteq M_{2}(\mathbb{F}_{q})$, let $T$ be the collection of all matrices
in $S$ whose minimal polynomial is SQD, and let $S_{0}=S\setminus T$. We know
that $S$ is noncore if $S_{0}$ is noncore (Proposition 2.5). If this is not
the case, then form a graph where each vertex corresponds to a root of
$\phi_{T}$, and an edge joins two vertices $a$ and $b$ if and only if
$S\cap\mathcal{C}((x-a)(x-b))$ is nonempty. For instance, if $\phi_{T}$ has
roots $a_{1}$, $a_{2}$, and $a_{3}$, then the graph might be

$a_{1}$$a_{2}$$a_{3}$$T_{1}$$T_{2}$or$a_{1}$$a_{2}$$a_{3}$$T_{1}$$T_{2}$or$a_{1}$$a_{2}$$a_{3}$$T_{1}$$T_{2}$$T_{3}$

among other possibilities. Each edge $T_{k}$ with endpoints $a_{i}$ and
$a_{j}$ represents the nonempty set $S\cap\mathcal{C}((x-a_{i})(x-a_{j}))$. In
one of these graphs, we will shade the vertex corresponding to the root $a$ if
we know that $x-a$ divides every polynomial in $N(S)$. If each vertex in the
graph is shaded, then $S$ is core by Fact 6.2.

The presence of $\mathcal{L}$-modules that equal $\\{0\\}$ can indicate when
to shade a vertex. Suppose $T_{k}\subseteq\mathcal{C}((x-a_{i})(x-a_{j}))$
corresponds to the edge joining vertices $a_{i}$ and $a_{j}$. By Lemma 6.1(3),
if $\mathcal{L}(T_{k},a_{i})=\\{0\\}$, then we shade vertex $a_{j}$, and if
$\mathcal{L}(T_{k},a_{j})=\\{0\\}$, then we shade vertex $a_{i}$. By
Proposition 2.4(3), if $T_{k}$ is core, then we shade both vertices.

######  Example 6.4.

Let $\mathcal{C}=\mathcal{C}(x(x-1))\cup\mathcal{C}((x-1)(x-2))$ in
$M_{2}(\mathbb{F}_{3})$. We count the number of cores subsets of
$\mathcal{C}$. Using Table 1, we calculate that each of $\mathcal{C}(x(x-1))$
and $\mathcal{C}((x-1)(x-2))$ contain $2^{12}-44=4052$ core subsets. Hence,
$\mathcal{C}$ contains $4052^{2}$ purely core subsets.

Now, let $S\subseteq\mathcal{C}$ be core, but not purely core. Then,
$S=T_{1}\cup T_{2}$, where $T_{1}\subseteq\mathcal{C}(x(x-1))$,
$T_{2}\subseteq\mathcal{C}((x-1)(x-2))$, and at least one of $T_{1}$ or
$T_{2}$ is noncore. We will consider three cases, depending on which of
$T_{1}$ or $T_{2}$ (or both) is noncore. Throughout, note that
$\phi_{S}(x)=x(x-1)(x-2)$, and $N(S)$ contains no polynomial of smaller
degree, cf. Fact 6.2.

Case 1: $T_{1}$ is core, but $T_{2}$ is noncore
Since $T_{1}\cup T_{2}$ is core, $T_{1}$ has to be nonempty. The corresponding
graph is

012$T_{1}$$T_{2}$

where both vertex 0 and 1 are shaded because $T_{1}$ is assumed to be core. We
can shade vertex $2$ if $\mathcal{L}(T_{2},1)=\\{0\\}$. However, if
$\mathcal{L}(T_{2},1)\neq\\{0\\}$, then $\alpha x(x-1)\in N(S)$ for each
nonzero $\alpha\in\mathcal{L}(T_{2},1)$. Thus, $S$ is core if and only if
$\mathcal{L}(T_{2},1)=\\{0\\}$. By Lemma 6.1(4), there are $16$ possibilities
for $T_{2}$. Thus, there are $4051\cdot 16$ possibilities for $S$ in this
case.

Case 2: $T_{1}$ is noncore, but $T_{2}$ is core
This time, the corresponding graph is

012$T_{1}$$T_{2}$

Proceeding as in Case 1, we find that there are $4051\cdot 16$ possibilities
for $S$.

Case 3: both $T_{1}$ and $T_{2}$ are noncore
Here, the graph is

012$T_{1}$$T_{2}$

With the argument used in Case 1, in order to shade both vertices 0 and 2, we
need $\mathcal{L}(T_{1},1)=\\{0\\}$ and $\mathcal{L}(T_{2},1)=\\{0\\}$, which
produces the graph

012$T_{1}$$T_{2}$

Now, since both $T_{1}$ and $T_{2}$ are noncore, both $\mathcal{L}(T_{1},0)$
and $\mathcal{L}(T_{2},2)$ are nonzero (Proposition 2.4(3)). In this
situation, [24, Theorem 6.6] shows that $S$ is core if and only if
$\mathcal{L}(T_{1},0)\neq\mathcal{L}(T_{2},2)$. By Lemma 4.4(1), there are 4
choices for each $\mathcal{L}$-module, and hence $4^{2}-4=12$ ways to choose
$\mathcal{L}(T_{1},0)$ and $\mathcal{L}(T_{2},2)$ so that they are not equal.
Once $\mathcal{L}(T_{1},0)$ has been specified, there are $2^{3}-(3+1)=4$
choices for $T_{1}$, because $T_{1}$ must be a subset of some
$\mathcal{B}(-,0)$ of size at least 2 (Lemma 6.1(1)). Likewise, there are 4
choices for $T_{2}$. In summary, there are $12\cdot 4^{2}$ possibilities for
$S$ in Case 3.

We conclude that $\mathcal{C}$ contains $4052^{2}$ purely core and $2\cdot
4051\cdot 16+12\cdot 4^{2}$ core subsets that are not purely core.

In our last example, we examine the effect of mixing an SQR class with two SQD
classes.

######  Example 6.5.

Let
$\mathcal{C}=\mathcal{C}(x^{2})\cup\mathcal{C}(x(x-1))\cup\mathcal{C}((x-1)(x-2))$
in $M_{2}(\mathbb{F}_{3})$. We count the number of core subsets of
$\mathcal{C}$. Via Table 1, $\mathcal{C}(x^{2})$ contains $2^{8}-12=244$ core
subsets, and each SQD class contains $4052$ core subsets (cf. Example 6.4).
So, $\mathcal{C}$ contains $244\cdot 4052^{2}$ purely core subsets.

From here, let $S\subseteq\mathcal{C}$ be core, but not purely core. Then,
$S=S_{0}\cup T_{1}\cup T_{2}$, where $S_{0}\subseteq\mathcal{C}(x^{2})$ is
core, $T_{1}\subseteq\mathcal{C}(x(x-1))$, and
$T_{2}\subseteq\mathcal{C}((x-1)(x-2))$ (Proposition 2.4(3)). If
$S_{0}=\varnothing$, then $T_{1}\cup T_{2}$ is core, but not purely core. From
Example 6.4, we know that there are $2\cdot 4051\cdot 16+12\cdot 4^{2}$
choices for $S$ when $S_{0}=\varnothing$.

For the remainder of the example, we will assume that $S_{0}$ is nonempty,
which gives 243 possibilities for $S_{0}$. Moreover, at least one of $T_{1}$
or $T_{2}$ must be noncore. We have $\phi_{S}(x)=x^{2}(x-1)(x-2)$, and since
$S_{0}$ is core, we know that $x^{2}$ divides each polynomial in $N(S)$ (cf.
Fact 6.2). As in Example 6.4, we will consider cases depending on $T_{1}$ and
$T_{2}$, and will draw graphs corresponding to each case. Because $x^{2}$
divides every polynomial in $N(S)$, vertex 0 will be shaded in each graph.

Case 1: $T_{1}$ is core, but $T_{2}$ is noncore
We must have $T_{1}\neq\varnothing$, since otherwise $x^{2}\cdot f\in N(S)$
for any $f\in N(T_{2})$ of degree 1, and $x^{2}\cdot f$ has degree less than
$\phi_{S}$ (cf. Fact 6.2). For this case, the graph is

012$T_{1}$$T_{2}$

Analogous to the argument in Example 6.4 Case 1, in order to shade vertex 2,
we need $\mathcal{L}(T_{2},1)=\\{0\\}$, and then
$\mathcal{L}(T_{2},2)\neq\\{0\\}$ because $T_{2}$ is noncore (Proposition
2.4(3)). From Lemma 6.1(4), there are $16$ possibilities for $T_{2}$. Hence,
there are $243\cdot 4051\cdot 16$ choices for $S$.

Case 2: $T_{1}$ is noncore, but $T_{2}$ is core
If $T_{2}=\varnothing$, then the graph is

01$T_{1}$

Again, to shade vertex 1, we need $\mathcal{L}(T_{1},0)=\\{0\\}$. Using
Proposition 2.4(3) and Lemma 6.1(4), when $T_{2}=\varnothing$ there are 16
choices for $T_{1}$.

Assume now that $T_{2}\neq\varnothing$. Graphically, we have

012$T_{1}$$T_{2}$

This means that $T_{1}$ could be any noncore subset of $\mathcal{C}(x(x-1))$,
and $S$ will still be core. Thus, if $T_{2}\neq\varnothing$, then there are
$44$ choices for $T_{1}$ and $4051$ choices for $T_{2}$ (see Table 1). In
total, Case 2 produces $243\cdot 16+243\cdot 44\cdot 4051$ possibilities for
$S$.

Case 3: both $T_{1}$ and $T_{2}$ are noncore
For this case, the initial graph is

012$T_{1}$$T_{2}$

In order to shade vertex 2, we need $\mathcal{L}(T_{2},1)=\\{0\\}$, which
forces $\mathcal{L}(T_{2},2)\neq\\{0\\}$ by Proposition 2.4(3). The graph
becomes

012$T_{1}$$T_{2}$

There are now two possible ways that vertex 1 could be shaded. By [24, Theorem
6.6], this will occur if and only
$\mathcal{L}(T_{1},0)\cap\mathcal{L}(T_{2},2)$ is zero. It could be that
$\mathcal{L}(T_{1},0)=\\{0\\}$, which leads to
$\mathcal{L}(T_{1},1)\neq\\{0\\}$ by Proposition 2.4(3), yielding 16 choices
each for $T_{1}$ and $T_{2}$ by Lemma 6.1(4), and $243\cdot 16^{2}$ choices
for $S$. Otherwise, $\mathcal{L}(T_{1},0)$ is nonzero but not equal to
$\mathcal{L}(T_{2},2)$. This situation is similar to Case 3 of Example 6.4.
There are 12 ways to select the $\mathcal{L}$-modules so that they are nonzero
and not equal. Once $\mathcal{L}(T_{2},2)$ is fixed, there are $2^{3}-(3+1)=4$
choices for $T_{2}$, since $T_{2}$ is contained in some $\mathcal{B}(-,2)$ and
$|T_{2}|\geq 2$. The set $T_{1}$ is likewise contained in some
$\mathcal{B}(-,0)$, but $T_{1}$ could be a singleton set. Hence, there are
$2^{3}-1=7$ possibilities for $T_{1}$. In total, Case 3 leads to $243\cdot
16^{2}+243\cdot 12\cdot 7\cdot 4$ choices for $S$.

Combining all of our work in Example 6.5, we see that $\mathcal{C}$ contains
$244\cdot 4052^{2}$ purely core and

$243\cdot(4051\cdot 16+16+44\cdot 4051+16^{2}+12\cdot 7\cdot 4)$

core but not purely core subsets.

As $q$ grows, the number of available SQD classes also grows, and the
potential interactions among SQD classes and non-SQD classes become
increasingly complicated. The examples above demonstrate that enumerating core
sets that are not purely core is feasible in particular situations, but
producing an exact formula for the number of such sets is difficult.
Nevertheless, we feel that the techniques and perspectives used in these
examples could be applicable for the study of core sets and null ideals over
$M_{n}(\mathbb{F}_{q})$ with $n\geq 3$, or over other rings or algebras.

## References

  * [1] S. Akbari, M. Aryapoor, and M. Jamaali, _Chromatic number and clique number of subgraphs of regular graph of matrix algebras_, Linear Algebra Appl. 436 (2012), no. 7, 2419–2424. MR 2890002
  * [2] S. Akbari, M. Jamaali, and S. A. Seyed Fakhari, _The clique numbers of regular graphs of matrix algebras are finite_, Linear Algebra Appl. 431 (2009), no. 10, 1715–1718. MR 2562416
  * [3] William C. Brown, _Null ideals and spanning ranks of matrices_, Comm. Algebra 26 (1998), no. 8, 2401–2417. MR 1627925
  * [4] by same author, _Null ideals and spanning ranks of matrices. II_, Comm. Algebra 27 (1999), no. 12, 6051–6067. MR 1726293
  * [5] by same author, _Null ideals of matrices_, Comm. Algebra 33 (2005), no. 12, 4491–4504. MR 2188324
  * [6] Paul-Jean Cahen and Jean-Luc Chabert, _Integer-valued polynomials_, Mathematical Surveys and Monographs, vol. 48, American Mathematical Society, Providence, RI, 1997. MR 1421321
  * [7] by same author, _What you should know about integer-valued polynomials_, Amer. Math. Monthly 123 (2016), no. 4, 311–337. MR 3493376
  * [8] S. Evrard, Y. Fares, and K. Johnson, _Integer valued polynomials on lower triangular integer matrices_, Monatsh. Math. 170 (2013), no. 2, 147–160. MR 3041736
  * [9] S. Evrard and K. Johnson, _The ring of integer valued polynomials on $2\times 2$ matrices and its integral closure_, J. Algebra 441 (2015), 660–677. MR 3391941
  * [10] Sophie Frisch, _Polynomial functions on upper triangular matrix algebras_, Monatsh. Math. 184 (2017), no. 2, 201–215. MR 3696109
  * [11] Clemens Heuberger and Roswitha Rissner, _Computing $J$-ideals of a matrix over a principal ideal domain_, Linear Algebra Appl. 527 (2017), 12–31. MR 3647467
  * [12] Roger A. Horn and Charles R. Johnson, _Topics in matrix analysis_ , Cambridge University Press, Cambridge, 1991.
  * [13] Seung Gyu Hyun, Vincent Neiger, and Éric Schost, _Algorithms for linearly recurrent sequences of truncated polynomials_, ISSAC ’21—Proceedings of the 2021 International Symposium on Symbolic and Algebraic Computation, ACM, New York, [2021] ©2021, pp. 201–208. MR 4398785
  * [14] T. Y. Lam, _A first course in noncommutative rings_, second ed., Graduate Texts in Mathematics, vol. 131, Springer-Verlag, New York, 2001. MR 1838439
  * [15] A. R. Naghipour, M. R. Rismanchian, and J. Sedighi Hafshejani, _Some results on the integer-valued polynomials over matrix rings_, Comm. Algebra 45 (2017), no. 4, 1675–1686. MR 3576685
  * [16] Bogdan Nica, _On the independence number of regular graphs of matrix rings_, Linear Algebra Appl. 681 (2024), 89–96. MR 4665007
  * [17] Roswitha Rissner, _Null ideals of matrices over residue class rings of principal ideal domains_, Linear Algebra Appl. 494 (2016), 44–69. MR 3455685
  * [18] J. Sedighi Hafshejani, A. R. Naghipour, and M. R. Rismanchian, _Integer-valued polynomials over block matrix algebras_, J. Algebra Appl. 19 (2020), no. 3, 2050053, 17. MR 4082437
  * [19] J. Sedighi Hafshejani, A. R. Naghipour, and A. Sakzad, _Integer-valued polynomials over subsets of matrix rings_, Comm. Algebra 47 (2019), no. 3, 1077–1090. MR 3938540
  * [20] Eric Swartz and Nicholas J. Werner, _Null ideals of sets of 3 × 3 similar matrices with irreducible characteristic polynomial_, Linear and Multilinear Algebra 0 (2023), no. 0, 1–23.
  * [21] István Tomon, _On the chromatic number of regular graphs of matrix algebras_, Linear Algebra Appl. 475 (2015), 154–162. MR 3325225
  * [22] Nicholas J. Werner, _Integer-valued polynomials over matrix rings_, Comm. Algebra 40 (2012), no. 12, 4717–4726. MR 2989677
  * [23] by same author, _Integer-valued polynomials on algebras: A survey of recent results and open questions_, Rings, Polynomials, and Modules (Marco Fontana, Sophie Frisch, Sarah Glaz, Francesca Tartarone, and Paolo Zanardo, eds.), Springer International Publishing, Cham, 2017, pp. 353–375.
  * [24] by same author, _Null ideals of subsets of matrix rings over fields_, Linear Algebra Appl. 642 (2022), 50–72. MR 4381683