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.

Isomorphism testing by backtracking
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.
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.
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").
  • 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".
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.