Linear Vector Combination Problem，即线性向量组合问题。写这个其实是由前一篇 post 而来（从百鸡问题到数学思维）。
这篇 post 由以下几个部分构成
这里再将题目重复一下，“鸡翁一值钱五，鸡母一值钱三，鸡雏三值钱一。百钱买百鸡，问鸡翁、母、雏各几何？”。
符号定义
那么我们令
\begin{equation}
V=\left[
\begin{array}
\vec{v_1}\\
\vec{v_2}\\
\vdots\\
\vec{v_n}
\end{array}
\right]
\tag{1}
\end{equation}
其中
\begin{equation}
\vec{v_i}=\left(
\begin{array}{}
p_1, p_2, \cdots, p_m
\end{array}
\right)
\tag{2}
\end{equation}
因此，\(V\)是一个\(n\times m\)的矩阵，其中每一行\(v_i\)都是一个\(m\)维向量，\(v_i\)里每一个分量\(p_j\)是第\(j\)个property。
例如在这道题里，我们有
\begin{equation}
V=\left[
\begin{array}{}
\vec{v_1}\\
\vec{v_2}\\
\vec{v_3}
\end{array}
\right]
=\left[
\begin{array}{Chicken}
5 & 1\\
3 & 1\\
1 & 3\\
\end{array}
\right]
\tag{3}
\end{equation}
对于\(\vec{v_1}=\left(5,1\right)\)来说，第一个分量\(p_1=5\)是价格这一项属性，第二个分量\(p_2=1\)是只数这一属性。
那么在具体的百元百鸡问题中，我们的目标向量是\(\vec{G}=\left(100,100\right)\)，并且有一组常数组成的\(1\times n\)的矩阵\(C\)作为各\(v_i\)的系数
$$C=\left[\begin{array}{}c_1 & c_2 & \cdots & c_n\end{array}\right]$$
使得
\begin{equation}
CV=G
\tag{4}
\end{equation}
矩阵求法
在这个矩阵方程中，\(C\)是我们需要求的，\(V,G\)均是已知的量。因为这是一个很简单的矩阵方程，自然会想到像这样求出\(C\)
\begin{equation}
\begin{aligned}
CV&=G\\
CVV^{-1}&=GV^{-1}\\
C&=GV^{-1}
\end{aligned}
\tag{5}
\end{equation}
不过我们并不能确定矩阵\(V\)是否是方阵，所以需要先将矩阵\(V\)变换为方阵。再提一下，\(C\)是\(1\times n\)的，\(V\)是\(n\times m\)，\(G\)是\(1\times m\)
这里假设有\(n\ge m\)，于是给出如下解决办法
先从\(V\)中提出前\(n-m\)行，组成新的\((n-m)\times m\)矩阵
\begin{equation}
V'=\left[
\begin{array}{}
\vec{v_1}\\
\vec{v_2}\\
\vdots\\
\vec{v}_{n-m}
\end{array}
\right]
\tag{6}
\end{equation}
而原来的\(V\)则变成了一个\(m\times m\)的矩阵
\begin{equation}
V=\left[
\begin{array}{}
\vec{v}_{n-m+1}\\
\vec{v}_{n-m+2}\\
\vdots\\
\vec{v_n}
\end{array}
\right]
\tag{7}
\end{equation}
接下来，对矩阵\(C\)也做类似的事
\begin{equation}
C'=\left[
\begin{array}{}
c_1 & c_2 & \cdots & c_{n-m}
\end{array}
\right]
\tag{8}
\end{equation}
\begin{equation}
C=\left[
\begin{array}{}
c_{n-m+1} & c_{n-m+2} & \cdots & c_n
\end{array}
\right]
\tag{9}
\end{equation}
如此一来，\(C\)是\(1\times m\)的，而\(C'\)是\(1\times (n-m)\)
那么这样变换是为了什么呢？为了说明原因，我们暂时回到具体的问题上来，在百元百鸡问题中，
\begin{equation}
\begin{aligned}
&CV=G\\
&c_1(5,1)+c_2(3,1)+c_3(1,3)=G\\
&c_1(5,1)+c_2(3,1)+c_3(1,3)=(100,100)\\
&c_2(3,1)+c_3(1,3)=(100,100)-c_1(5,1)
\end{aligned}
\tag{10}
\end{equation}
这里等价于我们之前用一般方法化简时的一组等式
（当然，这里我们移动的项不同，但从本质上来说是等价的）
\begin{equation}
\label{spend-amount-variation}
\left\{
\begin{aligned}
5a+3b&=n-\frac{c}{3}\\
a+b&=n-c
\end{aligned}
\right.
\end{equation}
在有了上面的等式之后，我们会人工进行消去变量的操作，然后得到\(a,b\)关于\(c\)的表达式
在这里，或许已经能猜出来了，根据上面提到的的解决办法，我们有
\begin{equation}
\begin{aligned}
&\left\{\begin{aligned}
C &= \left[\begin{array}{}c_2 & c_3\end{array}\right]\\
C'&= \left[\begin{array}{}c_1\end{array}\right]\\
\end{aligned}\right.\\\\
&\left\{\begin{aligned}
V &= \left[\begin{array}{}3&1\\1&3\end{array}\right]\\
V'&= \left[\begin{array}{}5&1\end{array}\right]
\end{aligned}\right.
\end{aligned}
\tag{11}
\end{equation}
那么可以观察到，\(V'C'\)正好就是\(c_1(5,1)\)，正好是和\(G=\begin{bmatrix}100 & 100\end{bmatrix}\)相同，是一个\(1\times 2\)的矩阵。那么我们可以对它们进行操作，并得到
\begin{equation}
\begin{aligned}
CV&=G-V'C'\\
CVV^{-1}&=(G-V'C')V^{-1}\\
C&=(G-V'C')V^{-1}
\end{aligned}
\tag{12}
\end{equation}
进行到这一步之后，我们一下就得到了\(c_2,c_3\)与\(c_1\)的关系。
放入题中则是
\begin{equation}
\begin{aligned}
CV&=G-V'C'\\
\begin{bmatrix}
c_2 & c_3
\end{bmatrix}
\begin{bmatrix}
3 & 1 \\
1 & 3
\end{bmatrix}&=
\begin{bmatrix}
100 - 5c_1 & 100 - c_1
\end{bmatrix}
\end{aligned}
\tag{13}
\end{equation}
接下来求出\(V^{-1}\)
\begin{equation}
\begin{aligned}
\begin{bmatrix}
3 & 1 \\
1 & 3
\end{bmatrix}^{-1} =
\frac{1}{8}
\begin{bmatrix}
3 & -1 \\
-1 & 3
\end{bmatrix}
\end{aligned}
\tag{14}
\end{equation}
同时右乘
\begin{equation}
\begin{aligned}
C&=(G-V'C')V^{-1}\\
\begin{bmatrix}
c_2 & c_3
\end{bmatrix}&=
\frac{1}{8}
\begin{bmatrix}
100 - 5c_1 & 100 - c_1
\end{bmatrix}
\begin{bmatrix}
3 & -1 \\
-1 & 3
\end{bmatrix}\\
&=\frac{1}{8}
\begin{bmatrix}
200 - 14c_1 & 200 + 2c_1
\end{bmatrix}\\
&=
\begin{bmatrix}
25 - \frac{7}{4}c_1 & 25 + \frac{1}{4}c_1
\end{bmatrix}
\end{aligned}
\tag{15}
\end{equation}
即
\begin{equation}
\left\{
\begin{aligned}
c_2 &= 25 - \frac{7}{4}c_1\\
c_3 &= 25 + \frac{1}{4}c_1
\end{aligned}
\right.
\end{equation}
再之后，根据限制条件即可算出来。
代码实现
from sympy.matrices import * n = 3 m = 2 V = Matrix(n, m, [5, 1, 3, 1, 1, 3]) G = Matrix(1, m, [100, 100]) def vcp(V, G, n, m): """ Linear Vector Combination Problem V Vector Matrix, \(v_i=(p_1,p_2,\cdots,p_m)\) G Goal, \(G=\left[g_1,g_2,\cdots,g_m\right]\) n Number of vectors in \(V\) m \(v_i\) is \(m\)-dim """ free_var = n - m if free_var > 0: V_ = Matrix(free_var, m, V[0:free_var * m]) V = Matrix(m, m, V[free_var * m:]) V_inv = V.inv() constants = G * V_inv coeffient = (-V_ * V_inv).transpose() non_free_var = len(constants) denoms = [[]] for i in range(non_free_var): print("x%d = %d" % (i + free_var, constants[i]), end='') for f in range(free_var): sign = '' fp = i*free_var+f if coeffient[fp] > 0: sign = '+ ' print(" %s%sx%d" % (sign, coeffient[fp], f), end='') if len(denoms) <= f: denoms.append([]) denoms[f].append(coeffient[fp].as_numer_denom()[1]) print('') vcp(V, G, n, m)
总结
那么用矩阵来做的意义是什么？比起人工计算变量间的关系，现在可以用计算机来做，特别是当\(n-m>1\)的时候，使用这种方法会减少不少人力。
另外这里的矩阵方法也回答了在一般解法中，“消去变量的意义是什么”这一问题，在线性代数中，如果我们有\(n\)个变量，但是却只有\(m\)个等式，这意味着我们有\(n-m\)个自由变量。因此，如果想要用矩阵求解，那么\(V\)必须是方阵，只有方阵才是可逆的，故选出\(n-m\)个自由变量，使得\(V\)是方阵。在经过矩阵运算之后，得到\(m\)个非自由变量与\(n-m\)个自由变量间的关系。