I have an under-determined homogenous linear system $Ax=0$ where matrix $A$ has dimensions $[m \times n], m<n$ and $rank(A) < m$. For example:
$A= \left[ \begin{array}{c|[cccc]} & c_1 & c_2 & c_3 & c_4\\ \hline r_1 & 1 & 1 & 0 & 1\\ r_2 & 0 & 0 & 1 & 1\\ r_3 & 0 & 0 & 0 & 0\\ \end{array} \right] $
n.b. Since I am not so familiar with MathJax, I have the row labels, $r_i$, and column labels, $c_i$, inside the matrix. The free variables of this matrix are $c_2$ and $c_4$.
If we permute the columns of the matrix and subsequently transform to reduced row echelon form (RREF), we see:
$A\cdot T=A'= \left[ \begin{array}{c|[cccc]} & c_1 & c_2 & c_4 & c_3\\ \hline r_1 & 1 & 1 & 1 & 0\\ r_2 & 0 & 0 & 1 & 1\\ r_3 & 0 & 0 & 0 & 0\\ \end{array} \right] \xrightarrow{\text{RREF}} \left[ \begin{array}{c|[cccc]} & c_1 & c_2 & c_4 & c_3\\ \hline r_1 & 1 & 1 & 0 & -1\\ r_2 & 0 & 0 & 1 & 1\\ r_3 & 0 & 0 & 0 & 0\\ \end{array} \right] $
The free variables are now $c_2$ and $c_3$ (note columns labels of the matrices).
My question: I would like to find the fewest possible permutation matrices $T$, such that the set of all free variables of the permuted matrices $A'$ contains all variables (=columns of $A$). If there is no analytical way of doing this, is there maybe a smart iterative way of finding or combining permutation matrices?
In this instance, two permutation matrices suffice. The identity matrix $I$ gives free variables $\{ c_2, c_4\}$. Matrix:
$T = \left[ \begin{array}{ccc]} 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0\\ \end{array} \right] \xrightarrow{\text{}} A \cdot T \overset{RREF}{=} \left[ \begin{array}{c|[cccc]} & c_2 & c_1 & c_4 & c_3\\ \hline r_1 & 1 & 1 & 0 & -1\\ r_2 & 0 & 0 & 1 & 1\\ r_3 & 0 & 0 & 0 & 0\\ \end{array} \right] $
gives free variables $\{ c_1, c_3\}$. Thus the union of the free variables for permutation matrices $I,T$ is $\{c_1, c_2, c_3, c_4\}$, which is all the possible variables.
To give a sense of my actual problem: $A^{[59 \times 79]}$ and $rank(A)=38$. I thus want the smallest amount of permutation matrices that gets all 79 variables to be free.