每日一题[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$中最多可以有多少个元素.


cover

分析与解 (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}\]

此条目发表在每日一题分类目录,贴了, 标签。将固定链接加入收藏夹。

发表评论