Basics.hpp File Reference

General plans regarding basic notions and functions for (combinatorial) matrices. More...

Go to the source code of this file.

Detailed Description

General plans regarding basic notions and functions for (combinatorial) matrices.

Complete the tests
  • Split-off several files.
  • RandomMatrices.mac
  • AlgebraicOperations.mac
  • DONE Isomorphisms.mac
Basic notions
  • DONE A "(combinatorial) matrix" is a triple [R,C,f], where R is the set of row indices, C the set of column indices, and f is a map with domain R x C.
  • DONE While a "square matrix" is a pair [I, f], where f is a map with domain I x I.
  • DONE Square matrices [I,f] can be converted to matrices [I,I,f].
  • DONE A matrix "over H" is a matrix whose values are elements of H.
  • So combinatorial matrices over {0,1} correspond to *incidence structures*, while combinatorial matrices over {-1,0,+1} correspond to labelled boolean clause-sets.
  • DONE We also have "ordered matrices" and "ordered square matrices", where instead of index-sets we have repetition-free lists.
  • DONE Abbreviations:
    1. "com" for combinatorial matrices
    2. "scom" for square combinatorial matrices
    3. "sycom" for symmetric combinatorial matrices: perhaps better not, since we only express type information?
    4. "ocom" for ordered combinatorial matrices
    5. "oscom" for ordered square combinatorial matrices
    6. ("osycom" for ordered symmetric combinatorial matrices).
  • DONE A "standardised combinatorial matrix" (stdcom) has index sets {1,...,n} for n in NN_0.
  • Reflect on the naming of "lmcom2m, lmscom2m" (compare with "Improving the okl-arrays" in ComputerAlgebra/DataStructures/Lisp/plans/HashMaps.hpp).
  • DONE (it seems using "matrix" is preferable) A matrix [R,C,f] can be converted to a Maxima matrix genmatrix(lambda([i,j],f(listify(R)[i],listify(C)[j])), length(R), length(C));
  • A square matrix M=[I,f] is converted into a directed graph dg(M) with vertex set I and an directed edge from i to j for i # j iff f(i,j) # 0.
  • dgl(M) has a loop at entry [i,i] iff f(i,i) # 0.
  • DONE The general hypergraph hyp(M) for matrix M=[I,J,f] has vertex set I, hyperedge set J, and hyperedge j contains vertex i iff f(i,j) # 0.
  • The labelled clause-set cls(M) for matrix M=[I,J,f] has variable set I, clause-index set J, while clause j contains variable i positively, negatively or not iff f(i,j) > 0, < 0, = 0 respectively.
  • For a general hypergraph G we can form the vertex-edge incidence matrix as well as the edge-vertex incidence matrix.
  • For a labelled clause-set F we can form the clause-variable matrix as well as the variable-clause matrix.
  • For a directed graph (with loops) G we can form the adjacency matrix.
Symmetric matrices
  • Maxima has "symmetricp" (in package "ctensor"), but this does not work.
    1. It seems to belong to the base, but is not defined.
    2. Then, after load(ctensor), it comes up with an error, showing that apparently it is defined differently.
    3. Make a bug-report.
Duality and polarity

Definition in file Basics.hpp.