has_SSP

3080 days ago by chlin

##This cell provides required functions. ##SSPmatrix(A) returns a matrix of {n \choose 2} rows and |E(Gbar)| columns. ##If X is a matrix with I o X=0 and A o X=0, then X has |E(Gbar)| variables; ## each column of SSPmatrix(A) represents one of these variables. ##Each row of SSPmatrix represents a restriction that ([A,X])_{i,j}=0 for all i<j. ##Therefore, A has SSP iff the rank of SSPmatrix(A) is |E(Gbar)|. ##Using this fact, has_SSP(A) returns True if A has SSP, and Fasle otherwise. def SSPmatrix(A): """ Input: a symmetric matrix A Output: the linear system given by SSP conditions """ n=A.dimensions()[0]; row_index={}; #{n+1 choose 2} restrictions column_index={}; #|E(Gbar)| variables res_counter=0; var_counter=0; for i in range(0,n): for j in range(i+1,n): row_index[i,j]=res_counter; res_counter+=1 if A[i,j]==0: column_index[i,j]=var_counter; column_index[j,i]=var_counter; var_counter+=1; SSP_sys=matrix(RR,res_counter,var_counter); for i in range(0,n): for j in range(i+1,n): for k in range(n): if k!=j and A[k,j]==0: SSP_sys[row_index[i,j],column_index[k,j]]+=A[i,k]; if i!=k and A[i,k]==0: SSP_sys[row_index[i,j],column_index[i,k]]-=A[k,j]; return SSP_sys; def has_SSP(A): """ Input: a symmetric matrix A (described by some graph G) Output: return if A has SSP or not. SSP means if for symmetric matrix B with AB-BA=0, A.Hadamard_product(B)=0, and I.Hadamard_product(B)=0, then B=0. Example: g=graphs.PathGraph(5); A=g.adjacency_matrix(); has_SSP(A); ->True """ SSP_sys=SSPmatrix(A); return rank(SSP_sys)==SSP_sys.dimensions()[1]; 
       
## Matrix for H tree print "H tree" A=matrix(6,6,[ [0,0,1,0,0,0], [0,0,1,0,0,0], [1,1,-1,1,0,0], [0,0,1,2,1,1], [0,0,0,1,1,0], [0,0,0,1,0,1]]) print "A=" show(A) print "rank=%s"%A.rank(); print "eigenvalues=%s"%A.eigenvalues(); print "Auxiliary SSP matrix for A:" show(SSPmatrix(A).change_ring(ZZ)); print "has_SSP?",has_SSP(A); 
       
H tree
A=
rank=4
eigenvalues=[1, 1, 0, 0, -2.192582403567252?, 3.192582403567252?]
Auxiliary SSP matrix for A:
has_SSP? True
H tree
A=
rank=4
eigenvalues=[1, 1, 0, 0, -2.192582403567252?, 3.192582403567252?]
Auxiliary SSP matrix for A:
has_SSP? True
## Matrix for campstool print "campstool" A=matrix(5,5,[ [1,1,1,0,0], [1,1,-1,0,0], [1,-1,0,1,1], [0,0,1,0,0], [0,0,1,0,0]]) print "A=" show(A) print "rank=%s"%A.rank(); print "eigenvalues=%s"%A.eigenvalues(); print "Auxiliary SSP matrix for A:" show(SSPmatrix(A).change_ring(ZZ)); print "has_SSP?",has_SSP(A); 
       
campstool
A=
rank=3
eigenvalues=[-2, 2, 2, 0, 0]
Auxiliary SSP matrix for A:
has_SSP? True
campstool
A=
rank=3
eigenvalues=[-2, 2, 2, 0, 0]
Auxiliary SSP matrix for A:
has_SSP? True
## Matrix for bowtie print "bowtie" A=matrix(5,5,[ [1,1,0,0,sqrt(6)], [1,1,0,0,sqrt(6)], [0,0,4,1,5], [0,0,1,4,5], [sqrt(6),sqrt(6),5,5,16]]) print "A=" show(A) print "rank=%s"%A.rank(); print "eigenvalues=%s"%A.eigenvalues(); print "Auxiliary SSP matrix for A:" show(SSPmatrix(A)); print "has_SSP?",has_SSP(A); 
       
bowtie
A=
rank=3
eigenvalues=[20, 3, 3, 0, 0]
Auxiliary SSP matrix for A:
has_SSP? True
bowtie
A=
rank=3
eigenvalues=[20, 3, 3, 0, 0]
Auxiliary SSP matrix for A:
has_SSP? True
## Matrix for long Y tree print "long Y tree" A=matrix(7,7,[ [0,1,0,1,0,1,0], [1,1,1,0,0,0,0], [0,1,1,0,0,0,0], [1,0,0,1,1,0,0], [0,0,0,1,1,0,0], [1,0,0,0,0,1,1], [0,0,0,0,0,1,1]]) print "A=" show(A) print "rank=%s"%A.rank(); print "eigenvalues=%s"%A.eigenvalues(); print "Auxiliary SSP matrix for A:" show(SSPmatrix(A).change_ring(ZZ)); print "has_SSP?",has_SSP(A); 
       
long Y tree
A=
rank=5
eigenvalues=[2, 2, 0, 0, -1.460504870018764?, 0.7608767217434455?,
2.699628148275318?]
Auxiliary SSP matrix for A:
has_SSP? True
long Y tree
A=
rank=5
eigenvalues=[2, 2, 0, 0, -1.460504870018764?, 0.7608767217434455?, 2.699628148275318?]
Auxiliary SSP matrix for A:
has_SSP? True
## Matrix for 3-sun print "3-sun" A=matrix(6,6,[ [2,1,1,1,0,0], [1,2,1,0,1,0 ], [1,1,2,0,0,1], [1,0,0,1,0,0 ], [0,1,0,0,1,0], [0,0,1,0,0,1]]) print "A=" show(A) print "rank=%s"%A.rank(); print "eigenvalues=%s"%A.eigenvalues(); print "Auxiliary SSP matrix for A:" show(SSPmatrix(A).change_ring(ZZ)); print "has_SSP?",has_SSP(A); 
       
3-sun
A=
rank=4
eigenvalues=[2, 2, 0, 0, 0.6972243622680054?, 4.302775637731994?]
Auxiliary SSP matrix for A:
has_SSP? True
3-sun
A=
rank=4
eigenvalues=[2, 2, 0, 0, 0.6972243622680054?, 4.302775637731994?]
Auxiliary SSP matrix for A:
has_SSP? True