Why does the Minus-1 trick to get particular and general solutions work?
Minus-1 trick: A practical trick where the reduced row-echelon form of a system of equations is augmented with -1 rows. It is used to get particular and general solutions.
While it is a handy trick, I was wondering why does it work.
The following is an example of the minus-1 trick from the book Mathematics for Machine Learning Book
2 Answers
$\begingroup$In the example, set the non-pivot variables to $x_2=-\lambda_1$, $x_5=-\lambda_2$ and solve the system for other variables. You will get the exact same result.
The minus-1 trick is just a schematic way to achieve the same with less writing.
Another way to look at this: The columns $1$, $3$ and $4$ of $A$ are the standard basis of the column space. Using these you can uniquely express the remaining two columns:\begin{align*} \color{blue}{\begin{pmatrix} 3\\0\\0\end{pmatrix}} &= 3 \begin{pmatrix}1\\0\\0\end{pmatrix} + 0 \begin{pmatrix}0\\1\\0\end{pmatrix} + 0 \begin{pmatrix}0\\0\\1\end{pmatrix}, \\ \color{blue}{\begin{pmatrix} 3\\9\\-4\end{pmatrix}} &= 3 \begin{pmatrix}1\\0\\0\end{pmatrix} + 9 \begin{pmatrix}0\\1\\0\end{pmatrix} -4 \begin{pmatrix}0\\0\\1\end{pmatrix}. \end{align*}We can rewrite these two equations as\begin{align*} 3 \begin{pmatrix}1\\0\\0\end{pmatrix} \color{blue}{{}- 1 \begin{pmatrix} 3\\0\\0\end{pmatrix}} + 0 \begin{pmatrix}0\\1\\0\end{pmatrix} + 0 \begin{pmatrix}0\\0\\1\end{pmatrix} + \color{red}{0 \begin{pmatrix} 3\\9\\-4\end{pmatrix}} &= \begin{pmatrix}0\\0\\0\end{pmatrix}, \\ 3 \begin{pmatrix}1\\0\\0\end{pmatrix} + \color{red}{0 \begin{pmatrix} 3\\0\\0\end{pmatrix}} + 9 \begin{pmatrix}0\\1\\0\end{pmatrix} - 4 \begin{pmatrix}0\\0\\1\end{pmatrix} \color{blue}{{}- 1 \begin{pmatrix} 3\\9\\-4\end{pmatrix}} &= \begin{pmatrix}0\\0\\0\end{pmatrix}, \end{align*}Hence, we have two (linearly independent) solutions to $Ax=0$ given by$$ \begin{pmatrix} 3\\\color{blue}{-1}\\0\\0\\\color{red}{0} \end{pmatrix}, \begin{pmatrix} 3\\\color{red}{0}\\9\\-4\\\color{blue}{-1} \end{pmatrix}. $$Again, the minus-1 trick is just a schematic way to achieve the same result mechanically.
$\endgroup$ 1 $\begingroup$It can easily be verified that, if:
$$\tilde{A}=\begin{bmatrix}1&3&0&0&3\\0&-1&0&0&0\\0&0&1&0&9\\0&0&0&1&-4\\0&0&0&0&-1\end{bmatrix}$$
then $\tilde{A}$ is an involutory matrix, i.e.:
$$\tilde{A}^{-1}=\tilde{A}$$
We will prove that later. However, let's see how this helps. The equation $Ax=0$ now becomes equivalent to $A\tilde{A}\tilde{A}x=0$, which is equivalent to:
$$\begin{bmatrix}1&0&0&0&0\\0&0&1&0&0\\0&0&0&1&0\end{bmatrix}\tilde{A}x=0$$
(As the rows of $A$ are some of the rows of $\tilde{A}$, then the rows of $A\tilde{A}$ are the corresponding rows of $\tilde{A}\tilde{A}=I$.)
Set $y=\tilde{A}x$, and solve the system:
$$\begin{bmatrix}1&0&0&0&0\\0&0&1&0&0\\0&0&0&1&0\end{bmatrix}y=0$$
It has obvious solutions:
$$y=\lambda_2\begin{bmatrix}0\\1\\0\\0\\0\end{bmatrix}+\lambda_5\begin{bmatrix}0\\0\\0\\0\\1\end{bmatrix}$$
However, then:
$$x=\tilde{A}^{-1}y=\tilde{A}y=\lambda_2\tilde{A}\begin{bmatrix}0\\1\\0\\0\\0\end{bmatrix}+\lambda_5\tilde{A}\begin{bmatrix}0\\0\\0\\0\\1\end{bmatrix}$$
and one can easily see that the two columns $\tilde{A}\begin{bmatrix}0\\1\\0\\0\\0\end{bmatrix}$ and $\tilde{A}\begin{bmatrix}0\\0\\0\\0\\1\end{bmatrix}$ multiplied by $\lambda_2$ and $\lambda_5$ are indeed the $2$nd and $5$th column of $\tilde{A}$.$\quad\blacksquare$
Now, why is $\tilde{A}^{-1}=\tilde{A}$? One can recall the algorithm for finding the inverse matrix for a given matrix, say $\tilde{A}$, via Gaussian elimination:
$$\left[\begin{array}{ccccc|ccccc}1&3&0&0&3&1&0&0&0&0\\0&-1&0&0&0&0&1&0&0&0\\0&0&1&0&9&0&0&1&0&0\\0&0&0&1&-4&0&0&0&1&0\\0&0&0&0&-1&0&0&0&0&1\end{array}\right]$$
Once you apply the following elementary transformations to bring the left-side matrix to $I$:
- Add the second row multiplied by $3$ to the first
- Add the fifth row multiplied by $3,0,9,-4$ to $1$st,$2$nd,$3$rd,$4$th row, respectively
- Multiply the second and fifth row by $-1$
you will indeed get the matrix $I$ on the left side, but notice that you will actually create the very same matrix $\tilde{A}$ on the right side. Thus, $\tilde{A}^{-1}=\tilde{A}$.$\quad\blacksquare$
$\endgroup$
