Suggest a Book

# Matrix rank is submodular

Level: unknown

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.
Source: folklore
delete retag edit

## Stats

Posted: Aug 12 '12

Seen: 69 times

Last updated: Aug 12 '12