The Inverse Characteristic Polynomial Problem for Graphs over Finite Fields

Abstract

Let $\mathbb{F}$ be a finite field, and let $G$ be a graph on $n$ vertices. We study the possible characteristic polynomials that may be realized by matrices $A$ over a finite field such that the graph of $A$ is $G$. We focus mainly on the case $G$ is a tree $T$, not only because trees are computationally simpler, but also because the theory of eigenvalue multiplicities is much better understood for trees than it is for general graphs. We demonstrate the applications to this problem by branch duplication and the recently developed geometric Parter-Wiener, etc. theory. We end with a list of several conjectures which should pave the way for future study.

1. Introduction

Let $\mathbb{F}$ be a field. We say that a combinatorially symmetric matrix $A=\left(a_{\mathit{ij}}\right)\in M_n\left(\mathbb{F}\right)$ has (undirected, simple) graph $G$ if $a_{\mathit{ij}}\ne 0$ precisely when $\left\{i,j\right\}$ is an edge of $G$ (no restriction is placed upon the diagonal entries of $A$, except that they are in $\mathbb{F}$). We write $G\left(A\right)=G$ to indicate the graph of $A$ is $G$. By $\mathcal{F}\left(G\right)$ we mean $\left\{A\in M_n\left(\mathbb{F}\right):G\left(A\right)=G\right\}$. Each $A\in \mathcal{F}\left(G\right)$ has a monic characteristic polynomial of degree $n$ with coefficients in $\mathbb{F}$. The inverse characteristic polynomial problem over $\mathbb{F}$ for $G$ is to determine the set

$$P\left(\mathbb{F},G\right)=\left\{p\left(x\right)=det\left(\mathit{xI}-A\right)|A\in \mathcal{F}\left(G\right)\right\}.$$E1

If we denote the set of all monic, degree $n$ polynomials over $\mathbb{F}$ by $P_n\left(\mathbb{F}\right)$, we may ask which $n$-vertex graphs G satisfy $P\left(\mathbb{F},G\right)=P_n\left(\mathbb{F}\right)$; we call such $G$ constructible. If a graph $G$ is not constructible, we say $G$ is non-constructible.

Our primary interest here is the case in which $\mathbb{F}$ is a finite field ${\mathbb{F}}_q$, the finite field of order $q$ (where $q$ is any prime power), in which case the number of monic degree $n$ polynomials over ${\mathbb{F}}_q$, denoted $\mid P_n\left({\mathbb{F}}_q\right)\mid$, is given by $\mid P_n\left({\mathbb{F}}_q\right)\mid ={\left|{\mathbb{F}}_q\right|}^n=q^n$. Although we are interested in all graphs, we focus primarily on trees. We present a mixture of theoretical results and suggestive, extensive empirical/computational results.

In case $\mathbb{F}=\mathbb{C}$, the complex numbers, all graphs are constructible: given an $n$-by-$n$ matrix $A$ over $\mathbb{C}$ and complex numbers ${\lambda }_1,\dots ,{\lambda }_n\in \mathbb{C}$, then there exists a diagonal matrix $D$ such that $A+D$ has eigenvalues ${\lambda }_1,\dots ,{\lambda }_n$ [1]. If $\mathbb{F}=\mathbb{R}$, the real numbers, the question has been studied [2], though a complete answer is not yet known. This already motivates our problem, and extensive recent work on multiplicities [3] does as well. In our case, many trees are non-constructible, and it is an engaging combinatorial problem to ask which trees are constructible over a given field.

The remaining content is organized as follows. The next section summarizes our empirical results, with some details in the Appendix. We hope these will be useful to other researchers, who may make further advances with these data as a guide. In the third section, we give some theoretical results, inspired partly by what we found. In the fourth section, we record a number of conjectures that appear strongly suggested by our data. Some of these seem plausible, and others are a bit of a surprise. As construction techniques are difficult to come by, these conjectures should inspire further work.

2. Empirical data

Given a tree $T$, let $N\left(T\right)$ be the subset of $\mathcal{F}\left(T\right)$ having all nonzero subdiagonal entries equal to $1$. More generally, for any graph $G$, let $N\left(G\right)$ be the subset of $\mathcal{F}\left(G\right)$ such that for any $A\in N\left(G\right)$ there exists a spanning tree $T^{\prime }\subset G$ whose nonzero subdiagonal entries correspond to edges in $T^{\prime }$ equal to $1$. By diagonal similarity, the characteristic polynomial of any $A\in \mathcal{F}\left(G\right)$ is preserved if $n-1$ entries are normalized (See, for example, [4]). It follows that $A\in \mathcal{F}\left(G\right)$ has $p_A\left(x\right)=f\left(x\right)$ if and only if there exists $A^{\prime }\in N\left(G\right)$ such that $p_{A^{\prime }}\left(x\right)=f\left(x\right)$. Therefore, to determine if $G$ realizes $f\left(x\right)$, it suffices to compute $p_A\left(x\right)$ for all $A\in N\left(G\right)$.

Let $\mathbb{F}={\mathbb{F}}_q$, the finite field of order $q$, where $q$ is a prime power. Let $G$ be a graph with $n$ vertices and $e$ edges. There are $q$ choices for each of the $n$ diagonal entries and $q-1$ choices for each of the $2e-\left(n-1\right)$ entries that correspond to the edges in $G-T^{\prime }$. It follows that

$$\mid N\left(G\right)\mid =q^n{\left(q-1\right)}^{2e-n+1}.$$E2

This implies, for example, that if we want to show $G$ is constructible, then it suffices to compute the characteristic polynomials of no more than $q^n{\left(q-1\right)}^{2e-n+1}$ matrices. If all polynomials are realized, then $G$ is constructible; otherwise, $G$ is non-constructible.

2.1 Acquisition of raw data

We wrote a program in Mathematica [5] to compute the characteristic polynomials of all matrices in $N\left(G\right)$, thereby determining if $G$ is constructible over ${\mathbb{F}}_q$. By Equation (2), Mathematica computes the characteristic polynomials of at most $q^n{\left(q-1\right)}^{2e-n+1}$ matrices for each n-vertex graph G on n vertices with e edges.

We acquired extensive data in the case the graph $G$ is a tree $T$, and the field is the finite field $\mathbb{F}={\mathbb{F}}_3$ since these conditions are computationally the lightest (after the exceptional case $\mathbb{F}={\mathbb{F}}_2$). The realizability status for all polynomials $f$, including the number of matrices in $\mathcal{F}\left(T\right)$ realizing $f$, has been computed for all trees $T$ up to $n=10$ vertices. Because the program automatically normalizes $n-1$ entries, the number of times a given polynomial $f\left(x\right)$ is realized by $G$ refers to the number of elements $A\in N\left(G\right)$ such that $p_A\left(x\right)=f\left(x\right)$.

The realizability status for each polynomial over ${\mathbb{F}}_3$ is also known for several trees $T$ on $n=11$ vertices, but data for the number of matrices in $N\left(T\right)$ that realize a given polynomial was not computed in exchange for program speed. This was done by allowing the program to forget the previous realizations of $f\left(x\right)$ by $T$ during the computation and to only record whether or not $f\left(x\right)$ is realized by some $A\in N\left(T\right)$. If the program finds that G realizes all polynomials, then computation for that tree terminates, and this is recorded so that computation for a new tree can begin. (This is why most trees for which the constructibility status is known on $11$ vertices are constructible.)

We then acquired data over the field $\mathbb{F}={\mathbb{F}}_5$ for all trees through $n=8$ vertices. However, again to promote speed, the program only records the realizability status of all polynomials and does not record the number of times each is realized.

Finally, we acquired data over the field $\mathbb{F}={\mathbb{F}}_3$ for all connected graphs through $n=7$ vertices. See the Appendix for instructions to access these data.

2.2 Graph of graphs

Definition 1 (co-realizable graphs). We say that graphs $G$ and $H$ are co-realizable (over $\mathbb{F}$) if $P\left(\mathbb{F},G\right)=P\left(\mathbb{F},H\right)$. We call the equivalence class of $G$ with respect to co-realizability the co-realizability class of $G$ (over $\mathbb{F}$).

We can equip the set of all co-realizability classes of graphs on $n$ vertices with a natural partial order by declaring that $H<G\text{if and only if}P\left(\mathbb{F},H\right)\subset P\left(\mathbb{F},G\right).$ Organizing the empirical data with respect to this partial order reveals the structure of co-realizable classes. An example demonstrating this graph in the case $\mathbb{F}={\mathbb{F}}_3$, $n=8$, together with additional information about each tree, can be found in Figure 1. See the Appendix for analogous diagrams for cases $n=9,10$, as well as tabulations of other empirical results.

Figure 1.

The co-realizability partial ordering for all trees on $n=8$ vertices over ${\mathbb{F}}_3$. The box containing a tree $T$ contains information as follows. The green number is the number of polynomials $T$ realizes, while the red is the number missed. p$n_1$n$n_2$T$n_3$ indicates that the field is ${\mathbb{F}}_q={\mathbb{F}}_{n_1}$, the tree is on $n_2$ vertices, and is the $n_3$th such tree to be indexed by Mathematica 13.1 function GraphData. $\mathrm{\Delta }$, $d$, and gp indicates $T$’s maximum degree, diameter, and the order of the graph automorpshim group of T, respectively.

3. Theoretical results

Although much of the following theory can be generalized from over fields to over arbitrary commutative rings, we will only work over fields.

3.1 Useful results for checking realizability

Proposition 2. Let $\mathit{G}$ be a graph on n vertices, let $\mathbb{F}$ be any field, and let $f\left(x\right)=x^n+a_{n-1}{x}^{n-1}+\cdots +a_0$ be a monic polynomial over $\mathbb{F}$. If $f\left(x\right)\in P\left(\mathbb{F},G\right),$ then for all $\alpha \in \mathbb{F}$,

• $f\left(x-\alpha \right)\in P\left(\mathbb{F},G\right)$, and

• $x^n+\alpha a_{n-1}{x}^{n-1}+\cdots +{\alpha }^n{a}_0\in P\left(\mathbb{F},G\right)$.

Proof: Let $f\left(x\right)\in P\left(\mathbb{F},G\right)$. Then there exists $A\in \mathcal{F}\left(G\right)$ such that $p_A\left(x\right)=f\left(x\right)$. If $\alpha \in \mathbb{F}$, then $f\left(x+\alpha \right)=p_A\left(x-\alpha \right)=det\left(\left(x-\alpha \right)I-A\right)=det\left(\mathit{xI}-\left(A+\mathit{\alpha I}\right)\right)$. Since $A+\mathit{\alpha I}\in \mathcal{F}\left(G\right)$ whenever $A\in \mathcal{F}\left(G\right)$, the first point follows.

For the second point, recall that if $p_A\left(x\right)=x^n+\alpha a_{n-1}{x}^{n-1}+\cdots +{\alpha }^n{a}_0$, then $a_k=E_{n-k}\left(A\right)$ for all $k=1,\dots ,n$, where $E_k\left(A\right)$ denotes the sum of all $k$-by-$k$ principal minors of $A$. The determinant of a $k$-by-$k$ matrix is homogeneous of order $k$, so $E_k\left(\mathit{\alpha A}\right)={\alpha }^k{E}_k\left(A\right)$.

3.2 Non-constructibility from concentrated pendants

The following theorem shows that given any graph $G$, we can construct a non-constructible graph over ${\mathbb{F}}_q$ by adding sufficiently many pendant vertices to a single fixed vertex of $G$.

Theorem 3. Let $G$ be a graph on $n$ vertices. If $k\ge q+1$ vertices are pendant at some vertex of $G$, then all members of $P\left({\mathbb{F}}_q,G\right)$ have $k-q$ linear factors over ${\mathbb{F}}_q$, counting multiplicities.

Proof: Suppose $k\ge q+1$ vertices are pendant at a vertex $v$ of $G$, and let $A\in \mathcal{F}\left(G\right)$. Then the characteristic matrix $A-\mathit{xI}$ is permutationally and then diagonally similar to a matrix of the form

There are only $q$ elements of the field, so by relabeling if necessary, we can assume $a_q=a_{q+1}$, $a_{q+2}=a_{q+3}$, $\dots$, $a_k=a_{k+1}$. In addition, since $b_{1,k+1}\ne 0$, we can zero out the first row entries of columns $k+2,\dots ,n$ by subtracting multiples of the $\left(k+1\right)$st column. Thus, $A^{\prime }-\mathit{xI}$ is similar to a matrix of the form

$p_A\left(x\right)=p_{{A^{\prime }}^{\prime }}\left(x\right)$ and ${A^{\prime }}^{\prime }-\mathit{xI}$ is a lower triangular block matrix, so

$$p_A\left(x\right)=p_{{A^{\prime }}^{\prime }}\left(x\right)=det\left({A^{\prime }}^{\prime }-\mathit{xI}\right)=det\left(S\right)det\left[{\ast }^{\prime }\right],$$E3

where $S$ denotes the upper-left block of ${A^{\prime }}^{\prime }-\mathit{xI}$ shown above. The graph of $S$ is a simple star on $k+1$ vertices, so by Theorem 2.1 of [5], we know the characteristic polynomial of $S$ has $\ge k-q$ roots over ${\mathbb{F}}_q$ since $k-q$ values are repeated on the diagonal. Then the result follows from the observation from Eq. (3) that $det\left(S\right)$ divides $p_A\left(x\right)$.

3.3 Failure of the converse to Theorem 3

There is a counterexample to the converse of Theorem 3.

Proposition 4. The converse of Theorem 3 is not true in general.

Proof of Proposition 4: Let $T$ be the tree in Figure 2, which has no vertices with more than $q=3$ pendants. We claim each $f\left(x\right)\in P\left({\mathbb{F}}_3,T\right)$ has a root over ${\mathbb{F}}_3$. Let $f\left(x\right)\in P\left({\mathbb{F}}_3,T\right)$. Then there exists some $A\in N\left(T\right)$ such that $f\left(x\right)=det\left(A-\mathit{xI}\right)$. Since any $A\in N\left(T\right)$ takes the form

Figure 2.

The tree $T$ on $9$ vertices such that each $f\left(x\right)\in P\left({\mathbb{F}}_3,T\right)$ has a root over ${\mathbb{F}}_3$, but no vertices of $T$ have more than $q=3$ pendants.

we have $f\left(x\right)$ is the determinant of the matrix given by

It is left as a straightforward exercise to show the determinant of this matrix always has a linear factor.

3.4 Application of geometric Parter-Wiener, etc. theory

We initially suspected that if $T$ is a graph on $n\le \mid \mathbb{F}\mid$ vertices, then $T$ is constructible. However, we found a counterexample by considering the simple star on four vertices over the field ${\mathbb{F}}_4$. To show that this indeed presents a counterexample, we apply methods from the relatively young Geometric Parter-Wiener, etc. theory [6]. The notation and terminology of this subsection is adopted from [6]. See also [3, Chapter 12].

Proposition 5. There may be trees on q vertices that are non-constructible over ${\mathbb{F}}_q$. Indeed,

$$\prod _{\alpha \in {\mathbb{F}}_4}\left(x-\alpha \right)=x^4-x\notin P\left({\mathbb{F}}_4,S_4\right).$$E4

Proof: Let $v$ be the central vertex and $u_1,u_2,u_3$ the pendants at $v$. Let $k\in \left\{u_1,u_2,u_3\right\}$ and ${\mathrm{gm}}_A\left(k\right)=1$. $v$ is g-Parter for $k$—indeed, this follows from geometric Parter-Wiener, etc. theory since $v$ is the only vertex with degree $\ge 2$. In other words, if $k\in \sigma \left(A\right)$ and $k\in \left\{u_1,u_2,u_3\right\}$ then $k$ appears at least least twice in $\left\{u_1,u_2,u_3\right\}$.

Suppose each $k\in {\mathbb{F}}_4$ is a simple eigenvalue of $A\in \mathcal{F}\left(S_4\right)$. Then ${\mathrm{gm}}_A\left(k\right)=1$, so by the above statement, each of $\left\{u_1,u_2,u_3\right\}$ appears twice in $\left\{u_1,u_2,u_3\right\}$. The only way for this to happen is if $u_1=u_2=u_3=k$, in which case $rank\left(A-\mathit{kI}\right)\le 2$. But then ${\mathrm{gm}}_A\left(k\right)=dimker\left(A-\mathit{kI}\right)\ge 2>{\mathrm{am}}_A\left(k\right)=1$, a contradiction. This establishes Eq. (4) and completes the proof.

Remark 6. In fact, $x^4-x$ is the only polynomial over ${\mathbb{F}}_4$ that is not realized by $S_4$, which is to say $P\left({\mathbb{F}}_4,S_4\right)=P_4\left({\mathbb{F}}_4\right)\backslash \left\{x^4-x\right\}$.

3.5 Algebraic branch duplication

This subsection largely adopts the definitions and background from [7, Section 2]. That work notes that many of these arguments also work for general graphs, but presents them in the case of trees, and we will take the same approach. To read more on the technique of branch duplication, one can also consult [3, Section 6.3].

Let $T$ be a tree and $\left\{v,u_1\right\}$ be an edge of $T$. Let $T_v$ (resp. $T_1$) be the connected component of $T$ resulting from deletion of $u_1$ (resp. $v$) and containing $v$ (resp. $u_1$). Denote by $n_i=\mid T_i\mid$ the number of vertices in $T_i$. An $s$-combinatorial branch duplication of $T_1$ at $v$ is the tree obtained by appending $s\ge 1$ copies of the branch T₁ T at v. We will denote by ${\mathbf{e}}_{n_i,n_j}$, or sometimes ${\mathbf{e}}_{i,j}$ when clear from context, the $n_i$-by-$n_j$ matrix over $\mathbb{F}$ with $1$ as the $\left(1,1\right)$-entry and 0 as all remaining entries. We will also use the notation ${\mathbf{e}}_{\mathit{vu}}$ for vertices u and v of T, which is defined similarly. These notations may also be combined to yield e_1,v and e_v,1, whose definitions should also be clear from context.

Let $A\in \mathcal{F}\left(T\right)$. By permutation similarity, A is similar to a matrix of the form

E5

where $a_{{\mathit{vu}}_1}$, $a_{u_{1}v}$ are the nonzero entries of $A$ correspond to the edge $\left\{v,u_1\right\}$ in $T$. Since the characteristic polynomial is invariant under matrix similarity, we may assume without loss of generality that $A$ is of the form in (5) above.

Let $T$ be a tree and v a vertex of T. Let $\stackrel{⌣}{T}$ be the s-combinatorial branch duplication of the branch $T_1$ of at v. Let $u_2,\dots ,u_{1+s}$ (resp. $T_2,\dots ,T_{1+s}$) be the new neighbors of $v$ (resp. the new branches at $v$) in $\stackrel{⌣}{T}$.

We say that a matrix $\stackrel{⌣}{A}=\left({\stackrel{⌣}{a}}_{\mathit{ij}}\right)$ is $s$-algebraic branch duplication of $A$ by $A\left[T_1\right]$ at v if Ǎ satisfies the following requirements:

1. $\stackrel{⌣}{A}\left[T_v\right]=A\left[T_v\right]$ and $\stackrel{⌣}{A}\left[T_1\right]=\cdots =\stackrel{⌣}{A}\left[T_{1+s}\right]=A\left[T_1\right]$.

2. ${\stackrel{⌣}{a}}_{{\mathit{vu}}_i}{\stackrel{⌣}{a}}_{u_{i}v}\ne 0$ ($i=1,\dots ,1+s$), and ${\stackrel{⌣}{a}}_{{\mathit{vu}}_1}{\stackrel{⌣}{a}}_{u_{1}v}+\cdots +{\stackrel{⌣}{a}}_{{\mathit{vu}}_{1+s}}{\stackrel{⌣}{a}}_{u_{1+s}v}=a_{{\mathit{vu}}_1}{a}_{u_{1}v}$.

3. The graph of Ǎ is Ť.

These conditions together imply

E6

It turns out that Ǎ has a nice characteristic polynomial in relation to that of A:

Theorem 7. ([7], Theorem 1]). Let T be a tree, v a vertex of T, T₁ a branch of T at v and A be a combinatorially symmetric matrix whose graph is T. If $\stackrel{⌣}{A}$ is obtained from A by an $s$-algebraic branch duplication of summand $A\left[T_1\right]$ at $v$ then $\stackrel{⌣}{A}$ is similar to the block diagonal matrix $A{\oplus }_{i=1}^{s}A\left[T_1\right]$. Therefore

$$p_{\stackrel{⌣}{A}}\left(t\right)=p_A\left(t\right)·{\left[p_{A\left[T_1\right]}\left(t\right)\right]}^s.$$

and, for each eigenvalue λ of Ǎ, we have

$${\mathrm{am}}_{Ǎ}\left(\lambda \right)={\mathrm{am}}_A\left(\lambda \right)+s·{\mathrm{am}}_{A\left[{\mathit{T}}_1\right]}\left(\lambda \right)\text{and}{\mathrm{gm}}_{Ǎ}\left(\lambda \right)={\mathrm{gm}}_A\left(\lambda \right)+s·{\mathrm{gm}}_{A\left[{\mathit{T}}_1\right]}\left(\lambda \right).$$

See [7] for a proof of Theorem 7, where it is noted that the proof works over all fields not equal to ${\mathbb{F}}_2$. Indeed, by the following lemma, proven in [8], we can find scalars satisfying condition (ii) above in every field other than ${\mathbb{F}}_2$:

Lemma 8. ([8], Lemma 2.3]). For any field $\mathbb{F}\ne {\mathbb{F}}_2$, any element $a\in \mathbb{F}$, and any integer $s\ge 2$, there exists ${\stackrel{⌣}{a}}_1,\dots ,{\stackrel{⌣}{a}}_s\in \mathbb{F}$ such that ${\stackrel{⌣}{a}}_1+\cdots +{\stackrel{⌣}{a}}_s=a$.

Corollary 9. Let $\mathbb{F}\ne {\mathbb{F}}_2$ be a field and suppose $T$ is a $s$-combinatorial branch duplication of a tree $T_0$ of the branch $T_1$ at a vertex $v$ of T. Then for all $g\left(x\right)\in P\left(\mathbb{F},T_1\right)$ and $h\left(x\right)\in P\left(\mathbb{F},T_0\right),{\left[g,\left(x\right)\right]}^{s}h\left(x\right)\in P\left(\mathbb{F},T\right)$.

Remark 10. Using the same notation and hypotheses of Corollary 9, we can now construct a matrix $A\in \mathcal{F}\left(T\right)$ such that $p_A\left(x\right)={\left[g\left(x\right)\right]}^{\mathrm{s}}h\left(x\right)$ as follows: Let $B\in \mathcal{F}\left(T_1\right)\text{and}C\in \mathcal{F}\left(T_0\right)$ be matrices such that $p_B\left(x\right)=g\left(x\right)$ and $p_C\left(x\right)=h\left(x\right)$. Define a new matrix $C^{\prime }$ by $C^{\prime }=C+e_{v,u_1}\left({\stackrel{⌣}{b}}_0-c_{v,u_1}\right)$. Then choose nonzero elements ${\stackrel{⌣}{b}}_2,\dots ,{\stackrel{⌣}{b}}_{\mathrm{1+s}}\in \mathbb{F}$ such that ${\stackrel{⌣}{b}}_1+{\stackrel{⌣}{b}}_2,\dots ,{\stackrel{⌣}{b}}_{\mathrm{1+s}}=c_v,{}_{u_1}$. Then, where ${\mathbf{e}}_{1,0}$ is the $\mid T_1\mid$-by-$\mid T_0\mid$ matrix with a 1 in the (1, 1)-entry and zeros elsewhere, the matrix

satisfies $p_A\left(x\right)={\left[g\left(x\right)\right]}^{\mathrm{s}}h\left(x\right).$

4. Conjectures

Let $\mathbb{F}$ be any field other than ${\mathbb{F}}_2$. A primary product of our empirical work is to reveal potentially valid statements of which we may not have otherwise thought. Here we record the most interesting of these statements, and a few relations among them, in hopes that they may spark an idea in others. Related conjectures are grouped together. In some cases, the evidence is very compelling. We give these as a list with comments.

1. If the simple star on n vertices realizes a monic polynomial p over ${\mathbb{F}}_q$, then all trees on n vertices realize p. This statement is likely true for infinite fields as well.

2. If every vertex in a tree T has degree strictly less than $\mathbb{F}$, then T is constructible.

   [Note: the same statement but with “strictly less than” replaced with “at most” is false, which can be seen by the counterexample used for Proposition 4, namely the 10-vertex nonlinear tree over ${\mathbb{F}}_3$. Also, since nonlinear trees are sources of frequent counterexamples (see, for example, [3]), it would not be surprising if the latter statement holds when restricted to linear trees.]

   1. An important special case is the path on $n$ vertices. This has long been conjectured, though it has proven elusive. This was investigated extensively in [9], which partly inspired our work and is where this conjecture first arose.

3. When trees are categorized by diameter, those with larger diameters tend to realize more polynomials and are more often constructible than those with shorter diameters.

   1. Suppose a tree $T$ is constructible over a field $\mathbb{F}$ and a new vertex is added to $T$, as to increase the diameter and produce $T^{\prime }$, then $T^{\prime }$ is also constructible.

   2. Suppose a tree $T$ is non-constructible over a field $\mathbb{F}$ and a vertex is added to $T$ to produce $T^{\prime }$ such that $T^{\prime }$ have the same diameter as T. Then $T^{\prime }$ is also non-constructible.

4. If a non-constructible tree T has at most $\mid \mathbb{F}\mid$ pendants at any vertexvertex, then sufficiently many vertices may be added to increase the diameter and achieve constructibility.

   [Note: This statement is motivated by the case $\mathbb{F}={\mathbb{F}}_3$, as the data for that case suggests it. However, this statement may also hold in general.]

   1. Let ${\mathbb{F}}_q\ne {\mathbb{F}}_2$ be a finite field and let T be the tree produced by adding a pendant path to the simple star on $\mid {\mathbb{F}}_q\mid +2$ vertices. Then $P\left({\mathbb{F}}_q,T\right)$ is the set of monic polynomials over ${\mathbb{F}}_q$ with a root.

      [Note: Theorem 3 implies that P(${\mathbb{F}}_q$, T) is a subset of the set of monic polynomials without a root, so to prove this it would be enough to prove the reverse inclusion.]

5. As the number of vertices increases, the fraction of polynomials that are constructible for any tree among all polynomials tends to 0.

   [Note: This is implied by the first conjecture, so an avenue to showing this would show that first.]

6. The number of co-realizability classes for trees on $n$ vertices over ${\mathbb{F}}_3$ is $2^{n-4}$.

7. If a graph $G$ is constructible over ${\mathbb{F}}_q$, then the graph $G^{\prime }$ obtained by adding an edge to $G$ is also constructible. In particular, for each positive integer $n$, there exists a threshold number of edges, $t_n$ such that any graph on $n$ vertices with at least $t_n$ edges is constructible.

8. $K_n$, the complete graph on $n$ vertices, is constructible for all $n\ge 1$ over all fields other than ${\mathbb{F}}_2$.

   [We suggest that a proof for this statement be as follows: First, write the companion matrix for the desired polynomial. Then perform elementary operations to obtain similar matrices with properly more nonzero entries after each iteration. This may not be easy, but we believe it can be done; this holds for the real numbers, and the data supports it for small finite fields other than ${\mathbb{F}}_2.$]

5. Conclusion

Prior to this work, little was known. By studying the computational data, we formulated several conjectures and proved several. We demonstrated applications of branch duplication and geometric Parter-Wiener, etc. theory to the inverse characteristic polynomial problem by using them to prove results for general graphs over arbitrary finite fields. For some graphs, such as the path, the data suggests that all monic polynomials are realized over any field with more than two elements, although proving this has proved elusive. The authors hope the given results, arguments, and list of conjectures in this work will pave the way for future study.

The authors suggest that further work be done on the inverse characteristic polynomial problem for the case of the path over finite fields because a solution to this problem would likely result in a method for constructing a matrix with a given characteristic polynomial. Such construction techniques could also be pursued by considering methods such as the generalized partial fraction decomposition for arbitary fields (See [10]). This is motivated by the successful application of the partial fraction decomposition in [2] for matrices over the real numbers. The generalized Euclidean algorithm and Bézout’s identity could also be investigated in the case of the path.

A. Appendix

We now show selected figures that were generated from this data. To download a zipped folder containing the raw data, some figures, and other information, please email the corresponding author or visit https://drive.google.com/drive/u/1/folders/1m0t6fmBpGx6PMeKhw7UtCk6Hg8gf2e1k. The folder also contains diagrams analogous to Figures 3 and 4 through $n=10$ vertices, together with higher-quality versions of these figures (Figures 5 and 6).

Figure 3.

Each bar in the bar chart corresponds to a polynomial in $P_3\left({\mathbb{F}}_3\right)$. The bar’s height at a given polynomial is the number of times that polynomial is realized by matrices (whose nonzero subdiagonal entries all equal $1$) whose graph is the given tree.

Figure 4.

Values on the $x$-axis of the bar chart represent different the polynomials of $P_4\left({\mathbb{F}}_3\right)$. The bar height at a given polynomial indicates the number of times that polynomial is realized by matrices (whose nonzero subdiagonal entries all equal $1$) whose graph is the given tree.

Figure 5.

Values on the $x$-axis of the bar chart represent different polynomials of $P_5\left({\mathbb{F}}_3\right)$. The bar height at a given polynomial indicates the number of times that polynomial is realized by matrices (whose nonzero subdiagonal entries all equal $1$) whose graph is the given tree.

Figure 6.

The co-realizability partial ordering for all trees on $n=9$ vertices over ${\mathbb{F}}_3$. The labeling scheme used is that of Figure 1.