This question is a follow up to a previous question of mine: Is it always possible to make two vectors orthogonal in the following case?
Suppose we are given a tuple, $S$, of $N$ vectors, each with $d$ components. In general, $S_i$ looks like:
$$ S_i = \begin{bmatrix} f_i(0) & f_i(1) & f_i(2) & \cdots \end{bmatrix}^T $$
(It is a column vector, I wrote it as a row vector as it took up too much vertical space)
Where $f_i(x) \colon \mathbb{N} \mapsto \{0, 1\}$.
Let's define the $overlap$ between two elements, $a, b \in S$ to be how many times $f_a(x) = f_b(x) = 1$. Every vector in $S$ is guaranteed to have at least $2$ overlap with every other vector.
If we were allowed to change any nonzero element in any vector an arbitrary number of times to a complex value with magnitude $1$, could we make $S$ an orthogonal set of vectors?
Another way to phrase this equivalently:
Could we come up with a tuple of diagonal matrices, where each element in each matrix has magnitude $1$, $U$, such that $U_a S_a \perp U_b S_b \: \forall a, b$?
An "easier" version of this is is:
Is there a tuple of unitary matrices, $U$, such that $U_aS_a \perp U_bS_b \: \forall a,b$?
However this easier version is pretty trivial. Let's call $v$ a set of orthogonal vectors. We can just define each successive $U$ to output an element of $v$ (each must be unique) when given their respective $S_i$. This is why I think the harder problem with only the diagonal matrix is more interesting.
No, it is not always possible to make $S$ an orthogonal set of vectors. Counterexample: consider the case where $N=2$ and $d=2$ and $S_1=[1,0]^T$, $S_2=[1,1]^T$. Every vector has at least $2$ overlap with every other vector, and we can change any nonzero element in any vector to a complex value with magnitude $1$. However, it is not possible to make $S$ an orthogonal set of vectors, because $\langle S_1,S_2\rangle \neq 0$.
The second phrasing is equivalent to the first. If $U_a$ is a diagonal matrix with each element having magnitude $1$, then $U_a S_a$ is just a rephrasing of the arbitrary modification of nonzero elements in $S_a$ to complex values with magnitude $1$.