Identify my $\{-1,1\}$-matrix

29 Views Asked by At

Let $n$ be a positive integer. Let $\mathbb{F}$ be a field not of characteristic $2$.

Let $\mathbf{M} \in \mathbb{F}^{2^{n-1} \times n}$ be a matrix with entries from $\{-1_{\mathbb{F}},1_{\mathbb{F}}\}$ such that no two of its rows have the same entries and no two of its rows have their entries sum to $0$.

One may observe that such a matrix $\mathbf{M}$ continues to have its defining properties even if its rows are permuted, or if a row is negated (multiplied by $-1$).

It is then not hard to show that $\mathbf{M}$ is a partial Hadamard matrix. Indeed, suppose that $\mathbf{M}$ has more than $2^{n-2}$ rows for which $\left(\mathbf{M}\right)_{i,j}=\left(\mathbf{M}\right)_{i,k}$ for some fixed $j \neq k$, then negate each such row which has $\left(\mathbf{M}\right)_{i,j}=\left(\mathbf{M}\right)_{i,k}=-1$ in order to obtain that $\mathbf{M}$ has more than $2^{n-2}$ rows for which $\left(\mathbf{M}\right)_{i,j}=\left(\mathbf{M}\right)_{i,k}=1$, where they are all distinct and no two sum to $0$ - but this is impossible. Suppose now that $\mathbf{M}$ has less than $2^{n-2}$ rows for which $\left(\mathbf{M}\right)_{i,j}=\left(\mathbf{M}\right)_{i,k}$ for some fixed $j \neq k$, then negate each of the other rows which has $\left(\mathbf{M}\right)_{i,j}=-\left(\mathbf{M}\right)_{i,k}=-1$ in order to obtain that $\mathbf{M}$ has more than $2^{n-2}$ rows for which $\left(\mathbf{M}\right)_{i,j}=-\left(\mathbf{M}\right)_{i,k}=1$, where they are all distinct and no two sum to $0$ - but this is impossible. Hence any two columns of $\mathbf{M}$ agree at exactly half ($2^{n-2}$) the entries, thus $$ \mathbf{M}^{\top}\mathbf{M}=2^{n-1}\mathbf{I}_{n} $$ where $\mathbf{M}^{\top}$ is the transpose of $\mathbf{M}$ and $\mathbf{I}_{n}$ is the identity of $\mathbb{F}^{n \times n}$.

The above implies that my matrix is necessarily a partial Hadamard matrix, but being a partial Hadamard matrix is not sufficient, because for $ n \ge 5$ there are partial Hadamard matrices which do not respect my matrix's condition on the rows.

Is there a nice way to characterize my matrix (which does not invoke the condition on the rows explicitly)? Is my matrix known by some name? Does it correspond to a studied combinatorial design or to a special partial Hadamard matrix?