0
$\begingroup$

Where $V$ is a vector space and $E$ is a finite subset of $V$. $I$ is the the set of linearly independent subsets of $E$. How to prove $(E, I)$ is a matroid?

Edit: I understand that by definition $M$ = $(E, S)$ is called a matroid if $A, B ∈ S$ such that $|B| = |A| + 1$, then $∃v ∈ B\setminus A $ with $A ∪ {v} ∈ S$.

This is part of a homework problem. But I am new to this and would appreciate a hint or a construction of the proof.

$\endgroup$
0

1 Answer 1

0
$\begingroup$

$A$ is a set of $|A|$ independent vectors, thus it spans $|A|$ dimensions. The vectors in $B$ span $|A|+1$ dimensions. if all the vectors in $B$ were some linear combination of vectors in $A$ then $B$ would only span $|A|$ dimensions, so there must be a vector in $B$ independent from $A$, that vector can be added to $A$ to form a bigger independent set.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .