Return to Question

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, whenever an entry $B_{i,j}$ is equal to $0$, all the entries of the $i$-th row or the $j$-th column of $B$ are equal to $0$ too.

Namely, given any such block $B\in \{0,1\}^{r_B\times c_B}$ of $M$, $B_{i,j}=0$ implies (i) $B_{i,p}=0~~\forall p\in [c_B]$ or (ii) $B_{q,j}=0~~\forall q\in [r_B]$ (hence, we may even have simultaneously both (i) and (ii)).

Note that this is equivalent to say that, given any such block $B\in \{0,1\}^{r_B\times c_B}$, we have $0$ or more rows and $0$ or more columns of $B$ containing only $0$-entries, 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$.

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$.

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, whenever an entry $B_{i,j}$ is equal to $0$, all the entries of the $i$-th row or the $j$-th column of $B$ are equal to $0$ too.

Namely, given any such block $B\in \{0,1\}^{r_B\times c_B}$ of $M$, $B_{i,j}=0$ implies (i) $B_{i,p}=0~~\forall p\in [c_B]$ or (ii) $B_{q,j}=0~~\forall q\in [r_B]$ (hence, we may even have simultaneously both (i) and (ii)).

Note that this is equivalent to say that, given any such block $B\in \{0,1\}^{r_B\times c_B}$, we have $r^0_B \in \{0, 1, \dots, r_B\}$ rows and $c^0_B \in \{0, 1, \dots, c_B\}$ columns of $B$ containing only $0$-entries, 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$.

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, whenever an entry $B_{i,j}$ is equal to $0$, all the entries of the $i$-th row or the $j$-th column of $B$ are equal to $0$ too.

Namely, given any such block $B\in \{0,1\}^{r_B\times c_B}$ of $M$, $B_{i,j}=0$ implies (i) $B_{i,p}=0~~\forall p\in [c_B]$ or (ii) $B_{q,j}=0~~\forall q\in [r_B]$ (hence, we may even have simultaneously both (i) and (ii)).

Note that this is equivalent to say that, given any such block $B\in \{0,1\}^{r_B\times c_B}$, we have $0$ or more rows and $0$ or more columns of $B$ containing only $0$-entries, 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$.

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, whenever an entry $B_{i,j}$ is equal to $0$, all the entries of the $i$-th row or the $j$-th column of $B$ are equal to $0$ too.

Namely, given any such block $B\in \{0,1\}^{r_B\times c_B}$ of $M$, $B_{i,j}=0$ implies (i) $B_{i,p}=0~~\forall p\in [c_B]$ or (ii) $B_{q,j}=0~~\forall q\in [r_B]$ (hence, we may even have simultaneously both (i) and (ii)).

Note that this is equivalent to say that, given any such block $B\in \{0,1\}^{r_B\times c_B}$, we have $r^0_B \in \{0, 1, \dots, r_B\}$ rows and $c^0_B \in \{0, 1, \dots, c_B\}$ columns of $B$ containing only $0$-entries, 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$.

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, whenever an entry $B_{i,j}$ is equal to $0$, all the entries of the $i$-th row or the $j$-th column of $B$ are equal to $0$ too.

Namely, given any such block $B\in \{0,1\}^{r_B\times c_B}$ of $M$, $B_{i,j}=0$ implies (i) $B_{i,p}=0~~\forall p\in [c_B]$ or (ii) $B_{q,j}=0~~\forall q\in [r_B]$ (hence, we may even have simultaneously both (i) and (ii)).

Note that this is equivalent to say that, given any such block $B\in \{0,1\}^{r_B\times c_B}$, we have $r^0_B \in \{0, 1, \dots, r_B\}$ rows and $c^0_B \in \{0, 1, \dots, c_B\}$ columns of $B$ containing only $0$-entries, 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$.