# Function definitions
def make_zerolist(sym, zerolist=None):
""" Given a symmetric matrix sym, create or validate a list of places,
one per symmetric pair of off-diagonal entries, where the entries
of the matrix are zero.
If the list is non-empty, assume that missing items in the list
correspond to +/-0 entries, double edges that are allowed to vary.
If no list is passed in, create one and populate it.
In any of the functions below, if you want to know the meaning
of each column of the verification matrix, pass in an empty
list and upon return the same list will have column labels.
"""
nn = sym.ncols() # size of matrix
if zerolist is None:
zerolist = []
full_list = []
for ii in range(nn):
for jj in range(ii + 1, nn): # strict upper triangular part
if not sym[ii, jj]: # entry is zero
if sym[jj, ii]:
raise ValueError('Matrix is not combinatorially symmetric.')
full_list.append((ii, jj))
if not sym[jj, ii] and sym[ii, jj]:
raise ValueError('Matrix is not combinatorially symmetric.')
if zerolist is None:
return full_list
if not len(zerolist): # empty list was passed in
for xx in full_list:
zerolist.append(xx)
return zerolist
# Non-empty list just requires validation
for xx in zerolist:
if (xx[0], xx[1]) not in full_list and (xx[1], xx[0]) not in full_list:
raise ValueError('zerolist value ' + str(xx) + ' is not a zero location.')
return zerolist
print("make_zerolist(sym, zerolist=None): Create column labels for the X matrix.")
print("")
def checkMatrixSAP(sym, zerolist=None):
""" Given a symmetric matrix sym, produce a verification matrix for the
Strong Arnold Property, whose columns are independent iff sym has SAP.
"""
zerolist = make_zerolist(sym, zerolist)
nn = sym.ncols() # size of matrix
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), nn*nn, len(zerolist))
col = 0 # one column for each
for pair in zerolist: # zero pair in the matrix
row = 0 # one row for each entry of
for kk in range(nn): # the matrix AX, which should be zero.
for ll in range(nn):
# record the value of AX in this position.
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
print("checkMatrixSAP(sym, zerolist=None): Produce a check matrix for SAP.")
print("")
def hasSAP(sym):
""" Return True if sym has SAP. """
check = checkMatrixSAP(sym)
return rank(check) == check.ncols()
print("hasSAP(sym): Return True if sym has SAP.")
print("")
def checkMatrixSSP(sym, zerolist=None):
""" Given a symmetric matrix sym, produce a verification matrix for the
Strong Spectral Property, whose columns are independent iff sym has SSP.
"""
zerolist = make_zerolist(sym, zerolist)
nn = sym.ncols() # size of matrix
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), nn*(nn-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(nn): # basis element K with 1 in kk, ll
for ll in range(kk+1, nn): # 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
print("checkMatrixSSP(sym, zerolist=None): Produce a check matrix for SSP.")
print("")
def hasSSP(sym):
""" Return True if sym has SSP. """
check = checkMatrixSSP(sym)
return rank(check) == check.ncols()
print("hasSSP(sym): Return True if sym has SSP.")
print("")
def checkMatrixSIP(sym, zerolist=None):
""" Given a symmetric matrix sym, produce a verification matrix for the
Strong Interlacing Property, whose columns are independent iff sym has SIP.
"""
zerolist = make_zerolist(sym, zerolist)
nn = sym.ncols() # size of matrix
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), (nn-1)*(nn-2)/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(1, nn): # basis element K with 1 in kk, ll
for ll in range(kk+1, nn): # 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
print("checkMatrixSIP(sym, zerolist=None): Produce a check matrix for SIP.")
print("")
def hasSIP(sym):
""" Return True if sym has SIP. """
check = checkMatrixSIP(sym)
return rank(check) == check.ncols()
print("hasSIP(sym): Return True if sym has SIP.")
print("")
def checkMatrixSMP(sym, zerolist=None, q=None, find_q=True):
""" Given a symmetric matrix sym, produce a verification matrix for the
Strong Multiplicity Property, whose columns are independent iff sym has SSP.
The number of rows depends on an upper bound q on the number of distinct
eigenvalues of sym. If q is passed in, this is accepted as a known upper
bound. If no value for q is passed in (or None is passed in), then
calculate the degree of the minimal polynomial by default; otherwise
use the universal upper bound of n.
"""
zerolist = make_zerolist(sym, zerolist)
nn = sym.ncols() # size of matrix
if q is None:
if find_q:
q = sym.minpoly().degree()
else:
q = nn # universal upper bound
powerlist = [] # list of powers of sym
power = sym
for ii in range(2, q): # powers 2 through q - 1
power *= sym
powerlist.append(power + 0) # append a copy, just to be safe
# blank starting matrix
outMatrix = Matrix(sym.base_ring(), nn*(nn-1)/2 + len(powerlist), 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(nn): # basis element K with 1 in kk, ll
for ll in range(kk+1, nn): # 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
print("checkMatrixSMP(sym, zerolist=None): Produce a check matrix for SMP.")
print("")
def hasSMP(sym):
""" Return True if sym has SMP """
check = checkMatrixSMP(sym)
return rank(check) == check.ncols()
print("hasSMP(sym): Return True if sym has SMP.")
print("")
def strongXList(sym, prop='SAP'):
""" Return a basis for the space of X matrices which, if nonzero, show that sym does
not have property prop, which is one of 'SAP', 'SSP', 'SMP', or 'SIP'.
"""
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)
elif prop == 'SIP':
checkmat = checkMatrixSIP(sym, compedge)
else:
raise ValueError("Choices for prop are 'SAP', 'SMP', 'SSP', and 'SIP'.")
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
print("strongXList(sym, prop='SAP'): Produce a basis of X matrices making prop='SAP', 'SSP', 'SIP', or 'SMP' fail.")
print("")
|
make_zerolist(sym, zerolist=None): Create column labels for the X
matrix.
checkMatrixSAP(sym, zerolist=None): Produce a check matrix for SAP.
hasSAP(sym): Return True if sym has SAP.
checkMatrixSSP(sym, zerolist=None): Produce a check matrix for SSP.
hasSSP(sym): Return True if sym has SSP.
checkMatrixSIP(sym, zerolist=None): Produce a check matrix for SIP.
hasSIP(sym): Return True if sym has SIP.
checkMatrixSMP(sym, zerolist=None): Produce a check matrix for SMP.
hasSMP(sym): Return True if sym has SMP.
strongXList(sym, prop='SAP'): Produce a basis of X matrices making
prop='SAP', 'SSP', 'SIP', or 'SMP' fail.
make_zerolist(sym, zerolist=None): Create column labels for the X matrix.
checkMatrixSAP(sym, zerolist=None): Produce a check matrix for SAP.
hasSAP(sym): Return True if sym has SAP.
checkMatrixSSP(sym, zerolist=None): Produce a check matrix for SSP.
hasSSP(sym): Return True if sym has SSP.
checkMatrixSIP(sym, zerolist=None): Produce a check matrix for SIP.
hasSIP(sym): Return True if sym has SIP.
checkMatrixSMP(sym, zerolist=None): Produce a check matrix for SMP.
hasSMP(sym): Return True if sym has SMP.
strongXList(sym, prop='SAP'): Produce a basis of X matrices making prop='SAP', 'SSP', 'SIP', or 'SMP' fail.
|