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$ Feb 3, 2021 at 7:27
  • $\begingroup$ Can you explain? $\endgroup$
    – Turbo
    Feb 3, 2021 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$ Feb 3, 2021 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$
    – Turbo
    Feb 3, 2021 at 7:35

1 Answer 1

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$
5
  • $\begingroup$ Interesting.. so always first entry is $1\neq0$? $\endgroup$
    – Turbo
    Feb 3, 2021 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$ Feb 3, 2021 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$
    – Turbo
    Feb 3, 2021 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$ Feb 3, 2021 at 7:49
  • $\begingroup$ I am looking at $\mathbb F_2$. So perhaps there is a possibility in $\mathbb F_2$ if not in $\mathbb R$? $\endgroup$
    – Turbo
    Oct 18, 2021 at 2:52

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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