Past exam of the mathematics course of the University of Cambridge / 2024 / ib / Paper 4 / 8G / b / Solution

For $I\subseteq [m]$, the independent vectors $\{v_i:i\in I\}$ lie in the coordinate subspace supported onwhich has dimension $|S_I|$. Hence $|I|\le |S_I|$, and the stated form of Hall marriage theorem gives an injection $f$ with $f(i)\in \mathrm{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 whichThus $f(i)\in \mathrm{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\notin B$ is block triangular, with diagonal blocks $V_B$ and an identity matrix. Its determinant is nonzero. Consequentlyis a basis of ${\mathbb{C}}^n$. This is the simultaneous basis exchange from a nonzero minor.