Prove that a real matrix is a matroid

Question

Problem

• $A$ real matrix, size $m\times n$
• $M$ some structure, possible matroid
• $E(M)$ set of all columns of $A$ (we're considering them vectors)
• $I(M)$ set of all linearly independent columns of $A$

And now, I'm supposed to prove, that the structure $M$ really is matroid.

---

My attempt

I know about axioms for $I(M)$:

1. $\emptyset \in I(M)$
2. $(i_1 \in I(M) ) \wedge (i_2 \subset i_1) \Rightarrow (i_2 \in I(M))$
3. $\big( i_1, i_2 \in I(M) \big) \wedge \big(||i_1|| > ||i_2|| \big) \Rightarrow \big(\exists d \in (i_1 \setminus i_2): i_2 \cup \{d\} \in I(M) \big)$

But even with them, I have no idea, how should I proceed to prove that M is a matroid. So, how should I begin with it? I think the most problematic will be the third axiom...

---

Is $\emptyset$ linearly independent?

Yes, because it doesn't contain any linear combination of vectors.

Any linear dependence of vectors that holds in I2 also holds in I1

$i_1 \in I(M)$

$\Rightarrow i_1$ is linearly independent

$\Rightarrow \big( (c_1v_1 + c_2v_2 + ... + c_nv_n = 0) \Rightarrow (c_1 = c_2 = ... = c_n = 0) \big), \forall v \in i_1$

$\tilde{v_1} + \tilde{v_2} + ... + \tilde{v_n} \in i_2$

$i_2 \subset i_1$

$\Rightarrow \tilde{v_1} + \tilde{v_2} + ... + \tilde{v_n} \in i_1$

$\Rightarrow$ all vectors in $i_2$ are also linearly independent

$\Rightarrow i_2$ is linearly independent

Answer 1

1. Is the empty set of columns linearly independent?

   Yes (check the definition of linear independence).

2. Is any subset $I_2$ of a linearly independent set of columns $I_1$ linearly independent?

   Hint: Prove that any linear dependence of vectors that holds in $I_2$ also holds in $I_1$.

3. If $I_1, I_2$ are linearly independent sets of column vectors with $\lvert I_1\rvert > \lvert I_2\rvert$ then what can you say about the dimensions of the spaces they span? Can you then use this to construct a vector $d \in I_1 \setminus I_2$ such that $I_2 \cup \{d\}$ is linearly independent?