def checkMatrixSAP(sym, zerolist=None):
# sym: a symmetric matrix from which to produce a check matrix
# for the Strong Arnold Property
# zerolist: if specified, populate this list with the nonedges
n = sym.ncols() # size of matrix
if zerolist is None:
zerolist = [] # list of pairs of off-diagonal zero entries
else:
while len(zerolist) > 0:
zerolist.pop() # Always start empty.
for ii in range(n):
for jj in range(ii+1, n): # only check upper half
if not sym[ii,jj]: # if equal to zero
zerolist.append([ii, jj])
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), n*n, len(zerolist))
col = 0 # one column for each
for pair in zerolist: # zero pair in the matrix
row = 0 # one row for each skew-symmetric
for kk in range(n): # basis element E with 1 in kk, ll
for ll in range(n): # and -1 in ll, kk.
# record the value of EA + AE in the zero pair place
if ll == pair[0]:
outMatrix[row, col] += sym[kk, pair[1]]
if ll == pair[1]:
outMatrix[row, col] += sym[pair[0], kk]
row += 1 # advance a row in the check matrix
col += 1 # advance a column in the check matrix
return outMatrix # A has SAP if the rank is the number of columns
def hasSAP(sym):
check = checkMatrixSAP(sym)
return rank(check) == check.ncols()
def checkMatrixSSP(sym, zerolist=None):
# sym: a symmetric matrix from which to produce a check matrix
# for the Strong Spectral Property
# zerolist: if specified, populate this list with the nonedges
n = sym.ncols() # size of matrix
if zerolist is None:
zerolist = [] # list of pairs of off-diagonal zero entries
else:
while len(zerolist) > 0:
zerolist.pop() # Always start empty.
for ii in range(n):
for jj in range(ii+1, n): # only check upper half
if not sym[ii,jj]: # if equal to zero
zerolist.append([ii, jj])
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), n*(n-1)/2, len(zerolist))
col = 0 # one column for each
for pair in zerolist: # zero pair in the matrix
row = 0 # one row for each skew-symmetric
for kk in range(n): # basis element K with 1 in kk, ll
for ll in range(kk+1, n): # and -1 in ll, kk.
# record the value of AK - KA in the zero pair place
if ll == pair[1]:
outMatrix[row, col] += sym[pair[0], kk]
if kk == pair[1]:
outMatrix[row, col] -= sym[pair[0], ll]
if ll == pair[0]:
outMatrix[row, col] += sym[kk, pair[1]]
if kk == pair[0]:
outMatrix[row, col] -= sym[ll, pair[1]]
row += 1 # advance a row in the check matrix
col += 1 # advance a column in the check matrix
return outMatrix # A has SSP if the rank is the number of columns
def hasSSP(sym):
check = checkMatrixSSP(sym)
return rank(check) == check.ncols()
def checkMatrixSMP(sym, zerolist=None, q=None):
# sym: a symmetric matrix from which to produce a check matrix
# for the Strong Multiplicity Property
# q: an upper bound for the number of distinct eigenvalues
# zerolist: if specified, populate this list with the nonedges
n = sym.ncols() # size of matrix
if q is None:
q = n # easy upper bound
powerlist = [] # list of powers of sym
power = sym
for ii in range(2, q): # second through qth powers
power *= sym
powerlist.append(power)
if zerolist is None:
zerolist = [] # list of pairs of off-diagonal zero entries
else:
while len(zerolist) > 0:
zerolist.pop() # Always start empty.
for ii in range(n):
for jj in range(ii+1, n): # only check upper half
if not sym[ii,jj]: # if equal to zero
zerolist.append([ii, jj])
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), n*(n-1)/2 + q, len(zerolist))
col = 0 # one column for each
for pair in zerolist: # zero pair in the matrix
row = 0 # one row for each skew-symmetric
for kk in range(n): # basis element K with 1 in kk, ll
for ll in range(kk+1, n): # and -1 in ll, kk.
# record the value of AK - KA in the zero pair place
if ll == pair[0]:
outMatrix[row, col] += sym[kk, pair[1]]
if kk == pair[0]:
outMatrix[row, col] -= sym[ll, pair[1]]
if ll == pair[1]:
outMatrix[row, col] += sym[kk, pair[0]]
if kk == pair[1]:
outMatrix[row, col] -= sym[ll, pair[0]]
row += 1 # advance a row in the check matrix
for ii in range(2, q):
outMatrix[row, col] += powerlist[ii - 2][pair[0], pair[1]]
row += 1 # progress through the extra rows for powers
col += 1 # advance a column in the check matrix
return outMatrix # A has SMP if the rank is the number of columns
def hasSMP(sym):
check = checkMatrixSMP(sym)
return rank(check) == check.ncols()
def strongXList(sym, prop='SAP'):
compedge = []
prop = prop.upper()
if prop == 'SAP':
checkmat = checkMatrixSAP(sym, compedge)
elif prop == 'SMP':
checkmat = checkMatrixSMP(sym, compedge)
elif prop == 'SSP':
checkmat = checkMatrixSSP(sym, compedge)
else:
raise ValueError("Choices for prop are 'SAP', 'SMP', and 'SSP'.")
matlist = []
ker = checkmat.transpose().kernel().basis_matrix()
for ii in range(ker.nrows()):
thismat = Matrix(ker.base_ring(), sym.ncols())
for jj in range(ker.ncols()):
thismat[compedge[jj][0], compedge[jj][1]] = ker[ii,jj]
thismat[compedge[jj][1], compedge[jj][0]] = ker[ii,jj]
matlist.append(thismat)
return matlist