OKlibrary  0.2.1.6
Isomorphisms.mac
Go to the documentation of this file.
00001 /* Oliver Kullmann, 9.8.2008 (Swansea) */
00002 /* Copyright 2008, 2009, 2011 Oliver Kullmann
00003 This file is part of the OKlibrary. OKlibrary is free software; you can redistribute
00004 it and/or modify it under the terms of the GNU General Public License as published by
00005 the Free Software Foundation and included in this library; either version 3 of the
00006 License, or any later version. */
00007 
00022 oklib_include("OKlib/ComputerAlgebra/CombinatorialMatrices/Lisp/Basics.mac")$
00023 oklib_include("OKlib/ComputerAlgebra/Hypergraphs/Lisp/SetSystems.mac")$
00024 
00025 
00026 /* *****************************************************
00027    * The notion of "isomorphic combinatorial matrices" *
00028    *****************************************************
00029 */
00030 
00031 /*
00032   Combinatorial matrices are algebraic structures [A,B,f], where
00033   dom(f) = AxB, and thus an isomorphims from [A,B,f] to [A',B',f']
00034   is a pair [alpha,beta] of bijection alpha: A -> A', beta: B -> B'
00035   with f'(alpha(i),beta(j)) = f(i,j) for i in A, j in B.
00036 */
00037 
00038 
00039 /* ********************************
00040    * Incomplete isomorphism tests *
00041    ********************************
00042 */
00043 
00044 /* The following incomplete checks for matrix isomorphism return either
00045    "true", "false" or "unknown".
00046 */
00047 
00048 /* Simple checks, considering the sizes and the trivial cases: */
00049 is_isomorphic_incl0_com(A,B) := block(
00050  [d : dim_com(A)],
00051   if d # dim_com(B) then false
00052   else block([s : d[1] * d[2]],
00053     if s = 0 then true
00054     elseif s=1 then block(
00055      [reA : single_element(A[1]), ceA : single_element(A[2]),
00056       reB : single_element(B[1]), ceB : single_element(B[2])],
00057       is(A[3](reA,ceA) = B[3](reB,ceB)))
00058     else unknown))$
00059 /* Additionally considering row- and column-sums: */
00060 is_isomorphic_incl1_com(A,B) :=
00061   block([check0 : is_isomorphic_incl0_com(A,B)],
00062   if check0 # unknown then check0 else
00063     if rowsums_list_com(A) # rowsums_list_com(B) or
00064        columnsums_list_com(A) # columnsums_list_com(B)
00065     then false
00066     else unknown)$
00067 /* Stronger, compute the associated symmetric matrices and the
00068    characteristic polynomials: */
00069 is_isomorphic_incl2a_com(A,B) :=
00070   block([check0 : is_isomorphic_incl0_com(A,B)],
00071   if check0 # unknown then check0 else block(
00072    [a : com2m(A), b : com2m(B), x],
00073     if charpoly_m(a . transpose(a)) # charpoly_m(b . transpose(b)) then false
00074     else unknown))$
00075 /* Alternatively, consider the associated multisets of row/column-multisets: */
00076 is_isomorphic_incl2b_com(A,B) :=
00077   block([check0 : is_isomorphic_incl0_com(A,B)],
00078   if check0 # unknown then check0
00079   elseif com2omsoms_r(A) # com2omsoms_r(B) then false
00080   elseif com2omsoms_c(A) # com2omsoms_c(B) then false
00081   else unknown)$
00082 
00083 
00084 /* "All" invariants for combinatorial matrices: */
00085 is_isomorphic_inclall_com(A,B)  :=
00086   block([check : is_isomorphic_incl2b_com(A,B)],
00087   if check # unknown then check
00088   else block([a : com2m(A), b : com2m(B), x],
00089     is_isomorphic_inclall_scom(m2scom(a . transpose(a)), m2scom(b . transpose(b)))))$
00090 
00091 
00092 /* "All" invariants for square combinatorial matrices: */
00093 is_isomorphic_inclall_scom(A,B) :=
00094   block([check : is_isomorphic_incl2b_com(scom2com(A),scom2com(B))],
00095   if check # unknown then check
00096   else block([x],
00097     if charpoly_m(scom2m(A)) # charpoly_m(scom2m(B)) then false
00098     elseif maindiagoms_scom(A) # maindiagoms_scom(B) then false
00099     else unknown))$
00100 
00101 
00102 /* ******************************
00103    * Complete isomorphism tests *
00104    ******************************
00105 */
00106 
00107 /* Testing whether two combinatorial matrices are isomorphic by
00108    running through all row permutations of the first matrix.
00109    Prerequisites: A, B are non-empty.
00110    If the matrices are isomorphic, then a list containing the row
00111    permutation of A is returned, otherwise "false".
00112 */
00113 is_isomorphic_rowperm_com(A,B) := 
00114  block(
00115   [found : false,
00116    Bcolumns : sort(map(lambda([j],
00117                      map(lambda([i],B[3](i,j)),listify(B[1]))),
00118                    listify(B[2]))),
00119    L : listify(A[2])],
00120    for p in permutations(listify(A[1])) unless found#false do
00121      if Bcolumns = sort(map(lambda([j],
00122                           map(lambda([i],A[3](i,j)),p)),
00123                         L))
00124      then found : p,
00125    return(found))$
00126 
00127 /* Combining is_isomorphic_rowperm_com with the various tests: */
00128 
00129 is_isomorphic_rowperm0_com(A,B) := block(
00130  [check0 : is_isomorphic_incl0_com(A,B)],
00131   if check0=true then listify(A[1])
00132   elseif check0=false then false
00133   else is_isomorphic_rowperm_com(A,B))$
00134 is_isomorphic_rowperm0_com_p(A,B) := listp(is_isomorphic_rowperm0_com(A,B))$
00135 
00136 is_isomorphic_rowperm1_com(A,B) := block(
00137  [check1 : is_isomorphic_incl1_com(A,B)],
00138   if check1=true then listify(A[1])
00139   elseif check1=false then false
00140   else is_isomorphic_rowperm_com(A,B))$
00141 is_isomorphic_rowperm1_com_p(A,B) := listp(is_isomorphic_rowperm1_com(A,B))$
00142 
00143 is_isomorphic_rowperm2a_com(A,B) := block(
00144  [check2a : is_isomorphic_incl2a_com(A,B)],
00145   if check2a=true then listify(A[1])
00146   elseif check2a=false then false
00147   else is_isomorphic_rowperm_com(A,B))$
00148 is_isomorphic_rowperm2a_com_p(A,B) := listp(is_isomorphic_rowperm2a_com(A,B))$
00149 
00150 /* The "strongest" combination: */
00151 is_isomorphic_rowpermall_com(A,B) := block(
00152  [checkall : is_isomorphic_inclall_com(A,B)],
00153   if checkall=true then listify(A[1])
00154   elseif checkall=false then false
00155   else is_isomorphic_rowperm_com(A,B))$
00156 is_isomorphic_rowpermall_com_p(A,B) :=
00157  listp(is_isomorphic_rowpermall_com(A,B))$
00158 
00159 
00160 /* ************************
00161    * Duality and polarity *
00162    ************************
00163 */
00164 
00165 /* Tests whether a Maxima square matrix is isomorphic as a general
00166    matrix to a symmetric matrix: */
00167 selfpolar_bydef_m_p(M) := block([found : false],
00168   if rowsums_list_com(m2com(M)) # columnsums_list_com(m2com(M)) then
00169     return(false),
00170   for p in permutations(setn(matrix_size(M)[1])) unless found do
00171     found : symmetric_m_p(M . scom2m(trans_l2scom(p))),
00172   return(found))$
00173 
00174 /* Tests whether a square matrix is isomorphic as a general
00175    matrix to its transposed: */
00176 selfdual_bydef_com_p(M) := is_isomorphic_rowperm1_com_p(M,trans_com(M))$
00177 selfdual_bydef_m_p(M) := is_isomorphic_rowperm1_com_p(m2com(M),m2com(transpose(M)))$
00178 
00179 
00180 /* Experiment: searching for a smallest matrix which is self-dual but not
00181    self-polar. */
00182 
00183 /* Creating random square 0,1-matrices of order n; passed by reference
00184    are the total count of matrices and the count of self-dual found
00185    (which should be 0-initialised): */
00186 exp_dualpolar(n,_totalcount,_selfdualcount) := block([found : false],
00187  while found=false do block([M : random_m(n,n,2)],
00188   if oklib_monitor then print(M),
00189   if selfdual_bydef_m_p(M) then (
00190     _totalcount :: ev(_totalcount)+1,
00191     _selfdualcount :: ev(_selfdualcount)+1,
00192     if not selfpolar_bydef_m_p(M) then found : M
00193   )
00194   else _totalcount :: ev(_totalcount)+1),
00195  found)$
00196 
00197 /* Checking all square 0,1-matrices of order n: */
00198 exp_dualpolar2(n) := block(
00199  [found : false, M : all_m(n,n,[0,1]), count_sd : 0],
00200   for m in M while found=false do
00201     if selfdual_bydef_m_p(m) then (
00202       count_sd : count_sd + 1,
00203       if  not selfpolar_bydef_m_p(m) then
00204         found : m),
00205   return([found,count_sd]))$
00206 
00207