[proofplan] We identify the rank of a matrix with the dimension of the span of its columns. The equation $Ax=b$ is solvable exactly when $b$ is a linear combination of the columns of $A$. The augmented matrix $(A \mid b)$ has as its column space the span of the columns of $A$ together with $b$, so its rank is unchanged exactly when adjoining $b$ does not enlarge that span. [/proofplan]

[step:Express solvability as membership in the column span of $A$] For each $j \in \{1,\dots,n\}$, let $a_j \in k^m$ denote the $j$-th column of $A$. Define the column span of $A$ by $W := \operatorname{span}_k\{a_1,\dots,a_n\} \subseteq k^m$. Define the [linear map](/page/Linear%20Map) associated to $A$ by $L_A: k^n \to k^m$ given by $L_A(x)=Ax$. If $x=(x_1,\dots,x_n) \in k^n$, then matrix multiplication gives $Ax=\sum_{j=1}^n x_j a_j$. Therefore $Ax=b$ for some $x \in k^n$ if and only if $b \in W$. [/step]

[step:Relate the rank of the augmented matrix to adjoining the vector $b$]Let $W_b := \operatorname{span}_k\{a_1,\dots,a_n,b\} \subseteq k^m$. Since $(A \mid b)$ is the matrix whose columns are $a_1,\dots,a_n,b$, the column-space interpretation of rank gives $\operatorname{rank}(A)=\dim_k W$ and $\operatorname{rank}(A \mid b)=\dim_k W_b$.[/step]

[guided]The point of the augmented matrix is that it records the original columns of $A$ and the target vector $b$ in one matrix. We have already named the original column span $W := \operatorname{span}_k\{a_1,\dots,a_n\}$. After appending $b$ as the final column, the resulting column span is $W_b := \operatorname{span}_k\{a_1,\dots,a_n,b\}$. Thus the rank comparison in the theorem is exactly a comparison of two dimensions: $\operatorname{rank}(A)=\dim_k W$ and $\operatorname{rank}(A \mid b)=\dim_k W_b$. So the theorem reduces to a finite-dimensional vector-space question: when does adding one vector $b$ to a spanning set leave the dimension unchanged? The answer is precisely when $b$ was already in the old span.[/guided]

[step:Show that adjoining $b$ preserves dimension exactly when $b$ is already in the span] We prove the elementary dimension fact needed here. Let $V$ be a finite-dimensional [vector space](/page/Vector%20Space) over $k$, let $U \subseteq V$ be a subspace, and let $v \in V$. Then $\dim_k \operatorname{span}_k(U \cup \{v\})=\dim_k U$ if and only if $v \in U$. If $v \in U$, then $\operatorname{span}_k(U \cup \{v\})=U$, so the dimensions are equal. Conversely, suppose $v \notin U$. Let $(u_1,\dots,u_r)$ be a basis of $U$, where $r=\dim_k U$. We claim that $(u_1,\dots,u_r,v)$ is linearly independent. Indeed, if scalars $c_1,\dots,c_r,c \in k$ satisfy $\sum_{i=1}^r c_i u_i + c v = 0$, then $c \neq 0$ would imply $v=-c^{-1}\sum_{i=1}^r c_i u_i \in U$, contradicting $v \notin U$. Hence $c=0$, and then the [linear independence](/page/Linear%20Independence) of $(u_1,\dots,u_r)$ gives $c_1=\cdots=c_r=0$. Thus $(u_1,\dots,u_r,v)$ is linearly independent and spans $\operatorname{span}_k(U \cup \{v\})$, so $\dim_k \operatorname{span}_k(U \cup \{v\})=r+1>\dim_k U$. This proves the equivalence. [/step]

[step:Apply the dimension criterion to the column spans] Apply the preceding dimension fact with $V=k^m$, $U=W$, and $v=b$. Since $W_b=\operatorname{span}_k(W \cup \{b\})$, we obtain $\dim_k W_b=\dim_k W$ if and only if $b \in W$. Using the rank identities from the augmented-matrix step, this says $\operatorname{rank}(A \mid b)=\operatorname{rank}(A)$ if and only if $b \in W$. By the solvability step, $b \in W$ if and only if there exists $x \in k^n$ such that $Ax=b$. Therefore the system $Ax=b$ has a solution if and only if $\operatorname{rank}(A)=\operatorname{rank}(A \mid b)$. This is the desired equivalence. [/step]