# Linear Vector Combination Problem

Linear Vector Combination Problem，即线性向量组合问题。写这个其实是由前一篇 post 而来（从百鸡问题到数学思维）。

V=\left[
\begin{array}
\vec{v_1}\\
\vec{v_2}\\
\vdots\\
\vec{v_n}
\end{array}
\right]
\tag{1}

\vec{v_i}=\left(
\begin{array}{}
p_1, p_2, \cdots, p_m
\end{array}
\right)
\tag{2}

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}

$$C=\left[\begin{array}{}c_1 & c_2 & \cdots & c_n\end{array}\right]$$

CV=G
\tag{4}

\begin{aligned}
CV&=G\\
CVV^{-1}&=GV^{-1}\\
C&=GV^{-1}
\end{aligned}
\tag{5}

V'=\left[
\begin{array}{}
\vec{v_1}\\
\vec{v_2}\\
\vdots\\
\vec{v}_{n-m}
\end{array}
\right]
\tag{6}

V=\left[
\begin{array}{}
\vec{v}_{n-m+1}\\
\vec{v}_{n-m+2}\\
\vdots\\
\vec{v_n}
\end{array}
\right]
\tag{7}

C'=\left[
\begin{array}{}
c_1 & c_2 & \cdots & c_{n-m}
\end{array}
\right]
\tag{8}

$$C=\left[ \begin{array}{} c_{n-m+1} & c_{n-m+2} & \cdots & c_n \end{array} \right] \tag{9}$$

\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}

（当然，这里我们移动的项不同，但从本质上来说是等价的）

\label{spend-amount-variation}
\left\{
\begin{aligned}
5a+3b&=n-\frac{c}{3}\\
a+b&=n-c
\end{aligned}
\right.

\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}

\begin{aligned} CV&=G-V'C'\\ CVV^{-1}&=(G-V'C')V^{-1}\\ C&=(G-V'C')V^{-1} \end{aligned} \tag{12}

\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}

\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}

\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}

\left\{
\begin{aligned}
c_2 &= 25 - \frac{7}{4}c_1\\
c_3 &= 25 + \frac{1}{4}c_1
\end{aligned}
\right.

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)