OKlibrary  0.2.1.6
Isomorphisms.hpp File Reference

Plans for isomorphisms of (combinatorial) matrices. More...

Go to the source code of this file.


Detailed Description

Plans for isomorphisms of (combinatorial) matrices.

Todo:
Isomorphism testing by backtracking
Todo:
Connections to other modules
  • Via isomorphism of combinatorial {-1,0,1}-matrices we can decide var-isomorphism of labelled clause-sets.
  • And isomorphism of general hypergraphs is the special case where only {0,1}-matrices are involved.
  • While isomorphism of graphs with loops is the special case where only square {0,1}-matrices are involved.
Todo:
Invariants for matrix isomorphism
  • Additionally to the distribution of row- and column-sums we should involve other invariants for isomorphic matrices.
  • DONE (covered by characteristic polynomial) We have the rank.
  • If matrices A, B are isomorphic, then the square matrices A^t A, B^t B are isomorphic, and, since A^t, B^t are isomorphic, also A A^t, B B^t are isomorphic (again, as square matrices(!)).
    1. So we can use invariants for square matrix isomorphism (see below).
    2. This covers the rank-criterion, since we have rank(A^t A) = rank(A A^t) = rank(A).
    3. DONE (covered by is_isomorphic_inclall_scom) The conditions for equal row- and column-sum-distributions are also covered by considering the associated square matrices, since their diagonals contain the column- and row-sums.
    4. DONE The matrices A^t A and A A^t (as well as B^t B and B B^t) have identical characteristic polynomials, so they don't need to be computed twice.
  • DONE (we have now is_isomorphic_incl2b_com) But the value-distributions for A, B are not covered.
  • A polytime computable invariant in case of externally square matrices is whether the matrices are fully indecomposable.
Todo:
Invariants for square matrix isomorphism
  • DONE The characteristic polynomial (compare "hermitian_rank_charpoly" in ComputerAlgebra/LinearAlgebra/Lisp/QuadraticForms.mac) should be a good invariant test.
  • Easier to compute are trace, rank and determinant, which are included when computing the characteristic polynomial for square matrices.
  • Another invariant is the main diagonal as a multiset.
    1. This is not covered by the characteristic polynomial, as the matrices [[2,0],[0,0]] and [[1,1],[1,1]] show which have both the characteristic polynomial x^2 - 2x.
  • Then we have the invariants for (general) matrices:
    1. row-sum distribution
    2. column-sum distribution
    3. value-distribution.
    As the above example shows, none of these invariants is covered by the characteristic polynomial.
  • Using scom2dgl, we can compute invariants for the associated directed graphs (with loops):
    1. The number of loops.
    2. Strong connectedness (corresponding to "irreducibility").
Todo:
Self-duality
  • Compared to the standard checks for isomorphic matrices (see "Invariants for square matrix isomorphism" above), many tests can be saved:
    1. As mentioned above, the characteristic polynomials of A^t A and A A^t are necessarily identical, so this test can be saved at all.
    2. Other tests only need to be performed "half".
Todo:
Valued matrices and their homo- and isomorphisms
  • The matrix concept as a triple [I,J,A] can be extended to a quadruple [I,J,A,V], where V is the set of values, and thus A: I x J -> V.
  • Such generalised matrices could be called "valued matrices" (seems easier to use than "matrices with values").
  • The natural notion of homomorphism f: [I,J,A,V] -> [I',J',A',V'] is that of a triple f = [i,j,v], where i: I -> I', j: J -> J' and v: V -> V' such that f(A(x,y)) = A'(i(x),j(y)).
  • These are just called homomorphisms of valued matrices.
  • The corresponding isomorphisms are given when all maps i, j, v are bijections.
  • A valued square matrix is then a triple [I,A,V] with A: I^2 -> V, and a homomorphism f: [I,A,V] -> [I',A',V'] is a pair f = [i,v] with f(A(x,x')) = A'(f(x),f(x')). Isomorphisms are where i, v are bijections.
  • We need predicates (for checking whether something is a valued (square) matrix, or a homomorphism (isomorpism) for valued (square) matrices.
  • And we need again the algorithms for the isomorphism problem.

Definition in file Isomorphisms.hpp.