Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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

share|improve this question
    
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 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 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 at 15:58

1 Answer 1

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.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.