Five prism q 3 impossible

993 days ago by hthall

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.
set_random_seed(892142) # so we get the same picture every time the worksheet is run G = Graph('I?bFB_wF?') G 
       
### Some routines useful for finding unique shortest path and monotone signed shortest path bounds def upper(nn): for ii in range(nn): for jj in range(ii, nn): yield ii, jj def q_unsigned(A): # Also allow a graph try: nn = A.ncols() except AttributeError: A = A.adjacency_matrix() nn = A.ncols() bound = 1 oldmat = A + 1 - A while True: reach = oldmat * A + oldmat for ii, jj in upper(nn): if (reach + 2)[ii, jj] == 1: bound += 1 break else: return bound oldmat = reach def signings(G): for spantree in G.spanning_trees(): break # just need the one spanners = spantree.edges() unspan = [(xx[0], xx[1]) for xx in G.edges() if xx not in spanners] A = G.adjacency_matrix() for xx in sxrange(1 << len(unspan), 1 << (len(unspan) + 1)): # for binary strings B = A + 0 for ii, digit in enumerate(xx.binary()[1:]): if digit == '1': B[unspan[ii]] = -1 B[unspan[ii][1], unspan[ii][0]] = -1 yield B def qbound(signmat): nn = signmat.ncols() A = Matrix(ZZ, nn, nn, lambda ii, jj: abs(signmat[ii, jj])) bound = 1 oldmat = A + 1 - A oldsign = signmat + 1 - signmat while True: reach = oldmat * A + oldmat cancel = oldsign * signmat for ii, jj in upper(nn): if reach[ii, jj] and not oldmat[ii, jj]: expanded = True if abs(cancel[ii, jj]) == reach[ii, jj]: bound += 1 break else: return bound oldmat = reach oldsign = cancel def count_q(G, q=3): queues = [qbound(xx) for xx in signings(G)] return len([xx for xx in queues if xx <= q]), len(queues) 
       
### The smallest number of eigenvalues compatible with the unique shortest path bound q_unsigned(G) 
       
3
3
### The number of signings compatible with monotone signed shortest paths succeed, total = count_q(G, 3) print("{} signings out of {} viable for q = 3.".format(succeed, total)) 
       
22 signings out of 64 viable for q = 3.
22 signings out of 64 viable for q = 3.

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.

# Rename the vertices with letters (this is especially useful when there are more than 10) set_random_seed(43976) # for consistent plotting G = Graph('I?bFB_wF?') # this allows re-executing this cell nn = G.order() G.relabel({ii : chr(65 + ii) for ii in range(nn)}) G.plot(save_pos=True) # Keep the same vertex positions on subsequent plots G.plot() 
       
## For curiousity's sake. G.automorphism_group().order() 
       
20
20

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.

# Let Sage pick some random spanning tree for spantree in G.spanning_trees(): break # Just take the first one it gives us # A list of edges in the spanning tree, with the vertices of each edge so far listed # in no particular order prespan = [xx[:2] for xx in spantree.edges()] # Default format has three elements, like ('A', 'E', None) # Or if you have a reason to prefer some particular or more symmetric spanning tree, go ahead and list # the edges in that. prespan = [('A', 'G'), ('G', 'C'), ('C', 'I'), ('I', 'E'), ('A', 'F'), ('G', 'B'), ('C', 'H'), ('I', 'D'), ('E', 'J')] # select a root node for the spanning tree root = 'F' # Choose an orientation for each edge ordered away from the root node spanner = [] seen = {root: True} predict = {xx: True for xx in prespan} while predict: for xx in list(predict): if xx[0] in seen: spanner.append(xx) seen[xx[1]] = True del predict[xx] break if xx[1] in seen: spanner.append((xx[1], xx[0])) seen[xx[0]] = True del predict[xx] break else: raise ValueError('Not a spanning tree.') print(spanner) 
       
[('F', 'A'), ('A', 'G'), ('G', 'B'), ('G', 'C'), ('C', 'H'), ('C', 'I'),
('I', 'D'), ('I', 'E'), ('E', 'J')]
[('F', 'A'), ('A', 'G'), ('G', 'B'), ('G', 'C'), ('C', 'H'), ('C', 'I'), ('I', 'D'), ('I', 'E'), ('E', 'J')]
# A picture of the spanning tree with the same vertex positions as before spantree = G.copy() # for onespan in G.spanning_trees(): # break # spanner = [xx[:2] for xx in onespan.edges()] for ed in G.edges(): if (ed[0], ed[1]) not in spanner and (ed[1], ed[0]) not in spanner: spantree.delete_edge(ed) spantree.plot() 
       
A = G.adjacency_matrix() A 
       
[0 0 0 0 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1]
[1 0 0 0 0 0 0 0 1 1]
[1 1 0 0 0 0 0 0 0 1]
[1 1 1 0 0 0 0 0 0 0]
[0 1 1 1 0 0 0 0 0 0]
[0 0 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 0 0 0]
[0 0 0 0 1 1 1 0 0 0]
[0 0 0 0 0 1 1 1 0 0]
[0 0 0 0 0 0 1 1 1 0]
[0 0 0 0 0 0 0 1 1 1]
[1 0 0 0 0 0 0 0 1 1]
[1 1 0 0 0 0 0 0 0 1]
[1 1 1 0 0 0 0 0 0 0]
[0 1 1 1 0 0 0 0 0 0]
[0 0 1 1 1 0 0 0 0 0]
[0 0 0 1 1 1 0 0 0 0]
## Set the number of distinct eigenvalues we are shooting for qq = 3 ## How many paths of that length are there between every pair of vertices? (A + 1)^qq 
       
[10  6  4  3  9 10  9  3  4  6]
[ 6 10  6  4  3  9 10  9  3  4]
[ 4  6 10  6  4  3  9 10  9  3]
[ 3  4  6 10  6  4  3  9 10  9]
[ 9  3  4  6 10  6  4  3  9 10]
[10  9  3  4  6 10  6  4  3  9]
[ 9 10  9  3  4  6 10  6  4  3]
[ 3  9 10  9  3  4  6 10  6  4]
[ 4  3  9 10  9  3  4  6 10  6]
[ 6  4  3  9 10  9  3  4  6 10]
[10  6  4  3  9 10  9  3  4  6]
[ 6 10  6  4  3  9 10  9  3  4]
[ 4  6 10  6  4  3  9 10  9  3]
[ 3  4  6 10  6  4  3  9 10  9]
[ 9  3  4  6 10  6  4  3  9 10]
[10  9  3  4  6 10  6  4  3  9]
[ 9 10  9  3  4  6 10  6  4  3]
[ 3  9 10  9  3  4  6 10  6  4]
[ 4  3  9 10  9  3  4  6 10  6]
[ 6  4  3  9 10  9  3  4  6 10]

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.

## Names for diagonal entries dnames = ['d_' + chr(65 + ii) for ii in range(nn)] print(dnames) 
       
['d_A', 'd_B', 'd_C', 'd_D', 'd_E', 'd_F', 'd_G', 'd_H', 'd_I', 'd_J']
['d_A', 'd_B', 'd_C', 'd_D', 'd_E', 'd_F', 'd_G', 'd_H', 'd_I', 'd_J']
## Names for edge variables, starting with 'a', and strictly positive edge variables, starting with 'p'. anames = [] pnames = [] for ii in range(nn): for jj in range(ii + 1, nn): if A[ii, jj]: p, q = chr(65 + ii), chr(65 + jj) if (p, q) in spanner or (q, p) in spanner: pnames.append('p_' + p + q) else: anames.append('a_' + p + q) print(anames) print(pnames) 
       
['a_AE', 'a_BF', 'a_BH', 'a_DH', 'a_DJ', 'a_FJ']
['p_AF', 'p_AG', 'p_BG', 'p_CG', 'p_CH', 'p_CI', 'p_DI', 'p_EI', 'p_EJ']
['a_AE', 'a_BF', 'a_BH', 'a_DH', 'a_DJ', 'a_FJ']
['p_AF', 'p_AG', 'p_BG', 'p_CG', 'p_CH', 'p_CI', 'p_DI', 'p_EI', 'p_EJ']
## Names for eigenvalues, starting with 't', and elementary symmetric functions in them, starting with 'f'. tnames = ['t_' + str(ii) for ii in range(1, qq + 1)] fnames = ['f_' + str(ii) for ii in range(1, qq + 1)] print(tnames) print(fnames) 
       
['t_1', 't_2', 't_3']
['f_1', 'f_2', 'f_3']
['t_1', 't_2', 't_3']
['f_1', 'f_2', 'f_3']

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.

P = PolynomialRing(QQ, ['s'] + tnames + dnames + anames + pnames + fnames) P.inject_variables() 
       
Defining s, t_1, t_2, t_3, d_A, d_B, d_C, d_D, d_E, d_F, d_G, d_H, d_I,
d_J, a_AE, a_BF, a_BH, a_DH, a_DJ, a_FJ, p_AF, p_AG, p_BG, p_CG, p_CH,
p_CI, p_DI, p_EI, p_EJ, f_1, f_2, f_3
Defining s, t_1, t_2, t_3, d_A, d_B, d_C, d_D, d_E, d_F, d_G, d_H, d_I, d_J, a_AE, a_BF, a_BH, a_DH, a_DJ, a_FJ, p_AF, p_AG, p_BG, p_CG, p_CH, p_CI, p_DI, p_EI, p_EJ, f_1, f_2, f_3

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.

PQ = P.fraction_field() PQ 
       
Fraction Field of Multivariate Polynomial Ring in s, t_1, t_2, t_3, d_A,
d_B, d_C, d_D, d_E, d_F, d_G, d_H, d_I, d_J, a_AE, a_BF, a_BH, a_DH,
a_DJ, a_FJ, p_AF, p_AG, p_BG, p_CG, p_CH, p_CI, p_DI, p_EI, p_EJ, f_1,
f_2, f_3 over Rational Field
Fraction Field of Multivariate Polynomial Ring in s, t_1, t_2, t_3, d_A, d_B, d_C, d_D, d_E, d_F, d_G, d_H, d_I, d_J, a_AE, a_BF, a_BH, a_DH, a_DJ, a_FJ, p_AF, p_AG, p_BG, p_CG, p_CH, p_CI, p_DI, p_EI, p_EJ, f_1, f_2, f_3 over Rational Field

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.

def truedim(anideal): return anideal.dimension() + len(anideal.gens().variables()) - len(anideal.ring().gens()) 
       

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.

def mname(ii, jj): p = chr(65 + ii) q = chr(65 + jj) rowmult = P(1) for xx in spanner: if xx[1] == p: rowmult *= P('p_' + min(xx) + max(xx)) if ii == jj: return P('d_' + p) # * rowmult if not A[ii, jj]: return P(0) entmult = P(1) if (p, q) not in spanner and (q, p) not in spanner: entmult *= P('a_' + min(p, q) + max(p, q)) return entmult * rowmult 
       
M = Matrix(PQ, nn, nn, mname) show(M) 
       

                                
                            

                                

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.

show(M[[9, 2, 4, 7, 3, 8], [5, 6, 0, 1, 9, 4]]) 
       

                                
                            

                                

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.

schur = (M[[0, 1, 5, 6], [2, 3, 7, 8]] - (M[[0, 1, 5, 6], [5, 6, 0, 1, 9, 4]] * M[[9, 2, 4, 7, 3, 8], [5, 6, 0, 1, 9, 4]]^-1 * M[[9, 2, 4, 7, 3, 8], [2, 3, 7, 8]])) 
       
for ii in range(4): for jj in range(4): if schur[ii, jj]: fact = schur[ii, jj].numerator().factor() print(fact) print else: print(0) print 
       
(-1) * (a_AE^2*a_FJ*p_AF*p_CG*p_EI + d_C*a_AE*a_FJ*p_AF*p_EI -
d_A*d_E*a_FJ*p_CG - a_AE*p_AF*p_CG*p_EI)

(-1) * (a_AE^2*a_DJ*a_FJ*p_AF*p_DI*p_EI*p_EJ +
a_AE*a_DJ^2*p_AF*p_DI*p_EI*p_EJ - d_A*d_E*a_DJ*a_FJ*p_DI*p_EJ -
a_AE*a_DJ*p_AF*p_DI*p_EI*p_EJ - d_D*d_J*a_AE*p_AF*p_EI -
d_A*d_D*a_FJ*p_EI*p_EJ)

(-1) * (a_AE*a_DJ*a_FJ*p_AF*p_EJ - d_J*a_AE*a_DH*p_AF -
d_A*a_DH*a_FJ*p_EJ)

(-1) * (d_I*a_AE^2*a_DJ*a_FJ*p_AF*p_EI*p_EJ +
a_AE*a_DJ*a_FJ*p_AF*p_CI*p_EI*p_EJ - d_A*d_E*d_I*a_DJ*a_FJ*p_EJ -
d_I*a_AE*a_DJ*p_AF*p_EI*p_EJ + d_A*a_DJ*a_FJ*p_CI*p_EI*p_EJ -
d_J*a_AE*p_AF*p_CI*p_EI - d_A*a_FJ*p_CI*p_EI*p_EJ)

-d_C*a_BH*a_FJ*p_BG + a_BF*a_BH*p_BG*p_CG - d_B*a_FJ*p_CG

(-1) * (a_BF*a_BH*a_DJ^2*p_BG*p_DI*p_EJ + d_B*a_DH*a_DJ*a_FJ*p_DI*p_EJ -
a_BF*a_BH*a_DJ*p_BG*p_DI*p_EJ - d_D*d_J*a_BF*a_BH*p_BG)

a_BH^2*a_DJ*a_FJ*p_BG*p_CH*p_EJ + d_J*a_BF*a_BH*a_DH*p_BG*p_CH -
a_BH*a_DJ*a_FJ*p_BG*p_CH*p_EJ - d_B*d_H*a_DJ*a_FJ*p_EJ

(-1) * p_BG * (-d_I*a_BF*a_DJ*p_EJ + a_DJ*a_FJ*p_CI*p_EJ -
d_J*a_BF*p_CI)

(-1) * (-d_F*a_AE*a_BH*p_EI + a_AE*a_BF*a_FJ*p_EI - d_E*a_BH*a_FJ)

(-1) * (d_F*a_AE*a_BH*a_DJ^2*p_DI*p_EI*p_EJ +
a_AE*a_BF*a_DH*a_DJ*a_FJ*p_DI*p_EI*p_EJ + d_D*a_AE*a_BH*a_FJ^2*p_EI*p_EJ
- d_F*a_AE*a_BH*a_DJ*p_DI*p_EI*p_EJ - d_D*d_F*d_J*a_AE*a_BH*p_EI -
d_E*a_BH*a_DJ*a_FJ*p_DI*p_EJ - d_D*a_BH*a_FJ*p_EI*p_EJ)

(-1) * (a_AE*a_BH*a_DH*a_FJ^2*p_CH*p_EJ - d_F*d_J*a_AE*a_BH*a_DH*p_CH +
d_H*a_AE*a_BF*a_DJ*a_FJ*p_EJ - a_BH*a_DH*a_FJ*p_CH*p_EJ)

(-1) * (-d_F*d_I*a_AE*a_DJ*p_EI*p_EJ + a_AE*a_FJ^2*p_CI*p_EI*p_EJ -
d_F*d_J*a_AE*p_CI*p_EI - d_E*d_I*a_DJ*a_FJ*p_EJ +
a_DJ*a_FJ*p_CI*p_EI*p_EJ - a_FJ*p_CI*p_EI*p_EJ)

-d_C*d_G*a_AE*a_BH*p_EI + a_AE*a_BH*p_AG*p_CG*p_EI + d_E*a_BH*p_AG*p_CG
- a_AE*p_AG*p_CG*p_EI

(-1) * p_AG * (a_AE*a_DH*a_DJ*p_DI*p_EI - d_E*a_BH*a_DJ*p_DI -
d_D*a_BH*p_EI)

-d_G*a_AE*a_BH*a_DJ*p_CH - d_H*a_AE*a_DJ*p_AG + a_BH*a_DH*p_AG*p_CH

(-1) * (d_G*a_AE*a_DJ*p_CI*p_EI - d_E*d_I*a_DJ*p_AG +
a_DJ*p_AG*p_CI*p_EI - p_AG*p_CI*p_EI)
(-1) * (a_AE^2*a_FJ*p_AF*p_CG*p_EI + d_C*a_AE*a_FJ*p_AF*p_EI - d_A*d_E*a_FJ*p_CG - a_AE*p_AF*p_CG*p_EI)

(-1) * (a_AE^2*a_DJ*a_FJ*p_AF*p_DI*p_EI*p_EJ + a_AE*a_DJ^2*p_AF*p_DI*p_EI*p_EJ - d_A*d_E*a_DJ*a_FJ*p_DI*p_EJ - a_AE*a_DJ*p_AF*p_DI*p_EI*p_EJ - d_D*d_J*a_AE*p_AF*p_EI - d_A*d_D*a_FJ*p_EI*p_EJ)

(-1) * (a_AE*a_DJ*a_FJ*p_AF*p_EJ - d_J*a_AE*a_DH*p_AF - d_A*a_DH*a_FJ*p_EJ)

(-1) * (d_I*a_AE^2*a_DJ*a_FJ*p_AF*p_EI*p_EJ + a_AE*a_DJ*a_FJ*p_AF*p_CI*p_EI*p_EJ - d_A*d_E*d_I*a_DJ*a_FJ*p_EJ - d_I*a_AE*a_DJ*p_AF*p_EI*p_EJ + d_A*a_DJ*a_FJ*p_CI*p_EI*p_EJ - d_J*a_AE*p_AF*p_CI*p_EI - d_A*a_FJ*p_CI*p_EI*p_EJ)

-d_C*a_BH*a_FJ*p_BG + a_BF*a_BH*p_BG*p_CG - d_B*a_FJ*p_CG

(-1) * (a_BF*a_BH*a_DJ^2*p_BG*p_DI*p_EJ + d_B*a_DH*a_DJ*a_FJ*p_DI*p_EJ - a_BF*a_BH*a_DJ*p_BG*p_DI*p_EJ - d_D*d_J*a_BF*a_BH*p_BG)

a_BH^2*a_DJ*a_FJ*p_BG*p_CH*p_EJ + d_J*a_BF*a_BH*a_DH*p_BG*p_CH - a_BH*a_DJ*a_FJ*p_BG*p_CH*p_EJ - d_B*d_H*a_DJ*a_FJ*p_EJ

(-1) * p_BG * (-d_I*a_BF*a_DJ*p_EJ + a_DJ*a_FJ*p_CI*p_EJ - d_J*a_BF*p_CI)

(-1) * (-d_F*a_AE*a_BH*p_EI + a_AE*a_BF*a_FJ*p_EI - d_E*a_BH*a_FJ)

(-1) * (d_F*a_AE*a_BH*a_DJ^2*p_DI*p_EI*p_EJ + a_AE*a_BF*a_DH*a_DJ*a_FJ*p_DI*p_EI*p_EJ + d_D*a_AE*a_BH*a_FJ^2*p_EI*p_EJ - d_F*a_AE*a_BH*a_DJ*p_DI*p_EI*p_EJ - d_D*d_F*d_J*a_AE*a_BH*p_EI - d_E*a_BH*a_DJ*a_FJ*p_DI*p_EJ - d_D*a_BH*a_FJ*p_EI*p_EJ)

(-1) * (a_AE*a_BH*a_DH*a_FJ^2*p_CH*p_EJ - d_F*d_J*a_AE*a_BH*a_DH*p_CH + d_H*a_AE*a_BF*a_DJ*a_FJ*p_EJ - a_BH*a_DH*a_FJ*p_CH*p_EJ)

(-1) * (-d_F*d_I*a_AE*a_DJ*p_EI*p_EJ + a_AE*a_FJ^2*p_CI*p_EI*p_EJ - d_F*d_J*a_AE*p_CI*p_EI - d_E*d_I*a_DJ*a_FJ*p_EJ + a_DJ*a_FJ*p_CI*p_EI*p_EJ - a_FJ*p_CI*p_EI*p_EJ)

-d_C*d_G*a_AE*a_BH*p_EI + a_AE*a_BH*p_AG*p_CG*p_EI + d_E*a_BH*p_AG*p_CG - a_AE*p_AG*p_CG*p_EI

(-1) * p_AG * (a_AE*a_DH*a_DJ*p_DI*p_EI - d_E*a_BH*a_DJ*p_DI - d_D*a_BH*p_EI)

-d_G*a_AE*a_BH*a_DJ*p_CH - d_H*a_AE*a_DJ*p_AG + a_BH*a_DH*p_AG*p_CH

(-1) * (d_G*a_AE*a_DJ*p_CI*p_EI - d_E*d_I*a_DJ*p_AG + a_DJ*p_AG*p_CI*p_EI - p_AG*p_CI*p_EI)

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.

## An ideal for reducing eigenvalues, as they appear in equations, to elementary symmetric functions element = ideal(*[P('f_' + str(zz)) - sum([prod([P(yy) for yy in xx]) for xx in Combinations(tnames,zz)]) for zz in range(1, qq + 1)]) ## not necessary, as it turns out, but included for generality 
       
element.groebner_basis() 
       
[t_3^3 - t_3^2*f_1 + t_3*f_2 - f_3, t_2^2 + t_2*t_3 + t_3^2 - t_2*f_1 -
t_3*f_1 + f_2, t_1 + t_2 + t_3 - f_1]
[t_3^3 - t_3^2*f_1 + t_3*f_2 - f_3, t_2^2 + t_2*t_3 + t_3^2 - t_2*f_1 - t_3*f_1 + f_2, t_1 + t_2 + t_3 - f_1]
 
       
## A routine to extract the i, j entry of the minimal polynomial, and factor it def z(amat, ii, jj): Mprod = prod(amat - P(xx) for xx in tnames) red = P((Mprod)[ii, jj].numerator()).reduce(element) if not red: # It complains if you try to factor 0 return P(0) fax = red.factor() return fax 
       
 
       
z(M, 2, 5) 
       
p_CG * (a_BF*a_BH*p_BG*p_CH + a_BF*p_AG*p_BG + p_AF*p_AG)
p_CG * (a_BF*a_BH*p_BG*p_CH + a_BF*p_AG*p_BG + p_AF*p_AG)
M2 = M(a_BH=-(a_BF*p_AG*p_BG + p_AF*p_AG)/(a_BF*p_BG*p_CH)) 
       
z(M2, 2, 5) 
       
0
0
z(M2, 4, 7) 
       
p_EI * (a_DH*a_DJ*p_DI*p_EJ + a_DH*p_CI*p_DI + p_CG*p_CI)
p_EI * (a_DH*a_DJ*p_DI*p_EJ + a_DH*p_CI*p_DI + p_CG*p_CI)
M2 = M2(a_DJ=-(a_DH*p_CI*p_DI + p_CG*p_CI)/(a_DH*p_DI*p_EJ)) 
       
z(M2, 4, 7) 
       
0
0
z(M2, 6, 9) 
       
p_AG * (a_BF*a_FJ*p_BG + a_AE*p_AF*p_EI + a_FJ*p_AF)
p_AG * (a_BF*a_FJ*p_BG + a_AE*p_AF*p_EI + a_FJ*p_AF)
M2 = M2(a_BF=-(a_AE*p_AF*p_EI + a_FJ*p_AF)/a_FJ/p_BG) 
       
z(M2, 6, 9) 
       
0
0
z(M2, 8, 1) 
       
p_CI * p_AG * (a_AE*a_DH*p_DI*p_EI - a_FJ*p_CG)
p_CI * p_AG * (a_AE*a_DH*p_DI*p_EI - a_FJ*p_CG)
M2 = M2(a_DH=a_FJ*p_CG/a_AE/p_DI/p_EI) 
       
z(M2, 8, 1) 
       
0
0
z(M2, 0, 3) 
       
(-1) * p_CI * p_AF * (a_AE^2*p_EI^2 + a_AE*a_FJ*p_EI + a_FJ^2)
(-1) * p_CI * p_AF * (a_AE^2*p_EI^2 + a_AE*a_FJ*p_EI + a_FJ^2)

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

 
       
# Extract the last factor in the list, and keep only the factor and not the multiplicity zpol = z(M2, 0, 3)[-1][0] zpol 
       
a_AE^2*p_EI^2 + a_AE*a_FJ*p_EI + a_FJ^2
a_AE^2*p_EI^2 + a_AE*a_FJ*p_EI + a_FJ^2

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

zpol == (a_AE*p_EI + a_FJ)^2 * 3/4 + (a_AE*p_EI - a_FJ)^2 * 1/4 
       
True
True