has_SSP -- Sage

##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=

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr} 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 \end{array}\right)$

rank=4
eigenvalues=[1, 1, 0, 0, -2.192582403567252?, 3.192582403567252?]
Auxiliary SSP matrix for A:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrr} 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & -2 & -1 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 0 & -1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 & 0 \\ -1 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & -2 & -1 & -1 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & -1 & 0 & 1 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & 0 & -1 & 0 & 1 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 0 & -1 & -1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 1 & 0 & -2 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & 0 & 1 & 0 & -2 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)$

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=

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} 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 \end{array}\right)$

rank=3
eigenvalues=[-2, 2, 2, 0, 0]
Auxiliary SSP matrix for A:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} 0 & 0 & 0 & 0 & 0 \\ -1 & -1 & 0 & 0 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & -1 & -1 & 0 \\ 1 & 0 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 \\ 1 & 0 & -1 & 0 & 1 \\ 0 & 1 & 0 & -1 & 1 \\ 0 & 0 & 0 & 0 & 0 \end{array}\right)$

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=

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} 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 \end{array}\right)$

rank=3
eigenvalues=[20, 3, 3, 0, 0]
Auxiliary SSP matrix for A:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrr} 0.000000000000000 & 0.000000000000000 & 0.000000000000000 & 0.000000000000000 \\ -3.00000000000000 & -1.00000000000000 & 1.00000000000000 & 0.000000000000000 \\ -1.00000000000000 & -3.00000000000000 & 0.000000000000000 & 1.00000000000000 \\ -5.00000000000000 & -5.00000000000000 & 0.000000000000000 & 0.000000000000000 \\ 1.00000000000000 & 0.000000000000000 & -3.00000000000000 & -1.00000000000000 \\ 0.000000000000000 & 1.00000000000000 & -1.00000000000000 & -3.00000000000000 \\ 0.000000000000000 & 0.000000000000000 & -5.00000000000000 & -5.00000000000000 \\ 0.000000000000000 & 0.000000000000000 & 0.000000000000000 & 0.000000000000000 \\ -2.44948974278318 & 0.000000000000000 & -2.44948974278318 & 0.000000000000000 \\ 0.000000000000000 & -2.44948974278318 & 0.000000000000000 & -2.44948974278318 \end{array}\right)$

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=

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrr} 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 \end{array}\right)$

rank=5
eigenvalues=[2, 2, 0, 0, -1.460504870018764?, 0.7608767217434455?,
2.699628148275318?]
Auxiliary SSP matrix for A:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrrrrrrr} -1 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & -1 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ -1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & -1 & 0 & 0 & 1 \\ 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & -1 \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & -1 & 0 \\ 0 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \end{array}\right)$

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=

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrr} 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 \end{array}\right)$

rank=4
eigenvalues=[2, 2, 0, 0, 0.6972243622680054?, 4.302775637731994?]
Auxiliary SSP matrix for A:

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrr} -1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & -1 & 0 & 0 & 1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 1 & 0 \\ 0 & 0 & 0 & -1 & 0 & 1 & 0 & 0 & 0 \\ 0 & 0 & 1 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 0 & 0 & 1 & 0 \\ 1 & 0 & 0 & 0 & 0 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & -1 & 0 & 0 & 0 & 0 \\ 0 & 0 & 0 & 1 & 0 & -1 & 0 & 0 & 0 \end{array}\right)$

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

has_SSP

3145 days ago by chlin