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)?

-
According to the computer there are no solutions for n=9 and n=13. It found solution for n=5. Might be wrong. – joro Feb 5 '14 at 13:50
Indeed, a solution for $n=5$ is given by considering a symmetric square matrix of size $5$ with $1$ on the diagonal and $-1$ everywhere else. – Roland Bacher Feb 5 '14 at 14:03
Ehlich, Barba, and Wojtas did the work on matrix determinants for (some permutation of) orders 1,2, and 3 mod 4. Some recent accounts (e.g. Osborn or Orrick) of the Hadamard problem may talk enough about Gram matrices to say why you can't do optimal for 1 mod 4. – The Masked Avenger Feb 5 '14 at 15:58

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: