**Contents**hide

## 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.