1
$\begingroup$

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.

$\endgroup$
4
  • 1
    $\begingroup$ Isn't this basically Gaussian elimination with complete pivoting? $\endgroup$ – Federico Poloni Feb 3 at 7:27
  • $\begingroup$ Can you explain? $\endgroup$ – 1.. Feb 3 at 7:27
  • $\begingroup$ 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. $\endgroup$ – Federico Poloni Feb 3 at 7:28
  • $\begingroup$ 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\}$. $\endgroup$ – 1.. Feb 3 at 7:35
1
$\begingroup$

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.

$\endgroup$
4
  • $\begingroup$ Interesting.. so always first entry is $1\neq0$? $\endgroup$ – 1.. Feb 3 at 7:41
  • $\begingroup$ 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. $\endgroup$ – Federico Poloni Feb 3 at 7:44
  • $\begingroup$ I think you meant to say 'unless $M_i$ is zero matrix at an $i\in\{0,1,\dots,n-1\}$'? $\endgroup$ – 1.. Feb 3 at 7:46
  • $\begingroup$ 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. $\endgroup$ – Federico Poloni Feb 3 at 7:49

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.