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.



Schur complement and depermuting an algorithm for $\mathsf{determinant}\bmod2$
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.


