Five prism q 3 impossible

The $5$-prism cannot achieve $q=3$

This worksheet illustrates some techniques for trying to determine whether a particular graph can achieve a particular multiplicity list. Since the graph turns out not to achieve $q=3$, full generality must be maintained throughout. That means that this worksheet is necessarily missing the technique of substituting in particular guesses using up degrees of freedom with arbitrary (small but nonzero) rational numbers, in hopes that what remains will still have sufficient flexibility for any three eigenvalues.

Techniques that are illustrated:

• Breaking symmetry by converting a spanning tree's worth of variables from squared variables to positive variables.
• Extracting equations from Schur complements of triangular sub-matrices, complementary to zero forcing.
• Extracting equations from entries of the matrix plugged into its minimal polynomial.

That is on the high side for these graphs, which tends to make things difficult: There are a lot of possible sign choices that have to be ruled out. That was why I picked this example, without looking at the graph, somewhat at random from the middle of the pack with a high number of signings.

In some cases it is possible, for graphs with high symmetry, to find realizations for arbitrary eigenvalues by picking edge and vertex values that preserve some or all of the symmetries of the graph. To exclude eigenvalues, however, you can't make any such assumptions.

First technique: Symmetry breaking. Start by choosing a spanning tree of variables to be squared.

The number of paths of length $3$ tells us how many terms will be in the equations that are extracted from the minimal polynomial. It makes us happy to see $2$ all over the place. Anything else and substitutions start to multiply the number of terms. Three term equations, like we have here, aren't so bad at first, but they quickly become unmanageable after many substitutions.

We create a polynomial ring in all these variables, plus a slack variable $s$ which is useful for enforcing non-zero conditions: Adding the equation `s*a*b*c - 1` to an ideal says that $s = 1/(abc)$ and therefore that all these variables must be nonzero.

We use the default term ordering, which is degree reverse lexicographic.

The matrix entries will actually be rational functions, but as much as possible only with denominators that are monomials in variables that are guaranteed to be nonzero. This obviates having to keep track of cases where one of the denominators would be zero.

Not actually used in this worksheet, since we don't calculate any elemination ideals. But when you do, you often want to know the dimension of the result, which Sage reports including all the degrees of freedom that are no longer mentioned because you explicitly wanted to get rid of them. This dimension counter compensates for that.

The following routine populates a matrix with the symmetry-broken variables. The commented out bit, `# * rowmult`, would give you diagonal entries that are multplied by a `p` variable like everything else in the row, which may or may not be preferable. For now, I'm leaving bare diagonal variables in the matrix.

Assumption: every `p` variable is strictly positive.

At this point, I tried the minimal polynomial technique for a good while, with no success, including trying to eat up degrees of freedom by setting variable entries arbitrarily, in hopes of finding a family of $q=3$ representatives. Eventually I gave up and decided to use the Schur complement technique first.

In separate work, I calculated the zero forcing number for this graph, which is $4$ (it is not hard to see; color the vertices of a square in the graph blue). This is good news, because it is impossible to get $10$ eigenvalues in total from only three distinct eigenvalues each of multiplicity strictly less than $4$, so we can assume without loss of generality that $0$ is an eigenvalue of multiplicity $4$.

The positive semidefinite zero forcing number is $4$, which isn't so useful in this case. If it were $3$, we would know that the only viable ordered multiplicity list is $(3, 4, 3)$, and if it were $2$ there would be no viable multiplicity list and we would be done.

Assumption: $M$ has rank $6$.

Zero forcing gives $n - \mathrm{t\#}(G)$ where the triangle number $\mathrm{t\#}(G)$ is the largest size of a square submatrix that is permutation equivalent to an upper triangular matrix all of whose diagonal entries are nonzero. To find the triangle, strike out all the rows of the matrix corresponding to vertices that are never forced (because they start blue), and strike out all the columns of the matrix that never perform a force (because they are the ends of forcing chains, which start out blue in the reverse forcing). Then permute the rows and columns until the triangle appears.

Having a triangular submatrix whose rank is the same as the assumed rank of the whole matrix sets us up to be able to use the Schur complement technique, because the Schur complement of this submatrix must have every entry equal to zero, and because the determinant of this matrix, which turns into denominators in the Schur complement, is a monomial in nonzero variables.

From these equations we are able to solve for eight of the ten diagonal entries $\dots$

which turns out to be completely unneccesary.

Forget the assumption of rank $6$.

It turns out that this graph can be quickly dealt with, using the minimal polynomial technique, just by picking the right $3$-term equations, which come from distance $3$ pairs connected by $3$ different paths, and which therefore don't involve the diagonal entries or the eigenvalues $t_i$ at all.

We have discovered an expression that must be zero, but cannot equal zero over the real numbers using nonzero variables.

This factor that must equal zero is a sum of squares of values that are unequal, and thus cannot both be zero.