0
$\begingroup$

Let $M$ be a $0/1$ matrix over $\mathbb F_2^{n\times n}$ with determinant $0$.

The set of such singular matrices form a semigroup.

The set of nilpotent matrices of size $n\times n$ form a semigroup.

  1. Are there always permutations $P,Q$ such that $PMQ$ is nilpotent?

  2. How many permutations $P,Q$ are always there such that $PMQ$ is nilpotent?

  3. If $T$ is nilpotent, there is always a $k\leq n$ such that there is always a row or column with all $0$s in $T^k$. What is a tight upper bound on $k$ as a function of $n$ that works for all nilpotent matrices in $\mathbb F_2^{n\times n}$?

  4. Are there always permutations $P,Q$ such that $(PMQ)^2$ contains a $0$ row or a $0$ column?

Improve this question
$\endgroup$
6
  • 5
    $\begingroup$ $M=\pmatrix{1&1\cr0&0\cr}$ has determinant zero, but there are no permutations $P,Q$ such that $PMQ$ is nilpotent. $\endgroup$
    – Gerry Myerson
    Commented Apr 18, 2023 at 7:34
  • $\begingroup$ I think it is called index when the matrix vanishes valnishes. There is no nomenclature for the $k$ introduced. $\endgroup$
    – Turbo
    Commented Apr 18, 2023 at 16:10
  • $\begingroup$ The nilpotent elements do not form a subsemigroup. Take E_12 E_21=E_11 $\endgroup$
    – Benjamin Steinberg
    Commented Apr 18, 2023 at 19:13
  • 1
    $\begingroup$ If n is a power of 2 the answer to 3 is k=n. Take I+P where P is the permutation matrix of order 2^n corresponding to the cyclic permutation (1,2,...,n) $\endgroup$
    – Benjamin Steinberg
    Commented Apr 18, 2023 at 20:12
  • 1
    $\begingroup$ Sorry, in my last comment I meant of order n which is a power of 2 $\endgroup$
    – Benjamin Steinberg
    Commented Apr 19, 2023 at 0:22

0

Reset to default

You must log in to answer this question.