Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$

Question

Let $$M=\begin{bmatrix}A&B\\C&D\end{bmatrix}$$ be a matrix in $\mathbb F_2^{n\times n}$ where $A\in\mathbb F_2$ and $D\in\mathbb F_2^{(n-1)\times(n-1)}$ are square.

Through the determinant result on Schur complement $$\det(M)=\det(D-CB)$$ if $A=1$ holds.

It suggests an algorithm for $\det(M)$. Without loss of generality assume $A=M_{1,1}=1$.

At step $i\in\{0,1,\dots,n-1\}$ we permute the $(n-i)\times(n-i)$ matrix $M_i=\begin{bmatrix}A_i&B_i\\C_i&D_i\end{bmatrix}$ (where $M_0=M$ and $A_i\in\mathbb F_2$ and $D_i\in\mathbb F_2^{(n-i-1)\times(n-i-1)}$ holds) by $P_{1i}M_iP_{2i}$ where $P_{1i},P_{2i}\in\mathbb F_2^{(n-i)\times(n-i)}$ are permutation matrices satisfying $M_i(1,1)=1$ (first entry is $1$ and so invertible) and set $M_{i+1}=D_i-C_iB_i\in\mathbb F_2^{(n-i-1)\times(n-i-1)}$.

At end of $n$ iterations the remaining entry is determinant of $M$.

My question:

Is there a single permutation $P_1,P_2\in\mathbb F_2^{n\times n}$ we can apply to $M$ and set $M_0=P_1MP_2$ so that $P_{1i}=P_{2i}$ are identity matrices in $\mathbb F_2^{(n-i)\times(n-i)}$ at every $i\in\{1,2,\dots,n-1\}$ so that either $M_i$ is a zero matrix at an $i\in\{1,2,\dots,n-1\}$ or $M_{n-1}=1$ holds?

My guess is the answer is no since number of matrices is $2^{\Omega(n^2)}$ while number of permutations is $2^{O(n\log n)}$. We require every permutation to depermute for $2^{\Omega(n^2)}$ matrices which is unlikely.

Answer 1

As the comments note, what you are doing is Gaussian elimination with complete pivoting: permute rows and column to bring an 1 to the top-left corner, make one step of Gaussian elimination, repeat.

Note that in this algorithm we can choose to apply all permutations directly before step 1, and the result won't change (just the ordering of rows/columns in the intermediate matrices). So if you have a working choice of $P_{1i}, P_{2i}$ at each step then this is equivalent to applying $P_1 = P_{1,n-1}P_{1,n-2}\dots P_{1,1}$ and $P_2 = P_{2,1}P_{2,2}\dots P_{n,2}$.

Is there a way to determine this permutation a priori, though? No, as far as I know, at least in $\mathbb{F}=\mathbb{R}$; the simplest way is constructing it one step at a time like you are doing. There is a lot of research on solving efficiently large and/or sparse linear systems in scientific computing, and as far as I know essentially the algorithms all permute on the go; I would be surprised if there is a trick they have missed.