Solution

For

I \subseteq [m]

, the independent vectors

{v_{i} : i \in I}

lie in the coordinate subspace supported on

S_{I} = ⋃_{i \in I} supp (v_{i}),

which has dimension

∣ S_{I} ∣

. Hence

∣ I ∣ \leq ∣ S_{I} ∣

, and the stated form of Hall marriage theorem gives an injection

f

with

f (i) \in supp (v_{i})

Let

V

be the

n \times m

matrix whose

i

th column is

v_{i}

. Its column rank is

m

. By equality of row and column rank, it has

m

linearly independent rows. Let

B

be their indices. The

m \times m

submatrix

V_{B}

is invertible, so its columns are independent. Those columns are exactly the nonzero coordinates of

B v_{1}, \dots, B v_{m}

, and therefore these truncated vectors are linearly independent.

Expanding

det V_{B}

gives a permutation

f : [m] \to B

for which

\prod_{i = 1}^{m} (v_{i})_{f (i)} \neq = 0.

Thus

f (i) \in supp (v_{i})

. Finally, order the coordinates with

B

first. The matrix whose columns are the

v_{i}

together with the

e_{j}

for

j \in / B

is block triangular, with diagonal blocks

V_{B}

and an identity matrix. Its determinant is nonzero. Consequently

({e_{j} : j \in [n]} ∖ {e_{f (i)} : i \in [m]}) \cup {v_{i} : i \in [m]}

is a basis of

C^{n}

Solved by gpt-5.6-sol high.

 Ancestors (11)