Let \(X\) be any set and \(Y\) a finite set, and let \(R \subseteq X \times Y\) be a rectangle, meaning \(R = A \times B\) for some \(A \subseteq X\) and \(B \subseteq Y\). Let \(M_R \in \mathbb {R}^{X \times Y}\) be its indicator matrix, with \((M_R)_{x,y} = 1\) when \((x,y) \in R\) and \((M_R)_{x,y} = 0\) otherwise. Then \(\mathrm{rank}(M_R) \le 1\).

Let \(X\) be any index set and \(Y\) a finite index set, and let \(A, B \in \mathbb {R}^{X \times Y}\) be real matrices with rows indexed by \(X\) and columns indexed by \(Y\). Then

Let \(s\) be a finite subset of an index set, and let \((A_i)_{i \in s}\) be a family of real matrices with rows indexed by a set \(X\) and columns indexed by a finite set \(Y\). Then the rank of their sum is at most the sum of their ranks:

Let \(X\) be a finite set, \(Y\) a finite set, and \(f : X \to Y \to \mathrm{Bool}\) a Boolean function. If \(\mathcal{P}\) is a monochromatic rectangle partition of \(X \times Y\) for \(f\), then the rank of \(f\) is at most the number of members of \(\mathcal{P}\):

Let \(X\) and \(Y\) be finite types and let \(f : X \to Y \to \mathrm{Bool}\) be a two-party Boolean function, whose rank \(\mathrm{rank}(f)\) is the \(\mathbb {R}\)-rank of the \(0/1\) matrix \(M_f \in \mathbb {R}^{X \times Y}\) with \((M_f)_{x,y} = 1\) exactly when \(f\, x\, y = \mathrm{true}\). If the deterministic communication complexity \(D(f)\) is at most \(n\) for some \(n \in \mathbb {N}\), then \(\mathrm{rank}(f) \le 2^n\).

Let \(X\) be a finite type and \(Y\) a finite type, and let \(f : X \to Y \to \mathrm{Bool}\) be a Boolean function with associated \(0/1\) matrix \(M_f \in \mathbb {R}^{X \times Y}\), whose rank \(\mathrm{rank}(f) = \mathrm{rank}_{\mathbb {R}}(M_f)\) is the rank of \(f\). Then the deterministic communication complexity \(D(f) \in \mathbb {N}_\infty \) of \(f\) satisfies