# Submatrix of small rank

Let $G=(V,E)$ be a graph with adjacency matrix $M=(m_{ij};i,j \in V )$ over $\mathbb{F}_2$ and $k \in \mathbb{Z^+}$. How can we find in polynomial time a subset $A \subseteq V$ such that

1. The rank of the sub matrix $M[A, V\setminus A] \leq k$

2. $|A|\geq |V|/c$, $|V \setminus A|\geq |V|/c$, for some constant $c>1$.

where $M[A, V\setminus A]$ denote the submatrix $(m_{ij};i \in A, j \in V \setminus A)$.

Note: Assume that existence of such a subset $A$ is guaranteed. .

• Assume we take $A=\emptyset$ (or any $A$ smaller than $k$). Doesn't it satisfy the rank request? do you have further constraints on the size of $A$?
– R B
Nov 16 '15 at 17:53
• Sorry I forgot to mention it. size of $A$ is at least some constant fraction of $|V|$. i.e., $|A| > |V|/c$ for $c>1$. Nov 16 '15 at 17:57
• Is $k$ a constant? Is a running time of $O(n^{f(k)})$ allowed? Feb 25 '20 at 11:51
• Even for $k=0$ you are looking for a submatrix not containing any diagonal elements that consists of all zeros (because the rank of the submatrix has to be zero). Thus in the complement of the graph you are searching for a bipartite clique of linear size -- which is $\mathsf{NP}$-hard, I presume. If you replace $n/c$ by $K$ then there is an obvious $n^{K}$ algorithm Just guess the at most $k\times k$ full-rank matrix and a disjoint $(K-k)\times (K-k)$ matrix of rank $0$ making sure that you never guess the same row and column in either guess. Feb 25 '20 at 12:13
• Ah! I see now taht this is already an answer by @ThomasS Feb 27 '20 at 7:11

Note that the notion of rankwidth uses "rank over the finite field $\mathbb{F}_2$", which may or may not be the field you were asking about.
This looks rather NP-hard (i.e., as it is obviously in NP, NP-complete) to me: Already the case $k=1$ looks hard (and interesting!). It asks for a large submatrix for which a vector $v$ exists such that all columns are either zero or $v$. The subgraph induced by $A$ thus has sets $B$ and $C$ such that (1) the nodes of $B$ have no outgoing edges (in $A$) and (2) all other nodes in $A-B$ have outgoing edges exactly to $C$. This looks like a "linear combination" of Clique and Independent set: $B=\emptyset, C=A$ yields a clique, $C=\emptyset,B=A$ and independent set. I do not know whether this has been studied before. (This is rather a comment, but it was too long...)