Given an $n\times n$ matrix $A$, whose elements are over $GF\left(2\right)$ and all diagonal elements are $1$. There are $m\ (m\leq n^2-n)$ non-zero off-diagonal elements in $A$. If we are allowed to choose $k$ non-zero off-diagonal elements of $A$ and set them to $0$, then what is the minimum rank of $A$ over all $k\ (k\leq m)$ and all possible choices?

Denote the above minimum rank as $\text{mk}_2$, since the number of all possible choices (the size of the search spaces) is $2^m$, it's hard to determine $\text{mk}_2$ exactly. If we want to calculate $\text{mk}_2$ approximately, $e.g.$, find possible choices whose rank are less than $c\cdot \text{mk}_2$ or $\text{mk}_2+c$ ($c$ is a constant not increasing with $n$ and $m$), then what is the number of possible choices satisfying this demand?

Is there any structure that can be used to reduce the search spaces in the problem of determining $\text{mk}_2$ exactly? Is there any approximation algorithm that is guaranteed to get within a certain factor of $\text{mk}_2$ with polynomial complexity?


If $A$ is block diagonal then the problem can be reduced by considering each block independently.

Considering $n=6$ in the example proposed by @Robert Israel, the matrix over $GF(2)$ is $$A= \left(\begin{matrix} 1&0&1&0&1&0\\ 0&1&1&1&0&1\\ 1&0&1&1&1&0\\ 0&1&0&1&1&1\\ 1&0&1&0&1&1\\ 0&1&0&1&0&1\\ \end{matrix}\right) \tag{2}.$$

The rank of $A$ is $6$. There are $16$ off-diagonal '1's in $A$. The $\text{mk}_2$ of $A$ is $2$ and the corresponding unique choice of off-diagonal '1's is given in @Robert Israel's answer.

Now we compute the number of choices that give different ranks for each $k\ (k=0,1,2,\dots,16)$. The results are given as follows:

The number of choices of off-diagonal '1's that give the corresponding ranks


1 Answer 1


(EDITED) Changing one element can never decrease the rank by more than $1$, so changing $k$ elements can never decrease it by more than $k$. For at least some cases we can arrange to decrease it by $k$. For example, $$ \pmatrix{1 & 1 & 1 & 1\cr 0 & 1 & 1 & 1\cr 0 & 1 & 1 & 0\cr 1 & 0 & 1 & 1 \cr}$$ has rank $4$, but changing the $(4,3)$ and $(2,4)$ entries from $1$ to $0$ gives you a matrix of rank $2$. Using block matrices with copies of this on the diagonal, we find examples for all $n$ divisible by $4$ where the original matrix has $3n$ ones and rank $n$, and we can decrease the rank to $n/2$.

EDIT: Actually it seems there are examples for an $n \times n$ matrix with any even $n \ge 4$ where we can reduce the rank from $n$ to $2$ by changing $n-2$ $1$'s to $0$'s. The $n \times n$ matrix with entries $1$ for $i+j$ even and $0$ for $i+j$ odd has rank $2$ (because there are only two different rows). Change the $n-2$ entries in the first super-diagonal except in the first row, and we get an invertible matrix $A$: in fact its inverse (over $GF(2)$) has this block-matrix structure: $$ \pmatrix{1 & u & t\cr t & v & 1\cr v^T & I & u^T\cr}$$ where $$ t \equiv 1 + (n/2) \mod 2,\ u = [1,0,1,\ldots,0], \ v = [0,1,0,\ldots, 1]$$ Thus we can change $n-2$ $1$'s to $0$'s in $A$ and reduce the rank to $2$.

  • $\begingroup$ Excuse me, should the $m$ be $n$? $m$ is the number of off-diagonal non-zero elements in the problem. $\endgroup$
    – Tang
    Sep 7, 2018 at 6:06
  • $\begingroup$ Ah, yes (edited). $\endgroup$ Sep 7, 2018 at 6:07
  • $\begingroup$ This is a good example and provides some insights. $\endgroup$
    – Tang
    Sep 7, 2018 at 6:24
  • $\begingroup$ This problem has graph theory background. The matrix A-I is actually the adjacency matrix of a given directed graph, The operation in the problem corresponds to deleting some edges in the graph. In your example, the corresponding graph is some unconnected repeated subgraph. Maybe the original problem should add a constraint that the graph is connected. $\endgroup$
    – Tang
    Sep 7, 2018 at 6:28

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.