# This is the calculation of the global rigidity of a graph G for a # generic configuration in d-dimensional space. p is a prime number # used to replace the generic calculations. > with(networks): > G:=complete(5,5): > delete(edges({5,6},G),G): > addvertex({11},G): > addedge({{11,5},{11,6},{11,7},{11,4}},G): > d:=3: > p:=1009: # This is the graph that will be used for the calculation. Various # graph operations are available to define the graph desired. The # vertices of G are labeled 1, .. , nops(vertices(G)), and the edges # are labled e1, .., nops(edges(G)). > with(linalg): # Warning, the assigned names charpoly and rank now have a global # binding # Warning, the protected names norm and trace have been redefined and # unprotected # The following procedure 'Stress' forms an n-by-n matrix with 4 # entries of 1 corresponding to the columns i and j. > Stress := proc( i,j,n ) > description "Forms an n-by-n stress matrix with a stress of 1 > between node i and node j"; > A:=Matrix(n) : A[i,i]:=1 : A[i,j]:=-1 : A[j,i]:=-1 : > A[j,j]:=1 : A > end proc: # Warning, `A` is implicitly declared local to procedure `Stress` # The following defines a list W of variables that will correspond to # the stresses on the edges of the graph G. The default is a generic # sequence of variables, but this is changed later with the subs # command. > W:=[seq(w[i],i=1..nops(edges(G)))]: # The following 'edgs' computes the vertex pairs that comprise the # edges of the graph G. > edgs := proc( G ) > description"Computes the node pairs of edges of the graph G"; > seq(ends(G)[i],i=1..nops(ends(G))); > end proc: # The following 'StrsMat' is the stress matrix corresponding to the # stresses given by W. (nops(W) must be nops(edges(G)).) > StrsMat:= proc( G,w ) > description"Computes the general sress matrix of the graph G > with stresses w[1]..w[nops(edges(G))"; > > simplify(add(w[i]*Stress(edgs(G)[i][1],edgs(G)[i][2],nops(vertices(G)) > ),i=1..nops(edges(G)))) ; > end proc: # The following is a configuration matrix P consisting of vertices(G) # column vectors in d-dimensional space. The default is that P is # random with variables x[i,j] mod p. > with(LinearAlgebra:-Modular): P := > Random(p,d,nops(vertices(G)),integer[]): # The following matrix X is the product of the configuration matrix P # and the stress matrix. > with(LinearAlgebra): X:=simplify(Multiply(P,StrsMat(G,W))): # Warning, these names have been rebound: Adjoint, BackwardSubstitute, # Basis, CharacteristicPolynomial, Copy, Determinant, # ForwardSubstitute, GramSchmidt, LUDecomposition, Multiply, Transpose # The following is a list of equations corresponding to the conditions # that each entry of X be 0. These are the equilibrium equations. > eq:=[seq(seq(X[i,j], i=1..d), j=1..nops(vertices(G)))]: # The following is the set of equations that are the consequence of the # equilibrium equations on the stress. This solution is then # substituted back into the stress vector W, with a choice of one (or # more) stress being 1 to eliminate the generic variables. You the # user must see what variable(s) Maple uses as the independent # variable(s) and then substitute a convenient (random?) value for it. > S:=solve({op(eq)},{op(W)}) mod p; S := {w[6] = w[6], w[1] = 1004 w[6], w[2] = 192 w[6], w[3] = 177 w[6], w[15] = 779 w[6], w[14] = 68 w[6], w[27] = 347 w[6], w[13] = 792 w[6], w[20] = 296 w[6], w[23] = 281 w[6], w[19] = 160 w[6], w[18] = 146 w[6], w[11] = 274 w[6], w[9] = 746 w[6], w[12] = 954 w[6], w[28] = 130 w[6], w[25] = 931 w[6], w[26] = 465 w[6], w[24] = 265 w[6], w[4] = 126 w[6], w[7] = 197 w[6], w[5] = 441 w[6], w[16] = 947 w[6], w[17] = 626 w[6], w[22] = 632 w[6], w[10] = 995 w[6], w[8] = 750 w[6], w[21] = 179 w[6]} > W:=subs(S,W); W := [1004 w[6], 192 w[6], 177 w[6], 126 w[6], 441 w[6], w[6], 197 w[6], 750 w[6], 746 w[6], 995 w[6], 274 w[6], 954 w[6], 792 w[6], 68 w[6], 779 w[6], 947 w[6], 626 w[6], 146 w[6], 160 w[6], 296 w[6], 179 w[6], 632 w[6], 281 w[6], 265 w[6], 931 w[6], 465 w[6], 347 w[6], 130 w[6]] # Here is where the actual substitution, which you must choose, is made. > W:=subs(w[6]=1,W); W := [1004, 192, 177, 126, 441, 1, 197, 750, 746, 995, 274, 954, 792, 68, 779, 947, 626, 146, 160, 296, 179, 632, 281, 265, 931, 465, 347, 130] # This new value for W is put back into the stress matrix to get the # stress matrix SM mod p. > SM:=StrsMat(G,W); [ 11 x 11 Matrix ] [ Data Type: anything ] SM := [ Storage: rectangular ] [ Order: Fortran_order ] # This converts the stress matrix mod p to all integer form which is # friendly for the mod p rank calculation. > B := Mod(p,SM, integer[]); [ 11 x 11 Matrix ] [ Data Type: integer[4] ] B := [ Storage: rectangular ] [ Order: C_order ] # These next commands put the machine in a mode to do the mod p rank # calculation. Then RowReduce does the rank calculation. > with(LinearAlgebra:-Modular): # Warning, these names have been rebound: Adjoint, BackwardSubstitute, # Basis, CharacteristicPolynomial, Copy, Determinant, # ForwardSubstitute, LUDecomposition, Multiply, Transpose > unprotect(det): > unprotect(linalg:-rank)# ; # Warning, inserted missing semicolon at end of statement, # ...linalg:-rank); > C := Copy(p,B): > RowReduce(p,C,nops(vertices(G)),nops(vertices(G)),nops(vertices(G)),'d > et',0,'rank',0,0,true): > rank; 7 > restart;