SAP/SSP/SMP tester

2659 days ago by butler

### ### The following code was developed by Tracy Hall to ### give an automated method for determining if a matrix ### satisfies either: ### * Strong Arnold Property (SAP) ### * Strong Spectral Property (SSP) ### * Strong Multiplicity Property (SMP) ### (see https://arxiv.org/abs/1511.06705) ### ### To use the code first specify a symmetric matrix M ### and then run one of the following: ### hasSAP(M) ### hasSSP(M) ### hasSMP(M) ### 
       
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