Almost Hadamard matrices

Question

As well-known, a Hadamard matrix is a square matrix with all coefficients $\pm 1$ and pairwise orthogonal rows or columns. Such matrices exist conjecturally in every dimension divisible by $4$. Call a matrix with an odd number $n$ of columns an "almost Hadamard matrix" if all its coefficients are $\pm 1$ and if all scalar products between distinct rows are $\pm 1$. We want to maximize the number of rows in almost Hadamard matrices: If $n\equiv 3\pmod 4$ this is easy: erase the last column of a Hadamard matrix of size $n+1$ (provided such a matrix exists). This yields a matrix with $n+1$ rows which is best possible. If $n\equiv 1\pmod 4$ the number of rows cannot exceed $n$ (argument: up to replacing rows by their opposites, we can suppose that all rows have an even number of coefficients $-1$. All scalar products between rows are now equivalent to $n$ modulo $4$ and a rank computation of the corresponding Gram matrix gives the result).

A solution with $n-1$ rows in the case $n\equiv 1\pmod 4$ is obtained by adding an arbitrary last column (with coefficients $\pm 1$) to a Hadamard matrix of size $n-1$.

For $n=5$ (and of course for $n=1$) there is a solution with $n$ rows but I am unaware of the existence of solutions with $n$ rows for any $n\equiv 1\pmod 4$ greater than $5$. Are there any?

Is there any literature on such almost Hadamard matrices (perhaps under a different terminology, they are for example related to systems of equiangular lines)?

Answer 1

You can find most useful information on this page, which however has not been updated since 2012. The initial question is different, but the partial solution they have found is relevant here.

Quote:
The Hadamard maximal determinant problem asks when a matrix of a given order with entries -1 and +1 has the largest possible determinant.

If the determinant of such an extremal matrix $M=M_n$ for $n\equiv1\pmod4$ attains Barba's bound $$\sqrt{ (2n-1) (n-1)^{n-1}},$$ which obviously needs $(2n-1)$ to be a perfect square, then $$M^TM=MM^T=J_n+(n-1)I_n$$ where $J_n$ is the all-$1$-matrix. So this matrix is an "almost Hadamard" (a.H.) matrix. (Moreover, all scalar products are $+1$.)
Examples are given for $n=5,13,25,41,61,113$.
If $2n-1=(2q+1)^2$ and $q$ is a prime power (note that the examples correspond to $q=1,2,3,4,5,7$), there is an explicit construction according to the paper
A. E. Brouwer, An infinite series of symmetric designs, Math. Centrum Amsterdam Report ZW 202/83 (1983).

If $(2n-1)$ is not a perfect square at all, we cannot conclude inversely that no square a.H. matrix exists, though I have a (kind of) heuristic argument against its existence:
What we can conclude is that $M^TM$ must have a determinant smaller than Barba's bound because it must be a square. This means that the set of column vectors cannot be split in two sets $V$ and $W$ such that $v^T_iv_j=w_i^Tw_j=+1$ and $v^T_iw_j=-1$. (Nor, similarly, for the rows.)
Before explaining why, here is an illustration of what I mean with those two sets. Take for instance the matrix $M$ given for $n=13$ in Gottfried Helms' comment. After some row and column permutations we have $$MM^T=-J_{13}+2J_5\oplus J_8+12I_{13}$$ and $$M^TM=-J_{13}+2J_3\oplus J_{10}+12I_{13},$$ written in compact form: $MM^T=$

n 1 1 1 1 - - - - - - - -
1 n 1 1 1 - - - - - - - -
1 1 n 1 1 - - - - - - - -
1 1 1 n 1 - - - - - - - -
1 1 1 1 n - - - - - - - -
- - - - - n 1 1 1 1 1 1 1
- - - - - 1 n 1 1 1 1 1 1
- - - - - 1 1 n 1 1 1 1 1
- - - - - 1 1 1 n 1 1 1 1
- - - - - 1 1 1 1 n 1 1 1
- - - - - 1 1 1 1 1 n 1 1
- - - - - 1 1 1 1 1 1 n 1
- - - - - 1 1 1 1 1 1 1 n

and similarly for $M^TM$. That is, the rows of $M$ come in two sets of sizes $5$ and $8$, while the columns of $M$ form two sets of sizes $3$ and $10$.
Now the determinant of such a block matrix is always $(2n-1) (n-1)^{n-1}$, independently of the block sizes. So if $(2n-1)$ is not a square, the rows and columns cannot be partitioned in such a way, which means that an $n\times n$ a.H. matrix cannot have this kind of "symmetries". And heuristically, the existence of such a matrix seems to me about as improbable as the existence of a projective plane of non prime-power order...

BUT based on the data of the above site, e.g. the $n=93$ example, I would conjecture that $n-1$ almost orthogonal vectors always exist.

Answer 2

If you regard each row of your desired matrix as a sequence of bipolar signals and each column as a time frame, then, with one additional condition that the matrix is circulant, what you're asking becomes a set of bipolar binary sequences whose periodic out-of-phase autocorrelations are either $+1$ or $-1$. Because such sequences are close to optimal for various purposes, most likely there are a bunch of known results in the intersection of information theory, signal processing, and design theory. (The caveat is that when $n \equiv 3 \pmod{4}$, you might be able to have one more row.)

For instance, if you take the binary $m$-sequence of period $2^m-1$, its out-of-phase atuocorrelations are always $-1$. Hence, by stacking all the $2^m-1$ cyclic shifts of the sequence, you have a desired square matrix, where the inner product between a pair of rows is always $-1$.

You can exploit this idea with other well-known sequences. For example, the Legendre sequence of period $n$ has optimal autocorrelations if and only if $n \equiv 3 \pmod{4}$, i.e., if $n$ is of the form $4k-1$, its out-of-phase autocorrelations are $-1$ just like $m$-sequences. Hence, all Lengendre sequences of period $n = 4k-1$ can be turned into square matrices with the desired property.

You can use design theory with this sequence approach as well. Take a cyclic difference set $D$ of order $n$, block size $k$, and index $\lambda$. Construct the $n$-dimensional vector $\boldsymbol{a} = (a_0,\dots,a_{n-1})$, where $a_i = -1$ if $i \in D$ and $a_i = 1$ otherwise. Then, it is straightforward to check that the inner product between $\boldsymbol{a}$ and any of its cyclic shift is exactly $n-4(k-\lambda)$ (except when you take the product of exactly the same vectors). Hence, by taking cyclic difference sets satisfying $n-4(k-\lambda) = -1$ or $1$ such as the cyclic $(19,10,5)$ difference set $D = \{0,1,4,5,6,7,9,11,16,17\}$, you obtain a desired square matrix by stacking the cyclic shifts of the corresponding vector.

A good reference book for such sequences that is mathematician-friendly is Sequence Design for Communications Applications by P. Fan and M Darnell.

The second edition of Handbook of Combinatorial Designs edited by C. J. Colbourn and J. H. Dinitz has a section for "Sequence Correlation" within Chapter "Hadamard Matrices and Related Designs."

I'm not sure if you can construct an $n \times n$ or $(n+1)\times n$ almost Hadamard matrix this way when there is no known Hadamard matrix of size $n$ if you stick with sequences whose out-of-phase autocorrelations are always $-1$. But if you allow them to be either $1$ or $-1$, maybe you can for many values of $n$.

Also, this is somewhat trivial, but your method of adding/deleting columns works for partial Hadamard matrices. Fortunately, Seraj made a reference request on partial Hadamard matrix and got a nice answer by Carlo Beenakker here:

Reference for partial Hadamard matrices

This should give not necessarily circulant examples with many rows.

I know this "answer" doesn't give a satisfactory answer to your question. But searching the literature (and the internet) with some of the keywords in this post may be a good starting point.