Zero forcing 4x4 grid after GM switching

1291 days ago by mrc3

load("https://raw.githubusercontent.com/jephianlin/minrank_aux/master/load_all.py") load_all() 
       
xrange test passed
Loading Zq_c.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_GiTjNM.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_cmVviZ.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_RwkIA1.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading general_Lib.sage...
---sshow, multi_sshow, tuple_generator, minimal_graphs, empty_array,
all_one_matrix, elementary_matrix, eigens_multi, sort_dictionary,
has_minor, etc.
Loading oc_diag_analysis.sage...
---gZ_leq, find_gZ, find_EZ, diagonal_analysis, etc.
Loading xi_dict.py...
---SAPreduced_matrix, has_SAP, find_ZFloor, Zsap, etc.
Loading mu_dict.py...
---get_mu_from_dict, find_mu, etc.
Loading SXP.sage...
This code contains extra copy of Z_game, Zell_game, Zplus_game, for the
completeness of Zsap_game program.
Loading matrix_forcing.py...
xrange test passed
Loading Zq_c.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_GiTjNM.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_cmVviZ.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_RwkIA1.pyx...
Loading minrank.py...
Loading inertia.py...
Loading general_Lib.sage...
---sshow, multi_sshow, tuple_generator, minimal_graphs, empty_array, all_one_matrix, elementary_matrix, eigens_multi, sort_dictionary, has_minor, etc.
Loading oc_diag_analysis.sage...
---gZ_leq, find_gZ, find_EZ, diagonal_analysis, etc.
Loading xi_dict.py...
---SAPreduced_matrix, has_SAP, find_ZFloor, Zsap, etc.
Loading mu_dict.py...
---get_mu_from_dict, find_mu, etc.
Loading SXP.sage...
This code contains extra copy of Z_game, Zell_game, Zplus_game, for the completeness of Zsap_game program.
Loading matrix_forcing.py...
URL='https://raw.githubusercontent.com/jephianlin/mr_JG/py2/' files=['Zq_c.pyx','Zq.py','zero_forcing_64.pyx','zero_forcing_wavefront.pyx','minrank.py', 'inertia.py'] for f in files: print("Loading %s..."%f); load(URL+f) 
       
Loading Zq_c.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_FpGqFB.pyx..\
.
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_VezyD1.pyx..\
.
Loading zero_forcing_wavefront.pyx...
Compiling
/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_zgNFVh.pyx..\
.
Loading minrank.py...
Loading inertia.py...
Loading Zq_c.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_FpGqFB.pyx...
Loading Zq.py...
Loading zero_forcing_64.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_VezyD1.pyx...
Loading zero_forcing_wavefront.pyx...
Compiling /home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_zgNFVh.pyx...
Loading minrank.py...
Loading inertia.py...
B=matrix([[0,0,0,0],[0,0,0,0],[0,0,0,0],[0,0,0,0]]); #print B N=matrix([[1,1,1,1,0,0,1,0,0,1,0,0],[1,0,0,1,1,1,0,1,0,0,1,0],[0,1,0,0,1,0,1,1,1,0,0,1],[0,0,1,0,0,1,0,0,1,1,1,1]]); #print N C=matrix([[0,1,1,0,0,0,0,1,0,0,1,0],[1,0,1,0,1,0,0,0,0,0,0,1],[1,1,0,0,0,1,0,0,1,0,0,0],[0,0,0,0,1,1,1,0,0,1,0,0],[0,1,0,1,0,1,0,0,0,0,0,1],[0,0,1,1,1,0,0,0,1,0,0,0],[0,0,0,1,0,0,0,1,1,1,0,0],[1,0,0,0,0,0,1,0,1,0,1,0],[0,0,1,0,0,1,1,1,0,0,0,0],[0,0,0,1,0,0,1,0,0,0,1,1],[1,0,0,0,0,0,0,1,0,1,0,1],[0,1,0,0,1,0,0,0,0,1,1,0]]); #print C Nc=matrix([[0,0,0,0,1,1,0,1,1,0,1,1],[0,1,1,0,0,0,1,0,1,1,0,1],[1,0,1,1,0,1,0,0,0,1,1,0],[1,1,0,1,1,0,1,1,0,0,0,0]]); #print Nc 
       
A=block_matrix([ [B, N], [N.transpose(), C] ]); print A G=Graph(A) print('Z(G) is', find_Z(G)) print('Zplus(G) is', Zplus(G)) #Zskew is equivalent to find_loopedZ(g, []) print('Zskew(G) is', find_loopedZ(G, [])) 
       
[0 0 0 0|1 1 1 1 0 0 1 0 0 1 0 0]
[0 0 0 0|1 0 0 1 1 1 0 1 0 0 1 0]
[0 0 0 0|0 1 0 0 1 0 1 1 1 0 0 1]
[0 0 0 0|0 0 1 0 0 1 0 0 1 1 1 1]
[-------+-----------------------]
[1 1 0 0|0 1 1 0 0 0 0 1 0 0 1 0]
[1 0 1 0|1 0 1 0 1 0 0 0 0 0 0 1]
[1 0 0 1|1 1 0 0 0 1 0 0 1 0 0 0]
[1 1 0 0|0 0 0 0 1 1 1 0 0 1 0 0]
[0 1 1 0|0 1 0 1 0 1 0 0 0 0 0 1]
[0 1 0 1|0 0 1 1 1 0 0 0 1 0 0 0]
[1 0 1 0|0 0 0 1 0 0 0 1 1 1 0 0]
[0 1 1 0|1 0 0 0 0 0 1 0 1 0 1 0]
[0 0 1 1|0 0 1 0 0 1 1 1 0 0 0 0]
[1 0 0 1|0 0 0 1 0 0 1 0 0 0 1 1]
[0 1 0 1|1 0 0 0 0 0 0 1 0 1 0 1]
[0 0 1 1|0 1 0 0 1 0 0 0 0 1 1 0]
('Z(G) is', 10)
('Zplus(G) is', 10)
('Zskew(G) is', 10)
[0 0 0 0|1 1 1 1 0 0 1 0 0 1 0 0]
[0 0 0 0|1 0 0 1 1 1 0 1 0 0 1 0]
[0 0 0 0|0 1 0 0 1 0 1 1 1 0 0 1]
[0 0 0 0|0 0 1 0 0 1 0 0 1 1 1 1]
[-------+-----------------------]
[1 1 0 0|0 1 1 0 0 0 0 1 0 0 1 0]
[1 0 1 0|1 0 1 0 1 0 0 0 0 0 0 1]
[1 0 0 1|1 1 0 0 0 1 0 0 1 0 0 0]
[1 1 0 0|0 0 0 0 1 1 1 0 0 1 0 0]
[0 1 1 0|0 1 0 1 0 1 0 0 0 0 0 1]
[0 1 0 1|0 0 1 1 1 0 0 0 1 0 0 0]
[1 0 1 0|0 0 0 1 0 0 0 1 1 1 0 0]
[0 1 1 0|1 0 0 0 0 0 1 0 1 0 1 0]
[0 0 1 1|0 0 1 0 0 1 1 1 0 0 0 0]
[1 0 0 1|0 0 0 1 0 0 1 0 0 0 1 1]
[0 1 0 1|1 0 0 0 0 0 0 1 0 1 0 1]
[0 0 1 1|0 1 0 0 1 0 0 0 0 1 1 0]
('Z(G) is', 10)
('Zplus(G) is', 10)
('Zskew(G) is', 10)
Aafterswitching=block_matrix([ [B, Nc], [Nc.transpose(), C] ]); print Aafterswitching Gafterswitching=Graph(Aafterswitching) print('Z(Gafterswitching) is', find_Z(Gafterswitching)) print('Zplus(Gafterswitching) is', Zplus(Gafterswitching)) #Zskew is equivalent to find_loopedZ(g, []) print('Zskew(Gafterswitching) is', find_loopedZ(Gafterswitching, [])) 
       
[0 0 0 0|0 0 0 0 1 1 0 1 1 0 1 1]
[0 0 0 0|0 1 1 0 0 0 1 0 1 1 0 1]
[0 0 0 0|1 0 1 1 0 1 0 0 0 1 1 0]
[0 0 0 0|1 1 0 1 1 0 1 1 0 0 0 0]
[-------+-----------------------]
[0 0 1 1|0 1 1 0 0 0 0 1 0 0 1 0]
[0 1 0 1|1 0 1 0 1 0 0 0 0 0 0 1]
[0 1 1 0|1 1 0 0 0 1 0 0 1 0 0 0]
[0 0 1 1|0 0 0 0 1 1 1 0 0 1 0 0]
[1 0 0 1|0 1 0 1 0 1 0 0 0 0 0 1]
[1 0 1 0|0 0 1 1 1 0 0 0 1 0 0 0]
[0 1 0 1|0 0 0 1 0 0 0 1 1 1 0 0]
[1 0 0 1|1 0 0 0 0 0 1 0 1 0 1 0]
[1 1 0 0|0 0 1 0 0 1 1 1 0 0 0 0]
[0 1 1 0|0 0 0 1 0 0 1 0 0 0 1 1]
[1 0 1 0|1 0 0 0 0 0 0 1 0 1 0 1]
[1 1 0 0|0 1 0 0 1 0 0 0 0 1 1 0]
('Z(Gafterswitching) is', 10)
('Zplus(Gafterswitching) is', 9)
('Zskew(Gafterswitching) is', 10)
[0 0 0 0|0 0 0 0 1 1 0 1 1 0 1 1]
[0 0 0 0|0 1 1 0 0 0 1 0 1 1 0 1]
[0 0 0 0|1 0 1 1 0 1 0 0 0 1 1 0]
[0 0 0 0|1 1 0 1 1 0 1 1 0 0 0 0]
[-------+-----------------------]
[0 0 1 1|0 1 1 0 0 0 0 1 0 0 1 0]
[0 1 0 1|1 0 1 0 1 0 0 0 0 0 0 1]
[0 1 1 0|1 1 0 0 0 1 0 0 1 0 0 0]
[0 0 1 1|0 0 0 0 1 1 1 0 0 1 0 0]
[1 0 0 1|0 1 0 1 0 1 0 0 0 0 0 1]
[1 0 1 0|0 0 1 1 1 0 0 0 1 0 0 0]
[0 1 0 1|0 0 0 1 0 0 0 1 1 1 0 0]
[1 0 0 1|1 0 0 0 0 0 1 0 1 0 1 0]
[1 1 0 0|0 0 1 0 0 1 1 1 0 0 0 0]
[0 1 1 0|0 0 0 1 0 0 1 0 0 0 1 1]
[1 0 1 0|1 0 0 0 0 0 0 1 0 1 0 1]
[1 1 0 0|0 1 0 0 1 0 0 0 0 1 1 0]
('Z(Gafterswitching) is', 10)
('Zplus(Gafterswitching) is', 9)
('Zskew(Gafterswitching) is', 10)
# WE FOCUS ON Z+, and try to extend it to an infinite construction using the q-clique product of the graphs with themselves, for defs of the products see https://www.sciencedirect.com/science/article/abs/pii/S0166218X17303177 n=16 print('Using q-clique extension') ################################################################################## print('COSPECTRAL MATE product:') A=G.adjacency_matrix() A.eigenvalues() zeros=matrix(QQ, n, n, 0) P=block_matrix([ [A, A], [A, A] ]) print P.eigenvalues() GP=Graph(P); #GP.show() print('Zplus(GP) is', Zplus(GP)) print('COSPECTRAL MATE product after GM switching:') Aafterswitching=Gafterswitching.adjacency_matrix() Aafterswitching.eigenvalues() zeros=matrix(QQ, n, n, 0) Pafter=block_matrix([ [Aafterswitching, Aafterswitching], [Aafterswitching, Aafterswitching] ]) print Pafter.eigenvalues() GPafter=Graph(Pafter); #GPafter.show() print('Zplus(GPafter) is', Zplus(GPafter)) 
       
Using q-clique extension
COSPECTRAL MATE product:
[12, 4, 4, 4, 4, 4, 4, -4, -4, -4, -4, -4, -4, -4, -4, -4, 0, 0, 0, 0,
0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Traceback (click to the left of this block for traceback)
...
MemoryError
Using q-clique extension
COSPECTRAL MATE product:
[12, 4, 4, 4, 4, 4, 4, -4, -4, -4, -4, -4, -4, -4, -4, -4, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0]
Traceback (most recent call last):    A=G.adjacency_matrix()
  File "", line 1, in <module>
    
  File "/tmp/tmpAI4HJj/___code___.py", line 14, in <module>
    print('Zplus(GP) is', Zplus(GP))
  File "/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_kFa_hI.py", line 475, in Zplus
    return Zq_compute(G,0, return_track=return_track)
  File "/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_kFa_hI.py", line 472, in Zq_compute
    return Zq_bitset(G,q,push_zeros=push_zeros, return_track=return_track)
  File "/home/sageuser/3/.sage/temp/sage.math.iastate.edu/22485/tmp_kFa_hI.py", line 300, in Zq_bitset
    cost[Z]=n
MemoryError