# Number of signatures of each type in a fixed column set of the Hadamard matrix

Consider a $$2^n \times 2^n$$ Walsh-Hadamard matrix (via Sylvester's construction). Fix a set $$S \subset [2^n]$$ of $$k\leq 2^{n-1}$$ columns.

Consider the rows in the $$2^n \times k$$ submatrix $$H'$$ that's obtained by dropping all columns not in $$S$$. Then we have $$2^n$$ many $$k$$-long row vectors. Consider the equivalence relation defined by multiplication by $$-1$$: $$u \sim v$$ iff. $$u = \pm v$$. There are $$2^{k}/2 = 2^{k-1}$$ equivalence classes this way. Is it true that the number of rows of $$H'$$ in each equivalence class is the same?

The $$2^n \times 2^n$$ Walsh-Hadamard matrix is given explicitly by $$M(u,v) = (-1)^{\langle u,v \rangle},$$ where $$u,v \in \{0,1\}^n$$, and the inner product is given by $$\langle u,v \rangle = \sum_{i=1}^n u_i v_i.$$ To simplify matters, we will assume henceforth that all computations are modulo 2.

If we restrict to columns $$v_1,\ldots,v_k$$, then we see a row $$\beta_1,\ldots,\beta_k$$ whenever $$\langle u, v_i \rangle = \beta_i, \quad i \in [k].$$ We can think of this as a linear system in $$u_1,\ldots,u_n \in \mathbb{F}_2$$. If the system has rank $$r$$, then there are either no solutions, or $$2^{n-r}$$ solutions.

In your case, you are identifying rows of the forms $$\beta_1,\ldots,\beta_k$$ and $$\beta_1+1,\ldots,\beta_k+1$$. A row is of one of these forms whenever $$\langle u, v_i + v_k \rangle = \beta_i, \quad i \in [k-1].$$ Again, this system either has no solutions, or $$2^{n-r}$$ solutions, where $$r$$ is the rank.

What this means is that every equivalence class of rows which appears at all, appears the same number of times.

In general, not all $$2^{k-1}$$ will appear. Indeed, there are only $$2^n$$ many rows, so if $$k > n+1$$ then this will certainly not be the case.

Another example is $$n = 3$$ and $$S = \{0,\ldots,7\}$$. Here only $$4$$ out of the $$8$$ possible equivalence classes appear, each of them appearing twice:

$$\begin{bmatrix} 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1\\ 1&1&1&1\\ 1&-1&1&-1\\ 1&1&-1&-1\\ 1&-1&-1&1 \end{bmatrix}$$

• Thank you, @Yuval Filmus, I actually meant to tag you under my question because I hoped you'll know the answer, but somehow the system wouldn't let me. Thanks again for this informative answer.
– gen
Nov 14, 2021 at 16:13