Given an underdetermined system of linear equations like
$$
a X = b \tag{1}
$$
with $a \in \mathbb{R}^{1 \times n}$, $X \in \mathbb{R}^{n \times n}$ and $b \in \mathbb{R}^{1 \times n}$ where $a$ and $b$ are given and $X$ is the matrix of unknowns. For $n > 1$, the system is clearly underdetermined, since only $n$ equations exist for $n^2$ unknowns. So, either none or infinitely many solutions exist.
Of course, a straightforward way to find some solution is to use the Moore-Penrose pseudo inverse like $X = a^{\dagger} b$.
However, I am only interested in "invertible solutions". That is a solution to $(1)$ such that $X^{-1}$ exists. For my problem, I know that such a solution always exists, however I also want to explicitly compute it.
I know that I can add some multiple of the nullspace of $a$ to the solution to get a new solution. However, how can I select this multiple such that the solution is guaranteed to be invertible?
Currently I add a random multiple of the nullspace in a loop until the solution is invertible. But that is of course not a nice way to do this.
Question: Is there a general way to find "invertible solutions" to $(1)$?
Example: Take as an example
$$
\underbrace{\begin{bmatrix}
1 & 2 & 0
\end{bmatrix}}_{a} X = \underbrace{\begin{bmatrix}
5 & 0 & 0
\end{bmatrix}}_{b}
$$
Now one possible solution is given by the Moore-Penrose pseudo inverse:
$$
X_1 = a^\dagger b = \begin{bmatrix}
1 & 0 & 0 \\
2 & 0 & 0 \\
0 & 0 & 0
\end{bmatrix}
$$
So we have $a X_1 = b$ but unfortunatly $X_1^{-1}$ does not exist. If we use however instead
$$
X_2 = \begin{bmatrix}
1 & 1 & 0 \\
2 & -1/2 & 0 \\
0 & 0 & 1
\end{bmatrix}
$$
we have again $a X_2 = b$ as required but this time $X_2^{-1}$ does exist. But how to find such a solution in general?
Best Answer
I would look at this not as a system of equations but rather a unknown linear map with transformation matrix $X$ such that $X^Ta^T=b^T$.
First we construct a basis of the domain $B_1=\{u_1,u_2,\ldots,u_{n-1},a^T\}$ and the image $B_1=\{v_1,v_2,\ldots,v_{n-1},b^T\}$. It doesnt matter how it looks apart from $a^T$ and $b^T$ being basis vectors. (Obviously we need $a\neq0$ and $b\neq0$, see remark below)
Then we can simply calculate the transformation matrix by the standard procedure of elementary column operations to obtain the identity matrix.
$$ \begin{bmatrix} u_1 & u_2 & \ldots u_{n-1} & a^T \\ \hline v_1 & v_2 & \ldots v_{n-1} & b^T \end{bmatrix}\to \begin{bmatrix} I_n\\\hline X^T \end{bmatrix} $$
For your special example this would read: $$ \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 2 \\ 1 & 0 & 0 \\ \hline 0 & 0 & 5 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \end{bmatrix}\to \begin{bmatrix} 0 & 0 & 1 \\ 0 & 1 & 0 \\ 1 & 0 & 0 \\ \hline 0 & 0 & 5 \\ 0 & 1 & -2 \\ 1 & 0 & 0 \\ \end{bmatrix}\to \begin{bmatrix} 1 & 0 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \\ \hline 5 & 0 & 0 \\ -2 & 1 & 0 \\ 0 & 0 & 1 \\ \end{bmatrix} $$
which yields $$X=\begin{bmatrix} 5 & -2 & 0 \\ 0 & 1 & 0 \\ 0 & 0 & 1 \end{bmatrix}$$
Remark 1: Obviously you will get a different result for another choice of your basis.
Remark 2: If $a=0$ xor $b=0$ there exists no invertible $X$. If $a=b=0$ any invertible matrix will to the trick.
Remark 3: You can omit the transpositions and calculate with row vectors and elementary row operations, that was just my personal preference...
Remark 4: Probably the easiest way is to take the canonical basis $e_1,\ldots,e_n$ and replace one of the vectors $e_k$ by $a^T$ like I did in the example. It will always work as long as $e_k\cdot a^T\neq0$.