# Reduced Power Graphs of $PGL_{3}(\mathbb{F}_{q})$

Yilong Yang

###### Abstract

Given a group $G$, let us connect two non-identity elements by an edge if and
only if one is a power of another. This gives a graph structure on $G$ minus
identity, called the reduced power graph.

In this paper, we shall find the exact number of connected components and the
exact diameter of each component for the reduced power graphs of
$PGL_{3}(\mathbb{F}_{q})$ for all prime power $q$.

##  1 Introduction

Given a group $G$, the _reduced power graph_ of $G$ has all non-identity
elements of $G$ as vertices, and two distinct vertices are connected by an
edge if and only if one is a power of the other. One interesting aspect of the
reduced power graph is its connectivity. In particular, Akbari and Ashrafi
proposed the following conjecture in 2015.

######  Conjectures 1.1 (Akbari and Ashrafi,[1]).

The reduced power graph of a non-abelian simple group $G$ is connected only if
$G$ is isomorphic to some alternating group $A_{n}$.

In a previous work [2], we showed that the conjecture above is false, and have
provided a description about the connected components of the reduced power
graphs of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$ and an upper bound for these
components. In this paper, we shall find the precise diameter bounds when
$n=3$. In particular, we have the following result:

######  Theorem 1.2.

Let $p$ be the characteristic of a finite field $\mathbb{F}_{q}$. The reduced
power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$ must fall into one of the
following cases.

  1. 1.

The reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{2})$ has $51$
components, each with diameter $1$.

  2. 2.

The reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{3})$ has $321$
components. One has diameter $11$, and $312$ components have diameter $1$. and
$8$ components have diameter $2$.

  3. 3.

If $q\neq 2$ is even and $q-1$ is prime, then the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has
$1+q^{3}(q^{3}-1)(q+1)(q-3)+\frac{1}{3}q^{3}(q^{2}-1)(q-1)$ components. One
has diameter $13$, $q^{3}(q^{3}-1)(q+1)(q-3)$ components has diameter $1$, and
the other $\frac{1}{3}q^{3}(q^{2}-1)(q-1)$ components have diameter $1$ if
$q=8$, and diameter $2$ otherwise.

  4. 4.

If $q\neq 2$ is even and $q-1$ is not prime, then the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has $1+\frac{1}{3}q^{3}(q^{2}-1)(q-1)$
components. One has diameter $10$, and the other
$\frac{1}{3}q^{3}(q^{2}-1)(q-1)$ components have diameter $2$.

  5. 5.

If $q\neq 3$ is odd and $q-1$ is a prime power (i.e., when $q=9$ or $q$ is a
Fermat prime), then the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has
$1+\frac{1}{p-1}(q^{3}-1)(q^{3}-q)+\frac{1}{3}q^{3}(q^{2}-1)(q-1)$ components.
One has diameter $12$, $\frac{1}{p-1}(q^{3}-1)(q^{3}-q)$ components has
diameter $1$, and the other $\frac{1}{3}q^{3}(q^{2}-1)(q-1)$ components have
diameter $1$ if $q^{2}+q+1$ is a prime, and diameter $2$ otherwise.

  6. 6.

If $q\neq 3$ is odd and $q-1$ is not a prime power, then the reduced power
graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has
$1+\frac{1}{p-1}(q^{3}-1)(q^{3}-q)+\frac{1}{3}q^{3}(q^{2}-1)(q-1)$ components.
One has diameter $8$, all other components have diameter $2$.

##  2 Preliminary

###  2.1 Projectively Reduced Power Graph and Pivot Component

In this paper, we shall study a special graph on $\mathrm{GL}_{n}(q)$, which
has the reduced power graph of $\mathrm{PGL}_{n}(q)$ as a quotient graph.

######  Definition 2.1.

Given a group $G$, let $Z$ be its center. Then the projectively reduced power
graph of $G$ is obtained from the reduced power graph of $G$ by deleting
vertices in $Z$.

######  Proposition 2.2.

Given a group $G$, let $Z$ be its center. Let $\Gamma$ be projective reduced
power graph of $G$, and let $\Gamma^{\prime}$ be the reduced power graph of
$G/Z$. If $\Gamma$ is connected, then $\Gamma^{\prime}$ is connected with the
same or less diameter.

###### Proof.

$\Gamma^{\prime}$ is a quotient graph of $\Gamma$. ∎

When $q>2$ is a prime power, we say a matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ is a _pivot matrix_ if it is
diagonalizable over $\mathbb{F}_{q}$ with exactly two distinct eigenvalues. In
the projectively reduced power graph of $G$, the connected component
containing a pivot matrix is called a _pivot component_. We also call the
corresponding connected component in $\mathrm{PGL}_{3}(\mathbb{F}_{q})$ a
_pivot component_ as well. In the previous work [2], we have shown that for
$q\neq 2$, all pivot matrices are connected in the projectively reduced power
graph of $\mathrm{GL}_{3}(\mathbb{F}_{q})$. So in particular, when $q\neq 2$,
the pivot component of $\mathrm{GL}_{3}(\mathbb{F}_{q})$ or
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ is unique. Furthermore, the precise
diameter of all non-pivot components of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$ is
already obtained in [2]. So we only need to figure out the precise diameter of
the pivot component.

###  2.2 Obstructions and Connections

We now list some important results from [2] about obstructions to the
connectivity of the reduced power graph, and about certain connection results.
We say a matrix $A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ is a _Jordan pivot
matrix_ if $A-I$ has rank one and $(A-I)^{2}=0$.

######  Proposition 2.3 (Diagonalizable obstruction).

Suppose $q>2$ is a power of $2$ with $q-1$ prime, and $2\leq n<q$. Let $A$ be
an $n\times n$ diagonalizable matrix with $n$ distinct non-zero eigenvalues
over $\mathbb{F}_{q}$. Then the image of $A$ in the reduced power graph of
$\mathrm{PGL}_{n}(q)$ is trapped in a connected component with $q-2$ vertices
and diameter $1$, made of images of non-identity powers of $A$.

######  Proposition 2.4 (Irredicible obstruction).

Let $n$ be prime and $A$ be a matrix over $\mathbb{F}_{q}$ whose
characteristic polynomial is irreducible. Then the image of $A$ in the reduced
power graph of $\mathrm{PGL}_{n}(q)$ is trapped in a connected component with
$(q^{n}-q)/(q-1)$ vertices, made of images of polynomials of $A$ that are not
multiples of identity. The diameter of this component is at most $2$.

######  Proposition 2.5 (Jordan-type obstruction).

Consider a finite field $\mathbb{F}_{q}$ with characteristic $p$. If $2\leq
n\leq p$, let $A$ be any matrix over $\mathbb{F}_{q}$ similar to the $n\times
n$ matrix $\begin{bmatrix}\lambda&1&&\\\ &\ddots&\ddots&\\\ &&\ddots&1\\\
&&&\lambda\end{bmatrix}$ for some $\lambda\in\mathbb{F}_{q}^{*}$. Then the
image of $A$ in the reduced power graph of $\mathrm{PGL}_{n}(q)$ is trapped in
a connected component with $p-1$ vertices and diameter $1$, made of images of
powers of $A$ that are not multiples of identity.

######  Proposition 2.6 (Quasi-diagonalizable obstruction when $q=2$).

Suppose we have a prime $p_{0}=2^{p_{1}}-1$ (i.e., Mersenne prime) for some
positive integer $p_{1}$. Suppose $n\leq p_{0}$. Let $A$ be an $n\times n$
non-identity matrix such that $A^{p_{0}}=I$, and its minimal polynomial equal
to its characteristic polynomial. Then the $A$ in the reduced power graph of
$\mathrm{GL}_{n}(2)$ is trapped in a connected component with $p_{0}-1$
vertices and diameter $1$, made of non-identity powers of $A$.

Note that in this case, $p_{1}$ must be a prime factor of $n$ or $n-1$.

######  Proposition 2.7 (Extra irredicible obstruction when $q=2$).

Let $n-1$ be prime and $A$ be an $n\times n$ matrix over $\mathbb{F}_{2}$
whose characteristic polynomial has an irreducible factor of degree $n-1$.
Then the image of $A$ in the reduced power graph of $\mathrm{PGL}_{n}(2)$ is
trapped in a connected component with $2^{n-1}-2$ vertices, made of non-
identity powers of a matrix $C\in\mathrm{PGL}_{n}(2)$. The diameter of this
component is at most $2$.

######  Proposition 2.8.

For $q\neq 2$ and $n=3$, any two pivot matrices in the projectively reduced
power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ will have distance at most
$8$.

######  Proposition 2.9.

For $q\neq 2$ and $n\geq 3$ or for $q=2$ and $n\geq 4$, any two Jordan pivot
matrices in the projectively reduced power graph of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ will have distance at most $8$.

###  2.3 Other useful results

We now list some important results that will be useful here. Proofs and
references will be found in [2].

######  Lemma 2.10.

If $q,q-1$ are both prime powers, then either $q$ is Fermat prime, or $q-1$ is
a Mersenne prime, or $q=9$.

######  Corollary 2.11.

Let $q$ be a power of a prime $p$, and let $n\geq 1$. Let $p_{0}$ be a prime
factor of $q-1$. If any $n\times n$ matrix $A$ over $\mathbb{F}_{q}$ has
multiplicative order coprime to $p_{0}$, then $A$ has a $p_{0}$-th root whose
multiplicative order is a multiple of $p_{0}$.

######  Lemma 2.12.

Let $q$ be a power of a prime $p$, and let $n\geq 2$. If a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ has
projective order coprime to $p$, then its generalized Jordan canonical form is
a block diagonal matrix where each diagonal block is either $1\times 1$ or
some companion matrix of an irreducible polynomial.

######  Lemma 2.13.

Suppose the characteristic polynomial of a matrix
$C\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ is irreducible, and the multiplicative
order of $C$ is $k$. For any positive integer $t$, the minimal polynomial of
$C^{t}$ is irreducible. For any factor $t$ of $k$, if $\frac{k}{t}$ is a
factor of $q^{m}-1$, then the minimal polynomial of $C^{t}$ is irreducible
with degree at most $m$.

######  Corollary 2.14.

Suppose the characteristic polynomial of a matrix
$C\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ is irreducible, and the multiplicative
order of $C$ is $k$. For any factor $t$ of $k$, $\frac{k}{t}$ is a factor of
$q-1$ if and only if $C^{t}$ is a multiple of identity.

##  3 Classification and Connections

By standard enumeration, here is a list of possible types of generalized
Jordan canonical forms for matrices in $\mathrm{GL}_{3}(\mathbb{F}_{q})$.

  1. 1.

(Multiples of identity) $A$ is a multiplies of identity. These are excluded in
the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$.

  2. 2.

(Pivot matrices) The canonical form of $A$ is $\begin{bmatrix}a&&\\\ &a&\\\
&&b\end{bmatrix}$ diagonalizable and $a\neq b$. (Only possible if $q\neq 2$.)

  3. 3.

(LLL matrices) The canonical form of $A$ is $\begin{bmatrix}a&&\\\ &b&\\\
&&c\end{bmatrix}$ all eigenvalues are distinct. (Only possible if $q\neq
2,3$.) We call them LLL matrices because the most important invaraint
subspaces for this kind of matrices are the three eigenlines. By Proposition
2.3, when $q-1$ is an odd prime, images of these matrices form isolated
connected components in the reduced power graphs of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, and each component has diameter at most
$2$.

  4. 4.

(Irreducible Matrices) The canonical form of $A$ is the companion matrix to an
irreducible polynomial of degree three over $\mathbb{F}_{q}$. By Proposition
2.4, images of these matrices form isolated connected components in the
reduced power graphs of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, and each component
has diameter at most $1$.

  5. 5.

(LP matrices) The canonical form of $A$ is $\begin{bmatrix}a&\\\
&C\end{bmatrix}$ where $C$ is the companion matrix to an irreducible
polynomial of degree two over $\mathbb{F}_{q}$. We call them LP matrices
because the most important invaraint subspaces for this matrix are the
eigenline and an invariant plane. By Proposition 2.6 or Proposition 2.7, when
$q=2$, images of these matrices form isolated connected components in the
reduced power graphs of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, and each component
has diameter at most $1$.

  6. 6.

(Jordan pivot matrices) The canonical form of $A$ is $\begin{bmatrix}a&&1\\\
&a&\\\ &&a\end{bmatrix}$.

  7. 7.

(LLP matrices)The canonical form of $A$ is $\begin{bmatrix}a&&\\\ &b&1\\\
&&b\end{bmatrix}$. (Only possible if $q\neq 2$.) We call them LLP matrices
because the most important invaraint subspaces for this matrix are the two
eigenlines and an invariant plane.

  8. 8.

(NPJ matrices) The canonical form of $A$ is $\begin{bmatrix}a&1&\\\ &a&1\\\
&&a\end{bmatrix}$. We call them NPJ matrices because they are non-pivot Jordan
matrices. When $q$ is odd, by Proposition 2.5, images of these matrices form
isolated connected components in the reduced power graphs of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, and each component has diameter at most
$1$. When $n$ is even, then the square of this matrix is a multiple of a
Jordan pivot matrix.

######  Definition 3.1.

For any prime power $q$, we say the _Jordan type_ of a matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ is identity, pivot, LLL, irreducible,
LP, Jordan pivot, LLP, or NPJ if its generalized Jordan normal form has the
corresponding form classified as above.

We want to analyze the pivot components, which contains pivot matrices, Jordan
pivot matrices, LLL matrices, LP matrices, LLP matrices, and (when $q$ is
even) NPJ matrices. Now, by calculating potential powers, we can obtain the
connection diagrams below. We use solid arrows to indicate that some matrices
of a certain type has a power in another type. If the arrow has the word “char
$2$”, then the connection is only possible when $q$ is even.

LLL Matrices $\begin{bmatrix}a&&\\\ &b&\\\ &&c\end{bmatrix}$ Pivot Matrices
$\begin{bmatrix}a&&\\\ &b&\\\ &&b\end{bmatrix}$ LP Matrices
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ LLP Matrices $\begin{bmatrix}a&&\\\
&b&1\\\ &&b\end{bmatrix}$ Jordan Pivot Matrices $\begin{bmatrix}a&&\\\ &a&1\\\
&&a\end{bmatrix}$ NPJ Matrices $\begin{bmatrix}a&1&\\\ &a&1\\\
&&a\end{bmatrix}$ char 2 Figure 1: When $q-1$ is not a prime power LLL
Matrices $\begin{bmatrix}a&&\\\ &b&\\\ &&c\end{bmatrix}$ Pivot Matrices
$\begin{bmatrix}a&&\\\ &b&\\\ &&b\end{bmatrix}$ LP Matrices
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ LLP Matrices $\begin{bmatrix}a&&\\\
&b&1\\\ &&b\end{bmatrix}$ Jordan Pivot Matrices $\begin{bmatrix}a&&\\\ &a&1\\\
&&a\end{bmatrix}$ NPJ Matrices Isolated $\begin{bmatrix}a&1&\\\ &a&1\\\
&&a\end{bmatrix}$ Figure 2: When $q=9$ or $q$ is a Fermat prime, $q\neq 3$ LLL
Matrices Isolated $\begin{bmatrix}a&&\\\ &b&\\\ &&c\end{bmatrix}$ Pivot
Matrices $\begin{bmatrix}a&&\\\ &b&\\\ &&b\end{bmatrix}$ LP Matrices
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ LLP Matrices $\begin{bmatrix}a&&\\\
&b&1\\\ &&b\end{bmatrix}$ Jordan Pivot Matrices $\begin{bmatrix}a&&\\\ &a&1\\\
&&a\end{bmatrix}$ NPJ Matrices $\begin{bmatrix}a&1&\\\ &a&1\\\
&&a\end{bmatrix}$ Figure 3: When $q$ even and $q-1$ prime LLL Matrices (N/A)
$\begin{bmatrix}a&&\\\ &b&\\\ &&c\end{bmatrix}$ Pivot Matrices
$\begin{bmatrix}a&&\\\ &b&\\\ &&b\end{bmatrix}$ LP Matrices
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ LLP Matrices $\begin{bmatrix}a&&\\\
&b&1\\\ &&b\end{bmatrix}$ Jordan Pivot Matrices $\begin{bmatrix}a&&\\\ &a&1\\\
&&a\end{bmatrix}$ NJP Matrices Isolated $\begin{bmatrix}a&1&\\\ &a&1\\\
&&a\end{bmatrix}$ Figure 4: When $q=3$ LLL Matrices (N/A)
$\begin{bmatrix}a&&\\\ &b&\\\ &&c\end{bmatrix}$ Pivot Matrices (N/A)
$\begin{bmatrix}a&&\\\ &b&\\\ &&b\end{bmatrix}$ LP Matrices Isolated
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ LLP Matrices (N/A)
$\begin{bmatrix}a&&\\\ &b&1\\\ &&b\end{bmatrix}$ Jordan Pivot Matrices
$\begin{bmatrix}a&&\\\ &a&1\\\ &&a\end{bmatrix}$ NPJ Matrices
$\begin{bmatrix}a&1&\\\ &a&1\\\ &&a\end{bmatrix}$ Figure 5: When $q=2$

Going through these diagram, we can clearly see the following result.

######  Lemma 3.2.

Let $q\neq 2$ be a prime power. For any matrix $A$ whose image is in the pivot
component of the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$,
either $A$ is similar to $\begin{bmatrix}a&\\\ &C\end{bmatrix}$ for some
$a\in\mathbb{F}_{q}^{*}$ and invertible $2\times 2$ matrix $C$, or $q$ is even
and $A$ is similar to $\begin{bmatrix}a&1&\\\ &a&1\\\ &&a\end{bmatrix}$ for
some $a\in\mathbb{F}_{q}^{*}$.

###### Proof.

Check the diagrams above one by one. ∎

For this purpose, we make the following definition.

######  Definition 3.3.

For any prime power $q$, if $A\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ is similar
to $\begin{bmatrix}a&\\\ &C\end{bmatrix}$ for some $a\in\mathbb{F}_{q}^{*}$
and invertible $2\times 2$ matrix $C$, then we say $A$ is _decomposable_.

Note that decomposable matrices are exactly the LLL matirces, pivot matrices,
LP matrices, LLP matrices, and Jordan pivot matrices.

##  4 Decomposable Matrices to Pivot Matrices

######  Lemma 4.1.

Let $q\neq 2$ be a power of a prime $p$, and pick any factor $p_{0}$ of $q-1$.
Suppose a decomposable matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ has
projective order coprime to $p_{0}$. Then a power of a root of a scalar
multiple of $A$ is a pivot matrix with multiplicative order $p_{0}$.

###### Proof.

Suppose $A$ has projective order $k$. If $A$ is similar to
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ for some $a\in\mathbb{F}_{q}^{*}$ and
invertible $2\times 2$ matrix $C$, consider $a^{-1}A$, which is similar to
$\begin{bmatrix}1&\\\ &a^{-1}C\end{bmatrix}$. Its multiplicative order must be
$k$. So $a^{-1}C$ has multiplicative order $k$.

Since $k$ is coprime to $p_{0}$, by Corollary 2.11, $a^{-1}C$ has a $p_{0}$-th
root $C^{\prime}$ whose multiplicative order is a multiple of $p_{0}$. Let
$x\in\mathbb{F}_{q}^{*}$ be any element with multiplicative order $p_{0}$.
Then since $(C^{\prime})^{kp_{0}}$ must be identity and $p_{0}$ is coprime to
$p$, therefore $(C^{\prime})^{k}$ must be diagonalizable with eigenvalue
$x^{s_{1}},x^{s_{2}}$ for some positive integer $s_{1},s_{2}$. Note that $k$
is coprime to $p_{0}$. So we can find a positive integer $k^{\prime}$ such
that $kk^{\prime}$ is $1$ modulus $p_{0}$.

Suppose $s_{1}-s_{2}$ is a multiple of $p_{0}$. So since $a^{-1}A$ is similar
to $\begin{bmatrix}1&\\\ &a^{-1}C\end{bmatrix}$, therefore $a^{-1}A$ has a
$p_{0}$-th root similar to $\begin{bmatrix}1&\\\
&x^{k^{\prime}(1-s_{1})}C^{\prime}\end{bmatrix}$, whose $k$-th power is
similar to $\begin{bmatrix}1&&\\\ &x&\\\ &&x\end{bmatrix}$, a pivot matrix
with multiplicative order $p_{0}$.

Suppose $s_{1}-s_{2}$ is not a multiple of $p_{0}$. So since $a^{-1}A$ is
similar to $\begin{bmatrix}1&\\\ &a^{-1}C\end{bmatrix}$, therefore $a^{-1}A$
has a $p_{0}$-th root similar to $\begin{bmatrix}1&\\\
&x^{-k^{\prime}s_{1}}C^{\prime}\end{bmatrix}$, whose $k$-th power is similar
to $\begin{bmatrix}1&&\\\ &1&\\\ &&x^{s_{2}-s_{1}}\end{bmatrix}$, a pivot
matrix with multiplicative order $p_{0}$. ∎

######  Lemma 4.2.

If $q$ is a power of an odd prime $p$. Suppose a decomposable matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ has
even projective order. Then a power of a scalar multiple of $A$ is a pivot
matrix with multiplicative order $2$.

###### Proof.

Suppose $A$ has projective order $k$. If $A$ is similar to
$\begin{bmatrix}a&\\\ &C\end{bmatrix}$ for some $a\in\mathbb{F}_{q}^{*}$ and
invertible $2\times 2$ matrix $C$, consider $a^{-1}A$, which is similar to
$\begin{bmatrix}1&\\\ &a^{-1}C\end{bmatrix}$. Its multiplicative order must be
$k$. So $a^{-1}C$ has multiplicative order $k$.

Now $k$ is even. Therefore, consider $(a^{-1}A)^{\frac{k}{2}}$, which has
multiplicative order $2$, and hence it must be diagonalizable over
$\mathbb{F}_{q}$, and it must have eigenvalues $1,\pm 1,\pm 1$. Since it
cannot be identity, $A^{\frac{k}{2}}$ is similar to $\begin{bmatrix}1&&\\\
&-1&\\\ &&-1\end{bmatrix}$ or $\begin{bmatrix}1&&\\\ &1&\\\
&&-1\end{bmatrix}$. So we are done. ∎

######  Corollary 4.3.

If $q$ is a power of an odd prime $p$. Then for any matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$, in
the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, either the
image of $A$ has distance at most $2$ to the image of a pivot matrix with
multiplicative order $2$, or the image of $A$ has no path to the image of any
pivot matrix.

###### Proof.

Note that the image of $A$ has a path to the image of any pivot matrix if and
only if $A$ is not as described by Proposition 2.5 or Proposition 2.4. By
going through all possible generalized Jordan canonical form, $A$ is not as
described by Proposition 2.5 or Proposition 2.4 if and only if $A$ is
decomposable.

If $A$ has even projective order, then this distance is at most $1$ by Lemma
4.2. If $A$ has odd projective order, then this distance is at most $2$ by
Lemma 4.1. ∎

######  Lemma 4.4.

If $q\neq 2$ is a power of $2$. Fix any prime factor $p_{0}$ of $q-1$. Suppose
the projective order of a decomposable matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is
not a power of $p_{0}$, then in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A$ has distance at most $3$
to the image of a pivot matrix with multiplicative order $p_{0}$.

###### Proof.

Suppose $A$ has projective order $k$. Since $k$ is not a power of $p_{0}$, we
can find a prime factor $p_{1}$ of $k$ distinct from $p_{0}$. Then
$A^{\prime}=A^{\frac{k}{p_{1}}}$ will have projective order $p_{1}$. Also note
that $A^{\prime}$ is a power of a decomposable matrix, hence it is
decomposable itself. By Lemma 4.1, in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A^{\prime}$ has distance at
most $2$ to the image of a pivot matrix with multiplicative order $p_{0}$. So
the image of $A$ has distance at most $3$ to the image of a pivot matrix with
multiplicative order $p_{0}$. ∎

######  Lemma 4.5.

If $q\neq 2$ is a power of $2$. Fix any prime factor $p_{0}$ of $q-1$. Suppose
a matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is
similar to $\begin{bmatrix}a&1&\\\ &a&1\\\ &&a\end{bmatrix}$ for some
$a\in\mathbb{F}_{q}^{*}$, then in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A$ has distance at most $3$
to the image of a pivot matrix with multiplicative order $p_{0}$.

###### Proof.

Note that $A^{\prime}=(a^{-1}A)^{2}$ is similar to $\begin{bmatrix}1&&1\\\
&1&\\\ &&1\end{bmatrix}$, which is a decomposable matrix with multiplicative
order $2$. By Lemma 4.1, in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A^{\prime}$ has distance at
most $2$ to the image of a pivot matrix with multiplicative order $p_{0}$. So
the image of $A$ has distance at most $3$ to the image of a pivot matrix with
multiplicative order $p_{0}$. ∎

######  Lemma 4.6.

If $q\neq 2$ is a power of $2$ and $q-1$ is not prime. Fix any prime factor
$p_{0}$ of $q-1$. Suppose the projective order of a decomposable matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is a
power of $p_{0}$, then in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A$ has distance at most $4$
to the image of a pivot matrix with multiplicative order $p_{0}$.

###### Proof.

Since $q$ is even and $q-1$ is not prime, by Lemma 2.10, $q-1$ is not a prime
power. So we can find a prime factor $p_{1}$ of $q-1$ distinct from $p_{0}$.

If the projective order of $A$ is a power of $p_{0}$, then it is coprime to
$p_{1}$. By Lemma 4.1, in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A$ has distance at most $2$
to the image of a pivot matrix with multiplicative order $p_{1}$. However,
this pivot matrix has multiplicative order coprime to $p_{0}$. So again by
Lemma 4.1, the image of this pivot matrix has distance at most $2$ to the
image of a pivot matrix with multiplicative order $p_{0}$. So all in all, the
image of $A$ has distance at most $4$ to the image of a pivot matrix with
multiplicative order $p_{0}$. ∎

######  Lemma 4.7.

If $q\neq 2$ is a power of $2$ and $p_{0}=q-1$ is a prime.Suppose the
projective order of a matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is a
power of $p_{0}$, then $A$ is diagonalizable over $\mathbb{F}_{q}$ or its
characteristic polynomial is irreducible. In particular, either $A$ is a pivot
matrix itself, or $A$ is as described in Proposition 2.3 or Proposition 2.4.

###### Proof.

Since the projective order of $A$ is a power of $p_{0}$, which is odd, by
Lemma 2.12, the generalized Jordan canonical form of $A$ is block diagonal
with companion matrices of irreducible polynomials as diagonal blocks.

If $C$ is one of these blocks and it is $m\times m$ for some $m>1$, then by
Corollary 2.14, its multiplicative order must divide $q^{m}-1$, but cannot
divide $q-1$. Hence if the projective order of a matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is a
power of $p_{0}$, then $q^{m}-1$ must be a multiple of $p_{0}^{2}$. Since $q$
is $1$ modulus the odd prime $p_{0}$, clearly $q+1$ is cannot be a multiple of
$p_{0}$. So $q^{2}-1$ is not a multiple of $p_{0}^{2}$. So $m\neq 2$. Hence
all diagonal blocks in the generalized Jordan canonical form of $A$ must be
$1\times 1$ or $3\times 3$. If one block is $3\times 3$, then $A$ has
irreducible polynomial. If all blocks are $1\times 1$, then $A$ is
diagonalizable over $\mathbb{F}_{q}$. ∎

##  5 Upper Bounds when $q-1$ is not a prime power

Let $q\neq 2$ be a power of a prime $p$. Suppose $q-1$ is not a prime power.
Fix any prime factor $p_{0}$ of $q-1$. Our goal here is to find a short path
(distance at most $4$) in the projectively reduced power graph of
$\mathrm{GL}_{3}(\mathbb{F}_{q})$ between any two pivot matrices whose
multiplicative order is $p_{0}$.

Pick any $b\in\mathbb{F}_{q}$ such that $x\neq 0,1$. In the group
$\mathrm{GL}_{3}(\mathbb{F}_{q})$, let $S_{1},S_{2},S_{3}$ be the centralizers
of $\begin{bmatrix}1&&\\\ &b&\\\ &&b\end{bmatrix},\begin{bmatrix}b&&\\\ &1&\\\
&&b\end{bmatrix},\begin{bmatrix}b&&\\\ &b&\\\ &&1\end{bmatrix}$ respectively.
Let $S_{J}$ be the centralizer of $\begin{bmatrix}1&&\\\ &1&1\\\
&&1\end{bmatrix}$. Finally, let $S=S_{2}\cup S_{3}\cup S_{J}$.

######  Lemma 5.1.

Any $X\in\mathrm{GL}_{3}(\mathbb{F}_{q})$, then $X=X_{1}X_{2}X_{3}$ for some
matrices $X_{1},X_{3}\in S_{1}$ and $X_{2}\in S$.

###### Proof.

Suppose $X=\begin{bmatrix}a&\boldsymbol{v}^{\mathrm{T}}\\\
\boldsymbol{w}&B\end{bmatrix}$ for
$\boldsymbol{v},\boldsymbol{w}\in\mathbb{F}_{q}^{2}$ and a $2\times 2$ matrix
$B$ over $\mathbb{F}_{q}$.

Suppose $B$ is not invertible. Since $X$ is invertible, we cannot have
$B=\begin{bmatrix}0&0\\\ 0&0\end{bmatrix}$. Hence $B$ has rank $1$, and we can
find $B=B_{1}\begin{bmatrix}1&0\\\ 0&0\end{bmatrix}B_{2}$ for some invertible
$B_{1},B_{2}\in\mathrm{GL}_{2}(\mathbb{F}_{q})$. Then

$X=\begin{bmatrix}1&\\\ &B_{1}\end{bmatrix}\begin{bmatrix}a&x&y\\\ c&1&0\\\
d&0&0\end{bmatrix}\begin{bmatrix}1&\\\ &B_{2}\end{bmatrix}.$

Since $X$ is invertible, we must have $d,y\neq 0$. So we have

$X=\begin{bmatrix}1&\\\ &B_{1}\end{bmatrix}\begin{bmatrix}1&&\\\
&1&\frac{c}{d}\\\ &&1\end{bmatrix}\begin{bmatrix}a&0&y\\\ 0&1&0\\\
d&0&0\end{bmatrix}\begin{bmatrix}1&&\\\ &1&\\\
&\frac{x}{y}&1\end{bmatrix}\begin{bmatrix}1&\\\ &B_{2}\end{bmatrix}\in
S_{1}S_{2}S_{1}\subseteq S_{1}SS_{1}.$

Suppose $\boldsymbol{v}=\boldsymbol{w}=\boldsymbol{0}$. Then $X\in
S_{1}\subseteq S_{1}SS_{1}$.

Suppose $\boldsymbol{v}=\boldsymbol{0}$ but
$\boldsymbol{w}\neq\boldsymbol{0}$. Then $B$ must be invertible. Pick
$Y\in\mathrm{GL}_{2}(\mathbb{F}_{q})$ such that $BY^{-1}\begin{bmatrix}1\\\
0\end{bmatrix}=\boldsymbol{w}$. Then

$X=\begin{bmatrix}1&\\\ &BY^{-1}\end{bmatrix}\begin{bmatrix}a&&\\\ 1&1&\\\
&&1\end{bmatrix}\begin{bmatrix}1&\\\ &Y\end{bmatrix}\in
S_{1}S_{3}S_{1}\subseteq S_{1}SS_{1}.$

Similarly, if $\boldsymbol{w}=\boldsymbol{0}$ but
$\boldsymbol{v}\neq\boldsymbol{0}$, then again $X\in S_{1}S_{3}S_{1}\subseteq
S_{1}SS_{1}$.

From now on, we assume that $B$ is invertible and
$\boldsymbol{v},\boldsymbol{w}\neq\boldsymbol{0}$. Pick
$Y\in\mathrm{GL}_{2}(\mathbb{F}_{q})$ such that $BY^{-1}\begin{bmatrix}1\\\
0\end{bmatrix}=\boldsymbol{w}$. Suppose
$\boldsymbol{v}^{\mathrm{T}}Y^{-1}=\begin{bmatrix}x&y\end{bmatrix}$. Then

$X=\begin{bmatrix}1&\\\ &BY^{-1}\end{bmatrix}\begin{bmatrix}a&x&y\\\ 1&1&\\\
&&1\end{bmatrix}\begin{bmatrix}1&\\\ &Y\end{bmatrix}.$

Here, $x$ is actually determined by $\boldsymbol{v},\boldsymbol{w},B$ alone.
Indeed we have

$x=\begin{bmatrix}x&y\end{bmatrix}\begin{bmatrix}1\\\
0\end{bmatrix}=\boldsymbol{v}^{\mathrm{T}}Y^{-1}YB^{-1}\boldsymbol{w}=\boldsymbol{v}^{\mathrm{T}}B^{-1}\boldsymbol{w}.$

If $\boldsymbol{v}^{\mathrm{T}}B^{-1}\boldsymbol{w}\neq 0$, then we further
have

$X=\begin{bmatrix}1&\\\ &BY^{-1}\end{bmatrix}\begin{bmatrix}1&&\\\
&1&-\frac{y}{x}\\\ &&1\end{bmatrix}\begin{bmatrix}a&x&0\\\ 1&1&\\\
&&1\end{bmatrix}\begin{bmatrix}1&&\\\ &1&\frac{y}{x}\\\
&&1\end{bmatrix}\begin{bmatrix}1&\\\ &Y\end{bmatrix}\in
S_{1}S_{3}S_{1}\subseteq S_{1}SS_{1}.$

Now suppose $\boldsymbol{v}^{\mathrm{T}}B^{-1}\boldsymbol{w}=0$. Then we have

$X=\begin{bmatrix}1&\\\ &BY^{-1}\end{bmatrix}\begin{bmatrix}a&0&y\\\ 1&1&\\\
&&1\end{bmatrix}\begin{bmatrix}1&\\\ &Y\end{bmatrix}\in
S_{1}S_{J}S_{1}\subseteq S_{1}SS_{1}.$

∎

######  Corollary 5.2.

Let $q\neq 2$ be any prime power such that $q-1$ is not a prime power. Let
$p_{0}$ be any prime factor of $q-1$. Then in the projectively reduced power
graph of $\mathrm{GL}_{3}(\mathbb{F}_{q})$, any two pivot matrices with
multiplicative order $p_{0}$ has distance at most $4$.

###### Proof.

Suppose $A,B$ are two pivot matrices in $\mathrm{GL}_{3}(\mathbb{F}_{q})$ with
multiplicative order $p_{0}$. Say $A=X_{A}\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}X_{A}^{-1}$ and $B=X_{B}\begin{bmatrix}b_{1}&&\\\
&b_{2}&\\\ &&b_{2}\end{bmatrix}X_{B}^{-1}$. Let $X=X_{A}^{-1}X_{B}$. By Lemma
5.1, $X=X_{1}X_{2}X_{3}$ for some matrices $X_{1},X_{3}\in S_{1}$ and
$X_{2}\in S$.

Note that $\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix},\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\
&&b_{2}\end{bmatrix}$ both have centralizer $S_{1}$. Since $q-1$ is not a
prime power, we can find a prime factor $p_{1}$ of $q-1$ different from
$p_{0}$. Let $x\in\mathbb{F}_{q}^{*}$ be any element with multiplicative order
$p_{1}$. If $X_{2}\in S_{2}$, $S_{3}$ or $S_{J}$, then we set
$D=\begin{bmatrix}x&&\\\ &1&\\\ &&x\end{bmatrix}$, $\begin{bmatrix}x&&\\\
&x&\\\ &&1\end{bmatrix}$ or $\begin{bmatrix}1&&\\\ &1&1\\\ &&1\end{bmatrix}$
respectively.

Then $D$ has multiplicative order $p_{1}$ or $p$, which is coprime to $p_{0}$
either way. Furthermore, we always have $\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}D=D\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}$ and $\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\
&&b_{2}\end{bmatrix}D=D\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\
&&b_{2}\end{bmatrix}$. Consequently, $\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}$ and $D$ are both powers of $\begin{bmatrix}a_{1}&&\\\
&a_{2}&\\\ &&a_{2}\end{bmatrix}D$, and in the same manner,
$\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\ &&b_{2}\end{bmatrix}$ and $D$ are both
powers of $\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\ &&b_{2}\end{bmatrix}D$.
Therefore, in the projectively reduced power graph of
$\mathrm{GL}_{3}(\mathbb{F}_{q})$, $\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}$ and $\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\
&&b_{2}\end{bmatrix}$ both have distance at most $2$ to $D$.

So we have path

$\displaystyle A=X_{A}\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}X_{A}^{-1}=X_{A}X_{1}\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{2}\end{bmatrix}X_{1}^{-1}X_{A}^{-1}$ $\displaystyle\to$ $\displaystyle
X_{A}X_{1}DX_{1}^{-1}X_{A}^{-1}=X_{A}X_{1}X_{2}DX_{2}^{-1}X_{1}^{-1}X_{A}^{-1}$
$\displaystyle\to$ $\displaystyle X_{A}X_{1}X_{2}\begin{bmatrix}b_{1}&&\\\
&b_{2}&\\\ &&b_{2}\end{bmatrix}X_{2}^{-1}X_{1}^{-1}X_{A}^{-1}$
$\displaystyle=$ $\displaystyle X_{A}X_{1}X_{2}X_{3}\begin{bmatrix}b_{1}&&\\\
&b_{2}&\\\ &&b_{2}\end{bmatrix}X_{3}^{-1}X_{2}^{-1}X_{1}^{-1}X_{A}^{-1}$
$\displaystyle=$ $\displaystyle X_{A}X\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\
&&b_{2}\end{bmatrix}X^{-1}X_{A}^{-1}=X_{B}\begin{bmatrix}b_{1}&&\\\ &b_{2}&\\\
&&b_{2}\end{bmatrix}X_{B}^{-1}=B.$

Here each arrow means distance at most $2$. So $A,B$ have distance at most $4$
between them. ∎

######  Proposition 5.3.

If $q$ is an odd prime power, and $q-1$ is not a prime power, then in the
reduce power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the pivot component
has diameter at most $8$.

###### Proof.

Suppose $A,B$ are any two matrices in the pivot component. By Figure 1, all
matrices in the pivot component are decomposable. Since $q$ is odd, by
Corollary 4.3, in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, images $A,B$ will respectively have
distance at most $2$ to images of some pivot matrices $A^{\prime},B^{\prime}$
with multiplicative order $2$. Then by Corollary 5.2, images of
$A^{\prime},B^{\prime}$ have distance at most $4$ between them. So in total,
$A,B$ have distance at most $2+2+4=8$ between them. ∎

######  Proposition 5.4.

If $q$ is power of $2$, and $q-1$ is not a prime, then in the reduce power
graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the pivot component has diameter
at most $10$.

###### Proof.

Suppose $A,B$ are any two matrices in the pivot component. Then by Lemma 3.2,
each of them is either decomposable, or an NPJ matrix.

Let $p_{0},p_{1}$ be any two distinct prime factors of $q-1$. Suppose $A,B$
are both not a decomposable matrix whose projective order is a power of
$p_{i}$. Then by Lemma 4.4 and Lemma 4.5, in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the images of $A$ and $B$ will
respectively have distance at most $3$ to the images of some pivot matrices
$A^{\prime}$ and $B^{\prime}$ with multiplicative order $p_{i}$. Then by
Corollary 5.2, the distance between images of $A^{\prime},B^{\prime}$ is at
most $4$. Therefore the total distance between images of $A,B$ is at most
$3+3+4=10$.

If the above assumption does not happen, then one of $A,B$ is a decomposable
matrix whose projective order is a power of $p_{0}$, and the other is a
decomposable matrix whose projective order is a power of $p_{1}$. Say $A$ has
projective order a power of $p_{0}$ and $B$ has projective order a power of
$p_{1}$. Then by Lemma 4.6, the image of $A$ has distance at most $4$ to the
image of a pivot matrix $A^{\prime}$ with multiplicative order $p_{0}$. By
Lemma 4.1, the image of $B$ has distance at most $2$ to the image of a pivot
matrix $B^{\prime}$ with multiplicative order $p_{0}$. Then by Corollary 5.2,
the distance between images of $A^{\prime},B^{\prime}$ is at most $4$.
Therefore the total distance between images of $A,B$ is at most $4+2+4=10$. ∎

##  6 Upper bound when $q-1$ is a prime power

######  Proposition 6.1.

Let $q$ be a Fermat prime or $q=9$. Then the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has diameter at most $12$.

###### Proof.

Suppose $A,B$ are any two matrices in the pivot component. By Figure 2 and
Figure 4, all matrices in the pivot component are decomposable. Since $q$ is
odd, by Corollary 4.3, in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, images $A,B$ will respectively have
distance at most $2$ to images of some pivot matrices $A^{\prime},B^{\prime}$
with multiplicative order $2$. Then by Proposition 2.8, images of
$A^{\prime},B^{\prime}$ have distance at most $8$ between them. So in total,
$A,B$ have distance at most $2+2+8=12$ between them. ∎

######  Proposition 6.2.

Let $q\neq 2$ be a power of $2$ such that $q-1$ is prime. Then the reduced
power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has diameter at most $13$.

###### Proof.

Suppose $A,B$ are any two matrices in the pivot component. By Figure 3, all
matrices in the pivot component are decomposable or NJP matrices, and they
cannot be LLL matrices.

Suppose $A$ is not an NJP matrix. By Lemma 4.7, either $A$ is a pivot matrix,
or the projective order of $A$ is not a power of the prime $q-1$. Then by
Lemma 4.4, the $A$ has distance at most $2$ to the image of a pivot matrix
$A^{\prime}$.

Now, if $B$ is also not an NPJ matrix, then similarly the image of $B$ has
distance at most $2$ to the image of a pivot matrix $B^{\prime}$. If $B$ is an
NPJ matrix, by Lemma 4.5, the image of $B$ has distance at most $3$ to the
image of a pivot matrix $B^{\prime}$.

By Proposition 2.8, images of $A^{\prime},B^{\prime}$ have distance at most
$8$ between them. So in total, images of $A,B$ have distance at most
$2+3+8=13$ between them.

Similarly, if $B$ is not an NPJ matrix, images of $A,B$ have distance at most
$2+3+8=13$ between them.

Finally, suppose $A,B$ are both NPJ matrices. Then $A^{2}$ and $B^{2}$ will be
Jordan pivot matrices. By Proposition 2.9, images of $A^{2},B^{2}$ have
distance at most $8$ between them. So in total, images of $A,B$ have distance
at most $1+1+8=10$ between them.

All in all, images of $A,B$ have distance at most $13$ between them. ∎

######  Proposition 6.3.

The reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{3})$ has diameter at
most $11$.

###### Proof.

Suppose $A,B$ are any two matrices in the pivot component. If both matrices
are Jordan pivot matrices, by Proposition 2.9, images of $A,B$ have distance
at most $8$ between them.

Now WLOG suppose $A$ is not a Jordan pivot matrix. Then by Figure 4, $A$ is an
LP matrix or an LLP matrix. If $A$ is an LP matrix, then its multiplicative
order must divides $3^{2}-1=8$. So it must have even projective order. By
Lemma 4.2, it has distance at most $1$ to the image of a pivot matrix
$A^{\prime}$. On the other hand, if $A$ is an LLP matrix, then
$A^{\prime}=A^{3}$ is a pivot matrix. Either way, the image of a pivot matrix
$A^{\prime}$ has distance $1$ to the image of $A$.

By Figure 4, $B$ is a decomposable matrix. Since $q$ is odd, by Corollary 4.3,
image $B$ will have distance at most $2$ to image of some pivot matrix
$B^{\prime}$.

By Proposition 2.8, images of $A^{\prime},B^{\prime}$ have distance at most
$8$ between them. So in total, images of $A,B$ have distance at most
$1+2+8=11$ between them. ∎

##  7 Connection restrictions to pivot matrices

First, let us discuss the cases when two matrices of the same Jordan type are
connected by an edge in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$.

######  Lemma 7.1.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of a matrix $A$ and the image of a matrix $B$ are connected by an edge, and
$A,B$ have the same Jordan type, then they have identical invariant subspaces,
eigenspaces and generalized eigenspaces.

###### Proof.

If the image of a matrix $A$ and the image of a matrix $B$ are connected by an
edge, then WLOG say $xB=A^{k}$ for some positive integer $k$ and some
$x\in\mathbb{F}_{q}^{*}$. Then all invariant subspaces of $A$ are invariant
subspaces of $A^{k}=xB$, and thus also invariant subspaces of $B$. Similarly,
all eigenspaces of $A$ are eigenspaces of $B$, and all generalized eigenspaces
of $A$ are generalized eigenspaces of $B$.

Suppose $A,B$ have the same Jordan type. Then they have the same finite number
of invariant subspaces, eigenspaces and generalized eigenspaces. Hence they
have identical invariant subspaces, eigenspaces and generalized eigenspaces. ∎

Next, let us discuss the cases when a matrix and a pivot matrix are connected
by an edge in the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$.

######  Lemma 7.2.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of an LLL matrix $A$ and the image of a pivot matrix $B$ are connected by an
edge, then each eigenspace of $B$ is spanned by some eigenspaces of $A$.

###### Proof.

If the image of an LLL matrix $A$ and the image of a pivot matrix $B$ are
connected by an edge, then $xB=A^{k}$ for some positive integer $k$ and some
$x\in\mathbb{F}_{q}^{*}$.

Since $A$ is an LLL matrix, $A=X\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{3}\end{bmatrix}X^{-1}$ for some invertible $X$ and some
$a_{1},a_{2},a_{3}\in\mathbb{F}_{q}^{*}$. Then
$B=X\begin{bmatrix}x^{-1}a_{1}^{k}&&\\\ &x^{-1}a_{2}^{k}&\\\
&&x^{-1}a_{3}^{k}\end{bmatrix}X^{-1}$.

Since $A$ is an LLL matrix, the eigenspaces of $A$ are the three lines spanned
by the three columns of $X$ respectively. Since $B$ is a pivot matrix, its
eigenspaces are a line spanned by a column of $X$, and a plane spanned by the
other two column of $X$. So we are done. ∎

######  Lemma 7.3.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of an LP matrix $A$ and the image of a pivot matrix $B$ are connected by an
edge, then the invariant subspaces of $A$ are exactly the eigenspaces of $B$.

###### Proof.

If the image of an LP matrix $A$ and the image of a pivot matrix $B$ are
connected by an edge, then a power of $A$ must be $xB$ for some
$x\in\mathbb{F}_{q}^{*}$.

Since $A$ is an LP matrix, $A=X\begin{bmatrix}a&\\\ &C\end{bmatrix}X^{-1}$ for
some invertible $X$, some $a\in\mathbb{F}_{q}^{*}$ and a companion matrix $C$
to some irreducible polynomial. Then $B=X\begin{bmatrix}x^{-1}a^{k}&\\\
&x^{-1}C^{k}\end{bmatrix}X^{-1}$. Since $B$ is a pivot matrix, $x^{-1}C^{k}$
must be diagonalizable over $\mathbb{F}_{q}$ as well. But by Lemma 2.13,
$C^{k}$ is either not diagonalizable over $\mathbb{F}_{q}$, or a multiple of
identity. So we must have $C^{k}=\begin{bmatrix}y&\\\ &y\end{bmatrix}$ for
some $y\in\mathbb{F}_{q}^{*}$, and $B=X\begin{bmatrix}x^{-1}a^{k}&&\\\
&x^{-1}y&\\\ &&x^{-1}y\end{bmatrix}X^{-1}$ with $x^{-1}a^{k}\neq x^{-1}y$.

Now the invariant subspaces of $A$ are the line spanned by the first column of
$X$, and the plane spanned by the last two columns of $X$. But these are
exactly the eigenspaces of $B$. ∎

######  Lemma 7.4.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of an LLP matrix $A$ and the image of a pivot matrix $B$ are connected by an
edge, then the generalized subspaces of $A$ are exactly the eigenspaces of
$B$.

###### Proof.

If the image of an LLP matrix $A$ and the image of a pivot matrix $B$ are
connected by an edge, then a power of $A$ must be $xB$ for some
$x\in\mathbb{F}_{q}^{*}$.

Since $A$ is an LLP matrix, $A=X\begin{bmatrix}a_{1}&&\\\ &a_{2}&1\\\
&&a_{2}\end{bmatrix}X^{-1}$ for some invertible $X$ and some
$a_{1},a_{2}\in\mathbb{F}_{q}^{*}$. Then
$B=X\begin{bmatrix}x^{-1}a_{1}^{k}&&\\\ &x^{-1}a_{2}^{k}&x^{-1}ka_{2}^{k-1}\\\
&&x^{-1}a_{2}^{k}\end{bmatrix}X^{-1}$. Since $B$ is a pivot matrix,
$\begin{bmatrix}x^{-1}a_{2}^{k}&x^{-1}ka_{2}^{k-1}\\\
&x^{-1}a_{2}^{k}\end{bmatrix}$ must be diagonalizable over $\mathbb{F}_{q}$ as
well, so $x^{-1}ka_{2}^{k-1}=0$ and $B=X\begin{bmatrix}x^{-1}a_{1}^{k}&&\\\
&x^{-1}a_{2}^{k}&\\\ &&x^{-1}a_{2}^{k}\end{bmatrix}X^{-1}$ with
$x^{-1}a_{1}^{k}\neq x^{-1}a_{2}^{k}$.

Now the generalized subspaces of $A$ are the line spanned by the first column
of $X$, and the plane spanned by the last two columns of $X$. But these are
exactly the eigenspaces of $B$. ∎

######  Lemma 7.5.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of a pivot matrix $A$ and the image of a pivot matrix $B$ have distance at
most $3$, then either they have the same eigenspaces, or the $2$-dimensional
eigenspace of $A$ contains the $1$-dimensional eigenspace of $B$ and vice
versa.

###### Proof.

Suppose in the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the
image of $A$ has an edge to the image of $A^{\prime}$, which has an edge to
the image of $B^{\prime}$, which has an edge to the image of $B^{\prime}$. By
going through the diagrams from Figure 1 to Figure 4, $A^{\prime},B^{\prime}$
must have the same Jordan type and must be LLL matrices or LP matrices or LLP
matrices.

If $A^{\prime},B^{\prime}$ are both LP or both LLP matrices, then they have
the same invariant subspaces and generalized eigenspaces by Lemma 7.1. Then by
Lemma 7.3 and Lemma 7.4, $A,B$ must have the same eigenspaces.

If $A^{\prime},B^{\prime}$ are both LLL matrices, then they have the same
eigenspaces by Lemma 7.1. Say the three $1$-dimensional eigenspaces are
$W_{1},W_{2},W_{3}$. By Lemma 7.2, eigenspaces of $A$ and of $B$ are spanned
by these. By exhausting all possibilities, either $A,B$ have the same
eigenspaces, or the $2$-dimensional eigenspace of $A$ contains the
$1$-dimensional eigenspace of $B$ and vice versa. ∎

Here are some special restrictions when $q=9$ or $q$ is a Fermat prime.

######  Lemma 7.6.

Suppose $q=9$ or $q$ is a Fermat prime. For an LLL matrix
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})$, let $k$ be the projective order of $A$.
Then $A^{\frac{k}{2}}$ is a pivot matrix. Furthermore, in the reduced power
graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, suppose the image $A$ is
connected to the image of a pivot matrix $B$ by an edge, then
$A^{\frac{k}{2}}$ and $B$ must have identical eigenspaces.

###### Proof.

Since $A$ is an LLL matrix, $A=X\begin{bmatrix}a_{1}&&\\\ &a_{2}&\\\
&&a_{3}\end{bmatrix}X^{-1}$ for some invertible $X$ and some
$a_{1},a_{2},a_{3}\in\mathbb{F}_{q}^{*}$. Since $k$ is the projective order of
$A$, and $q-1$ is a power of $2$, $k$ must be a power of $2$. So
$a_{1}^{k}=a_{2}^{k}=a_{3}^{k}$, but
$a_{1}^{\frac{k}{2}},a_{2}^{\frac{k}{2}},a_{3}^{\frac{k}{2}}$ cannot all be
identical, and they are all square roots of the same element in
$\mathbb{F}_{q}^{*}$. Since each element in $\mathbb{F}_{q}^{*}$ has at most
two square roots, $A^{\frac{k}{2}}$ cannot have three distinct eigenvalues. So
it is indeed a pivot matrix.

Now, if the image of an LLL matrix $A$ and the image of a pivot matrix $B$ are
connected by an edge, then $xB=A^{t}$ for some positive integer $t$ and some
$x\in\mathbb{F}_{q}^{*}$. Since $B$ is not a scalar multiple of identity, $k$
cannot divide $t$. So let $t^{\prime}$ be the power of $2$ such that
$\frac{k}{2}$ divides $tt^{\prime}$ but $k$ does not divide $tt^{\prime}$, and
set $B^{\prime}=(xB)^{t^{\prime}}$. Then $B^{\prime}$ is a power of $A$ that
is not a scalar multiple of identity, but it is a power of $A^{\frac{k}{2}}$.
Hence it is a pivot matrix. So the image of $B$ and the image of $B^{\prime}$
are connected by an edge, and the image of $B^{\prime}$ and the image of
$A^{\frac{k}{2}}$ are connected by an edge. By Lemma 7.1, they all of the same
eigenspaces. ∎

######  Lemma 7.7.

Suppose $q=9$ or $q$ is a Fermat prime. Suppose in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of an LLL matrix $A$ and the
image of an LLL matrix $B$ are connected by an edge. Let $k_{A},k_{B}$ be the
projective order of $A,B$ respectively. Then the pivot matrices
$A^{\frac{k_{A}}{2}}$ and $B^{\frac{k_{B}}{2}}$ must have identical
eigenspaces.

###### Proof.

If the image of a matrix $A$ and the image of a matrix $B$ are connected by an
edge, then WLOG say $xB=A^{k}$ for some positive integer $k$ and some
$x\in\mathbb{F}_{q}^{*}$. Then $B^{\frac{k_{B}}{2}}$ is a scalar multiple of a
power of $A$, and it is a pivot matrices. So by Lemma 7.6,
$A^{\frac{k_{A}}{2}}$ and $B^{\frac{k_{B}}{2}}$ must have identical
eigenspaces. ∎

######  Lemma 7.8.

Suppose $q\neq 2$ and $q-1$ is a prime power. In the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, suppose the image of a pivot matrix $A$ is
connected to the image of a pivot matrix $B$ by an path that does not include
any Jordan pivot matrix, then $A$ and $B$ must have identical eigenspaces.

###### Proof.

WLOG we can assume that there is no other pivot matrices on this path other
than $A$ and $B$. By Figure 2 and Figure 3, then all matrices in this path
between $A$ and $B$ must have the same Jordan type. They must all be LP
matrices, or all be LLP matrices, or all be LLL matrices.

Suppose they are all LP matrices. Then by Lemma 7.1, since all of them are
connected by edges, they all have the same invariant subspaces. By Lemma 7.3,
the eigenspaces of $A$ and $B$ must be identical to these invariant subspaces.
So $A$ and $B$ must have identical eigenspaces.

Suppose they are all LLP matrices. Then by Lemma 7.1, since all of them are
connected by edges, they all have the same generalized eigenspaces. By Lemma
7.4, the eigenspaces of $A$ and $B$ must be identical to these generalized
eigenspaces. So $A$ and $B$ must have identical eigenspaces.

Finally, suppose they are all LLL matrices. Note that in this case, $q$ must
be odd, so $q=9$ or $q$ is a Fermat prime by Lemma 2.10. Suppose the path goes
from the image of $A$ to the image of $A_{1}$, to the image of $A_{2}$, …, to
the image of $A_{t}$, and finally to the image of $B$. Let $k_{i}$ be the
projective order of $A_{i}$. By Lemma 7.7, all $A_{i}^{\frac{k_{i}}{2}}$ have
the same eigenspaces. And by Lemma 7.6, $A$ and $B$ must also have the same
eigenspaces as these matrices. ∎

##  8 Lower Bounds when $q-1$ is not a prime power

Let $q\neq 2$ be a power of a prime $p$. Suppose $q-1$ is not a prime power.
When $q$ is odd, let $p_{0}$ be any odd prime factor of $q-1$, and pick any
$x\in\mathbb{F}_{q}^{*}$ with multiplicative order $p_{0}$. When $q$ is even,
pick any multiplicative generator $x\in\mathbb{F}_{q}^{*}$, and set
$p_{0}=q-1$. Note that either way, we must have $x\neq 0,1$, and both $x$ and
$x^{2}$ have multiplicative order $p_{0}$.

Set $A=\begin{bmatrix}1&&\\\ &x&\\\ &&x^{2}\end{bmatrix}$. Pick any
$x^{\prime}\neq 0,1,-2$ in $\mathbb{F}_{q}$. By our assumption, $q>3$, so this
is possible. Set $X=\begin{bmatrix}x^{\prime}&1&1\\\ 1&x^{\prime}&1\\\
1&1&x^{\prime}\end{bmatrix}$, which has determinant
$(x^{\prime}+2)(x^{\prime}-1)^{2}\neq 0$, so it is invertible. Finally, set
$B=XAX^{-1}$. Note that $A,B$ must be LLL matrices with projective and
multiplicative order $p_{0}$. I claim that in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, images of $A,B$ will have distance at
least $8$ when $q$ is odd, and at least $10$ when $q$ is even.

######  Lemma 8.1.

Let $q\neq 2$ be a power of a prime $p$. Suppose $q-1$ is not a prime power.
If $q$ is odd, in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the distance between the image of $A$ or
$B$ to the image of any pivot matrix is at least $2$. If $q$ is even, this
distance is at least $3$.

###### Proof.

It is enough to prove it for $A$, as $A,B$ are similar matrices.

Note that $A$ has eigenvalue $1,x,x^{2}$. So for any $y\in\mathbb{F}_{q}^{*}$,
the matrix $yA^{k}$ has eigenvalues $y,yx^{k},yx^{2k}$. But since $x$ has odd
multiplicitive order $p_{0}$, $yA^{k}$ has all three eigenvalues distinct when
$k$ is not a multiple of $p_{0}$, and all three eigenvalues identical when $k$
is a multiple of $p_{0}$. So it is either an LLL matrix or a scalar multiple
of identity.

Also note that roots of an LLL matrix must still be an LLL matrix. Therefore,
powers and roots of scalar multiples of $A$ cannot be a pivot matrix. So the
distance between the image of $A$ to the image of any pivot matrix is at least
$2$.

Suppose $q$ is even. Suppose for contradiction that, in the reduce power graph
of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the image of $A$ is connected to the
image of $A^{\prime}$ by an edge, and the image of $A^{\prime}$ is connected
to the image of a pivot matrix $B$ by an edge. Then $B$ must be a scalar
multiple of a power of $A^{\prime}$. Since $B$ cannot be a scalar multiple of
a power of $A$, therefore $A^{\prime}$ must be the root of a scalar multiple
of $A$, and must be an LLL matrix.

Suppose $A^{\prime}$ has eigenvalues $x^{\prime},y^{\prime},z^{\prime}$, and
$(A^{\prime})^{k}=yA$ for some $y\in\mathbb{F}_{q}^{*}$ and some positive
integer $k$. Then
$(x^{\prime})^{k}=y,(y^{\prime})^{k}=yx,(z^{\prime})^{k}=yx^{2}$. So
$x^{\prime}(y^{\prime})^{-1},y^{\prime}(z^{\prime})^{-1},z^{\prime}(x^{\prime})^{-1}$
are all roots of $x$ or $x^{2}$, both are multiplicative generators of
$\mathbb{F}_{q}^{*}$. Therefore
$x^{\prime}(y^{\prime})^{-1},y^{\prime}(z^{\prime})^{-1},z^{\prime}(x^{\prime})^{-1}$
are all multiplicative generators of $\mathbb{F}_{q}^{*}$, and they all have
multiplicative order $q-1$. So powers of $A^{\prime}$ will either have all
three eigenvalues distinct, or all three eigenvalues identical. So if $B$ is a
scalar multiple of a power of $A^{\prime}$, then it must have identical
eigenvalues and become a multiple of identity. But $B$ is supposed to be a
pivot matrix, contradiction. ∎

######  Proposition 8.2.

Let $q\neq 2$ be a power of a prime $p$. Suppose $q-1$ is not a prime power.
If $q$ is odd, in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the distance between the image of $A$ and
the image of $B$ is at least $8$. If $q$ is even, this distance is at least
$10$.

###### Proof.

Suppose for contradiction that there is a path from the image of $A$ to the
image of $B$ in the reduce power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$,
with distance at most $7$ for $q$ odd or distance at most $9$ for $q$ even.

First note that $A,B$ do not have the same eigenspaces. So by Lemma 7.1, any
path between them in the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ cannot be entirely made of LLL matrices. By
Figure 1, our path must contain a pivot matrix.

Let $A^{\prime}$ be the first pivot matrix on this path starting from $A$, and
let $B^{\prime}$ be the last pivot matrix on this path. By Lemma 8.1, the
distance between $A$ and $A^{\prime}$ is at least $2$ for $q$ odd, and at
least $3$ for $q$ even. The same is true for $B$ and $B^{\prime}$. Hence
either way, the distance between $A^{\prime}$ and $B^{\prime}$ is at most $3$.

Now by construction, $A$ must be connected to $A^{\prime}$ via a series of LLL
matrices. By Lemma 7.2, eigenspaces of $A^{\prime}$ are spanned by eigenspaces
of $A$. Let $\boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}$ be the
three columns of the identity matrix, then the eigenspaces of $A^{\prime}$
must be $\mathrm{span}(\boldsymbol{e}_{1})$ and
$\mathrm{span}(\boldsymbol{e}_{2},\boldsymbol{e}_{3})$, or
$\mathrm{span}(\boldsymbol{e}_{2})$ and
$\mathrm{span}(\boldsymbol{e}_{3},\boldsymbol{e}_{1})$, or
$\mathrm{span}(\boldsymbol{e}_{3})$ and
$\mathrm{span}(\boldsymbol{e}_{1},\boldsymbol{e}_{2})$. These are the only
three possibilities.

Similarly, eigenspaces of $B^{\prime}$ are spanned by eigenspaces of $B$. Let
$\boldsymbol{x}_{1},\boldsymbol{x}_{2},\boldsymbol{x}_{3}$ be the three
columns of the matrix $X$, then the one dimensional eigenspace of $B^{\prime}$
must be $\mathrm{span}(\boldsymbol{x}_{1})$ or
$\mathrm{span}(\boldsymbol{x}_{2})$ or $\mathrm{span}(\boldsymbol{x}_{3})$.
Neither of them can coinside with the one dimensional eigenspace of
$A^{\prime}$, and neither of them can be contained in the two dimensional
eigenspace of $A^{\prime}$. But this is impossible by Lemma 7.5. So we are
done. ∎

##  9 Connection restrictions to Jordan pivot matrices

######  Lemma 9.1.

If $A\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ is a Jordan pivot matrix with
eigenvalue $a$, then the column space of $A-aI$ is contained in the kernel of
$A-aI$.

###### Proof.

This is because $(A-aI)^{2}$ is zero by the definition of a Jordan pivot
matrix. ∎

######  Lemma 9.2.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of an LLP matrix $A$ and the image of a Jordan pivot matrix $B$ are connected
by an edge. Suppose $A$ has simple eigenvalue $a_{1}\in\mathbb{F}_{q}^{*}$ and
repeated eigenvalue $a_{2}\in\mathbb{F}_{q}^{*}$, and $B$ has an eigenvalue
$b\in\mathbb{F}_{q}^{*}$. Then the column space of $B-bI$ is the eigenspace of
$A$ for $a_{2}$, and the kernel of $B-bI$ is spanned by the two eigenspaces of
$A$.

###### Proof.

If the image of an LLP matrix $A$ and the image of a Jordan pivot matrix $B$
are connected by an edge, then a power of $A$ must be $xB$ for some
$x\in\mathbb{F}_{q}^{*}$.

Since $A$ is an LLP matrix, $A=X\begin{bmatrix}a_{1}&&\\\ &a_{2}&1\\\
&&a_{2}\end{bmatrix}X^{-1}$ for some invertible $X$. Then
$B=X\begin{bmatrix}x^{-1}a_{1}^{k}&&\\\ &x^{-1}a_{2}^{k}&x^{-1}ka_{2}^{k-1}\\\
&&x^{-1}a_{2}^{k}\end{bmatrix}X^{-1}$ for some positive integer $k$. Since $B$
is a Jordan pivot matrix with eigenvalue $b$, therefore all three diagonal
entries here must be $b$.

Now the column space of $B-bI$ and the eigenspace of $A$ for $a_{2}$ are both
the span of the second column of $X$. The two eigenspaces of $A$ are the span
of the first column of $X$ and the span of the second column of $X$, while the
kernel of $B-bI$ is spanned by the first two columns of $X$. So we are done. ∎

######  Lemma 9.3.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, if the image
of an NPJ matrix $A$ and the image of a Jordan pivot matrix $B$ are connected
by an edge. Suppose $A$ has an eigenvalue $a\in\mathbb{F}_{q}^{*}$ and $B$ has
an eigenvalue $b\in\mathbb{F}_{q}^{*}$. Then the column space of $B-bI$ is the
eigenspace of $A$ for $a$, and the kernel of $B-bI$ is the same as the kernel
of of $(A-aI)^{2}$.

###### Proof.

If the image of an NPJ matrix $A$ and the image of a Jordan pivot matrix $B$
are connected by an edge, then $xB=A^{k}$ for some $x\in\mathbb{F}_{q}^{*}$
and some positive integer $k$, and $k$ must be an even number.

Since $A$ is an NPJ matrix, $A=X\begin{bmatrix}a&1&\\\ &a&1\\\
&&a\end{bmatrix}X^{-1}$ for some invertible $X$. Then
$B=X\begin{bmatrix}x^{-1}a^{k}&&\frac{k}{2}(k-1)a^{k-2}\\\ &x^{-1}a^{k}&\\\
&&x^{-1}a_{2}^{k}\end{bmatrix}X^{-1}$. Since $B$ is a Jordan pivot matrix with
an eigenvalue $b$, therefore all three diagonal entries here must be $b$.

Now the column space of $B-bI$ and the eigenspace of $A$ for $a$ are both the
span of the first column of $X$. The kernel of $B-bI$ and the kernel of
$(A-aI)^{2}$ are both the span of the first two columns of $X$. So we are
done. ∎

######  Lemma 9.4.

In the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, suppose the
image of a Jordan pivot matrix $A$ is connected to the image of a Jordan pivot
matrix $B$ by an path that does not include any pivot matrix. Suppose $A$ has
an eigenvalue $a\in\mathbb{F}_{q}^{*}$ and $B$ has an eigenvalue
$b\in\mathbb{F}_{q}^{*}$. Then the column space of $A-aI$ is the same as the
column space of $B-bI$, and the kernel of $A-aI$ is the same as the kernel of
of $B-bI$.

###### Proof.

WLOG we can assume that there is no otherJordan pivot matrices on this path
other than $A$ and $B$. By checking all diagrams from Figure 1 to Figure 5,
all matrices in this path between $A$ and $B$ must have the same Jordan type.
They must all be LLP matrices, or all be NJP matrices.

Suppose they are all LLP matrices. Then by Lemma 7.1, since all of them are
connected by edges, they all have the same eigenspaces. By Lemma 9.2, the
column space and the kernel of $A-aI$ and the column space and the kernel of
$B-bI$ are determined by these same spaces. So we are done.

Suppose they are all NJP matrices. Then by Lemma 7.1, since all of them are
connected by edges, they all have the same invariant subspaces. By Lemma 9.3,
the column space and the kernel of $A-aI$ and the column space and the kernel
of $B-bI$ are determined by these same spaces. So we are done. ∎

Now we investigate paths between a pivot matrix and a Jordan pivot matrix. We
first make an important definition.

######  Definition 9.5.

Let $A$ be a pivot matrix and $B$ be a Jordan pivot matrix with eigenvalue
$b$. We say $A,B$ are compatible if the two dimensional eigenspace of $A$
contains the column space of $B-bI$, and the kernel of $B-bI$ contains the one
dimensional eigenspace of $A$.

######  Lemma 9.6.

Let $q\neq 2$ be a prime power such that $q-1$ is also a prime power. In the
reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, suppose the image
of a pivot matrix $A$ is connected to the image of a Jordan pivot matrix $B$
by an path. Suppose either $A$ is the only pivot matrix on this path, or $B$
is the only Jordan pivot matrix on this path. Then $A,B$ are compatible to
each other.

###### Proof.

Using Lemma 7.8 and Lemma 9.4, we can WLOG assume that $A$ is the only pivot
matrix on this path, and $B$ is the only Jordan pivot matrix on this path.
Then all other matrices on this path must be LLP matrices, and by Lemma 7.1,
they must all have the same invariant subspaces.

Suppose $C$ is an LLP matrix on this path with simple eigenvalue $c_{1}$ and
repeated eigenvalue $c_{2}$. Let $L_{1}$ be the eigenspace of $C$ for $c_{1}$,
$L_{2}$ be the eigenspace of $C$ for $c_{2}$, and $P$ be the generalized
eigenspace of $C$ for $c_{2}$. By Lemma 7.4, the eigenspaces for $A$ must be
$L_{1}$ and $P$, while the column space of $B-bI$ is $L_{2}$, and the kernel
of $B-bI$ is spanned by $L_{1}$ and $L_{2}$. It is easy to see now that $A,B$
are compatible to each other. ∎

######  Lemma 9.7.

Let $q\neq 2$ be a prime power such that $q-1$ is also a prime power. Let
$A,B\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ be pivot matrices, such that the one
dimensional eigenspace of $B$ is contained in the two dimensional eigenspace
of $A$. Then in the reduced power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$,
their images have distance at least $8$ to each other.

###### Proof.

Suppose for contradiction that there is a path between them with distance at
most $7$. Let the eigenspaces of $A$ be $L_{A},P_{A}$ and the eigenspaces of
$B$ be $L_{B}$ and $P_{B}$, where $L_{A},L_{B}$ are one dimensional and
$P_{A}$ and $P_{B}$ are two dimensional. Since $P_{A}$ cannot contain $L_{A}$,
yet it contains $L_{B}$, therefore $A$ and $B$ do not have the same
eigenspaces. So by Lemma 7.8, there must be a Jordan pivot matrix on this
path.

Let $A^{\prime}$ be the first Jordan pivot matrix on this path starting from
$A$, and let $B^{\prime}$ be the last Jordan pivot matrix on this path. By
Figure 2, Figure 3 and Figure 4, the distance between a pivot matrix and a
Jordan pivot matrix is at least $2$. Since our path has total distance $7$,
the distance between $A^{\prime}$ and $B^{\prime}$ is at most $3$. In
particular, the path from $A^{\prime}$ to $B^{\prime}$ cannot contain a pivot
matrix. If $A^{\prime}$ has eigenvalue $a$ and $B^{\prime}$ has eigenvalue
$b$, then by Lemma 9.4, $A^{\prime}-aI$ and $B^{\prime}-bI$ will have the same
column space and same kernel. Let the common column space be $L$ and the
common kernel be $P$.

Since $A$ has a path to $A^{\prime}$ on which $A^{\prime}$ is the only Jordan
pivot matrix, $A$ and $A^{\prime}$ are compatible by Lemma 9.6. Similarly, $B$
and $B^{\prime}$ are compatible. So $L\subseteq P_{A}\cap P_{B}$, and
therefore $L\neq L_{A},L_{B}$. Now, since $L$ and $L_{B}$ are two different
one dimensional subspaces inside $P_{A}$, $P_{A}$ must be the span of them.
But similarly, $L_{B}$ must be inside $P$, and by Lemma 9.1, $L$ must also be
inside $P$. Hence $P$ is also the span of $L$ and $L_{B}$, and this means
$P=P_{A}$. Then $P$ cannot contains $L_{A}$, contradiction. So we are done. ∎

######  Lemma 9.8.

Let $q\neq 2$ be a prime power such that $q-1$ is also a prime power. Let
$A\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ be a pivot matrix and let
$B\in\mathrm{GL}_{3}(\mathbb{F}_{q})$ be a Jordan pivot matrix with eigenvalue
$b$, such that the two dimensional eigenspace of $A$ is the same as the kernel
of $B-bI$. Then in the reduced power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$, their images have distance at least $10$
to each other.

###### Proof.

Suppose there is a path from $A$ to $B$. Let $B^{\prime}$ be the first pivot
matrix on this path starting from $B$. By Lemma 9.6, $B$ and $B^{\prime}$ are
compatible. So the one dimensional subspace of $B^{\prime}$ is contained in
the kernel of $B-bI$, which is the two dimensional eigenspace of $A$. By Lemma
9.7, $A$ and $B^{\prime}$ have distance at least $8$, while the path from
$B^{\prime}$ to $B$ has distance at least $2$ by Figure 2, Figure 3 and Figure
4. Therefore this path from $A$ to $B$ must have a distance at least $10$. ∎

##  10 Lower bounds when $q-1$ is a prime power

Let $q\neq 2$ be a power of a prime $p$, such that $q-1$ is also the power of
a prime.

If $q\neq 3$ and $q-1$ is a power of $2$, $q+1$ cannot be a power of $2$. Pick
any odd prime factor $p_{0}$ of $q+1$. If $q\neq 2$ is a power of $2$ and
$q-1$ is a prime, then $q+1$ must be coprime to $q-1$. Pick any prime factor
$p_{0}$ of $q+1$. Finally, if $q=3$, then set $p_{0}=q^{2}-1=8$. Either way,
$p_{0}$ is a factor of $q^{2}-1$ but not a factor of $q-1$.

Let $C$ be a companion matrix to any irreducible polynomial over
$\mathbb{F}_{q}$ of degree $2$, then $\mathbb{F}_{q}[C]$ is a field with
$q^{2}$ elements. So we can find $C^{\prime}\in\mathbb{F}_{q}[C]$ with
multiplicative order $p_{0}$. Since $p_{0}$ cannot divide $q-1$, $C^{\prime}$
must have irreducible characteristic polynomial. Set
$A=\begin{bmatrix}C^{\prime}&\\\ &1\end{bmatrix}$, then $A$ is an LP matrix.

######  Lemma 10.1.

Let $q\neq 2,3$ be a power of a prime $p$. Suppose $q-1$ is a prime power.
Then in the reduce power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$, the
image of $A$ has distance at least $2$ to the image of any pivot matrix.

###### Proof.

Since $q\neq 2,3$, $p_{0}$ is a prime number. So by Corollary 2.14, powers of
$A$ are either still LP matrices or scalar multiples of identity. We can also
see that roots of scalar multiples of $A$ cannot be a pivot matrix. So $A$ has
distance at least $2$ to the image of any pivot matrix. ∎

######  Proposition 10.2.

Let $q\neq 3$ be a Fermat prime or $q=9$. Then the reduce power graph of
$\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has diameter at least $12$.

###### Proof.

Set $B=\begin{bmatrix}1&&1\\\ &1&\\\ &&1\end{bmatrix}$, so it is a Jordan
pivot matrix. Suppose there is a path from $A$ to $B$. By Figure 2, this path
must contain a pivot matrix.

Let $A^{\prime}$ be the first pivot matrix on this path starting from $A$. Let
$\boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}$ be the three
columns of the identity matrix. By Lemma 7.3, the eigenspace of $A^{\prime}$
must be the span of $\boldsymbol{e}_{1}$ and $\boldsymbol{e}_{2}$, and the
span of $\boldsymbol{e}_{3}$. In particular, the two dimensional eigenspace of
$A^{\prime}$ is the same as the kernel of $B-I$. By Lemma 9.8, the images of
$A^{\prime}$ and $B$ has distance at least $10$.

By Lemma 10.1, the images of $A$ and $A^{\prime}$ has distance at least $2$.
So this path from $A$ to $B$ have distance at least $12$. ∎

######  Proposition 10.3.

Let $q\neq 2$ be a power of $2$, and $q-1$ is prime. Then the reduce power
graph of $\mathrm{PGL}_{3}(\mathbb{F}_{q})$ has diameter at least $13$.

###### Proof.

Set $B=\begin{bmatrix}1&1&\\\ &1&1\\\ &&1\end{bmatrix}$, so it is an NPJ
matrix. Suppose there is a path from $A$ to $B$. By Figure 3, this path must
contain a pivot matrix and a Jordan pivot matrix.

Let $A^{\prime}$ be the first pivot matrix on this path starting from $A$. Let
$\boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}$ be the three
columns of the identity matrix. By Lemma 7.3, the eigenspace of $A^{\prime}$
must be the span of $\boldsymbol{e}_{1}$ and $\boldsymbol{e}_{2}$, and the
span of $\boldsymbol{e}_{3}$.

Let $B^{\prime}$ be the last Jordan pivot matrix on this path starting from
$A$, and suppose it has an eigenvalue $b\in\mathbb{F}_{q}^{*}$. Let
$\boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}$ be the three
columns of the identity matrix. By Lemma 9.3, the kernel of $B^{\prime}-bI$
must be the span of $\boldsymbol{e}_{1}$ and $\boldsymbol{e}_{2}$, and it is
identical to the two dimensional eigenspace of $A^{\prime}$. By Lemma 9.8, the
images of $A^{\prime}$ and $B^{\prime}$ has distance at least $10$.

By Lemma 10.1, the images of $A$ and $A^{\prime}$ has distance at least $2$.
And since $B$ and $B^{\prime}$ are not in the same Jordan type, their images
have distance at least $1$. So this path from $A$ to $B$ have distance at
least $13$. ∎

######  Proposition 10.4.

The reduce power graph of $\mathrm{PGL}_{3}(\mathbb{F}_{3})$ has diameter at
least $11$.

###### Proof.

Set $B=\begin{bmatrix}1&&1\\\ &1&\\\ &&1\end{bmatrix}$, so it is a Jordan
pivot matrix. Suppose there is a path from $A$ to $B$. By Figure 4, this path
must contain a pivot matrix.

Let $A^{\prime}$ be the first pivot matrix on this path starting from $A$. Let
$\boldsymbol{e}_{1},\boldsymbol{e}_{2},\boldsymbol{e}_{3}$ be the three
columns of the identity matrix. By Lemma 7.3, the eigenspace of $A^{\prime}$
must be the span of $\boldsymbol{e}_{1}$ and $\boldsymbol{e}_{2}$, and the
span of $\boldsymbol{e}_{3}$. In particular, the two dimensional eigenspace of
$A^{\prime}$ is the same as the kernel of $B-I$. By Lemma 9.8, the images of
$A^{\prime}$ and $B$ has distance at least $10$.

Since $A$ and $A^{\prime}$ are not in the same Jordan type, their images have
distance at least $1$. So this path from $A$ to $B$ have distance at least
$11$. ∎

## References

  * AA [15] Narges Akbari and Ali-Reza Ashrafi.  Note on the power graph of finite simple groups.  Quasigroups and Related Systems, 23(2):165–173, 2015.
  * [2] Yilong Yang.  Connectivity of the reduced power graphs of finite simple groups.  preprint https://arxiv.org/abs/2207.04404.