Matrix rank is submodular

posted Aug 12 '12

Shiva Kintali
691 ● 1 ● 6 ● 22
http://www.cs.princeton.e...

A real-valued set function $f : 2^S \rightarrow \mathcal{R}$ is called submodular if it satisfies the following property :

• $f(X \cup Y) + f(X \cap Y) \leq f(X) + f(Y)$ for all $X, Y \subseteq S$

Let $A$ be a matrix and let $C$ be the set of its columns. For $X \subseteq C$, let $r(X)$ denote the rank of the matrix formed by the columns in $X$.

• Prove that $r$ is submodular.