7
$\begingroup$

Given $M$ a symmetric matrix in $\mathbb F_2^{n\times n}$ having $\mathsf{det}_\mathbb R(M)\neq0$ (non-singular in reals) and satisfying $PMP'=(M+J+I)$ or $P(M+J+I)P'=M$ where $P$ is a permutation matrix in $\mathbb F_2^{n\times n}$ and where $J$ is all $1$s and $I$ is identity matrix in $\mathbb F_2^{n\times n}$ ($'$ is transpose and so $P'=P^{-1}$ holds).

$\mathsf{Det}(M)=\mathsf{Det}(M+J+I)$ and $\mathsf{Det}(M+I)=\mathsf{Det}(M+J)$ are satisfied as $\mathsf{Det}(P)\equiv1\bmod2$.

Can $M,M+I\not\in\mathsf{SL}(n,\mathbb F_2)$ be simultaneously impossible?

Is there an example of $\mathsf{det}(M)+\mathsf{det}(M+I)\equiv1\bmod2$?

Update Antoine Labelle's comments below suggests either $M,M+I\in\mathsf{SL}(n,\mathbb F_2)$ or $M,M+I\not\in\mathsf{SL}(n,\mathbb F_2)$ holds and he has no situation $\mathsf{det}(M)+\mathsf{det}(M+I)\equiv1\bmod2$.

$\endgroup$
5
  • $\begingroup$ what is $P'$? $P$ transposed? $\endgroup$
    – user42024
    Mar 16, 2021 at 10:03
  • 3
    $\begingroup$ In 1, is $\mathsf{Det}(P) = 1$ a separate condition that you mean to impose? Do you not mean to impose it in 2? \\ Also, the answer to 1 is trivially yes, by taking $n = 1$ and $M = 0$, so I guess you want to exclude that case. \\ Finally, it seems weird to specify $P M P' = M + J + I$ or $P(M + J + I)P' = M$, since these conditions are equivalent for $P$ a permutation matrix. $\endgroup$
    – LSpice
    Mar 16, 2021 at 12:39
  • 3
    $\begingroup$ Doesn’t every permutation matrix have determinant 1 over the binary field? $\endgroup$ Mar 16, 2021 at 13:08
  • $\begingroup$ If $PMP’=M+I+J$ then $P(M+I)P’=PMP’+PIP’=M+J$ because $P’=P^{-1}$, permutation matrices are orthogonal. $\endgroup$ Mar 16, 2021 at 13:55
  • $\begingroup$ I am not sure what the question is now. The latest iteration seems to be equivalent to: can both $0$ and $1$ be eigenvalues of $M$? It may also be noted that if there is such a permutation matrix $P$, it may be assumed to have order a power of $2$. $\endgroup$ Mar 16, 2021 at 19:07

2 Answers 2

1
$\begingroup$

Most of the question has already been addressed. As regards the last part, I just poit out that if ${\rm det} M = 0$ and ${\rm det}(M+I) = 1$, then we must have ${\rm rank}(M) = n-1$ ( I mean here the $\mathbb{F}_{2}$ rank). This follows since $M + I + J$ is (by assumption) similar to $M$, and hence has the same rank. If that rank is $n-2$ or less, then the null space of $M+I+J$ is at least two-dimensional, and the null space of $J$ is $n-1$ dimensional. Hence there is a non-zero column vector $v$ with $(M+I+J)v = 0$ and $Jv = 0.$ Hence $(M+I)v = 0,$ so that ${\rm det}(M+I) = 0.$

$\endgroup$
4
  • $\begingroup$ If the rank of $M+I+J$ were $n-2$ or less, then subadditivity of the rank would give $\textrm{rank}(M+I)=\textrm{rank}(M+I+J+J) \le \textrm{rank}(M+I+J) + \textrm{rank}(J) \le (n-2)+1=n-1$, contradicting $\det(M+I)=1$. $\endgroup$ Mar 19, 2021 at 1:52
  • $\begingroup$ But this does not show that $\det(M)=0$ while $\det(M+I)=1$ is impossible, correct? It shows only that $M$ must have rank $n-1$ in this case? Or is that somehow enough? $\endgroup$ Mar 19, 2021 at 1:54
  • $\begingroup$ @LouisDeaett:: Your first comment is essentially the argument I use. As for the second comment, indeed I do not claim to have completely answered that part of the question, and I have only shown that in case det M = 0, the only way that det(M+I) = 1 can occur is if M has rank n-1. I do not say, claim or prove that this is enough to exclude det (M+I) = 1 when det M = 0. $\endgroup$ Mar 19, 2021 at 13:07
  • $\begingroup$ Okay, that is what I thought, but I just wanted to verify. I agree it's an observation that does feel like it should be useful. $\endgroup$ Mar 19, 2021 at 16:19
6
$\begingroup$

Some computation in sage yielded the following example, with $n=8$ and $P$ the cyclic permutation $(12345678)$:

$$M=\left( \begin{array}{cc} 0 & 0 & 0 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 1 & 0 & 1 & 0 & 0 \\ \end{array} \right)$$

Interesting observation: Computation seems to show, however, that we always have $\text{det}(M)= \text{det}(M+I)$ (at least for cyclic permutations, which are the ones I tested). In other words, $M$ cannot have one of $0,1$ as an eigenvalue without the other. I wonder if this could be proven.

EDIT: Here is an example (still for a cyclic permutation) with nonzero determinant in characteristic $0$ if we replace the elements of $\mathbb{F}_2$ by their representative in $\{0,1\}$. The characteristic $0$ determinant is $16$.

$$M=\left( \begin{array}{cc} 0 & 0 & 0 & 0 & 1 & 1 & 0 & 1 \\ 0 & 0 & 1 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 1 & 0 & 0 & 1 & 1 & 1 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 1 & 1 & 0 & 1 & 0 & 0 \\ 1 & 1 & 1 & 0 & 0 & 1 & 0 & 0 \\ \end{array} \right)$$

$\endgroup$
4
  • $\begingroup$ In the comment on $8|n$ are you talking det mod $2$ or det in reals (in answer you say det is $16$ so I think you imply det mod $2$)? Can you check for $n=4k+a$ where $a\in\{0,1\}$? My guess is det in reals is mostly $0$ (hence $0\bmod2$) if $a=1$. $\endgroup$
    – Turbo
    Mar 19, 2021 at 12:20
  • $\begingroup$ Yes unless specified otherwise it's over $\mathbb{F}_2$. Also for cyclic permutations it's easy to see that the matrix $M$ can only exist if $4|n$, so $a=1$ is impossible. $\endgroup$ Mar 19, 2021 at 13:10
  • $\begingroup$ Why is it easy to see? $\endgroup$
    – Turbo
    Mar 19, 2021 at 14:04
  • $\begingroup$ The condition $PMP'=(M+J+I)$ basically says that $M_{i+1,j+1}=M_{i,j}+1$ for $i\ne j$, (indices taken mod $n$). If $n$ is odd you can deduce $M_{i,j}=M_{i,j}+1$ by repeating this, which is impossible. Similarly if $n=2k$ with $k$ odd we find $M_{i,i+k}=M_{i+k,i}+1$ which is imposibble as $M$ is symmetric. $\endgroup$ Mar 19, 2021 at 18:00

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.