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

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.

• Isn't this basically Gaussian elimination with complete pivoting? Feb 3, 2021 at 7:27
• Can you explain? Feb 3, 2021 at 7:27
• What you are doing can be interpreted as follows: permute rows and column to bring an 1 to the top-left corner, make one step of Gaussian elimination, repeat. Feb 3, 2021 at 7:28
• I understand it. I am asking if there is a single permutation we can apply initially and we do not permute again in following iterations and we naturally satisfy $M_i(1,1)=1\neq0$ at every iteration $i\in\{1,2,\dots,n-1\}$. Feb 3, 2021 at 7:35

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.
• Interesting.. so always first entry is $1\neq0$? Feb 3, 2021 at 7:41
• If I understand correctly what you are asking, yes: unless the matrix is zero, there is always a way to bring an 1 to the top-left corner by permuting rows and columns with $P_{1,1}$ and $P_{2,1}$. Then the following permutations won't affect the (1,1) entry anymore, since they act on $(2,...,n)$ only. Feb 3, 2021 at 7:44
• I think you meant to say 'unless $M_i$ is zero matrix at an $i\in\{0,1,\dots,n-1\}$'? Feb 3, 2021 at 7:46
• Yes; my comment refers to step $i=0$ specifically, but then the same holds at each step; either $M_i$ is the zero matrix, or it has a 1 that you can permute into its (1,1) entry. Feb 3, 2021 at 7:49
• I am looking at $\mathbb F_2$. So perhaps there is a possibility in $\mathbb F_2$ if not in $\mathbb R$? Oct 18, 2021 at 2:52