Is the real rank of a matrix always larger than its binary rank

linear algebra

Let A be an $n \times n$ matrix, all of whose entries are either 0 or 1. $A$ can be viewed as a matrix over $\mathbb{F}_2$ or as a matrix over $\mathbb{R}$. Is there any relationship between the real rank (rank over $\mathbb{R}$) and the binary rank (rank over $\mathbb{F}_2$) of $A$?

(The context of this question comes from communication complexity, where one can bound the communication complexity of boolean functions by the ranks of their associated matrices. I've heard it claimed that the real rank is always at least as large as the binary rank, but haven't been able to find a source.)

Best Answer

If by "larger", you mean "not less than", then yes, it's true. Consider reducing the real matrix to row-echelon form. Any rows that end up being $0$ are also $0\pmod{2}$, but there may be additional, nonzero rows that are $0\pmod{2}$.

Related Question