A problem on binary orthogonal matrix

Problem

is a binary square matrix whose elements are chosen from the set . That is . And is an orthogonal matrix, .

Theorem: prove that any sub matrix of , with size , if this sub matrix  contains only (no in it at all), then .

Proof

Consider any sub matrix of of . Let’s focus on the row vectors of . And all these vectors’ column contains only 1.

Let’s eval the Hamming Distance between each pair of these row vectors. Each row vector consists of two parts:

• (this part is the same for all these row vectors).
• the remaining columns(this is the part that will cause Hamming Distance)

Taking any two row vectors, let

• be the number of the columns in the second part that the elements in the two vectors have the same sign
• be the number of the columns in the second part that the elements in the two vectors have the different sign

We have:

• , (the length of the second part)
• , (the two vectors are orthogonal)

So .

Now let’s only consider the vectors contain only the second-part columns. These vectors’ length is . There are such vectors. And the pair-wise Hamming Distance is .

Let’s model this a coding problem and find the relation among codewords number, codewords length and Hamming Distance.

There is a famous theorem Plotkin Bound for the problem:

Pay attention to the symbols and do not mix them up:

• in the above picture means the codeword’s length, inour case
• in the above picture means the minimal Hamming Distance,  in our case
• in the above picture means the the codewords number, in our case

If is even, then , so we can use i) of the theorem. That is, , this is just what we want to prove.

If is odd, then , so we can use ii) of the theorem. That is :

• if , it is obvious that
• if ,

So we prove that .

Plotkin Bound

Please refer wikipedia link for more details: Plotkin Bound. It is quite easy to prove and understand. The core idea is to represent the summation of all pairs’ Hamming Distance in two different ways.