4
$\begingroup$

Let $M\in\{-1,0,+1\}^{n\times n}$ be a matrix of rank $r$.

Consider the matrix $f(M)\in\{0,+1\}^{mn\times mn}$ where $0$ in $M$ is replaced by $m\times m$ all $0$ matrix, $+1$ in $M$ is replaced by $m\times m$ identity matrix and $-1$ in $M$ is replaced by $m\times m$ anti-identity matrix (anti-diagonal matrix having $1$s on anti-diagonal whose square is identity).

Example at $m=2$:

$0$ is replaced by $\begin{bmatrix}0&0\\0&0\end{bmatrix}$, $+1$ is replaced by $\begin{bmatrix}1&0\\0&1\end{bmatrix}$ and $-1$ is replaced by $\begin{bmatrix}0&1\\1&0\end{bmatrix}$.

  1. Is the real rank of the new matrix $O(r)$? Is there a precise bound?
  1. Is the $\mathbb F_2$ rank of the new matrix $O(r)$? Is there a precise bound?

On the real and finite field rank of a $0/1$ matrix - II

$\endgroup$
3
  • $\begingroup$ What is the definition of $r$? $\endgroup$ Commented Mar 21, 2021 at 14:04
  • $\begingroup$ "Intuitively" (so likely very wrong :-) a Hadamard matrix would be a worst case, but the rank does not seem to drop even over $\Bbb{F}_2$. $\endgroup$ Commented Mar 21, 2021 at 20:58
  • $\begingroup$ @RichardStanley Real rank (I thought it was clear because of $-1\in\{-1,0,+1\}$). $\endgroup$
    – Turbo
    Commented Mar 21, 2021 at 21:02

1 Answer 1

1
$\begingroup$

A partial answer: if we write $M = M_+ - M_-$ where $M_+$ and $M_-$ are zero-one matrices corresponding to the nonnegative and nonpositive entries respectively, then we have $$f(M) = M_+ \otimes I + M_- \otimes A$$ for $A$ the anti-identity matrix. Over the reals, $A$ is diagonalizable, with eigenvalues $1$ with multiplicity $\lceil m/2 \rceil$ and $-1$ with multiplicity $\lfloor m/2 \rfloor$. Call the eigenspaces $W$ and $W'$ respectively. Clearly $f(M)$ preserves the decomposition of $\mathbb R^{mn}$ into $\mathbb R^n \otimes W$ and $\mathbb R^n \otimes W'$, on which it respectively acts as $(M_+ + M_-) \otimes I$ and $(M_+ - M_-) \otimes I$. Thus we get the exact answer $$\operatorname{rank} f(M) = \lceil m/2 \rceil \operatorname{rank} |M| + \lfloor m/2 \rfloor \operatorname{rank} M$$ where $|M| = M_+ + M_-$ is the entrywise absolute value. Assuming $M \ne 0$ this gives bounds $$\frac{(r + 1)m}{2} \le \operatorname{rank} f(M) \le \frac{(r+n)m}{2}$$ where the lower bound is achieved by Hadamard matrices but I don't know about the upper bound. From this old question it seems that for general matrices one can have $\operatorname{rank}|M| = n$ even for $M$ low rank, but I don't know if the situation for $\{0, \pm 1\}$-matrices is better.

(This argument completely collapses over $\mathbb F_2$, of course.)

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .