I'm trying to understand the exact degrees of freedom involved in constructing Hadamard matrices with elements in $\{1, -1\}$, and if possible, reduce them in such a way that they can be algorithmically generated.

For simplicity, I've chosen matrix A of order $n = 4k$ to be symmetric, with $Tr(A) = 0$ (diagonal is 111 ... -1-1-1), leaving $\frac{n(n-1)}2$ entries undetermined. In the example of a 4x4 matrix, there are 6 entries undetermined above the diagonal, and thus $2^6 = 64$ potential matrices. By hand, I've found that only 8 matrices work, their eigenvalues are always the same, and their eigenvectors are all the same down to absolute value of the entries:

$$-2 => \{-1, 1, 2, 0\}$$ $$-2 => \{-1, 1, 0, 2\}$$ $$2 => \{2, 0, 1, 1\}$$ $$2 => \{1, 1, 0, 0\}$$

The reason for why the absolute value of the entries is the same is unclear to me, and I'm not yet sure if this holds for higher dimensions. There does not seem to be a clear pattern behind how to change the signs in either the choices or the eigenvectors to find the next Hadamard matrix, either. There are 11 choices to make in the eigenvectors for sign, so it would be less work simply permutating signs through the entries and calculating the determinant, unless a pattern can be established.

For ease of defining the characteristic polynomial, I've assumed that all eigenvalues are real and come in $\pm$ pairs, with $\pm2$ having multiplicity $2k-1$, and $\pm2k^k$ having multiplicity 1. This leads to a positive determinant, an easy closed definition for the coefficients from binomial theorem, and the cancellation of the odd powered terms, although I've not figured out how I can use those coefficients in the construction of the matrices.

Perhaps exploring higher dimensions will give more clarity, but are there any papers attempting to tackle this kind of work? I've found papers that construct matrices with given characteristic polynomial limited to entries in $\mathbb Q$ or $\mathbb R$, but nothing quite so constrained as $\{1,-1\}$

Edit: It seems like $\pm\sqrt{n}$ with multiplicity $\frac{n}{2}$ would be a better choice for eigenvalues. Assuming normalized Hadamard (first row, column all equal to 1) also reduces choices to $\frac{(n-1)(n-2)}{2}$, and atleast for $n=4$, leaves 0 degrees of freedom.


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.