In[]:=
(*deployswithcanonicalname*)deploy
Mon 19 Jun 2023 21:35:58
Boolean matrices
Boolean matrices
In[]:=
booleanMatmul[mat1_,mat2_]:=Array[Inner[And,mat1[[#1,;;]],mat2[[;;,#2]],Or]&,{Length[mat1],Length[mat2]}];booleanEquals[mat1_,mat2_]:=And@@Flatten@MapThread[Xnor,{mat1,mat2},2];booleanGreaterEqual[mat1_,mat2_]:=And@@Flatten@MapThread[Or[#1,Not[#2]]&,{mat1,mat2},2];
Generate boolean matrices such that square is weakly transitive
Generate boolean matrices such that square is weakly transitive
{2,16,432,32242
genWeaklyTransitiveSquare[d_]:=Block[{x},mat=Array[x,{d,d}];vars=Flatten[mat];mat2=booleanMatmul[mat,mat];mat4=booleanMatmul[mat2,mat2];sat=booleanGreaterEqual[mat2,mat4];numSolutions=SatisfiabilityCount[sat,vars];booleSolutions=SatisfiabilityInstances[sat,vars,numSolutions];On[Assert];Assert[Length@booleSolutions==numSolutions];(*Convertsolutionstomatrixform*)matrixSolutions=mat/.Thread[vars->Boole@#]&/@booleSolutions];MatrixForm/@genWeaklyTransitiveSquare[2]
Out[]=
,
,
,
,
,
,
,
,
,
,
,
,
,
,
,
1 | 1 |
1 | 1 |
1 | 1 |
1 | 0 |
1 | 1 |
0 | 1 |
1 | 1 |
0 | 0 |
1 | 0 |
1 | 1 |
1 | 0 |
1 | 0 |
1 | 0 |
0 | 1 |
1 | 0 |
0 | 0 |
0 | 1 |
1 | 1 |
0 | 1 |
1 | 0 |
0 | 1 |
0 | 1 |
0 | 1 |
0 | 0 |
0 | 0 |
1 | 1 |
0 | 0 |
1 | 0 |
0 | 0 |
0 | 1 |
0 | 0 |
0 | 0 |
Count boolean matrices such that square is weakly transitive
Count boolean matrices such that square is weakly transitive
In[]:=
countWeaklyTransitiveSquare[d_]:=Block[{x},mat=Array[x,{d,d}];vars=Flatten[mat];mat2=booleanMatmul[mat,mat];mat4=booleanMatmul[mat2,mat2];sat=booleanGreaterEqual[mat2,mat4];numSolutions=SatisfiabilityCount[sat,vars]];countWeaklyTransitiveSquare/@Range[5]
Out[]=
{2,16,432,32242,7398488}
In[]:=
countWeaklyTransitiveSquare[6]
Out[]=
$Aborted
Count Weakly Transitive matrics
Count Weakly Transitive matrics
Number of transitive relations on n labeled nodes.
https://oeis.org/A006905
https://oeis.org/A006905
In[]:=
countWeaklyTransitive[d_]:=(mat=Array[x,{d,d}];mat2=booleanMatmul[mat,mat];SatisfiabilityCount[booleanGreaterEqual[mat2,mat],Flatten[mat]]);countWeaklyTransitive/@Range[5]
Out[]=
{2,13,333,34924,15339497}
In[]:=
countWeaklyTransitive[7]
Out[]=
878222530
Count boolean matrices such that square is idempotent
Count boolean matrices such that square is idempotent
{2,16,420,31114,7192088}
About 21% of all boolean matrices satisfy this constraint at size 5x5
In[]:=
countIdempotentSquare[d_]:=(mat=Array[x,{d,d}];vars=Flatten[mat];(*constructmat^2usingAnd/Orinsteadof*/+*)mat2=Array[Inner[And,mat[[#1,;;]],mat[[;;,#2]],Or]&,{d,d}];mat4=Array[Inner[And,mat2[[#1,;;]],mat2[[;;,#2]],Or]&,{d,d}];sat=And@@Flatten@MapThread[Xnor,{mat2,mat4},2];SatisfiabilityCount[sat,vars]);countIdempotentSquare/@{1,2,3,4}
Out[]=
{2,16,420,31114}
In[]:=
countIdempotentSquare[5]
Out[]=
7192088
In[]:=
7192088./
25
2
Out[]=
0.214341
In[]:=
countIdempotentSquare[6]
Out[]=
$Aborted
booleanMatmul[mat1_,mat2_]:=Array[Inner[And,mat1[[#1,;;]],mat2[[;;,#2]],Or]&,{Length[mat1],Length[mat2]}];booleanEquals[mat1_,mat2_]:=And@@Flatten@MapThread[Xnor,{mat1,mat2},2];booleanGreater[mat1_,mat2_]:=And@@Flatten@MapThread[Or[Not[#1],And[#1,#2]]&,{mat1,mat2},2];
Generate boolean matrices such that their square is transitive
Generate boolean matrices such that their square is transitive
In[]:=
genIdempotentSquare[d_]:=(mat=Array[x,{d,d}];vars=Flatten[mat];(*constructmat^2usingAnd/Orinsteadof*/+*)mat2=Array[Inner[And,mat[[#1,;;]],mat[[;;,#2]],Or]&,{d,d}];mat4=Array[Inner[And,mat2[[#1,;;]],mat2[[;;,#2]],Or]&,{d,d}];sat=And@@Flatten@MapThread[Xnor,{mat2,mat4},2];numSolutions=SatisfiabilityCount[sat,vars];booleSolutions=SatisfiabilityInstances[sat,vars,numSolutions];On[Assert];Assert[Length@booleSolutions==numSolutions];(*Convertsolutionstomatrixform*)matrixSolutions=mat/.Thread[vars->Boole@#]&/@booleSolutions);MatrixForm/@genIdempotentSquare[3]
Out[]=
Count idempotent matrices
Count idempotent matrices
https://mathematica.stackexchange.com/questions/286550/square-root-of-a-boolen-matrix/286752?noredirect=1#comment713844_286752
In[]:=
countIdempotent[d_]:=(mat=Array[x,{d,d}];vars=Flatten[mat];(*constructmat^2usingAnd/Orinsteadof*/+*)mat2=Array[Inner[And,mat[[#1,;;]],mat[[;;,#2]],Or]&,{d,d}];sat=And@@Flatten@MapThread[Xnor,{mat,mat2},2];numSolutions=SatisfiabilityCount[sat,vars]);countIdempotent/@Range[6]
Out[]=
{2,11,123,2360,73023,3494057}
List all idempotent matrices
List all idempotent matrices
List all square roots of identity
List all square roots of identity
List all square roots of all idempotent matrices
List all square roots of all idempotent matrices