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 .
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
- , (the length of the second part)
- , (the two vectors are orthogonal)
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 .
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.