patternMinor
Matrix equality up to row/column permutations problem name
Viewed 0 times
problemequalitycolumnnamerowmatrixpermutations
Problem
Sorry for the trivial question; has the following decision problem an "official" (possibly short) name?
Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same up to row and column permutations.
(something like the short names used in complexity theory for decision problems: e.g. 3SAT, GI (Graph Isomorphism), X3C (Exact Cover By Three Set), CLIQUE, ...)
Given two $n \times m$ $\text{0-1}$ (binary) matrices $M_1, M_2$ check if they are the same up to row and column permutations.
(something like the short names used in complexity theory for decision problems: e.g. 3SAT, GI (Graph Isomorphism), X3C (Exact Cover By Three Set), CLIQUE, ...)
Solution
After a few observation in the comments (thanks to Hendrik Jan, Yuval Filmus, and D.W), I post an extended comment as an answer.
It seems (unless I'm missing something) that the problem is equivalent to Hypergraph isomorphism (HI):
The question remains valid ... is there a short name for the problem other than Hypergraph Isomorphism (if it appears somewhere not related to graph theory) ?
(if nobody post another answer in a few days I'll temporarily accept mine).
Additional stuff:
-
for proving that it is GI-complete it is enough to consider the incidence matrix of the source graphs $G_1, G_2$;
-
the reverse reduction is similar to the well known reduction from HI to GI: it is enough to consider the incidence matrix of the source hypergraphs $H_1, H_2$, transform them to graphs: every column becomes a node $c_i$, every row becomes a node $r_i$; an edge $(c_i,r_i)$ is added if and only if the corresponding cell contains a $1$; and finally a new triangle is linked to every set of nodes $\{c_{i_1},...,c_{i_m}\}$ that represents an hyperedge to preserve hyperedge mapping.
It seems (unless I'm missing something) that the problem is equivalent to Hypergraph isomorphism (HI):
- to prove that it is equivalent to HI, it is enough to use incidence matrices: every column represents a node of the hypergraph, every row represents an hyperedge (the $1$s are placed on the columns corresponding to the nodes of the hyperedge).
The question remains valid ... is there a short name for the problem other than Hypergraph Isomorphism (if it appears somewhere not related to graph theory) ?
(if nobody post another answer in a few days I'll temporarily accept mine).
Additional stuff:
-
for proving that it is GI-complete it is enough to consider the incidence matrix of the source graphs $G_1, G_2$;
-
the reverse reduction is similar to the well known reduction from HI to GI: it is enough to consider the incidence matrix of the source hypergraphs $H_1, H_2$, transform them to graphs: every column becomes a node $c_i$, every row becomes a node $r_i$; an edge $(c_i,r_i)$ is added if and only if the corresponding cell contains a $1$; and finally a new triangle is linked to every set of nodes $\{c_{i_1},...,c_{i_m}\}$ that represents an hyperedge to preserve hyperedge mapping.
Context
StackExchange Computer Science Q#23850, answer score: 2
Revisions (0)
No revisions yet.