Rank-revealing transform to identity*

Question

how to calculate below matrices M and N for a (possibly singular) square matrix E?

As a bonus, the method should be applicable to E containing symbolic variables.

Rank-revealing transform

Answer 1

Let $E$ be a $n\times n$ matrix of rank $r$ over the field $k$. Let $x_{r+1}, \ldots, x_n$ be a basis of $\ker E$ and complete it into a basis $x_1,\ldots, x_r,x_{r+1},\ldots, x_n$ of $k^n$. Let :$$ N = \left(\begin{array}{c|c|c|c} x_1 & x_2 & \ldots & x_n\end{array}\right)$$

Then, we have : \begin{align} EN &= \left(\begin{array}{c|c} Ex_1 & Ex_2 & \ldots & Ex_n\end{array}\right) \\ &= \left(\begin{array}{c|c} y_1 & \ldots & y_r & 0 & \ldots & 0\end{array}\right) \end{align}

where $y_1,\ldots,y_r$ is a set of linearly independent vectors. Complete it into a basis $(y_1,\ldots,y_n)$ of $k^n$, then set : $$M = \left(\begin{array}{c|c|c|c} y_1 & y_2 & \ldots & y_n\end{array}\right)$$ so that : $$EN = M \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix}$$ i.e. $$E = M \begin{pmatrix} I_r & 0 \\ 0 & 0 \end{pmatrix}N^{-1}$$

If $E$ contains formal variables $X_1,\ldots,X_n$, just extends the base field to the rational fractions $k(X_1,\ldots,X_n)$, so the above algorithm works.

Algorithms You need two sub-algorithms : one to compute a basis of $\ker E$ (a quick search seem to indicate that Mathlab has a built-in function) and another one to extend a linearly independent family into a basis (see the different answers here).