每日一题[907]正交向量

已知集合$A_n=\left\{\left(x_1,x_2,\cdots,x_n\right)\left|\ x_i\in\{-1,1\}\ (i=1,2,\cdots,n)\right.\right\}$，${\overrightarrow x},{\overrightarrow y}\in A_n$，${\overrightarrow x}=\left(x_1,x_2,\cdots,x_n\right)$，${\overrightarrow y}=\left(y_1,y_2,\cdots,y_n\right)$，其中$x_i,y_i\in\{-1,1\}\ (i=1,2,\cdots,n)$．定义${\overrightarrow x}\cdot {\overrightarrow y}=x_1y_1+x_2y_2+\cdots+x_ny_n$．若${\overrightarrow x}\cdot{\overrightarrow y}=0$，则称${\overrightarrow x}$与${\overrightarrow y}$正交．
(1) 若${\overrightarrow x}=(1,1,1,1)$，写出$A_4$中与${\overrightarrow x}$正交的所有元素；
(2) 令$B=\left\{{\overrightarrow x}\cdot{\overrightarrow y}\left|\ {\overrightarrow x},{\overrightarrow y}\in A_n\right.\right\}$．若$m\in B$，证明：$m+n$为偶数；
(3) 若$A\subseteq A_n$，且$A$中任意两个元素均正交，分别求出$n=8,14$时，$A$中最多可以有多少个元素．

---

分析与解　(1) $A_4$中与${\overrightarrow x}$正交的所有元素为

$$(1,1,-1,-1),\ (-1,-1,1,1),\ (1,-1,1,-1),\ (-1,1,-1,1),\ (1,-1,-1,1),\ (-1,1,1,-1).$$

(2) 任取${\overrightarrow x},{\overrightarrow y}\in A_n$，设${\overrightarrow x}$与${\overrightarrow y}$有$t$个分量完全相同，则${\overrightarrow x}$与${\overrightarrow y}$有$n-t$个分量完全相反，其中$t\in\mathbb{N}$．故

$$m+n=t-(n-t)+n=2t$$ 为偶数．

(3) 当$n=8$时，设$A_8$的子集$A$中有$k$个两两正交的元素

$$\begin{split} {\overrightarrow x}_1&=\left(x_{11},x_{12},\cdots,x_{18}\right),\\{\overrightarrow x}_2&=\left(x_{21},x_{22},\cdots,x_{28}\right),\\&\vdots\\{\overrightarrow x}_k&=\left(x_{k1},x_{k2},\cdots,x_{k8}\right),\end{split}$$
将这$k$个元素的分量排成一个$k$行$8$列的数表 $$\begin{pmatrix}x_{11}&x_{12}&\cdots&x_{18}\\x_{21}&x_{22}&\cdots&x_{28}\\\vdots&\vdots&&\vdots\\x_{k1}&x_{k2}&\cdots&x_{k8}\end{pmatrix}.$$

我们先给出$8$个元素两两正交的构造：

$$\begin{split}{\overrightarrow x}_1&=(+1,+1,+1,+1,+1,+1,+1,+1),\\{\overrightarrow x}_2&=(+1,-1,+1,-1,+1,-1,+1,-1),\\ {\overrightarrow x}_3&=(+1,+1,-1,-1,+1,+1,-1,-1),\\{\overrightarrow x}_4&=(+1,-1,-1,+1,+1,-1,-1,+1),\\{\overrightarrow x}_5&=(+1,+1,+1,+1,-1,-1,-1,-1),\\ {\overrightarrow x}_6&=(+1,-1,+1,-1,-1,+1,-1,+1),\\{\overrightarrow x}_7&=(+1,+1,-1,-1,-1,-1,+1,+1),\\{\overrightarrow x}_8&=(+1,-1,-1,+1,-1,+1,+1,-1).\end{split}$$

下面我们来证明$k \leqslant 8$．若$k\geqslant 9$，那么将这些向量排成一个矩阵

$$\begin{pmatrix}x_{11} & x_{12} & x_{13} & x_{14} & x_{15} & x_{16} & x_{17} & x_{18} \\x_{21} & x_{22} & x_{23} & x_{24} & x_{25} & x_{26} & x_{27} & x_{28} \\\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\x_{81} & x_{82} & x_{83} & x_{84} & x_{85} & x_{86} & x_{87} & x_{88} \\\cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots & \cdots \\x_{k1} & x_{k2} & x_{k3} & x_{k4} & x_{k5} & x_{k6} & x_{k7} & x_{k8} \\\end{pmatrix}$$ 从第$1$列中选择一个不为$0$的数，将其所在的行与第$1$行交换，并乘以$1$或$-1$使其第$1$位是$1$，然后利用第$1$行与其他行依次相加或相减，使其他行的第$1$位均变为$0$；然后在得到的矩阵中从第$2$列中选择一个不为$0$的数，将其所在的行与第$2$行交换，并乘以$1$或$-1$使其第$2$位是$1$，然后利用第$2$行与其他行依次相加或相减，使其他行的第$2$位均变为$0$；依次进行下去(如果某一列全是$0$，就跳过该列去处理下一列)，每次操作都让对应的列中只出现一个$1$，由于该矩阵只有$8$列，因此至多进行$8$次操作，就可以使得从第$9$行开始的向量为零向量．这样我们可以得到下面的结论，在$k$个向量中，必然存在 $${\overrightarrow x_9}=\lambda_1{\overrightarrow x_1}+\lambda_2{\overrightarrow x_2}\cdots +\lambda_8{\overrightarrow x_8},$$ 其中$\lambda_1,\lambda_2,\cdots,\lambda_8$均为实数．于是就有 $${\overrightarrow x_9}\cdot {\overrightarrow x_9}=\left(\lambda_1{\overrightarrow x_1}+\lambda_2{\overrightarrow x_2}\cdots +\lambda_8{\overrightarrow x_8}\right)\cdot {\overrightarrow x_9}=0,$$ 矛盾．这样就证明了$k\leqslant 8$．

综上所述，当$n=8$时，$A_8$的子集$A$中最多有$8$个两两正交的元素．

当$n=14$时，设$A_{14}$的子集$A$中有$k$个两两正交的元素．

一方面，取

$$\begin{split}{\overrightarrow x}_1&=(+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1),\\{\overrightarrow x}_2&=(+1,+1,+1,+1,+1,+1,+1,-1,-1,-1,-1,-1,-1,-1),\end{split}$$ 则${\overrightarrow x}_1$与${\overrightarrow x}_2$正交．

另一方面，若$k \geqslant 3$，考虑一般的情形，设${\overrightarrow x}_1$与${\overrightarrow x}_2$相比较，有$a$个对应分量二者都取$+1$；有$b$个对应分量二者都取$-1$；有$c$个对应分量${\overrightarrow x}_1$取$+1$，${\overrightarrow x}_2$取$-1$；有$d$个对应分量${\overrightarrow x}_1$取$-1$，${\overrightarrow x}_2$取$+1$，则

$$a+b=c+d=7,$$ 故${\overrightarrow x}_1$有$a+c$个分量取$+1$，${\overrightarrow x}_2$有$a+d$个分量取$+1$，因为 $$(a+c)+(a+d)=2a+7$$ 是奇数，所以${\overrightarrow x}_1$与${\overrightarrow x}_2$中取$+1$的分量个数一奇一偶．此时再考虑${\overrightarrow x}_3$中取$+1$的分量个数，矛盾．

综上所述，当$n=14$时，$A_{14}$的子集$A$中最多有$2$个两两正交的元素．

注一　第(2)小题直观上只需注意到$m$与$n$的奇偶性相同即可．

注二　利用

$$\begin{matrix} A& A\\ A &\overline A\\\end{matrix}$$ 可以将$n$个向量的构造变成$2n$个向量的构造，再考虑到$n$维欧氏空间中两两正交的向量最多有$n$个，所以我们证明了$A_{2^k}$中最多有$2^k$个两两正交的向量，其中$k\in \mathbb{N}^{*}$．

注三　若$n$为奇数，易证$A_{n}$中不存在正交的向量；若$n=4k+2\ \left(k\in \mathbb{N}\right)$，易证$A_n$中最多有$2$个彼此正交的向量．

注四　当$n=4k\ \left(k\in \mathbb{N}^{*}\right)$时，$A_n$中最多有$n$个两两正交的向量，这个问题即阿达玛猜想．

注五　当$n=12$时，$12$个两两正交的向量可以如下构造：

$$\begin{split}{\overrightarrow x}_1&=(+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1),\\{\overrightarrow x}_2&=(+1,+1,+1,+1,+1,+1,-1,-1,-1,-1,-1,-1),\\{\overrightarrow x}_3&=(+1,+1,+1,-1,-1,-1,+1,+1,+1,-1,-1,-1),\\{\overrightarrow x}_4&=(+1,+1,-1,-1,-1,+1,-1,-1,+1,+1,+1,-1),\\{\overrightarrow x}_5&=(+1,+1,-1,-1,+1,-1,-1,+1,-1,+1,-1,+1),\\{\overrightarrow x}_6&=(+1,+1,-1,+1,-1,-1,+1,-1,-1,-1,+1,+1),\\{\overrightarrow x}_7&=(+1,-1,+1,-1,-1,+1,-1,+1,-1,-1,+1,+1),\\{\overrightarrow x}_8&=(+1,-1,+1,-1,+1,-1,+1,-1,-1,+1,+1,-1),\\{\overrightarrow x}_9&=(+1,-1,+1,+1,-1,-1,-1,-1,+1,+1,-1,+1),\\{\overrightarrow x}_{10}&=(+1,-1,-1,+1,+1,-1,-1,+1,+1,-1,+1,-1),\\{\overrightarrow x}_{11}&=(+1,-1,-1,+1,-1,+1,+1,+1,-1,+1,-1,-1),\\{\overrightarrow x}_{12}&=(+1,-1,-1,-1,+1,+1,+1,-1,+1,-1,-1,+1)\end{split}$$ 两两正交．

注六　当$n=20$时，$20$个两两正交的向量可以如下构造：

$$\begin{split}{\overrightarrow x}_1&=(+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1,+1),\\{\overrightarrow x}_2&=(-1,+1,+1,-1,-1,-1,+1,+1,+1,-1,-1,+1,+1,+1,-1,-1,+1,+1,-1,-1),\\{\overrightarrow x}_3&=(+1,+1,-1,-1,-1,+1,+1,+1,+1,+1,-1,-1,-1,+1,+1,-1,-1,-1,+1,-1),\\{\overrightarrow x}_4&=(-1,+1,+1,+1,-1,-1,-1,-1,+1,+1,-1,-1,+1,-1,+1,+1,-1,+1,+1,-1),\\{\overrightarrow x}_5&=(+1,-1,+1,-1,+1,-1,-1,+1,+1,-1,-1,+1,-1,-1,+1,-1,-1,+1,+1,+1),\\{\overrightarrow x}_6&=(+1,-1,+1,-1,-1,+1,-1,-1,+1,-1,+1,+1,+1,+1,+1,+1,-1,-1,-1,-1),\\{\overrightarrow x}_7&=(+1,+1,-1,+1,-1,-1,-1,-1,+1,-1,-1,+1,-1,+1,-1,+1,+1,-1,+1,+1),\\{\overrightarrow x}_8&=(+1,-1,+1,+1,-1,+1,-1,+1,+1,+1,-1,-1,+1,-1,-1,-1,+1,-1,-1,+1),\\{\overrightarrow x}_9&=(+1,-1,-1,-1,+1,+1,+1,-1,+1,-1,-1,-1,+1,-1,-1,+1,+1,+1,+1,-1),\\{\overrightarrow x}_{10}&=(+1,+1,+1,+1,+1,+1,-1,+1,-1,-1,-1,-1,-1,+1,-1,+1,-1,+1,-1,-1),\\{\overrightarrow x}_{11}&=(+1,+1,+1,-1,-1,+1,-1,-1,-1,+1,+1,+1,-1,-1,-1,-1,+1,+1,+1,-1),\\{\overrightarrow x}_{12}&=(+1,+1,-1,-1,+1,-1,-1,-1,+1,+1,+1,-1,+1,+1,-1,-1,-1,+1,-1,+1),\\{\overrightarrow x}_{13}&=(-1,+1,+1,-1,+1,+1,-1,-1,-1,-1,-1,-1,+1,+1,+1,-1,+1,-1,+1,+1),\\{\overrightarrow x}_{14}&=(-1,-1,+1,-1,+1,-1,-1,+1,+1,+1,+1,-1,-1,+1,-1,+1,+1,-1,+1,-1),\\{\overrightarrow x}_{15}&=(-1,-1,-1,-1,-1,+1,-1,+1,-1,+1,-1,+1,+1,+1,-1,+1,-1,+1,+1,+1),\\{\overrightarrow x}_{16}&=(-1,-1,-1,+1,+1,+1,-1,-1,+1,+1,-1,+1,-1,+1,+1,-1,+1,+1,-1,-1),\\{\overrightarrow x}_{17}&=(+1,-1,+1,-1,-1,-1,+1,-1,-1,+1,-1,-1,-1,+1,+1,+1,+1,+1,-1,+1),\\{\overrightarrow x}_{18}&=(+1,+1,-1,-1,+1,-1,-1,+1,-1,+1,-1,+1,+1,-1,+1,+1,+1,-1,-1,-1),\\{\overrightarrow x}_{19}&=(+1,-1,-1,+1,-1,-1,-1,+1,-1,-1,+1,-1,+1,+1,+1,-1,+1,+1,+1,-1),\\{\overrightarrow x}_{20}&=(-1,+1,-1,-1,-1,+1,-1,+1,+1,-1,+1,-1,-1,-1,+1,+1,+1,+1,-1,+1).\end{split}$$