I had an idea. Let us start with an example. Consider the matrix $$ A = \left[ \begin{array}{ccc} 1 & 1 & 0 \\ 1 & 1 & 1 \\ 1 & 0 & 1 \end{array} \right] $$ It is invertible, since its determinant is $1$. Now consider the sequence of the upper-left square submatrices:
$$ A \left[ 1 \right] = \left[ \begin{array}{c} 1 \end{array} \right], \quad A \left[ 1,2 \right] = \left[ \begin{array}{cc} 1 & 1\\ 1 & 1 \end{array} \right], \quad A \left[ 1,2,3 \right] = A $$ The second matrix is singular (its determinant is zero). However, we can find other sequence of nested "central" sub-matrices such that all of them are invertible: $$ A \left[ 1 \right] = \left[ \begin{array}{c} 1 \end{array} \right], \quad A \left[ 1,3 \right] = \left[ \begin{array}{cc} 1 & 0\\ 1 & 1 \end{array} \right], \quad A \left[ 1,2,3 \right] = A $$ I wonder whether such a sequence always exists. I need some notation to enunciate the problem.
Let $A$ be a $n \times n$ matrix. Given $S \subset \left[ 1,n \right]$, we denote $A\left[ S \right]$ the matrix obtained from $A$ by only taking the rows and columns whose index are in $S$. Formally, $$ A\left[ S \right] = R_S \, A \, R^t_S, $$ where $S = \lbrace s_1 < \ldots < s_m \rbrace$ and $R_s$ is the $m \times n$ matrix with $1$ at the positions $(i, s_i)$ and zero elsewhere.
Question: Let $A$ be a regular $n \times n$ matrix. Under which conditions there exist a nested sequence $$ S_1 \subset S_2 \subset \cdots \subset S_n = \left[ 1,n \right], \quad |S_i| = i$$ such that each $A\left[ S_i \right]$ is regular? How to compute such a sequence? How many sequences are there?
It is trivial that the matrix must have a non-zero entry in its diagonal. Does anybody know if this problem has already been studied?
I have made several numerical experiments (with $n < 6$) and it seems that almost every sequence verify the condition.
Let $A$ be a matrix and suppose that $\dim(\text{image}(A))=k$. This means that there are $k$ independent columns in $A$. Let $0\leq r\leq k$. Choose $r$ independent columns in $A$.
Now, consider these $r$ columns in a new (sub-matrix) $B$ of $A$. Since the rank of $B$ is $r$, it has $r$ independent rows. Choose $r$ independent rows in $B$.
Let $C$ be the sub-matrix of $B$ formed from these independent rows of $B$. This is a square matrix of size $r\times r$ which is invertible because its rows are independent.
To count the number of such sequences may be more challenging.
This does not answer the question posed by the OP, but is a substitute, since the invertible matrix $$\begin{bmatrix}0&1\\1&0\end{bmatrix}$$ fails the conditions. The answer above is the same after applying a permutation, perhaps.