# Reduced Power Graphs of $PGL_{n}(\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. It is conjectured by Akbari and
Ashrafi that if a non-abelian finite simple group has connected reeuced power
graph, then it must be an alternating group.

In this paper, we shall give a complete descprition about when the reduced
power graphs of $PGL_{n}(\mathbb{F}_{q})$ is connected for all $q$ and all
$n\geq 3$. In particular, the conjectured by Akbari and Ashrafi is false. We
shall also provide an upper bound in their diameters, and in case of
disconnection, provide a description of all connected components.

##  1 Introduction

###  1.1 Background and Main Results

Graphical representations of an algebraic structure is always a fascinating
research topic. The most well-known class of graphs is the Cayley graphs of
finitely generated groups, which has been studied for a long time. Recently,
some other graphical representations of groups have also been gathering more
attention from researchers. Around 2000, the concept of a directed power graph
was introduced by Kelarev and Quinn [5] as a new kinds of graphical
representations, and later on Chakrabarty et al. [2] introduced the undirected
power graph of a group.

######  Definition 1.1.

Given a group $G$, the _directed power graph_ of $G$ has all elements of $G$
as vertices, and two distinct vertices $g,h$ are connected by an edge from $g$
to $h$ if and only if $h$ is a power of $g$. The _(undirected) power graph_ of
$G$ is the same graph but we drop all directions on all edges. The _reduced
power graph_ of $G$ is obtained from the undirected power graph by deleting
the identity element.

In this paper, by power graph we shall always mean the undirected power graph,
unless specifically said otherwise.

Power graphs have been shown to capture many algebraic properties of a group.
For example, the power graph of a finite group is a tree if and only if every
element of the group is its own inverse [11]. If a finite group’s power graph
lack particular kinds of subgraphs, then its isomorphism types can be
classified [3]. A finite group is a non-cyclic group of prime exponent if and
only if its power graph is non-complete and minimally edge-connected [8]. For
more results of this type, see [6].

One interesting aspect of the power graph is its connectivity. For finite
groups, obviously power graphs are always connected,because every element is
connected to the identity element. For this purpose, it is more interesting to
consider the connectivity of the reduced power graph, i.e., power graph with
the identity element removed. In particular, Akbari and Ashrafi proposed the
following conjecture in 2015.

######  Conjectures 1.2 (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 this paper, we shall show that this conjecture is false.

######  Theorem 1.3.

Let $\mathbb{F}_{q}$ be a field with characteristic $p$. For any $n\geq 3$
when $q\neq 2$, and for any $n\geq 6$ when $q=2$, the connected components of
the reduced power graph of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$ are the
following.

  1. 1.

If $n$ is prime, and the minimal polynomial of $A$ is irreducible of degree
$n$, then the images of all powers of $A$ that are not multiples of identity
would form a connected component in the reduced power graph of
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$.

  2. 2.

If $n<p$, and $A$ has minimal polynomial $p(x)=(x-\lambda)^{n}$ for some
$\lambda\in\mathbb{F}_{q}^{*}$, then the images of all powers of $A$ that are
not multiples of identity would form a connected component in the reduced
power graph of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$.

  3. 3.

If $q-1$ is prime and $n<q$, and $A$ is diagonalizable with distinct
eigenvalues, then the images of all powers of $A$ that are not multiples of
identity would form a connected component in the reduced power graph of
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$.

  4. 4.

If $q=2$ and $n-1$ is prime, and the minimal polynomial of $A$ is $(x-1)p(x)$
where $p(x)$ is irreducible of degree $n-1$, then the images of all powers of
$A$ that are not multiples of identity would form a connected component in the
reduced power graph of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$.

  5. 5.

If $q=2$, and $n$ or $n-1$ has a prime factor $p_{1}$ such that
$p_{0}=2^{p_{1}}-1$ is also prime, and the characteristic polynomial of $A$
divides $p(x)=x^{p_{0}}-1$, then the images of all powers of $A$ that are not
multiples of identity would form a connected component in the reduced power
graph of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$. (Note that in this case $n$ or
$n-1$ must be at most $p_{0}-1$.)

  6. 6.

All other matrices are in the same connected component. If $q=2$ and $n\geq
6$, then this component has diameter at most $20$. If $q=3$ and $n=4$, then
this component has diameter at most $20$. If $q\neq 2,n\geq 3$ and we are not
in the previous case, this component has diameter at most $16$.

######  Corollary 1.4.

Let $\mathbb{F}_{q}$ be a field with odd characteristic $p$. Then
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$ has connected reduced power graph if and
only if $n$ is not a prime and $n>p$.

If $\mathbb{F}_{q}$ is a field with characteristic $2$ and $q\neq 2$, then
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$ has connected reduced power graph if and
only if $n$ is not a prime, $n>2$, and either $q-1$ is not prime or $n\geq q$.

Finally, $\mathrm{PGL}_{n}(\mathbb{F}_{2})$ has disconnected reduced power
graph if and only if at least one of the following three situations occurs.

  1. 1.

$n$ or $n-1$ is prime.

  2. 2.

$n$ has a prime factor $p_{1}$ such that $p_{0}=2^{p_{1}}-1$ is also a prime
and $n\leq 2^{p_{1}}-2$.

  3. 3.

$n-1$ has a prime factor $p_{1}$ such that $p_{0}=2^{p_{1}}-1$ is also a prime
and $n\leq 2^{p_{1}}-1$.

Note that when $n$ and $q-1$ are coprime, then
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$ is isomorphic to
$\mathrm{PSL}_{n}(\mathbb{F}_{q})$, which is always non-abelian simple when
$n\geq 3$. Say when $q=3$ and $n=9$, then we have a non-abelian finite simple
group $\mathrm{PGL}_{9}(\mathbb{F}_{3})$ with connected reduced power graph.
Similarly,
$\mathrm{PGL}_{9}(\mathbb{F}_{2}),\mathrm{PGL}_{12}(\mathbb{F}_{2})$ also have
connected reduced power graphs. And these are not isomorphic to any
alternating groups. These shows that the conjecture by Akbari and Ashrafi is
false.

For the sake of completion, we also list the number of connected components
and the diameter of each component for the reduced power graph of
$\mathrm{GL}_{3}(\mathbb{F}_{2}),\mathrm{GL}_{4}(\mathbb{F}_{2}),\mathrm{GL}_{5}(\mathbb{F}_{2})$.
These can easily be verified using a computer or some adaptations of the
methods in this paper.

  1. 1.

The reduced power graph of $\mathrm{GL}_{3}(\mathbb{F}_{2})$ is made of
components with diameter $1$, each component is made of non-identity powers of
$X\begin{bmatrix}1&1&\\\ &1&1\\\ &&1\end{bmatrix}X^{-1}$ for some invertible
$X$.

  2. 2.

The reduced power graph of $\mathrm{GL}_{4}(\mathbb{F}_{2})$ has one component
containing $\begin{bmatrix}1&1&&\\\ &1&&\\\ &&1&\\\ &&&1\end{bmatrix}$, and
another component containing $\begin{bmatrix}1&1&&\\\ &1&&\\\ &&1&1\\\
&&&1\end{bmatrix}$, and the rest are isolated components as described by
Proposition 4.6.

  3. 3.

The reduced power graph of $\mathrm{GL}_{5}(\mathbb{F}_{2})$ has one component
containing $\begin{bmatrix}1&1&&&\\\ &1&&&\\\ &&1&&\\\ &&&1&\\\
&&&&1\end{bmatrix}$, and another component containing
$\begin{bmatrix}1&1&&&\\\ &1&&&\\\ &&1&1&\\\ &&&1&\\\ &&&&1\end{bmatrix}$, and
the rest are isolated components as described by Proposition 4.2.

Thus the connected components of the reduced power graph of
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$ for all $n\geq 3$ has be described, and a
diameter upper bound is established for each component.

###  1.2 Notations and Outline of Proof

We use $\mathbb{F}_{q}$ to denote the field with $q$ elements, and
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ to denote the group of invertible $n\times
n$ matrices on $\mathbb{F}_{q}$. We use $Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$
to denote the center of the group $\mathrm{GL}_{n}(\mathbb{F}_{q})$, i.e., the
subgroup made of scalar multiples of identity. We use
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$ to denote the quotient group
$\mathrm{GL}_{n}(\mathbb{F}_{q})/Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$.
Throughout this paper, we use $I_{k}$ to denote the $k\times k$ identity
matrix.

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

######  Definition 1.5.

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

######  Proposition 1.6.

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

Therefore, to establish connectivity, diameters and distances on the reduced
power graph of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$, it is enough to establish
the same statements in Theorem 1.3 on the projectively reduced power graph of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$.

In order to achieve connection, we first need to identify elements of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ that are connected to as much other elements
as possible. Note that if $A$ connected to $B$ in the projectively reduced
power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$, then $B$ must be a power or
a root of $A$. Therefore $B$ must be in the centralizer of $A$. Consequently,
to search for elements with many connections, we can try to find elements with
large centralizers. We shall call these the pivot matrices.

######  Definition 1.7.

For a prime power $q$ and an integer $n\geq 2$, an $n\times n$ matrix $A$ over
$\mathbb{F}_{q}$ is called a _pivot matrix_ if $A$ is diagonalizable over
$\mathbb{F}_{q}$, and $A$ has exactly two eigenvalues not counting
multiplicity. An $n\times n$ matrix $A$ over $\mathbb{F}_{q}$ is called a
_Jordan pivot matrix_ if all eigenvalues of $A$ are $1$, and
$\dim\mathrm{Ker}(A-I)=n-1$.

In particular, pivot matrices are those similar to $\begin{bmatrix}x&&&&&\\\
&\ddots&&&&\\\ &&x&&&\\\ &&&y&&\\\ &&&&\ddots&\\\ &&&&&y\end{bmatrix}$ for
some distinct $x,y\in\mathbb{F}_{q}^{*}$. Jordan pivot matrices are those
similar to $\begin{bmatrix}1&&1\\\ &\ddots&\\\ &&1\end{bmatrix}$.

Our focus is on the pivot matrices when $q\neq 2$. But for $q=2$, there are no
pivot matrices, so we have to resort to Jordan pivot matrices. (And sometimes,
even for $q\neq 2$, connections via Jordan pivot matrices might also give a
shorter distance.) All these matrices are important, because they all have big
centralizers.

In particular, in Section 3, we shall show that all (Jordan) pivot matrices in
the projectively reduced power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ are
connected to each other by some short path if $n$ is large enough. (We need
$n\geq 3$ when $q\neq 2$, and $n\geq 4$ when $q=2$.)

In Section 5, we shall show that almost all matrices in the projectively
reduced power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$ have paths to
(Jordan) pivot matrices, with exceptions outlined in Section 4. These results
will establish Theorem 1.3.

###### Proof of Theorem 1.3.

Combine Proposition 3.1 and Proposition 5.4. ∎

##  2 Preliminary

In this section, we compile many preliminary results about prime powers,
finite fields and matrices over them. These are mostly elementary and are kept
here for reference purpose.

###  2.1 Prime powers

######  Lemma 2.1.

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

###### Proof.

This is a easy and special case of Catalan’s conjecture, proven by Mihăilescu
[7]. ∎

######  Lemma 2.2.

Suppose $q$ and $q-1$ are both prime powers, and $q\neq 2$. For any positive
integer $n>1$, $q^{n}-1$ has a prime factor coprime to $q-1$, unless $q=3$ and
$n=2$.

###### Proof.

Note that $q-1$ is a prime power. So if $q^{n}-1$ has no prime factor coprime
to $q-1$, then $q^{n}$ is also a prime power, hence $q^{n}$ and $q^{n}-1$ are
also consecutive prime powers.

Since $n>1$, $q^{n}$ cannot be prime. Since $q\neq 2$ and $n>1$, $q^{n}-1$
must have a proper factor $q-1$, so it also cannot be prime. So by Lemma 2.1,
the only possibility is $q^{n}=9$. ∎

###  2.2 Matrices over finite fields

In this subsection, we focus on $n\times n$ matrices over $\mathbb{F}_{q}$
whose minimal polynomial is irreducible of degree $n$. Note that such a matrix
must be similar to the campanion matrix of an irreducible polynomial.

######  Lemma 2.3.

Suppose the characteristic polynomial of a matrix
$C\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ is irreducible. Then polynomials of $C$
of degree at most $n-1$ form a field $\mathbb{F}_{q}[C]$ isomorphic to
$\mathbb{F}_{q^{n}}$ under the usual matrix addition and matrix
multiplication. In particular, $C$ is invertible, with multiplicative order
dividing $q^{n}-1$.

###### Proof.

It is easy to very that this is a field with $q^{n}$ elements. ∎

######  Lemma 2.4.

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

###### Proof.

Let the characteristic polynomial of $C$ be $f(x)$. Since this is irreducible,
$f(x)$ is also the minimal polynomial for $C$.

Suppose the minimal polynomial of $C^{t}$ is reducible, say it is $g(x)h(x)$
for polynomials $g(x),h(x)$ of degree at least one. Then we must have
$g(C^{t})h(C^{t})=0$, and thus the minimal polynomial $f(x)$ of $C$ must
divide $g(x^{t})h(x^{t})$. Since $f(x)$ is irreducible, $f(x)$ must divide
$g(x^{t})$ or $h(x^{t})$. But this means we have $g(C^{t})=0$ or $h(C^{t})=0$,
contradicting the fact that $g(x)h(x)$ is supposed to be the minimal
polynomial for $C^{t}$. Hence the minimal polynomial of $C^{t}$ is
irreducible.

Now suppose $t$ is a factor of $k$, then $C^{t}$ has order $\frac{k}{t}$,
which is a factor of $q^{m}-1$, therefore in the finite field
$\mathbb{F}_{q}[C]$, $C^{t}$ is contained in the field with $q^{m}-1$
elements. Hence its minimal polynomial has degree at most $m$. ∎

######  Corollary 2.5.

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 scalar multiple of identity.

######  Corollary 2.6.

Suppose $C$ is an $n\times n$ matrix over $\mathbb{F}_{q}$, $n>1$, and its
characteristic polynomial is irreducible. If $C^{p_{1}}$ is a scalar multiple
of identity for a prime number $p_{1}$, then $n$ is the smallest positive
integer such that $p_{1}(q-1)$ divides $q^{n}-1$.

###### Proof.

Let $n_{1}$ be the smallest positive integer such that $p_{1}(q-1)$ divides
$q^{n_{1}}-1$. We shall show that $n=n_{1}$.

Since $n>1$ and the characteristic polynomial of $C$ is irreducible, by
Corollary 2.5, the multiplicative order of $C$ cannot divide $q-1$, but must
divide $q^{n}-1$. On the other hand, since $C^{p_{1}}$ is a scalar multiple of
identity, $C^{p_{1}(q-1)}=I$. So the multiplicative order of $C$ must divide
$p_{1}(q-1)$. Together, this means the least common multiple of $q-1$ and the
multiplicative order of $C$ must be $p_{1}(q-1)$. Since the multiplicative
order of $C$ and $q-1$ are factors of $q^{n}-1$, therefore their least common
multiple $p_{1}(q-1)$ must divide $q^{n}-1$. So $n_{1}\leq n$.

Suppose $C$ has multiplicative order $k$. Note that since $C^{p_{1}}$ is a
scalar multiple of identity, $C^{p_{1}(q-1)}=I$. So $k$ divides $p_{1}(q-1)$,
and therefore divides $q^{n_{1}}-1$. By Lemma 2.4, this means the minimal
polynomial of $C$ has degree at most $n_{1}$. But it has degree $n$. So $n\leq
n_{1}$. ∎

######  Lemma 2.7.

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$, if $kt$ is a factor of
$q^{n}-1$, then $C$ has a $t$-th root $M$ whose characteristic polynomial is
also irreducible, and whose multiplicative order is $kt$.

###### Proof.

Since $\mathbb{F}_{q}[C]$ is a field with $q^{n}$ elements, its multiplicative
group $\mathbb{F}_{q}[C]^{*}$ is cyclic. Therefore if $C$ has multiplicative
order $k$, and $kt$ is a factor of $q^{n}-1$ for some positive integer $k$,
then a $t$-th root $M$ whose multiplicative order is $kt$.

Now $\mathbb{F}_{q}[M]$ is a vector space over $\mathbb{F}_{q}$ with dimension
at most $n$, but it contains $\mathbb{F}_{q}[C]$. Therefore
$\mathbb{F}_{q}[M]=\mathbb{F}_{q}[C]$ and it is a field. Therefore the minimal
polynomial of $M$ is irreducible and has degree $n$, which means it is also
the characteristic polynomial of $M$. ∎

######  Lemma 2.8.

Suppose $C$ is an $n\times n$ matrix over $\mathbb{F}_{q}$ whose
characteristic polynomial is irreducible, and whose multiplicative order is a
power of a prime $p_{1}$. Then for any prime $p_{0}\neq p_{1}$, $C$ has a
$p_{0}$-th root. Furthermore, if $p_{0}$ divides $q^{n}-1$, then $C$ has a
$p_{0}$-th root whose multiplicative order is a multiple of $p_{0}$.

###### Proof.

Note that $\mathbb{F}_{q}[C]$ is a field with $q^{n}$ elements. Suppose
$p_{0}$ does not divide $q^{n}-1$. Then as the multiplicative group
$\mathbb{F}_{q}[C]^{*}$ is cyclic with order $q^{n}-1$, every non-zero element
in this field must have a unique $p_{0}$-th root.

Suppose $p_{0}$ divides $q^{n}-1$. Since $C$ has multiplicative order
$p_{1}^{k}$ for some integer $k$, $p_{1}^{k}$ must also divide $q^{n}-1$.
Since $p_{0}\neq p_{1}$, $p_{0}p_{1}^{k}$ must divide $q^{n}-1$. So by Lemma
2.7, $C$ has a $p_{0}$-th root whose multiplicative order is a multiple of
$p_{0}p_{1}^{k}$. ∎

######  Lemma 2.9.

Suppose $C$ is an $n\times n$ matrix over $\mathbb{F}_{q}$ whose
characteristic polynomial is irreducible, and whose multiplicative order is a
power of a prime $p_{1}$. Then for any prime $p_{0}\neq p_{1}$ dividing
$q^{2n}-1$, $\begin{bmatrix}C&\\\ &C\end{bmatrix}$ has a $p_{0}$-th root whose
multiplicative order is a multiple of $p_{0}$.

###### Proof.

If $p_{0}$ divides $q^{n}-1$ as well, then by Lemma 2.8, $C$ has a $p_{0}$-th
root $C^{\prime}$ whose multiplicative order is a multiple of $p_{0}$. Then
$\begin{bmatrix}C^{\prime}&\\\ &C^{\prime}\end{bmatrix}$ is the desired
$p_{0}$-th root of $\begin{bmatrix}C&\\\ &C\end{bmatrix}$.

Now suppose $p_{0}$ does not divide $q^{n}-1$. Note that $\mathbb{F}_{q}[C]$
is a field with $q^{n}$ elements. Since $p_{0}\neq p_{1}$ is a factor of
$q^{2n}-1$, we can find an irreducible factor of the polynomial
$f(x)=x^{p_{0}}-C$ of degree $2$ over the field $\mathbb{F}_{q}[C]$. Let this
polynomial be $g(x)=x^{2}+g_{1}(C)x+g_{0}(C)$ for some polynomials
$g_{1}(x),g_{0}(x)$ over $\mathbb{F}_{q}$. Then $\begin{bmatrix}0&-g_{0}(C)\\\
I&-g_{1}(C)\end{bmatrix}$ is the desired $p_{0}$-th root of
$\begin{bmatrix}C&\\\ &C\end{bmatrix}$. ∎

###  2.3 Generalized Jordan canonical form over finite fields

We have the following well-known results for matrices over any field.

######  Theorem 2.10.

For any matrix $A$ over a field $K$, $A$ is similar to a block diagonal matrix
$\begin{bmatrix}J_{1}&&\\\ &\ddots&\\\ &&J_{t}\end{bmatrix}$ over $K$, such
that each diagonal block is $J_{i}=\begin{bmatrix}C_{i}&N&&\\\
&\ddots&\ddots&\\\ &&\ddots&N\\\ &&&C_{i}\end{bmatrix}$ for a companion matrix
$C_{i}$ of some irreducible polynomial over $K$, and
$N=\begin{bmatrix}0&0&\dots&0\\\ \vdots&\vdots&\iddots&\vdots\\\
0&0&\dots&0\\\ 1&0&\dots&0\end{bmatrix}$.

This block diagonal matrix is called the generalized Jordan canonical form of
$A$ over the field $K$, and it is unique up to permutations of the diagonal
blocks. For more detail, see for example [9].

Since the focus of this paper is on matrices over finite fields, we can
actually obtain a better result, by combining the following two statements.

######  Proposition 2.11.

Every irreducible polynomial over a finite field is separable.

###### Proof.

Commonly found in abstract algebra textbooks, say [4]. ∎

######  Proposition 2.12 ([10]).

Let $C$ be a companion matrix of an irreducible polynomial $f(x)$ over a field
$K$. Again let $N=\begin{bmatrix}0&0&\dots&0\\\ \vdots&\vdots&\dots&\vdots\\\
0&0&\dots&0\\\ 1&0&\dots&0\end{bmatrix}$. Then $\begin{bmatrix}C&N&&\\\
&\ddots&\ddots&\\\ &&\ddots&N\\\ &&&C\end{bmatrix}$ and
$\begin{bmatrix}C&I&&\\\ &\ddots&\ddots&\\\ &&\ddots&I\\\ &&&C\end{bmatrix}$
are similar if and only if $f(x)$ is separable.

Combining these two statements, we have the follower prettier version of
generalized Jordan canonical form over finite fields.

######  Theorem 2.13.

For any matrix $A$ over a finite field $K$, $A$ is similar to a block diagonal
matrix $\begin{bmatrix}J_{1}&&\\\ &\ddots&\\\ &&J_{t}\end{bmatrix}$ over $K$,
such that each diagonal block is $J_{i}=\begin{bmatrix}C_{i}&I&&\\\
&\ddots&\ddots&\\\ &&\ddots&I\\\ &&&C_{i}\end{bmatrix}$ for a companion matrix
$C_{i}$ of some irreducible polynomial over $K$.

This version of canonical form is much easier to calculate. We establish some
easy results here for later use.

######  Lemma 2.14.

If $A$ is an $n\times n$ matrix whose minimal polynomial is an irreducible
polynomial over $\mathbb{F}_{q}$ of degree $n$, and $B=A^{k}$ for some
positive integer $k$. Then the generalized Jordan canonical form of $B$ is
block diagonal with identical diagonal blocks, each block is a companion
matrix to the same irreducible polynomial.

###### Proof.

This is simply Lemma 2.4 in terms of generalized Jordan canonical form. ∎

######  Lemma 2.15.

If $A$ is an $n\times n$ matrix whose characteristic polynomial is an
irreducible or has an irreducible factor of degree $n-1$, and $B^{k}=A$ for
some positive integer $k$. Then the characteristic polynomial of $B$ is
irreducible or has an irreducible factor of degree $n-1$, respectively.

###### Proof.

We prove the contrapositives. If $B$ has reducible characteristic polynomial,
then the generalized Jordan canonical form of $B$ will be
$\begin{bmatrix}C_{1}&*&*\\\ &\ddots&*\\\ &&C_{t}\end{bmatrix}$ for some
companion matrices $C_{1},\dots,C_{t}$ and $t\geq 2$. Therefore $A$ will be
similar to $\begin{bmatrix}C_{1}^{k}&*&*\\\ &\ddots&*\\\
&&C_{t}^{k}\end{bmatrix}$, and thus its characteristic polynomial is also
reducible.

The other statement about $n-1$ can be proven similarly. ∎

##  3 Connections between Pivot Matrices

In this section, we shall show that all (Jordan) pivot matrices are connected
by a short path in the projectively reduced power graph of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$, when $n$ is not too small. In particular,
we should establish the following.

######  Proposition 3.1.

For $q\neq 2$ and $n\geq 3$, in the projectively reduced power graph of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$, all pivot matrices has distance at most $8$
to each other.

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

###### Proof.

Combine Proposition 3.6, Proposition 3.10 and Proposition 3.13. ∎

As a special remark, the proofs here rely fundamentally on the fact that these
(Jordan) piviot matrices have big centralizers. In fact, every matrix in the
group $\mathrm{GL}_{n}(\mathbb{F}_{q})$ can be written as the product of at
most five matrices in the centralizers of some Jordan pivot matrices and some
pivot matrices.

###  3.1 From Jordan to Jordan

We only consider the cases for $q\neq 2$ and $n\geq 3$, or for $q=2$ and
$n\geq 4$.

We consider the group $\mathrm{GL}_{n}(\mathbb{F}_{q})$. In this group, pick
$J=\begin{bmatrix}1&&1\\\ &\ddots&\\\ &&1\end{bmatrix}$, which is a Jordan
pivot matrix. We also pick $A=\begin{bmatrix}1&&&&\\\ &x&&&\\\ &&1&&\\\
&&&\ddots&\\\ &&&&1\end{bmatrix}$, where $x\neq 1\in\mathbb{F}_{q}^{*}$ for
$q\neq 2$, and $x$ is a block $\begin{bmatrix}1&1\\\ 1&0\end{bmatrix}$ when
$q=2$. Note that for $q\neq 2$ and $n\geq 3$, or for $q=2$ and $n\geq 4$, we
always have $AJ=JA$. We also always have $A^{q^{2}-1}=I$.

######  Lemma 3.2.

For $q\neq 2$ and $n\geq 3$ or for $q=2$ and $n\geq 4$, $A,J$ are both powers
of $AJ$. In particular, $A$ and $J$ have distance $2$ in the projectively
reduced power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$.

###### Proof.

Let $p$ be the characteristic of the field $\mathbb{F}_{q}$. Since $AJ=JA$,
$J^{p}=I$ and $A^{q^{2}-1}=I$, we have $(AJ)^{q^{2}}=A$.

On the other hand, $J^{q^{2}-1}=J^{-1}$. So we have $(AJ)^{(q^{2}-1)^{2}}=J$.
∎

Let $\mathrm{Comm}(A)$ and $\mathrm{Comm}(J)$ be the centralizer of the two
elements in $\mathrm{GL}_{n}(\mathbb{F}_{q})$ respectively. We adopt the
notation that for any two subsets $H,K$ of a group $G$, then $HK$ stands for
the the subset $\\{hk\in G:h]inH,k\in K\\}$. Our goal here is to show that
these two centralizers can generate $\mathrm{GL}_{n}(\mathbb{F}_{q})$ quickly,
and specifically
$\mathrm{GL}_{n}(\mathbb{F}_{q})=\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$.
Our first step is to show that, most of the time,
$\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$ is enough.

######  Lemma 3.3.

For $q\neq 2$ and $n\geq 3$ or for $q=2$ and $n\geq 4$, suppose a matrix
$X\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ has non-zero lower left entry and
invertible lower left $(n-1)\times(n-1)$ block, then
$X\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$.

###### Proof.

This is essentially the LU decomposition.

Pick $T=\begin{bmatrix}&&1\\\ &I_{n-2}&\\\
1&&\end{bmatrix}\in\mathrm{Comm}(A)$. Then $TX$ has non-zero upper left entry,
and invertible upper left $(n-1)\times(n-1)$ block. Consequently, it has a
unique block LDU decomposition $TX=LDU$ where $L=\begin{bmatrix}1&&\\\
*&I_{n-2}&\\\ *&*&1\end{bmatrix}$ and $U=\begin{bmatrix}1&*&*\\\ &U_{n-2}&*\\\
&&1\end{bmatrix}$ and $D=\begin{bmatrix}d_{1}&&\\\ &I_{n-2}&\\\
&&d_{n}\end{bmatrix}$ for some $(n-2)\times(n-2)$ invertible matrix $U_{n-2}$
and some $d_{1},d_{n}\in\mathbb{F}_{q}^{*}$. Note that
$TLT,U\in\mathrm{Comm}(J)$ and $TD\in\mathrm{Comm}(A)$.

So $X=TLDU=(TLT)(TD)U\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$. ∎

Our second step is to show that every matrix can be adjusted to the case as
described in Lemma 3.3.

######  Lemma 3.4.

For $q\neq 2$ and $n\geq 3$ or for $q=2$ and $n\geq 4$, and any
$X\in\mathrm{GL}_{n}(\mathbb{F}_{q})$, we can find a unit upper triangular
matrix $U$ and a matrix $T=\begin{bmatrix}&&1\\\ &I_{n-2}&\\\
1&&\end{bmatrix}$, such that $XUT$ has non-zero lower left entry, and
invertible lower left $(n-1)\times(n-1)$ block.

###### Proof.

Consider $X=\begin{bmatrix}*&*&*\\\
\boldsymbol{x}_{1}&\dots&\boldsymbol{x}_{n}\end{bmatrix}$ where
$\boldsymbol{x}_{1},\dots,\boldsymbol{x}_{n}\in\mathbb{F}_{q}^{n-1}$. Since
$X$ is invertible, these vectors cannot all have zero last coordinate. So
$\boldsymbol{y}=\boldsymbol{x}_{n}+u_{1}\boldsymbol{x}_{1}+\dots+u_{n-1}\boldsymbol{x}_{n-1}$
will have non-zero last coordinate for some constants
$u_{1},\dots,u_{n-1}\in\mathbb{F}_{q}$. Set $U_{1}=\begin{bmatrix}1&&&u_{1}\\\
&\ddots&&\vdots\\\ &&1&u_{n-1}\\\ &&&1\end{bmatrix}$. Then
$XU_{1}=\begin{bmatrix}*&*&*&*\\\
\boldsymbol{x}_{1}&\dots&\boldsymbol{x}_{n-1}&\boldsymbol{y}\end{bmatrix}$
will have non-zero lower right entry.

Let $V$ be the space spanned by
$\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n-1},\boldsymbol{y}$. If
$V=\mathbb{F}_{q}^{n-1}$, then $XU_{1}$ will also have invertible lower right
$(n-1)\times(n-1)$ block. So $XU_{1}T$ is as desired.

Suppose that is not the case. Since $X$ is invertible, we must have $\dim
V=n-2$, and $\boldsymbol{x}_{1}\notin V$. Now $\boldsymbol{y}$ has non-zero
last coordinate, so $\boldsymbol{y}\neq\boldsymbol{0}$. Since the collection
$\boldsymbol{x}_{2},\dots,\boldsymbol{x}_{n-1},\boldsymbol{y}$ spans $V$ and
since $\boldsymbol{y}\neq\boldsymbol{0}$, therefore we can find a
subcollection of $n-2$ vectors including $\boldsymbol{y}$ that already spans
$V$. Let $\boldsymbol{x}_{i}$ be the excluded vector for some $2\leq i\leq
n-1$.

Then since $\boldsymbol{x}_{1}\notin V$, we must have
$\boldsymbol{x}_{i}+\boldsymbol{x}_{1}\notin V$. So if we set $U_{2}$ be the
unit upper triangular matrix that corresponds to the elementary column
operation of adding the first column to the $i$-th column, then $XU_{1}U_{2}$
will now have non-zero lower right entry and invertible lower right
$(n-1)\times(n-1)$ block. So $XU_{1}U_{2}T$ is as desired. ∎

######  Corollary 3.5.

For $q\neq 2$ and $n\geq 3$ or for $q=2$ and $n\geq 4$,

$\mathrm{GL}_{n}(\mathbb{F}_{q})=\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J).$

###### Proof.

Pick any $X\in\mathrm{GL}_{n}(\mathbb{F}_{q})$. By Lemma 3.4, we can find a
unit upper triangular matrix $U$ and $T=\begin{bmatrix}&&1\\\ &I_{n-2}&\\\
1&&\end{bmatrix}$, such that $XUT$ has non-zero lower left entry, and
invertible lower left $(n-1)\times(n-1)$ block. Then by Lemma 3.3, we see that
$XUT\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$. However, we also see
that $U\in\mathrm{Comm}(J)$ and $T\in\mathrm{Comm}(A)$. So our result follows.
∎

######  Proposition 3.6.

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

###### Proof.

Suppose $J_{1},J_{2}$ are two Jordan pivot matrices. Say
$J_{1}=X_{1}JX_{1}^{-1}$ and $J_{2}=X_{2}JX_{2}^{-1}$ for invertible matrices
$X_{1},X_{2}$. Set $X=X_{1}^{-1}X_{2}$.

By Lemma 3.5, we have $X=M_{1}M_{2}M_{3}M_{4}M_{5}$ where
$M_{1},M_{3},M_{5}\in\mathrm{Comm}(J)$ and $M_{2},M_{4}\in\mathrm{Comm}(A)$.

Now we have the following path.

$\displaystyle J_{1}=$ $\displaystyle
X_{1}JX_{1}^{-1}=X_{1}M_{1}JM_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}AM_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}AM_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}JM_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}JM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}M_{3}AM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}M_{4}AM_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}M_{3}M_{4}JM_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}M_{4}M_{5}JM_{5}^{-1}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle=$ $\displaystyle
X_{1}XJX^{-1}X_{1}^{-1}=X_{2}JX_{2}^{-1}=J_{2}.$

∎

###  3.2 From Pivot to Pivot when $n\geq 4$

When $q\neq 2$, it is more important to have a path between pivot matrices.
For now, we only consider the cases for $q\neq 2$ and $n\geq 4$.

As before, we consider the group $\mathrm{GL}_{n}(\mathbb{F}_{q})$. In this
group, pick $J=\begin{bmatrix}1&&1\\\ &\ddots&\\\ &&1\end{bmatrix}$, which is
a Jordan pivot matrix. We also pick $A=\begin{bmatrix}1&&&&\\\ &x&&&\\\
&&1&&\\\ &&&\ddots&\\\ &&&&1\end{bmatrix}$, where $x\neq
1\in\mathbb{F}_{q}^{*}$.

We first establish a version of Lemma 3.3 with a weaker requirement. However,
this only works for $n\geq 4$.

######  Lemma 3.7.

For $q\neq 2$ and $n\geq 4$, suppose a matrix
$X\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ has non-zero lower left entry, then
$X\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$.

###### Proof.

Since the lower left entry of $X$ is non-zero, using elementary row and column
operations, we can find unit upper triangular matrices $U_{1},U_{2}$ such that
$U_{1}XU_{2}=\begin{bmatrix}0&\begin{matrix}*&\dots\end{matrix}&*\\\
\begin{matrix}\vdots\\\ 0\end{matrix}&X^{\prime}&\begin{matrix}\vdots\\\
*\end{matrix}\\\ x_{n1}&\begin{matrix}0&\dots\end{matrix}&0\end{bmatrix}$ for
some $(n-2)\times(n-2)$ matrix $X^{\prime}$ and some $x_{n1}\neq 0$.

Since $U_{1}XU_{2}$ is invertible, its upper right $(n-1)\times(n-1)$ block
will have rank $n-1$. Hence $X^{\prime}$ has rank at least $n-3$. When $n\geq
4$, this implies that $X^{\prime}$ is not zero. So
$R^{\prime}_{1}X^{\prime}R^{\prime}_{2}=\begin{bmatrix}1&\\\
&X^{\prime\prime}\end{bmatrix}$ for some invertible $(n-2)\times(n-2)$
matrices $R^{\prime}_{1},R^{\prime}_{2}$ and some $(n-3)\times(n-3)$ matrix
$X^{\prime\prime}$. Set $R_{1}=\begin{bmatrix}1&&\\\ &R^{\prime}_{1}&\\\
&&1\end{bmatrix}$ and $R_{2}=\begin{bmatrix}1&&\\\ &R^{\prime}_{2}&\\\
&&1\end{bmatrix}$, then
$R_{1}U_{1}XU_{2}R_{2}=\begin{bmatrix}0&*&\begin{matrix}*&\dots&*\end{matrix}&*\\\
0&1&\begin{matrix}0&\dots&0\end{matrix}&*\\\ \begin{matrix}0\\\ \vdots\\\
0\end{matrix}&\begin{matrix}0\\\ \vdots\\\
0\end{matrix}&X^{\prime\prime}&\begin{matrix}*\\\ \vdots\\\ *\end{matrix}\\\
x_{n1}&0&\begin{matrix}0&\dots&0\end{matrix}&0\end{bmatrix}$.

Then using elementary row and column operations, we can find unit upper
triangular matrices $U_{3},U_{4}$ such that
$U_{3}R_{1}U_{1}XU_{2}R_{2}U_{4}=\begin{bmatrix}0&0&\begin{matrix}*&\dots&*\end{matrix}&*\\\
0&1&\begin{matrix}0&\dots&0\end{matrix}&0\\\ \begin{matrix}0\\\ \vdots\\\
0\end{matrix}&\begin{matrix}0\\\ \vdots\\\
0\end{matrix}&X^{\prime\prime}&\begin{matrix}*\\\ \vdots\\\ *\end{matrix}\\\
x_{n1}&0&\begin{matrix}0&\dots&0\end{matrix}&0\end{bmatrix}\in\mathrm{Comm}(A)$.

Since $U_{1},U_{2},U_{3},U_{4},R_{1},R_{2}\in\mathrm{Comm}(J)$, we are done. ∎

Now a pivot matrix is diagonalizable, but its diagonal form does not
necessarily looks like $A$. So the analogue to Lemma 3.5 are the followings.

######  Lemma 3.8.

For $q\neq 2$ and $n\geq 3$, in the group $\mathrm{GL}_{n}(\mathbb{F}_{q})$,
we pick an arbitrary $A_{1}=\begin{bmatrix}x_{1}I_{n-m_{1}-1}&&\\\
&y_{1}I_{m_{1}}&\\\ &&x_{1}\end{bmatrix}$ and
$A_{2}=\begin{bmatrix}x_{2}I_{n-m_{2}-1}&&\\\ &y_{2}I_{m_{2}}&\\\
&&x_{2}\end{bmatrix}$ for some positive integers $m_{1},m_{2}\leq n-2$, and
some $x_{1},x_{2},y_{1},y_{2}\in\mathbb{F}_{q}^{*}$ such that $x_{1}\neq
y_{1}$ and $x_{2}\neq y_{2}$.

Suppose $m_{1}+m_{2}<n$, then
$\mathrm{GL}_{n}(\mathbb{F}_{q})=\mathrm{Comm}(A_{1})\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A_{2})$.

Suppose $m_{1}=\frac{n}{2}$, then $\mathrm{GL}_{n}(\mathbb{F}_{q})$ is the
union of
$\mathrm{Comm}(A_{1})\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A_{2})$
and
$P\mathrm{Comm}(A_{1})\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A_{2})$
for a permutation matrix $P$ such that
$PA_{1}P^{-1}=\begin{bmatrix}y_{1}I_{n-m_{1}-1}&&\\\ &x_{1}I_{m_{1}}&\\\
&&y_{1}\end{bmatrix}$.

###### Proof.

For any $X\in\mathrm{GL}_{n}(\mathbb{F}_{q})$, we break it down into block
form $X=\begin{bmatrix}X_{11}&X_{12}&X_{13}\\\ X_{21}&X_{22}&X_{23}\\\
X_{31}&X_{32}&X_{33}\end{bmatrix}$ where the rows are grouped into the first
$n-m_{1}-1$ rows, the next $m_{1}$ rows, and the last row, and the columns are
grouped into the first $n-m_{2}-1$ columns, the next $m_{2}$ columns, and the
last column.

The submatrix $\begin{bmatrix}X_{11}&X_{13}\\\ X_{31}&X_{33}\end{bmatrix}$ has
rank at least $n-m_{1}-m_{2}$. If $m_{1}+m_{2}<n$, then this submatrix is non-
zero. So we can find invertible matrices $\begin{bmatrix}R_{11}&R_{12}\\\
R_{21}&R_{22}\end{bmatrix}$ and
$\begin{bmatrix}R^{\prime}_{11}&R^{\prime}_{12}\\\
R^{\prime}_{21}&R^{\prime}_{22}\end{bmatrix}$ such that
$\begin{bmatrix}R_{11}&R_{12}\\\
R_{21}&R_{22}\end{bmatrix}\begin{bmatrix}X_{11}&X_{13}\\\
X_{31}&X_{33}\end{bmatrix}\begin{bmatrix}R^{\prime}_{11}&R^{\prime}_{12}\\\
R^{\prime}_{21}&R^{\prime}_{22}\end{bmatrix}$ has a non-zero lower left entry.

Let $R=\begin{bmatrix}R^{\prime}_{11}&&R^{\prime}_{12}\\\ &I_{m_{1}}&\\\
R^{\prime}_{21}&&R^{\prime}_{22}\end{bmatrix}$ and
$R^{\prime}=\begin{bmatrix}R^{\prime}_{11}&&R^{\prime}_{12}\\\ &I_{m_{2}}&\\\
R^{\prime}_{21}&&R^{\prime}_{22}\end{bmatrix}$. Then $RXR^{\prime}$ will have
non-zero lower left entry. So by Lemma 3.7,
$RXR^{\prime}\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$. Since
$R\in\mathrm{Comm}(A_{1})$ and $R^{\prime}\in\mathrm{Comm}(A_{2})$, we are
done.

Now suppose $m_{1}=\frac{n}{2}$. Then $\begin{bmatrix}X_{13}\\\ X_{23}\\\
X_{33}\end{bmatrix}$ is in fact the last column of $X$. Since $X$ is
invertible, entries in this column cannot all be zero. Let $P$ be any
permutation matrix such that
$PA_{1}P^{-1}=\begin{bmatrix}y_{1}I_{n-m_{1}-1}&&\\\ &x_{1}I_{m_{1}}&\\\
&&y_{1}\end{bmatrix}$. Then $P$ swaps the $\frac{n}{2}$ rows involved in
$X_{23}$ with the $\frac{n}{2}$ rows involved in $X_{13}$ and $X_{33}$. Then
$X$ or $PX$ will have a block structure
$\begin{bmatrix}X^{\prime}_{11}&X^{\prime}_{12}&X^{\prime}_{13}\\\
X^{\prime}_{21}&X^{\prime}_{22}&X^{\prime}_{23}\\\
X^{\prime}_{31}&X^{\prime}_{32}&X^{\prime}_{33}\end{bmatrix}$ where the
submatrix $\begin{bmatrix}X^{\prime}_{11}&X^{\prime}_{13}\\\
X^{\prime}_{31}&X^{\prime}_{33}\end{bmatrix}$ is non-zero.

So we can find invertible matrices $\begin{bmatrix}R_{11}&R_{12}\\\
R_{21}&R_{22}\end{bmatrix}$ and
$\begin{bmatrix}R^{\prime}_{11}&R^{\prime}_{12}\\\
R^{\prime}_{21}&R^{\prime}_{22}\end{bmatrix}$ such that
$\begin{bmatrix}R_{11}&R_{12}\\\
R_{21}&R_{22}\end{bmatrix}\begin{bmatrix}X^{\prime}_{11}&X^{\prime}_{13}\\\
X^{\prime}_{31}&X^{\prime}_{33}\end{bmatrix}\begin{bmatrix}R^{\prime}_{11}&R^{\prime}_{12}\\\
R^{\prime}_{21}&R^{\prime}_{22}\end{bmatrix}$ has a non-zero lower left entry.

Let $R=\begin{bmatrix}R^{\prime}_{11}&&R^{\prime}_{12}\\\ &I_{n/2}&\\\
R^{\prime}_{21}&&R^{\prime}_{22}\end{bmatrix}$ and
$R^{\prime}=\begin{bmatrix}R^{\prime}_{11}&&R^{\prime}_{12}\\\ &I_{n/2}&\\\
R^{\prime}_{21}&&R^{\prime}_{22}\end{bmatrix}$. Then $RXR^{\prime}$ or
$RPXR^{\prime}$ will have non-zero lower left entry. So by Lemma 3.7,
$RXR^{\prime}\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$ or
$RPXR^{\prime}\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$.

Since $R\in\mathrm{Comm}(A_{1})$ and $R^{\prime}\in\mathrm{Comm}(A_{2})$, we
see that $X$ or $PX$ is in
$\mathrm{Comm}(A_{1})\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A_{2})$.
So we are done. ∎

######  Lemma 3.9.

Suppose $q\neq 2$ and $n\geq 3$. Let $A^{\prime}$ be a diagonal matrix whose
upper left entry and lower right entry are identical. Then $A^{\prime},J$ are
both powers of $A^{\prime}J$. In particular, $A^{\prime}$ and $J$ have
distance $2$ in the projectively reduced power graph of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$.

###### Proof.

Let $p$ be the characteristic of the field $\mathbb{F}_{q}$. Since
$A_{i}J=JA_{i}$, $J^{p}=I$ and $A_{i}^{q-1}=I$, we have $(A_{i}J)^{q}=A_{i}$.

On the other hand, $J^{q-1}=J^{-1}$. So we have $(A_{i}J)^{(q-1)^{2}}=J$. ∎

######  Proposition 3.10.

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

###### Proof.

Suppose we have two Jordan pivot matrices. Say they are $X_{1}A_{1}X_{1}^{-1}$
and $X_{2}A_{2}X_{2}^{-1}$ for invertible matrices $X_{1},X_{2}$, and
$A_{1}=\begin{bmatrix}x_{1}I_{n-m_{1}-1}&&\\\ &y_{1}I_{m_{1}}&\\\
&&x_{1}\end{bmatrix}$ and $A_{2}=\begin{bmatrix}x_{2}I_{n-m_{2}-1}&&\\\
&y_{2}I_{m_{2}}&\\\ &&x_{2}\end{bmatrix}$ for some integers $m_{1},m_{2}\leq
n-2$, and some $x_{1},x_{2},y_{1},y_{2}\in\mathbb{F}_{q}^{*}$ such that
$x_{1}\neq y_{1}$ and $x_{2}\neq y_{2}$. By choosing $X_{1},X_{2}$ carefully,
we may assume that $m_{1},m_{2}\leq\frac{n}{2}$. Then we must either have
$m_{1}+m_{2}<n$, or we must have $m_{1}=m_{2}=\frac{n}{2}$.

Set $X=X_{1}^{-1}X_{2}$. By Lemma 3.8, we must either have
$X=M_{1}M_{2}M_{3}M_{4}M_{5}$ or have $PX=M_{1}M_{2}M_{3}M_{4}M_{5}$, where
$M_{1}\in\mathrm{Comm}(A_{1}),M_{3}\in\mathrm{Comm}(A),M_{5}\in\mathrm{Comm}(A_{2})$
and $M_{2},M_{4}\in\mathrm{Comm}(J)$, and $P$ is a permutation matrix such
that $PA_{1}P^{-1}=\begin{bmatrix}y_{1}I_{n-m_{1}-1}&&\\\ &x_{1}I_{m_{1}}&\\\
&&y_{1}\end{bmatrix}$.

Suppose we have $X=M_{1}M_{2}M_{3}M_{4}M_{5}$. Then we have the following
path.

$\displaystyle X_{1}A_{1}X_{1}^{-1}=$ $\displaystyle
X_{1}M_{1}A_{1}M_{1}^{-1}X_{1}^{-1}$ $\displaystyle\xrightarrow{\text{distance
2}}$ $\displaystyle
X_{1}M_{1}JM_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}JM_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}AM_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}AM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}M_{3}JM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}M_{4}JM_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}M_{3}M_{4}A_{2}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}M_{4}M_{5}A_{2}M_{5}^{-1}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle=$ $\displaystyle
X_{1}XA_{2}X^{-1}X_{1}^{-1}=X_{2}A_{2}X_{2}^{-1}.$

Now suppose we have $PX=M_{1}M_{2}M_{3}M_{4}M_{5}$. Let
$A^{\prime}_{1}=PA_{1}P^{-1}$. Then we have the following path.

$\displaystyle X_{1}A_{1}X_{1}^{-1}=$ $\displaystyle
X_{1}P^{-1}A^{\prime}_{1}PX_{1}^{-1}=X_{1}P^{-1}M_{1}A^{\prime}_{1}M_{1}^{-1}PX_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}P^{-1}M_{1}JM_{1}^{-1}PX_{1}^{-1}=X_{1}P^{-1}M_{1}M_{2}JM_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}P^{-1}M_{1}M_{2}AM_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}=X_{1}P^{-1}M_{1}M_{2}M_{3}AM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}P^{-1}M_{1}M_{2}M_{3}JM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}=X_{1}P^{-1}M_{1}M_{2}M_{3}M_{4}JM_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}P^{-1}M_{1}M_{2}M_{3}M_{4}A_{2}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}$
$\displaystyle=$ $\displaystyle
X_{1}P^{-1}M_{1}M_{2}M_{3}M_{4}M_{5}A_{2}M_{5}^{-1}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}PX_{1}^{-1}$
$\displaystyle=$ $\displaystyle
X_{1}P^{-1}PXA_{2}X^{-1}P^{-1}PX_{1}^{-1}=X_{2}A_{2}X_{2}^{-1}.$

∎

###  3.3 From Pivot to Pivot when $n=3$

For $q\neq 2,n=3$, we do not have Lemma 3.7. So we are forced to use Lemma 3.3
which requires a stronger assumption. For this end, we need a stronger version
of Lemma 3.8.

As before, we consider the group $\mathrm{GL}_{3}(\mathbb{F}_{q})$. In this
group, pick $J=\begin{bmatrix}1&&1\\\ &1&\\\ &&1\end{bmatrix}$, which is a
Jordan pivot matrix. We also pick $A=\begin{bmatrix}x&&\\\ &y&\\\
&&x\end{bmatrix}$ for any $x,y\in\mathbb{F}_{q}^{*}$ such that $x\neq y$. note
that the specific values of $x,y$ does not matter, because the centralizer
$\mathrm{Comm}(A)$ will always be the same.

######  Lemma 3.11.

For $q\neq 2$ and $n=3$, for any $X\in\mathrm{GL}_{n}(\mathbb{F}_{q})$, we can
find $R_{1},R_{2}\in\mathrm{Comm}(A)$ such that $R_{1}XR_{2}$ has non-zero
lower left entry, and invertible lower left $2\times 2$ block.

###### Proof.

Suppose $X=\begin{bmatrix}x_{11}&x_{12}&x_{13}\\\ x_{21}&x_{22}&x_{23}\\\
x_{31}&x_{32}&x_{33}\end{bmatrix}$. Then since $X$ is invertible, the
submatrix $\begin{bmatrix}x_{11}&x_{13}\\\ x_{31}&x_{33}\end{bmatrix}$ cannot
be zero. So we can find $\begin{bmatrix}r_{11}&r_{12}\\\
r_{21}&r_{22}\end{bmatrix}$ and
$\begin{bmatrix}r^{\prime}_{11}&r^{\prime}_{12}\\\
r^{\prime}_{21}&r^{\prime}_{22}\end{bmatrix}$ such that
$\begin{bmatrix}r_{11}&r_{12}\\\
r_{21}&r_{22}\end{bmatrix}\begin{bmatrix}x_{11}&x_{13}\\\
x_{31}&x_{33}\end{bmatrix}\begin{bmatrix}r^{\prime}_{11}&r^{\prime}_{12}\\\
r^{\prime}_{21}&r^{\prime}_{22}\end{bmatrix}$ is either $\begin{bmatrix}0&1\\\
1&0\end{bmatrix}$ or $\begin{bmatrix}0&0\\\ 1&0\end{bmatrix}$.

Let $R=\begin{bmatrix}r_{11}&&r_{12}\\\ &1&\\\ r_{21}&&r_{22}\end{bmatrix}$
and $R^{\prime}=\begin{bmatrix}r^{\prime}_{11}&&r^{\prime}_{12}\\\ &1&\\\
r^{\prime}_{21}&&r^{\prime}_{22}\end{bmatrix}$, then
$R,R^{\prime}\in\mathrm{Comm}(A)$ and $RXR^{\prime}=\begin{bmatrix}0&*&*\\\
*&*&*\\\ 1&*&0\end{bmatrix}$ where the upper right entry is $0$ or $1$.

First, let us deal with the case $RXR^{\prime}=\begin{bmatrix}0&a&1\\\
b&c&d\\\ 1&e&0\end{bmatrix}$.

If the lower left $2\times 2$ block is already invertible, then we are done.
If the upper right $2\times 2$ block is invertible, then set
$T=\begin{bmatrix}&&1\\\ &1&\\\ 1&&\end{bmatrix}\in\mathrm{Comm}(A)$. We would
then have $TRXR^{\prime}T$ with non-zero lower left entry and invertible lower
left $2\times 2$ block as well. Since $T\in\mathrm{Comm}(A)$ as well, we are
also done.

Now suppose that the lower left $2\times 2$ block and the upper right $2\times
2$ block of $RXR^{\prime}$ are both not invertible. Since the lower left block
is not invertible, we must have $a,d\neq 0$. Since the upper right block is
not invertible, we must have $b,e\neq 0$. Finally, since both the lower left
block and the upper right block must have determinant $0$, we must have
$c=ad=be$. Set $L=\begin{bmatrix}1&&\\\ &1&\\\
1&&1\end{bmatrix}\in\mathrm{Comm}(A)$, then
$RXR^{\prime}L=\begin{bmatrix}1&a&1\\\ b+d&c&d\\\ 1&e&0\end{bmatrix}$, and its
lower left $2\times 2$ block has determinant $(b+d)e-c=de\neq 0$. So it is
invertible, and we are done.

Second, let us deal with the case $RXR^{\prime}=\begin{bmatrix}0&a&0\\\
b&c&d\\\ 1&e&0\end{bmatrix}$. Again if the lower left $2\times 2$ block is
already invertible, then we are done. Suppose that this is not the case, then
$be-c=0$

Since $RXR^{\prime}$ is invertible, we must have $a,d\neq 0$. Set
$L=\begin{bmatrix}1&&\\\ &1&\\\ 1&&1\end{bmatrix}\in\mathrm{Comm}(A)$. If
$b\neq 0$, then $LRXR^{\prime}=\begin{bmatrix}0&a&0\\\ b&c&d\\\
1&e+a&0\end{bmatrix}$, and the lower left block has determinant
$b(e+a)-c=ab\neq 0$. So we are done. Similarly, if $e\neq 0$, then
$RXR^{\prime}L=\begin{bmatrix}0&a&0\\\ b+d&c&d\\\ 1&e&0\end{bmatrix}$, and the
lower left block has determinant $(b+d)e-c=de\neq 0$. So we are done.

Suppose $b=e=0$. Since the lower left block should not be invertible, we must
have $c=0$ as well. So we have $RXR^{\prime}=\begin{bmatrix}0&a&0\\\ 0&0&d\\\
1&0&0\end{bmatrix}$. Then $LRXR^{\prime}L=\begin{bmatrix}0&a&0\\\ d&0&d\\\
1&a&0\end{bmatrix}$, and the lower left block has determinant $ad\neq 0$. So
we are done.

In all cases, we can find $R_{1},R_{2}\in\mathrm{Comm}(A)$ such that
$R_{1}XR_{2}$ has non-zero lower left entry, and invertible lower left
$2\times 2$ block. ∎

######  Corollary 3.12.

For $q\neq 2$ and $n=3$,
$\mathrm{GL}_{n}(\mathbb{F}_{q})=\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A)$.

###### Proof.

For any $X\in\mathrm{GL}_{3}(\mathbb{F}_{q})$, by lemma 3.11, we can find
$R_{1},R_{2}\in\mathrm{Comm}(A)$ such that $R_{1}XR_{2}$ has non-zero lower
left entry, and invertible lower left $2\times 2$ block. The by Lemma 3.3,
$R_{1}XR_{2}\in\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)$. Therefore
$X\in\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A)\mathrm{Comm}(J)\mathrm{Comm}(A)$.
∎

######  Proposition 3.13.

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

###### Proof.

Suppose we have two pivot matrices. Note that a $3\times 3$ pivot matrix must
have exactly one eigenvalue with multiplicity $2$, and another eigenvalue with
multiplicity $1$. Say they are $X_{1}A_{1}X_{1}^{-1}$ and
$X_{2}A_{2}X_{2}^{-1}$ for invertible matrices $X_{1},X_{2}$, and
$A_{1}=\begin{bmatrix}x_{1}&&\\\ &y_{1}&\\\ &&x_{1}\end{bmatrix}$ and
$A_{2}=\begin{bmatrix}x_{2}&&\\\ &y_{2}&\\\ &&x_{2}\end{bmatrix}$ for some
$x_{1},x_{2},y_{1},y_{2}\in\mathbb{F}_{q}^{*}$ such that $x_{1}\neq y_{1}$ and
$x_{2}\neq y_{2}$. Note that we must have
$\mathrm{Comm}(A_{1})=\mathrm{Comm}(A_{2})=\mathrm{Comm}(A)$.

Set $X=X_{1}^{-1}X_{2}$.

By Corollary 3.12, we have $X=M_{1}M_{2}M_{3}M_{4}M_{5}$ where
$M_{1},M_{3},M_{5}\in\mathrm{Comm}(A)$ and $M_{2},M_{4}\in\mathrm{Comm}(J)$.

Now we have the following path.

$\displaystyle X_{1}A_{1}X_{1}^{-1}=$ $\displaystyle
X_{1}M_{1}A_{1}M_{1}^{-1}X_{1}^{-1}$ $\displaystyle\xrightarrow{\text{distance
2}}$ $\displaystyle
X_{1}M_{1}JM_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}JM_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}AM_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}AM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}M_{3}JM_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}M_{4}JM_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle\xrightarrow{\text{distance 2}}$ $\displaystyle
X_{1}M_{1}M_{2}M_{3}M_{4}A_{2}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}=X_{1}M_{1}M_{2}M_{3}M_{4}M_{5}A_{2}M_{5}^{-1}M_{4}^{-1}M_{3}^{-1}M_{2}^{-1}M_{1}^{-1}X_{1}^{-1}$
$\displaystyle=$ $\displaystyle
X_{1}XA_{2}X^{-1}X_{1}^{-1}=X_{2}A_{2}X_{2}^{-1}.$

So we are done. ∎

##  4 Obstructions to connectivity

In this section, we show several types of obstructions to the connectivity of
the reduced power graphs of $\mathrm{PGL}_{n}(\mathbb{F}_{q})$, and the
projectively reduced power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$. As we
shall see later, Proposition 4.1, Proposition 4.2 and Proposition 4.4 are in
fact the only obstructions when $q\neq 2$ and $n\geq 3$.

For $q=2$, there are two extra types of obstructions by Proposition 4.5 and
Proposition 4.6. Again as we shall see later, they are the only extra
obstructions for $\mathrm{GL}_{n}(\mathbb{F}_{2})$ and
$\mathrm{PGL}_{n}(\mathbb{F}_{2})$ when $n\geq 6$.

######  Proposition 4.1 (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 scalar multiples of identity.

###### Proof.

We want to show that, in the reduced power graph of
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$, images of powers of $A$ that are not
scalar multiples of identity form a connected component. Then it is enough to
show that, if $B$ is a root of $A^{\prime}$, a scalar multiple of a power of
$A$ that is not a scalar multiple of identity, then $B$ is a multiple of a
power of $A$.

Note that since $n\leq p$, $A^{p}$ is a scalar multiple of identity. Suppose
$B^{k}=zA^{t}$ for some $z\in\mathbb{F}_{q}^{*}$ and positive integers $k,t$
such that $A^{t}$ is not a scalar multiple of identity. Then $t$ and $p$ must
be coprime. Hence $A$ is a multiple of a power of $A^{t}$ as well. So we may
WLOG assume that $t=1$.

Suppose $B^{k}=zA$ for some $z\in\mathbb{F}_{q}^{*}$ and a positive integer
$k$. Then we have $AB=BA$. Hence $B$ must be a polynomial of $A$. This implies
that $B^{p}$ is a scalar multiple of identity, say $B^{p}=bI$ for some
$b\in\mathbb{F}_{q}^{*}$. In particular, $k$ cannot be a multiple of $p$. So
we can find a positive integer $k^{\prime}$ such that $kk^{\prime}=mp+1$ for
some positive integer $m$. Then
$z^{k^{\prime}}A^{k^{\prime}}=B^{kk^{\prime}}=b^{m}B$. So $B$ is a scalar
multiple of a power of $A$.

Hence images of powers of $A$ that are not scalar multiples of identity form a
connected component. They are the images of $A,A^{2},\dots,A^{p-1}$. They all
corresponds to distinct vertices, and they are all powers of each other. Hence
this connected component has $p-1$ vertices and diameter $1$. ∎

######  Proposition 4.2 (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
scalar multiples of identity. The diameter of this component is at most $2$.

###### Proof.

We know polynomials of $A$ form a field $\mathbb{F}_{q}[A]$ with $q^{n}$
elements. Pick $C$ that generate $\mathbb{F}_{q}[A]^{*}$ multiplicatively.
Then all non-zero polynomials of $A$ are powers of $C$. Clearly $C$ is also
similar to a companion matrix of an irreducible polynomial of degree $n$.

It is enough to show that, if $B$ is a root of $C^{\prime}$, a scalar multiple
of a power of $C$ that is not a scalar multiple of identity, then $B$ is a
scalar multiple of a power of $C$. Then this would imply that images of
polynomials of $A$ (or equivalently, powers of $C$) that are not scalar
multiples of identity form a connected component, where everyone is connected
to $C$. Hence it will have $(q^{n}-q)/(q-1)$ vertices and diameter at most
$2$.

Suppose $B^{k}=zC^{t}$ for some $z\in\mathbb{F}_{q}^{*}$ and positive integer
$k,t$ such that $C^{t}$ is not a scalar multiple of identity. Note that by
Lemma 2.14, the generalized Jordan canonical form of $C^{t}$ is made of
identical diagonal blocks that are the same companion matrix of some
irreducible polynomial. Since $n$ is prime, either these blocks are $1\times
1$ which implies that $C^{t}$ is a scalar multiple of identity, or the block
is $n\times n$. Only the latter case is possible. So $C^{t}$ is similar to a
companion matrix of an irreducible polynomial.

Now we have $BC^{t}=C^{t}B$. By Lemma 4.3, $B$ must be a polynomial of
$C^{t}$. In particular, $B\in\mathbb{F}_{q}[A]$. Since we know $B^{k}=zC$, we
know that $B$ is invertible and hence non-zero. Therefore
$B\in\mathbb{F}_{q}[C]^{*}$, and it must be a power of $C$. So we are done. ∎

######  Lemma 4.3.

For $n\geq 2$, consider an $n\times n$ companion matrix
$A=\begin{bmatrix}\boldsymbol{e}_{2}&\boldsymbol{e}_{3}&\dots&\boldsymbol{e}_{n}&\boldsymbol{v}\end{bmatrix}$
where $\boldsymbol{e}_{1},\dots,\boldsymbol{e}_{n}$ are the standard basis for
$\mathbb{F}_{q}^{n}$ and $\boldsymbol{v}$ is an arbitrary vector in
$\mathbb{F}_{q}^{n}$. If $AB=BA$ for some $n\times n$ matrix $B$, then $B$ is
a polynomial of $A$.

###### Proof.

Let
$B=\begin{bmatrix}\boldsymbol{b}_{1}&\dots&\boldsymbol{b}_{n}\end{bmatrix}$.
Then we have

$BA=\begin{bmatrix}B\boldsymbol{e}_{2}&B\boldsymbol{e}_{3}&\dots&B\boldsymbol{e}_{n}&B\boldsymbol{v}\end{bmatrix}=\begin{bmatrix}\boldsymbol{b}_{2}&\dots&\boldsymbol{b}_{n}&B\boldsymbol{v}\end{bmatrix},$
$AB=\begin{bmatrix}A\boldsymbol{b}_{1}&\dots&A\boldsymbol{b}_{n}\end{bmatrix}.$

Hence $AB=BA$ implies that $\boldsymbol{b}_{i+1}=A\boldsymbol{b}_{i}$ for
$1\leq i\leq n-1$. So we have

$B=\begin{bmatrix}\boldsymbol{b}_{1}&A\boldsymbol{b}_{1}&\dots&A^{n-1}\boldsymbol{b}_{1}\end{bmatrix}.$

Now we set

$B_{i}=\begin{bmatrix}\boldsymbol{e}_{i}&A\boldsymbol{e}_{i}&\dots&A^{n-1}\boldsymbol{e}_{i}\end{bmatrix}=A^{i-1}.$

Suppose $\boldsymbol{b}_{1}=\sum x_{i}\boldsymbol{e}_{i}$ for coefficients
$x_{1},\dots,x_{n}\in\mathbb{F}_{q}$. Then $B=\sum x_{i}B_{i}=\sum
x_{i}A^{i-1}$. Hence $B$ is a polynomial of $A$. ∎

######  Proposition 4.4 (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$.

###### Proof.

It is enough to show that, if $B$ is a root of $A^{\prime}$, a scalar multiple
of a power of $A$ that is not a scalar multiple of identity, then $B$ is a
scalar multiple of a power of $A$. Then powers of $A$ that are not scalar
multiples of identity would form a connected component in the reduced power
graph of $\mathrm{PGL}_{n}(q)$ with vertices represented by $A,\dots,A^{q-2}$.
None of these matrices can be scalar multiples of each other. They all have
order $q-1$, which is prime, so they are all powers of each other. So this is
a connected component with $q-2$ vertices and diameter $1$.

Suppose $B^{k}=zA^{t}$ for some $z\in\mathbb{F}^{*}$ and positive integer
$k,t$ such that $A^{t}$ is not a scalar multiple of identity. Note that if
$A^{t}$ is not a scalar multiple of identity, then $t$ must be coprime to the
prime number $q-1$. Hence $A^{t}$ and $A$ are powers of each other, and
$A^{t}$ also has $n$ distinct non-zero eigenvalues over $\mathbb{F}_{q}$. Then
$BA^{t}=A^{t}B$ implies that $A^{t},B$ are simultaneously diagonalizable over
$\mathbb{F}_{q}$. Suppose $A^{t}$ has eigenvalues $a_{1},\dots,a_{n}$ and $B$
has corresponding eigenvalues $b_{1},\dots,b_{n}$ such that
$b_{i}^{k}=za_{i}$. Note that $q-1$ is prime, so the multiplicative group
$\mathbb{F}_{q}^{*}$ is cyclic of prime order. Hence if all $b_{i}^{k}$ are
distinct, we must have $k$ coprime to $q-1$. Let $k^{\prime}$ be a positive
integer such that $kk^{\prime}$ is $1$ modulus $q-1$. Then
$b_{i}=z^{k^{\prime}}a_{i}^{k^{\prime}}$. Hence we have
$B=z^{k^{\prime}}A^{tk^{\prime}}$. So we are done. ∎

Finally, we discuss two special type of obstructions to connectivity when
$q=2$. Note that in this case, $\mathrm{PGL}_{n}(2)=\mathrm{GL}_{n}(2)$.

The following obstruction is essentially a variant of the obstruction above.

######  Proposition 4.5 (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$.

###### Proof.

Set $q=p_{0}+1$. Then $q$ is a power of $2$, so we can pick an extension
$\mathbb{F}_{q}$ of $\mathbb{F}_{2}$. Let us treat $A$ as a matrix over
$\mathbb{F}_{q}$ instead.

Then $A^{q-1}=I$ implies that $A$ is diagonalizable over $\mathbb{F}_{q}$. And
since its minimal polynomial is the same as its characteristic polynomials, it
has $n$ distinct non-zero eigenvalues over $\mathbb{F}_{q}$, and $2\leq n<q$,
and $q-1$ is a prime. So we are in the case of Proposition 4.4. So $A$ is
trapped in a connected component even in the reduced power graph of
$\mathrm{PGL}_{n}(q)$, made of non-identity powers of $A$. Therefore in the
subgraph made of matrices in $\mathrm{PGL}_{n}(2)$, $A$ is also trapped in the
same connected component.

For the last statement, if $p_{0}=2^{p_{1}}-1$ is a prime, then it is a
Mersenne prime. Thus $p_{1}$ is also prime.

Now if $A$ has multiplicative order $p_{0}$, then by Lemma 5.2, the
generalized Jordan canonical form of $A$ is block diagonal with diagonal
blocks $C_{1},\dots,C_{t}$ of companion matrices for irreducible polynomials.
Since $A$ has multiplicative order $p_{0}$, each $C_{i}$ must have
multiplicative order dividing $p_{0}$. So either $C_{i}$ is $1\times 1$, or
$C_{i}$ is $p_{1}\times p_{1}$ by Corollary 2.6.

Since the minimal polynomial and characteristic polynomial of $A$ are the
same, all $C_{i}$ must be distinct. Hence there is at most one block of size
$1\times 1$, and all other blocks must be $p_{1}\times p_{1}$. Therefore $n$
or $n-1$ is a multiple of $p_{1}$. ∎

The second one is a variant of Proposition 4.2.

######  Proposition 4.6 (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$.

###### Proof.

Consider the generalized Jordan canonical form of $A$, we must have
$A=X\begin{bmatrix}A^{\prime}&\\\ &1\end{bmatrix}X^{-1}$ for invertible $X$,
where $A^{\prime}$ is a companion matrix of an irreducible polynomial of
degree $n-1$.

We know polynomials of $A^{\prime}$ form a field $\mathbb{F}_{q}[A^{\prime}]$
with $2^{n-1}$ elements. Pick $C^{\prime}$ that generate
$\mathbb{F}_{q}[A^{\prime}]^{*}$ multiplicatively. Then $A^{\prime}$ is a
power of $C^{\prime}$. Then all non-zero polynomials of $A^{\prime}$ are
powers of $C^{\prime}$. Let $C=X\begin{bmatrix}C^{\prime}&\\\
&1\end{bmatrix}X^{-1}$, then $A$ is similar to a power of $C$.

It is enough to show that, if $B$ is a root of $C^{\prime\prime}$, a scalar
multiple of a power of $C$ that is not a scalar multiple of identity, then $B$
is a scalar multiple of a power of $C$. Then this would imply that non-
identity powers of $C$ form a connected component, where everyone is connected
to $C$. Since $C$ has multiplicative order $2^{n-1}-1$, this connected
component will have $2^{n-1}-2$ vertices and diameter at most $2$.

Suppose $B^{k}=C^{t}$ for some positive integers $k,t$ such that
$C^{t}=X\begin{bmatrix}(C^{\prime})^{t}&\\\ &1\end{bmatrix}X^{-1}$ is not
identity. In particular, $(C^{\prime})^{t}$ is not identity. By Lemma 2.14,
the generalized Jordan canonical form of $(C^{\prime})^{t}$ is made of
identical diagonal blocks that are the same companion matrix of some
irreducible polynomial. Since $n-1$ is prime, either these blocks are $1\times
1$ which (over $\mathbb{F}_{2}$) implies that $C^{t}$ is identiy, or there is
only one $(n-1)\times(n-1)$ block. Only the latter case is possible. So
$(C^{\prime})^{t}$ is similar to a companion matrix of an irreducible
polynomial.

Now we have $BC^{t}=C^{t}B$. Since $(C^{\prime})^{t}$ has no eigenvalue $1$,
this implies that $B=X\begin{bmatrix}B^{\prime}&\\\ &1\end{bmatrix}X^{-1}$ for
some $(n-1)\times(n-1)$ matrix $B^{\prime}$ such that
$B^{\prime}(C^{\prime})^{t}=(C^{\prime})^{t}B^{\prime}$. (Here the lower right
entry has to be $1$, because our field is $\mathbb{F}_{2}$ and there is no
other non-zero element.) Then by Lemma 4.3, since $(C^{\prime})^{t}$ is
similar to a companion matrix, $B^{\prime}$ must be a polynomial of
$(C^{\prime})^{t}$. In particular, $B^{\prime}\in\mathbb{F}_{q}[C^{\prime}]$.
But $B$ is non-zero due to $B^{k}=C$, therefore $B^{\prime}$ is a power of
$C^{\prime}$. Consequently, $B$ is a power of $C$. So we are done. ∎

Finally, for the sake of completion, here is the criteria for when the
diameter in Proposition 4.2 and Proposition 4.6 is one.

######  Proposition 4.7.

In Proposition 4.2, the diameter of each connected component is $1$ if and
only if $q-1$ is a prime power and $\frac{q^{n}-1}{q-1}$ is a prime.
Similarly, in Proposition 4.6, the diameter of each connected component is $1$
if and only if $2^{n-1}-1$ is a prime.

###### Proof.

In either case, the connected component is made of powers of the same element.
So this follows by the property of cyclic groups below in Lemma 4.8. ∎

######  Lemma 4.8.

Let $q$ be a power of a prime $p$, and pick any positive integer $n\geq 3$. In
a cyclic group $G$ with $q^{n}-1$ elements, if we can find two subgroups $H,K$
such that neither contains the other, and neither is the subgroup whose order
divides $q-1$, then $q-1$ is a prime power and $\frac{q^{n}-1}{q-1}$ is a
prime, and this condition is necessary and sufficient.

###### Proof.

Let $x$ be a generator of $G$. Let us write the group operation in $G$
multiplicatively.

Suppose $q-1$ is not a prime power. Then we can find distinct prime factors
$p_{1},p_{2}$ of $q-1$, and the elements $x^{p_{1}},x^{p_{2}}$ would
respectively generate subgroups $H,K$ that does not contain each other. Since
$p_{i}<q-1\leq\frac{q^{n}-1}{q-1}$ for $i=1,2$, neither $H$ nor $K$ can have
order dividing $q-1$.

Now suppose $q-1$ is a power of a prime $p_{1}$, but $\frac{q^{n}-1}{q-1}$ is
not a prime. Pick any prime factor $p_{2}$ of $\frac{q^{n}-1}{q-1}$. If
$p_{1}=p_{2}$, then $q^{n}-1$ is a prime power. By Lemma 2.2, this means $q=3$
and $n=2$. So this cannot happen when $n\geq 3$. Now suppose $p_{1}\neq
p_{2}$. Then again $x^{p_{1}},x^{p_{2}}$ would respectively generate subgroups
$H,K$ that does not contain each other. Now obviously $p_{1}\leq
q-1\leq\frac{q^{n}-1}{q-1}$, but since $\frac{q^{n}-1}{q-1}$ is not prime, we
have $p_{1}<\frac{q^{n}-1}{q-1}$. At the same time, since
$\frac{q^{n}-1}{q-1}$ is not prime, its factor $p_{2}$ must also be strictly
less than $\frac{q^{n}-1}{q-1}$. So again neither $H$ nor $K$ can have $q-1$
elements.

Finally, suppose $q-1$ is a power of a prime $p_{1}$, and
$p_{2}=\frac{q^{n}-1}{q-1}$ is a prime. Then the order of $G$ is $p_{2}$ times
a power of $p_{1}$. Then for any two subgroups $H,K$ of $G$ whose order do not
divide $q-1$, then $p_{2}$ must divide both of their orders. Hence their index
must be powers of $p_{1}$. In a cyclic group, this means one subgroup must
contain the other. ∎

##  5 The connectivity of the projectively reduced power graphs of
$\mathrm{GL}_{n}(q)$

###  5.1 Overview

We want to study the connectivity of the projectively reduced power graphs of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$. Our strategy is to connect most element of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ to (Jordan) pivot matrices, with exceptions
outlined in section 4. Since we are dealing with the projectively reduced
power graph, we must avoid the center of $\mathrm{GL}_{n}(\mathbb{F}_{q})$,
i.e., scalar multiples of the identity matrix. Hence we make the following
definition.

######  Definition 5.1.

For a matrix $A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$, its projective order is
the multiplicative order of the image of $A$ in
$\mathrm{PGL}_{n}(\mathbb{F}_{q})$.

This concept is useful to understand the generalized Jordan canonical form of
$A$.

######  Lemma 5.2.

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.

###### Proof.

Suppose $A^{k}=\lambda I$ for some $k$ coprime to $p$ and
$\lambda\in\mathbb{F}_{q}^{*}$. Then the minimal polynomial of $A$ is a factor
of $f(x)=x^{k}-\lambda$. Since $k$ is coprime to $p$, the polynomial $f(x)$ is
separable. Hence the minimal polynomial of $A$ is separable, and our statement
follows. ∎

Given any matrix, by raising it to some power, we can obtian a matrix whose
projective order is a prime number. In fact, we can also require that this
matrix also has prime-power multiplicative order.

######  Lemma 5.3.

If $p_{0}$ is a prime number dividing the projective order of a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$, then $A$ has a power $A^{\prime}$ whose
multiplicative order is a power of $p_{0}$, and projective order is exactly
$p_{0}$.

###### Proof.

Let the projective order of $A$ be $mp_{0}^{k}$ for a positive integer $m$
coprime to $p_{0}$, and a positive integer $k$. Let the multiplicative order
of $A$ be $m^{\prime}p_{0}^{k^{\prime}}$ for a positive integer $m$ coprime to
$p_{0}$, and a positive integer $k$. Note that $m$ must divide $m^{\prime}$
and we must have $1\leq k\leq k^{\prime}$.

Now set $A^{\prime}=A^{m^{\prime}p_{0}^{k-1}}$. Then $A^{\prime}$ has
multiplicative order $p_{0}^{k^{\prime}-k+1}$, and projective order $p_{0}$
exactly. ∎

We can now discuss how a matrix in the projectively reduced graph of
$\mathrm{GL}_{n}(\mathbb{F}_{q})$ could have a path to a pivot or Jordan pivot
matrix.

When $q\neq 2$ and $n\geq 3$, the path towards a pivot matrix is outlined in
Figure 1. (Here $A$ is a generic matrix in $\mathrm{GL}_{n}(\mathbb{F}_{q})$
and not a scalar multiple of identity. $p$ is the characteristic of the field
$\mathbb{F}_{q}$.)

When $q=2$ and $n\geq 6$, the path towards a Jordan pivot matrix is outlined
in Figure 2.

Does $p$ divide the projective order of $A$? The minimal polynomial of $A$ has
degree $n$ and $n\leq q$. No path to pivot, $A$ must be described by
Proposition 4.1 Distance to pivot $\leq 3$ by Proposition 5.6 Is the
characteristic polynomial of $A$ reducible? Is $n$ prime? No path to pivot,
$A$ must be described by Proposition 4.2 If $q=3,n=4$, distance to pivot $\leq
6$, otherwise distance $\leq 4$ by Proposition 5.9 Are $q-1$ and the
projective order of $A$ both powers of the same prime? Distance to pivot $\leq
3$ by Proposition 5.8 Is $A$ diagonalizable over $\mathbb{F}_{q}$? If
$q=3,n=4$, distance to pivot $\leq 5$, otherwise distance $\leq 4$ by
Proposition 5.12 Is $q$ even? Distance to pivot $\leq 1$, by Proposition 5.10
Does $A$ have $n$ distinct eigenvalues? Distance to pivot $\leq 4$, by
Proposition 5.11 No path to pivot, $A$ must be described by Proposition 4.4
YesNoYesNoNoYesYesNoNoYesNoYesNoYesNoYes Figure 1: Path to pivot matrices when
$q\neq 2$ Is the multiplicative order of $A$ even? Distance to pivot $\leq 5$
by Proposition 5.13 Does the characteristic polynomial of $A$ has an
irreducible factor of degree $n$ or $n-1$? Is the degree of this irreducible
factor a composite number? Distance to pivot $\leq 6$ by Proposition 5.20 No
path to pivot, $A$ must be described by Proposition 4.2 or Proposition 4.6 Is
the multiplicative order of $A$ a composite number? Distance to pivot $\leq 5$
by Proposition 5.18 Is one plus the multiplicative order of $A$ a power of
two? Distance to pivot $\leq 4$ by Proposition 5.15 Does $A$ have the same
minimal polynomial and characteristic polynomial? Distance to pivot $\leq 6$
by Proposition 5.17 No path to pivot, $A$ must be described by Proposition 4.5
YesNoYesNoYesNoYesNoNoYesNoYes Figure 2: Path to pivot matrices when $q=2$

In particular, we have the following results.

######  Proposition 5.4.

We have the following connection pattern in the projectively reduced power
graph for $\mathrm{GL}_{n}(\mathbb{F}_{q})$.

  1. 1.

If $q=2$ and $n\geq 6$, then all matrices in
$\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ must
either have a distance at most $6$ to a Jordan pivot matrix, or have no path
to pivot matrices.

  2. 2.

If $q=3$ and $n=4$, then all matrices in
$\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ must
either have a distance at most $6$ to a pivot matrix, or have no path to pivot
matrices.

  3. 3.

If $n\geq 3$ and we are not in the cases above, then all matrices in
$\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ must
either have a distance at most $4$ to a pivot matrix, or have no path to pivot
matrices.

  4. 4.

If $q\neq 2$ and $n\geq 3$, and a matrix in
$\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ has no
path to a pivot matrix, then it must be as described in Proposition 4.1,
Proposition 4.2, and Proposition 4.4.

  5. 5.

If $q=2$ and $n\geq 6$, and a matrix in
$\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ has no
path to a pivot matrix, then it must be as described in Proposition 4.2,
Proposition 4.4, Proposition 4.5, and Proposition 4.6.

###  5.2 When $q\neq 2$

We first deal with the case when the characteristic $p$ of $\mathbb{F}_{q}$
divides the projective order of $A$.

######  Lemma 5.5.

Let $q$ be a power of a prime $p$, and let $n\geq 2$. For an $n\times n$
matrix $A$ over $\mathbb{F}_{q}$, if $p$ divides the projective order of $A$,
then $A$ has a power $A^{\prime}$ whose minimal polynomial is $(x-1)^{k}$ for
some $2\leq k\leq p$.

###### Proof.

By Lemma 5.3, $A$ has a power $A^{\prime}$ whose projective order is $p$, and
its multiplicative order is a power of $p$.

Suppose $(A^{\prime})^{p}=\lambda I$ for some $\lambda\in\mathbb{F}_{q}^{*}$.
Then the minimal polynomial of $A^{\prime}$ must divide the polynomial
$f(x)=x^{p}-\lambda$. Since $p$ is the characteristic of the field
$\mathbb{F}_{q}$, we can find $\mu\in\mathbb{F}_{q}$ such that
$\mu^{p}=\lambda$. Then $f(x)=x^{p}-\mu^{p}=(x-\mu)^{p}$. So the minimal
polynomial of $A^{\prime}$ is a power of $x-\mu$ with degree at most $p$.

Furthermore, since the multiplicative order of $A^{\prime}$ is a power of $p$,
its eigenvalue $\mu$ must also have multiplicative order a power of $p$ in the
group $\mathbb{F}_{q}^{*}$. But since the group $\mathbb{F}_{q}^{*}$ has $q-1$
elements, which is coprime to $p$, therefore $\mu=1$. So we are done. ∎

######  Proposition 5.6.

For any power $q\neq 2$ of a prime $p$, and let $n\geq 2$, suppose $p$ divides
the projective order of a matrix $A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$. Then
either $A$ has distance at most $3$ to a pivot matrix, or $A$ has not path to
any pivot matrix, and $A$ must be as described in Proposition 4.1.

###### Proof.

By Lemma 5.5, $A$ has a power $A^{\prime}$ whose minimal polynomial is
$(x-1)^{k}$ for some $2\leq k\leq p$. So in the generalized Jordan canonical
form of $A^{\prime}$, all diagonal blocks are of the form
$\begin{bmatrix}1&1&&\\\ &\ddots&\ddots&\\\ &&\ddots&1\\\ &&&1\end{bmatrix}$,
and the size of each block is at most $p\times p$.

Suppose $A^{\prime}$ has at least two such blocks. Say
$A^{\prime}=X\begin{bmatrix}J&\\\ &A^{\prime\prime}\end{bmatrix}X^{-1}$ for
some invertible $X$, where $J=\begin{bmatrix}1&1&&\\\ &\ddots&\ddots&\\\
&&\ddots&1\\\ &&&1\end{bmatrix}$ is at most $p\times p$, and
$A^{\prime\prime}$ also has minimal polynomial $(x-1)^{k^{\prime}}$ for some
$2\leq k^{\prime}\leq p$. In particular, $J^{p}$ and $(A^{\prime\prime})^{p}$
are both identity matrices (maybe with different size).

Pick any $x\neq 1\in\mathbb{F}_{q}^{*}$. Consider $B=X\begin{bmatrix}xJ&\\\
&A^{\prime\prime}\end{bmatrix}X^{-1}$. Then $B^{q}=X\begin{bmatrix}x^{q}I&\\\
&I\end{bmatrix}X^{-1}=X\begin{bmatrix}xI&\\\ &I\end{bmatrix}X^{-1}$ is a pivot
matrix. On the other hand, $B^{(q-1)^{2}}=X\begin{bmatrix}J&\\\
&A^{\prime\prime}\end{bmatrix}X^{-1}=A^{\prime}$. So a power of a root of
$A^{\prime}$ is a pivot matrix. So $A$ has distance at most $3$ to a pivot
matrix.

Now suppose $A^{\prime}$ is similar to a single block $\begin{bmatrix}1&1&&\\\
&\ddots&\ddots&\\\ &&\ddots&1\\\ &&&1\end{bmatrix}$, and the size of this
block is at most $p\times p$. Then immediately we have $n\leq p$, and
$A^{\prime}$ must be as described in Proposition 4.1. Since $A$ and
$A^{\prime}$ must be in the same connected component, $A$ must also be as
described in Proposition 4.1. ∎

As we can see, when $q\neq 2$ and $p$ divides the projective order of $A$,
then the only possible obstruction is from Proposition 4.1.

we now deal with matrices whose projective order is coprime to the
characteristic of the base field. The path to a pivot matrix would usually go
through a middle matrix, as described in Lemma 5.7.

######  Lemma 5.7.

Let $q\neq 2$ be a power of a prime $p$, and let $n\geq 2$. Suppose a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ has prime projective order $p_{1}\neq
p$, and its multiplicative order is also a power of $p_{1}$. Furthermore,
suppose $q-1$ is not a power of $p_{1}$, say $p_{0}$ is another prime factor
of $q-1$. Finally, suppose that the characteristic polynomial of $A$ is
reducible. Then $A$ has distance at most $2$ to a pivot matrix with
multiplicative order $p_{0}$.

###### Proof.

Since we have $p_{1}\neq p$, by Lemma 5.2, $A=X\begin{bmatrix}C_{1}&&\\\
&\ddots&\\\ &&C_{t}\end{bmatrix}X^{-1}$ for some invertible $X$, where
$C_{1},\dots,C_{t}$ are companion matrices to various irreducible polynomials
over $\mathbb{F}_{q}$. Since the characteristic polynomial of $A$ is not
irreducible, we know that $t\geq 2$. By Corollary 2.6, we can find a positive
integer $k$ depending only on $p_{1}$ and $q$, such that all $C_{i}$ are
either $1\times 1$ or $k\times k$.

For each $i$, let $m_{i}$ be the multiplicative order of the block $C_{i}$.
Then $m_{i}$ must divide the multiplicative order of $A$, hence it is a power
of $p_{1}$.

Since $q-1$ is not a power of $p_{1}$, we can find a prime factor $p_{0}$ of
$q-1$ distinct from $p_{1}$. Then $p_{0}$ is also a factor of $q^{k}-1$, and
it is coprime to $m_{i}$. If $C_{i}$ is $k\times k$, then by Lemma 2.3,
$m_{i}$ is a factor of $q^{k}-1$. Therefore, $p_{0}m_{i}$ is a factor of
$q^{k}-1$. By Lemma 2.7, this means $C_{i}$ must have a $p_{0}$-th root
$C^{\prime}_{i}$ whose multiplicative order is $p_{0}m_{i}$. Similarly, if
$C_{i}$ is $1\times 1$, then $p_{0}p_{1}$ is a factor of $q-1$, and again
$C_{i}$ must have a $p_{0}$-th root $C^{\prime}_{i}$ whose multiplicative
order is $p_{0}m_{i}$.

Since $p_{0}$ divides $q-1$, we can find $x\neq 1\in\mathbb{F}_{q}^{*}$ such
that $x^{p_{0}}=1$. Let $m$ be the multiplicative order of $A$ which is the
least common multiples of all $m_{i}$, and hence coprime to $p_{0}$. Then
$(C^{\prime}_{i})^{m}$ will have multiplicative order $p_{0}$, a factor of
$q-1$. By Corollary 2.5, $(C^{\prime}_{i})^{m}=x^{d_{i}}I$ for some integer
$d_{i}$.

Since $m$ is coprime to $p_{0}$, we can pick a positive integer $m^{\prime}$
such that $mm^{\prime}$ is $1$ modulus $p_{0}$. Then we have a path in the
projectively reduced power graph of $\mathrm{GL}_{n}(\mathbb{F}_{q})$.

$\displaystyle A=$ $\displaystyle X\begin{bmatrix}C_{1}&&\\\ &\ddots&\\\
&&C_{t}\end{bmatrix}X^{-1}$ $\displaystyle\xrightarrow{\text{$p_{0}$-th
root}}$ $\displaystyle
X\begin{bmatrix}x^{(1-d_{1})m^{\prime}}C^{\prime}_{1}&&&\\\
&x^{-d_{2}m^{\prime}}C^{\prime}_{2}&&\\\ &&\ddots&\\\
&&&x^{-d_{t}m^{\prime}}C^{\prime}_{t}\end{bmatrix}X^{-1}$
$\displaystyle\xrightarrow{\text{$m$-th power}}$ $\displaystyle
X\begin{bmatrix}xI&&&\\\ &I&&\\\ &&\ddots&\\\ &&&I\end{bmatrix}X^{-1}.$

The last matrix here is a pivot matrix, so we are done. ∎

This immediately shows that many matrices are connected to pivot matrices by
some short path.

######  Proposition 5.8.

Let $q\neq 2$ be a power of a prime $p$, and let $n\geq 2$. Suppose the
characteristic polynomial of a matrix $A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ is
reducible, and we can find a prime $p_{1}$ dividing the projective order of
$A$, such that $q-1$ is not a power of $p_{1}$. Then $A$ has distance at most
$3$ to a pivot matrix.

###### Proof.

By Lemma 5.3, $A$ has a power $A^{\prime}$ with projective order $p_{1}$, and
multiplicative order a power of $p_{1}$. Since the characteristic polynomial
of $A$ is reducible, the characteristic polynomial of $A^{\prime}$ must also
be reducible. Then we are done by Lemma 5.7 above. ∎

We are left with only two situations: when the characteristic polynomial of
$A$ is irreducible, or when the projective order of $A$ and $q-1$ are both
powers of the same prime.

If the characteristic polynomial of an $n\times n$ matrix $A$ is irreducible,
and $n$ is prime, then this is exactly the situation as described in
Proposition 4.2. If $n$ is not prime, then the situation is described by
Proposition 5.9 below.

######  Proposition 5.9.

Let $q\neq 2$ be a power of a prime $p$, and let $n$ be a composite number.
Suppose a matrix $A\in\mathrm{GL}_{n}(\mathbb{F}_{q})$ has projective order
coprime to $p$, and its characteristic polynomial is irreducible. Then either
$A$ has distance at most $4$ to a pivot matrix, or $q=3$ and $n=4$ and $A$ has
distance at most $6$ to a pivot matrix.

###### Proof.

First let us suppose that $q\neq 3$ or $n\neq 4$.

If $q=3$ but $n\neq 4$, then we can pick a proper factor $k\geq 3$ of $n$. If
$q\neq 3$, pick any proper factor $k\geq 2$ of $n$. Then by Lemma 2.2, either
way, we can find a prime factor $p_{1}$ of $q^{k}-1$ that does not divide
$q-1$.

By Lemma 2.3, since $A$ has irreducible characteristic polynomial,
$\mathbb{F}_{q}[A]$ is a field. So $A$ has a root $A^{\prime}$ which is a
multiplicative generator of $\mathbb{F}_{q}[A]$. Since $p_{1}$ divides
$q^{k}-1$, it also divides $q^{n}-1$. So $p_{1}$ divides the multiplicative
order of $A^{\prime}$. So $A^{\prime}$ has a power $B$ with multiplicative
order $p_{1}$. But since $p_{1}$ does not divide $q-1$, $B$ is not a scalar
multiple of identity. Hence $B$ has projective order exactly $p_{1}$.

Agains since $p_{1}$ divides $q^{k}-1$, by Lemma 2.6, the characteristic
polynomial of $B$ cannot be irreducible. Hence by Lemma 5.7, $B$ has distance
at most $2$ to some pivot matrix. Hence $A$ has distance at most $4$ to some
pivot matrix.

Now let us consider the case when $q=3$ and $n=4$. Again by Lemma 2.3, since
$A$ has irreducible characteristic polynomial, $\mathbb{F}_{q}[A]$ is a field.
So any multiplicative generator of $\mathbb{F}_{q}[A]$ is a root of $A$. We
can pick a multiplicative generator $A^{\prime}$ of $\mathbb{F}_{q}[A]$ which
has multiplicative order $80$. Since $A^{\prime}$ is a root of $A$, it is also
similar to the companion matrix of some polynomials. Now $(A^{\prime})^{2}0$
has multiplicative order $4$, which is not a factor of $q-1$, but a factor of
$q^{2}-1$. So by Lemma 2.4, the minimal polynomial of $(A^{\prime})^{2}0$ is
irreducible with degree $2$. In particular, $(A^{\prime})^{20}$ must be
similar to $\begin{bmatrix}C&\\\ &C\end{bmatrix}$ for some companion matrix
$C$ to some irreducible polynomial. Over $\mathbb{F}_{3}$, it is easy to see
that there is only one such polynomial, so we have $C=\begin{bmatrix}0&-1\\\
1&0\end{bmatrix}$.

Now $\begin{bmatrix}C&\\\ &C\end{bmatrix}$ has a $9$-th root
$\begin{bmatrix}C&I\\\ &C\end{bmatrix}$, whose fourth power is
$\begin{bmatrix}I&-C\\\ &I\end{bmatrix}$, which has a $4$-th root
$\begin{bmatrix}1&0&0&1\\\ &-1&1&0\\\ &&-1&0\\\ &&&1\end{bmatrix}$, whose
third power is $\begin{bmatrix}1&&&\\\ &-1&&\\\ &&-1&\\\ &&&1\end{bmatrix}$, a
pivot matrix. So $(A^{\prime})^{2}0$ has distance at most $4$ to a pivot
matrix.

All in all, $A$ has distance at most $2$ to $(A^{\prime})^{20}$, which has
distance at most $4$ to a pivot matrix. So we are done. ∎

For the rest of this section, we can assume that the projective order of $A$
and $q-1$ are both powers of the same prime. However, if $q-1$ is a prime
power, then by Lemma 2.1, either $q=9$, or $q$ is a Fermat prime, or $q$ is a
power of $2$ with $q-1$ prime.

First we deal with the diagonalizable case.

######  Proposition 5.10.

Let $q$ be Fermat prime or $9$, and let $n\geq 2$. Suppose a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is
diagonalizable over $\mathbb{F}_{q}$, then it has distance at most $1$ to a
pivot matrix.

###### Proof.

Suppose $A$ is diagonalizable with eigenvalues
$\lambda_{1},\dots,\lambda_{n}\in\mathbb{F}_{q}$, and suppose $A$ has
projective order $m\neq 1$. Then $m$ divides $q-1$ and thus it is a power of
$2$. So $A^{\frac{m}{2}}$ has eigenvalues
$\lambda_{1}^{\frac{m}{2}},\dots,\lambda_{n}^{\frac{m}{2}}$, and all these
eigenvalues have the same square. However, in the cyclic group
$\mathbb{F}_{q}^{*}$, each element can have at most two square roots. Hence
$\lambda_{1}^{\frac{m}{2}},\dots,\lambda_{n}^{\frac{m}{2}}$ can take only two
possible values. Since $A^{\frac{m}{2}}$ is not a scalar multiple of identity,
it must be a pivot matrix. ∎

######  Proposition 5.11.

Let $q$ be a power of $2$ such that $q-1$ is prime, and let $n\geq 2$. Suppose
a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is
diagonalizable over $\mathbb{F}_{q}$ but not all eigenvalues are distinct,
then it has distance at most $4$ to a pivot matrix.

###### Proof.

Suppose $\lambda$ is a repeating eigenvalue for $A$. Then we have
$A=X\begin{bmatrix}C_{1}&\\\ &C_{2}\end{bmatrix}X^{-1}$ for some invertible
$X$, where $C_{1}=\begin{bmatrix}\lambda&\\\ &\lambda\end{bmatrix}$ and
$C_{2}$ is diagonal.

By Lemma 2.2, we can find a prime factor $p_{1}$ of $q^{2}-1$ coprime to
$q-1$. Since $C_{1}$ has multiplicative order dividing $q-1$, therefore
$p_{1}(q-1)$ divides $q^{2}-1$. Hence by Lemma 2.9, we can find a matrix
$C^{\prime}_{1}$ which is a $p_{1}$-th root of $C_{1}$, and has $p_{1}$
dividing its multiplicative order. Note that since $p_{1}$ and $q-1$ are
coprime, $p_{1}$ must also divide the projective order of $C^{\prime}_{1}$.

Since $q-1$ and $p_{1}$ are coprime, each diagonal entry of $C_{2}$ has a
unique $p_{1}$-th root. So $C_{2}$ has a $p_{1}$-th root $C^{\prime}_{2}$.
Therefore $A$ has a $p_{1}$-th root
$A^{\prime}=X\begin{bmatrix}C^{\prime}_{1}&\\\
&C^{\prime}_{2}\end{bmatrix}X^{-1}$, and since $p_{1}$ divides the projective
order of $C^{\prime}_{1}$, it must also divide the projective order of
$A^{\prime}$. Furthermore, since $A^{\prime}$ is similar to a block diagonal
matrix, its characteristic polynomial is reducible. So by Proposition 5.8,
$A^{\prime}$ has distance at most $3$ to a pivot matrix. Hence $A$ has
distance at most $4$ to a pivot matrix. ∎

Note that if $q$ be a power of $2$ such that $q-1$ is prime, and a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is
diagonalizable over $\mathbb{F}_{q}$ with $n$ distinct eigenvalues. Then we
must have $n<q$, and this is exactly the situation described by Proposition
4.4. So we have completed all discussions on diagonalizable matrices.

We now sum up the remaining cases.

######  Proposition 5.12.

Let $q$ be a power of a prime $p$, and $q-1$ is a power of a prime $p_{0}$,
and let $n\geq 2$. Suppose a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{q})-Z(\mathrm{GL}_{n}(\mathbb{F}_{q}))$ is
not diagonalizable, has reducible characteristic polynomial, and its
projective order is also a power of $p_{0}$. Then either $A$ has distance at
most $4$ to a pivot matrix, or $q=3$ and $n=4$ and $A$ has distance at most
$5$ to a pivot matrix.

###### Proof.

Since the projective order of $A$ is coprime to $p$, by Lemma 5.2, the
generalized Jordan canonical form of $A$ is block diagonal, with companion
matrices for irreducible polynomials on its diagonal. Since $A$ is not
diagonalizable, one of these diagonal blocks $C_{1}$ is not $1\times 1$.

Since $A$ has reducible characteristic polynomial, we must have
$A=X\begin{bmatrix}C_{1}&\\\ &C_{2}\end{bmatrix}X^{-1}$ for some invertible
$X$, where $C_{2}$ is block diagonal, with companion matrices for irreducible
polynomials on its diagonal.

Suppose $C_{1}$ is $k\times k$. If $q\neq 3$, then by Lemma 2.2, we can find a
prime factor $p_{1}$ of $q^{k}-1$ coprime to $q-1$. Since the projective order
of $C_{1}$ and all diagonal blocks of $C_{2}$ are powers of $p_{0}$, by Lemma
2.8, $C_{1},C_{2}$ have $p_{1}$-th root $C^{\prime}_{1},C^{\prime}_{2}$.
Furthremore, since $p_{1},p_{0}$ are distinct primes dividing $q^{k}-1$, by
Lemma 2.8 again, we can choose $C^{\prime}_{1}$ such that $p_{1}$ divides its
multiplicative order. Note that since $p_{1}$ and $q-1$ are coprime, $p_{1}$
must also divide the projective order of $C^{\prime}_{1}$.

So $A$ has a $p_{1}$-th root $A^{\prime}=X\begin{bmatrix}C^{\prime}_{1}&\\\
&C^{\prime}_{2}\end{bmatrix}X^{-1}$ with reducible characteristic polynomial,
and $p_{1}$ divides the projective order of $A^{\prime}$. Then by Proposition
5.8, $A^{\prime}$ has distance at most $3$ to a pivot matrix. Hence $A$ has
distance at most $4$ to a pivot matrix.

Now suppose $q=3$. Suppose in the diagonal blocks of the generalized Jordan
canonical form of $A$, at least one block $C_{1}$ is $k\times k$ for some
$k\geq 3$. Then again by Lemma 2.2, we can find a prime factor $p_{1}$ of
$q^{k}-1$ coprime to $q-1$. The rest of the argument is identical to above.

Now suppose $q=3$, but all diagonal blocks of the generalized Jordan canonical
form of $A$ are either $1\times 1$ or $2\times 2$. Suppose $A$ has
multiplicative order $m$, which must be a power of $2$. If
$A^{\frac{m}{2}}\neq-I$, then it must be a diagonalizable matrix with
eigenvalues $1$ and $-1$, hence it is a pivot matrix. If $A^{\frac{m}{2}}=-I$,
then for the matrix $A^{\prime}=A^{\frac{m}{4}}$, its generalized Jordan
canonical form must have all diagonal blocks identical to
$\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}$.

If $n>4$, then again $A=X\begin{bmatrix}C_{1}&\\\ &C_{2}\end{bmatrix}X^{-1}$
where $C_{1},C_{2}$ are both block diagonal with all diagonal blocks identical
to $\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}$, but $C_{1}$ only have two
diagonal blocks while $C_{2}$ have $\frac{n-4}{2}$ diagonal blocks. Then by
Lemma 2.9, $C_{1}$ has a $5$-th root $C^{\prime}_{1}$, and $C^{\prime}_{1}$
have projective order a multiple of $5$. We also have $C_{2}$ as its own
$5$-th root. Hence $A$ has a $5$-th root
$A^{\prime}=X\begin{bmatrix}C^{\prime}_{1}&\\\ &C_{2}\end{bmatrix}X^{-1}$ with
reducible characteristic polynomial, and $5$ divides the projective order of
$A^{\prime}$. So again by Proposition 5.8, $A^{\prime}$ has distance at most
$3$ to a pivot matrix. Hence $A$ has distance at most $4$ to a pivot matrix.

Finally, the last case requires $n=4$. Then $A^{\prime}=A^{\frac{m}{4}}$ is
similar to a matrix which is block diagonal, and the two diagonal blocks are
both $\begin{bmatrix}0&-1\\\ 1&0\end{bmatrix}$. We have already encountered
this matrix in Proposition 5.9, and it has distance at most $4$ to a pivot
matrix. Hence $A$ has distance at most $5$ to a pivot matrix. ∎

###  5.3 When $q=2$

Now we turn to the case of $q=2$. Since there is no pivot matrix in this case,
we would connect matrices in
$\mathrm{GL}_{n}(\mathbb{F}_{2})-Z(\mathrm{GL}_{n}(\mathbb{F}_{2}))$ to Jordan
pivot matrices.

######  Proposition 5.13.

For $n\geq 6$, if $2$ divides the multiplicative order of a matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$, then $A$ has distance at most $5$ to a
Jordan pivot matrix.

###### Proof.

First, by Lemma 5.5, $A$ has a power $A^{\prime}$ whose generalized Jordan
canonical form is made of diagonal blocks of the form $\begin{bmatrix}1&1\\\
&1\end{bmatrix}$ or $\begin{bmatrix}1\end{bmatrix}$. If $n\geq 6$ (in fact
$n\geq 4$ is enough here), then either this Jordan canonical form has at least
two $1\times 1$ blocks, or it has at least two $2\times 2$ blocks.

Note that $\begin{bmatrix}1&1&&\\\ &1&&\\\ &&1&1\\\ &&&1\end{bmatrix}$ is
similar to $\begin{bmatrix}I_{2}&I_{2}\\\ &I_{2}\end{bmatrix}$. Therefore,
consider the generalized Jordan canonical form of $A^{\prime}$, we have
$A^{\prime}=X\begin{bmatrix}I_{2}&\\\ &A^{\prime\prime}\end{bmatrix}X^{-1}$ or
$X\begin{bmatrix}I_{2}&I_{2}&\\\ &I_{2}&\\\
&&A^{\prime\prime}\end{bmatrix}X^{-1}$ for some invertible $X$, where
$A^{\prime\prime}$ has multiplicative order exactly $2$.

Set $P=\begin{bmatrix}0&1\\\ 1&1\end{bmatrix}$ which has multiplicative order
$3$. Set $B=X\begin{bmatrix}P&\\\ &A^{\prime\prime}\end{bmatrix}X^{-1}$ or
$X\begin{bmatrix}P&P&\\\ &P&\\\ &&A^{\prime\prime}\end{bmatrix}X^{-1}$
respectively. Either way, we have $B^{3}=A^{\prime}$, $B^{6}=I_{n}$ and
$B^{4}=X\begin{bmatrix}P&\\\ &I_{n-2}\end{bmatrix}X^{-1}$ or
$X\begin{bmatrix}P&&\\\ &P&\\\ &&I_{n-4}\end{bmatrix}X^{-1}$. Let
$C=X\begin{bmatrix}I_{n-2}&\\\ &J\end{bmatrix}X^{-1}$ where
$J=\begin{bmatrix}1&1\\\ &1\end{bmatrix}$. Then as $n\geq 6$, $B^{4}$ must
commute with $C$, and hence $(B^{4}C)^{4}=B^{4}$ and $(B^{4}C)^{3}=C$.

Then we have the following path

$A\xrightarrow{\text{power}}A^{\prime}\xrightarrow{\text{$3$-rd
root}}B\xrightarrow{\text{$4$-th power}}B^{4}\xrightarrow{\text{$4$-th
root}}B^{4}C\xrightarrow{\text{$3$-rd power}}C.$

So we have reached a Jordan pivot matrix in $5$ steps. ∎

######  Lemma 5.14.

For $n\geq 4$, suppose a non-identity matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ has odd multiplicative order, and
$(x-1)^{2}$ is a factor of the characteristic polynomial $f(x)$ of $A$. Then
$A$ has distance at most $2$ to a Jordan pivot matrix.

###### Proof.

Since the projective order of $A$ is coprime to $2$, by Lemma 5.2, the
generalized Jordan canonical form of $A$ is block diagonal, with companion
matrices for irreducible polynomials on its diagonal. Since $(x-1)^{2}$ is a
factor of the characteristic polynomial $f(x)$ of $A$, therefore
$A=X\begin{bmatrix}I_{2}&\\\ &C\end{bmatrix}X^{-1}$ for some invertible $X$,
where $I_{2}$ is the $2\times 2$ identity matrix and $C$ has the same
multiplicative order as $A$.

Let $k$ be the multiplicative order of $A$. Since $k$ is an odd number,
therefore $A$ has a $(k+1)$-th root $A^{\prime}=X\begin{bmatrix}J&\\\
&C\end{bmatrix}X^{-1}$ where $J=\begin{bmatrix}1&1\\\ &1\end{bmatrix}$, and
$(A^{\prime})^{k}$ is a Jordan pivot matrix. So $A$ has distance at most $2$
to a Jordan pivot matrix. ∎

######  Proposition 5.15.

For $n\geq 6$, suppose the multiplicative order of a non-identity matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ is an odd prime $p$, $p+1$ is not a
power of $2$, and the characteristic polynomial of $A$ has no irreducible
factor of degree $n$ or $n-1$. Then $A$ has distance at most $4$ to a Jordan
pivot matrix.

###### Proof.

Let $m$ be the smallest positive integer such that $p$ divides $2^{m}-1$.
Since $p+1$ is not a power of $2$, this means that $2^{m}-1$ is a composite
number. In particular, by Lemma 2.1, $2^{m}-1$ cannot be a prime power. So we
can find a prime factor $p_{0}\neq p$ of $2^{m}-1$.

Since we must have $p\neq 2$, by Lemma 5.2, $A=X\begin{bmatrix}C_{1}&&\\\
&\ddots&\\\ &&C_{t}\end{bmatrix}X^{-1}$ for some invertible $X$, where
$C_{1},\dots,C_{t}$ are companion matrices to various irreducible polynomials
over $\mathbb{F}_{2}$. By Corollary 2.6, all $C_{i}$ are either $1\times 1$ or
$m\times m$. Since $A$ is not identity, one of these $C_{i}$ is $m\times m$.
Say $C_{1}$ is $m\times m$.

Now $\mathbb{F}_{2}[C_{1}]$ is a field with $2^{m}$ elements. So $C_{1}$ has a
$p_{0}$-th root $C^{\prime}_{1}$ with multiplicative order $pp_{0}$. For other
$C_{i}$, since each has multiplicative order $1$ or $p$, each has a $p_{0}$-th
root $C^{\prime}_{i}$ with multiplicative order $1$ or $p$. Hence $A$ has a
$p_{0}$-th root $A^{\prime}=X\begin{bmatrix}C^{\prime}_{1}&&\\\ &\ddots&\\\
&&C^{\prime}_{t}\end{bmatrix}X^{-1}$, which has multiplicative order $pp_{0}$.

Now, $(A^{\prime})^{p}=X\begin{bmatrix}(C^{\prime}_{1})^{p}&\\\
&I_{n-m}\end{bmatrix}X^{-1}$ has multiplicative order $p_{0}$. Since the
characteristic polynomial of $A$ has no irreducible factor of degree $n$ or
$n-1$, therefore $m\leq n-2$. So $(x-1)^{2}$ is a factor of the characteristic
polynomial $f(x)$ of $(A^{\prime})^{p}$. Hence by Lemma 5.14,
$(A^{\prime})^{p}$ has distance at most $2$ to a Jordan pivot matrix.
Therefore, $A$ has distance at most $4$ to a Jordan pivot matrix. ∎

######  Lemma 5.16.

For $n\geq 6$, suppose the multiplicative order of a non-identity matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ is an odd prime $p$, and $p+1=2^{m}$ for
some positive integer $m$. If the minimal polynomial and the characteristic
polynomial of $A$ are not the same, then either $A$ has distance at most $4$
to a Jordan pivot matrix, or $A$ is similar to $\begin{bmatrix}C&\\\
&C\end{bmatrix}$ or $\begin{bmatrix}C&&\\\ &C&\\\ &&1\end{bmatrix}$ for some
companion matrix $C$ to an irreducible polynomial.

###### Proof.

Since we must have $p\neq 2$, by Lemma 5.2, $A=X\begin{bmatrix}C_{1}&&\\\
&\ddots&\\\ &&C_{t}\end{bmatrix}X^{-1}$ for some invertible $X$, where
$C_{1},\dots,C_{t}$ are companion matrices to various irreducible polynomials
over $\mathbb{F}_{2}$. By Corollary 2.6, all $C_{i}$ are either $1\times 1$ or
$m\times m$. Since the minimal polynomial and the characteristic polynomial of
$A$ are not the same, two of these $C_{i}$ are identical. Say $C_{1}=C_{2}$.

If $C_{1},C_{2}$ are both $1\times 1$, then $(x-1)^{2}$ divides the
characteristic polynomial of $A$. Hence $A$ has distance at most $2$ to a
Jordan pivot matrix.

Now suppose $C_{1},C_{2}$ are both $m\times m$. Note that
$2^{2m}-1=(2^{m}-1)(2^{m}+1)$, and $2^{m}-1,2^{m}+1$ must be coprime. Hence we
can find a prime factor $p_{0}\neq p$ of $2^{m}+1$. By Lemma 2.9, we can find
a matrix $C^{\prime}$ such that $(C^{\prime})^{p_{0}}=\begin{bmatrix}C_{1}&\\\
&C_{2}\end{bmatrix}$ and $p_{0}$ divides the multiplicative order of
$C^{\prime}$.

For all $i>2$, since $p_{0}\neq p$, $C_{i}$ has a $p_{0}$-th root
$C^{\prime}_{i}$ by Lemma 2.8. So all in all, $A$ has a $p_{0}$-th root
$A^{\prime}=X\begin{bmatrix}C^{\prime}&&&\\\ &C^{\prime}_{3}&&\\\ &&\ddots&\\\
&&&C^{\prime}_{t}\end{bmatrix}X^{-1}$, and
$(A^{\prime})^{p}=X\begin{bmatrix}(C^{\prime})^{p}&\\\
&I_{n-2m}\end{bmatrix}X^{-1}$. Since $p_{0}\neq p$ divides the multiplicative
order of $C^{\prime}$, we see that $(A^{\prime})^{p}$ is not an identity
matrix.

Suppose that $A$ is not similar to $\begin{bmatrix}C&\\\ &C\end{bmatrix}$ or
$\begin{bmatrix}C&&\\\ &C&\\\ &&1\end{bmatrix}$ for some companion matrix $C$
to an irreducible polynomial. Then the matrix $\begin{bmatrix}C_{3}&&\\\
&\ddots&\\\ &&C_{t}\end{bmatrix}$ is at least $2\times 2$, and hence $n-2m\geq
2$. Therefore $(A^{\prime})^{p}$ satisfies the requirement of Lemma 5.14.
Hence $(A^{\prime})^{p}$ has distance at most $2$ to a Jordan pivot matrix,
and $A$ has distance at most $4$ to a Jordan pivot matrix. ∎

######  Proposition 5.17.

For $n\geq 6$, suppose the multiplicative order of a non-identity matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ is an odd prime $p$, and $p+1=2^{m}$ for
some positive integer $m$. If the minimal polynomial and the characteristic
polynomial of $A$ are not the same, then $A$ has distance at most $6$ to a
Jordan pivot matrix.

###### Proof.

By Lemma 5.16, we only need to consider the case when $A$ is similar to
$\begin{bmatrix}C&\\\ &C\end{bmatrix}$ or $\begin{bmatrix}C&&\\\ &C&\\\
&&1\end{bmatrix}$ for some $m\times m$ companion matrix $C$ to an irreducible
polynomial. Since $n\geq 6$, this implies that $m\geq 3$. So $3$ divides
$2^{2m}-1$ but $3\neq p$.

By Lemma 2.9, we can find a matrix $C^{\prime}$ such that
$(C^{\prime})^{3}=\begin{bmatrix}C&\\\ &C\end{bmatrix}$ and the multiplicative
order of $C^{\prime}$ is exactly $3p$. Therefore, if $A$ is similar to
$\begin{bmatrix}C&\\\ &C\end{bmatrix}$ or $\begin{bmatrix}C&&\\\ &C&\\\
&&1\end{bmatrix}$, then $A$ has a third root $A^{\prime}$ similar to
$C^{\prime}$ or $\begin{bmatrix}C^{\prime}&\\\ &1\end{bmatrix}$. In
particular, $A^{\prime}$ has multiplicative order $3p$, and $(A^{\prime})^{p}$
has multiplicative order $3$. Its minimal polynomial has degree at most $3$,
so it cannot equal to its characteristic polynomial.

Furthermore, since $3=2^{2}-1$, by Corollary 2.6, the generalized Jordan
canonical form of $(A^{\prime})^{p}$ must be block diagonal by $1\times 1$ or
$2\times 2$ blocks. Since $n\geq 6$, it cannot be similar to
$\begin{bmatrix}C^{\prime\prime}&\\\ &C^{\prime\prime}\end{bmatrix}$ or
$\begin{bmatrix}C^{\prime\prime}&&\\\ &C^{\prime\prime}&\\\ &&1\end{bmatrix}$
for some $2\times 2$ companion matrix $C^{\prime\prime}$ to an irreducible
polynomial. So by Lemma 5.16, $(A^{\prime})^{p}$ has distance at most $4$ to a
Jordan pivot matrix. Hence $A$ has distance at most $6$ to a Jordan pivot
matrix. ∎

Note that in the case above, if the minimal polynomial and the characteristic
polynomial of $A$ are the same, then this is exactly the case described by
Proposition 4.5.

######  Proposition 5.18.

For $n\geq 6$, suppose the multiplicative order of a non-identity matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ is an odd composite number, and the
characteristic polynomial of $A$ has no irreducible factor of degree $n$ or
$n-1$. Then $A$ has distance at most $5$ to a Jordan pivot matrix.

###### Proof.

Suppose the multiplicative order of $A$ has a prime factor $p$ such that $p+1$
is not a power of $2$, then $A$ has a power $A^{\prime}$ of multiplicative
order $p$. By Lemma 2.15, the characteristic polynomial of $A^{\prime}$ has no
irreducible factor of degree $n$ or $n-1$. Therefore, by Proposition 5.15,
$A^{\prime}$ has distance at most $4$ to a Jordan pivot matrix. So $A$ has
distance at most $5$ to a Jordan pivot matrix.

Now suppose all prime factors of the multiplicative order of $A$ are one less
than some powers of two. Say the multiplicative order of $A$ has a prime
factor $p=2^{m}-1$ for some positive integer $m$. Then $A$ has a power
$A^{\prime}$ of multiplicative order $p$.

By Lemma 5.2, $A=X\begin{bmatrix}C_{1}&&\\\ &\ddots&\\\
&&C_{t}\end{bmatrix}X^{-1}$ for some invertible $X$, where $C_{1},\dots,C_{t}$
are companion matrices to various irreducible polynomials over
$\mathbb{F}_{2}$. Let $k$ be the multiplicative order of $A$, then
$A^{\prime}=A^{\frac{k}{p}}=X\begin{bmatrix}C_{1}^{\frac{k}{p}}&&\\\
&\ddots&\\\ &&C_{t}^{\frac{k}{p}}\end{bmatrix}X^{-1}$.

Note that each $C_{i}^{\frac{k}{p}}$ has multiplicative order $1$ or
$p=2^{m}-1$. If all $C_{i}^{\frac{k}{p}}$ have irreducible characteristic
polynomials, then by Corollary 2.6, they all have size $1\times 1$ or $m\times
m$. But then $C_{i}$ must have multiplicative order dividing $1$ or
$p=2^{m}-1$. So $A$ has prime multiplicative order, contradiction. So for some
$C_{i}$, $C_{i}^{\frac{k}{p}}$ no longer has irreducible characteristic
polynomial. In particular, $A^{\prime}$ must have distinct minimal polynomial
and characteristic polynomial.

Suppose for contradiction that $A^{\prime}$ is similar to
$\begin{bmatrix}C&\\\ &C\end{bmatrix}$ or $\begin{bmatrix}C&&\\\ &C&\\\
&&1\end{bmatrix}$ for some companion matrix $C$ of some irreducible
polynomial. Since $C$ must have multiplicative order $p$, it must be $m\times
m$. Since the characteristic polynomial of $A$ has no irreducible factor of
degree $n$ or $n-1$, compare with the generalized Jordan canonical forms of
$A$ and of $A^{\prime}$, we can only have $A=\begin{bmatrix}C_{1}&\\\
&C_{2}\end{bmatrix}$ or $\begin{bmatrix}C_{1}&&\\\ &C_{2}&\\\
&&1\end{bmatrix}$, where $C_{1},C_{2}$ are both $m\times m$. But since
$p=2^{m}-1$, the multiplicative orders of $C_{1},C_{2}$ must divide $p$. So
again $A$ has prime multiplicative order, contradiction. So $A^{\prime}$ is
not similar to $\begin{bmatrix}C&\\\ &C\end{bmatrix}$ or
$\begin{bmatrix}C&&\\\ &C&\\\ &&1\end{bmatrix}$ for some companion matrix $C$
of some irreducible polynomial.

In conclusion, Lemma 5.16 must apply to $A^{\prime}$. So $A^{\prime}$ has
distance at most $4$ to a Jordan pivot matrix. Thus $A$ has distance at most
$5$ to a Jordan pivot matrix. ∎

######  Lemma 5.19.

For a compositite number $n\geq 6$, suppose the multiplicative order of a non-
identity matrix $A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ is an odd number. If the
characteristic polynomial of $A$ is irreducible, then $A$ has distance at most
$6$ to a Jordan pivot matrix.

###### Proof.

Since the characteristic polynomial of $A$ is irreducible, $\mathbb{F}_{q}[A]$
is a field with $q^{n}$ elements. Let $A^{\prime}$ be a multiplicative
generator of this field (and hence a root of $A$).

Since $n\geq 6$ is a composite number, let $m\geq 2$ be its smallest prime
factor, then $n\geq 3m\geq 2m+2$. Pick any prime factor $p$ dividing
$2^{m}-1$. Then $p$ also divides $2^{n}-1$, and therefore $A^{\prime}$ has a
power $A^{\prime\prime}$ whose multiplicative order is $p$. By Lemma 5.2,
$A^{\prime\prime}=X\begin{bmatrix}C_{1}&&\\\ &\ddots&\\\
&&C_{t}\end{bmatrix}X^{-1}$ for some invertible $X$, where $C_{1},\dots,C_{t}$
are companion matrices to various irreducible polynomials over
$\mathbb{F}_{q}$. Furthermore, since each $C_{i}$ has multiplicative order
dividing $p$, by Corollary 2.6, therefore it is either $1\times 1$ or $m\times
m$.

Since $n\geq 3m$, we must have $t\geq 3$, so the characteristic polynomial of
$A^{\prime\prime}$ cannot have irreducible factor of degree $n$ or $n-1$. If
$p\neq 2^{m}-1$, then by Proposition 5.15, $A^{\prime\prime}$ has distance at
most $4$ to a Jordan pivot matrix. Therefore $A$ has distance at most $6$ to a
Jordan pivot matrix.

If $p=2^{m}-1$, note that $n\geq 2m+2$, so $A^{\prime\prime}$ cannot be
similar to $\begin{bmatrix}C&\\\ &C\end{bmatrix}$ or $\begin{bmatrix}C&&\\\
&C&\\\ &&1\end{bmatrix}$ for some companion matrix $C$ of some irreducible
polynomial. Furthermore, $A^{\prime\prime}$ is a power of $A^{\prime}$, so by
Lemma 2.4, its minimal polynomial must be irreducible. So its minimal
polynomial and characteristic polynomial are different. Hence by Lemma 5.16,
$A^{\prime\prime}$ has distance at most $4$ to a Jordan pivot matrix.
Therefore $A$ has distance at most $6$ to a Jordan pivot matrix. ∎

######  Proposition 5.20.

For $n\geq 6$, suppose the multiplicative order of a non-identity matrix
$A\in\mathrm{GL}_{n}(\mathbb{F}_{2})$ is an odd number. If the characteristic
polynomial of $A$ has an irreducible of degree $n$ or $n-1$, and this degree
is a composite number, then $A$ has distance at most $6$ to a Jordan pivot
matrix.

###### Proof.

By Lemma 5.19, we only need to prove the case when the characteristic
polynomial of $A$ has an irreducible of degree $n-1$, and $n-1$ is a composite
number. Then the generalized Jordan canonical form of $A$ must be
$\begin{bmatrix}C&\\\ &1\end{bmatrix}$ where $C$ is a companion matrix to an
irreducible polynomial of degree $n-1$.

Since $n-1$ is a composite number, we cannot have $n=6$. So $n\geq 7$. Then
$C$ has irreducible characteristic polynomial, and its dimension is $n-1\geq
6$. Therefore by Lemma 5.19, $C$ has distance at most $6$ to a Jordan pivot
matrix. Since $A$ is similar to $\begin{bmatrix}C&\\\ &1\end{bmatrix}$ and $1$
is its own power and root, $A$ has distance at most $6$ to a Jordan pivot
matrix. ∎

## 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.
  * CGS [09] Ivy Chakrabarty, Shamik Ghosh, and MK Sen.  Undirected power graphs of semigroups.  In Semigroup Forum, volume 78, pages 410–426. Springer, 2009.
  * DEFD [14] Alireza Doostabadi, Ahmad Erfanian, and M Farrokhi DG.  On power graphs of finite groups with forbidden induced subgraphs.  Indagationes Mathematicae, 25(3):525–533, 2014.
  * DF [91] David S Dummit and Richard M Foote.  Abstract algebra, volume 1999.  Prentice Hall Englewood Cliffs, NJ, 1991.
  * KQ [00] AV Kelarev and SJ Quinn.  A combinatorial property and power graphs of groups.  Contributions to general algebra, 12(58):3–6, 2000.
  * KSCC [21] Ajay Kumar, Lavanya Selvaganesh, Peter J Cameron, and T Tamizh Chelvam.  Recent developments on the power graph of finite groups–a survey.  AKCE International Journal of Graphs and Combinatorics, 18(2):65–94, 2021.
  * Mih [04] Preda Mihăilescu.  Primary cyclotomic units and a proof of catalans conjecture.  2004\.
  * Pan [20] Ramesh Prasad Panda.  A combinatorial characterization of finite groups of prime exponent.  Indagationes Mathematicae, 31(1):1–6, 2020.
  * Per [52] Sam Perlis.  Theory of matrices.  1952\.
  * Rob [70] DW Robinson.  The generalized jordan canonical form.  The American Mathematical Monthly, 77(4):392–395, 1970.
  * TCS [13] T Tamizh Chelvam and M Sattanathan.  Power graph of finite abelian groups.  Algebra and Discrete Mathematics, 2013.