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
    Apr 7, 2018 at 17:28
  • 1
    $\begingroup$ Ah, yes, minimum) $\endgroup$
    – Fedor Petrov
    Apr 8, 2018 at 15:57

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.