Designing a Hadamard matrix design of order 12 using Algebra methods

Question

I am trying to design a Hadamard design of n=12. it takes a lot of times, I want to convert the problem into algebra and I hope the problem become easier to find the values of the matrix.

we have 12 by 12 matrix, all rows and columns have -1s and 1s, and we have the following conditions:

P1. First row and First column has a value of 1. (this condition is to make the matrix as normalized matrix)

P2. Each row has 3 common of 1s with other rows.

P3. Each column has 3 common of -1s with other columns.

P4. Each row and columns has 6 digits of -1s.

P5. Each row and column has 6 digits of 1s.

so far I have reached row no. 7 and I'm struggling to find the correct values for it, the difficult thing are properties P2 and P3. My technique is build each row based on the previous rows, so each new row must achieve the five properties.

My construction is as following:

\begin{array}{|c|c|c|c|c|c|c|c|c|c|c|c|}\hline 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1& 1 &1\\\hline 1 & -1 & -1 & -1 & -1 & -1 & -1 & 1 & 1 & 1 & 1 & 1\\\hline 1 & 1 & 1 & 1 & -1 & -1 & -1 & 1 & 1 & -1 & -1 & -1\\\hline 1 & -1 & -1 & 1 & 1 & 1 & -1 & 1 & -1& 1 & -1 & -1\\\hline 1 & 1 & -1 & 1 & -1 & -1 & 1 & -1&-1& 1& 1 &-1\\\hline 1 & 1 & -1 & -1 & -1 & 1 & 1 & 1 & -1 & -1& -1 &1\\\hline & & & & & & & & & & &\\\hline \end{array}

Now in order to find the values of 7th row, then I did the following: Suppose i is the ith row and j is the column in matrix. The number of -1s in jth column is denoted by y_j, so for example in column no. 12, we have -1s in rows $x_2, x_3, x_4$ so we write the following formula: $y_{12} = x_2 + x_3 + x_4$. Now, if we continue to do the same for all columns, we have following formulas

$x_1 + x_3 = y_2$

$x_1 +x_3 + x_4 + x_5 = y_3$

$x_1 + x_5 = y_4$

$x_1 + x_2 + x_4 + x_5 = y_5$

$x_1 + x_2 + x_3 = y_7$

$x_4 = y_8$

$x_3+x_4+x_5=y_9$

$x_2+x_5 = y_{10}$

$x_2 + x_3 + x_5 = y_{11}$

$x_2 + x_3 + x_4 = y_{12}$

Now, we want to find 6 of different ys, such that all equal to 3 of each x, i.e.: $y_i + y_j + y_k + y_l + y_m + y_n = 3x_1 + 3x_2 + 3x_3 + 3x_4 + 3x_5$ where $i,j,k,l,m,n \in \{ 2,3,4,5,6,7,8,9,10,11,12 \}$ Do you have an idea how to do this in algebra to find i,j,k,l,m, and n so that the equality hold? the number of different possible values is: 11 choose 6 = 462, and of course a lot of these numbers doesn't achieve the properties, do you know to find these ys in easy way?

---

UPDATE: I have reduces the number of possible from 462 to only 30, since we must choose 2,3,4,5,6,7 for three ys and 8,9,10,11,12 for the other remaining ys, so 6 choose 3 = 20 and 5 choose 3 = 10. and checking this number is possible. The reason is that for each new row, we need to choose 3 of ys for first row since first row has -1 from 2 to 7, and so we have 20 possible ways for choosing ys. and the remaining is 3 of ys for other five columns.

Thank you!

Answer 1

Note that your conditions 2-5 apply only to rows or columns other than the first. Also note that conditions 4 and 5 imply that each of rows 2-12 is orthogonal to row 1 and that each of columns 2-12 is orthogonal to column 1. Third, note that conditions 2 and 3 imply that any two rows taken from rows 2-12 forms an orthogonal pair, and likewise for two columns taken from columns 2-12.

If you find a solution, and then permute columns 2-11 in any way whatsoever and permute rows 2-11 in any way whatsoever, then you have another solution. It turns out that this design has a lot of symmetry, which means that these permuted solutions won't all be different from each other. Even so, the number of solutions is going to be large. For that reason, it will be helpful to impose a canonical ordering on rows to reduce the number of possibilities.

You may also negate some rows or columns without destroying the orthogonality property of rows or of columns, although your five conditions may no longer hold. This implies that if you can find a $12\times12$ matrix with elements $\pm1$ and orthogonal rows (and hence columns), then you can obtain your desired design by negating rows and columns as needed so that the first row and column contain only $1$s. If this is done, your other four properties will automatically hold. I find it somewhat more convenient not to start with a first row that contains only $1$s, but rather to insist that in the first three rows of each column have an even number of $-1$s, which means either three $1$s or one $1$ and two $-1$s. First prove the following:

1. The first three rows contain equal numbers of the four column types $$ \begin{bmatrix}1\\1\\1\end{bmatrix},\qquad\begin{bmatrix}1\\-1\\-1\end{bmatrix},\qquad\begin{bmatrix}-1\\1\\-1\end{bmatrix},\qquad\begin{bmatrix}-1\\-1\\1\end{bmatrix}, $$ three of each type in the case of a $12\times12$ matrix. We may accordingly partition the columns into four sets of three.
2. In row $k$, with $k>3$, these four column sets will contain equal numbers of $1$s.

Clearly these properties hold for columns as well as rows. These observations allow us to put the first three rows and first three columns in a standard form $$ \begin{bmatrix} 1 & 1 & 1 & 1 & 1 & 1 & - & - & - & - & - & -\\ 1 & 1 & 1 & - & - & - & 1 & 1 & 1 & - & - & -\\ 1 & 1 & 1 & - & - & - & - & - & - & 1 & 1 & 1\\ 1 & - & -\\ 1 & - & -\\ 1 & - & -\\ - & 1 & -\\ - & 1 & -\\ - & 1 & -\\ - & - & 1\\ - & - & 1\\ - & - & 1 \end{bmatrix} $$ Since in each of rows 4-12, the first column set contains one $1$ and two $-1$s, this must also be true of each of the other three column sets obtained from the partition described above. If you impose the condition that whenever there are multiple equivalent possibilities for next row to be added, the lexicographically minimal choice is taken (with $1$ coming before $-1$), then the rest of the structure is forced by the orthogonality condition on rows. You can then obtain your design by negating the last six rows and the last six columns.

Added: To see how the structure is forced, consider row 4. It must have one $1$ in each of the four sets of three columns determined by the partition of columns described above. (The first set of three is already determined.) To be lexicographically minimal, the order of elements must be $\begin{bmatrix}1 & -1 & -1\end{bmatrix}$ in each of the three remaining sets of three columns.

Now consider row 5. It must also have one $1$ in each of the three as yet undermined sets of three columns. But it must also be orthogonal to row 4. The inner product of two vectors of length $3$, each consisting of one $1$ and two $-1$s, can only be $3$ or $-1$. In the first set of three columns of rows 4 and 5 this inner product equals $3$. The only way to make rows 4 and 5 orthogonal is for the remaining three inner products to equal $-1$. This means that the remaining $1$s in row 5 cannot coincide with $1$s in row 4. To make row 5 lexicographically minimal, the order must be $\begin{bmatrix}-1 & 1 & -1\end{bmatrix}$ in each set of three columns. At this stage we have $$ \left[\begin{array}{ccc|ccc|ccc|ccc} 1 & 1 & 1 & 1 & 1 & 1 & - & - & - & - & - & -\\ 1 & 1 & 1 & - & - & - & 1 & 1 & 1 & - & - & -\\ 1 & 1 & 1 & - & - & - & - & - & - & 1 & 1 & 1\\ 1 & - & - & 1 & - & - & 1 & - & - & 1 & - & -\\ 1 & - & - & - & 1 & - & - & 1 & - & - & 1 & -\\ 1 & - & -\\ - & 1 & -\\ - & 1 & -\\ - & 1 & -\\ - & - & 1\\ - & - & 1\\ - & - & 1 \end{array}\right] $$

At this point it may be helpful to introduce a shorthand for the three possible length-3 vectors: $$ \begin{bmatrix}1 & - & -\end{bmatrix}\rightarrow1,\qquad\begin{bmatrix}- & 1 & -\end{bmatrix}\rightarrow2,\qquad\begin{bmatrix}- & - & 1\end{bmatrix}\rightarrow3. $$ In this notation, rows 4-12 currently contain $$ \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2\\ 1\\ 2\\ 2\\ 2\\ 3\\ 3\\ 3 \end{bmatrix}. $$ Let the elements of this $9\times4$ matrix be $m_{ij}\in\{1,2,3\}$, where $4\le i\le12$ and $1\le j\le4$. In completing row $k$, we must adhere to two rules:

1. for each $i$ ($4\le i\le k-1$), $m_{kj}=m_{ij}$ for exactly one $j\in\{1,2,3,4\}$; this is needed for orthogonality, as the only way for the inner product of two rows to equal $0$ is for one of the three-column sets to have inner product $3$ and the other three to have inner product $-1$;
2. if there is more than one equivalent way to complete a row, we choose the one that is lexicographically least.

These conditions mean that row 6 must be $\begin{bmatrix}1 & 3 & 3 & 3\end{bmatrix}$. If we write row 7 as $\begin{bmatrix}2 & i & j & k\end{bmatrix}$ then, to be orthogonal to rows 4, 5, and 6, $i,\ j,\ k$ must be a permutation of $1,\ 2,\ 3$. But all permutations are equivalent since permutation of $i, j,\ k$—or, more properly, permutation of the corresponding column sets—accompanied by the corresponding permutation of rows 1, 2, 3 leaves the matrix in the standard form above. So we take the lexicographically minimal permutation and let row 7 be $\begin{bmatrix}2 & 1 & 2 & 3\end{bmatrix}$.

To complete rows 8 and 9, we likewise need permutations of $1,\ 2,\ 3$, but to be orthogonal to row 7, these permutations must actually be derangements of $1, 2,\ 3$. They must also be derangements of each other so that rows 8 and 9 are orthogonal. From this we get $$ \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2\\ 1 & 3 & 3 & 3\\ 2 & 1 & 2 & 3\\ 2 & 2 & 3 & 1\\ 2 & 3 & 1 & 2\\ 3\\ 3\\ 3 \end{bmatrix}. $$

It remains to complete rows 10, 11, and 12. Orthogonality with rows 4, 5, and 6 requires that each of these rows be completed with a permutation of $1,\ 2,\ 3$. Orthogonality with rows 7, 8, and 9 requires that the permutation have exactly one element in common position with each of the permutations used in those rows. The permutations used in rows 10, 11, and 12 must also be derangements of each other so that those rows are pairwise mutually orthogonal. There are only three permutations of $1$, $2$, $3$ that haven't yet been used, and they exactly fit the bill. Therefore we get $$ \begin{bmatrix} 1 & 1 & 1 & 1\\ 1 & 2 & 2 & 2\\ 1 & 3 & 3 & 3\\ 2 & 1 & 2 & 3\\ 2 & 2 & 3 & 1\\ 2 & 3 & 1 & 2\\ 3 & 1 & 3 & 2\\ 3 & 2 & 1 & 3\\ 3 & 3 & 2 & 1 \end{bmatrix}. $$ The resulting matrix is $$ \left[\begin{array}{ccc|ccc|ccc|ccc} 1 & 1 & 1 & 1 & 1 & 1 & - & - & - & - & - & -\\ 1 & 1 & 1 & - & - & - & 1 & 1 & 1 & - & - & -\\ 1 & 1 & 1 & - & - & - & - & - & - & 1 & 1 & 1\\ \hline 1 & - & - & 1 & - & - & 1 & - & - & 1 & - & -\\ 1 & - & - & - & 1 & - & - & 1 & - & - & 1 & -\\ 1 & - & - & - & - & 1 & - & - & 1 & - & - & 1\\ \hline - & 1 & - & 1 & - & - & - & 1 & - & - & - & 1\\ - & 1 & - & - & 1 & - & - & - & 1 & 1 & - & -\\ - & 1 & - & - & - & 1 & 1 & - & - & - & 1 & -\\ \hline - & - & 1 & 1 & - & - & - & - & 1 & - & 1 & -\\ - & - & 1 & - & 1 & - & 1 & - & - & - & - & 1\\ - & - & 1 & - & - & 1 & - & 1 & - & 1 & - & - \end{array}\right]. $$ Now negate columns 7-12 and rows 7-12. This amounts to negating the four $3\times3$ blocks in the upper right corner and the four $3\times3$ blocks in the lower left corner. The result is $$ \left[\begin{array}{ccc|ccc|ccc|ccc} 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1\\ 1 & 1 & 1 & - & - & - & - & - & - & 1 & 1 & 1\\ 1 & 1 & 1 & - & - & - & 1 & 1 & 1 & - & - & -\\ \hline 1 & - & - & 1 & - & - & - & 1 & 1 & - & 1 & 1\\ 1 & - & - & - & 1 & - & 1 & - & 1 & 1 & - & 1\\ 1 & - & - & - & - & 1 & 1 & 1 & - & 1 & 1 & -\\ \hline 1 & - & 1 & - & 1 & 1 & - & 1 & - & - & - & 1\\ 1 & - & 1 & 1 & - & 1 & - & - & 1 & 1 & - & -\\ 1 & - & 1 & 1 & 1 & - & 1 & - & - & - & 1 & -\\ \hline 1 & 1 & - & - & 1 & 1 & - & - & 1 & - & 1 & -\\ 1 & 1 & - & 1 & - & 1 & 1 & - & - & - & - & 1\\ 1 & 1 & - & 1 & 1 & - & - & 1 & - & 1 & - & - \end{array}\right]. $$

This construction shows that, up to equivalence, there is a unique solution since at no point were there two or more non-equivalent ways to add the next row.