Singleton is Independent implies Rank is One/Corollary
< Singleton is Independent implies Rank is One(Redirected from Singleton is Independent iff Rank is One)
Jump to navigation
Jump to search
Theorem
Let $M = \struct{S, \mathscr I}$ be a matroid.
Let $x \in S$.
Then:
- $\set x$ is an independent subset if and only if $\map \rho {\set x} = 1$
where $\rho$ denotes the rank function of $M$.
Proof
By definition of an independent subset:
- $x$ is an independent subset if and only if $\set x \notin \mathscr I$
From Singleton is Independent implies Rank is One:
- if $\set x \in \mathscr I$ then $\map \rho {\set x} = 1$
From Singleton is Dependent implies Rank is Zero:
- if $\set x \notin \mathscr I$ then $\map \rho {\set x} = 0$
It follows that:
- $\set x \in \mathscr I$ if and only if $\map \rho {\set x} = 1$
$\blacksquare$