12
$\begingroup$

I am interested in answering the following question:

Question

For a given $n$, does there exist a $2n \times 2n$ matrix with entries in $\{1, 0, -1\}$ having orthogonal rows and columns with exactly $n$ zeroes in each row and column?

Conjectures

  1. For $n=2^k$, $k\ge0$ such a matrix always exists.

  2. For $n=3$ such a matrix does not exist.

  3. For $n=5$ such a matrix exists, for example: $$ \left( \begin{array}{cccccccccc} 1 & 1 & 1 & 1 & 1 & 0 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 0 & -1 & 0 & -1 & -1 & -1 & 0 \\ 1 & 0 & 0 & -1 & 0 & 0 & -1 & 1 & 1 & 0 \\ 0 & -1 & -1 & 1 & 1 & 0 & -1 & 0 & 0 & 0 \\ 1 & 0 & -1 & 0 & 0 & -1 & 1 & 0 & 0 & -1 \\ 1 & -1 & 0 & 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 0 & 0 & -1 & 1 & -1 & 0 & -1 & 0 & 1 \\ 0 & -1 & 1 & 0 & 0 & 0 & 0 & -1 & 1 & -1 \\ 0 & -1 & 1 & 0 & 0 & -1 & 0 & 1 & -1 & 0 \\ 0 & 0 & 0 & -1 & 1 & 1 & 0 & 0 & -1 & -1 \\ \end{array} \right) $$

  4. For $n=7$ such a matrix does not exist.

$\endgroup$
5
  • $\begingroup$ Do you mean "having orthogonal columns and rows" when saying "orthogonal matrix"? $\endgroup$ May 3, 2022 at 19:25
  • $\begingroup$ Yes, let me update the question accordingly to make it clear. $\endgroup$ May 3, 2022 at 19:29
  • 6
    $\begingroup$ Well one observation is that if $A$ satisfies the conditions so does $\left( \begin{array}{cccccccccc} A & -A \\ -A & -A \end{array} \right)$ So starting with say the $2 \times 2$ identity matrix we get ones of size $2^k$ for all $k$. $\endgroup$
    – Nate
    May 3, 2022 at 19:50
  • 3
    $\begingroup$ If $H$ is an $n \times n$ Hadamard matrix, then $\begin{bmatrix} H&0 \\ 0&H \end{bmatrix}$ meets the requirements. As a reminder, the Hadamard conjecture says that there is a Hadamard matrix of size $4k$ for every $k$, and this has been checked for $4k \leq 668$. $\endgroup$ May 3, 2022 at 20:22
  • 1
    $\begingroup$ Generalizing both Nate and my observations: If $H$ is a Hadamard matrix, and $A$ is one of your matrices, then the Kronecker product $H \otimes A$ (see en.wikipedia.org/wiki/Kronecker_product ) is one of your matrices. $\endgroup$ Dec 1, 2022 at 1:48

3 Answers 3

14
$\begingroup$

There is no such matrix if $n\equiv 3\pmod 4$.

Suppose otherwise. Each column represents a vector of length $\sqrt n$. Since those vectors are pairwise orthogonal, their sum is a vector whose scalar square is $2n^2$.

On the other hand, the sum of all columns has odd entries, so their squares are all congruent to $1$ modulo $8$. Hence the sum of those squares is congruent to $2n$ modulo $8$. Hence we should have $2n^2\equiv 2n\pmod 8$, or $8\mid 2n(n-1)$ which does not hold.

$\endgroup$
1
  • $\begingroup$ These matrices are actually a special case of weighing matrices. Weighing matrices $W(n, k)$ are $n \times n$ matrices with entries $\{\pm 1, 0\}$ such that $W^TW = kI_n$, The question is asking about the existence of $W(2n, n)$. So, one alternative proof that there is no such matrix for $n \equiv 3 (\mathrm{mod}\ 4)$ is as follows. Suppose $n \equiv 3 (\mathrm{mod}\ 4)$ and there exists $W(2n, n)$. It is known that if there exists $W(2n, n)$ with $2n \equiv 2(\mathrm{mod}\ 4)$ then $n$ must be a sum of two integer squares. This is a contradiction with $n \equiv 3 (\mathrm{mod}\ 4)$. $\endgroup$ Apr 24, 2023 at 19:36
9
$\begingroup$

Your first conjecture was proven by Nate in the comments.

Your second conjecture is also true - there is no such matrix for $n=3$. If we just look at which entries are nonzero in each row, because any two rows are orthogonal, they must share an even number of nonzero entries, i.e. either share $0$ entries or $2$ entries. Only $3$ other rows can share $2$ nonzero entries with a given row, since otherwise there'd be more than $3$ nonzero entries in a column by the pidgeonhole principle, so $2$ rows must share $0$ nonzero entries, but then they share $3$ entries with each other, contradiction.

$\endgroup$
1
  • 3
    $\begingroup$ You can go even further: The third conjecture is also true ;-) $\endgroup$ May 4, 2022 at 1:40
8
$\begingroup$

$\def\Id{\text{Id}}$A Hadamard matrix is an $n \times n$ matrix with entries in $\{-1, 1 \}$ with $H H^T = H^T H = n \Id$. What you want is a matrix $X$ with entries in $\{-1, 0, 1 \}$ with $XX^T = X^T X = (n/2) \Id$.

I will show that, if there is an $n \times n$ Hadamard matrix $H$, then there is also an $n \times n$ matrix $X$ obeying your condition. The proof is simple: Let $S = \left[ \begin{smallmatrix} 1/2 & 1/2 \\ 1/2 & - 1/2 \\ \end{smallmatrix} \right]$; note that $S S^T = (1/2) \Id_2$. Let $D = \left[ \begin{smallmatrix} S&&& \\ &S&& \\ &&\ddots& \\ &&&S \\ \end{smallmatrix} \right]$ where there are $n/2$ copies of $S$. We take $X=DH$. Since $H$ has entries in $\{ -1, 1 \}$, the matrix $DH$ has entries in $\{ -1, 0, 1 \}$. We have $(DH)(DH)^T = DHH^TD^T = n DD^T = (n/2)\Id_n$ and similarly $(DH)^T (DH) = (n/2) \Id_n$ as desired.

This is useful because Hadamard matrices are extensively studied. Hadamard's conjecture says that there is always a Hadamard matrix of order $4k$ for any $k$. Hadamard matrices are known to exist for $n$ of the form $q+1$ or $2(q+1)$, where $q$ is a prime power which is $3 \bmod 4$ or $1 \bmod 4$ respectively, and in many other cases; see the above cited Wikipedia article.

That's only half of what you want, because your matrices sometimes exist for $n \equiv 2 \bmod 4$, and Hadamard matrices never do, but it seems like progress.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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