BBFHHLSY_IEPG

2421 days ago by chlin

""" This Sage worksheet provides the following functions (in the last cell), using the abbreviation S?P means SAP, SMP, or SSP: TSS?P_matrix: to obtain the S?P tangent matrix; if induced_rows="nonedge", then return the S?P verification matrix; with_S?P: to return if the given matrix has the S?P or not. This worksheet also provides the verifications for the paper The Inverse eigenvalue problem of a graph: Multiplicities and minors by Wayne Barrett, Steve Butler, Shaun M. Fallat, H. Tracy Hall, Leslie Hogben, Jephian C.-H. Lin, Bryan L. Shader, Michael Young The code is written by Jephian C.-H. Lin """ 
       
# It is neccesary to evaluate the cell at the end. 
       
# Verifications for Proposition 3.4 
       
print "For C_4, the matrix" A=matrix(4,[0,1,0,-1, 1,0,1,0, 0,1,0,1, -1,0,1,0]) show(A); print "has spectrum", A.eigenvalues(), "."; print "Has the SSP?", with_SSP(A); print "Every shift and (nonzero) scale of this matrix still has the SSP." 
       
For C_4, the matrix
has spectrum [-1.414213562373095?, -1.414213562373095?,
1.414213562373095?, 1.414213562373095?] .
Has the SSP? True
Every shift and (nonzero) scale of this matrix still has the SSP.
For C_4, the matrix
has spectrum [-1.414213562373095?, -1.414213562373095?, 1.414213562373095?, 1.414213562373095?] .
Has the SSP? True
Every shift and (nonzero) scale of this matrix still has the SSP.
print "For K_{1,3}, the matrix" a,b=var("a b") A=matrix(4,[a,b,b,b, b,0,0,0, b,0,0,0, b,0,0,0]) show(A); print "has spectrum", A.eigenvalues(),"."; print "The SSP verification matrix B is"; B=TSSSP_matrix(A,"nonedge"); show(B); print "Then det(B*B.transpose()) is"; p=det(B*B.transpose()); show(p); print "which is never zero when b is nonzero, so B is always full-rank." 
       
For K_{1,3}, the matrix
has spectrum [1/2*a - 1/2*sqrt(a^2 + 12*b^2), 1/2*a + 1/2*sqrt(a^2 +
12*b^2), 0, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero when b is nonzero, so B is always full-rank.
For K_{1,3}, the matrix
has spectrum [1/2*a - 1/2*sqrt(a^2 + 12*b^2), 1/2*a + 1/2*sqrt(a^2 + 12*b^2), 0, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero when b is nonzero, so B is always full-rank.
# Verification for Lemma 3.5 
       
print "The matrix M_1" t=var("t") A=matrix(5,[-t^4+2*t^3-t^2-1,0,-(t-1)*t,(t-1)^2*t^2,0, 0,-t^4+2*t^3-t^2-1,0,-(t-1)*t^2,-(t-1)*t, -(t-1)*t,0,-t^2*(t^2-2*t+2),0,-(t-1)*t^2, (t-1)^2*t^2,-(t-1)*t^2,0,-t^2*(t^2-2*t+2),0, 0,-(t-1)*t,-(t-1)*t^2,0,-2*(t-1)^2*t^2]); show(A); print "has spectrum", A.eigenvalues(),"."; print "The SSP verification matrix B is"; B=TSSSP_matrix(A,"nonedge"); show(B); print "Let C be the induced submatrix of B on the first five columns." print "Then det(C) is"; C=B[:,[0,1,2,3,4]]; p=det(C); show(factor(p)); print "which is never zero when 0<t<1, so B is always full-rank." 
       
The matrix M_1
has spectrum [-3/2*t^4 + 3*t^3 - 2*t^2 - 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 +
3*t^2 + 2*t + 1)*(t - 1) - 1/2, -3/2*t^4 + 3*t^3 - 2*t^2 - 1/2*sqrt(t^6
- 2*t^5 + 3*t^4 + 3*t^2 + 2*t + 1)*(t - 1) - 1/2, -3/2*t^4 + 3*t^3 -
2*t^2 + 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 + 3*t^2 + 2*t + 1)*(t - 1) - 1/2,
-3/2*t^4 + 3*t^3 - 2*t^2 + 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 + 3*t^2 + 2*t +
1)*(t - 1) - 1/2, 0] .
The SSP verification matrix B is
Let C be the induced submatrix of B on the first five columns.
Then det(C) is
which is never zero when 0<t<1, so B is always full-rank.
The matrix M_1
has spectrum [-3/2*t^4 + 3*t^3 - 2*t^2 - 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 + 3*t^2 + 2*t + 1)*(t - 1) - 1/2, -3/2*t^4 + 3*t^3 - 2*t^2 - 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 + 3*t^2 + 2*t + 1)*(t - 1) - 1/2, -3/2*t^4 + 3*t^3 - 2*t^2 + 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 + 3*t^2 + 2*t + 1)*(t - 1) - 1/2, -3/2*t^4 + 3*t^3 - 2*t^2 + 1/2*sqrt(t^6 - 2*t^5 + 3*t^4 + 3*t^2 + 2*t + 1)*(t - 1) - 1/2, 0] .
The SSP verification matrix B is
Let C be the induced submatrix of B on the first five columns.
Then det(C) is
which is never zero when 0<t<1, so B is always full-rank.
print "The matrix M_2" a=var("a") A=matrix(5,[-1,1,-a,0,0, 1,-1,-a,0,0, -a,-a,2*a^2-2,-a,-a, 0,0,-a,0,0, 0,0,-a,0,0]); show(A); print "has spectrum", A.eigenvalues(),"."; print "The SSP verification matrix B is"; B=TSSSP_matrix(A,"nonedge"); show(B); print "Then det(B*B.transpose()) is"; p=det(B*B.transpose()); show(factor(p)); print "which is never zero when a is nonzero, so B is always full-rank." 
       
The matrix M_2
has spectrum [2*a^2, -2, -2, 0, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero when a is nonzero, so B is always full-rank.
The matrix M_2
has spectrum [2*a^2, -2, -2, 0, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero when a is nonzero, so B is always full-rank.
print "The matrix M_3" a=var("a") A=matrix(5,[1,-1,0,0,-a, -1,1,0,0,-a, 0,0,-a^2,a^2,a, 0,0,a^2,-a^2,a, -a,-a,a,a,2-2*a^2]); show(A); print "has spectrum", A.eigenvalues(),"."; print "The SSP verification matrix B is"; B=TSSSP_matrix(A,"nonedge"); show(B); print "Then det(B*B.transpose()) is"; p=det(B*B.transpose()); show(factor(p)); print "which is never zero when a is nonzero, so B is always full-rank." 
       
The matrix M_3
has spectrum [-2*a^2, -2*a^2, 2, 2, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero when a is nonzero, so B is always full-rank.
The matrix M_3
has spectrum [-2*a^2, -2*a^2, 2, 2, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero when a is nonzero, so B is always full-rank.
print "The matrix M_4" a,b,c=var("a b c") A=matrix(5,[a,0,b,b,b, 0,-a*c^2,b*c,b*c,b*c, b,b*c,0,0,0, b,b*c,0,0,0, b,b*c,0,0,0]); show(A); print "has spectrum", A.eigenvalues(),"."; print "The SSP verification matrix B is"; B=TSSSP_matrix(A,"nonedge"); show(B); print "Let C be the induced submatrix of B on the second to the fifth columns." print "Then det(C) is"; C=B[:,[1,2,3,4]]; p=det(C); show(factor(p)); print "which is never zero when b is nonzero and c is not 1 or -1, so B is always full-rank." 
       
The matrix M_4
has spectrum [-1/2*a*c^2 + 1/2*a - 1/2*sqrt(a^2*c^4 + 2*(a^2 +
6*b^2)*c^2 + a^2 + 12*b^2), -1/2*a*c^2 + 1/2*a + 1/2*sqrt(a^2*c^4 +
2*(a^2 + 6*b^2)*c^2 + a^2 + 12*b^2), 0, 0, 0] .
The SSP verification matrix B is
Let C be the induced submatrix of B on the second to the fifth columns.
Then det(C) is
which is never zero when b is nonzero and c is not 1 or -1, so B is
always full-rank.
The matrix M_4
has spectrum [-1/2*a*c^2 + 1/2*a - 1/2*sqrt(a^2*c^4 + 2*(a^2 + 6*b^2)*c^2 + a^2 + 12*b^2), -1/2*a*c^2 + 1/2*a + 1/2*sqrt(a^2*c^4 + 2*(a^2 + 6*b^2)*c^2 + a^2 + 12*b^2), 0, 0, 0] .
The SSP verification matrix B is
Let C be the induced submatrix of B on the second to the fifth columns.
Then det(C) is
which is never zero when b is nonzero and c is not 1 or -1, so B is always full-rank.
print "The matrix M_5" a=var("a") A=matrix(5,[a^2,0,sqrt(2)*a,a,a, 0,1,-sqrt(2),1,1, sqrt(2)*a,-sqrt(2),4,0,0, a,1,0,2,2, a,1,0,2,2]); show(A); print "has spectrum", A.eigenvalues(),"."; print "The SSP verification matrix B is"; B=TSSSP_matrix(A,"nonedge"); show(B); print "Then det(B*B.transpose()) is"; p=det(B*B.transpose()); show(factor(p)); print "which is never zero, so B is always full-rank." 
       
The matrix M_5
has spectrum [5, a^2 + 4, 0, 0, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero, so B is always full-rank.
The matrix M_5
has spectrum [5, a^2 + 4, 0, 0, 0] .
The SSP verification matrix B is
Then det(B*B.transpose()) is
which is never zero, so B is always full-rank.
# Verification for Proposition 4.2 
       
print "The matrix B" B=matrix(12,[1,-1,0,0,0,-1,sqrt(2),0,0,0,0,0, -1,1,-1,0,0,0,0,sqrt(2),0,0,0,0, 0,-1,1,-1,0,0,0,0,sqrt(2),0,0,0, 0,0,-1,1,-1,0,sqrt(2),0,0,0,0,0, 0,0,0,-1,1,-1,0,sqrt(2),0,0,0,0, -1,0,0,0,-1,1,0,0,sqrt(2),0,0,0, sqrt(2),0,0,sqrt(2),0,0,-2,0,0,2,0,0, 0,sqrt(2),0,0,sqrt(2),0,0,-2,0,0,2,0, 0,0,sqrt(2),0,0,sqrt(2),0,0,-2,0,0,2, 0,0,0,0,0,0,2,0,0,0,1,1, 0,0,0,0,0,0,0,2,0,1,0,1, 0,0,0,0,0,0,0,0,2,1,1,0]); show(B); print "has the SMP?", with_SMP(B); 
       
The matrix B
has the SMP? True
The matrix B
has the SMP? True
# Verification for Theorem 5.1 
       
print "For K_{1,6}, the matrix A" A=matrix(7,[[0, 1, 1, 1, 2, 2, 2], [1, 1, 0, 0, 0, 0, 0], [1, 0, 1, 0, 0, 0, 0], [1, 0, 0, 1, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0], [2, 0, 0, 0, 0, 0, 0]]); show(A); print "has spectrum", A.eigenvalues(),"."; print "has the SSP?", with_SSP(A); 
       
For K_{1,6}, the matrix A
has spectrum [4, 1, 1, 0, 0, -3.791287847477920?, 0.7912878474779200?] .
has the SSP? True
For K_{1,6}, the matrix A
has spectrum [4, 1, 1, 0, 0, -3.791287847477920?, 0.7912878474779200?] .
has the SSP? True
print "For S(2,1,1,1,1), the matrix A" A=matrix(7,[0, 1, 0, 3, 2, 1, 1, 1, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 3, 0, 0, 2, 0, 0, 0, 2, 0, 0, 0, 2, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0]); show(A); print "has spectrum", A.eigenvalues(),"."; print "has the SSP?", with_SSP(A); 
       
For S(2,1,1,1,1), the matrix A
has spectrum [5, 2, 2, 0, 0, -3.302775637731995?, 0.3027756377319947?] .
has the SSP? True
For S(2,1,1,1,1), the matrix A
has spectrum [5, 2, 2, 0, 0, -3.302775637731995?, 0.3027756377319947?] .
has the SSP? True
print "For S(2,2,1,1), the matrix A" A=matrix(7,[0, 2, 0, 2, 0, 1, sqrt(2), 2, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 0, 0, 2, 0, 0, 1, 1, 0, 0, 0, 0, 0, 1, 1, 0, 0, 1, 0, 0, 0, 0, 2, 0, sqrt(2), 0, 0, 0, 0, 0, 0]); show(A); print "has spectrum", A.eigenvalues(),"."; print "has the SSP?", with_SSP(A); 
       
For S(2,2,1,1), the matrix A
has spectrum [-3, 4, 1, 2, 2, 0, 0] .
has the SSP? True
For S(2,2,1,1), the matrix A
has spectrum [-3, 4, 1, 2, 2, 0, 0] .
has the SSP? True
def lex_sort(pairlist): """ Input: pairlist: a list of pairs Output: first change the order so that all pairs (i,j) has i<=j; then sort the list according to the lexicographic order, and return; Example: sage: l=[(2,4),(3,10),(5,2),(1,6),(2,100)]; sage: lex_sort(l); [(1, 6), (2, 4), (2, 5), (2, 100), (3, 10)] """ swapped_list=[]; for p in pairlist: i,j=p; if i<=j: swapped_list.append((i,j)); else: swapped_list.append((j,i)); Gap=max([p[1] for p in swapped_list])+1; swapped_list.sort(key=lambda k: k[0]*Gap+k[1]); return swapped_list; def zero_list(M): """ Input: M: a symmetric matrix; Output: the list of off-diagonal pairs (i,j) with M[i,j]==0 in lexicographic order; Example: sage: g=graphs.CompleteBipartiteGraph(2,3); sage: A=g.adjacency_matrix(); sage: zero_list(A); [(0, 1), (2, 3), (2, 4), (3, 4)] """ z_list=[]; n=M.dimensions()[0]; for i in range(n-1): for j in range(i+1,n): if M[i,j]==0: z_list.append((i,j)); return z_list; def mtx_to_vex(M,pickedlist=None): """ Input: M: a symmetric matrix; pickedlist: the list of entries (in order) to be picked; Output: return a vector (a list) recording the entries of M from pickedlist; If pickedlist=None, the default is all upper triangular entriees in the lexicographic order. Example: sage: A=matrix(3,[0,1,2,1,3,4,2,4,5]); sage: mtx_to_vex(A); [1, 2, 4] """ n=M.dimensions()[0]; if pickedlist==None: pickedlist=[]; for i in range(n): for j in range(i,n): pickedlist.append((i,j)); return [M[p] for p in pickedlist]; def TSSAP_matrix(M, induced_rows=None): """ Input: M: a symmetric matrix; induced_rows: a list of pairs (i,j) with i<=j; Output: By default, return the SAP tangent space matrix TS_A(M); If induced_rows is given, return the induced matrix of TS_A(M) on these rows. If induced_rows=="nonedges", return the SAP verification matrix. """ n=M.dimensions()[0]; if induced_rows=="nonedge": induced_rows=zero_list(M); column_list=[] for k in range(n): for l in range(n): Ekl=zero_matrix(n,n); Ekl[k,l]=1; column_list.append(mtx_to_vex(M*Ekl+Ekl.transpose()*M,induced_rows)); return matrix(column_list).transpose(); def TSSMP_matrix(M, induced_rows=None): """ Input: M: a symmetric matrix; induced_rows: a list of pairs (i,j) with i<=j; Output: By default, return the SMP tangent space matrix TS_M(M); If induced_rows is given, return the induced matrix of TS_M(M) on these rows. If induced_rows=="nonedges", return the SMP verification matrix. """ n=M.dimensions()[0]; if induced_rows=="nonedge": induced_rows=zero_list(M); column_list=[] for k in range(n-1): for l in range(k+1,n): Kkl=zero_matrix(n,n); Kkl[k,l]=1; Kkl[l,k]=-1; column_list.append(mtx_to_vex(M*Kkl+Kkl.transpose()*M,induced_rows)); q=M.minpoly().degree(); M_power=identity_matrix(n); for k in range(q): column_list.append(mtx_to_vex(M_power,induced_rows)); M_power=M_power*M; return matrix(column_list).transpose(); def TSSSP_matrix(M, induced_rows=None): """ Input: M: a symmetric matrix; induced_rows: a list of pairs (i,j) with i<=j; Output: By default, return the SSP tangent space matrix TS_M(M); If induced_rows is given, return the induced matrix of TS_S(M) on these rows. If induced_rows=="nonedges", return the SSP verification matrix. """ n=M.dimensions()[0]; if induced_rows=="nonedge": induced_rows=zero_list(M); column_list=[] for k in range(n-1): for l in range(k+1,n): Kkl=zero_matrix(n,n); Kkl[k,l]=1; Kkl[l,k]=-1; column_list.append(mtx_to_vex(M*Kkl+Kkl.transpose()*M,induced_rows)); return matrix(column_list).transpose(); def with_SAP(M): ver=TSSAP_matrix(M,"nonedge"); return ver.rank()==ver.dimensions()[0]; def with_SMP(M): ver=TSSMP_matrix(M,"nonedge"); return ver.rank()==ver.dimensions()[0]; def with_SSP(M): ver=TSSSP_matrix(M,"nonedge"); return ver.rank()==ver.dimensions()[0];