2
$\begingroup$

We are given a matrix $M \in \{0,1\}^{n\times n}$ satisfying the following property.

The rows and columns of $M$ can be partitioned into $k$ rowgroups and $k$ colgroups respectively, such that in each block $B \subseteq M$ induced by these partitions, we have $0$ or more rows and $0$ or more columns of $B$ containing only entries equal to $0$, while all the remaining entries of $B$ are equal to $1$.

Question: What is the maximum rank of $M$?

I only know the maximum rank of $M$ is upper bounded by $k^2$.

Improve this question
$\endgroup$

1 Answer 1

Reset to default
1
$\begingroup$

The answer is $\min(n,k^2)$.

The upper estimate: rank of $n\times n$ matrix does not exceed $n$, and rank of the sum of at most $k^2$ matrices of rank 1 does not exceed $k^2$.

Example: enumerate rows and columns from 0 to $n-1$ and partition the columns from 0 to $N-1:=\min(n,k^2)$ by the value of remainder modulo $k$; partition rows from 0 to $N-1$ by the value of quotient after division by $k$. Put 1's on the main diagonal at the places $0,1,\dots,N-1$ and zeroes at other places. This matrix has rank $N$ and it satisfies your condition: each block has at most one 1.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Great, thank you! PS: Typo: I guess obviously you mean $\min(n,k^2)$ by writing $\max(n,k^2)$, right? $\endgroup$
    – Penelope Benenati
    Commented Apr 7, 2018 at 17:28
  • 1
    $\begingroup$ Ah, yes, minimum) $\endgroup$
    – Fedor Petrov
    Commented Apr 8, 2018 at 15:57

You must log in to answer this question.

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