Consider this matrix $$ A=\begin{pmatrix} 1 & 0 & 0 & 0 &|& 1 & 0 & 0 & 0\\ 1 & 0 & 0 & 0 &|& 0 & 1 & 0 & 0\\ 1 & 0 & 0 & 0 &|& 1 & 0 & 0 & 0\\ - & - & - & - &|& - & - & - & -\\ 0 & 1 & 0 & 0 &|& 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 &|& 0 & 0 & 0 & 1\\ 0 & 1 & 0 & 0 &|& 0 & 0 & 1 & 0\\ 0 & 1 & 0 & 0 &|& 0 & 0 & 0 & 1\\ - & - & - & - &|& - & - & - & -\\ 0 & 0 & 1 & 0 &|& 0 & 0 & 1 & 0\\ 0 & 0 & 1 & 0 &|& 0 & 0 & 0 & 1\\ 0 & 0 & 1 & 0 &|& 0 & 0 & 1 & 0\\ - & - & - & - &|& - & - & - & -\\ 0 & 0 & 0 & 1 &|& 1 & 0 & 0 & 0\\ 0 & 0 & 0 & 1 &|& 0 & 1 & 0 & 0 \end{pmatrix} $$
This matrix has size $12\times 8$ and it has rank $6$.
I want to find all the pairs of columns of $A$ that, once deleted, lead to a matrix $C$ of size $12\times 6$ that is full column rank $6$.
Can you suggest a formal way to do this? In particular, I would like to know if this is something we can understand from the row reduced echelon form of $A$.
My thoughts: By naive checking all possible pairs of columns of $A$, I have found that the "successful" pairs are of the form $(i,j)$ where $$ i\in \{1,4,5,6\}\\ j\in \{3,2,7,8\}\\ $$
In fact, take any $(i,j)$ where $i\in \{1,4,5,6\}$ and $j\in \{3,2,7,8\}$. Construct the matrix $C$ whose columns are the columns of matrix $A$ but the $i$-th and $j$-th columns. Then, $C$ has full column rank 6.
Note that, for example, the pair $(1,4)$ is not listed above. In fact, the matrix $C$ whose columns are the columns of matrix $A$ but the $1$-st and $4$-th columns has rank $5$.
I'm looking for a faster and more formal way to find all the "successful" pairs.
I thought about looking at the row reduced echelon form of $A$. This form suggests that we one "successful" pair is $(6,8)$. How can I find the others?