BBFHHLSY_IEPG -- Sage

""" 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

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

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

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

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

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

Then det(B*B.transpose()) is

$\newcommand{\Bold}[1]{\mathbf{#1}}4 \, b^{6}$

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

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrr} -t^{4} + 2 \, t^{3} - t^{2} - 1 & 0 & -{\left(t - 1\right)} t & {\left(t - 1\right)}^{2} t^{2} & 0 \\ 0 & -t^{4} + 2 \, t^{3} - t^{2} - 1 & 0 & -{\left(t - 1\right)} t^{2} & -{\left(t - 1\right)} t \\ -{\left(t - 1\right)} t & 0 & -{\left(t^{2} - 2 \, t + 2\right)} t^{2} & 0 & -{\left(t - 1\right)} t^{2} \\ {\left(t - 1\right)}^{2} t^{2} & -{\left(t - 1\right)} t^{2} & 0 & -{\left(t^{2} - 2 \, t + 2\right)} t^{2} & 0 \\ 0 & -{\left(t - 1\right)} t & -{\left(t - 1\right)} t^{2} & 0 & -2 \, {\left(t - 1\right)}^{2} t^{2} \end{array}\right)$

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

$\newcommand{\Bold}[1]{\mathbf{#1}}\left(\begin{array}{rrrrrrrrrr} 0 & 0 & {\left(t - 1\right)} t^{2} & {\left(t - 1\right)} t & {\left(t - 1\right)} t & -{\left(t - 1\right)}^{2} t^{2} & 0 & 0 & 0 & 0 \\ {\left(t - 1\right)} t & {\left(t - 1\right)} t^{2} & 0 & 2 \, {\left(t - 1\right)}^{2} t^{2} - t^{4} + 2 \, t^{3} - t^{2} - 1 & 0 & 0 & 0 & 0 & -{\left(t - 1\right)} t & {\left(t - 1\right)}^{2} t^{2} \\ -{\left(t - 1\right)} t & 0 & 0 & 0 & -t^{4} + {\left(t^{2} - 2 \, t + 2\right)} t^{2} + 2 \, t^{3} - t^{2} - 1 & 0 & {\left(t - 1\right)} t^{2} & {\left(t - 1\right)} t^{2} & {\left(t - 1\right)} t & 0 \\ 0 & {\left(t - 1\right)}^{2} t^{2} & -{\left(t - 1\right)} t & 0 & -{\left(t - 1\right)} t^{2} & 0 & 0 & 0 & 0 & {\left(t - 1\right)} t^{2} \\ 0 & 0 & 0 & {\left(t - 1\right)}^{2} t^{2} & 0 & -{\left(t - 1\right)} t & -{\left(t - 1\right)} t^{2} & -{\left(t - 1\right)} t^{2} & 0 & 2 \, {\left(t - 1\right)}^{2} t^{2} - {\left(t^{2} - 2 \, t + 2\right)} t^{2} \end{array}\right)$

Let C be the induced submatrix of B on the first five columns.
Then det(C) is

$\newcommand{\Bold}[1]{\mathbf{#1}}2 \, {\left(t + 1\right)} {\left(t - 1\right)}^{7} t^{7}$

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

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

has spectrum [2*a^2, -2, -2, 0, 0] .
The SSP verification matrix B is

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

Then det(B*B.transpose()) is

$\newcommand{\Bold}[1]{\mathbf{#1}}64 \, {\left(a^{2} + 2\right)} a^{6}$

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

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

has spectrum [-2*a^2, -2*a^2, 2, 2, 0] .
The SSP verification matrix B is

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

Then det(B*B.transpose()) is

$\newcommand{\Bold}[1]{\mathbf{#1}}64 \, {\left(2 \, a^{2} + 1\right)} {\left(a^{2} + 2\right)} {\left(a^{2} + 1\right)}^{2} a^{4}$

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

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

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

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

Let C be the induced submatrix of B on the second to the fifth columns.
Then det(C) is

$\newcommand{\Bold}[1]{\mathbf{#1}}2 \, b^{4} {\left(c + 1\right)} {\left(c - 1\right)}$

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

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

has spectrum [5, a^2 + 4, 0, 0, 0] .
The SSP verification matrix B is

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

Then det(B*B.transpose()) is

$\newcommand{\Bold}[1]{\mathbf{#1}}8 \, {\left(a^{4} + 2 \, a^{2} + 5\right)} {\left(a^{2} + 9\right)} {\left(a^{2} + 1\right)}$

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

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

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

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

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

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

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

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

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];

BBFHHLSY_IEPG

2618 days ago by chlin