Lets say I have a vector $v$ and $n$ vectors $u_1,\; ... \;, u_n$
Is there a fast way to know if there are more than 1 or just 1 possibility to express $v$ as combination of $u$'s ?
The information I can use is:
- I know if $u$'s can combinate to create $v$ (that means I know if $v$ can be created with $u$'s).
- I know a vector $c$ of coeficients such that $|u_1\; ... \; u_n| *c = v$
With this information, how can I discover if there are more than one vector $w$ such that $|u_1\; ... \; u_n| *w = v$ ?
PS: $|u_1\; ... \; u_n| $ means a matrix with the vectors written vertically inside it.
$u_1\alpha_1 + u_2\alpha_2 + \dots + u_n\alpha_n = v$
iff
$\begin{bmatrix}|&|&|&&|\\ u_1&u_2&u_3&\dots&u_n\\ |&|&|&&|\end{bmatrix}\begin{bmatrix}\alpha_1\\\alpha_2\\\vdots\\\alpha_n\end{bmatrix} = \begin{bmatrix}|\\v\\|\end{bmatrix}$
Solve the system by setting up the associated augmented matrix: $\left[\begin{array}{cccc|c} |&|&&|&|\\ u_1&u_2&\dots&u_n&v\\ |&|&&|&|\end{array}\right]$
Row reduce and then reinterpret as a system of equations.
A row of $[0,0,\dots,0~|~1]$ will imply no solutions exist as this corresponds to the equation $0\alpha_1+0\alpha_2+\dots+0\alpha_n=1$ which is always false.
Assuming no such rows exist, a column without a leading one in the reduced row echelon form implies that infinitely many solutions exist.
If all columns have a leading one and no row of zeroes followed by a one exist, then exactly one solution exists.
E.g. $u_1 = \begin{bmatrix} 1\\0\end{bmatrix}, u_2=\begin{bmatrix}1\\1\end{bmatrix}, u_3=\begin{bmatrix}0\\1\end{bmatrix}, v=\begin{bmatrix}2\\1\end{bmatrix}$
Our augmented matrix: $\left[\begin{array}{ccc|c} 1&1&0&2\\0&1&1&1\end{array}\right]$
Row reducing: $\begin{array}{c}\color{red}{\rightarrow}\\\color{red}{\rightarrow}\end{array}\left[\begin{array}{ccc|c}\color{red}{1}&0&-1&1\\0&\color{red}{1}&1&1\end{array}\right]$
We see the third column does not have any leading ones (by this I mean a pivot point, a furthest left nonzero entry in a row). This implies that infinitely many solutions exist. Interpreting the augmented matrix above as a system of equations:
$\begin{cases}\alpha_1-\alpha_3=1\\ \alpha_2+\alpha_3=1\end{cases}$
Letting $\alpha_3$ be any real number $t$, we have $\alpha_1 = 1+t$ and $\alpha_2=1-t$. That is to say:
$(1+t)\begin{bmatrix}1\\0\end{bmatrix}+(1-t)\begin{bmatrix}1\\1\end{bmatrix}+t\begin{bmatrix}0\\1\end{bmatrix}=\begin{bmatrix}2\\1\end{bmatrix}$ for any choice of $t\in\Bbb R$
Additional example:
$u_1=\begin{bmatrix}1\\0\\0\end{bmatrix}, u_2=\begin{bmatrix} 2\\0\\0\end{bmatrix}, u_3 = \begin{bmatrix}1\\1\\0\end{bmatrix}, u_4=\begin{bmatrix}1\\2\\0\end{bmatrix}, v=\begin{bmatrix}1\\1\\1\end{bmatrix}$
Set up the augmented matrix:
$\left[\begin{array}{cccc|c} 1&2&1&1&1\\0&0&1&2&1\\0&0&0&0&1\end{array}\right]$
Row reducing:
$\begin{array}{c}\color{red}{\rightarrow}\\\color{red}{\rightarrow}\\\color{red}{\rightarrow}\end{array}\left[\begin{array}{cccc|c} \color{red}1&2&0&-1&0\\0&0&\color{red}1&2&1\\0&0&0&0&\color{red}1\end{array}\right]$
Here, even though we have columns without leading ones (the second and fourth), we have a row $[0,0,0,0~ |~ 1]$, implying that no combination of those four vectors will result in $v$ (this should be clear without much work since any combination of $u_i$ will have a third component as zero, whereas $v$ has nonzero third component)