证明2^n dimensional 哈达玛矩阵的column vectors 是orthonmal?

Question

如题，正在学习哈达玛矩阵，不知如何证明.

如何证明2^n阶哈达玛矩阵的column vectors是orthonmal?

Answer 1

要证明一个矩阵的列向量是正交的，需要证明它们两两之间的内积为0，即它们的点积为0。对于2^n阶哈达玛矩阵的列向量，有一个简单的证明方法。

首先，我们考虑哈达玛矩阵的定义。哈达玛矩阵是一个2^n阶的矩阵，它的每个元素都等于+1或-1。其中，第一行和第一列的元素都是+1，而其他的元素则按照以下规律构造：

• 对于每个行向量和列向量，它们的元素按照二进制数的顺序排列，从0到2^n-1。
• 对于每个元素的位置，如果其对应的行向量和列向量在该位置上的元素值相同，则该元素的值为+1，否则为-1。

例如，对于2阶哈达玛矩阵，其定义如下：

H = [1  1;
     1 -1];

对于4阶哈达玛矩阵，其定义如下：

H = [1  1  1  1;
     1 -1  1 -1;
     1  1 -1 -1;
     1 -1 -1  1];

接下来，我们考虑两个不同的列向量，它们的位置分别为i和j，且i<j。根据哈达玛矩阵的定义，这两个列向量的点积可以表示为：

dot(H(:,i), H(:,j)) = H(1,i)*H(1,j) + H(2,i)*H(2,j) + ... + H(2^n,i)*H(2^n,j)

我们可以将这个点积表示为一个求和式，其中每个元素都是+1或-1。根据求和式的性质，如果其中有两个元素的值相同，那么它们的和为2或-2，否则它们的和为0。因此，如果我们能证明在求和式中，有且仅有一个元素的值为-1，那么我们就证明了这两个列向量的点积为0，即这两个列向量是正交的。

现在，我们考虑在求和式中，有且仅有一个元素的值为-1的情况。根据哈达玛矩阵的定义，对于任意的两个不同的列向量，它们的在某个位置上的元素值不同。因此，在求和式中，如果一个元素的值为-1，那么在另一个列向量中，它的值就为+1。因此，在求和式中，如果有且仅有一个元素的值为-1，那么对应的两个列向量在该位置上的元素值必须分别为+1和-1。

由于哈达玛矩阵的每个列向量的元素值都是+1或-1，因此，在任意的两个列向量中，只有当它们在某个位置上的元素值分别为+1和-1时，对应的元素的值才可能为-1。因此，在求和式中，有且仅有一个元素的值为-1的情况只有一种，即对应的两个列向量在某个位置上的元素值分别为+1和-1。

综上所述，我们证明了对于2^n阶哈达玛矩阵的任意两个不同的列向量，它们的点积为0，即这些列向量是正交的。因此，2^n阶哈达玛矩阵的列向量是正交的。