几道用线性代数解决的问题

解答：

考虑由全体实系数多项式组成的线性空间ℝ[𝑥]，其一组基底为{1,𝑥,𝑥^(2),⋯}．

若存在满足题意的多项式𝑎(𝑥)，𝑏(𝑥)，𝑐(𝑥)，𝑑(𝑥)．分别令𝑦=−1，0，1，得：

公式：\begin{cases} c(-1)a(x)+d(-1)b(x)=1-x+x^2\\ c(0)a(x)+d(0)b(x)=1\\ c(1)a(x)+d(1)b(x)=1+x+x^2 \end{cases}

即多项式1−𝑥+𝑥^(2)，1，1+𝑥+𝑥^(2)均为𝑎(𝑥)和𝑏(𝑥)的线性组合，然而这三个多项式线性无关，故无法被𝑎(𝑥)，𝑏(𝑥)两个多项式线性表出，矛盾！

因此不存在满足题意的多项式𝑎(𝑥)，𝑏(𝑥)，𝑐(𝑥)，𝑑(𝑥)．

注： 上述证明过程只要求𝑎(𝑥)和𝑏(𝑥)为多项式，𝑐(𝑥)和𝑑(𝑥)可为任意函数．

证明：

即证𝐴的𝑛个列向量线性无关．

假设结论不成立，即存在不全为零的实数𝑐_(1)，𝑐_(2)，⋯，𝑐_(𝑛)，使得对任意𝑖=1，2，⋯，𝑛，都有

公式：\begin{aligned} |a_{ii}|=&\left|\sum_{j\neq i}\frac{c_j}{c_i}a_{ij}\right|\\ \le&\sum_{j\neq i}\frac{|c_j|}{|c_i|}|a_{ij}|\\ \le&\sum_{j\neq i}|a_{ij}|\\ <&|a_{ii}| \end{aligned}

矛盾！于是原结论成立．

注： 这样的矩阵称为对角占优矩阵．

分析： 这里要处理的是mod2的问题，所以我们考虑只有2个元素的数域𝔽_(2)．

证明：

对任意𝑖=1，2，⋯，𝑚，以𝑣_(𝑖)∈𝔽𝑛2表示居民和第𝑖个俱乐部的关系，即𝑣_(𝑖)的第𝑗个元素为1当且仅当第𝑗个居民在俱乐部𝑖中，𝑣_(𝑖)的第𝑗个元素为0当且仅当第𝑗个居民不在俱乐部𝑖中．

于是𝑣_(𝑖)和𝑣_(𝑖)的内积𝑣_(𝑖)⋅𝑣_(𝑖)即为第𝑖个俱乐部的成员数，𝑣_(𝑖)和𝑣_(𝑗)的内积𝑣_(𝑖)⋅𝑣_(𝑗)即为第𝑖个俱乐部和第𝑗个俱乐部的公共成员数．

于是由每个俱乐部有奇数个成员知，对任意𝑖，在𝔽_(2)中，𝑣_(𝑖)⋅𝑣_(𝑖)=1．由任意两个不同俱乐部之间有偶数个公共成员知，对任意𝑖≠𝑗，在𝔽_(2)中，𝑣_(𝑖)⋅𝑣_(𝑗)=0．

下证：𝑣_(1)，𝑣_(2)，⋯，𝑣_(𝑚)线性无关．

若存在𝑐_(1)，𝑐_(2)，⋯，𝑐_(𝑚)∈𝔽_(2)，使得

与𝑣_(𝑖)作内积知：

公式：\begin{aligned} 0=&v_i\cdot(c_1v_1+c_2v_2+\cdots+c_mv_m)\\ =&c_iv_i\cdot v_i+\sum_{j\neq i}c_j v_i\cdot v_j\\ =&c_i \end{aligned}

于是对任意𝑖=1，2，⋯，𝑚，都有𝑐_(𝑖)=0，这就说明了𝑣_(1)，𝑣_(2)，⋯，𝑣_(𝑚)线性无关．

于是𝑣_(1)，𝑣_(2)，⋯，𝑣_(𝑚)为𝑛为线性空间中𝑚个线性无关的向量，故𝑚≤𝑛．

证明：

设{0,1}向量𝑣_(1)，𝑣_(2)，⋯，𝑣_(𝑚)∈ℝ^(𝑛)，满足𝑣_(𝑖)的第𝑗个元素为1当且仅当第𝑗个居民在俱乐部𝑖中，𝑣_(𝑖)的第𝑗个元素为0当且仅当第𝑗个居民不在俱乐部𝑖中．

于是对任意𝑖≠𝑗，都有𝑣_(𝑖)⋅𝑣_(𝑗)=𝑘．（这就是本题不再在𝔽_(2)中考虑的原因）

下证：𝑣_(1)，𝑣_(2)，⋯，𝑣_(𝑚)线性无关．

否则，若存在不全为零的𝑐_(1)，𝑐_(2)，⋯，𝑐_(𝑚)∈ℝ，使得

则

公式：\begin{aligned} 0=&(c_1v_1+c_2v_2+\cdots+c_mv_m)^2\\ =&\sum_{i=1}^mc_i^2v_i^2+2\sum_{1\le i< j\le m}c_ic_jv_i\cdot v_j\\ =&\sum_{i=1}^mc_i^2|v_i|^2+2k\sum_{1\le i< j\le m}c_ic_j\\ =&\sum_{i=1}^mc_i^2(|v_i|^2-k)+\sum_{i=1}^m\sum_{j=1}^mc_ic_j\\ =&\sum_{i=1}^mc_i^2(|v_i|^2-k)+\left(\sum_{i=1}^mc_i\right)^2 \end{aligned}

由于任意两个不同俱乐部之间恰有𝑘个公共成员，每个俱乐部均至少有𝑘个成员，即对任意𝑖，都有|𝑣_(𝑖)|^(2)≥𝑘．

于是公式：\sum\limits_{i=1}^mc_i^2(|v_i|^2-k)+\left(\sum\limits_{i=1}^mc_i\right)^2非负，即上面的不等式等号恰好成立．

由于𝑐_(1)，𝑐_(2)，⋯，𝑐_(𝑚)不全为零，且𝑐2𝑖≥0，故存在某个𝑖，使得|𝑣_(𝑖)|^(2)−𝑘=0，即第𝑖个俱乐部恰有𝑘个成员．因此其余俱乐部和第𝑖个俱乐部的公共成员恰为第𝑖个俱乐部中的𝑘个成员，并且两两之间不再有其它公共成员．

于是剩余𝑛−𝑘个居民至多属于一个俱乐部，因此至多还有𝑛−𝑘个俱乐部．

俱乐部总数𝑚≤𝑛−𝑘+1≤𝑛．