Bổ đề trao đổi Steinitz

Chứng minh bằng quy nạp theo $k$, số lượng $w$ đã được trao đổi vào cho tới nay. Với $k=0$, bất đẳng thức $0\leq m$ là tầm thường, và không cần trao đổi nào. Giả sử theo quy nạp rằng $w_1,\dots,w_{k-1}$ đã được trao đổi vào thay cho $k-1$ trong số các $v_i$ ban đầu (đánh lại số để đó là $v_1,\dots,v_{k-1}$), sao cho $\{w_1,\dots,w_{k-1},v_k,\dots,v_m\}$ vẫn sinh ra $V$.

Nếu $k-1$ đã bằng $m$, mọi $v_i$ đã bị dùng hết, nên $\{w_1,\dots,w_{k-1}\}$ một mình sinh ra $V$; nhưng khi đó $w_k\in V$ sẽ là một tổ hợp tuyến tính của $w_1,\dots,w_{k-1}$, mâu thuẫn với tính độc lập tuyến tính của $\{w_1,\dots,w_k\}$. Vậy trường hợp này không thể xảy ra khi $k\leq m$ vẫn cần được chỉ ra cho $k$ hiện tại — chính xác hơn, nó cho thấy $k-1<m$, tức $k\leq m$, ngay lập tức.

Ngược lại $k-1<m$, nên còn ít nhất một $v_j$ (trong số $v_k,\dots,v_m$). Vì $\{w_1,\dots,w_{k-1},v_k,\dots,v_m\}$ sinh ra $V$, viết $w_k$ dưới dạng tổ hợp $w_k=\lambda_1w_1+\cdots+\lambda_{k-1}w_{k-1}+\mu_1v_{j_1}+\cdots+\mu_{m-k+1}v_{j_{m-k+1}}$. Nếu mọi hệ số $\mu_1,\dots$ trên các $v$ còn lại đều bằng $0$, thì $w_k$ sẽ là một tổ hợp chỉ của $w_1,\dots,w_{k-1}$, lại mâu thuẫn với tính độc lập — nên một $v_j$ còn lại nào đó có hệ số khác không.

Giải phương trình đó để tìm $v_j$ (chia cho hệ số khác không của nó), biểu diễn $v_j$ như một tổ hợp của $w_1,\dots,w_k$ và các $v$ còn lại khác. Thay biểu diễn này cho $v_j$ ở mọi nơi nó xuất hiện cho thấy $\{w_1,\dots,w_k\}$ cùng với các $v$ còn lại (trừ $v_j$) vẫn sinh ra $V$ — một $v$ nữa đã được trao đổi thành công thành $w_k$, hoàn tất bước quy nạp và xác nhận $k\leq m$.