Past exam of the mathematics course of the University of Cambridge / 2003 / ib / Paper 2 / 15E (Linear Mathematics)

By the rank-nullity theorem, $\mathrm{nullity}A=n-\mathrm{rank}A\ge n-m>0$. Thus a first dependent column prefix exists. Minimality of $k$ makes the first $k-1$ columns independent, so $\mathrm{rank}{A}_{k-1}=k-1$. Adding one column cannot reduce this rank, while nonzero nullity of $A_k$ implies rank at most $k-1$. HenceFor $k=1$ the earlier prefix is the zero-dimensional empty matrix, and the same argument applies.

Choose any nonzero vector $b$ in the one-dimensional kernel of $A_k$. It gives ${\sum }_{j=1}^k{a}_{ij}{b}_j=0$ for every row. Because no column is zero, $b$ must have at least two nonzero entries: a relation supported at a single index would make that column zero.

Suppose, contrary to the claim, that $A_k\mathrm{diag}({\lambda }_1,\dots ,{\lambda }_k)b=0$. Its kernel is spanned by $b$, so there is a scalar $c$ with ${\lambda }_j{b}_j=c{b}_j$ for every $j$. At the two nonzero entries this gives two equal weights ${\lambda }_j=c$, contradicting their distinctness. Thus the weighted sum is nonzero in at least one row. This proves that distinct diagonal weights break a first column dependence. Some entries of $b$ may be zero; only two nonzero entries are needed.

Assume for contradiction that $n>m$. Apply part b to the matrix of the given relation coefficients, whose columns are nonzero. For its first dependent prefix choose $b_1,\dots ,b_k$ withMultiply the $j$th given vector relation by $b_j$ and sum. Interchanging the finite sums givesThe $w_i$ are a basis, so all $z_i$ must be zero, contradicting part b. Therefore $n\le m$.

Choose a fixed reference basis and let $V,W$ have columns $v_i,w_i$. Both matrices are invertible. The vectors $v_i+\lambda w_i$ are dependent exactly when $\det (V+\lambda W)=0$. This is a polynomial in $\lambda$ of degree $m$, whose leading coefficient is $\det W\ne 0$. A nonzero degree-$m$ polynomial has at most $m$ distinct real roots. Thus there are at most $m$ exceptional parameters. This is the determinant argument for the matrix pencil $V+\lambda W$.