Semi-orthogonal tall binary matrices with zero column sum

Question

I asked a question about tall semi-orthogonal matrices with zero sum over individual columns and how to arrive at them. This question follows up to deal with binary matrices of the same form and having the same constraints.

To summarize the previous question, we need a matrix $\mathbf{A_{m\times n}}$, with $m\gt n$ such that $\mathbf A^T\mathbf A=\mathbf I_n$, and

$$\sum_{i=1}^m a_{ij} = 0\qquad\forall j \in [1, n]$$

Under an additional constraint that all elements of $\mathbf A$ must be of the form $\pm\frac{1}{\sqrt m}$, under what conditions can we have $\mathbf A^T\mathbf A=\mathbf I_n$?

I can see that the least we need is $m=2k$ for some natural number $k\gt 1$. What other conditions are required?

Going further, what conditions are necessary to achieve $\mathbf e^T [\mathbf A^T\mathbf A-\mathbf I_n] \mathbf e \lt 0$ where $\mathbf e=\mathbf 1$?

Answer 1

Armed with the knowledge so far based on @kodlu's answer, to achieve a solution to the query for obtaining $\mathbf A_{m\times n}$ for $m=2^k$ we can start with a Sylvester Hadamard matrix and discard the first column since it is all ones and so doesn't satisfy $\sum a_i = 0$. Also discard any other columns until we are left with $n$ column vectors, i.e., $n$ equidistant constant weight binary codes with hamming distance and weights (number of ones) both equaling $m/2$. These remaining vectors will meet the desired criteria after normalization.

To answer the second part of the question, we could get $\mathbf e^T [\mathbf A^T\mathbf A-\mathbf I_n] \mathbf e \lt 0$ by using two Hadamard matrices $\mathbf{H}$ and $\mathbf{-H}$ for this space. Again ignoring the first column, we could select a vector from $\mathbf{H}$ and its complement from $\mathbf{-H}$. After $\lceil m/2\rceil$ selections followed by normalization, this will leave us with an $\mathbf A$ that will satisfy the inequality, where for $i\neq j$ half of the vectors will meet $\mathbf{v_iv_j}^T=-1$ and the remaining will satisfy $\mathbf{v_iv_j}^T=0$. Based on this argument, the lowest value we can get for $\mathbf e^T [\mathbf A^T\mathbf A-\mathbf I_n] \mathbf e$ should be $-m/2$.

Note 1: This solution assumes an $\mathbf H$ of the type exists where we can find at least $\lceil m/2\rceil$ columns having zero sum. This certainly is the case for Sylvester's method for $m=2^k$ or for Paley's cases (see reference 1). However, for an arbitrary $\mathbf H$ in $m$ dimensions, this might not be the case (see reference 2).

Note 2: Our solution is bounded by Plotkin bound, which is $n\le 2m$. However, for this specific query it is not an issue as $n \lt m$ is a tighter bound.

Answer 2

There aren't many possibilities.

If two binary vectors in $\{\pm 1\}^n$ are orthogonal (thus $n$ even) that means their Hamming distance is $n/2.$

Plotkin bound (see https://en.wikipedia.org/wiki/Plotkin_bound) tells us that $A_2(n,d)$ the maximum number of binary codewords with length $n$ and minimum distance $d$ obeys $$ A_2(2d,d)\leq 4d $$ when $d$ is even. Thus you can have at most $m=4d=4(n/2)=2n.$ Take a Hadamard matrix (when it exists) and complement its rows and you can achieve this.

Edit: After taking complements, a row of the Hadamard and its complement are at pairwise distance $n$. Since all distinct rows of the Hadamard matrix are at distance $n/2$ the distance from an original row of the Hadamard matrix to a complement of another row of the Hadamard matrix is also $n/2.$

In particular, this is what is called a first order Reed Muller code if we take length $n=2^k,$ and a Sylvester Hadamard matrix.