Computational complexity of colored vector space isomorphism over the binary field

Question

Suppose there are two vector spaces $V$ and $W$ of the same dimension $n$ over the binary field $\mathbb{Z}_2$ together with subsets $S_V$ and $S_W$ of $V \setminus \{0\}$ and $W \setminus \{0\}$, respectively. Equivalently, one can think of $S_V$ and $S_W$ as sets of white points that determine the coloring of $V \setminus \{0\}$ and $W \setminus \{0\}$ into two colors (black and white). We say that $(V, S_V)$ and $(W, S_W)$ are isomorphic if and only if there exists a vector space isomorphism (i.e. an invertible linear map) $f: V \to W$ s.t. $f(S_V) = S_W$.

The input data is given as two bitmaps (each of size $2^n-1$). There are 3 related problems:

1. Determine whether $(V, S_V)$ is isomorphic to $(W, S_W)$.
2. Given only $(V, S_V)$, determine a canonical form (map $f_V: V \to \mathbb{Z}_2^n$, i.e. a basis in $V$) s.t. $f_V(S_V) = f_W(S_W)$ if and only if $(V, S_V)$ is isomorphic to $(W, S_W)$.
3. Given only $(V, S_V)$, find an invariant (i.e. a bitstring $I(V, S_V)$) s.t. $I(V, S_V) = I(W, S_W)$ if and only if $(V, S_V)$ is isomorphic to $(W, S_W)$.

Clearly, a solution of #2 implies a solution of #3 and a solution of #3 implies a solution of #1.

What are the proper scientific names of these problems? What is their computational complexity (e.g., can they be solved for $n=16$)?

Answer 1

The first problem is more or less the same as code equivalence problem over the field with 2 elements. It is clear that two subsets can be isomorphic only if the number of coordinates is the same. Denote by $M_V$ the matrix containing all points of $V$ as columns. Then $V$ and $W$ are isomorphic if and only if $M_V = A M_W P$ with $A$ invertible and $P$ permutation matrix. Here $A$ is essentially your map $f$, and $P$ accounts for the fact that our sets are unordered.

Code equivalence problem was first considered in E. Petrank, R. M. Roth "Is code equivalence easy to decide?", IEEE Trans. Inf. Theory 43(5):1602–1604 (1997). They proved that this problem is GI-hard, that is, if you can solve code equivalence, then you can also solve graph isomorphism. This also means you are unlikely to find polynomially computable normal forms or invariants for your problems 2 and 3, as they are unlikely to exist for graphs.

As for practical algorithms, I cannot help you. I was told that there are quite good practical solutions for graph isomorphism, at least for graphs appearing in applications, but I don't know any specifics. It is likely that $n$ is not the parameter you need to worry about, the number of points in your sets is more important.